Introduction

1.1 The method

A polynomial in one variable of degree $d$ over a field has at most $d$ roots. This is the first nontrivial fact one learns about polynomials, and it is also, suitably generalised, the engine of one of the most productive techniques in modern combinatorics.

The technique works by contradiction. One wishes to show that a finite configuration, a set of points, lines, or residues, cannot be too small or too large. One supposes otherwise, and uses the supposed size to find a nonzero polynomial of unexpectedly low degree that vanishes on the configuration; this step is pure linear algebra, since vanishing at a point is a linear condition on coefficients. One then uses the structure of the configuration, the fact that it contains lines, or sums, or arithmetic progressions, to show that the polynomial must vanish on a much larger set than the configuration itself, indeed on so large a set that a polynomial of that degree cannot vanish there without being identically zero. The contradiction bounds the size of the configuration.

The method has an old history. Chevalley (1935) and Warning (1935) used the vanishing of power sums over a finite field to show that a system of polynomial equations in more variables than the sum of its degrees has a number of solutions divisible by the characteristic. Alon (1999), drawing on work with Tarsi (Alon and Tarsi 1992) and with Nathanson and Ruzsa in the preceding decade, formulated the Combinatorial Nullstellensatz, a statement about which polynomials can vanish on a product of finite sets, and showed that it gave short proofs of the Cauchy–Davenport theorem, of the Erdős–Heilbronn conjecture (first proved by Dias da Silva and Hamidoune in 1994 by other means), of Chevalley–Warning, and of results in graph colouring. But the method's standing changed in 2008, when Dvir (2009) proved in two pages a conjecture of Wolff (1999) on the size of Kakeya sets over finite fields, a problem that had resisted a decade of work by harmonic analysts. Within two years Guth and Katz (2010) had used a refinement of Dvir's idea to settle the joints problem and, with the further tool of polynomial partitioning, the Erdős distinct-distances problem (Guth and Katz 2015). Dvir, Kopparty, Saraf, and Sudan (2013) sharpened the Kakeya bound by requiring the polynomial to vanish to high order. And in 2016 Croot, Lev, and Pach (2017) and then Ellenberg and Gijswijt (2017) found that a variant of the method bounded the size of cap sets in $\mathbb F_3^n$ exponentially, a problem on which the best bound had for twenty years been only slightly better than trivial.

These results are usually presented separately, each with its own apparatus. The premise of this dissertation is that they share a common core, and that the core consists of three lemmas that can be stated and proved in a few pages of elementary algebra.

1.2 Three lemmas

The three lemmas are the following. Precise statements and proofs occupy Chapter 2.

The counting lemma. Let $V$ be a linear space of polynomials of dimension $N$, and let $A$ be a finite set of points at each of which we impose $c$ linear conditions (vanishing, or vanishing together with all derivatives up to a given order). If $c|A|<N$, some nonzero member of $V$ satisfies all the conditions. The space of polynomials of degree at most $d$ in $n$ variables has dimension $\binom{d+n}{n}$; vanishing to order $m$ at a point imposes $\binom{m+n-1}{n}$ conditions.

The zeros lemma. A nonzero polynomial of degree $d$ in $n$ variables has at most $d|S|^{n-1}$ zeros on the grid $S^n$, and this remains true when zeros are counted with multiplicity. A closely related statement, the Combinatorial Nullstellensatz, says that a polynomial cannot vanish on a product $S_1\times\dots\times S_n$ if it has a monomial $x_1^{t_1}\cdots x_n^{t_n}$ of maximal degree with nonzero coefficient and $|S_i|>t_i$ for each $i$.

The rank lemma. If $P$ is a polynomial of degree at most $d$ in $n$ variables, then for any finite set $A\subseteq\mathbb F^n$ the matrix $(P(\mathbf x+\mathbf y))_{\mathbf x,\mathbf y\in A}$ has rank at most twice the number of monomials of degree at most $d/2$. This is because each monomial in the expansion of $P(\mathbf x+\mathbf y)$ has low degree in $\mathbf x$ or low degree in $\mathbf y$.

The first lemma finds the polynomial; the second and third say what a polynomial cannot do. Every theorem in this dissertation is a combination of the first with one of the other two, with the specific geometry or arithmetic of the problem supplying the bridge between them. The following table records the pattern.

1.3 Main theorems

For definiteness, the theorems proved in full are the following. In each case the statement is the one in the literature, and where the argument here yields an explicit constant it is stated.

Theorem A (Alon 1999). Let $P\in\mathbb F[x_1,\dots,x_n]$ have degree $t_1+\dots+t_n$ with the coefficient of $x_1^{t_1}\cdots x_n^{t_n}$ nonzero, and let $S_i\subseteq\mathbb F$ with $|S_i|>t_i$. Then $P$ does not vanish identically on $S_1\times\dots\times S_n$.

Theorem B (Cauchy 1813; Davenport 1935; Alon–Nathanson–Ruzsa 1996; Dias da Silva–Hamidoune 1994). Let $p$ be prime and $A,B\subseteq\mathbb Z_p$ nonempty with $|A|=k$, $|B|=l$. Then $|A+B|\ge\min(p,k+l-1)$; if $k\ne l$ then $|A\mathbin{\hat+}B|\ge\min(p,k+l-2)$; and if $k\ge2$ then $|A\mathbin{\hat+}A|\ge\min(p,2k-3)$.

Theorem C (Chevalley 1935; Warning 1935; Erdős–Ginzburg–Ziv 1961). If $f_1,\dots,f_r\in\mathbb F_q[x_1,\dots,x_n]$ satisfy $\sum\deg f_i<n$, the number of common zeros is divisible by $p$. Consequently any $2n-1$ integers contain $n$ whose sum is divisible by $n$.

Theorem D (Dvir 2009; Dvir–Kopparty–Saraf–Sudan 2013). A Kakeya set $K\subseteq\mathbb F_q^n$ satisfies $|K|\ge\binom{q+n-1}{n}$ and $|K|\ge\big(q^2/(2q-1)\big)^n$.

Theorem E (Guth–Katz 2010; Kaplan–Sharir–Shustin 2010; Quilodrán 2010; Carbery–Iliopoulou 2014). Over any field, $L$ lines in $n$-space determine at most $\big(2\,(n!)^{1/n}\big)^{n/(n-1)}L^{n/(n-1)}$ joints. For $n=3$ the constant is $\sqrt{48}<6.93$.

Theorem F (Ellenberg–Gijswijt 2017). A subset of $\mathbb F_3^n$ containing no three distinct collinear points has at most $3\,m_{\lfloor 2n/3\rfloor}\le 3c^n$ elements, where $m_D$ is the number of $\boldsymbol\alpha\in\{0,1,2\}^n$ with $|\boldsymbol\alpha|\le D$ and

$$c=\frac{1+t_0+t_0^2}{t_0^{2/3}},\qquad t_0=\frac{\sqrt{33}-1}{8},\qquad c=2.755105\ldots$$

Theorem G (new; Chapter 7). Call $K\subseteq\mathbb F_q^2$ a punctured Kakeya set if for every direction some line in that direction has at most one point outside $K$, and let $\kappa^-(q)$ be the least size of such a set. Then $\kappa^-(q)=(q^2-1)/2$ for every odd $q\ge3$; and for even $q\ge4$, $q^2/2-\lceil(q+1)/6\rceil\le\kappa^-(q)\le q^2/2-1$, with equality on the right for $q=4,8$.

1.4 Contributions and provenance

This is, in the main, a dissertation of synthesis. None of the theorems A to F is new, and each is attributed to its authors where it is stated. Theorem G is new to the best of my knowledge, and Chapter 7 says exactly what it depends on. What the dissertation claims to add is the following.

First, an architecture. The three lemmas of §1.2 are isolated, proved once in their sharpest elementary forms, and used without further apparatus. The layer of multiplicity, Hasse derivatives and the multiplicity version of the zeros lemma, is developed in §2.3 and §2.5 and then used verbatim in the Kakeya argument of Chapter 4. A reader who has understood Chapter 2 has, I claim, understood everything that is not problem-specific in Chapters 3 to 6.

Second, complete proofs with explicit constants. The published proofs of Theorems D, E, and F are short and, in places, compressed. The proofs here are longer and, I hope, leave nothing to the reader; where a constant appears, the argument is carried through to an explicit value, and where a choice of parameter is made (the degree in the cap-set argument, the multiplicity in the Kakeya argument) the choice is optimised in the text.

Third, verification. Every bound in the dissertation has been compared with exhaustive computation in the smallest cases: the minimum sizes of sumsets and restricted sumsets in $\mathbb Z_p$ for $p\le17$; the Erdős–Ginzburg–Ziv theorem for $n\le9$; the minimum size of a Kakeya set in $\mathbb F_q^2$ for $q\le7$; the maximum size of a cap set in $\mathbb F_3^n$ for $n\le3$; and the numerical values of the Ellenberg–Gijswijt bound for $n\le12$. The computations are described in Appendix A and their outputs are reproduced there. They confirm the theorems, which was never in doubt, but more usefully they show how far each polynomial bound is from the truth in small cases, which is the beginning of an understanding of where the method is sharp and where it is not.

Fourth, a few corollaries and remarks that I have not seen stated in the form given here: the version of Theorem D for sets containing only a fraction of each line, with the multiplicity method (Corollary 4.8); the form of the joints theorem over an arbitrary field via the Frobenius map (Theorem 5.4, which follows Carbery and Iliopoulou); and the per-degree form of the cap-set bound in Theorem 6.5, which is slightly sharper than the usual statement in small dimensions. I make no claim that these are new; I claim only that I have not found them stated in this way, and a reader who knows the literature better will correct me.

Fifth, one new theorem. Chapter 7 determines 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, exactly for odd $q$ and up to an additive $\lceil(q+1)/6\rceil$ for even $q$ (Theorem G). The proof is not by the polynomial method, which gives only $\binom q2$; it is by inclusion–exclusion sharpened by a matching argument, and for odd $q$ it uses the Blokhuis–Mazzocca classification of minimal Kakeya sets. The chapter is therefore also a measurement: it shows that in the plane the polynomial method falls short of the truth by exactly $(q-1)/2$ for this variant, as it does for the original problem. The result was found by computation, proved afterwards, and checked against a literature search whose results are reported in the chapter; I have not found it elsewhere, but the search was mine and not a referee's.

I have tried to be scrupulous about what is proved and what is cited. Every result stated without proof is marked as such and attributed.

1.5 Outline

Chapter 2 develops the three lemmas, together with Hasse derivatives and multiplicity. Chapter 3 applies the zeros lemma, in its Nullstellensatz form, to sums of residues, and the power-sum form to Chevalley–Warning and Erdős–Ginzburg–Ziv. Chapter 4 proves Dvir's theorem and the Dvir–Kopparty–Saraf–Sudan bound for Kakeya sets, and compares them with the exact results in the plane. Chapter 5 proves the joints theorem in every dimension and over every field. Chapter 6 proves the Ellenberg–Gijswijt bound and determines its constant. Chapter 7 proves Theorem G on punctured Kakeya sets, the dissertation's one new result. Chapter 8 asks what the three lemmas do and do not explain, and lists open problems. Chapter 9 concludes. Appendix A contains the computations.

For the wider subject the reader may consult the surveys of Tao (2014) and Dvir (2012) and the lecture notes of Guth (2016), which cover polynomial partitioning and the Euclidean applications omitted here; for the additive number theory of Chapter 3, Nathanson (1996) and Tao and Vu (2006).