Polynomial method in combinatorics

The polynomial method in combinatorics encodes a discrete configuration by polynomials and obtains combinatorial bounds from their degree, zeros, coefficients, or linear independence.

Suppose every point of ${\mathbb{F}}_q^n$ lies on an affine line in a vector space meeting a subset $N$ in at least $m$ points, with $1\le m\le q$. A smaller $N$ would admit a nonzero multivariate polynomial of total degree at most $m-1$ vanishing on it, by the dimension of a bounded-total-degree polynomial space. Each selected line then has more roots of a polynomial than the degree of its restriction, so the polynomial vanishes at every point. The Schwartz-Zippel lemma forbids this because $m-1<q$. Thus the displayed bound holds, and is at least $m^n/n!$. This is a point-covering condition; the finite-field Kakeya set condition instead quantifies over directions.

For a nonzero multivariate polynomial of total degree $d$ over a field, and a finite subset $S$ of that field, at most $d|S{|}^{n-1}$ points of $S^n$ are zeros. For one variable this is the root bound for a polynomial. If $d\ge |S|$, the bound is already trivial. Otherwise, in the inductive proof write the polynomial as degree $k$ in its last variable, with a nonzero leading coefficient of degree at most $d-k$ in the other variables. The leading coefficient vanishes on at most $(d-k)|S{|}^{n-2}$ fibers; outside those fibers there are at most $k$ roots of a polynomial per fiber. Counting the bad fibers with the trivial $|S|$ bound gives the asserted inequality.

A family of $L\ge 1$ lines in ${\mathbb{R}}^3$ imposes at most $L(d+1)$ linear conditions on degree-at-most-$d$ polynomials, by polynomial restriction to a line. The coefficient space has dimension $\left(\genfrac{}{}{0ex}{}{d+3}{3}\right)$. Whenever $(d+2)(d+3)>6L$, a nonzero common vanishing polynomial exists. Taking $d=\lceil \sqrt{6L}\rceil$ gives degree less than $4\sqrt{L}$.

For a finite set $A\subseteq [n]$ and a finite list $L$ of allowed intersection sizes, the displayed polynomial satisfies $p_A({\chi }_B)={\prod }_{\ell \in L}(|A\cap B|-\ell )$ at characteristic vectors of sets. For an $r$-uniform set family whose pairwise intersection sizes lie in $L\subseteq \{0,\dots ,r-1\}$, these polynomials vanish at all other family members and have nonzero values at their own members. Their restrictions are therefore linearly independent. Multilinear reduction on the Boolean cube and homogenisation on a uniform layer then prove the Ray-Chaudhuri–Wilson theorem bound.

Every length-$p$ sequence in the prime field ${\mathbb{F}}_p$ with sum zero, including sequences with repetitions, is the coordinatewise difference of two enumerations of that field. Apply the Combinatorial Nullstellensatz on $({\mathbb{F}}_p^{\ast }{)}^{p-1}$ to the product of the Vandermonde determinant in variables $x_i$ and its translate by the first $p-1$ sequence terms. The Dyson constant-term identity gives a nonzero top coefficient, and the zero-sum condition supplies the final missing field element. The argument includes $p=2$.

Let $P\in {\mathbb{F}}_p[x_1,\dots ,x_n]$ have total degree of a polynomial less than $p$. If the associated polynomial function vanishes on all of ${\mathbb{F}}_p^n$, then $P$ is the zero polynomial. Induct on $n$: writeFor each fixed $(x_1,\dots ,x_{n-1})$, the resulting univariate polynomial of degree less than $p$ has all $p$ field elements as roots, so every coefficient $P_j$ vanishes everywhere. The induction hypothesis makes every $P_j$ the zero polynomial.

A cap set is a subset $A\subseteq {\mathbb{F}}_3^n$ containing no three distinct points $x,y,z$ satisfying $x+y+z=0$. Equivalently, it contains no nonconstant three-term arithmetic progression.

A cap set in ${\mathbb{F}}_3^n$ has subset density $O(1/n)$. A Fourier analysis on a finite abelian group proof uses a hyperplane density increment for cap sets repeatedly: absence of nondiagonal zero-sum triples forces a large finite abelian Fourier coefficient, and hence a denser slice. This is a weaker bound than the Ellenberg–Gijswijt cap-set bound, but illustrates the density increment method.

Every Cartesian product of cap sets is a cap set. In characteristic three, $x+y+z=0$ with any two equal forces all three equal. A zero-sum triple in a Cartesian product of cap sets is therefore diagonal in every coordinate block, hence diagonal overall.

Suppose every cap set in ${\mathbb{F}}_3^n$ has cardinality at most $K{\theta }^n$, with $K$ independent of $n$. Applying this to the $k$-fold Cartesian product of a fixed cap set $A$ gives $|A{|}^k\le K{\theta }^{nk}$. Taking $k$th roots and letting $k$ tend to infinity proves $|A|\le {\theta }^n$. More generally this argument applies to any class of finite objects closed under products with multiplicative size and additive dimension.

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$.

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.

If polynomials $f_1,\dots ,f_r$ over a finite field have total degree sum strictly smaller than their number of variables, then the number of their common zeros is divisible by the field characteristic.

Every sequence of $4p-3$ elements of ${\mathbb{F}}_p^2$, where $p$ is prime, contains $p$ terms whose sum is zero. A proof applies the Chevalley-Warning theorem to the cardinality and two coordinate sums and then double-counts zero-sum subsequences.

For nonnegative integers $a_1,\dots ,a_n$,

When all exponents are positive, the Dyson constant-term identity satisfies $D(a)={\sum }_{i}D(a-e_i)$. This follows from the rational identity ${\sum }_i{\prod }_{j\ne i}(1-X_i/X_j{)}^{-1}=1$, obtained from Lagrange interpolation polynomial at zero. When $a_i=0$, taking the constant term in $X_i$ deletes that coordinate, giving the boundary recurrence.

Let $A$ and $B$ be $k$-element subsets of the additive group of a field of odd characteristic $p$, with $k<p$. There is a bijection $\pi :A\to B$ for which the sums $a+\pi (a)$ are pairwise distinct. The exterior-algebra proof works because $k!\ne 0$ in the field.

Let $f\in F[x_1,\dots ,x_n]$ have degree at most $d_1+\cdots +d_n$, and let each $A_i\subset F$ contain $d_i+1$ distinct elements. The Alon-Tarsi coefficient formula isIt follows by applying Lagrange interpolation successively in each variable.

One coefficient form of the Combinatorial Nullstellensatz says that if $\mathrm{deg}f\le d_1+\cdots +d_n$ and $[x_1^{d_1}\cdots x_n^{d_n}]f\ne 0$, then for every choice of sets $A_i$ with $|A_i|=d_i+1$ there is a point $(a_1,\dots ,a_n)\in A_1\times \cdots \times A_n$ at which $f$ does not vanish.

Suppose $|A|>|B|>0$ in ${\mathbb{F}}_p$. Put $a=|A|$ and $b^{\prime }=\min (|B|,p+2-a)$, and choose $B^{\prime }\subseteq B$ of size $b^{\prime }$. Let $r=a+b^{\prime }-2$. If the restricted sumset fits in a set $D$ of size $r-1$, then $(x-y){\prod }_{d\in D}(x+y-d)$ vanishes on $A\times B^{\prime }$. Its coefficient of $x^{a-1}{y}^{b^{\prime }-1}$ isAll factorial arguments are below $p$ and $0<a-b^{\prime }<p$. The Combinatorial Nullstellensatz gives a contradiction. Since $r=\min (p,|A|+|B|-2)$, this includes the saturated case as well as the small-set case.

For prime $p$, a graph with $m>(p-1)n$ edges and maximum degree at most $2p-1$ contains a nonempty $p$-regular subgraph. Over ${\mathbb{F}}_p$, apply the Combinatorial Nullstellensatz on the Boolean edge-variable cube toIts full squarefree coefficient is nonzero because the first product has degree below $m$. A nonzero value cannot occur at the zero vector; at any other Boolean vector the second product vanishes, and the first forces all selected degrees to be multiples of $p$. The maximum-degree condition makes every positive selected degree exactly $p$.

If an $n$ by $n$ matrix $A$ over a field has nonzero permanent, $b\in F^n$, and every $S_i\subseteq F$ has two elements, then some $x\in {\prod }_i{S}_i$ makes every coordinate of $Ax-b$ nonzero. Apply the Combinatorial Nullstellensatz towhose coefficient of $x_1\cdots x_n$ is $\mathrm{perm}A$.

Let $E\subseteq {\mathbb{F}}_p$ have size $m$, and let $\mathcal{A}\subseteq \mathcal{P}([n])$ satisfy $|A|\notin E$ and $|A\cap B|\in E$ for distinct $A,B\in \mathcal{A}$. ThenThe multilinearizations ofare linearly independent functions on the characteristic vectors of the family and lie in the multilinear polynomial space of degree at most $m$.