ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.729446 J. Algebra Comb. Discrete Appl. 7(2) • 161–181 Received: 21 January 2019 Accepted: 4 December 2019 Journal of Algebra Combinatorics Discrete Structures and Applications Some bounds arising from a polynomial ideal associated to any t-design∗ Research Article William J. Martin, Douglas R. Stinson 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 λ “blocks” B ∈B for some fixed λ. 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: γ1(B) is the smallest degree of a non-trivial polynomial in the ideal I(B) and γ2(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 < γ1(B) ≤ γ2(B) ≤ k. Examining important families of examples, we find that, for symmetric 2-designs and Steiner systems, we have γ2(B) ≤ t. But we expect γ2(B) to be closer to k for less structured designs and we indicate this by constructing infinitely many triple systems satisfying γ2(B) = k. 2010 MSC: 05B05, 05E30, 13F20 Keywords: Design, Steiner system, Polynomial ideal, Bounds 1. Introduction Let X be a finite set of size v and consider a k-uniform hypergraph (X,B) with vertex set X and block (hyperedge) set B. We aim to study polynomial functions on X which vanish on each element of B so that B may be viewed as the variety of some naturally defined ideal of polynomials in v variables. In order to do so, we identify each block B ∈ B with a 01-vector cB, with entries indexed by the elements ∗ The first author’s research is supported by a grant from the US National Science Foundation. The second author’s research is supported by NSERC discovery grant RGPIN-03882. William J. Martin (Corresponding Author); Department of Mathematical Sciences and Department of Com- puter Science, Worcester Polytechnic Institute, 100 Institute Road, Worcester, MA 01609, USA (email: mar- tin@wpi.edu). Douglas R. Stinson; David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada (email: dstinson@uwaterloo.ca). 161 https://orcid.org/0000-0002-2027-5859 https://orcid.org/0000-0001-5635-8122 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 of X, whose ith entry is equal to one if i ∈ B and equal to zero otherwise. In other words, cB is the Bth column of the point-block incidence matrix, A, of the hypergraph. In this paper we work in characteristic zero and consider the polynomial ring R = C[x1, . . . ,xv]. The evaluation map ε : R→ CB given by ε(f) (B) = f(cB) is a ring homomorphism and its kernel is the ideal of all polynomials in v variables which evaluate to zero on each block of the hypergraph. Denoting this kernel by I, we see that I is the ideal of the finite variety {cB | B ∈ B} and we write I = I(B). Our goal in this paper is to explore connections between this ideal I and the hypergraph (X,B). Our primary question involves the identification of good generating sets G for I based on the combinatorial structure of the design (X,B). We are not concerned here with the actual size of the generating set; in fact, we prefer a set of polynomials preserved by the automorphism group of the design. By “good” here, we mean principally that polynomials in the generating set are all of low degree. But we also seek polynomials that shed light on properties of the design. 1.1. Background and related work Algebraic geometry has a long history in the theory of error-correcting codes. We also have a theory of spherical codes and designs that involves the evaluation of multivariate polynomials at finite sets of points on the unit sphere. Möller [20] constructs good quadrature rules for spherical integration by choosing zero sets of well-chosen families of polynomials. Conder and Godsil [5] studied the symmetric group as a polynomial space. The standard module of the Johnson association scheme J(v,k) can be identified with polynomials of degree at most k in v variables in such a way that the polynomials of a given maximum degree j correspond to a sum of eigenspaces V0 + V1 + · · ·+ Vj. This approach, which is implicit in [8] is worked out in more detail in a later paper of Delsarte [9] (see also [3]). These phenomena motivated Martin and Steele [17] to consider the ideal of polynomials that vanish on the shortest vectors of certain lattices. In work in progress, Martin [18] extends this to attach an ideal to any cometric association scheme by viewing the columns of the Q-polynomial generator E1 in the Bose-Mesner algebra as a finite variety. Several important examples are connected to combinatorial t-designs and – when disentangled from the language of association schemes – the problem of determining generating sets for the ideals of those association schemes reduces to the problem we address here. The “polynomial method” in combinatorics [24] is a powerful tool for deriving bounds on the size of combinatorial objects and for proving non-existence of extremal objects. In particular, a recent break- through by Croot, Lev and Pach [7] (see also [11]) has stimulated interest in collections of multivariate polynomials that vanish on some configuration in a finite vector space. Here, we work in characteristic zero and are interested in how the ideal we obtain is related to the structure of the design. By contrast, the authors of [7, 11] work over fields of positive characteristic. To see the connection, we note that, since our zero set lies in Zv, the polynomial generators g ∈G may always be chosen from Z[x]. So application of the reduction Z → Zp maps the ideal 〈G〉 ⊆ Z[x] into the ideal of the same finite variety considered modulo p. It will be an interesting follow-up task to determine when the image under this map is the full ideal in positive characteristic. We have recently learned of previous Gröbner basis approaches to algebraic aliasing in the statistical design of experiments. Once a useful basis is chosen for the space of polynomial functions on the elements of the design, higher order effects can be mapped to more elementary interactions between factors. For a recent survey, see [19], with the caveat that the terminology used there differs from the terminology in this paper. 1.2. The trivial ideal We pause to introduce our notation for the standard operations of elementary algebraic geometry. (See, e.g., [10, Chapter 15] for a basic introduction.) For a set S ⊆ Cv, we let I(S) denote the ideal of all polynomials in C[x] := C[x1, . . . ,xv] that vanish at each point in S. And if G is any set of 162 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 polynomials in C[x1, . . . ,xv], we denote by Z(G) the zero set of G, the collection of all points c in Cv which satisfy f(c) = 0 for all f ∈G. Note that, when S is finite, we have Z(I(S)) = S. In the opposite direction, for any ideal J of polynomials, the Nullstellensatz (see, e.g., [13, p21], [6, p179]) informs us that I(Z(J)) = Rad(J), where Rad(J) denotes the radical of ideal J, the ideal of all polynomials g such that gn ∈ J for some positive integer n. A radical ideal is an ideal which is already closed under this process: Rad(J) = J. Our first example to consider is the complete uniform hypergraph (X,Kvk). Lemma 1.1. Let X be a finite set of size v ≥ k and let Kvk = ( X k ) consist of all k-subsets of X. Let G0 = {x1 + · · ·+ xv −k}∪{x2i −xi | 1 ≤ i ≤ v}. (1) Then I(Kvk) = 〈G0〉 and Z(〈G0〉) = {cB | B ∈K v k}. Proof. One easily checks that each cB is a common zero of the polynomials in G0. Conversely, any point in Cv which is a zero of each polynomial in G0 must be a 01-vector with exactly k ones. In order to verify that G0 generates the full ideal, we check that the Zariski tangent space at each point is full- dimensional. Let B ⊂ X be a k-set; evaluating the gradient ∇f of f(x) = x2j −xj at cB we obtain ±ej where ej is the standard basis vector with a one in position j and all other entries zero. So the Jacobian of the set G0 of v + 1 polynomials in v variables evaluated at cB takes the form Jac(G0,cB) = [ ∂fi ∂xh ∣∣∣∣∣cB ] h,i =   1 ±1 0 · · · 0 1 0 ±1 · · · 0 ... ... 1 0 0 · · · ±1   which clearly has column rank equal to v. This guarantees that each cB is a simple zero of 〈G0〉 and so the ideal is indeed radical. It now follows from the Nullstellensatz that I({cB | B ∈Kvk}) = I(Z(〈G0〉)) = Rad(〈G0〉) = 〈G0〉. See Section 3 for details of these last calculations. 2. Two parameters In this paper, once we fix v and k, every ideal will contain the ideal we have just considered. We call this the trivial ideal and denote T = 〈G0〉 = 〈 x1 + · · ·+ xv −k, x21 −x1, . . . ,x 2 v −xv 〉 . (2) For any k-uniform hypergraph (X,B) on v points, the ideal I(B) := I({cB | B ∈B}) will contain T and a polynomial f ∈I(B) will be called non-trivial if f 6∈ T and trivial otherwise. To each C ⊆ {1,2, . . . ,v} we associate the monomial xC = ∏ j∈C xj and note that, for a block B ∈B, the value of xC at point cB is one if C ⊆ B and zero otherwise. A k-uniform hypergraph (X,B) is a t-(v,k,λ) design (or a block design of strength t) if, for every t-element subset T ⊆ X of points, there are exactly λ blocks B ∈B with T ⊆ B (so ∑ B∈B f(cB) = λ whenever f(x) = x T for some t-set T ⊆ X). Every t-(v,k,λ) design is an s-(v,k,λs) design for each s ≤ t where λs ( k−s t−s ) = λ ( v−s t−s ) . The following characterization of t-designs is well-known (see, for example, Godsil [14, Cor. 14.6.3]). Lemma 2.1 (Cf. Delsarte [9, Theorem 7]). Let X be a set of size v and let (X,B) be a k-uniform hypergraph defined on X with corresponding vectors cB (B ∈ B) as defined above. Then (X,B) is a t-design on X if and only if the average over B of any polynomial f(x) in v variables of total degree at most t is equal to the average of f(x) over the complete uniform hypergraph Kvk defined on X. 163 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Proof. Let C ⊆ X with |C| = s ≤ t. Exactly ( v−s k−s ) elements of Kvk contain C so the average value of f(x) = xC over {cB | B ∈Kvk} is( v −s k −s )/( v k ) = k(k −1) · · ·(k −s + 1) v(v −1) · · ·(v −s + 1) = λs λ0 which is exactly the average of f(x) over the block set B. So the result holds for monomials. But every polynomial in v variables of total degree at most t is a linear combination of such monomials, so the result holds for these as well by linearity. Given (X,B), we seek combinatorially meaningful generating sets for I(B). Two polynomials f(x) and g(x) have the same value at every point cB, B ∈B if and only if their difference belongs to the ideal I(B). For example, f(x) = x2j and g(x) = xj take the same value on every 01-vector so x 2 j −xj belongs to the ideal of any design. We say f(x) is a multilinear polynomial in v variables if f is linear in each xi: i.e., each monomial with non-zero coefficient in f is a product of distinct indeterminates. Modulo the trivial ideal T , each polynomial in C[x1, . . . ,xv] is equivalent to some (not necessarily unique) multilinear polynomial with zero constant term. With a preference for polynomials of smallest possible degree, we define two fundamental parameters. Definition 2.2. Let (X,B) be a non-empty, non-complete k-uniform hypergraph on vertex set X = {1, . . . ,v} with corresponding ring of polynomials R = C[x1, . . . ,xv]. Let I(B) and T be defined as above. Define γ1(B) = min{deg f | f ∈I(B), f 6∈ T } and γ2(B) = min{max{deg f : f ∈G} | G ⊆R, 〈G〉 = I(B)} . So γ1(B) is the smallest possible degree of a non-trivial polynomial that vanishes on each block and γ2(B) is the smallest integer s such that I(B) admits a generating set all polynomials of which have degree at most s. Obviously, γ1(B) ≤ γ2(B); designs satisfying equality here are particularly interesting. Theorem 2.3. If (X,B) is a t-design (t ≥ 2) and f ∈I(B) is non-trivial, then deg f > t/2. So, for any non-trivial t-design (X,B), γ1(B) ≥ (t + 1)/2. Proof. Suppose F ∈ I(B) has degree at most t/2. Write F(x) = f(x) + ig(x) where f,g ∈ R[x] each have degree at most t/2. Since the entries of each cB are real, it is clear that f,g ∈ I(B). Then f2 ∈ I(B) is a non-negative polynomial of degree at most t. By Lemma 2.1, its average over B is zero hence its average over Kvk is also zero. Since f 2 is everywhere non-negative, it must evaluate to zero on the incidence vector cB of every k-set B. So it belongs to the ideal I(Kvk). Since this ideal is radical and contains f2, it also contains f. By Lemma 1.1, f must be trivial. The same argument applies to g and, hence, to F. Remark 2.4. The same sort of reasoning used in this proof shows that I(B) admits a vector space basis, even a generating set, of polynomials with integer coefficients. Let F be a polynomial which vanishes on B and let {ζ1 . . . ,ζm} ⊆ C be a basis for the subspace of C, as a vector space over Q, that contains all the coefficients of F. Then there exist unique polynomials F1, . . . ,Fm in Q[x] with F = ∑ h ζhFh. Since each cB is a vector with integer entries, the fact that F evaluates to zero at cB implies that each Fh also vanishes at that point. So, scaling appropriately, we may assume each generator belongs to Z[x]. A standard result in the theory of designs (see; Cameron [4] and Delsarte [8, Theorem 5.21]) is the fact that a t-design with s distinct block intersection sizes satisfies t ≤ 2s. We now show that Theorem 2.3 implies a stronger result, which we believe is new. 164 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Let C ⊆ X with characteristic vector c and suppose {|C ∩B| : B ∈ B} = {i1, . . . , is}. Then every cB for B ∈B is a zero of the degree s zonal polynomial F(x) = (c ·x− i1) · · ·(c ·x− is). Of course, if |C| is sufficiently small, this polynomial belongs to the trivial ideal. Corollary 2.5. Let (X,B) be a t-design and let C1, . . . ,C` ⊆ X and {i1,1, . . . , i1,s1, i2,1, . . . , i`,s`} be a multiset of integers such that, for every B ∈B there exist 1 ≤ h ≤ ` and 1 ≤ j ≤ sh with |B∩Ch| = ih,j. If there exists some k-set S 6∈ B with |S∩Ch| 6∈ {ih,1, . . . , ih,sh} for all h = 1, . . . ,`, then γ1(B) ≤ s1+· · ·+s` hence s1 + · · ·+ s` > t/2. Proof. For Y ⊆ X, define 01-vector χY by (χY )a = 1 if a ∈ Y and (χS)a = 0 otherwise. E.g., χB = cB when B is a block. Consider the product of ` zonal polynomials F(x) = ∏̀ h=1 sh∏ j=1 ( χCh ·x− ih,j ) . By hypothesis, F(cB) = 0 for every B ∈ B. Since F(χS) 6= 0, F is non-trivial. So, by Theorem 2.3, deg F > t/2. Lemma 2.6. Let (X,B) be a t-(v,k,λ) design. Let s denote the smallest integer such that ( v s ) > |B|. Then γ1(B) ≤ s. Proof. The vector space of functions on Kvk representable by multilinear polynomials in R with zero constant term and total degree at most s has dimension ( v s ) . For the chosen value of s, there exists a non-zero multilinear polynomial f(x) ∈ R, of total degree at most s, which vanishes on each element of B. (We have |B| equations and ( v s ) unknowns.) Being multilinear with zero constant term, f(x) is non-trivial with degree at most s. We finish this section with two instructive examples. Example 2.7. Let us construct the ideal of the Fano plane. Let X = Z7 and take B = {{0,1,3},{1,2,4},{2,3,5},{3,4,6},{4,5,0},{5,6,1},{6,0,2}} . Starting from G0, let us build up a meaningful generating set for I(B). The unique triple in B containing both 0 and 1 also contains 3; this combinatorial condition may be encoded as x0x1 − x0x1x3 ∈ I(B). Alternatively, including the quadratic polynomial x0x1 − x0x3 in a generating set G for our ideal also guarantees that any vector c ∈Z(〈G〉) with c0 = 1 and c1 = 1 must have c3 = 1 as well. Up to sign, there are ( 7 2 ) quadratic generators of this form and these, together with those in G0, generate the full ideal. Example 2.8. With X = {1, . . . ,9} and B = {{1,2,3},{4,5,6},{7,8,9}}, a 1-design, we find generating set G = G0 ∪{x1 −x2, x1 −x3, x4 −x5, x4 −x6, x7 −x8, x7 −x9} . While we will not see further examples where the ideal is generated by G0 and linear polynomials, we will see that the difference of two monomials appears again as a useful tool. 3. Radical ideals In this section, we deal with a technicality which arises as we compute ideals of finite sets. We show here that every ideal containing the trivial ideal is radical, thereby eliminating any further need to check this property. 165 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Given a finite set S of points in Cv, it is often easy to come up with polynomials that vanish at each of those points and, with a bit of work, we might find a generating set G for some ideal J = 〈G〉 whose zero set is exactly S: Z(〈G〉) = S. Hilbert’s Nullstellensatz then tells us that I(S) = I(Z(J)) = Rad(J), (3) the radical of of ideal J given by Rad(J) = {f ∈R | (∃n ∈ N) (fn ∈ J)} . The ideal J is a radical ideal if Rad(J) = J. Our goal then is achieved in three steps: given a finite set of points S, find a nice set G of small-degree polynomials that vanish on S; verify that Z(G) = S and nothing more; verify also that 〈G〉 is a radical ideal. In this section, we discuss ways to achieve this last step. If J is an ideal in C[x1, . . . ,xv] with finite zero set Z(J) = S, then C[x]/J is a finite-dimensional complex vector space and its dimension is equal to the sum of the multiplicities of all the zeros of I, dim C[x]/J = ∑ c∈S mult(c). The coordinate ring of a variety S ⊆ C v is defined as the quotient ring C[x]/I(S) and this is naturally identified with the ring of “polynomial functions” on the set S. If J is an ideal in C[x] with finite zero set Z(J) = S, then it is well-known (e.g., Section 5.3, Proposition 7 in [6]) that ∑ c∈S mult(c) = dim C[x]/J ≥ dim C[x]/Rad(J) = |S| (4) where mult(c) is the multiplicity of point c as a zero of J. This proves Proposition 3.1. With notation as above: (i) If S ⊆Z(J), then dim C[x]/J ≥ |S|; (ii) If J is a radical ideal and Z(J) = S is finite, then J = I(S); (iii) If J is an ideal in C[x] with finite zero set Z(J) ⊇S and the coordinate ring C[x]/J has dimension equal to |S|, then the ideal J is radical, Z(J) = S, each point of S is a smooth point (multiplicity one), and I(S) = J. � Let G = {f1, . . . ,f`} be a generating set for ideal J ⊆ C[x1, . . . ,xv]. The Jacobian of the system {f1(x) = 0, . . . ,f`(x) = 0} of polynomial equations evaluated at point c ∈ Cv is the v×` matrix Jac(G,c) with (i,j)-entry equal to ∂fj ∂xi ∣∣∣ c , the partial derivative ∂fj/∂xi evaluated at point c. Since we are dealing only with zero-dimensional varieties in this paper, we say the point c is smooth if Jac(G,c) has column rank v, so that the Zariski tangent space is zero-dimensional. A smooth point has multiplicity one. So another way to show that the ideal J is radical is to check that, at each point c of its zero set, the Jacobian Jac(G,c) has full row rank where G is some generating set for J. Proposition 3.2. Let G ⊆ C[x] be any set of polynomials such that G0 ⊆ G (cf. Equation (1)). Then 〈G〉 is a radical ideal. Proof. In the proof of Lemma 1.1, we proved that the Jacobian Jac(G0,cB) of G0 has column rank equal to v at any characteristic vector cB of any k-set B. Since Jac(G0,cB) is a submatrix of Jac(G,cB), this latter Jacobian also has full row rank and each point of the finite variety Z(G) is smooth. We note here that this approach also provides another proof of the fundamental bound of Ray- Chaudhuri and Wilson. Lemma 3.3. Let S ⊆ {1, . . . ,v} and t ≥ |S|. If I is an ideal containing T , then in the quotient ring C[x]/I, the coset xS + I is expressible as a linear combination of cosets xT + I where |T | = t. 166 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Proof. Assume t = |S|+ 1. Since 1 + I = 1 k ∑ j xj + I we have xS + I = ∏ s∈S xs + I = 1 k ∑ j xj ∏ s∈S xs + I = ( t−1 k xS + I ) +   ∑ S⊆T |T|=t xT   + I and we may solve for xS + I. Theorem 3.4. If (X,B) is a 2s-(v,k,λ) design, then |B|≥ ( v s ) . Proof. Since the coordinate ring C[x]/I(B) has dimension |B| and the monomials {xC : |C| = s} represent linearly independent cosets in this quotient ring, we have |B|≥ ( v s ) . This language differs from that employed by Ray-Chaudhuri and Wilson. Consider the ( v s ) × |B| matrix A(s) with rows indexed by all C ⊆ X with |C| = s, with columns indexed by the set B of blocks of a t-(v,k,λ) design, and (C,B)-entry equal to one if C ⊆ B and equal to zero otherwise. The proof of Theorem 1 in [21] establishes that the columns cB of A(s) span the space R( v s). The celebrated bound follows immediately for even t and, for odd t, one obtains |B| ≥ 2 ( v s ) whenever B is the block set of a t-(v,k,λ) design with t = 2s+ 1 by applying this idea to both the derived design and the residual design. As we will use the fact later, we record it here as a lemma. Lemma 3.5. Let (X,B) be a t-(v,k,λ) design with t ≥ 2s and consider the incidence matrix A(s) of s-subsets of X versus blocks as defined in the previous paragraph. Then the column rank of A(s) is exactly( v s ) . � 4. Steiner systems and partial designs For a subset C ⊆ X and f ∈ R, define f(C) in the obvious way, by setting xi = 1 if i ∈ C and xi = 0 if i 6∈ C (1 ≤ i ≤ v), and then evaluating f(χC) where χC = (x1, . . . ,xv). We want to construct small-degree generating sets G for the ideal I = I(B) where B is the block set of our design (X,B). We assume throughout that G contains G0 so that 〈G〉 contains the trivial ideal T . Every zero of this latter ideal is a 01-vector with exactly k ones. As we choose the remaining generators, we need only search for multilinear polynomials: each monomial xe11 · · ·x ev v appearing in f(x) has all ei ∈ {0,1}. It is clear that the automorphism group of a design (X,B) acts on the ideal I(B) by permuting indeterminates; rather than minimizing |G|, we typically show a preference for sets of generators invariant under this action. Recall, for a subset C ⊆ X, we have xC = ∏ i∈C xi. Next define, for an integer j ≤ |C|, the polynomial xC,j = ∑ J⊆C,|J|=j xJ. (This is a certain symmetric function — the elementary symmetric polynomial of degree j — in the variables {xi | i ∈ C}.) For example, xC,|C| = xC. Since the trivial ideal contains ( xX,1 −k )j for all j it 167 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 also contains xX,j − ( k j ) for 1 ≤ j ≤ k. For example, modulo 〈G0〉, ( xX,1 −k )2 = v∑ i=1 x2i + 2  ∑ i 5 has been recently resolved in spectacular fashion by Keevash [16]. 168 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Theorem 4.3. Let (X,B) be any t-(v,k,1) design. For a block B ∈ B and any t-element subset T contained in B, define (as in (5)) gB,T (x) = x B,t − ( k t ) xT . Then (i) I(B) is generated by G0 ∪{gB,T (x) : B ∈B,T ⊆ B, |T | = t}; (ii) γ2(B) ≤ t. Proof. In view of Theorem 4.2, we can assume that t < k. Consider the generating set G = G0 ∪{gB,T (x) : B ∈B,T ⊆ B, |T | = t} . From Lemma 4.1, if B ∈ B then gB,T (B) = 0 for each t-subset T of B, while if B′ ∈ B, B′ 6= B, then |B′ ∩B| ≤ t−1 and it follows that gB′,T (B) = 0 for any t-subset T of B′. Now suppose that |C| = k, C 6∈ B, and choose T ⊆ C, |T | = t. There is a block B ∈B with T ⊆ B. Then gB,T (C) 6= 0 from Lemma 4.1 because t ≤ |B ∩C| ≤ k −1. So Z(G) = {cB | B ∈B}. By Proposition 3.2, 〈G〉 is a radical ideal. So Equation (3) gives I(B) = 〈G〉 and the result follows. Remark 4.4. Let B be a block of the t-(v,k,1) design (X,B) and let T and T ′ be two t-element subsets of B. Then it is easy to see that I(B) contains xT −xT ′ . Since each of the generators gB,T in the above theorem is expressible as a sum of polynomials of this form, we have a perhaps simpler set of generators G0 ∪ { xT −xT ′ | T,T ′ ⊆ B ∈B, |T | = |T ′| = t } for the ideal. Question: Do the cosets { xB,t +I(B) | B ∈B } form a basis for the coordinate ring C[x]/I(B) in this case? Next, we describe a couple of variations of Theorem 4.3. A partial t-(v,k,1)-design is a k-uniform hypergraph in which any t-subset occurs in at most one block. A partial t-(v,k,1)-design, (X,B), is maximal if there does not exist a k-subset C ⊆ X, C 6∈ B such that (X,B∪{C}) is a partial t-(v,k,1)- design. Corollary 4.5. For any maximal partial t-(v,k,1)-design (X,B), γ2(B) ≤ t. Proof. As we employ the same generating set as in the proof of Theorem 4.3, we need only check that Z(〈G〉) = B. As before, we have that gB,T (B′) = 0 for all blocks B,B′ ∈ B and all t-subsets T of B. Now suppose that |C| = k, C 6∈ B. Because (X,B) is a maximal partial t-(v,k,1)-design, it is possible to choose T ⊆ C, |T | = t such that there is a block B ∈B with T ⊆ B. Then gB,T (C) 6= 0 as before. By a slight extension of our construction, we do not require the partial t-(v,k,1)-design to be maximal. Theorem 4.6. For any partial t-(v,k,1)-design (X,B), γ2(B) ≤ t. Proof. If (X,B) is maximal, then Corollary 4.5 yields the desired result, so assume (X,B) is not maximal. Let T = {T ⊆ X : |T | = t,(∀B ∈B)(T 6⊆ B)} . 169 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Now consider the generating set G = G0 ∪{gB,T (x) : B ∈B,T ⊆ B, |T | = t}∪{xT : T ∈ T}. Since xT evaluates to zero on every block, we still have B ⊆ Z(〈G〉). But if C is a k-set not belonging to B, either B∪{C} is again a partial t-design or some t-subset T of C is contained in some block B. In the latter case, gB,T (C) 6= 0 as above; in the former case, every t-subset of C belongs to T so we can take any t-subset T ⊆ C and, with f(x) = xT ∈G, we have f(C) 6= 0. So Z(〈G〉) = B and the rest of the proof follows just as before. This result gives us another upper bound on γ2 for general t-designs. Corollary 4.7. Let (X,B) be a t-(v,k,λ) design with |B∩B′| < s for every pair B,B′ of distinct blocks. Then γ2(B) ≤ s. � 5. Symmetric balanced incomplete block designs A 2-(v,k,λ) design is traditionally called a balanced incomplete block design (BIBD) [23, Chapter 1]. Fisher’s inequality states that, for any such 2-design, we have |B| ≥ |X| since, for t ≥ 2, the point-block incidence matrix A has rank v. A 2-design with equally many blocks and points is called a symmetric 2- design. While Theorem 2.3 implies here that γ1(B) > 1, we may use the invertibility of A to obtain more information in this case. If f(x) = w0 + ∑v i=1 wixi ∈I(B) then w = (w1, . . . ,wv) satisfies w >A = −w01 and w + w0 k 1 lies in the left nullspace of A. So w is a scalar multiple of 1 and f is trivial. The quadratic case is more interesting. Let ri denote row i of matrix A. For any two distinct points i,j ∈ X, the entrywise product ri ◦rj is expressible as a linear combination of the rows of A. Say ri ◦rj = v∑ h=1 whrh . Then the polynomial f(x) given by f(x) = xixj − v∑ h=1 whxh is easily seen to belong to I(B): for a block B indexing column ` of matrix A, we have f(cB) = Ai`Aj` − ∑v h=1 whAh` = 0. In fact, we may determine the coefficients wh explicitly to obtain a nice generating set for our ideal. Theorem 5.1. Let (X,B) be any non-trivial symmetric 2-(v,k,λ) design. For each pair i,j of distinct points from X define fi,j(x) = (k −λ)xixj − ∑ i,j∈B∈B xB,1 + λ2. Then (i) I(B) is generated by G0 ∪{fi,j | i,j ∈ X}; (ii) γ1(B) = γ2(B) = 2; (iii) the coordinate ring C[x]/I(B) admits a basis consisting of cosets {xi +I(B) | 1 ≤ i ≤ v}. 170 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Proof. Assume (X,B) is a 2-design with |B| = v and incidence matrix A. As AA> = (k −λ)I + λJ, we see that the inverse of our incidence matrix is A−1 = 1 k −λ ( A> − λ k J ) . Letting ri denote the ith row of A (i ∈ X), observe that ri ◦ rj is a 01-vector of length v with λ entries equal to one. So ri ◦rj = w>A gives w> = (ri ◦rj)A−1 = 1 k −λ ∑ i,j∈B c>B − λ2 k(k −λ) 1> with entries wh = −λ2 k(k −λ) + 1 k −λ |{B ∈B | h,i,j ∈ B}| ; that is, I(B) contains the quadratic polynomial xixj + 1 k −λ ∑ i,j∈B xB,1 − λ2 k(k −λ) xX,1. As xX,1 takes value k on each cB, this shows that ideal I contains fi,j(x) for every pair i,j of distinct points. Set G = G0 ∪{fi,j | i,j ∈ X} and consider I = 〈G〉. The dimension of the quotient ring C[x]/I is v since every monomial of degree two is congruent, modulo 〈G〉, to some polynomial of degree one1. Since we have dim C[x]/I = |B|, we use Proposition 3.1(iii) to see that Z(I) = B and each zero has multiplicity one. It then follows that I = I(B) and the cosets of the form xixj + I(B) (i 6= j) form a basis as claimed. Example 5.2. Consider the case where (X,B) is a symmetric 2-(v,k,2) design. Let X = {i : 1 ≤ i ≤ v} be the set of points and let B = {Br : 1 ≤ r ≤ v} be the set of blocks in the design. Let i,j be any two distinct points. There are two blocks that contain i and j, say Br and Bs. Note that Br ∩Bs = {i,j}. Denote the symmetric difference by Zi,j = Br ∪Bs \{i,j} and define fi,j(x) = (k −2)xixj + 4−2(xi + xj)− ∑ h∈Zi,j xh. Then I(B) is generated by xX,1 −k, xi(xi −1) (1 ≤ i ≤ v) and the polynomials fi,j(x). Theorem 5.3. Suppose that (X,B) consists of the points and e-dimensional subspaces of PG(d,q), where 1 ≤ e < d. Let L denote the set of all lines (1-dimensional subspaces) of PG(d,q). For every line L in L and every 2-element subset J ⊆ L define gL,J(x) = xL,2 − ( q+1 2 ) xJ. Then (i) I(B) is generated by G := G0 ∪{gL,J | L ∈L,J ⊆ L, |J| = 2}; (ii) γ1(B) = γ2(B) = 2; 1 We choose some monomial ordering for the ring C[x] which refines the partial order by total degree. 171 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 (iii) the coordinate ring C[x]/I(B) admits a basis consisting of cosets {xi +I(B) | 1 ≤ i ≤ v}. Proof. Here we have v = (qd+1 − 1)/(q − 1) and k = (qe+1 − 1)/(q − 1). Every line of PG(d,q) contains q + 1 points. Suppose B is an e-dimensional subspace of PG(d,q) and L is a line. Then |L∩B| ∈ {0,1,q + 1}. In each case, gL,J(B) = 0 for any 2-element J ⊆ L by Lemma 4.1. A subset of points of PG(d,q) that intersects any line in 0,1 or q + 1 points is necessarily a subspace of PG(d,q). Suppose that |C| = k but C is not an e-dimensional subspace of PG(d,q). Then there exists a line L such that |L∩C| 6∈ 0,1,q + 1. In this case, gL,J(C) 6= 0 by Lemma 4.1. We have shown that the ideal generated by G is a radical ideal with zero set B, so we are done by Proposition 3.1(ii). Remark 5.4. Clearly we can build a much smaller generating set than our choice of G by selecting just one pair J of points in each line. We instead prefer here to choose a set G of polynomials which is invariant under the automorphism group of the design. 6. Triple systems Identifying each square-free monomial xC with the set C, the multilinear polynomials with real coefficients are in bijective correspondence with the real-valued functions on the Boolean lattice. For multilinear f write c(f) = (fD : D ⊆{1, . . . ,v}) where f(x) = ∑ D fDx D. Suppose that C ⊆ X and 0 ≤ s ≤ |C|. The s-incidence vector of C, denoted δ = δs(C), is the vector of length w = ∑s i=0 ( v i ) , whose coordinates correspond to the subsets of X of cardinality at most s, defined by δJ = { 1 if J ⊆ C 0 otherwise, where |J| ≤ s. Now suppose that f is a multilinear polynomial in x1, . . . ,xv of degree at most s. The vector of coefficients of f, denoted c = c(f), is also a w-dimensional vector whose coordinates correspond to the subsets of X of cardinality at most s. The following lemma is obvious. Lemma 6.1. If f is a polynomial of degree at most s and C ⊆ X, then f(C) = δ · c, where δ = δs(C) and c = c(f). � Example 6.2. Suppose that X = {1,2,3,4,5}, C = {1,2,3} and s = 2. Let f = 1 + x1 + 2x2 −3x3 + 4x4 −x1x2 + +3x1x5 + 2x2x3 −3x3x5. Then c(f) = (1,1,2,−3,4,0,−1,0,0,3,2,0,0,0,−3,0) and δs(C) = (1,1,1,1,0,0,1,1,0,0,1,0,0,0,0,0). It is easy to verify that f(C) = 1 + 1 + 2−3−1 + 2 = 2. 172 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Theorem 6.3. Suppose that (X,B) is a 2-(v,3,2) design such that {{1,2,3},{1,4,5},{2,4,6},{3,5,6},{1,2,4},{1,3,5},{2,3,6}}⊆B, but {4,5,6} 6∈B. Then γ2(B) = 3. Proof. By Theorems 2.3 and 4.2, we have 2 ≤ γ2(B) ≤ 3. We now show γ2(B) > 2. Denote B1 = {1,2,3}, B2 = {1,4,5}, B3 = {2,4,6}, B4 = {3,5,6}, B5 = {1,2,4}, B6 = {1,3,5}, B7 = {2,3,6} and C = {4,5,6}. For s = 2, it is easy to verify that δs(B1) + δ s(B2) + δ s(B3) + δ s(B4) = δ s(B5) + δ s(B6) + δ s(B7) + δ s(C). (7) For any f ∈I(B), we have that f(B1) = f(B2) = · · · = f(B7) = 0. It then follows from (7) and Lemma 6.1 that f(C) = 0. However, since C 6∈ B, it must be the case that f(C) 6= 0 for some f ∈ I(B). This contradiction establishes the desired result. Note that this linearization technique may be applied more generally. If we can find C 6∈ B such that δs(C) is a linear combination of the w-dimensional vectors {δs(B) | B ∈B}, then γ2(B) > s. We now show one way to construct examples of 2-(v,3,2) designs that satisfy the hypotheses of Theorem 6.3. Our construction works for any v ≡ 1,3 (mod 6), v ≥ 15. Suppose we have a 2-(v,3,2) design that satisfies the hypotheses of Theorem 6.3. We first observe that {{1,2,3},{1,4,5},{2,4,6},{3,5,6}} (8) is a set of four blocks that forms a so-called quadrilateral (or Pasch configuration). As well, {{1,2,4},{1,3,5},{2,3,6}} (9) is a set of three blocks that is not contained in a quadrilateral (because {4,5,6} is not a block). We require two ingredients: 1. The unique 2-(7,3,1) design is isomorphic to point-line structure of PG(2,2) and it contains a quadrilateral (in fact, it contains exactly seven distinct quadrilaterals). Therefore the points of this design can be relabelled so it contains the four blocks in (8). Now, from the Doyen-Wilson Theorem, we can embed this 2-(7,3,1) design in a 2-(v,3,1) design for any v ≡ 1,3 (mod 6), v ≥ 15. 2. It is shown in [22, Theorem 3.1] that the maximum number of quadrilaterals in a 2-(v,3,1) design is v(v − 1)(v − 3)/24, and this maximum is attained if an only if the design is isomorphic to the point-line structure of the projective geometry PG(n,2) for some integer n ≥ 2. Take any 2-(v,3,1) design that is not isomorphic to the projective geometry PG(n,2) (this can be done provided v ≡ 1,3 (mod 6), v ≥ 9. It is easy to see that design must contain three non-collinear points that are not contained in a quadrilateral. By relabelling points in the design, we can assume that the three non-collinear points are denoted 1,2 and 3, and they are contained in the three blocks in (9). Moreover, {4,5,6} is not a block in this design because the three points 1,2,3 are not contained in a quadrilateral. Now we take the union of the blocks in the two 2-(v,3,1) designs constructed above. The result is a 2-(v,3,2) design that contains the seven blocks in (8) and (9). We have already noted that {4,5,6} is not a block in the second design. It is also not a block in the first design because the pairs {4,5}, {4,6} and {5,6} occur in three different blocks in this design. As a consequence of this discussion and Theorem 6.3, the following result is immediate. 173 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Theorem 6.4. Suppose v ≡ 1,3 (mod 6), v ≥ 15. Then there exists a 2-(v,3,2) design (X,B) such that γ2(B) = 3. � We now give a more general version of this construction, starting from an arbitrary trade. We recall some definitions from [12]. A trade is a set T of two (finite) subsets of blocks of size three, say T = {T1,T2} that satisfies the following properties: 1. each T` (` = 1,2) is a partial Steiner triple system (i.e., no pair of points occurs in more than one block) 2. T1 ∩T2 = ∅ 3. the set of pairs contained in the blocks in T1 is identical to the set of pairs contained in the blocks in T2. As an example, if T1 = {{1,2,3},{1,4,5},{2,4,6},{3,5,6}} and T2 = {{1,2,4},{1,3,5},{2,3,6},{4,5,6}}, then T = {T1,T2} is a trade. The volume of a trade T = {T1,T2}, which is denoted vol(T), is the number of blocks in T1 (or, equivalently, the number of blocks in T2). The foundation of T, denoted found(T), is the set of points covered by the blocks in T1 (or, equivalently, the set of points covered by the blocks in T2). In the above example, vol(T) = 4 and found(T) = {1,2,3,4,5,6}. The following lemma is easy to prove. Lemma 6.5. T = {T1,T2} is a trade. Then∑ B∈T1 δ2(B) = ∑ B∈T2 δ2(B). Proof. The definition of a trade T = {T1,T2} ensures that T1 and T2 cover the same set of pairs. So we just need to prove that T1 and T2 contain the same points with the same multiplicities. Suppose i ∈ found(T). Let N` = {j : {i,j} is contained in a block in T1}. Then it is easy to see that i is contained in |N`|/2 blocks in each of T1 and T2. The following is a slight generalization of Theorem 6.3. We omit the proof, which makes use of Lemma 6.5, since it is essentially the same. Theorem 6.6. Let T = {T1,T2} be a trade. Suppose B = {h,i,j}∈ T2. Suppose that (X,B) is 2-(v,3,2) design such that T1 ∪ (T2 \{B}) ⊆B and B 6∈ B. Then γ2(B) = 3. � Theorem 6.7. Suppose that T = {T1,T2} is a trade, where |found(T)| = n. Let B ∈ T1. Suppose v ≡ 1,3 (mod 6), v ≥ 2n + 3. Then there exists a 2-(v,3,2) containing all the blocks in T1 ∪ (T2 \{B}), such that γ2(B) = 3. Proof. T1 is a partial Steiner triple system on n points. The famous result of Bryant and Horsley [2] shows that T1 can be embedded in a 2-(v,3,1) design for any v ≡ 1,3 (mod 6), v ≥ 2n + 1. 174 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Suppose B = {h,i,j} and let B∗ = {i,j,`}, where ` 6∈ found(T). Define T∗2 = (T2\{B})∪{B∗}. T∗2 is a partial Steiner triple system on n + 1 points, so (again, from [2]) it can be embedded in a 2-(v,3,1) design for any v ≡ 1,3 (mod 6), v ≥ 2(n + 1) + 1. So for v ≡ 1,3 (mod 6), v ≥ 2n + 3, we have two 2-(v,3,1) designs (which we can assume are defined on the same set of points), say (Y,B1) and (Y,B2), such that T1 ⊆ B1 and T∗2 ⊆ B2. Then (Y,B1 ∪B2) is a 2-(v,3,2) design that contains all the blocks in T1 ∪ (T2 \{B}). We claim that B is not a block in B1 ∪B2. First, there is a unique block B′ ∈B1 that contains the pair {i,j}, and this block B′ is one of the blocks in T1. Because B′ ∈ T1 and B ∈ T2, it follows that B′ 6= B. Therefore B 6∈ B1. To see that B 6∈ B2, we observe that the unique block in B2 that contains the pair {i,j} is B∗ 6= B. Thus we have shown that (Y,B1 ∪B2) satisfies the hypotheses of Theorem 6.6, and the proof is complete. 7. Strength greater than two We finish by addressing the ideals of non-trivial t-(v,k,λ) designs with t > 2. For Steiner systems (where λ = 1), we have t + 1 2 ≤ γ1(B) ≤ γ2(B) ≤ t using Theorem 2.3 and Theorem 4.3. When λ > 1, the lower bound still holds and we may apply Lemma 2.6: since the number of blocks is |B| = λ ( v t )( k t )−1 , we find γ1(B) ≤ s whenever ( v s )( k t ) > λ ( v t ) . We also have Corollary 4.7 which tells us that γ2(B) ≤ m+ 1 when m is the maximum size of the intersection of two distinct blocks. Let (X,B) be a t-(v,k,λ) design. For i ∈ X, the derived design of (X,B) with respect to i is the ordered pair (Ẋ, Ḃ) where Ẋ = X \{i} and Ḃ = {B \{i} | i ∈ B ∈B} . The residual design of (X,B) with respect to i has vertex set Ẋ and block set {B ∈B | i 6∈ B}. If (X,B) is a t-design, then both its derived design and its residual design are (t−1)-designs. Lemma 7.1. Let (X,B) be a non-trivial t-design with i ∈ X. With notation as above γh(Ḃ) ≤ γh(B) for h = 1,2. The same inequalities hold for the residual design. Proof. We handle the case of the derived design; the computations for the residual design are similar. To simplify the notation, we take i = 1. Let I = I(B) and define ideal J as the image of I under the ring homomorphism ϕ : C[x1, . . . ,xv] → C[x2, . . . ,xv] mapping x1 to 1 and mapping each xj to itself for j = 2, . . . ,v. For g ∈ I write ġ := ϕ(g) ∈ J. For any (k−1)-set C ⊆{2, . . . ,v}, we have ġ(C) = g(C∪{1}) and so, for C ∈ Ḃ we have ġ(C) = 0 for all ġ ∈ J and, for C 6∈ Ḃ, there exists ġ ∈ J for which ġ(C) 6= 0. It follows that, if G is a generating set for I, then ϕ(G) is a generating set for J. This shows γ2(Ḃ) ≤ γ2(B). Next, if g is a non-trivial polynomial in I of smallest degree, then ġ has degree no larger than the degree of g and is also non-trivial since ϕ maps trivial ideal to trivial ideal. We illustrate this and other results in this paper by recording, in the following table, the exact value of these parameters for the Witt designs and the t-designs appearing as their derived designs. Up to isomorphism, there are unique block designs with parameters 5-(24,8,1), 4-(23,7,1), 3-(22,6,1), 5- (12,6,1), 4-(11,5,1) and 3-(10,4,1). One accessible source of information on the Witt designs is the note [1] by Andries Brouwer. 175 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 t-(v,k,λ) γ1(B) γ2(B) Notes 5-(24,8,1) 3 3 Theorems 2.3, 7.2 4-(23,7,1) 3 3 Theorem 7.3 3-(22,6,1) 2 2 Theorem 7.4 2-(21,5,1) 2 2 Theorem 5.3 5-(12,6,1) 3 3 discussion below 4-(11,5,1) 3 3 Lemma 7.1 3-(10,4,1) 2 2 discussion below 2-(9,3,1) 2 2 Theorems 2.3, 4.3 In the large Witt design, with parameters 5-(24,8,1), blocks intersect in 0, 2 or 4 points. So we might start with the zonal polynomials (cB ·x)(cB ·x−2)(cB ·x−4)(cB ·x−8) where B ∈B. We know that the blocks of this design are the supports of the minimum weight codewords in the extended binary Golay code. We may then use the fact that this is a self-dual code to show that these, together with the generators of T , generate our ideal. But we can do better. Theorem 7.2. Let (X,B) be the 5-(24,8,1) design. For a block B ∈B and points i,j ∈ B, define fB,i,j(x) = (xi −xj)(cB ·x−2)(cB ·x−4). Then (i) I(B) is generated by G0 ∪{fB,i,j | i,j ∈ B ∈B}; (ii) γ1(B) = γ2(B) = 3. Proof. We know γ1(B) ≥ 3 by Theorem 2.3. For any block B ∈B, the number mi of blocks B′ ∈B with |B ∩B′| = i is given by i 8 7 6 5 4 3 2 1 0 mi 1 0 0 0 280 0 448 0 30 So the zonal polynomial (cf. Corollary 2.5) ∏ i=8,4,2,0(cB · x − i) belongs to I(B) and the quadratic polynomial (cB ·x−2)(cB ·x−4) vanishes on every block except B itself and those blocks disjoint from B. But if i and j both belong to block B, the linear function xi −xj vanishes on cB and on cB′ for any block B′ disjoint from B. To show that the polynomials fB,i,j — as B ranges over the blocks and i, j range over the elements of B — together with the polynomials in the trivial ideal, generate our ideal, we employ two basic facts about the extended binary Golay code G24. The blocks in B are precisely the supports of minimum weight codewords in this code. This is a self-dual code, so a binary tuple c ∈ F242 satisfies c ∈ G24 if and only if the mod 2 dot product c · c′ is zero for every c′ ∈ G24. Since G24 is generated by its weight eight codewords, we may say c ∈ G24 if and only if its inner product with these 759 codewords is zero mod two. Since we only want to recover the codewords of weight eight, we may omit integer inner product six. Let I = 〈G0 ∪{fB,i,j | i,j ∈ B ∈B}〉 and observe that any element of Z(I) has exactly eight entries equal to one and sixteen entries equal to zero. For c ∈ F242 , let c ∈ R24 be the corresponding 01-vector with real entries: cj = 1 if cj = 1 and cj = 0 if cj = 0. Assuming c ∈Z(I), we have fB,i,j(c) = 0 for each B ∈B and each i,j ∈ B which implies that either cB ·c ∈{2,4} or ci = 1 ⇔ cj = 1 for all i,j ∈ B. This latter alternative clearly means that either c = cB or c · cB = 0. For the corresponding binary vectors, this implies c ·c′ = 0 for each c′ ∈ G24 with Hamming weight eight. As outlined above, this gives c ∈ G24 and, in turn, c = cB′ for some B′ ∈B. By Propositions 3.2 and 3.1(ii), we have I = I(B). 176 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Theorem 7.3. Let (X,B) be the 4-(23,7,1) design. For three distinct points i, j and k, let Ci,j,k = {C = B \{i,j,k} | {i,j,k}⊆ B ∈B} and define hi,j,k(x) = 3 + 12xixjxk −3(xixj + xixk + xjxk)− ∑ C∈Ci,j,k xC,2 . Then (i) I(B) is generated by G0 ∪{hi,j,k | i,j,k}; (ii) γ1(B) = γ2(B) = 3; (iii) the coordinate ring C[x]/I(B) admits a basis consisting of those ( 23 2 ) cosets xixj +I(B) represented by multilinear monomials of degree two. Proof. Denote by B1,B2,B3,B4,B5 the five blocks containing T := {i,j,k} and set C` = B` \T . We know that two distinct blocks of our Witt design intersect in either three points or one point. We now show that hi,j,k(B) = 0 for each B ∈B. To illustrate the simple arithmetic involved, we write hi,j,k(x) = 3 + 12(xixjxk)−3(xixj + xixk + xjxk)− (xC1,2)− (xC2,2)− (xC3,2)− (xC4,2)− (xC5,2) where B` = C` ∪T and we retain most of the parentheses here in our evaluation. case (1) T ⊆ B. Here, we have B = B` for some ` ∈{1, . . . ,5} and hi,j,k(B) = 3 + 12(1)−3(1 + 1 + 1)− (1 + 1 + 1 + 1 + 1 + 1)− (0)− (0)− (0)− (0) = 0. case (2) |T ∩B| = 2. Here we must have |B ∩B`| = 3 for all ` and, as B never contains two points from the same “sub-block” C` = B` \T , we have hi,j,k(B) = 3 + 12(0)−3(1)− (0)− (0)− (0)− (0)− (0) = 0. case (3) |T ∩B| = 1. In this case, as there are five blocks containing T and |B| = 7, we must have |B ∩B`| = 3 for exactly three values of ` and, as B contains two points from the same sub-block C` = B` \T in each of these three cases, we have hi,j,k(B) = 3 + 12(0)−3(0)− (1)− (1)− (1)− (0)− (0) = 0. case (3) T ∩ B = ∅. In this case, as there are five blocks containing T and |B| = 7, we must have |B ∩C`| = 3 for some unique sub-block C` = B` \T and B must contain a unique point from each of the other four. In this case, we have hi,j,k(B) = 3 + 12(0)−3(0)− (1 + 1 + 1)− (0)− (0)− (0)− (0) = 0. On the other hand, if S is a 7-set of points which is not a block, then hi,j,k(S) 6= 0 for any {i,j,k}⊆ S. For if T := {i,j,k} is contained in S and hi,j,k(S) = 0, then we have 0 = hi,j,k(S) = 3 + 12(1)−3(1 + 1 + 1)− ( m1 2 ) − ( m2 2 ) − ( m3 2 ) − ( m4 2 ) − ( m5 2 ) where m` = |S ∩ C`|. But m1 + · · · + m5 = 4 and we see that the only arrangement that achieves the stated equality is where some m` = 4. But then S = B` and we are done. So, if I = 〈G0 ∪{hi,j,k | i,j,k}〉 we have shown Z(I) = {cB | B ∈B}. By Proposition 3.2, I is a radical ideal. so Proposition 3.1(ii) gives us I = I(B). This proves that γ2(B) = 3 and, by Theorem 2.3, γ1(B) = 3 as well. By Lemma 3.3, each coset xi + I can be expressed as a linear combination of cosets xixj + I. Since the number of blocks of the design is ( 23 2 ) , we see that the cosets {xixj +I | i,j} form a vector space basis for C[x]/I. 177 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 Next, if (X,B) denotes the Witt design on 22 points, Lemma 7.1 tells us 2 ≤ γ1(B) ≤ γ2(B) ≤ 3. We now show that both values are equal to two. Theorem 7.4. Let (X,B) be the 3-(22,6,1) design. For two distinct points i, j and a block B containing them, say B = {i,j,r,s,t,u}, define hi,j,B(x) = (xi −xj)(xr + xs + xt + xu −1). Then (i) I(B) is generated by G0 ∪{hi,j,B | i 6= j, i,j ∈ B, B ∈B}; (ii) γ1(B) = γ2(B) = 2; (iii) the coordinate ring C[x]/I(B) admits a basis consisting of the 77 cosets xB,2 +I(B) obtained as B ranges over the blocks of the design. Proof. By Theorem 2.3, we have γ1(B) ≥ 2. Consider B ∈ B and two distinct points i,j ∈ B. Write B = {i,j,r,s,t,u}. Since any two blocks of this design intersect in zero or two points, any block B′ that contains exactly one of i,j contains exactly one element from {r,s,t,u}. So hi,j,B(B′) = 0. The same holds if |B′∩{i,j}| is even. On the other hand, let C be a 6-element subset of X and choose three distinct points i,t,u ∈ C. There is a unique block B containing these three points, say B = {i,j,r,s,t,u}. If all three polynomials hi,j,B(x), hi,r,B(x), hi,s,B(x) vanish on C, then we must have C = B. This finishes the proof that Z(G) = {cB | B ∈B} and, as G0 ⊆G, the ideal 〈G〉 is radical, proving (i) and (ii). To show that the functions on B represented by the polynomials {xB,2 | B ∈ B} are linearly independent, consider the 77 × 77 matrix M with (B,B′)-entry equal to the value the polynomial xB ′,2 takes at the point cB. Then M −I is the adjacency matrix of a well-known2 strongly regular graph with eigenvalues 60, 5 and −3. It follows that M is invertible and the 77 cosets {xB,2 + I(B) | B ∈ B} are linearly independent in the coordinate ring. For the small Witt designs, we do not have a computer-free proof of our claims. Let us instead describe some generators for the ideals. First consider the unique Witt design on twelve points. Let (X,B) be the 5-(12,6,1) design. For three distinct points i, j and k, let C = X \ {i,j,k}. The twelve blocks containing i, j and k yield a 2-(9,3,1) design (C,B′), B′ = {B \{i,j,k} | i,j,k ∈ B ∈B} on the point set C and the four parallel classes of this affine plane may be oriented in a total of sixteen ways (each resulting in a 4-set of directed triples of blocks). We find that certain orientations yield polynomials of degree three which, together with those polynomials in G0, generate the ideal I(B). This shows γ1(B) = γ2(B) = 3. To be precise, let M12 be the subgroup of S12 generated by {(1 4)(3 10)(5 11)(6 12), (1 8 9)(2 3 4)(5 12 11)(6 10 7)} and consider the 132 6-sets in the orbit containing {1,2,3,4,5,9}. Since M12 is 5-transitive, this is a 5-(12,6,1) design. Two parallel lines in the derived design consisting of all blocks containing points 1, 2 and 3 are {4,5,9} and {8,10,11}. With a computer, one easily verifies that the polynomial F(x) = x1x4(x10 −x11) + x1x5(x11 −x8) + x1x9(x8 −x10) + x2x9(x10 −x11) + x2x4(x11 −x8) + x2x5(x8 −x10) + x3x5(x10 −x11) + x3x9(x11 −x8) + x3x4(x8 −x10) 2 See, for example, https: // www. win. tue. nl/ ~aeb/ graphs/ srg/ srgtab51-100. html 178 https://www.win.tue.nl/~aeb/graphs/srg/srgtab51-100.html W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 vanishes on each block of the design. It follows that any image [1π,2π,3π], [4π,5π,9π], [10π,11π,8π] of the three triples of indices under any π ∈ M12 yields another polynomial in the ideal. It requires a bit more computation, using the Singular computer algebra system [15], to check that the ideal I(B) is generated by these polynomials together with those in G0. The relative orderings within the three triples above is important and we do not have an intrinsic description of the permissible orderings that yield vanishing polynomials. If we take the above computation as correct, we may determine γ1 and γ2 for the Witt design on eleven points. If (X,B) now denotes a 4-(11,5,1) design, we may use Theorem 2.3 to see that γ1(B) ≥ 3. By Lemma 7.1, we have equality, and γ2(B) = 3 as well. Without proof, we note that if (X,B) is the unique 3-(10,4,1) design [23, Fig. 9.1], we find γ1(B) = γ2(B) = 2. In addition to the generators of the trivial ideal, we build certain quadratic generators from any pair B1,B2 of disjoint blocks. In order to explain these generators, we first describe the design. For the construction in [23], we take X = F23 ∪{∞} with the numbering 0 1 2 3 4 5 6 7 8 9 ∞ (0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2) and blocks {0} ∪ ` where ` is a line of AG(2,3) and the following eighteen symmetric differences of orthogonal lines: 1245, 1278, 1269, 1346, 1379, 1358, 2356, 2389, 2347, 4578, 4679, 5689, 1567, 2468, 3459, 1489, 2579, 3678. For any pair B1,B2 ∈ B with B1 ∩ B2 = ∅, the number mi,j of blocks B ∈ B with |B ∩ B1| = i and |B ∩B2| = j is given in the following table: i\j 0 1 2 3 4 0 0 0 2 0 1 1 0 0 8 0 0 2 2 8 8 0 0 3 0 0 0 0 0 4 1 0 0 0 0 For each i ∈ B1, the two blocks meeting B1 only in this point partition B2 into two sets of size two by their intersections. We select one of these two to determine two neighbours of i along an octagon as in Figure 1. Once B1 and B2 have been selected and this choice of a pair of neighbours has been made, this determines a quadratic generator for our ideal. We illustrate this with B1 = {0,1,2,3} and B2 = {4,5,7,8}. The resulting polynomial is g(x) = x0x5 −x5x1 + x1x7 −x7x3 + x3x8 −x8x2 + x2x4 −x4x0. We leave it to the reader to check that the way in which any block intersects this configuration guarantees that g(cB) = 0 for any B ∈ B. In fact, just five of these polynomials are needed — along with G0 — to generate the ideal. 8. Conclusion We have introduced an algebraic approach to the study of t-designs which builds on existing ma- chinery tied to the space of polynomial functions on blocks. For a design (X,B), we introduced the ideal 179 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 0 13 2 4 5 7 8 − + − +− + − + Figure 1. Two disjoint blocks {0,1,2,3} and {4,5,7,8} and the quadratic polynomial obtained from the pair I(B) and proposed two parameters γ1(B) and γ2(B) which we claim capture essential information in the case of designs where the number of blocks achieves, or is close to, the bound of Ray-Chaudhuri and Wilson. We prove, among other things, that t + 1 2 ≤ γ1(B) ≤ γ2(B) ≤ k with the upper bound of k replaced by t in the case of Steiner systems or partial Steiner systems. We determine the exact value of these parameters for symmetric 2-designs and the Witt designs. By constructing many triple systems with γ2(B) = k, we indicate that γ2(B) can be larger than t. While we expect the value to be more typically close to k, we leave this as an open problem. One may also investigate the ideal vanishing on the codewords of an error-correcting code. In order to compute γ1 and γ2 in such a situation, we have some degree of freedom as these parameters are invariant under affine transformations (provided one is careful with the definition of the trivial ideal). Representing the codewords of a binary linear [n,k,d] code C by ±1 vectors in Rn, we see that each dual codeword c = [c1, . . . ,cn] corresponds to an element fc(x) = −1 + ∏ j x cj j in the ideal of our code. In the linear case, γ1(C) is the minimum distance of C⊥ and γ2(C) seems tied to the smallest g such that C⊥ is generated by its codewords of weight g or less. So it seems interesting to classify those codes C for which γ1(C) = γ2(C) as these seem related to tight designs. Acknowledgment: The authors thank Padraig Ó Catháin, Bill Kantor and Brian Kodalen for useful comments on the work presented here. We are grateful to the referee for several improvements to the manuscript. 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. 180 https://www.win.tue.nl/~aeb/2WF02/Witt.pdf https://www.win.tue.nl/~aeb/2WF02/Witt.pdf https://www.win.tue.nl/~aeb/2WF02/Witt.pdf https://www.win.tue.nl/~aeb/2WF02/Witt.pdf https://doi.org/10.1002/jcd.20189 https://doi.org/10.1002/jcd.20189 https://doi.org/10.1090/S0002-9947-1993-1134756-0 https://doi.org/10.1090/S0002-9947-1993-1134756-0 W. J. Martin, D. R. Stinson / J. Algebra Comb. Discrete Appl. 7(2) (2020) 161–181 [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 Zn4 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 Fnq 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 Poly- nomial 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: Hand- book 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. 181 https://doi.org/10.1007/BF00147860 https://doi.org/10.1007/978-1-4613-8354-3_12 https://doi.org/10.1007/978-1-4613-8354-3_12 https://doi.org/10.1007/978-1-4613-8354-3_12 https://www.jstor.org/stable/24906442 https://www.jstor.org/stable/24906442 https://doi.org/10.1137/0134012 https://doi.org/10.1137/0134012 https://www.jstor.org/stable/24906443 https://www.jstor.org/stable/24906443 http://www.singular.uni-kl.de http://www.singular.uni-kl.de https://arxiv.org/abs/1401.3665 https://doi.org/10.1007/s10801-014-0550-5 https://doi.org/10.1007/s10801-014-0550-5 https://doi.org/10.1007/978-94-009-3889-2_19 https://doi.org/10.1007/978-94-009-3889-2_19 https://doi.org/10.1007/978-94-009-3889-2_19 https://doi.org/10.18910/7296 https://doi.org/10.1016/0012-365X(92)90143-4 https://doi.org/10.1016/0012-365X(92)90143-4 https://doi.org/10.4171/EMSS/1 https://doi.org/10.4171/EMSS/1 Introduction Two parameters Radical ideals Steiner systems and partial designs Symmetric balanced incomplete block designs Triple systems Strength greater than two Conclusion References