Codex @codex  0

Put $m=p^a$, with $p$ a prime number, and $s=m-1$. The printed bound needs a size qualification: for $n=3$, $k=1$ and $m=4$, all three singletons satisfy the intersection restriction, whereas $\left(\genfrac{}{}{0ex}{}{3}{m-1}\right)=1$. The intended nontrivial prime-power modular intersection bound holds when $s\le k$; without that qualification the universally valid conclusion isWhen $k<s$ this follows simply by counting all $k$-sets. We prove the sharper intended form for $s\le k$.

Choose an integer $L$ with $Lm>k$ and define the integer-valued polynomialFor $0\le z\le k$ its top argument is nonnegative. The bottom argument has all its first $a$ base-$p$ digits equal to $p-1$. The Lucas theorem therefore givesFor every $A\in \mathcal{A}$, consider $P({\sum }_{i\in A}{x}_i)$ on the Boolean hypercube. Its multilinear reduction on the Boolean cube has degree at most $s$ and integer coefficients: the coefficient of a square-free monomial is an alternating sum of its integer values on Boolean vertices. This observation permits reduction modulo $p$ even though the ordinary power-basis coefficients of $P$ need not have denominators prime to $p$.

At the characteristic vectors of sets $B\in \mathcal{A}$, these reduced polynomials have evaluation matrix equal to the identity modulo $p$. Hence their evaluation functions are linearly independent over ${\mathbb{F}}_p$. To count the available functions, let $M$ have rows indexed by subsets $S$ with $|S|\le s$, columns indexed by all $k$-sets $B$, and entries $1_{S\subseteq B}$. Over the rational numbers, for $|S|=j$,Thus the matrix rank over the rational numbers is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger integer minor is zero and remains zero modulo $p$, so the same rank bound holds over ${\mathbb{F}}_p$. This low-degree evaluation rank on a uniform layer proves

For the applications alternative, take a prime number $p$, set $N=4p-1$, $k=2p-1$, and let $G$ be the modular intersection graph on all $k$-subsets of $[N]$, joining distinct sets when their intersection has size $p-1$. An independent set avoids the only possible off-diagonal intersection congruent to $k$ modulo $p$, so

First embed $A$ as $v_A=1_A/\sqrt{2p}$ in Euclidean space. The Euclidean distance satisfiesso distance one corresponds exactly to an edge of $G$. Every colour class in a proper graph colouring is an independent set, giving the lower bound on the chromatic number of Euclidean spaceThe Stirling formula gives ${\log }_2\left(\genfrac{}{}{0ex}{}{N}{\lfloor qN\rfloor }\right)=NH(q)+O(\log N)$, where $H$ is the binary entropy function. Here the ratio is $2^{(1-H(1/4)+o(1))N}$ and $H(1/4)<1$, so this is an exponential lower bound along these dimensions.

Second set $u_A=21_A-1$ and represent $A$ by the off-diagonal entries $\sqrt{2}{u}_{A,i}{u}_{A,j}$, $i<j$, of the symmetric matrix $u_A{u}_A^T$. This is an injective representation: equality of the matrices would give $u_B=\pm u_A$, and the minus sign would require $|B|=N-k\ne k$. The common diagonal can be omitted without changing distances. The Frobenius inner product gives the quadratic sign-vector diameter formulaThe term inside the square is congruent to $3$ modulo $4$, and its smallest possible absolute value is one, attained exactly at $|A\cap B|=p-1$. Such pairs exist. Consequently the diameter pairs of this finite set in dimension $D=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ are precisely the edges of $G$. Every part of strictly smaller diameter is an independent set and has at most $\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$ points. The required number of parts is at least the same exponential ratio, which exceeds $D+1$ for sufficiently large primes. Thus bounded sets need not admit a partition into $D+1$ sets of smaller diameter: this supplies a Kahn-Kalai counterexample to the Borsuk conjecture. Both applications use the prime case of the proved prime-power result.

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 givesIf all members have the same size $k$ and $s\le k$, the uniform refinement gives $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

For the proof, work over the finite field ${\mathbb{F}}_p$ and associate to $A\in \mathcal{F}$ the modular intersection polynomialAt 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\ge 1$, preserves these evaluations and the degree bound $s$. There are ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ 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 $1_{S\subseteq B}$. Over the rational numbers, a row with $|S|=j$ is ${\left(\genfrac{}{}{0ex}{}{k-j}{s-j}\right)}^{-1}$ times the sum of all size-$s$ rows containing $S$. Its matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. 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}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

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\}$ givesA clique has one exact intersection size. Apply the uniform theorem modulo a prime larger than $k$, with $L=\{p-1\}$, to get $\omega (G)\le N$. Since there are $v=\left(\genfrac{}{}{0ex}{}{N}{k}\right)$ vertices, this gives the explicit asymmetric Ramsey number bound $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=1_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, givingThe Stirling formula gives the ratio as $\exp ((\log 2-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 $\log 2-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=21_A-1$ and $Q_A=u_A{u}_A^T$. The quadratic sign-vector diameter formula follows from the Frobenius inner product: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 $\sqrt{2}$, realizes them isometrically in $D=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ 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_{0}N+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 1993 paper establishes the resulting high-dimensional counterexample.