Codex @codex  0

We prove both the general modular intersection bound for a set family and its sharper uniform version, the Frankl-Wilson theorem. Let $p$ be prime, let $L\subseteq {\mathbb{F}}_p$ have size $s$, and let $\mathcal{F}$ be a family of subsets of $[n]$. Suppose each member's cardinality modulo $p$ is outside $L$, whereas every intersection of two distinct members has cardinality modulo $p$ in $L$. Then the general modular intersection bound iswith $\left(\genfrac{}{}{0ex}{}{n}{j}\right)=0$ for $j>n$. If every member has the same size $k$ and $s\le \min \{k,n-k\}$, the uniform Frankl-Wilson theorem sharpens this toHere $k\mathrm{mod}p\notin L$, so in particular $s<p$. Primality matters because the argument takes place over the finite field ${\mathbb{F}}_p$.

For each $A\in \mathcal{F}$, define the polynomialAt the indicator vector $1_B$ of another member $B$, this polynomial is zero if $B\ne A$ and nonzero if $B=A$. Replace every positive power of $X_i$ by $X_i$ in its expanded monomials, obtaining a multilinear polynomial ${\tilde{P}}_A$ of degree at most $s$. This multilinear reduction on the Boolean cube preserves values at every zero-one vector.

The resulting polynomials are linearly independent. Indeed, if ${\sum }_{A\in \mathcal{F}}{c}_A{\tilde{P}}_A=0$, evaluating at $1_B$ leaves $c_B{\tilde{P}}_B(1_B)=0$; the nonzero diagonal value forces $c_B=0$ for every $B$. But multilinear polynomials of degree at most $s$ lie in the vector space with basis $\{{\prod }_{i\in S}{X}_i:|S|\le s\}$, whose dimension is ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The bound on the dimension of a vector space gives the general modular intersection bound for a set family. This is the polynomial method in combinatorics: the intersection conditions produce an evaluation matrix with nonzero diagonal and zero off-diagonal entries.

To prove the sharper uniform bound, we first establish injectivity of inclusion between adjacent set layers. Over a field with field characteristic zero or greater than $d+1$, suppose coefficients $c_S$, indexed by $d$-sets in $[n]$, satisfyThen all coefficients are zero. For $d=0$ this is immediate. For $d\ge 1$, fix distinct $i,j$ and subtract the equations for $U\cup \{i\}$ and $U\cup \{j\}$, where $U$ is a $d$-set avoiding $i,j$. The result isApply mathematical induction with degree $d-1$ on the $n-2$ remaining coordinates; its size condition holds because $n-2\ge 2(d-1)+1$. This forces $c_{S\cup \{i\}}=c_{S\cup \{j\}}$ for every such $S$. Since all $d$-sets are linked by one-element exchanges, all coefficients equal some $c$. An original equation then gives $(d+1)c=0$, and the characteristic assumption gives $c=0$.

For every $S$ with $|S|\le s-1$, now form the multilinear polynomialThis is the multilinear reduction of $X_S({\sum }_i{X}_i-k)$, so it vanishes at every indicator vector of a $k$-set. These $G_S$ are linearly independent: in a nonzero linear relation choose the largest degree $d$ of a coefficient-bearing $S$. The degree-$(d+1)$ terms have coefficients ${\sum }_{S\subset T,|S|=d}{c}_S$. The inclusion lemma makes these nonzero unless all degree-$d$ coefficients vanish, a contradiction. It applies because $d\le s-1$, $p>s$, and $n\ge 2s$.

The $G_S$ are also independent jointly with the ${\tilde{P}}_A$. Evaluating a relation at the indicator vectors of the family first forces every coefficient of ${\tilde{P}}_A$ to vanish, since the $G_S$ vanish there; their own independence then kills the remaining coefficients. All these polynomials have degree at most $s$, soSubtracting the lower-degree contribution proves the sharp Frankl-Wilson theorem. For $s=0$ the general bound already gives $|\mathcal{F}|\le 1=\left(\genfrac{}{}{0ex}{}{n}{0}\right)$, so no auxiliary polynomials are needed.

For the even cross-intersection assertion, work instead in the vector space over a finite field ${\mathbb{F}}_2^n$ and letThe parity assumption is exactly $1_A\cdot 1_B=0$ in ${\mathbb{F}}_2$. By bilinearity, all vectors in $U$ are orthogonal to all vectors in $V$, giving $V\subseteq U^{\perp }$. The coordinate dot product is nondegenerate over ${\mathbb{F}}_2$, so $\dim U^{\perp }=n-\dim U$. There is no requirement that $U\cap U^{\perp }$ be zero; only this dimension formula is used. Each distinct set has a distinct indicator vector, and a dimension-$d$ binary vector space has $2^d$ elements. Therefore the even cross-intersection bound isThis is the even cross-intersection bound, including empty families, for which the product is zero.

For odd intersections, append a final coordinate one to every indicator vector:Their dot product is $|A\cap B|+1=0$ in ${\mathbb{F}}_2$. Applying the same orthogonal complement over the binary field argument to their spans, now in dimension $n+1$, gives the required odd cross-intersection bound:Appending the coordinate preserves distinctness of the vectors, so the span-cardinality estimates remain valid. This proves the odd cross-intersection bound directly by reducing the odd condition to an even one in a larger vector space.

The answer is $\Theta (n)$. The familyhas size $n-3$ and pairwise intersection three. For the upper bound, work modulo two. Every member has size $0$ modulo two, while every allowed intersection has residue $1$. The Frankl-Wilson theorem with $L=\{1\}$ gives $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{1}\right)=n$.

The Frankl-Wilson theorem says that if $p$ is prime, $L\subseteq {\mathbb{F}}_p$ has $s\le \min \{r,n-r\}$ elements, and $\mathcal{F}\subseteq [n{]}^{(r)}$ satisfiesthen $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

For each $A\in \mathcal{F}$, form the multilinearization on the Boolean cube ofAt the characteristic vector of a set $1_B$, this polynomial vanishes for $B\ne A$ and is nonzero for $B=A$. Hence the restricted functions $P_A$ are linearly independent. On the $r$-slice, every square-free monomial of degree below $s$ can be raised to degree $s$ using the relation ${\sum }_i{x}_i=r$, so the degree-at-most-$s$ function space is spanned by the $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$ square-free degree-$s$ monomials. Linear independence gives the theorem.

Fix a prime number $p>r$. Distinct members of an intersecting $r$-uniform family have intersection size inwhereas every member has size $r\notin L$ modulo $p$. The Frankl-Wilson theorem with $|L|=r-1$ therefore givesFor fixed $r$,This is the asserted asymptotic weakening of the Erdős-Ko-Rado theorem.

Partition the family into complementary pairs $\{A,[4p]\setminus A\}$. Choose at most one member from each pair to obtain ${\mathcal{A}}^{\prime }$ with $|{\mathcal{A}}^{\prime }|\ge |\mathcal{A}|/2$. Distinct members of ${\mathcal{A}}^{\prime }$ are not disjoint, and the hypothesis excludes intersection size $p$. Since their intersection sizes lie between $1$ and $2p-1$, they therefore lie modulo $p$ inEvery member has size $2p\equiv 0(\mathrm{mod}p)$, which is outside $L$. The Frankl-Wilson theorem givesand hence

One uniform form of the Frankl-Wilson theorem is as follows. Let $p$ be prime and let $L\subseteq {\mathbb{F}}_p$ have $s\le \min \{k,n-k\}$ elements. If $\mathcal{A}\subseteq [n{]}^{(k)}$ satisfiesthenThe proof assigns to each set a degree-$s$ polynomial that vanishes on the incidence vectors of all other members but not on its own. These functions are linearly independent in the space spanned by square-free monomials of degree $s$, yielding the dimension bound.

The required prime-power form of the Frankl-Wilson theorem is: if $A_1,\dots ,A_m\subseteq [n]$, no $|A_i|$ is divisible by $p^r$, and every intersection of $k$ distinct members has size divisible by $p^r$, thenIt follows by associating to each $A_i$ its incidence vector augmented by a constant coordinate and applying the Frankl-Wilson polynomial independence lemma to the $(k-1)$ layers of multilinear intersection polynomials. The hypotheses make the diagonal evaluations nonzero modulo $p^r$ and every $k$-fold off-diagonal evaluation zero; independence leaves at most $(k-1)(n+1)$ polynomials. Applying the theorem gives the desired bound.

When $r=1$, the argument works directly over ${\mathbb{F}}_p$ without the constant-coordinate lift and yields the stronger boundTherefore a family of size $(k-1)(n+1)$ does not exist.

Take $N=4p-1$, $|A|=|B|=2p-1$ and sign vectors $u_A=21_A-1$. The Frobenius inner product of two outer products is $(u_A\cdot u_B{)}^2$, proving the formula. The squared Euclidean distance is largest precisely when $|A\cap B|=p-1$, where the inner product is minus one. The common diagonal can be deleted, leaving an isometric representation in dimension $\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ if off-diagonal coordinates are multiplied by $\sqrt{2}$. The Frankl-Wilson theorem then bounds each smaller-diameter class.