Some Bounds Arising From a Polynomial Ideal Associated to Any t-Design

  • William J. Martin
  • Douglas R. Stinson
Keywords: Design, Steiner system, Polynomial ideal, Bounds

Abstract

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

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 FnqF_q^nF​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.
Published
2020-05-07
Section
Articles