Three Lemmas

The polynomial method proves combinatorial bounds by encoding a finite configuration as the zero set of a low-degree polynomial and then exploiting the tension between two facts: a nonzero polynomial of low degree has few zeros, and a polynomial vanishing on a large set must have high degree. In the last fifteen years the method has settled several problems that had resisted other techniques, among them the finite-field Kakeya problem (Dvir 2009), the joints problem (Guth and Katz 2010), and the cap-set problem (Croot, Lev, and Pach 2017; Ellenberg and Gijswijt 2017), and it underlies the earlier Combinatorial Nullstellensatz of Alon (1999) and its applications in additive number theory.

This dissertation isolates three elementary lemmas, a counting lemma (a linear space of polynomials of dimension greater than the number of imposed conditions contains a nonzero solution), a zeros lemma (a nonzero polynomial of degree $d$ has at most $d|S|^{n-1}$ zeros on a grid $S^n$, counted with multiplicity), and a rank lemma (a matrix whose entries are values of a low-degree polynomial in $\mathbf x+\mathbf y$ has low rank), and derives from them, with complete proofs and explicit constants, the principal theorems of the subject: the Combinatorial Nullstellensatz; the Cauchy–Davenport theorem; the Alon–Nathanson–Ruzsa theorem and the Erdős–Heilbronn conjecture; Chevalley–Warning and Erdős–Ginzburg–Ziv; Dvir's Kakeya bound $|K|\ge\binom{q+n-1}{n}$ and the Dvir–Kopparty–Saraf–Sudan bound $|K|\ge (q^2/(2q-1))^n$; the joints theorem in every dimension over every field, with the constant $(2\,(n!)^{1/n})^{n/(n-1)}$; and the Ellenberg–Gijswijt bound $|A|\le 3\cdot(2.7552)^n$ for cap sets in $\mathbb F_3^n$, with the exact value of the constant.

The dissertation's contribution is mainly one of synthesis and verification. Each proof is traced to the lemma it uses; a layer of multiplicity (Hasse derivatives) is developed once and used in both the Kakeya and the zeros arguments; and every bound is checked against exhaustive computation in small cases, where the polynomial bounds are compared with the true extremal values. One result is new: the minimum size of a punctured Kakeya set in the plane, a set containing all but at most one point of some line in every direction, is $(q^2-1)/2$ for every odd $q$, and lies between $q^2/2-\lceil(q+1)/6\rceil$ and $q^2/2-1$ for even $q$, with the upper value attained for $q=4$ and $q=8$. The proof reduces the problem to a matching problem on the lines and uses the Blokhuis–Mazzocca classification of minimal Kakeya sets; it shows that the polynomial method, which gives $\binom q2$, falls short of the truth in the plane by exactly $(q-1)/2$. The penultimate chapter marks the limits of the three lemmas and states the open problems that lie beyond them.