Frankl-Füredi Type Inequalities for Polynomial Semi-lattices Jin Qian and Dijen K. Ray-Chaudhuri^{1} Department of Mathematics The Ohio State University

Submitted: April 2, 1997; Accepted: October 20, 1997

Abstract

Let X be an n-set and L a set of nonnegative integers. F, a set of subsets of X, is said to be an L -intersection family if and only if for all E ≠ F ∈ F, |E ∩F | ∈ L. A special case of a conjecture of Frankl and Füredi [4] states that if L = {1, 2, …, k}, k a positive integer, then |F| ≤ ∑_{i=0}^{k} \binom{n−1}{i}.

Here |F| denotes the number of elements in F.

Recently Ramanan proved this conjecture in [6]. We extend his method to polynomial semi-lattices and we also study some special L-intersection families on polynomial semi-lattices.

Finally we prove two modular versions of Ray-Chaudhuri-Wilson inequality for polynomial semi-lattices.

§1. Introduction

Throughout the paper, we assume k, n ∈ ℕ, I_{n} = {1, 2, …, n} ⊂ ℕ, where ℕ denotes the set of positive integers.

In this part, we briefly review the concept of polynomial semi-lattice introduced by Ray-Chaudhuri and Zhu in [8]. The definition of polynomial semi-lattice given here is equivalent to but simpler than that in [8]. For the convenience of the reader, we also include various examples of polynomial semi-lattices.

Let (X, ≤) be a finite nonempty partially ordered set having the property that (X, ≤) is a semi-lattice, i.e., for every x, y ∈ X there is a unique greatest lower bound of x and y denoted by x ∧ y. If x ≤ y and x ≠ y, we write x < y. We

1e-mail addresses: <qian@math.ohio-state.edu>, <dijen@math.ohio-state.edu>

the electronic journal of combinatorics 4 (1997), #R28 2

also assume that (X, ≤) has a height function l(x), where l(x) + 1 is the number of terms in a maximal chain from the least element 0 to the element x including the end elements in the count. Let n be the maximum of l(x) for all the x in X. Define X_{i} = {x ∈ X| l(x) = i}, 0 ≤ i ≤ n and X_{0} = {0}. Then X = ∪_{i=0}^{n}X_{i} is a partition and the subsets X_{i}’s are called fibres. The integer n is said to be the height of (X, ≤).

(X, ≤) is called a polynomial semi-lattice, if for each fibre X_{i} there is a size number m_{i} ∈ ℕ ∪ {0} and a polynomial f_{i}(w) ∈ ℚ[w], where ℚ is the set of rational numbers such that

a) m_{0} < m_{1} < … < m_{n},

b) f_{i}(w) = a_{i}(w − m_{0})(w − m_{1}) … (w − m_{i−1}) for some positive rational number a_{i} for i > 0, and f_{0}(w) = 1,

c) For any i, j, k, 0 ≤ k ≤ i ≤ j ≤ n, x ∈ X_{k}, y ∈ X_{j} and x ≤ y, |{z | z ∈ X_{i}, x ≤ z ≤ y}| = f_{i−k}(m_{j−k}).

Remarks.

1) Taking k = 0 in c), we have |{z | z ∈ X_{i}, z ≤ y}| = f_{i}(m_{j}) for every y ∈ X_{j}.

2) For any x ∈ X we define |x| to be m_{i} if x ∈ X_{i}. Specializing y = E ∧ F in remark 1), we have |{I ∈ X_{i} | I ≤ E ∧ F }| = f_{i}(|E ∧ F |), where E, F ∈ X. This result is going to be used later.

3) Taking i = j in remark 1), we have f_{i}(m_{i}) = 1 since {z | z ∈ X_{i}, z ≤ y} = {y}. From this we can solve for a_{i}:

a_{i} = \frac{1}{(m_{i} − m_{0})(m_{i} − m_{1}) … (m_{i} − m_{i−1})}

for i = 1, 2, …, n.

4) From remark 3), we get

f_{i}(w) = \frac{(w − m_{0})(w − m_{1}) … (w − m_{i−1})}{(m_{i} − m_{0})(m_{i} − m_{1}) … (m_{i} − m_{i−1})}.

For j > i, we have m_{j} > m_{i} and therefore f_{i}(m_{j}) > 1.

the electronic journal of combinatorics 4 (1997), #R28 3

In the following examples we let s ∈ ℕ, q be a prime power, and

[w, i]_{q} = \frac{(w − 1)(w − q) ⋯ (w − q^{i−1})}{(q^{i} − 1)(q^{i} − q) ⋯ (q^{i} − q^{i−1})}.

Examples:

1) Johnson Scheme. Let V be an n-element set and X_{i} be the set of all i-element subsets of V, 0 ≤ i ≤ n. Then X = ∪_{i=0}^{n}X_{i}, with inclusion as the partial order, is a semi-lattice. Let m_{i} = i, f_{i}(w) = \binom{w}{i}. It is easy to see that (X, ≤) is a polynomial semi-lattice.

2) q-analogue of Johnson Scheme. Let V be an n-dimensional vector space over a finite field GF (q), X_{i} be the set of all i-dimensional subspaces of V, 0 ≤ i ≤ n. Let m_{i} = q^{i}, f_{i}(w) = [w, i]_{q} (defined after remark 4). Then X = ∪_{i=0}^{n}X_{i} is a polynomial semi-lattice with inclusion as the partial order.

3) Hamming Scheme. Let W be an s-element set. We define X_{i} = {(L, h) | L ⊆ {1, 2, …, n}, |L| = i, h : L → W a map }, 1 ≤ i ≤ n, X_{0} = {0}, where 0 is taken to be the least element, and X = ∪_{i=0}^{n}X_{i}. (L_{1}, h_{1}) ≤ (L_{2}, h_{2}) if and only if L_{1} ⊆ L_{2}, and h_{2}|_{L_{1}} = h_{1}. Then (X, ≤) is a polynomial semi-lattice, with m_{i} = i, f_{i}(w) = \binom{w}{i}.

4) q-analogue of Hamming Scheme. Let V be an s-dimensional vector space over a finite field GF (q) and W be an n-dimensional vector space over a finite field GF (q). Define X_{i} = {(U, h) | U ⊆ W, dim(U) = i, h : U → V, a linear transformation}, 0 ≤ i ≤ n. Let X = ∪_{i=0}^{n}X_{i}. ∀(U_{1}, h_{1}), (U_{2}, h_{2}) ∈ X, define (U_{1}, h_{1}) ≤ (U_{2}, h_{2}) if and only if U_{1} ⊆ U_{2} and h_{2}|_{U_{1}} = h_{1}. Then (X, ≤) is a polynomial semi-lattice, with m_{i} = q^{i}, f_{i}(w) = [w, i]_{q}.

5) Ordered Design. Let W be an s-element set and V be an n-element set with n ≤ s. We define X_{i} = {(L, h) | L ⊆ {1, 2, …, n}, |L| = i, h : L → W an injection}, 1 ≤ i ≤ n, X_{0} = {0}, where 0 is taken as the least element, and X = ∪_{i=0}^{n}X_{i}. ∀(L_{1}, h_{1}), (L_{2}, h_{2}) ∈ X, define (L_{1}, h_{1}) ≤ (L_{2}, h_{2}) if and only if L_{1} ⊆ L_{2} and h_{2}|_{L_{1}} = h_{1}. Then (X, ≤) is a polynomial semi-lattice, with m_{i} = i, f_{i}(w) = \binom{w}{i}.

6) q-analogue of Ordered Design. Let W be an s-dimensional vector space and V be an n-dimensional vector space over a finite field GF (q) with n ≤ s. Define

the electronic journal of combinatorics 4 (1997), #R28 4

X_{i} = {(U, h) | U ⊆ V, dim(U) = i, h : U → W, a nonsingular linear transformation }, 0 ≤ i ≤ n. Let X = ∪_{i=0}^{n}X_{i}. ∀(U_{1}, h_{1}), (U_{2}, h_{2}) ∈ X, define (U_{1}, h_{1}) ≤ (U_{2}, h_{2}) if and only if U_{1} ⊆ U_{2} and h_{2}|_{U_{1}} = h_{1}. Then (X, ≤) is a polynomial semilattice, with m_{i} = q^{i}, f_{i}(w) = [w, i]_{q}.

§2. Statement of Results

Let (X, ≤) be a polynomial semi-lattice of height n, i.e X = ∪_{i=0}^{n}X_{i} and L be a ksubset of I_{n} ∪{0}, where k ≤ n is a natural number. We call F ⊆ X an L-intersection family if and only if ∀E ≠ F ∈ F, E ∧ F ∈ ∪_{l∈L}X_{l}. If F is empty or contains only one element, it is vacuously an L-intersection family and all the theorems below are trivially true. So in the rest of this paper, we assume that F has at least two elements.

Ray-Chaudhuri and Zhu extended the well-known Ray-Chaudhuri-Wilson theorem to the polynomial semi-lattice and they have [8]:

Theorem 1. Let (X, ≤) be a polynomial semi-lattice. If F ⊆ X is an Lintersection family, then |F| ≤ ∑_{i=0}^{k} |X_{i}|.

For the special case L = {l, l + 1, …, l + k − 1}, we extend the method in Ramanan [6] to polynomial semi-lattices, and we have:

Theorem 2. Let (X, ≤) be a semi-lattice of height n, l, k ∈ ℕ, l + k − 1 ≤ n and F be an {l, l + 1, …, l + k − 1}-intersection family. Then

|F| ≤ |X_{k}| + |X_{k−2}| + ⋯ + |X_{k−[k/2]2}|.

Here [x] means the greatest integer less than or equal to x.

The above result for the set case was raised by Ramanan [6] as an interesting problem.

In the case of Johnson scheme where |X_{n}| = \binom{n}{i}, 0 ≤ i ≤ n, we have the

Corollary. Let X be an n-set. If F is a family of subsets of X such that ∀E ≠ F ∈ F, |E ∩ F | ∈ \{1, 2, …, k\}, then |F| ≤ ∑_{i=0}^{k} \binom{n−1}{i}.

This follows by specializing l = 1 in Theorem 2 and the easy observation that

∑_{i=0}^{[k/2]} \binom{n}{k − 2i} = ∑_{i=0}^{k} \binom{n − 1}{k − i}.

This is a special case of a conjecture of Frankl and Füredi which was recently proved by G. V. Ramanan [6]. Indeed, Frankl and Füredi conjectured a more general result

Conjecture 1. Let k ∈ ℕ, l ∈ ℕ ∪ {0}, k > 2l + 1, n > n_{0}(k), X be an n-set, L = {0, 1, 2, ⋯, k} − {l}. If F is an L-intersection family of subsets of X, then

|F| ≤ ∑_{i≤l−1} \binom{n}{i} + ∑_{i=l+1}^{k+1} \binom{n − l − 1}{i − l − 1}.

Ramanan proved the special case of Frankl-Füredi conjecture when l = 0. The general case is still open.

We also studied the special case of Theorem 1 when L = {0, 1, …, k − 1} and got a simpler proof of the inequality as well as a necessary and sufficient condition under which the equality holds.

Theorem 3. Let (X, ≤) be a polynomial semi-lattice. If F is an L-intersection family for L = {0, 1, …, k − 1}, then |F| ≤ ∑_{i=0}^{k} |X_{i}|.

The equality holds if and only if F = ∪_{i=0}^{k}X_{i}.

In the direction of Theorem 1, Snevily [9] studied the case L = {0, 1, ⋯, k − 1}, and ∀E ∈ F, |E| ≥ k and he obtained a better upper-bound. We show that it can be generalized to polynomial semi-lattices (Theorem 4 below) and we give a simpler proof of the inequality as well as a necessary and sufficient condition under which the equality holds.

Theorem 4. Let (X, ≤) be a polynomial semi-lattice of height n, k ∈ ℕ, F an L-intersection family for L = {0, 1, …, k − 1} and F ⊆ ∪_{i=k}^{n}X_{i}. Then |F| ≤ |X_{k}|.

The equality holds if and only if F = X_{k}.

the electronic journal of combinatorics 4 (1997), #R28 6

Next, we show that some modular versions of Ray-Chaudhuri-Wilson Theorem [7] also extend to polynomial semi-lattices.

First the uniform case (Frankl and Wilson’s modular version [5]):

Theorem 5. Let (X, ≤) be a polynomial semi-lattice of height n, s, k ∈ ℕ with s ≤ k, L ⊆ I_{n} ∪{0} and F ⊆ X_{k} an L-intersection family. Suppose μ_{0}, μ_{1}, ⋯, μ_{s} are distinct residues modulo a prime p such that m_{k} ≡ μ_{0} (mod p) and ∀l ∈ L, m_{l} ≡ μ_{i} (mod p) for some i, 1 ≤ i ≤ s. Further suppose that for every μ_{i}, ∃l_{i} ∈ L, such that m_{l_{i}} ≡ μ_{i} (mod p), for i = 1, 2, ⋯, s. Then |F| ≤ |X_{s}|.

Then the nonuniform case (Deza, Frankl and Singhi’s modular version [3]):

Theorem 6. Let (X, ≤) be a polynomial semi-lattice of height n and F ⊆ X_{k_{1}} ∪ X_{k_{2}} ∪ ⋯ ∪ X_{k_{ν}} be an L-intersection family, where L ⊆ I_{n} ∪ {0} and k_{1}, k_{2}, ⋯, k_{ν} are integers in I_{n} ∪ {0}. Suppose μ_{1}, μ_{2}, ⋯, μ_{s} are distinct residues modulo a prime p such that ∀l ∈ L, m_{l} ≡ μ_{i} (mod p) for some i, 1 ≤ i ≤ s and m_{k_{i}} is not congruent to any one of μ_{1}, μ_{2}, ⋯, μ_{s} modulo p for i = 1, 2, ⋯, ν. Then |F| ≤ ∑_{i=0}^{s} |X_{i}|.

§3. The Proof of Theorem 2

Convention: Empty product is defined to be 1.

First we prove two lemmas.

Lemma 1. Let k, ∈ ℕ and l_{1} < l_{2} < ⋯ < l_{k} be k positive integers in I_{n}. There exist k + 1 positive real numbers b_{0}, b_{1}, …, b_{k} such that

∑_{i=0}^{k}(−1)^{i}b_{i}f_{i}(x) = (−1)^{k}(x − m_{l_{1}})(x − m_{l_{2}}) … (x − m_{l_{k}}).

Proof. Recall that f_{i}(x) = a_{i}(x−m_{0})(x−m_{1}) … (x−m_{i−1}) and m_{0} < m_{1} < ⋯ < m_{n}, where a_{i}’s are positive. So it is enough to prove that there exist positive real numbers c_{0}, c_{1}, ⋯, c_{k} such that

∑_{i=0}^{k}(−1)^{i}c_{i}(x−m_{0})(x−m_{1}) ⋯ (x−m_{i−1}) = (−1)^{k}(x−m_{l_{1}})(x−m_{l_{2}}) … (x−m_{l_{k}}). The above result follows from the following more general statement:

Claim. For any j such that 0 ≤ j < l_{1}, there exist positive real numbers d_{0}, d_{1}, ⋯, d_{k} such that

∑_{i=0}^{k}(−1)^{i}d_{i}(x−m_{j})(x−m_{j+1}) ⋯ (x−m_{j+i−1}) = (−1)^{k}(x−m_{l_{1}})(x−m_{l_{2}}) ⋯ (x−m_{l_{k}}).

Proof of the claim. When k = 1, it is trivially true. Suppose it is true for k.

Now we want to prove that it holds for k + 1.

(−1)^{k+1}(x − m_{l_{1}})(x − m_{l_{2}}) ⋯ (x − m_{l_{k+1}})
=(−1)(x − m_{l_{1}})[(−1)^{k}(x − m_{l_{2}}) ⋯ (x − m_{l_{k+1}})]
=(−1)[(x − m_{j}) − (m_{l_{1}} − m_{j})][(−1)^{k}(x − m_{l_{2}}) ⋯ (x − m_{l_{k+1}})]
=(−1)(x − m_{j})[(−1)^{k}(x − m_{l_{2}}) ⋯ (x − m_{l_{k+1}})] +
(m_{l_{1}} − m_{j})[(−1)^{k}(x − m_{l_{2}}) ⋯ (x − m_{l_{k+1}})]  (1)

Since j + 1 < l_{1} + 1, we can apply the induction hypothesis to the first term of (1) (denoted by I) and we have

I = (−1)(x − m_{j}) ∑_{i=0}^{k}(−1)^{i}u_{i}(x − m_{j+1}) ⋯ (x − m_{j+1+i−1})
= ∑_{i=0}^{k}(−1)^{i+1}u_{i}(x − m_{j})(x − m_{j+1}) ⋯ (x − m_{j+1+i−1})

for some positive real numbers u_{k}, u_{k−1}, ⋯, u_{0}. Then we use the induction hypothesis on the second term (denoted by II) and we have

II = (m_{l_{1}} − m_{j}) ∑_{i=0}^{k}(−1)^{i}v_{i}(x − m_{j}) ⋯ (x − m_{j+i−1})
= ∑_{i=0}^{k}(−1)^{i}(m_{l_{1}} − m_{j})v_{i}(x − m_{j}) ⋯ (x − m_{j+i−1})

the electronic journal of combinatorics 4 (1997), #R28 8

for some positive real numbers v_{k}, v_{k−1}, ⋯, v_{0}. Now add up I and II and we have

(−1)(x − m_{j})[(−1)^{k}(x − m_{l_{2}}) ⋯ (x − m_{l_{k+1}})] +
(m_{l_{1}} − m_{j})[(−1)^{k}(x − m_{l_{2}}) ⋯ (x − m_{l_{k+1}})]
=  ∑_{i=0}^{k+1}(−1)^{i}d_{i}((x − m_{j}) ⋯ (x − m_{j+i−1})

where

d_{k+1} = u_{k},
d_{k} = u_{k−1} + (m_{l_{1}} − m_{j})v_{k},
d_{k−1} = u_{k−2} + (m_{l_{1}} − m_{j})v_{k−1},
⋯
d_{0} = (m_{l_{1}} − m_{j})v_{0}.

so d_{k+1}, d_{k}, ⋯, d_{0} are positive, which proves the claim and therefore the lemma.

Remark. In the rest of the paper, we will only use Lemma 1 in its special case where l_{1} = l, l_{2} = l + 1, ⋯, l_{k} = l + k − 1. Let’s denote (x − m_{l})(x − m_{l+1}) … (x − m_{l+k−1}) by g(x). Since F is an {l, l + 1, ⋯, l + k − 1}-intersection family, |E| ≥ m_{l} for all E ∈ F. So it is clear that g(|E|) ≥ 0 for all E ∈ F and g(|E|) > 0 if |E| > m_{l+k−1}.

To each E ∈ F we associate a variable x_{E}. For each I ∈ X , we define a linear form L_{I} as follows:

L_{I} := ∑_{E∈F,I≤E} x_{E}.

Lemma 2. With the same notation as in Lemma 1 and further we assume that l ∈ ℕ, l + k − 1 ≤ n, l_{1} = l, l_{2} = l + 1, ⋯, l_{k} = l + k − 1. We have

∑_{i=0}^{k}(−1)^{i}b_{i} ∑_{I∈X_{i}} L_{I}^{2} = ∑_{E∈F}(−1)^{k}g(|E|)x_{E}^{2} .  (2)

Proof. We regard both sides as quadratic forms on x_{E}’s, where E ∈ F and try to show that the corresponding coefficients are equal.

the electronic journal of combinatorics 4 (1997), #R28 9

For example, for E ≠ F ∈ F, the term L_{I}^{2} contributes a term 2x_{E}x_{F} if and only if I ≤ E ∧ F. Therefore the coefficient of x_{E}x_{F} in the L. H. S of (2) is 2 ∑_{i=0}^{k}(−1)^{i}b_{i}f_{i}(|E ∧ F |) (see remark 2 in the introduction) which is equal to

2(−1)^{k}(|E ∧ F | − m_{l})((|E ∧ F | − m_{l+1}) … (|E ∧ F | − m_{l+k−1})

by Lemma 1. Since F is an L-intersection family with L = {l, l + 1, …, l + k − 1}, |E ∧ F | ∈ {m_{l}, m_{l+1}, …, m_{l+k−1}} and so the product in the previous sentence is 0. Obviously the coefficient of x_{E}x_{F} in the R.H.S is also 0. So the coefficient of x_{E}x_{F} in the L.H.S is equal to that in the R.H.S.

Similarly the coefficient of x_{E}^{2} in the L.H.S is ∑_{i=0}^{k}(−1)^{i}b_{i}f(|E|) for the same reason as above. By Lemma 1 it is equal to (−1)^{k}g(|E|) which is the coefficient of x_{E}^{2} in the R.H.S. Here g(x) is as defined in the remark immediately after the proof of Lemma 1.

We define the real vector space W to be ℝ^{|F|} whose coordinates are indexed by elements of F, L to be the set of linear forms {L_{I} : |I| ∈ {m_{k}, m_{k−2}, …, m_{k−[k/2]2}}} and W_{0} ⊆ W to be the space of common solutions of the set of equations L_{I} = 0, L_{I} ∈ L. Clearly |L| = ∑_{i=0}^{[k/2]} |X_{k−2i}|. An element of W_{0} will be written as (v_{E}, E ∈ F) = (v_{E}) (for short).

If we can show that W_{0} consists of the zero vector only, then by linear algebra, rank(L) = the number of variables = |F| and therefore |F| = rank(L) ≤ |L| = ∑_{i=0}^{[k/2]} |X_{k−2i}|, which finishes the proof of Theorem 2.

So it is enough to prove

Lemma 3. W_{0} = {(0, 0, …, 0)}.

Proof. Suppose W_{0} contains (v_{E}). It suffices to show v_{E} = (0, 0, …, 0).

By Lemma 2, we have

∑_{i=0}^{k}(−1)^{i}b_{i} ∑_{I∈X_{i}} L_{I}^{2} = (−1)^{k} ∑_{E∈F} g(|E|)x_{E}^{2}.

Specializing x_{E} = v_{E}, ∀E ∈ F, we have

∑_{i=0}^{k}(−1)^{i}b_{i} ∑_{I∈X_{i}} L_{I}^{2}((v_{E})) = (−1)^{k} ∑_{E∈F} g(|E|)v_{E}^{2}.

Since L_{I}((v_{E})) = 0, for all L_{I} ∈ L, we have L_{I}((v_{E})) = 0 for k − i even and thus

∑_{i∈{0,1,...,k},k−i is odd}(−1)^{i}b_{i} ∑_{I∈X_{i}} L_{I}^{2}((v_{E})) = (−1)^{k} ∑_{E∈F} g(|E|)v_{E}^{2}.

We divide both sides by (−1)^{k} and move the L.H.S to the R.H.S. So we have

0 = ∑_{i∈{0,1,...,k},k−i is odd} b_{i} ∑_{I∈X_{i}} L_{I}^{2}((v_{E})) + ∑_{E∈F} g(|E|)v_{E}^{2}.  (3)

Since b_{i}’s are positive by Lemma 1 and g(|E|) ≥ 0 by the remark immediately after the proof of Lemma 1 in this section, the R.H.S is a sum of nonnegative terms. So obviously if l(E) > l + k − 1, i.e. |E| > m_{l+k−1}, then g(|E|) > 0, which implies v_{E} = 0. Here l(.) is the height function of X defined in §1. The equation (3) also implies that L_{I}((v_{E})) = 0 for I ∈ X_{i}, i = k − 1, k − 3, · · ·. So L_{I}((v_{E})) = 0 for all I ∈ X_{0} ∪ X_{1} ∪ ⋯ ∪ X_{k}. In particular, L_{0}((v_{E})) = 0 where 0 is the least element of X.

To show that v_{E} = 0 for all E ∈ F, we assume the contrary. Define J = {l(E)|E ∈ F, v_{E} ≠ 0}. Let j_{0} be the largest number of J. By the results in the previous paragraph and the remark after the proof of Lemma 1, we have l ≤ j_{0} ≤ k + l − 1.

In the following, we distinguish 2 cases:

Case 1. Suppose j_{0} = l, then there exists an E ∈ F with l(E) = l and v_{E} ≠ 0. Since F is an {l, l + 1, ⋯, l + k − 1}-intersection family, l(E ∧ F) ≥ l = l(E) for

∀F ∈ F, so either F > E or F = E. If F ≠ E, then F > E and l(F) > l(E). Therefore v_{F} = 0 by the definition of J and j_{0}. Further because 0 = L_{0}((v_{F})) = ∑_{F ∈F} v_{F} = v_{E}, we have v_{E} = 0, a contradiction.

Case 2. Suppose l < j_{0} ≤ l + k − 1 and there exists an E ∈ F such that l(E) = j_{0} and v_{E} ≠ 0. We fix such an E.

Since f_{0}, f_{1}, ⋯, f_{j_{0}−l} form a base of the vector space of polynomials of degree ≤ j_{0} − l, there exist real numbers c_{0}, c_{1}, ⋯, c_{j_{0}−l} such that

∑_{i=0}^{j_{0}−l} c_{i}f_{i}(x) = (x − m_{l}) ⋯ (x − m_{j_{0}−1}).

the electronic journal of combinatorics 4 (1997), #R28 11

In the following we let h(x) = (x − m_{l}) ⋯ (x − m_{j_{0}−1}) and define λ_{I}(E) = 1 if I ≤ E and 0 otherwise.

As in the proof of Lemma 2, we have

∑_{i=0}^{j_{0}−l} c_{i} ∑_{I∈X_{i}} λ_{I}(E)L_{I}

= ∑_{i=0}^{j_{0}−l} c_{i} ∑_{F ∈F} x_{F} |{I|I ∈ X_{i}, I ≤ F, I ≤ E}|
= ∑_{i=0}^{j_{0}−l} c_{i} ∑_{F ∈F} x_{F} f_{i}(|F ∧ E|)
= ∑_{F ∈F} x_{F} ∑_{i=0}^{j_{0}−l} c_{i}f_{i}(|F ∧ E|)
= ∑_{F ∈F} x_{F} h(|E ∧ F |).

Specializing x_{F} = v_{F}, ∀F ∈ F, we have

∑_{i=0}^{j_{0}−l} c_{i} ∑_{I∈X_{i}} λ_{I}(E)L_{I}((v_{F})) = ∑_{F ∈F} v_{F} h(|E ∧ F |)  (∗)

Since L_{I}((v_{F})) = 0, ∀I ∈ X_{0} ∪ X_{1} ∪ ⋯ ∪ X_{k}, the left hand side is equal to 0. We know if F ≱ E, then l(E ∧ F) < l(E) = j_{0} and so |E ∧ F | ∈ {m_{l}, m_{l+1}, ⋯, m_{j_{0}−1}} which implies h(|E ∧ F |) = 0; if F ≥ E and F ≠ E, then l(F) > l(E) = j_{0} and by the definition of J and j_{0}, v_{F} = 0. So the right hand side of (∗) is equal to h(|E ∧ E|)v_{E} = h(|E|)v_{E}. Since h(|E|) ≠ 0, we get v_{E} = 0, a contradiction. This proves Lemma 3 and therefore completes the proof of Theorem 2.

§4. The Proof of Theorem 3

Let l = | ∪_{i=0}^{k} X_{i}| = ∑_{i=0}^{k} |X_{i}|. We consider the |F| by l 0-1 matrix M whose rows are indexed by elements of F and whose columns are indexed by elements of Y_{k}, where Y_{k} := ∪_{i=0}^{k}X_{i} for k = 0, 1, …, n. For F ∈ F, S ∈ Y_{k}, the (F, S)-entry of M is defined to be 1 if either F ∈ Y_{k} and S = F or F ∈ X − Y_{k}, S ∈ X_{k} and S ≤ F. It is defined to be 0 otherwise.

the electronic journal of combinatorics 4 (1997), #R28 12

Observations. It is clear from the above definition of M that

(1) if the (F, S)-entry of M is 1 then S ≤ F,

(2) each row has at least one nonzero entry, and

(3) if F ∈ F and F ∈ X_{u}, u > k, then the row corresponding to F has f_{k}(m_{u}) > 1 nonzero entries (see remark 4 in the introduction).

Claim. For F ≠ E ∈ F, the (F, E)-entry in MM^{T} is 0.

Proof of the claim. Suppose the (F, E)-entry of MM^{T} is ≥ 1. Then there exists an S ∈ Y_{k} such that both the (F, S)-entry and the (E, S)-entry of M are 1. By observation (1), S ≤ F ∧ E, so S ∈ ∪_{i=0}^{k−1}X_{i} = Y_{k−1} since F is a {0, 1, …, k − 1}- intersection family. But from the definition of M, for such an S, the (F, S)-entry of M is 1 if and only if F = S. The same is true for the (E, S)-entry. So F = S = E, which is a contradiction. This proves the claim.

From the above claim, it is clear that MM^{T} is a diagonal matrix, and it is also clear that the diagonal entries are nonzero by observation (2) above. So MM^{T} is a nonsingular |F| by |F| matrix.

Therefore Rank(M) = Rank(MM^{T}) = |F|. Since M is an |F| by l matrix, we must have l ≥ |F|.

Now suppose |F| = ∑_{i=0}^{k} |X_{i}|, so M is a square matrix. It is clear that each column can contain at most one nonzero entry, otherwise MM^{T} would not be a diagonal matrix. So the total number of 1’s in M is ≤ |F|. Therefore by observation (2) the total number of 1’s in M is |F|. So each row of M should contain exactly one nonzero entry by the above observations. This means that F ∈ Y_{k} for any F ∈ F. So F ⊆ Y_{k} = ∪_{i=0}^{k}X_{i}. But |F| = ∑_{i=0}^{k} |X_{i}|, so F = ∪_{i=0}^{k}X_{i}.

Remark . For the proof of Theorem 4, we consider the 0-1 incidence matrix M_{k} whose rows and columns are indexed by the elements of F and X_{k} respectively. The rest of the proof is similar to but simpler than that of Theorem 3 above and hence omitted.

§5. The Proof of Theorem 5

the electronic journal of combinatorics 4 (1997), #R28 13

Define g_{i}(x) = (x − m_{0})(x − m_{1}) ⋯ (x − m_{i−1}) for i = 1, 2, ⋯, s and g_{0}(x) = f_{0}(x) = 1. Since g_{i}(x)’s are monic, there exist s + 1 integers b_{0}, b_{1}, ⋯, b_{s} such that (x − m_{l_{1}})(x − m_{l_{2}}) ⋯ (x − m_{l_{s}}) = ∑_{i=0}^{s} b_{i}g_{i}(x). So

(x − m_{l_{1}})(x − m_{l_{2}}) ⋯ (x − m_{l_{s}}) = ∑_{i=0}^{s} c_{i}f_{i}(x)  (4)

where c_{i} = b_{i}(m_{i} − m_{0})(m_{i} − m_{2}) ⋯ (m_{i} − m_{i−1}) are integers for i = 1, 2, ⋯, s and c_{0} = b_{0}, since by remark 4 in the introduction f_{i}(x) = g_{i}(x)/(m_{i} − m_{0})(m_{i} − m_{2}) ⋯ (m_{i} − m_{i−1}) for i = 1, 2, ⋯, s.

For 0 ≤ l ≤ k we define M_{k,l} to be an incidence matrix whose rows and columns are indexed by elements of X_{k} and X_{l} respectively. For A ∈ X_{k}, S ∈ X_{l}, the (A, S)-entry is 1 if S ≤ A and 0 otherwise.

The (A, B)-entry of M_{k,s}M_{s,i} is easily seen to be the number of elements S such that A ≥ S ≥ B where A ∈ X_{k}, S ∈ X_{s}, B ∈ X_{i}. Therefore from the definition of polynomial semi-lattice it follows that this number is f_{s−i}(m_{k−i}) and hence

M_{k,s}M_{s,i} = f_{s−i}(m_{k−i})M_{k,i} for i ≤ s ≤ k.

From this we see that the column space of M_{k,i} is contained in that of M_{k,s} for i = 0, 1, …, s.

Then the column space of the integer matrix M := ∑_{i=0}^{s} c_{i}M_{k,i}M_{k,i}^{T} is contained in that of M_{k,s}. So rank(M) ≤ rank(M_{k,s}) ≤ |X_{s}|.

Define M_{F} to be the submatrix of M, whose rows and columns are indexed by elements of F. Similarly as in the proof of Lemma 2 of §3, we easily check that the (A, B)-entry of M_{F} is ∑_{i=0}^{s} c_{i}f_{i}(|A ∧ B|) which by (4) above is equal to

(|A ∧ B| − m_{l_{1}})(|A ∧ B| − m_{l_{2}}) ⋯ (|A ∧ B| − m_{l_{s}}).

So the (A, B)-entry of M_{F} is ≡ (|A∧B|−μ_{1})(|A∧B|−μ_{2}) ⋯ (|A∧B|−μ_{s}) (mod p).

Now if A ≠ B, then |A ∧ B| ∈ L and therefore |A ∧ B| is congruent to one of μ_{1}, μ_{2}, ⋯, μ_{s} by the condition of Theorem 5, so the (A, B)-entry of M_{F} is ≡ 0 (mod p); if A = B, then |A ∧ B| = |A| = m_{k} which is not congruent to any one of μ_{1}, μ_{2}, ⋯, μ_{s}, so the (A, A)-entry of M_{F} is ≢ 0 (mod p).

the electronic journal of combinatorics 4 (1997), #R28 14

In summation we have: (A, B)-entry of M_{F} is ≡ 0 (mod p) if A ≠ B but ≢ 0 (mod p) if A = B.

So M_{F}, considered as a matrix over 𝔽_{p}, the finite field of order p, is a square matrtix whose diagonal entries are nonzero and whose nondiagonal entries are 0. So det(M_{F}) ≢ 0 (mod p). This implies that det(M_{F}) is a nonzero rational integer and therefore M_{F} is nonsingular.

Therefore |F| = rank(M_{F}) and hence |F| = rank(M_{F}) ≤ rank(M) ≤ |X_{s}|.

§6. The Proof of Theorem 6

We keep the notations as in the proof of Theorem 5 in §5. In particular, by the argument in §5, we have the following fact:

there exist s + 1 integers c_{0}, c_{1}, ⋯, c_{s} such that (x − μ_{1})(x − μ_{2}) ⋯ (x − μ_{s}) ≡ ∑_{i=0}^{s} c_{i}f_{i}(x) (mod p).

Define M_{i} to be the 0-1 incidence matrix of F and X_{i} whose rows and columns are indexed by the elements of F and X_{i} respectively. The (F, S)-entry of M_{i} is 1 if and only if F ≥ S, 0 otherwise. It is not hard to see that the (F, E)-entry of M_{i}M_{i}^{T} is f_{i}(|F ∧ E|).

Define M_{F} to be an integer matrix whose rows and columns are indexed by the elements of F. The (F, E)-entry of M_{F} is ∑_{i=0}^{s} c_{i}f_{i}(|F ∧ E|). It is clear that each row of M_{F} is a linear combination of rows of M_{0}M_{0}^{T} , M_{1}M_{1}^{T} , ⋯, M_{s}M_{s}^{T} and so

rank(M_{F}) ≤ ∑_{i=0}^{s} rank(M_{i}M_{i}^{T}) ≤ ∑_{i=0}^{s} |X_{i}|.

By a similar argument as in the proof of Theorem 5, we can show that M_{F}, considered as a matrix over 𝔽_{p}, is such that all the nondiagonal entries are 0 and all the diagonal entries are nonzero. So det(M_{F}) ≢ 0 (mod p), which implies that det(M) ≠ 0 in ℤ. So M is nonsingular and therefore |F| = rank(M) ≤ ∑_{i=0}^{s} |X_{i}|.

References

[1] N. Alon, L. Babai and H. Suzuki, “Multilinear Polynomials and Frankl-Ray-Chaudhuri-Wilson Type Theorems,” Journal of Combinatorial Theory Ser(A), 58: 165-180, 1991.

the electronic journal of combinatorics 4 (1997), #R28 15

[2] L.Babai and P. Frankl, “Linear Algebra Methods in Combinatorics,” (Preliminary version 2) Department of Computer Science, University of Chicago.

[3] M.Deza, P.Frankl and N.M.Singhi, “On functions of strength t,” Combinatorica 3 (1983) 331-339.

[4] P. Frankl and Z. Füredi, “Families of Finite sets with missing intersections,” Colloquia Mathematica Societatis Janos Bolyai 37:305-320, 1981.

[5] P. Frankl and R. M. Wilson, “Intersection Theorem with Geometric Consequences,” Combinatorica 1(4) (1981) 357-368.

[6] G. V. Ramanan, “Proof of a conjecture of Frankl and Füredi,” To appear.

[7] D. K Ray-Chaudhuri and R. M Wilson, “On t-designs,” Osaka J. Math 12(1975), 737-744.

[8] D. K. Ray-Chaudhuri and Tianbao Zhu, “S-Intersection Families and Tight Designs,” Coding Theory, Design Theory, Group Theory Proceeding of Marshall Hall Conference. Page: 67-75 John-Wiley & Sons 1993.

[9] H. S Snevily, “A generalization of the Ray-Chaudhuri-Wilson theorem,” J. Comb. Des. 3(1995) No. 5 349-352.