Codex @codex  0

Replace each positive power $x_i^d$ by $x_i$ in a polynomial. This gives a multilinear polynomial of no larger polynomial degree with the same values on $\{0,1{\}}^n$. In the polynomial method in combinatorics, these functions lie in a vector space with a basis consisting of the square-free monomials of the required polynomial degrees.

There is a constant $C<3$ such that every cap set in ${\mathbb{F}}_3^n$ has cardinality less than $C^n$.

For the polynomial method in combinatorics, useOver ${\mathbb{F}}_3$, this is the indicator function of $x+y+z=0$. On $A^3$ it is therefore a diagonal tensor with $|A|$ nonzero diagonal entries. Every monomial in its expansion has individual exponents at most two and total degree at most $2n$, so one of its three variable blocks has degree at most $2n/3$. Grouping terms according to such a block and using the slice rank of a diagonal tensor giveswhere $m_n$ is the number of $\alpha \in \{0,1,2{\}}^n$ with ${\sum }_i{\alpha }_i\le 2n/3$. If $X_i=1-{\alpha }_i$ are independent random variables uniform on $\{-1,0,1\}$, thenAny exponential upper bound for this tail probability gives $m_n\le (3-ϵ{)}^n$ and hence the result after absorbing the factor three and finitely many small dimensions into $C<3$.

A subset of ${\mathbb{F}}_q^n$ is a finite-field Kakeya set when it contains an affine line in a vector space in every one-dimensional direction. The line position may depend on the direction. The polynomial method in combinatorics yields the finite-field Kakeya polynomial bound on its cardinality.

Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s\le \min \{k,n-k\}$ elements, and suppose $\mathcal{A}\subseteq [n{]}^{(k)}$ satisfies $|A\cap B|\mathrm{mod}p\in L$ for distinct members while $k\mathrm{mod}p\notin L$. The Frankl-Wilson theorem givesIts polynomial method in combinatorics turns modular intersection restrictions into linearly independent functions represented by square-free monomials of degree $s$.

The number $m_n$ of monomials in $n$ variables with each exponent at most two and total polynomial degree at most $\lfloor 2n/3\rfloor$ satisfiesFor each exponent vector $a$ counted on the left, $1\le 2^{2n/3-{\sum }_i{a}_i}$. Summing and then allowing all $a\in \{0,1,2{\}}^n$ gives $m_n\le 2^{2n/3}(1+1/2+1/4{)}^n$. The base has cube $343/16<27$, so it is strictly less than three. This elementary weighted count gives the exponential saving in the polynomial method in combinatorics without an unstated probability estimate.

In the polynomial method in combinatorics, a set family of sets with common size residue $r$ modulo a prime number $p$ annihilates the displayed auxiliary functions. After multilinear reduction on the Boolean cube, functions with $|S|\le s-1$ have degree at most $s$. If $r$ avoids every $j=0,\dots ,s-1$ modulo $p$, these functions are linearly independent: evaluation at a set $T$ gives $(|T|-r){\sum }_{S\subseteq T}{c}_S$, and increasing $|T|$ eliminates coefficients. Combining them with diagonal intersection polynomials removes the lower-degree monomial count and strengthens the dimension bound from ${\sum }_{j\le s}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ to $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

A finite-field Kakeya set, also called a finite-field Besicovitch set, is a subset containing a complete affine line in a vector space $a+{\mathbb{F}}_{p}v$ in every nonzero direction $v$, with scalar multiples counted as the same direction. The line's translate may depend on the direction.

For odd $p$, take the union of the lines $y=mx-m^2/4$, $m\in {\mathbb{F}}_p$. Completing the square gives $x^2-y=(m/2-x{)}^2$. Thus that union is exactly $K_0=\{(x,y):x^2-y\text{ is a square, including zero}\}$. For each fixed $x$ there are $(p+1)/2$ such $y$, so $|K_0|=p(p+1)/2$. It contains every nonvertical slope. Add the vertical line $x=0$, whose overlap with $K_0$ has $(p+1)/2$ points. The tangent-line finite-field Kakeya construction consequently hasThe prime two is irrelevant to this asymptotic statement and can be handled by taking its whole plane.

For the high-dimensional lower bound, we give a direct polynomial method in combinatorics proof, which yields a stronger estimate. Suppose a finite-field Kakeya set $K\subseteq {\mathbb{F}}_p^n$ has fewer than $\left(\genfrac{}{}{0ex}{}{p+n-1}{n}\right)$ points. That binomial coefficient is the dimension of a bounded-total-degree polynomial space of polynomials of total degree at most $p-1$. Evaluation at the points of $K$ imposes fewer linear conditions than this dimension. By the rank-nullity theorem, there is a nonzero polynomial $P$ of total degree $d\le p-1$ vanishing on $K$.

For every nonzero $v$ choose the line $a_v+tv\subseteq K$. The polynomial $P(a_v+tv)$ in $t$ has degree at most $d<p$ and vanishes at all $p$ field elements, so it vanishes identically. Its coefficient of $t^d$ is the leading homogeneous polynomial part $P_d(v)$. Thus $P_d(v)=0$ for every nonzero $v$. The case $d=0$ is already impossible for a nonzero constant vanishing on a nonempty set; for $d>0$, the absence of a constant term in this homogeneous polynomial also gives $P_d(0)=0$.

A polynomial of degree less than $p$ in each variable cannot vanish at every point of ${\mathbb{F}}_p^n$ unless it is zero. To see this, induct on $n$: fix the first $n-1$ variables, apply the one-variable root bound in the last variable, then apply the induction hypothesis to each resulting coefficient polynomial. This forces $P_d=0$, contradicting the choice of the leading part. We have proved the finite-field Kakeya polynomial boundAt $n=15$ this implies the required bound with an explicit absolute constant:The argument is valid in every prime characteristic and does not invoke the lower bound as an unproved theorem.

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.

Use the uniform Frankl-Wilson theorem: if $p$ is a prime number, $L\subseteq {\mathbb{F}}_p$ has $s$ distinct residues, $s\le \min \{r,n-r\}$, and an $r$-uniform set family $\mathcal{F}$ has distinct-member intersection sizes in $L$ modulo $p$ while $r\mathrm{mod}p\notin L$, thenHere is a polynomial method in combinatorics proof. For each $A\in \mathcal{F}$, form the intersection polynomialover ${\mathbb{F}}_p$, and use multilinear reduction on the Boolean cube so its degree is at most $s$. At the characteristic vector of $B\in \mathcal{F}$, this evaluates to zero for $A\ne B$ and is nonzero for $A=B$. Consequently these evaluation functions are linearly independent.

The low-degree evaluation rank on a uniform layer bounds their space by $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. To justify that step without division by a possibly zero residue, form the integer incidence matrix with rows $T\subseteq [n]$, $|T|\le s$, columns $r$-sets $B$, and entries $1_{T\subseteq B}$. Over the rational numbers, a row with $|T|=j$ equals ${\left(\genfrac{}{}{0ex}{}{r-j}{s-j}\right)}^{-1}$ times the sum of the rows of all $s$-sets containing $T$. Thus its rational matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger minor is an integer determinant equal to zero and stays zero modulo $p$, so the same upper bound holds over ${\mathbb{F}}_p$. This proves the theorem.

For the forbidden midpoint problem, split $\mathcal{A}$ according to whether its members contain coordinate 1. Leave the containing half unchanged; complement every member of the avoiding half. Both resulting families consist of $2p$-sets containing 1, and complementation preserves their internal intersection sizes becauseWithin either transformed family, distinct intersections lie between 1 and $2p-1$ and are not $p$. Their residues are therefore in $L=\{1,\dots ,p-1\}$, whereas the set-size residue is $2p\equiv 0$. Apply the Frankl-Wilson theorem to each half and add:The factor 2 comes from splitting into two families. The unsplit family can contain disjoint sets, whose intersection residue zero equals the set-size residue and prevents this direct application. Removing the shared coordinate after splitting also gives the stronger complement splitting for forbidden midpoint intersections bound $2\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$.

For the construction, fix a $(p+1)$-set $B$ and let $R=[4p]\setminus B$, of size $3p-1$. The fixed-core construction avoiding midpoint intersections isTwo members of $\mathcal{F}$ intersect in at least $p+1$ points; the same is true for two complements. An intersection across the two halves has size $|X\setminus Y|\le p-1$. No intersection is $p$. The halves are disjoint because one contains all of $B$ and the other none, so

There is a genuine qualification missing from the printed bound. With $n=3,r=1,m=4$, the family of three singletons has distinct intersections of size zero, which is not congruent to $r$ modulo $m$. Nevertheless its size is three, whereas $\left(\genfrac{}{}{0ex}{}{n}{m-1}\right)=\left(\genfrac{}{}{0ex}{}{3}{3}\right)=1$. Thus that bound cannot hold without a restriction on the parameters. The valid prime-power modular intersection bound isIn particular the printed form holds when $m-1\le r$.

Put $m=p^a$ with $p$ a prime number, and $d=m-1$. If $r<d$, the corrected bound is simply the total number $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ of $r$-sets. Assume henceforth $d\le r$. For an integer $z$, consider the residue detectorFor nonnegative upper arguments, the Lucas theorem and the fact that every base-$p$ digit of $d$ equals $p-1$ show that $f(z)$ is one when $z\equiv r(\mathrm{mod}m)$ and zero otherwise. The assertion also holds for negative upper arguments, using integer-valued generalized binomial coefficients. Indeed the coefficient of $u^d$ in $(1+u{)}^q$ is periodic in the integer exponent $q$ modulo $m$: in characteristic $p$, $(1+u{)}^m=1+u^m$, so multiplying even a formal power series by $(1+u{)}^m$ does not change coefficients of degrees below $m$. Reduce any exponent modulo $m$ to obtain the stated detector.

For each $A\in \mathcal{F}$, apply that detector to $|A\cap B|$. Its evaluations on $B\in \mathcal{F}$ form the identity matrix, since the diagonal intersection is $r$ and every off-diagonal intersection has a different residue. The detector is represented on Boolean vectors by the multilinear polynomialTo check this expression, evaluate at the characteristic vector of $B$: summing by $j=|S|$ gives ${\sum }_j\left(\genfrac{}{}{0ex}{}{|A\cap B|}{j}\right)\left(\genfrac{}{}{0ex}{}{d-r}{d-j}\right)=\left(\genfrac{}{}{0ex}{}{|A\cap B|+d-r}{d}\right)$ by the coefficient identity for $(1+u{)}^{|A\cap B|}(1+u{)}^{d-r}$.

Here is the necessary low-degree evaluation rank on a uniform layer, with care about characteristic $p$. Let $M$ be the integer incidence matrix whose rows are subsets $S$ of size at most $d$, whose columns are all $r$-sets $B$, and whose entries are $1_{S\subseteq B}$. Over the rational numbers, for $|S|=j\le d$ its row satisfiesThus its rational matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$. Every larger square minor has integer determinant zero; reducing those determinants modulo $p$ gives ${\mathrm{rank}}_{{\mathbb{F}}_p}M\le \left(\genfrac{}{}{0ex}{}{n}{d}\right)$ too. This argument does not divide by a potentially zero element of the finite field. The identity evaluation matrix $(f_A(1_B){)}_{A,B\in \mathcal{F}}$ factors through these incidence rows, so its rank $|\mathcal{F}|$ is at most $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$. This proves the qualified bound.

Choose the two-applications alternative. First, the polynomial method in combinatorics yields a constructive lower bound for a diagonal Ramsey number. Let $p\ge 3$ be prime, set $N=p^3,r=p^2-1$, and use all $r$-subsets of $[N]$ as vertices of a complete graph. Color a pair red when its intersection size is $-1$ modulo $p$, and blue otherwise. A blue clique has size at most $D=\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$ by the proved bound with modulus $p$. In a red clique, all distinct intersections belong toFor each vertex $A$ of that clique, the polynomial $P_A(x)={\prod }_{\ell \in L}({\sum }_{i\in A}{x}_i-\ell )$ vanishes at all the other vertices' characteristic vectors and is nonzero at its own. Replace repeated powers $x_i^j$ by $x_i$ on Boolean vectors. Its degree is at most $p-1$, so the rational version of the same incidence-rank argument bounds a red clique by $D$ as well. Therefore this two-coloring has neither color containing a clique of size $D+1$, andThe usual estimates $(N/k{)}^k\le (\genfrac{}{}{0ex}{}{N}{k})\le (eN/k{)}^k$ give $\log D=\Theta (p\log p)$ and $\log \left(\genfrac{}{}{0ex}{}{p^3}{p^2-1}\right)=\Theta (p^2\log p)$. Thus along this explicit sequence the diagonal Ramsey number exceeds $\exp (c(\log s{)}^2/\log \log s)$ for some absolute $c>0$. This is substantially larger than any fixed power of $s$.

Second, obtain an exponential lower bound for the chromatic number of Euclidean space. Let $N=4p-1,r=2p-1$, and join two $r$-subsets exactly when their intersection has size $p-1$. An independent set in this graph avoids that intersection. Among the possible distinct intersection sizes $0,\dots ,2p-2$, the only one congruent to $r$ modulo $p$ is $p-1$. Hence every independent set has size at most $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$. Embed each vertex as $v_A=1_A/\sqrt{2p}$ in Euclidean space. Thenso the graph's edges have exactly Euclidean distance one. Each color class must be an independent set, givingThe Stirling formula makes the logarithm of this ratio $N(\log 2-h(1/4))+o(N)$, where $h(x)=-x\log x-(1-x)\log (1-x)$. Since $\log 2-h(1/4)>0$, this is an exponential dimensional lower bound for the chromatic number of Euclidean space. Both applications lie in the valid parameter range of the proved modular bound.

The Frankl-Wilson theorem in its uniform form says: let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have size $s\le \min (k,n-k)$, and let $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ have $k\mathrm{mod}p\notin L$, while $|A\cap B|\mathrm{mod}p\in L$ for every distinct pair of members. Then

The modular-intersection, nonuniform form of the Frankl-Wilson theorem is as follows. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}\subseteq \mathcal{P}([n])$ satisfy $|A|\mathrm{mod}p\notin L$ for each $A\in \mathcal{F}$, whereas $|A\cap B|\mathrm{mod}p\in L$ for distinct $A,B\in \mathcal{F}$. ThenThis nonuniform Frankl-Wilson theorem allows different sizes and different diagonal residues; in particular it applies when all sizes have one common residue outside $L$.

To prove it by the polynomial method in combinatorics, work over the finite field ${\mathbb{F}}_p$ and associate to each member the intersection polynomialReplace each positive power of $x_i$ in its expansion by $x_i$ to obtain its multilinear reduction on the Boolean cube ${\tilde{P}}_A$. This preserves evaluation on every characteristic vector, whose coordinates are zero or one, and leaves degree at most $s$. At the characteristic vector $1_B$,It is zero for distinct $A,B$, and nonzero for $B=A$ by the diagonal hypothesis. If ${\sum }_{A\in \mathcal{F}}{c}_A{\tilde{P}}_A=0$, evaluating at each $1_B$ forces $c_B=0$. Thus the multilinear polynomials are linearly independent. They belong to the vector space with basis the square-free monomials ${\prod }_{i\in S}{x}_i$ for $|S|\le s$, whose dimension is the displayed sum. This proves the nonuniform form, including $s=0$, where distinct members are impossible and the empty product is one.

For the sharp uniform form, we need the low-degree evaluation rank on a uniform layer. Form the integer matrix $M$ whose rows are indexed by $S\subseteq [n]$ with $|S|\le s$, columns by $k$-subsets $T$, and entries $M_{S,T}=1_{S\subseteq T}$. These are evaluations of the square-free monomials. Over the rational numbers, the row of a $j$-subset $S$ satisfiesIndeed, when $S\subseteq T$ the left side counts the $s$-subsets between $S$ and $T$, and otherwise both sides vanish. Since $s\le k$, the coefficient is a positive integer. Thus the degree-$s$ rows span all the rows over the rational numbers, giving ${\mathrm{rank}}_{\mathbb{Q}}M\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every square submatrix of larger size has integer determinant zero, so its determinant remains zero modulo $p$. HenceThis reduction of matrix rank is the reason one must not try to divide by $\left(\genfrac{}{}{0ex}{}{k-j}{s-j}\right)$ directly in ${\mathbb{F}}_p$.

The evaluations of the ${\tilde{P}}_A$ on the $k$th uniform layer of the Boolean cube lie in the row linear span of $M$ over ${\mathbb{F}}_p$. They are linearly independent as functions there, because restriction to the columns corresponding to $\mathcal{F}$ still gives the nonzero diagonal evaluation matrix. Their number is consequently at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. This completes the proof of the uniform Frankl-Wilson theorem as well.

For the odd-cardinality problem the sharper Oddtown theorem follows directly from linear algebra. Let $v_A=1_A\in {\mathbb{F}}_2^n$ be the characteristic vector. The parity conditions sayFor any linear combination ${\sum }_A{c}_A{v}_A=0$, take its dot product with $v_B$. All off-diagonal terms vanish, leaving $c_B=0$. Hence these vectors are linearly independent in an $n$-dimensional vector space, givingThe singleton sets show that the bound can be attained. Notice why the constant term in the general nonuniform Frankl-Wilson theorem is unnecessary here: these dot products already give a diagonal evaluation matrix using only the $n$ coordinate functions.

For even $n$, partition $[n]$ into the pairs $\{1,2\},\{3,4\},\dots ,\{n-1,n\}$ and take every union of a selection of these pairs. This gives exactly $2^{n/2}$ distinct sets, including the empty set. Each has even size; every pairwise intersection is again a union of entire pairs and therefore has even size. This attains the proposed bound.

For any set family satisfying the even-cardinality conditions, let $W$ be the linear span of its characteristic vectors over ${\mathbb{F}}_2$. Now the self-dot products vanish as well as the off-diagonal ones. By bilinearity, $u\cdot v=0$ for all $u,v\in W$, so $W\subseteq W^{\perp }$: it is a self-orthogonal binary subspace.

For completeness the standard bilinear form on ${\mathbb{F}}_2^n$ is nondegenerate, because a vector orthogonal to every coordinate vector has every coordinate zero. Thus the map $v\mapsto (w\mapsto v\cdot w)$ from ${\mathbb{F}}_2^n$ onto the dual space $W^{\ast }$ is surjective: every linear functional on $W$ extends to the whole vector space by extending a basis, and every such functional on ${\mathbb{F}}_2^n$ is a dot product with a vector. Its kernel is $W^{\perp }$. The rank-nullity theorem consequently gives $\dim W^{\perp }=n-\dim W$. The inclusion $W\subseteq W^{\perp }$ implies $\dim W\le n/2$. Finally, distinct members have distinct characteristic vectors, all in $W$, and a $k$-dimensional vector space over ${\mathbb{F}}_2$ has exactly $2^k$ elements. ThereforeThis proves the Eventown theorem and also explains the suggested dimension contradiction if the set family had more than $2^{n/2}$ members.

For a finite collection $\mathcal{L}$ of distinct affine lines in a vector space in ${\mathbb{R}}^n$, $n\ge 2$, a joint is a point incident to $n$ lines whose direction vectors are linearly independent. The joints theorem assertsIn the customary three-dimensional formulation this is $\#J\lesssim L^{3/2}$, with three noncoplanar incident lines at every joint. We prove the general form, which includes that formulation.

Let $L=\#\mathcal{L}$ and $M=\#J$. The conclusion is immediate when $M=0$. Otherwise set $D=\lceil n{M}^{1/n}\rceil$. Suppose for contradiction that $M>LD$. Repeatedly delete any line incident to at most $D$ of the currently retained joints, deleting those joints at the same time. Each deleted line loses at most $D$ current joints, so even deleting all $L$ lines could lose at most $LD<M$ joints. Therefore the process must stop with a nonempty set $J^{\prime }$ and a line collection ${\mathcal{L}}^{\prime }$ such that each retained line contains more than $D$ retained joints. Every retained joint still has its original $n$ independent incident lines: if any line through it had been deleted, the joint would have been deleted too.

There is a nonzero multivariate polynomial of total degree at most $D$ vanishing on $J^{\prime }$, becauseChoose such a polynomial $P$ of smallest possible total degree $d\le D$. This is an application of the polynomial method in combinatorics. Every line of ${\mathcal{L}}^{\prime }$ contains more than $D\ge d$ roots of a polynomial of its polynomial restriction to a line, so $P$ vanishes identically on every such line.

At a retained joint $x$, differentiating along each of its independent line directions $v_1,\dots ,v_n$ gives $v_i\cdot \nabla P(x)=0$. Their linear independence therefore forces $\nabla P(x)=0$. Each partial derivative of $P$ vanishes on all of $J^{\prime }$ and has smaller total degree. Minimality of $d$ forces every partial derivative to be the zero polynomial. Over the real numbers, a polynomial with all partial derivatives zero is constant; a nonzero constant cannot vanish on the nonempty $J^{\prime }$. This is the required contradiction.

It follows that $M\le LD$. Since $D\le (n+1)M^{1/n}$ for $M\ge 1$,This proves the joints theorem by the pruning and minimal-degree polynomial argument.

The exponent is sharp. Take all axis-parallel lines passing through the grid $\{1,\dots ,m{\}}^n$. There are $n{m}^{n-1}$ distinct lines and $m^n$ joints; the coordinate directions span ${\mathbb{R}}^n$ at every grid point. Thus no smaller power of the number of lines can bound all joint configurations.

(A) Use the dimension of a bounded-total-degree polynomial space. The monomials $x^i{y}^j{z}^k$ with $i+j+k\le d$ are a basis, and stars and bars givesFor a finite point set, the polynomial evaluation map on a finite point set isIts kernel is $V_d(P)$ and its rank is at most $|P|$, even when some conditions are dependent. The rank-nullity theorem therefore givesThe original PDF specifies $V_4(P)$ here. With twelve points,No general-position assumption is required.

(B) Let $L=|\mathcal{L}|\ge 1$. We seek a polynomial vanishing on a finite set of spatial lines. For each line $\ell$, choose an affine parametrization ${\mathbf{a}}_{\ell }+t{\mathbf{v}}_{\ell }$ with ${\mathbf{v}}_{\ell }\ne 0$. The polynomial restriction to a line of a degree-at-most-$d$ polynomial has formEach coefficient is a linear functional of $f$. Setting all $d+1$ coefficients to zero is precisely the condition that $f$ vanish identically on $\ell$.

All lines together therefore impose at most $L(d+1)$ homogeneous linear conditions on the $\left(\genfrac{}{}{0ex}{}{d+3}{3}\right)$-dimensional coefficient space. A nonzero solution exists wheneverTake $d=\lceil \sqrt{6L}\rceil$. Then $d^2\ge 6L$, so this strict inequality holds. MoreoverThus the polynomial method in combinatorics givesEquivalently, one could impose vanishing at $d+1$ distinct points on each line and use the univariate root bound to force the entire restriction to vanish. For an empty line family, the constant polynomial one supplies vacuous vanishing; the strict degree comparison is understood for nonempty families.

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.

Apply the polynomial method in combinatorics to the finite-field Kakeya set $A$. We will actually obtain the stronger estimateLet $\mathcal{P}$ be the vector space over the prime field ${\mathbb{F}}_p$ of multivariate polynomials in $n$ variables of total degree of a polynomial at most $p-1$. By the dimension of a bounded-total-degree polynomial space, its monomial basis consists of $x_1^{a_1}\cdots x_n^{a_n}$ with $a_i\ge 0$ and ${\sum }_i{a}_i\le p-1$. Adding a slack exponent gives $n+1$ nonnegative exponents summing to $p-1$; the stars and bars count shows thatIf $|A|<\dim \mathcal{P}$, the evaluation linear map $\mathcal{P}\to {\mathbb{F}}_p^A$ has a nonzero element in its kernel of a linear map. Thus there is a nonzero polynomial $P$ of total degree of a polynomial $d\le p-1$ vanishing at every point of $A$. Its degree cannot be zero, since $A$ contains a line and is nonempty. Write $P_d$ for its nonzero top homogeneous polynomial part.

For every nonzero $v\in {\mathbb{F}}_p^n$, the directional hypothesis supplies an affine line in a vector spaceDirections are one-dimensional vector subspaces; rescaling a representative does not change this line. The univariate polynomial $P(a_v+tv)$ has degree at most $d<p$ and vanishes for all $p$ values of $t$. The root bound for a polynomial makes it the zero polynomial. Its coefficient of $t^d$ is exactly $P_d(v)$, so $P_d(v)=0$ for every nonzero $v$. Because $d>0$, $P_d(0)=0$ too.

To finish, we prove the relevant polynomial nonvanishing below the field size. A polynomial over ${\mathbb{F}}_p$ of degree at most $p-1$ in each variable cannot vanish on all of ${\mathbb{F}}_p^n$ unless it is zero. Induct on $n$. The one-variable case is the root bound for a polynomial. For more variables, writeFixing the first $n-1$ coordinates gives a univariate polynomial with $p$ roots of a polynomial, so all its coefficients are zero. Hence every $Q_j$ vanishes on ${\mathbb{F}}_p^{n-1}$, and the induction hypothesis makes every $Q_j$ zero. Applying this to $P_d$, whose total degree of a polynomial is less than $p$, contradicts its choice as nonzero.

Therefore $|A|\ge \dim \mathcal{P}$. Finally,which proves the requested lower bound. The crucial observation in the finite-field Kakeya polynomial bound is that complete lines force the highest homogeneous polynomial part to vanish in every direction.

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.