Some bounds arising from a polynomial ideal associated to any $t$-design

Year 2020, , 161 - 181, 07.05.2020

William J. Martın Douglas R. Stınson

https://doi.org/10.13069/jacodesmath.729446

Abstract

We consider ordered pairs $(X,\mathcal{B})$ where $X$ is a finite set of size $v$ and $\mathcal{B}$ is some collection
of $k$-element subsets of $X$ such that every $t$-element subset of $X$ is contained in exactly $\lambda$
``blocks'' $B\in \mathcal{B}$ for some fixed $\lambda$. We represent each block $B$ by a zero-one vector $\bc_B$ of
length $v$ and explore the ideal $\mathcal{I}(\mathcal{B})$ of polynomials in $v$ variables with complex coefficients which vanish on
the set $\{ \bc_B \mid B \in \mathcal{B}\}$. After setting up the basic theory, we investigate two parameters related to
this ideal: $\gamma_1(\mathcal{B})$ is the smallest degree of a non-trivial polynomial in the ideal $\mathcal{I}(\mathcal{B})$
and $\gamma_2(\mathcal{B})$ is the smallest integer $s$ such that $\mathcal{I}(\mathcal{B})$ is generated by a set of polynomials
of degree at most $s$. We first prove the general bounds $t/2 < \gamma_1(\mathcal{B}) \le \gamma_2(\mathcal{B}) \le k$.
Examining important families of examples, we find that, for symmetric 2-designs and
Steiner systems, we have $\gamma_2(\mathcal{B}) \le t$. But we expect $\gamma_2(\mathcal{B})$
to be closer to $k$ for less structured designs and we indicate this by constructing infinitely many
triple systems satisfying $\gamma_2(\mathcal{B})=k$.

Keywords

Design, Steiner system, Polynomial ideal, Bounds

References

• [1] A. E. Brouwer, The Witt designs, Golay codes and Mathieu groups, Unpublished notes, https: //www.win.tue.nl/~aeb/2WF02/Witt.pdf.
• [2] D. Bryant, D. Horsley, A proof of Lindner’s conjecture on embeddings of partial Steiner triple systems. J. Combin. Des. 17 (2009) 63–89.
• [3] A. R. Calderbank, P. Delsarte, Extending the t–design concept, Trans. Amer. Math. Soc. 338 (1993) 941–952.
• [4] P. J. Cameron, Near–regularity conditions for designs, Geom. Dedicata 2 (1973) 213–223.
• [5] M. Conder, C. D. Godsil, The symmetric group as a polynomial space, Combinatorial and Graph- Theoretical Problems in Linear Algebra (R.A. Brualdi, S. Friedland and V. Klee, eds.) IMA Vol. Math. Appl. 50 (1993) 219–227.
• [6] D. Cox, J. Little, D. O’Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (4th ed.), Springer-Verlag Undergraduate Texts in Mathematics, Springer-Verlag, New York, 2015.
• [7] E. Croot, V. F. Lev, P. P. Pach, Progression–free sets in $\\mathbb{Z}_4^n$ are exponentially small, Ann. of Math. 185 (2017) 331–337.
• [8] P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Reports Suppl. No. 10, 1973.
• [9] P. Delsarte, Hahn polynomials, discrete harmonics, and t-designs, SIAM J. Appl. Math. 34(1) (1978) 157–166.
• [10] D. S. Dummit, R. M. Foote, Abstract Algebra (3rd ed.), John Wiley and Sons, Hoboken, 2004.
• [11] J. S. Ellenberg, D. Gijswijt, On large subsets of $F_q^n$ with no three-term arithmetic progression, Ann. of Math. 185 (2017) 339–343.
• [12] A. D. Forbes, M. J. Grannell, T. S. Griggs, Configurations and trades in Steiner triple systems, Australas. J. Combin. 29 (2004) 75–84.
• [13] W. Fulton, Algebraic Curves: An Introduction to Algebraic Geometry, Advanced Book Classics, Addison-Wesley, Reading, Mass., 1989.
• [14] C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
• [15] G.-M. Greuel, G. Pfister, H. Schönemann, Singular 3.0.2. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern, 2005.
• [16] P. Keevash, The existence of designs, Preprint v.3, (2019) arXiv:1401.3665.
• [17] W. J. Martin, C. L. Steele, On the ideal of the shortest vectors in the Leech lattice and other lattices, J. Algebraic Combin. 41(3) (2015) 707–726.
• [18] W. J. Martin, An ideal associated to any cometric association scheme, In preparation.
• [19] H. Maruri–Aguilar, H. P. Wynn, Algebraic Method in Experimental Design, pp. 415–454. In: Handbook of Design and Analysis of Experiments (1st Ed.) Chapman & Hall/CRC Handbooks of Modern Statistical Methods, Boca Raton, 2015.
• [20] H. M. Möller, On the construction of cubature formulae with few nodes using Groebner bases, pp. 177–192 in: Numerical integration (Halifax, N.S., 1986) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 203, Reidel, Dordrecht, 1987.
• [21] D. K. Ray-Chaudhuri, R. M. Wilson, On t-designs, Osaka J. Math. 12(3) (1975) 737–744.
• [22] D. R. Stinson, Y. J. Wei, Some results on quadrilaterals in Steiner triple systems, Discrete Math. 105(1–3) (1992) 207–219.
• [23] D. R. Stinson, Combinatorial Designs: Constructions and Analysis, Springer, New York, 2004.
• [24] T. Tao, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory. EMS Surv. Math. Sci. 1 (2014) 1–46.