= Solution
The <Frankl-Wilson theorem> is a striking example of the <polynomial method in combinatorics>: an intersection restriction creates a family of <linearly independent> low-degree <polynomials>, whose dimension bounds the set family. Let $p$ be a <prime number>, let $L\subseteq\mathbb F_p$ have $s$ elements, and let $\mathcal F$ be a <set family> such that member sizes modulo $p$ avoid $L$ while every distinct pair has intersection size in $L$ modulo $p$. Its general modular form gives
$$
|\mathcal F|\leq\sum_{j=0}^s\binom nj.
$$
If all members have the same size $k$ and $s\leq k$, the uniform refinement gives \b[$|\mathcal F|\leq\binom ns$].
For the proof, work over the <finite field> $\mathbb F_p$ and associate to $A\in\mathcal F$ the <modular intersection polynomial>
$$
P_A(x)=\prod_{\lambda\in L}\left(\sum_{i\in A}x_i-\lambda\right).
$$
At the <characteristic vector of a set> $B$, this equals zero for $B\ne A$ and is nonzero for $B=A$. A linear relation among the evaluation functions therefore has every coefficient zero. The <multilinear reduction on the Boolean cube>, replacing $x_i^a$ by $x_i$ for $a\geq1$, preserves these evaluations and the degree bound $s$. There are $\sum_{j=0}^s\binom nj$ possible square-free <monomials>, proving the general form.
For uniform members, the <low-degree evaluation rank on a uniform layer> supplies the sharper dimension bound. To verify this without division modulo $p$, form the integer incidence <matrix> with rows indexed by subsets $S$ of size at most $s$, columns indexed by $k$-subsets $B$, and entries $\mathbf1_{S\subseteq B}$. Over the <rational numbers>, a row with $|S|=j$ is $\binom{k-j}{s-j}^{-1}$ times the sum of all size-$s$ rows containing $S$. Its <matrix rank> is at most $\binom ns$. Every larger integer minor is consequently zero and remains zero modulo $p$, giving the same bound over $\mathbb F_p$. The nonzero diagonal evaluation <matrix> of the $P_A$ then forces $|\mathcal F|\leq\binom ns$.
The theorem, proved by Frankl and Wilson in 1981, extends the theme of the <Ray-Chaudhuri–Wilson theorem> from ordinary intersection sizes to residues. Modular restrictions can be weaker than exact intersection restrictions yet still force unexpectedly small families. Here are three consequences from one explicit <modular intersection graph>.
Take $N=4p-1$, $k=2p-1$, and let the <vertices> be all $k$-subsets of $[N]$, with an <edge> exactly when the intersection has size $p-1$. An <independent set> avoids the only possible off-diagonal intersection congruent to $k$ modulo $p$, so applying the <Frankl-Wilson theorem> with $L=\mathbb F_p\setminus\{p-1\}$ gives
$$
\alpha(G)\leq B:=\binom N{p-1}.
$$
A <clique> has one exact intersection size. Apply the uniform theorem modulo a prime larger than $k$, with $L=\{p-1\}$, to get $\omega(G)\leq N$. Since there are $v=\binom Nk$ <vertices>, this gives the explicit asymmetric <Ramsey number> bound \b[$R(N+1,B+1)>v$]. It illustrates how algebraic constructions produce graphs with simultaneously restricted <cliques> and <independent sets>.
For a geometric application, map each <vertex> to $x_A=\mathbf1_A/\sqrt{2p}$ in $\mathbb R^N$. Then $|x_A-x_B|^2=(k-|A\cap B|)/p$, so <edges> have unit <Euclidean distance>. Every proper colouring of Euclidean space therefore colours this finite <graph>, giving
$$
\chi(\mathbb R^N)\geq\chi(G)\geq\frac{\binom N{2p-1}}{\binom N{p-1}}.
$$
The <Stirling formula> gives the ratio as $\exp((\log2-H(1/4)+o(1))N)$, where $H(a)=-a\log a-(1-a)\log(1-a)$ is the <binary entropy function> in natural-log units. The positive constant $\log2-H(1/4)$ proves an exponential <chromatic number of Euclidean space> lower bound along these dimensions.
Finally, a quadratic embedding converts this same forbidden intersection into a forbidden <diameter> pair. Set $u_A=2\mathbf1_A-\mathbf1$ and $Q_A=u_Au_A^T$. The <quadratic sign-vector diameter formula> follows from the <Frobenius inner product>:
$$
\|Q_A-Q_B\|_F^2=2\bigl(N^2-(u_A\cdot u_B)^2\bigr),
\qquad
u_A\cdot u_B=4|A\cap B|-4p+3.
$$
For distinct members the smallest possible absolute inner product is one, attained exactly when the intersection is $p-1$. Thus maximum-distance pairs are exactly <edges> of $G$. The matrices have common diagonal; using their off-diagonal coordinates, multiplied by $\sqrt2$, realizes them isometrically in $D=\binom N2$ dimensions. They are distinct because equal outer products require $u_A=\pm u_B$, and complements have size $2p$, not $k$.
Any subset of smaller <diameter> contains at most $B$ points, so a partition into smaller-<diameter> pieces needs at least $v/B=\exp(c_0N+o(N))$ pieces. For sufficiently large primes this exceeds $D+1$, disproving the <Borsuk conjecture>. This is the mechanism behind the <Kahn-Kalai counterexample to the Borsuk conjecture>: the number of required pieces grows exponentially in the original set-system parameter while dimension grows quadratically. Their https://arxiv.org/abs/math/9307229[1993 paper] establishes the resulting high-dimensional counterexample.
Back to article page
