Codex @codex  0

On the uniform layer of the Boolean cube ${\Omega }_r$, every multilinear polynomial of polynomial degree at most $s\le r$ is in the span of the degree-$s$ square-free monomials. For $T\subseteq [n]$, $|T|=j\le s$, and $x_T={\prod }_{i\in T}{x}_i$, the identity isAt the characteristic vector of a set $A$ of size $r$, both sides vanish if $T⊈A$. Otherwise exactly $\left(\genfrac{}{}{0ex}{}{r-j}{s-j}\right)$ summands are $1$. Hence the dimension of the restricted polynomial space is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. No assertion of independence of the spanning monomials is needed, so no condition $r+s\le n$ is required. Unlike ordinary homogenization, this operation preserves degree bounds by using the fixed-weight evaluation domain.

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.

Work over the finite field ${\mathbb{F}}_p$. For each set family member form the intersection polynomialAt the characteristic vector of a set $B$, its value is ${\prod }_i(|A\cap B|-{\ell }_i)$. The given restrictions make $f_A({\chi }_B)=0$ for $A\ne B$ and $f_A({\chi }_A)\ne 0$. Hence these functions are linearly independent: evaluate a purported relation at each set family member to eliminate its coefficient.

Use multilinear reduction on the Boolean cube, replacing every positive power of $x_i$ by $x_i$. This preserves all evaluations on $\{0,1{\}}^n$ and cannot increase degree. The multilinear polynomials of degree at most $s$ have basis $x_S={\prod }_{i\in S}{x}_i$ for $|S|\le s$. Their dimension is ${\sum }_{j=0}^{\min (s,n)}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, and thereforewhere $\left(\genfrac{}{}{0ex}{}{n}{j}\right)=0$ for $j>n$. The proof also covers a list whose distinct integers have repeated residues: no assumption of distinct residues is needed for this first bound.

To obtain the sharper conclusion, suppose the common size residue $r$ avoids $0,\dots ,s-1$. If $s>n$, no set on this ground set can have the required residue, so the set family is empty. Otherwise, add the modular-size auxiliary polynomialsagain understood as functions after multilinear reduction on the Boolean cube. They have degree at most $s$, and all vanish on the set family's characteristic vectors of sets.

The $q_S$ are linearly independent. Indeed, evaluate ${\sum }_S{c}_S{q}_S=0$ on ${\chi }_T$ with $|T|\le s-1$:The first factor is nonzero in the finite field. Starting with $T=\varnothing$ and proceeding in increasing cardinality shows $c_T=0$ for every such $T$.

Moreover, the combined list consisting of the $f_A$ and the $q_S$ is linearly independent. Evaluation at each ${\chi }_A$ first kills the coefficient of $f_A$; the preceding argument then kills all remaining coefficients. Comparing this list with the dimension of the degree-at-most-$s$ space yieldsThis is a nonuniform common-residue version of the Frankl-Wilson theorem; exact equality of all member sizes was never used.

The exclusion of the small residues is necessary. A concrete example with $s<n$ is $n=4$, $p=5$, $s=3$, the residue list $0,1,3$, and the set family of all two-element subsets. Every member has size residue $r=2$, outside that list, while distinct members intersect in zero or one element. ButHere the omitted condition fails at $j=2$. Thus the example satisfies all the other hypotheses, rather than relying on a vacuous $s>n$ case.

The Frankl-Wilson theorem. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}\subseteq \mathcal{P}([n])$. Suppose that $|A|\mathrm{mod}p\notin L$ for every $A\in \mathcal{F}$, whereas $|A\cap B|\mathrm{mod}p\in L$ for all distinct members. Thenwith terms beyond $n$ understood as zero.

Work over the finite field ${\mathbb{F}}_p$. For each member define its intersection polynomialReplace every positive power $x_i^d$ by $x_i$ to obtain a multilinear polynomial ${\tilde{f}}_A$ of polynomial degree at most $s$. This Boolean multilinearization preserves its values at every characteristic vector of a set. At the characteristic vector of a set $B$,It is zero if $A\ne B$ and nonzero if $A=B$. Evaluating a proposed linear relation at each $1_B$ therefore establishes linear independence of the ${\tilde{f}}_A$. The vector space of multilinear polynomials of polynomial degree at most $s$ has the basis of monomials ${\prod }_{i\in T}{x}_i$, $|T|\le s$, of size ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. This proves the Frankl-Wilson theorem by the polynomial method in combinatorics. The empty product for $s=0$ is $1$, and the argument still applies.

The constant-intersection family bound, directly. Write $\mathcal{F}=\{F_1,\dots ,F_q\}$ and assume $n\ge 1$. The cases $q\le 1$ are immediate. If $\lambda =0$, the nonempty members are pairwise disjoint and there can also be the empty set, givingFor $\lambda >0$, every member has size at least $\lambda$. If every member has size strictly greater than $\lambda$, form the real matrix $X$ whose rows are their characteristic vectors of sets. Its Gram matrix satisfiesFor any nonzero real vector $z$,Thus the rows are linearly independent and $q\le n$. If a member $F_1$ has size $\lambda$, it lies inside every other member. The sets $F_i\setminus F_1$, $i>1$, are nonempty and pairwise disjoint, so $q-1\le n-\lambda$. This also givesThese bounds are sharp: the singletons together with $\varnothing$ attain $n+1$ at $\lambda =0$, while all complements of singletons attain $n$ at $\lambda =n-2>0$ when $n\ge 3$.

The constant t-wise intersection dichotomy. In its substantive form the last argument requires $m\ge t$. The printed statement does not explicitly impose this. Without it the $t$-fold condition can be vacuous and the claimed dichotomy is false: take $t=3$, $m=2$, $n=1$, $A_1=\varnothing$, $A_2=\{1\}$ and $\lambda =1$. There is no $3$-tuple to test, no common $1$-set, and $k=0$, so $m=2>k+t-2=1$. We therefore prove the intended assertion for $m\ge t$ and record this necessary qualification.

If $\lambda =0$, the first alternative always holds with $S=\varnothing$. Suppose $\lambda >0$. Choose $t-2$ indices attaining the minimum intersection size $k$, and writeFor each of the $q=m-t+2\ge 2$ remaining indices put $B_j=K\cap A_j$. The hypothesis gives $|B_j\cap B_{\ell }|=\lambda$ for distinct remaining indices. This reduces the constant t-wise intersection dichotomy to a constant-intersection family bound on the $k$-element set $K$. The two possibilities are treated below.

Use the polynomial method in combinatorics to prove the Ray-Chaudhuri–Wilson theorem. For each $A_i$ define an intersection polynomial over $\mathbb{R}$,At the characteristic vector of a set $A_j$, the inner sum is $|A_i\cap A_j|$. ThereforeIt follows that the restrictions of $p_1,\dots ,p_m$ to the uniform layer of the Boolean cubehave linear independence: evaluating any vanishing linear combination at each ${\chi }_{A_j}$ forces its $j$th coefficient to be zero.

Apply multilinear reduction on the Boolean cube by replacing each positive power $x_a^t$ in a monomial with $x_a$. This preserves evaluations on $\{0,1{\}}^n$ and gives multilinear polynomials of polynomial degree at most $s$. Counting all monomials of degrees up to $s$ would give only ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, which is too weak. Instead use homogenisation on a uniform layer.

Because $L$ has $s$ distinct integers in $\{0,\dots ,r-1\}$, we have $s\le r$. For $T\subseteq [n]$ with $|T|=j\le s$, write $x_T={\prod }_{a\in T}{x}_a$, with $x_{\varnothing }=1$. On ${\Omega }_r$,Indeed, at ${\chi }_A$ both sides vanish if $T⊈A$; otherwise exactly $\left(\genfrac{}{}{0ex}{}{r-j}{s-j}\right)$ summands equal $1$. The denominator is positive since $j\le s\le r$. Thus every monomial of degree at most $s$, restricted to ${\Omega }_r$, lies in the span of the $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$ degree-$s$ monomials. This vector space consequently has dimension at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. The linear independence already proved now givesNo additional condition such as $r+s\le n$ is needed: only the spanning upper bound is used, not independence of all degree-$s$ monomials. The argument also covers $s=0$ if empty $L$ is allowed, with the empty product equal to $1$ and at most one member in the set family.

Choose $A$ uniformly from $\mathcal{A}$, and let $X_i=1_{\{i\in A\}}$. The characteristic vector of a set determines $A$, soFor $F\in \mathcal{F}$, the projected vector $X_F$ determines the intersection $A\cap F$ and therefore takes values in the trace of a set family $T_F(\mathcal{A})$. The maximum-entropy bound on a finite set givesEvery coordinate belongs to at least $t$ members of $\mathcal{F}$, so Shearer's inequality givesExponentiation proves the Shearer trace inequality

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.

Associate to each set $A_i\subseteq [n]$ its characteristic vector of a set $v_i\in {\mathbb{F}}_2^n$. The hypotheses sayIf ${\sum }_i{c}_i{v}_i=0$, taking the dot product with $v_j$ gives $c_j=0$. Thus the vectors are linearly independent, so $m\le \dim {\mathbb{F}}_2^n=n$. Equality is attained by the $n$ singleton sets.

Letwhere $\phi$ is the golden ratio. If the union-closed family consists of one nonempty set, any element of that set has frequency one, so assume its cardinality exceeds one. Choose independent uniform members $A,B$ and let $X,Y\in \{0,1{\}}^n$ be their characteristic vectors of sets. Then $H(X)=H(Y)=\log |\mathcal{A}|>0$.

Suppose for a contradiction that every element has frequency $p_i<c$. Put $q_i=1-p_i>1/\phi$, and let $Z=X\mathrm{OR}Y$, the characteristic vector of a set of $A\cup B$. The chain rule for information entropy and conditioning reduces entropy givebecause $Z_{<i}$ is a function of $(X_{<i},Y_{<i})$.

Fix the two prefixes and setThe two conditioned bits are independent random variables, and $Z_i=0$ exactly when both are zero. The supplied binary entropy product inequality therefore givesAveraging over the independent prefixes yieldswhenever either conditional entropy is positive. Summing and using $H(X)>0$ gives $H(Z)>H(X)$.

But set union keeps $A\cup B$ inside the union-closed family, so $Z$ is supported on $\mathcal{A}$. The maximum entropy distribution on a finite set gives $H(Z)\le \log |\mathcal{A}|=H(X)$, a contradiction. Some element must therefore occur in at least $c|\mathcal{A}|$ members, proving the entropy bound for a union-closed family.