% A LaTex file for a 14 page document

\documentclass[12pt,oneside]{amsart}
\usepackage{amssymb,amsmath,amscd}
\setlength{\textheight}{8.5 in}
\setlength{\textwidth}{6.0 in}
\setlength{\leftmargin}{-1.5 in}
\renewcommand{\baselinestretch}{1.5}

\begin{document}
\pagestyle{myheadings}
\markboth{\hfill \sc the electronic journal of combinatorics 4 (1997), \#R27} 
{\sc the electronic journal of combinatorics 4 (1997), \#R28\hfill}
\thispagestyle{empty}

\centerline { \bf Frankl-F\"uredi Type Inequalities 
for Polynomial Semi-lattices}

\centerline { Jin Qian \;and \; Dijen K.\; Ray-Chaudhuri\footnote{e-mail addresses: \texttt{<qian@math.ohio-state.edu>, <dijen@math.ohio-state.edu>}}}

\centerline { Department of Mathematics }

\centerline { The Ohio State University }
\bigskip
\centerline{Submitted: April 2, 1997; Accepted: October 20, 1997}

\bigskip


\centerline {\bf Abstract}
~~~Let $X$ be an $n$-set and $L$ a set of nonnegative integers.\;
 ${\mathcal F}$, a set of subsets of $X$, is said to be  an $L$ 
-intersection family if and only if for all $E \neq F \in {\mathcal F}, \,
|E \cap F | \in L$. \; A special case of a conjecture of Frankl and 
F\"uredi [4] states that 
if $ L = \{1, 2, \dots,k\}$,\;\;$ k$ a positive integer,\; then
$|{\mathcal F}| \leq\sum_{i=0}^{k}\binom{n-1}{i}$.\;

Here $|{\mathcal F}|$ denotes the number of elements in ${\mathcal 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.


\bigskip

\S1.\; { \bf Introduction}
\smallskip

Throughout the paper, we assume $k, n \in \mathbb N $, 
$I_n = \{1,2, \dots, n\} \subset \mathbb N$, where
$\mathbb  N$ 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,\leq)$ be a finite nonempty partially 
ordered set having the property that
$(X,\leq)$ is a semi-lattice, i.e., for every $ x,y\in X $ there is a unique
greatest lower bound of $x$ and $y$ denoted by $x\wedge y$.\;  
If $x\leq y$ and $x \neq y$, we write $ x < y$. We also assume
that $(X,\leq)$ 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 \in X|~l(x)=i\}$,
$ 0 \leq i \leq n$ and $X_0=\{0\}$.\;
  Then $X=\cup_{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, \leq)$.\;

   $(X,\leq)$ is called a polynomial semi-lattice, if for each fibre $X_i$
there is a size number $m_i \in {\mathbb N} \cup \{0\}$ and a polynomial 
$f_i(w)\in  {\mathbb Q}[w]$, where ${\mathbb Q}$
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)\dots (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\leq k\leq i \leq j \leq n$,\, $x\in X_k$,
\, $y\in X_j$ and $x \leq y$, \,
$|\{z~|~z\in X_i, x\leq z\leq y\}|=f_{i-k}(m_{j-k})$.\;

\bigskip

{\em Remarks.}

1)  Taking $k=0$ in c), we have  $|\{z~~|~~z\in X_i, z\leq y\}|=
f_i(m_j)$ for every $y \in  X_j$.

2) For any $x \in X$ 
we define $|x|$ to be $m_i$ if $x \in X_i$.\;  Specializing 
$y = E \wedge F$ in remark 1),  we have
   $|\{I\in X_i~~|~~I\leq
    E\wedge F\}|=f_i(|E\wedge F|)$, where $E, F\in 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\in X_i, z\leq y\} = \{y\}$.\;  {From} this we can solve for $a_i$:
$$ a_i = \frac{1}{(m_i-m_0)(m_i-m_1)\dots(m_i-m_{i-1})}$$ for 
$i = 1,2,\dots,n$.\;

4)  {From} remark 3), we get 
$$ f_i(w) = \frac {(w-m_0)(w-m_1)\dots(w-m_{i-1})}
{(m_i-m_0)(m_i-m_1)\dots(m_i-m_{i-1})}.$$
For $j > i$, we have $m_j > m_i$ and therefore $f_i(m_j) > 1$.

\smallskip

In the following examples we let $s \in {\mathbb N}$, $q$ be a prime power,
and $$[w,i]_q=\frac{(w-1)(w-q)\cdots (w-q^{i-1})}{(q^i-1)(q^i-q)\cdots(q^i
   -q^{i-1})}.$$

\bigskip

Examples:

1)  {\em Johnson Scheme}.\;  Let $V$ be an
 $n$-element set and $X_i$ be the set of
    all $i$-element subsets of $V,0\leq i\leq n$.\;  Then $X=\cup_{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,\leq)$ is a polynomial semi-lattice.\;

2)  {\em $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\leq i\leq n$.\;  Let $m_i=q^i, f_i(w)=[w,i]_q$ (defined 
after remark 4).\;  Then
$X=\cup_{i=0}^n X_i$ is a polynomial semi-lattice with inclusion as the partial
   order.\;

3) {\em Hamming Scheme}.\;
  Let $W$ be an $s$-element set.\;  We define $X_i=\{(L,
   h)~|~L\subseteq\{1,2,\dots,n\},~~ |L|=i,~~ h:L \to W$ \; a map $\},
 1\leq i\leq n,~~~
X_0=\{0\}$, where $0$ is taken to be the {\em least element}, and
$X=\cup_{i=0}^n X_i$.\;  $(L_1,h_1) \leq (L_2,h_2)$ if and only if $L_1\subseteq
 L_2$, and $h_2|_{L_1}=h_1$.\;  Then $(X,\leq)$ is a polynomial semi-lattice,
with $m_i=i,  f_i(w)=\binom{w}{i}$.\;

4) {\em $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 \subseteq W, dim(U)=i$, \,
$ h:U\to V$, a linear
   transformation$\}$, $0\leq i\leq n$.\;  Let $X=\cup_{i=0}^n X_i$.\;
  $\forall (U_1,h_1), (U_2, h_2)\in X$, define $(U_1, h_1)\leq (U_2, h_2)$
 if and only if $U_1 \subseteq  U_2$ and $h_2|_{U_1}=h_1$.\;
Then $(X,\leq)$ is a polynomial semi-lattice,
    with $m_i=q^i, f_i(w)=[w,i]_q$.\;

5)  {\em Ordered Design}.\;  Let $W$ be an $s$-element set
and $V$ be an $n$-element set with $n \leq s$.\;  We define
$X_i=\{(L,h)~|~L\subseteq\{1,2,\dots, n\},|L|=i$, \, $ h:L\to W$ 
an injection$\}$,
$1\leq i \leq n$, $X_0=\{0\}$, where $0$ is taken as the {\em least element},
 and
 $X=\cup_{i=0}^nX_i$.\; 
$\forall (L_1,h_1),(L_2,h_2)\in X$, define $(L_1,h_1)\leq
   (L_2,h_2)$ if and only if $L_1\subseteq L_2$ and $h_2|_{L_1}=h_1$.\;  Then
   $(X,\leq)$ is a polynomial semi-lattice, with $m_i=i, f_i(w)=\binom{w}{i}$.\;

6)  {\em $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 \leq s$.\; 
 Define $X_i=\{(U,h)~|~U\subseteq V,dim(U)=i$, \,$ h:U\to W$, a 
nonsingular linear transformation $\}$, $0\leq i\leq n$.\;
Let $X=\cup_{i=0}^n X_i$.
\; $ \forall (U_1,h_1), (U_2,h_2)\in X$, define $(U_1,h_1)\leq(U_2, h_2)$ if
   and only if $U_1\subseteq U_2$ and $h_2|_{U_1}=h_1$.\;  Then $(X,\leq)$ is a
   polynomial semilattice, with $m_i=q^i, f_i(w)=[w,i]_q$.\;

\bigskip

\S2.\; {\bf Statement of Results}

\smallskip

Let $(X,\leq)$ be a polynomial semi-lattice of height $n$, i.e 
$X = \cup_{i=0}^n X_i$ and
$L$ be a $k$-subset of $I_n \cup \{0\}$, where $k \leq n$ is a natural number.
We call ${\mathcal F}\subseteq X$ an $L$-intersection family if and only if
$\forall E\neq F\in{\mathcal F}$,
$ E\wedge F\in \cup_{l\in L} X_l$. If ${\mathcal 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 ${\mathcal 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]:

\bigskip

{\bf Theorem 1}. Let $(X,\leq)$ be a polynomial semi-lattice.\; 
If ${\mathcal F} \subseteq X$ is an $L$-intersection family, 
then $|{\mathcal F}| \leq\sum_{i=0}^k|X_i|$.\;

\bigskip

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

\bigskip

{\bf Theorem 2.} Let $(X,\leq)$ be a semi-lattice
of height $n$, $l, k \in {\mathbb N}$, $l+k-1 \leq n$
and ${\mathcal F}$ be an $\{l,l+1,
\dots,l+k-1\}$-intersection family.\; Then

$|{\mathcal F}| \leq|X_k|+|X_{k-2}|+\dots+|X_{k-[k/ 2]2}|$.\;

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

\smallskip

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

\smallskip

   In the case of Johnson scheme where $|X_n| = \binom{n}{i}$, $ 0 \leq i 
\leq n$,  we have the
\bigskip

{\bf Corollary.}  Let $X$ be an $n$-set.\; If  ${\mathcal F}$ is a 
family of subsets of $X$ such
that $\forall E \neq F \in {\mathcal F}$, $|E \cap F| \in \{1,2,\dots,k\}$,
then $|{\mathcal F}| \leq\sum_{i=0}^{k}\binom{n-1}{i}$.\;

\bigskip

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

$$\sum_{i=0}^{[k/2]}\binom{n}{k-2i}=
    \sum_{i=0}^k \binom{n-1}{k-i} .\;$$

\smallskip 

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

{\bf Conjecture 1.}
Let $k  \in {\mathbb N}$, $l \in {\mathbb N} \cup \{0\}$, 
 $k>2l+1$, $n > n_0(k)$, $X$ be an $n$-set,
$ L=\{0,1,2,\cdots,k\}-\{l\}$.\;
If ${\mathcal F}$ is an $L$-intersection family of subsets of $X$, then
$$|{\mathcal F}| \leq \sum_{i\leq l-1}\binom{n}{i} +
 \sum_{i=l+1}^{k+1}\binom{n-l-1}{i-l-1} .$$
Ramanan proved the special case of Frankl-F\"uredi conjecture when
$l=0$. The general case is still open.




\bigskip

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

\bigskip

{\bf Theorem 3.} Let $(X,\leq)$ be a polynomial semi-lattice.\;  If 
${\mathcal F}$ is an $L$-intersection family 
for $L=\{0,1,\dots,k-1\}$,   then $|{\mathcal F}|\leq
\sum_{i=0}^k|X_i|$.\;

The equality holds if and only if ${\mathcal F}=\cup_{i=0}^kX_i$.


\bigskip


In the direction of Theorem 1, Snevily [9] studied the case 
$L= \{0,1,\cdots, k-1\}$, and $\forall E \in {\mathcal F}, |E| \geq 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.\;

\smallskip

{\bf Theorem 4.} Let $(X,\leq)$ be a polynomial semi-lattice of height $n$,
 $ k \in {\mathbb N}$, 
${\mathcal F}$ an  $L$-intersection family for
 $L=\{0,1,\dots,k-1\}$ and ${\mathcal F} \subseteq \cup_{i=k}^nX_i$.\;
 Then $|{\mathcal F}|\leq |X_k|$.\;

The equality holds if and only if ${\mathcal F}= X_k$.

\bigskip

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

\smallskip

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

\bigskip

 {\bf Theorem 5.}
Let $(X,\leq)$ be a polynomial semi-lattice of height $n$,
$s$, $  k \in {\mathbb N}$ with $s \leq k$,
 $L \subseteq I_n\cup\{0\}$ and
${\mathcal F} \subseteq X_k$  an $L$-intersection family.\;
  Suppose  $\mu_0,\mu_1,\cdots, \mu_s$
 are distinct residues modulo a prime $p$ such that $m_k
\equiv \mu_0 \pmod{p}$
and $\forall l\in L, m_l \equiv \mu_i \pmod{p}$ for some $i,1\leq i\leq s$.\;
Further suppose that for every $\mu_i$, $\exists l_i \in L$, such that 
$m_{l_i} \equiv \mu_i$ $(mod$ $p)$, for $i=1,2, \cdots, s$.
Then $|{\mathcal F }| \leq |X_s|$.\;

\bigskip

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

\smallskip

{\bf Theorem 6.}
Let $(X, \leq)$ be a polynomial semi-lattice of height $n$ and
${\mathcal F} \subseteq X_{k_1}\cup X_{k_2}\cup \cdots \cup X_{k_{\nu}}$ 
be an $L$-intersection family, where $L
\subseteq I_n \cup \{ 0 \}$ and $k_1,k_2,\cdots,k_{\nu}$ are integers
in $ I_n\cup\{0\}$.\;
 Suppose $\mu_1, \mu_2, \cdots,
\mu_s$ are distinct residues modulo a prime $p$ such that $\forall l \in L,
m_l \equiv \mu_i \pmod {p}$ for some $i,1 \leq i\leq s$ 
and $m_{k_i}$ is not
congruent to any one of $\mu_1, \mu_2, \cdots, \mu_s$ modulo $p$ for $i=1,2,
\cdots, \nu$.\;
  Then $|{\mathcal F}| \leq \sum_{i=0}^s |X_i|$.\;

\bigskip

  \S3.\; {\bf The Proof of Theorem 2}
\bigskip

Convention: Empty product is defined to be $1$.\;

 First we prove two lemmas.\;

\smallskip

{\bf Lemma 1}. Let $k, \in {\mathbb N}$ and $l_1 < l_2< \cdots <l_k $
be $k$ positive integers in $I_n$.\;
 There exist $k+1$ positive real numbers $b_0, b_1,\dots, b_k$
 such that
$$\sum_{i=0}^k(-1)^i b_i f_i(x)
=(-1)^k (x-m_{l_1})(x-m_{l_2})\dots(x-m_{l_k}).$$
{\bf Proof}.  Recall that $f_i(x)=a_i(x-m_0)(x-m_1)\dots(x-m_{i-1})$
 and $m_0<m_1<\dots<m_n$, where $a_i$'s are positive.\;
 So it is enough to prove that
there exist positive real numbers $c_0, c_1, \cdots, c_k$ such that

$\sum_{i=0}^k(-1)^i c_i (x-m_0)(x-m_1)\cdots(x-m_{i-1})
=(-1)^k (x-m_{l_1})(x-m_{l_2})\dots(x-m_{l_k})$.\;

The above result follows from the following more general statement:

{\em Claim.}\;  For any $j$ such that $ 0\leq j < l_1$, there exist    
 positive real numbers $d_0,d_1, \cdots, d_k$  such that
$$\sum_{i=0}^k(-1)^id_i(x-m_j)
(x-m_{j+1})\cdots (x-m_{j+i-1})
=(-1)^k(x-m_{l_1})(x-m_{l_2})\cdots (x-m_{l_k}).$$

{\em 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$.
\begin{align*}
  &(-1)^{k+1}(x-m_{l_1})(x-m_{l_2})\cdots (x-m_{l_{k+1}}) \\
 =&(-1)(x-m_{l_1}) [(-1)^k(x-m_{l_2})\cdots(x-m_{l_{k+1}})] \\
 =&(-1)[(x-m_j)-(m_{l_1}-m_j)][(-1)^k(x-m_{l_2})\cdots(x-m_{l_{k+1}})] \\
 =&(-1)(x-m_j)[(-1)^k(x-m_{l_2})\cdots(x-m_{l_{k+1}})]+ \\
  &(m_{l_1}-m_j)[(-1)^k(x-m_{l_2})\cdots(x-m_{l_{k+1}})]  &(1)
 \end{align*}
Since $j+1 < l_1+1$, we can apply the induction hypothesis to the first term of
(1) (denoted by {\bf I}) and we have
\begin{eqnarray*}
{\bf I}&=&(-1)(x-m_j)\sum_{i=0}^k(-1)^iu_i(x-m_{j+1})\cdots(x-m_{j+1+i-1})\\
&=&\sum_{i=0}^k(-1)^{i+1}u_i(x-m_j)(x-m_{j+1})\cdots(x-m_{j+1+i-1})
\end{eqnarray*}
for some positive real numbers $u_k, u_{k-1}, \cdots, u_0$.\;
Then we use the induction hypothesis on the second term (denoted by {\bf II}) and
we have
\begin{eqnarray*}
{\bf II}&=&(m_{l_1}-m_j)\sum_{i=0}^k(-1)^iv_i(x-m_j)\cdots(x-m_{j+i-1})\\
&=&\sum_{i=0}^k(-1)^i(m_{l_1}-m_j)v_i(x-m_j)\cdots(x-m_{j+i-1})
\end{eqnarray*}
for some positive real numbers $v_k, v_{k-1}, \cdots, v_0$.\;
Now add up {\bf I} and {\bf II} and we have
\begin{eqnarray*}
& &(-1)(x-m_j)[(-1)^k(x-m_{l_2})\cdots(x-m_{l_{k+1}})]+ \\
& &    (m_{l_1}-m_j)[(-1)^k(x-m_{l_2})\cdots(x-m_{l_{k+1}})]\\
&=&\qquad\sum_{i=0}^{k+1}(-1)^id_i((x-m_j)\cdots(x-m_{j+i-1})
\end{eqnarray*}
where
\begin{eqnarray*}
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},\\
&\cdots&\\
d_0&=&(m_{l_1}-m_j)v_0.
\end{eqnarray*}
so $d_{k+1},d_k, \cdots, d_0$ are positive, which proves the claim and therefore
the lemma.\; \qed

 \smallskip

{\em 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, \cdots, l_k = l+k-1$.
   Let's denote $(x-m_l)(x-m_{l+1})\dots(x-m_{l+k-1})$ by $g(x)$.\;
Since ${\mathcal F}$ is an $\{ l,l+1, \cdots, l+k-1\}$-intersection family, 
$|E| \geq m_l$ for all $E \in {\mathcal F}$.\; So it is clear that 
$g(|E|) \geq 0$ for all $E \in {\mathcal F}$
 and $g(|E|) > 0$ if $|E| > m_{l+k-1}$.\;

To each $ E \in {\mathcal F}$ 
we associate a variable $x_E$.\; For each $I \in X $ ,
we define a linear form $L_I$ as follows:

$$L_I:= \sum_{{E \in {\mathcal F}},{ I \leq E}} x_E. $$

\bigskip

{\bf Lemma 2.}\;  With the same notation as in Lemma 1 and further we assume 
that $l \in {\mathbb N}$, $l+k-1 \leq n$, $l_1 =l$, $l_2 =l+1, \cdots, 
l_k = l+k-1$.\;  We have 
 $$\sum_{i=0}^k(-1)^i b_i{\sum_{I\in X_i}L_I^2}=
\sum_{E\in{\mathcal F}}
(-1)^k g(|E|)x_E^2 \; .\; \eqno(2)$$

{\bf Proof}. We regard both sides as quadratic forms on $ x_E$'s,
where $E \in {\mathcal F}$ and try to show that the corresponding coefficients
are equal.\;

For example, for $E \neq F \in {\mathcal F}$, the term $L_I^2$ contributes 
a term $2x_Ex_F$ if and only if $I \leq E\wedge F$.\; Therefore
 the coefficient of $x_Ex_F$ in the
L.\;H.\;S of $(2)$ is $2 \sum_{i=0}^k(-1)^ib_if_i(|E \wedge F|)$
(see remark 2 in the introduction)
which is equal to 
\[2(-1)^k(|E\wedge F| -m_l)((|E\wedge F| -m_{l+1})\dots
(|E\wedge F|-m_{l+k-1})\]
by Lemma 1.\;
 Since ${\mathcal F}$ is an $L$-intersection 
family with $L = \{ l, l+1,\dots,l+k-1 \}$, \,
$|E\wedge F| \in \{m_l, m_{l+1}, \dots,
m_{l+k-1}\}$  and so the product in the previous sentence is $0$.\; 
Obviously the coefficient of $x_Ex_F$ in the R.H.S is also $0$.\;
So the coefficient of $x_Ex_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 $\sum_{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.
\qed

\bigskip

We define the real vector space $W$ to be ${\mathbb R}^{|{\mathcal F}|}$ whose 
coordinates are  indexed by elements of 
${\mathcal F}$, \, ${\mathcal L}$ to be the set  of linear forms 
$\{L_I \; : \;  |I| \in \{m_k, m_{k-2},
\dots,m_{k-[k/2]2}\}\}$ and  $W_0 \subseteq W$
to be the space of common solutions of the set of equations 
$L_I = 0$,  $L_I\in {\mathcal L}$.\; Clearly $|{\mathcal L}| = 
\sum_{i=0}^{[k/2]}|X_{k-2i}|$.\; An element of $W_0$ will be written as
$(v_E, E \in {\mathcal F})= (v_E)$ (for short).

   If we can show that $W_0$ consists of  the zero vector only, then by
linear algebra,  $rank({\mathcal L}) = $ the number of variables 
$= |{\mathcal F}|$ and therefore $|{\mathcal F}|
= rank({\mathcal L}) \leq |{\mathcal L}| = \sum_{i=0}^{[k/2]}|X_{k-2i}|$, 
which finishes the proof of Theorem 2.\; 

So it is enough to prove

{\bf Lemma 3.} $W_0=\{(0,0,\dots,0)\}$.\;

{\bf Proof.}
   Suppose $W_0$ contains $(v_E)$.\; It suffices to show $v_E = (0,0,\dots,0)$.\;

  By Lemma 2, we have
$$\sum_{i=0}^k(-1)^i b_i{\sum_{I\in X_i}L_I^2}=(-1)^k\sum_{E\in{\mathcal F}}
g(|E|)x_E^2 .\;$$

Specializing $x_E = v_E, \forall E \in {\mathcal F}$, we have 

$$\sum_{i=0}^k(-1)^i b_i{\sum_{I\in X_i}L_I
^2((v_E))}=(-1)^k\sum_{E\in{\mathcal F}}g(|E|)v_E^2 .\;$$

Since $L_I((v_E))=0$, for
all $L_I\in{\mathcal L}$, we have $L_I((v_E))=0$ for $k-i$ even and thus
 $$\sum_{i\in\{0,1,\dots,k\}, k-i~ is~ odd} 
(-1)^ib_i \sum_{I\in X_i}L_I^2((v_E))=(-1)^k\sum_{E\in{\mathcal 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=\sum_{i\in\{0,1,\dots,k\},k-i~ is~ odd}b_i \sum_{I\in X_
i}L_I^2((v_E))+\sum_{E\in{\mathcal F}}g(|E|)v_E^2.\; \eqno(3)$$

Since $b_i$'s are positive by Lemma 1 and $g(|E|) \geq 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$, {\em 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 \S1.
The equation 
 $(3)$ also implies that $L_I((v_E))=0$ for $I \in X_i$, $i=k-1,
k-3, \cdots$.
So $L_I((v_E))=0$ for all $I \in X_0\cup X_1\cup \cdots \cup 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 \in {\mathcal F}$, we assume the contrary.
Define $J=\{l(E) |  E \in {\mathcal F}, v_E \neq 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 \leq j_0 \leq k+l-1$.

In the following, we distinguish 2 cases:

Case 1. 
 Suppose $j_0=l$,  then there exists an $E \in {\mathcal F}$ with $l(E)=l$ and
$v_E \neq 0$.

Since ${\mathcal F}$ is an $\{l, l+1, \cdots,l+k-1\}$-intersection
family, $l(E\wedge F) \geq l = l(E)$ for $\forall F \in {\mathcal F}$,
  so either $F > E$ or $F=E$.
If $F \neq 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)) = \sum_{F \in {\mathcal F}}v_F
=v_E$, we have $v_E=0$, a contradiction. 

Case 2. Suppose $l < j_0 \leq l+k-1$ and there exists an
$E \in {\mathcal F}$ such that $l(E) =j_0$ and $v_E \neq 0$.
We fix such an $E$.

Since $f_0, f_1, \cdots, f_{j_0-l}$ form a base of the vector space
of polynomials of degree $\leq j_0-l$, there exist real numbers
$c_0, c_1, \cdots, c_{j_0-l}$ such that $$\sum_{i=0}^{j_0-l} c_if_i(x)
=(x-m_l)\cdots (x-m_{j_0-1}).$$ 
In the following we let $h(x) =(x-m_l)\cdots (x-m_{j_0-1})$ and define
$\lambda_I(E) =1$ if $ I \leq E$ and $0$ otherwise.

As in the proof of Lemma 2, we have
\begin{align*}
 &\sum_{i=0}^{j_0-l}c_i\sum_{I \in X_i}\lambda_I(E)L_I \\
=&\sum_{i=0}^{j_0-l}c_i\sum_{F \in {\mathcal F}}x_F|\{I |  I \in X_i, I \leq 
F, I \leq E\}| \\
=&\sum_{i=0}^{j_0-l}c_i\sum_{F \in {\mathcal F}}x_Ff_i(|F\wedge E|)\\
=&\sum_{F \in {\mathcal F}}x_F\sum_{i=0}^{j_0-l}c_if_i(|F\wedge E|) \\
=&\sum_{F \in {\mathcal F}}x_Fh(|E\wedge F|).
\end{align*}

Specializing $x_F=v_F$, $\forall F \in {\mathcal F}$, we have
$$\sum_{i=0}^{j_0-l}c_i\sum_{I \in X_i}\lambda_I(E)L_I((v_F))=
\sum_{F \in {\mathcal F}}v_Fh(|E\wedge F|) \eqno{(*)}$$
Since $L_I((v_F))=0, \forall I \in X_0\cup X_1\cup\cdots \cup X_k$, the 
left hand side is equal to $0$.
We know if $F \not \geq E$, then $l(E\wedge F) < l(E)=j_0$ and so
$|E\wedge F| \in \{m_l, m_{l+1}, \cdots, m_{j_0-1}\}$ which implies
$h(|E\wedge F|)=0$; if $ F \geq E$ and $F \neq 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 \wedge E|)v_E=h(|E|)v_E$. Since $h(|E|) \neq 0$,
we get $v_E=0$, a contradiction.
 This proves  Lemma 3 and therefore completes the proof of
 Theorem 2.

\bigskip

 \S4.\; {\bf The Proof of Theorem 3}

\smallskip

Let $l =|\cup_{i=0}^kX_i|=  \sum_{i=0}^k|X_i|$.\; We 
consider the $|{\mathcal F}|$ by $l$ $0$-$1$
matrix $M$ whose rows are indexed by 
elements of ${\mathcal F}$
 and whose columns are indexed by elements of $Y_k$, 
where $Y_k:=\cup_{i=0}^k X_i$ for $k = 0, 1, \dots, n$.\; 
 For $F \in{\mathcal F}, S\in Y_k$, 
 the $(F,S)$-entry of $M$ is defined to be $1$ if either $F \in Y_k$ and $S=F$ 
or $F \in X-Y_k$, \, $S \in X_k$
and $S\leq F$.\;  It is defined to be $0$ otherwise.\;

{\em Observations.} It is clear from the above definition of $M$ that

(1) if the $(F,S)$-entry of $M$ is $1$ then $S \leq F$, 

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

(3) if $F \in {\mathcal F}$ and $F \in X_u, u > k$, then the row corresponding 
  to $F$ has $f_k(m_u) > 1$ nonzero 
entries (see remark 4 in the introduction).\;

{\em Claim}. For $F \neq E \in {\mathcal  F}$, 
the $(F,E)$-entry in $MM^T$ is $0$.\;

{\em Proof of the claim.}\;
   Suppose the $(F,E)$-entry of $M M^T$ is $\geq 1$.\; Then there exists 
an  $S\in
Y_k$ such that both the $(F,S)$-entry and the $(E,S)$-entry of $M$ are $1$.\; 
By observation (1),
$S\leq F\wedge E$, so $S \in \cup_{i=0}^{k-1}X_i 
=Y_{k-1}$ since ${\mathcal F}$ 
is a $\{0, 1, \dots, 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.\; 

\smallskip

{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 $|{\mathcal F}|$ by $|{\mathcal F}|$ matrix.\;

Therefore $Rank(M)=Rank(M M^T)= |{\mathcal F}| $.\;
 Since $M$ is an $|{\mathcal F}|$ by $l$ matrix, we must have 
$ l \geq |{\mathcal F}|$.


\smallskip

Now suppose  $|{\mathcal F}| = \sum_{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 $\leq |{\mathcal F}|$.\; Therefore
by observation (2) the total number of $1$'s in $M$ is $|{\mathcal F}|$.
So each row of $M$ should contain exactly one nonzero entry  by the above
observations.\; This means that $F \in Y_k$ for any  $ F \in {\mathcal F}$.\;
So ${\mathcal F} \subseteq Y_k =\cup_{i=0}^k X_i$.\;  
But $|{\mathcal F}|=\sum_{i=0}^k|X_i|$, so ${\mathcal F}
=\cup_{i=0}^k X_i$. \qed

\smallskip

{\em 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 ${\mathcal F}$ and $ X_k$ respectively.\; The rest 
of the proof is similar to but simpler than that of Theorem 3 above and hence 
omitted.

\bigskip

 \S5.\; {\bf The Proof of Theorem 5}

\smallskip

Define $g_i(x) = (x-m_0)(x-m_1)\cdots(x-m_{i-1})$ for $ i= 1,2, \cdots, 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, \cdots, b_s$ such that
$(x-m_{l_1})(x-m_{l_2})\cdots(x-m_{l_s}) = \sum_{i=0}^sb_ig_i(x)$.\;
So
$$(x-m_{l_1})(x-m_{l_2})\cdots(x-m_{l_s})= \sum_{i=0}^sc_if_i(x) \eqno(4)$$
 where $c_i = b_i (m_i-m_0)(m_i-m_2)\cdots(m_i-m_{i-1})$ are integers for 
$i= 1,2, \cdots, 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)\cdots(m_i-m_{i-1})$ for 
$ i= 1,2, \cdots, s$.\;

For $0 \leq l \leq 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 \in X_k, S \in X_l$, the
$(A,S)$-entry is $1$ if $S \leq A $ and $0$ otherwise.\;

\smallskip

The $(A,B)$-entry of $M_{k,s} M_{s,i}$ is easily seen to be the number of 
elements $S$  such that $A \geq S \geq B$ where $ A \in X_k, S \in X_s,
B \in 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\leq s\leq 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,\dots,s$.\;

\smallskip

Then the column space of the integer matrix 
$M:=\sum_{i=0}^s c_i M_{k,i} M_{k,i}^T$ is contained
in that of $M_{k,s}$.\;  So $rank (M)\leq rank(M_{k,s}) \leq |X_s|$.\;

Define $M_{\mathcal F}$ to be the submatrix of $M$, whose rows and columns are
indexed by elements of ${\mathcal F}$.\;  
Similarly  as in the proof of Lemma 2 of \S3, we easily check that 
the $(A,B)$-entry of $M_{\mathcal F}$ 
is $\sum_{i=0}^s c_i f_i(|A\wedge B|)$ which by (4) above is equal to
$$ (|A\wedge B|-m_{l_1})(|A\wedge B|-m_{l_2})\cdots
(|A\wedge B|-m_{l_s}).\;$$
So the $(A,B)$-entry of $M_{\mathcal F}$ is
  $ \equiv (|A\wedge B|-\mu_1)(|A\wedge B|-\mu_2)
\cdots(|A\wedge B|-\mu_s) \pmod{p}$.\;

Now if $ A \neq B $, then $| A \wedge B| \in L$ and therefore $| A \wedge B|$
is congruent to one of $\mu_1,\mu_2,\cdots, \mu_s$ by the condition of
Theorem 5, so the $(A,B)$-entry of $M_{\mathcal F}$ is
$\equiv 0 \pmod{p}$;\;
 if $ A = B$, then $| A \wedge B| = |A| =m_k$ which is not 
congruent to any one of $\mu_1,\mu_2,\cdots, \mu_s$,
so the $(A,A)$-entry of $M_{\mathcal F}$ is $ \not \equiv 0 \pmod{p}$.\;

 In summation we have: $(A,B)$-entry of $M_{\mathcal F}$ is
$\equiv 0 \pmod{p}$ if $A \neq B $ but $\not \equiv 0 \pmod{p}$ if $A = B$.\;

\smallskip

So $M_{\mathcal F}$, considered as a matrix over ${\mathbb F}_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_{\mathcal F})
\not \equiv 0$ $(mod$ $p)$.
This implies that $det (M_{\mathcal F})$  is a nonzero 
rational integer and therefore 
 $M_{\mathcal F}$ is nonsingular.\;

Therefore $|{\mathcal F}|=rank (M_{\mathcal F})$ and 
hence $|{\mathcal F}|=rank (M_{\mathcal F})
\leq rank (M) \leq |X_s|$.\; \qed

\bigskip

\S6.  {\bf The Proof of Theorem 6}

\smallskip

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

{\em  there exist $s+1$ integers $c_0, c_1,\cdots, c_s$ such 
that $(x-\mu_1) (x-\mu_2) \cdots (x-\mu_s)\equiv \sum_{i=0}^s c_i f_i(x)$
$(mod$ $p)$.}\;

Define $M_i$ to be the 0-1 incidence matrix of ${\mathcal F}$ and $X_i$ whose
rows and columns
are indexed by the elements of ${\mathcal F}$ and $X_i$ respectively.\;
The $(F,S)$-entry of $M_i$ is $1$ if and only if $F \geq S$, $0$ otherwise.\;
It is not hard to see that the $(F,E)$-entry of $M_iM_i^T$ is $f_i(|F \wedge
E|)$.\;


Define $M_{\mathcal F}$ to be an integer matrix  whose 
rows and columns are indexed by the elements of ${\mathcal F}
$.\;  The $(F, E)$-entry of $M_{\mathcal F}$ 
is $\sum_{i=0}^s c_i f_i(|F \wedge E|)$.\;
It is clear that each row of $M_{\mathcal F}$
 is a linear combination of rows of $M_0M_0^T,
 M_1M_1^T, \cdots, M_sM_s^T$ and so

$rank(M_{\mathcal F}) \leq \sum_{i=0}^s rank (
M_iM_i^T) \leq \sum_{i=0}^s |X_i|$.\;

By a similar argument as in the proof of Theorem 5, we can show that
$M_{\mathcal F}$, considered as a matrix over 
 ${\mathbb F}_p$,  is such that 
all the nondiagonal entries are $0$ and all the diagonal
entries are nonzero.\;  So $det(M_{\mathcal F}) \not \equiv 0$ $(mod$ $p)$,
which implies that $det(M) \neq 0$ in $\mathbb Z$.\;  So $M$ is 
nonsingular
 and therefore $|{\mathcal F}| = rank (M) \leq \sum_{i=0}^s |X_i|$.\;
    \qed

\bigskip

\centerline{\bf References }

[1] N.\;Alon,  L.\;Babai and H.\;Suzuki,  ``Multilinear Polynomials and 
Frankl-Ray-Chaudhuri-Wilson Type Theorems,"
{\em Journal of Combinatorial Theory Ser(A),} 58: 165-180, 1991.\;

[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,"
 {\em Combinatorica} 3 (1983) 331-339.

[4] P.\;Frankl and Z.\;F\"uredi, ``Families of Finite sets with 
missing intersections,"
{\em Colloquia Mathematica Societatis Janos Bolyai} 37:305-320, 1981.\;

[5] P.\;Frankl and R.\;M.\;Wilson, ``Intersection Theorem with Geometric
Consequences,"  {\em  Combinatorica }1(4) (1981) 357-368.\;

[6] G.\;V.\;Ramanan, ``Proof of a conjecture of Frankl and F\"uredi,"
To appear.

[7] D.\;K Ray-Chaudhuri and R.\;M Wilson, ``On t-designs,"
{\em Osaka J.\;Math} 12(1975), 737-744.\;

[8] D.\;K.\;Ray-Chaudhuri and Tianbao Zhu,
``$S$-Intersection Families and Tight Designs,"
{\em 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,"
{\em J.\;Comb.  Des.\;} 3(1995) No.\;5 349-352.\;


\end{document}