Three Lemmas

2.1 Polynomials, degree, grids

Throughout, $\mathbb F$ is a field and $\mathbb F[\mathbf x]=\mathbb F[x_1,\dots,x_n]$. A polynomial is a finite linear combination of monomials $\mathbf x^{\boldsymbol\alpha}$; its degree $\deg P$ is the largest $|\boldsymbol\alpha|$ with nonzero coefficient, with $\deg 0=-\infty$. $P$ is homogeneous of degree $d$ if all its monomials have $|\boldsymbol\alpha|=d$, and every $P$ decomposes uniquely as $P=\sum_{k\ge0}P_k$ with $P_k$ homogeneous of degree $k$; $P_{\deg P}$ is the top homogeneous part. Two facts about degree are used constantly: $\deg(PQ)=\deg P+\deg Q$, and $\deg(P+Q)\le\max(\deg P,\deg Q)$.

A polynomial defines a function $\mathbb F^n\to\mathbb F$. Over an infinite field the polynomial is determined by the function; over $\mathbb F_q$ it is not, since $x^q-x$ vanishes identically. The following standard facts (Lidl and Niederreiter 1997, ch. 1) dispose of this.

Lemma 2.1. (a) The number of monomials $\mathbf x^{\boldsymbol\alpha}$ in $n$ variables with $|\boldsymbol\alpha|\le d$ is $\binom{d+n}{n}$; hence the space of polynomials of degree at most $d$ has dimension $\binom{d+n}{n}$. (b) Over $\mathbb F_q$, call $P$ reduced if every exponent in every monomial is at most $q-1$. Every function $\mathbb F_q^n\to\mathbb F_q$ is represented by exactly one reduced polynomial; in particular a reduced polynomial that vanishes on all of $\mathbb F_q^n$ is zero.

Proof. (a) Monomials of degree at most $d$ correspond to solutions of $\alpha_1+\dots+\alpha_n+\alpha_{n+1}=d$ in nonnegative integers, of which there are $\binom{d+n}{n}$. (b) The reduced monomials number $q^n$, as do the functions $\mathbb F_q^n\to\mathbb F_q$, so it suffices to show that the reduced polynomials span the functions. For $\mathbf a\in\mathbb F_q^n$ the polynomial $\delta_{\mathbf a}(\mathbf x)=\prod_{i=1}^n\big(1-(x_i-a_i)^{q-1}\big)$ is reduced and equals $1$ at $\mathbf a$ and $0$ elsewhere, because $t^{q-1}=1$ for $t\ne0$. The $\delta_{\mathbf a}$ span all functions. ∎

For $S\subseteq\mathbb F$ finite, the grid $S^n$ is the product set. The lemmas below concern polynomials on grids; the case $S=\mathbb F_q$, $S^n=\mathbb F_q^n$, is the most important.

2.2 Counting

Lemma 2.2 (Counting). Let $V$ be a linear space of polynomials in $\mathbb F[\mathbf x]$ of finite dimension $N$, and let $\lambda_1,\dots,\lambda_M:V\to\mathbb F$ be linear functionals with $M<N$. Then there is a nonzero $P\in V$ with $\lambda_j(P)=0$ for all $j$. In particular:

(a) If $A\subseteq\mathbb F^n$ and $|A|<\binom{d+n}{n}$, there is a nonzero polynomial of degree at most $d$ vanishing on $A$.

(b) If $A\subseteq\mathbb F^n$ and $|A|\binom{m+n-1}{n}<\binom{d+n}{n}$, there is a nonzero polynomial of degree at most $d$ vanishing to order at least $m$ at every point of $A$ (in the sense of Definition 2.4 below).

Proof. The map $P\mapsto(\lambda_1(P),\dots,\lambda_M(P))$ is linear from an $N$-dimensional space to an $M$-dimensional one; since $M<N$ its kernel is nonzero. For (a), take $V$ the polynomials of degree at most $d$ and the functionals $P\mapsto P(\mathbf a)$, $\mathbf a\in A$. For (b), take the functionals $P\mapsto P^{(\mathbf i)}(\mathbf a)$ for $\mathbf a\in A$ and $|\mathbf i|\le m-1$, where $P^{(\mathbf i)}$ is the Hasse derivative of §2.3; each is linear in $P$, and the number of $\mathbf i\in\mathbb N^n$ with $|\mathbf i|\le m-1$ is $\binom{m-1+n}{n}$ by Lemma 2.1(a). ∎

The lemma is trivial, and its triviality is the point: the existence of the polynomial costs nothing. Everything difficult in the method is in showing that the polynomial cannot exist.

2.3 Hasse derivatives and multiplicity

Over a field of positive characteristic the ordinary derivative behaves badly: $\frac{d}{dx}x^p=0$. The remedy, due to Hasse (1936), is to define derivatives by Taylor expansion rather than by differentiation.

Definition 2.3. For $P\in\mathbb F[\mathbf x]$ the Hasse derivatives $P^{(\mathbf i)}\in\mathbb F[\mathbf x]$, $\mathbf i\in\mathbb N^n$, are defined by the identity

$$P(\mathbf x+\mathbf y)=\sum_{\mathbf i\in\mathbb N^n}P^{(\mathbf i)}(\mathbf x)\,\mathbf y^{\mathbf i}\qquad\text{in }\mathbb F[\mathbf x,\mathbf y].$$

Since $(\mathbf x+\mathbf y)^{\boldsymbol\alpha}=\prod_j(x_j+y_j)^{\alpha_j}=\sum_{\mathbf i\le\boldsymbol\alpha}\binom{\boldsymbol\alpha}{\mathbf i}\mathbf x^{\boldsymbol\alpha-\mathbf i}\mathbf y^{\mathbf i}$, one has for monomials

$$(\mathbf x^{\boldsymbol\alpha})^{(\mathbf i)}=\binom{\boldsymbol\alpha}{\mathbf i}\mathbf x^{\boldsymbol\alpha-\mathbf i}\quad(\mathbf i\le\boldsymbol\alpha),\qquad(\mathbf x^{\boldsymbol\alpha})^{(\mathbf i)}=0\quad\text{otherwise},$$

and $P\mapsto P^{(\mathbf i)}$ is linear. $P^{(\mathbf 0)}=P$, and for $|\mathbf i|=1$ the Hasse derivative is the ordinary partial derivative. Over $\mathbb Q$, $P^{(\mathbf i)}=\frac{1}{\mathbf i!}\partial^{\mathbf i}P$; the point of the definition is that it makes sense in every characteristic.

Definition 2.4. The multiplicity of $P$ at $\mathbf a\in\mathbb F^n$ is

$$\operatorname{mult}(P,\mathbf a)=\min\{|\mathbf i|:P^{(\mathbf i)}(\mathbf a)\ne0\},$$

with $\operatorname{mult}(0,\mathbf a)=\infty$. Equivalently, since $P(\mathbf a+\mathbf y)=\sum_{\mathbf i}P^{(\mathbf i)}(\mathbf a)\mathbf y^{\mathbf i}$, it is the least degree of a monomial occurring in $P(\mathbf a+\mathbf y)$ as a polynomial in $\mathbf y$. Thus $\operatorname{mult}(P,\mathbf a)\ge1$ iff $P(\mathbf a)=0$, and $P$ vanishes to order $m$ at $\mathbf a$ iff $\operatorname{mult}(P,\mathbf a)\ge m$.

If $P\ne0$ then $P(\mathbf a+\mathbf y)\ne0$ (the substitution $\mathbf x\mapsto\mathbf x+\mathbf a$ is an automorphism of $\mathbb F[\mathbf x]$), so $\operatorname{mult}(P,\mathbf a)$ is finite and at most $\deg P$.

Lemma 2.5 (Properties of Hasse derivatives). Let $P\in\mathbb F[\mathbf x]$.

(i) (Composition) $\big(P^{(\mathbf i)}\big)^{(\mathbf j)}=\binom{\mathbf i+\mathbf j}{\mathbf i}P^{(\mathbf i+\mathbf j)}$.

(ii) (Degree) $\deg P^{(\mathbf i)}\le\deg P-|\mathbf i|$. If $P$ is homogeneous of degree $d$, then $P^{(\mathbf i)}$ is homogeneous of degree $d-|\mathbf i|$ or zero. Consequently the homogeneous part of $P^{(\mathbf i)}$ of degree $\deg P-|\mathbf i|$ is $(P_{\deg P})^{(\mathbf i)}$.

(iii) (Multiplicity of derivatives) If $\operatorname{mult}(P,\mathbf a)\ge m$ then $\operatorname{mult}(P^{(\mathbf i)},\mathbf a)\ge m-|\mathbf i|$.

(iv) (Restriction to a line) For $\mathbf a,\mathbf b\in\mathbb F^n$ let $P_{\mathbf a,\mathbf b}(t)=P(\mathbf a+t\mathbf b)\in\mathbb F[t]$. Then for every $t_0\in\mathbb F$, $\operatorname{mult}(P_{\mathbf a,\mathbf b},t_0)\ge\operatorname{mult}(P,\mathbf a+t_0\mathbf b)$.

(v) (Univariate multiplicity) For $0\ne P\in\mathbb F[t]$ and $t_0\in\mathbb F$, $\operatorname{mult}(P,t_0)$ is the largest $m$ with $(t-t_0)^m\mid P$, and $\sum_{t_0\in\mathbb F}\operatorname{mult}(P,t_0)\le\deg P$.

(vi) (Leading coefficient along a line) If $\deg P\le e$ and $P_e$ is its homogeneous part of degree $e$ (possibly zero), then for all $\mathbf a,\mathbf b$ the coefficient of $t^e$ in $P(\mathbf a+t\mathbf b)$ is $P_e(\mathbf b)$.

Proof. (i) Expand $P(\mathbf x+\mathbf y+\mathbf z)$ in two ways. Grouping as $(\mathbf x+\mathbf y)+\mathbf z$ and then expanding in $\mathbf y$,

$$P(\mathbf x+\mathbf y+\mathbf z)=\sum_{\mathbf j}P^{(\mathbf j)}(\mathbf x+\mathbf y)\mathbf z^{\mathbf j}=\sum_{\mathbf j}\sum_{\mathbf i}\big(P^{(\mathbf j)}\big)^{(\mathbf i)}(\mathbf x)\mathbf y^{\mathbf i}\mathbf z^{\mathbf j}.$$

Grouping as $\mathbf x+(\mathbf y+\mathbf z)$,

$$P(\mathbf x+\mathbf y+\mathbf z)=\sum_{\mathbf k}P^{(\mathbf k)}(\mathbf x)(\mathbf y+\mathbf z)^{\mathbf k}=\sum_{\mathbf k}P^{(\mathbf k)}(\mathbf x)\sum_{\mathbf i+\mathbf j=\mathbf k}\binom{\mathbf k}{\mathbf i}\mathbf y^{\mathbf i}\mathbf z^{\mathbf j}.$$

Comparing coefficients of $\mathbf y^{\mathbf i}\mathbf z^{\mathbf j}$ in $\mathbb F[\mathbf x,\mathbf y,\mathbf z]$ gives $(P^{(\mathbf j)})^{(\mathbf i)}=\binom{\mathbf i+\mathbf j}{\mathbf i}P^{(\mathbf i+\mathbf j)}$, which is (i) with the roles of $\mathbf i,\mathbf j$ exchanged (the binomial is symmetric).

(ii) By linearity it suffices to check monomials, and $(\mathbf x^{\boldsymbol\alpha})^{(\mathbf i)}$ is either zero or a scalar multiple of $\mathbf x^{\boldsymbol\alpha-\mathbf i}$, of degree $|\boldsymbol\alpha|-|\mathbf i|$. The last sentence follows: the monomials of $P^{(\mathbf i)}$ of degree $\deg P-|\mathbf i|$ can only arise from monomials of $P$ of degree $\deg P$.

(iii) By (i), $\big(P^{(\mathbf i)}\big)^{(\mathbf j)}(\mathbf a)=\binom{\mathbf i+\mathbf j}{\mathbf i}P^{(\mathbf i+\mathbf j)}(\mathbf a)$, and if $|\mathbf j|<m-|\mathbf i|$ then $|\mathbf i+\mathbf j|<m$, so $P^{(\mathbf i+\mathbf j)}(\mathbf a)=0$.

(iv) Let $\mathbf x_0=\mathbf a+t_0\mathbf b$ and $m=\operatorname{mult}(P,\mathbf x_0)$. Then

$$P_{\mathbf a,\mathbf b}(t_0+s)=P(\mathbf x_0+s\mathbf b)=\sum_{\mathbf i}P^{(\mathbf i)}(\mathbf x_0)\,s^{|\mathbf i|}\mathbf b^{\mathbf i},$$

and every term with $|\mathbf i|<m$ vanishes, so $s^m$ divides $P_{\mathbf a,\mathbf b}(t_0+s)$ as a polynomial in $s$, which is to say $\operatorname{mult}(P_{\mathbf a,\mathbf b},t_0)\ge m$.

(v) $P(t_0+s)=\sum_i P^{(i)}(t_0)s^i$ has least-degree term $s^m$ with $m=\operatorname{mult}(P,t_0)$, so $P(t_0+s)=s^mQ(s)$ with $Q(0)\ne0$, i.e. $P(t)=(t-t_0)^mQ(t-t_0)$ with $(t-t_0)\nmid Q(t-t_0)$. The divisibility characterisation follows, and since the polynomials $(t-t_0)^{m_{t_0}}$ for distinct $t_0$ are pairwise coprime, their product divides $P$, giving $\sum m_{t_0}\le\deg P$.

(vi) Write $P=\sum_{k\le e}P_k$. For a monomial $\mathbf x^{\boldsymbol\alpha}$ of degree $k$, $(\mathbf a+t\mathbf b)^{\boldsymbol\alpha}=\prod_j(a_j+tb_j)^{\alpha_j}$ is a polynomial in $t$ of degree at most $k$ whose coefficient of $t^k$ is $\mathbf b^{\boldsymbol\alpha}$. Hence $P_k(\mathbf a+t\mathbf b)$ has degree at most $k$ with $t^k$-coefficient $P_k(\mathbf b)$, and the only contribution to $t^e$ comes from $k=e$. ∎

2.4 Zeros: Schwartz–Zippel and the Combinatorial Nullstellensatz

Lemma 2.6 (Schwartz–Zippel). Let $0\ne P\in\mathbb F[x_1,\dots,x_n]$ have degree $d$ and let $S\subseteq\mathbb F$ be finite. Then $P$ has at most $d|S|^{n-1}$ zeros in $S^n$.

Proof. Induction on $n$. For $n=1$ this is the statement that a nonzero univariate polynomial of degree $d$ has at most $d$ roots, which is (v) of Lemma 2.5. For $n>1$ write $P=\sum_{j=0}^{t}P_j(x_1,\dots,x_{n-1})x_n^j$ with $P_t\ne0$, so $\deg P_t\le d-t$. For $\mathbf a\in S^{n-1}$: if $P_t(\mathbf a)=0$, count all $|S|$ points $(\mathbf a,b)$ as possible zeros; there are at most $(d-t)|S|^{n-2}$ such $\mathbf a$ by induction, contributing at most $(d-t)|S|^{n-1}$. If $P_t(\mathbf a)\ne0$, the univariate polynomial $P(\mathbf a,x_n)$ has degree exactly $t$ and hence at most $t$ roots, contributing at most $t|S|^{n-1}$ in total. The sum is $d|S|^{n-1}$. ∎

The lemma is attributed to Schwartz (1980) and Zippel (1979), and independently to DeMillo and Lipton (1978). Its most useful special case is $S=\mathbb F_q$ and $d<q$: then $P$ has fewer than $q^n$ zeros, so a nonzero polynomial of degree less than $q$ cannot vanish on all of $\mathbb F_q^n$.

The Combinatorial Nullstellensatz refines the lemma from grids $S^n$ to products $S_1\times\dots\times S_n$ of sets of different sizes, and from total degree to the degrees in each variable.

Theorem 2.7 (Combinatorial Nullstellensatz; Alon 1999). Let $S_1,\dots,S_n\subseteq\mathbb F$ be finite and nonempty, let $t_1,\dots,t_n\ge0$ be integers with $|S_i|\ge t_i+1$, and let $P\in\mathbb F[\mathbf x]$.

(a) If $\deg_{x_i}P\le t_i$ for every $i$ and $P$ vanishes on $S_1\times\dots\times S_n$, then $P=0$.

(b) If $\deg P=t_1+\dots+t_n$ and the coefficient of $x_1^{t_1}\cdots x_n^{t_n}$ in $P$ is nonzero, then there is $\mathbf a\in S_1\times\dots\times S_n$ with $P(\mathbf a)\ne0$.

Proof. (a) Induction on $n$; the case $n=1$ is Lemma 2.5(v). Write $P=\sum_{j\le t_n}P_j(x_1,\dots,x_{n-1})x_n^j$. For each $\mathbf a\in S_1\times\dots\times S_{n-1}$ the polynomial $P(\mathbf a,x_n)$ has degree at most $t_n$ and vanishes at the $|S_n|\ge t_n+1$ points of $S_n$, so it is zero, i.e. $P_j(\mathbf a)=0$ for all $j$. Thus each $P_j$ vanishes on $S_1\times\dots\times S_{n-1}$ and has $\deg_{x_i}P_j\le t_i$, so $P_j=0$ by induction.

(b) Shrinking the $S_i$ we may assume $|S_i|=t_i+1$. Let $g_i(x_i)=\prod_{s\in S_i}(x_i-s)$, monic of degree $t_i+1$ and vanishing on $S_i$. Suppose $P$ vanishes on $S_1\times\dots\times S_n$. Reduce $P$ as follows: while some monomial $\mathbf x^{\boldsymbol\alpha}$ with nonzero coefficient has $\alpha_i\ge t_i+1$ for some $i$, subtract from $P$ the polynomial $c\,\mathbf x^{\boldsymbol\alpha-(t_i+1)\mathbf e_i}g_i(x_i)$, where $c$ is the coefficient; this removes the monomial $\mathbf x^{\boldsymbol\alpha}$ and introduces monomials $\mathbf x^{\boldsymbol\alpha-(t_i+1)\mathbf e_i}x_i^j$ with $j\le t_i$, all of degree less than $|\boldsymbol\alpha|$. The process terminates (each step replaces one offending monomial by finitely many monomials of strictly smaller degree, so the multiset of degrees of offending monomials decreases in the well-founded multiset ordering), it does not change the values of $P$ on the product set (each $g_i$ vanishes there), and it does not change the coefficient of $x_1^{t_1}\cdots x_n^{t_n}$: the removed monomial $\mathbf x^{\boldsymbol\alpha}$ has some $\alpha_i>t_i$ and $|\boldsymbol\alpha|\le\deg P=\sum t_j$, hence is not $x_1^{t_1}\cdots x_n^{t_n}$; and the introduced monomials have degree less than $|\boldsymbol\alpha|\le\sum t_j$, so none of them is $x_1^{t_1}\cdots x_n^{t_n}$ either. The result is a polynomial $\bar P$ with $\deg_{x_i}\bar P\le t_i$, vanishing on the product set, with the same nonzero coefficient of $x_1^{t_1}\cdots x_n^{t_n}$ as $P$; in particular $\bar P\ne0$. This contradicts (a). ∎

Alon's paper gives (a) and (b) as Theorems 1.1 and 1.2 and calls them both the Combinatorial Nullstellensatz; the name refers to Hilbert's Nullstellensatz, of which (a) is a combinatorial analogue for the ideal generated by the $g_i$. Shorter proofs of (b) have since been given by Michałek (2010) and Lasoń (2010); the proof above follows Alon.

Two remarks on the hypothesis of (b). The degree condition $\deg P=\sum t_i$ is essential: it is what guarantees that the reduction cannot create the distinguished monomial. And the condition is about a single monomial of maximal degree, not about $P$ as a whole; $P$ may have many other monomials of the same degree, and it does not matter what they are.

2.5 Zeros with multiplicity

Lemma 2.8 (Multiplicity Schwartz–Zippel; Dvir, Kopparty, Saraf, and Sudan 2013). Let $0\ne P\in\mathbb F[x_1,\dots,x_n]$ have degree $d$ and let $S\subseteq\mathbb F$ be finite. Then

$$\sum_{\mathbf a\in S^n}\operatorname{mult}(P,\mathbf a)\le d\,|S|^{n-1}.$$

Proof. Induction on $n$. For $n=1$ this is Lemma 2.5(v). For $n>1$, write $P=\sum_{j=0}^tP_j(\mathbf x')x_n^j$ with $\mathbf x'=(x_1,\dots,x_{n-1})$ and $P_t\ne0$; then $\deg P_t\le d-t$. Fix $\mathbf a\in S^{n-1}$ and put $m_{\mathbf a}=\operatorname{mult}(P_t,\mathbf a)$, which is finite since $P_t\ne0$. We claim

$$\sum_{b\in S}\operatorname{mult}\big(P,(\mathbf a,b)\big)\le|S|\,m_{\mathbf a}+t.\tag{2.1}$$

Choose $\mathbf i'\in\mathbb N^{n-1}$ with $|\mathbf i'|=m_{\mathbf a}$ and $P_t^{(\mathbf i')}(\mathbf a)\ne0$, and let $R=P^{(\mathbf i',0)}$ be the Hasse derivative of $P$ of order $\mathbf i'$ in the variables $\mathbf x'$ and order $0$ in $x_n$. From the definition, $R=\sum_jP_j^{(\mathbf i')}(\mathbf x')x_n^j$, so the univariate polynomial $R(\mathbf a,x_n)$ has degree exactly $t$, its coefficient of $x_n^t$ being $P_t^{(\mathbf i')}(\mathbf a)\ne0$. By Lemma 2.5(v),

$$\sum_{b\in S}\operatorname{mult}\big(R(\mathbf a,\cdot),b\big)\le t.$$

For each $b$, Lemma 2.5(iii) gives $\operatorname{mult}(R,(\mathbf a,b))\ge\operatorname{mult}(P,(\mathbf a,b))-m_{\mathbf a}$, and Lemma 2.5(iv), applied to the line $(\mathbf a,b)+s(\mathbf 0,1)$, gives $\operatorname{mult}(R(\mathbf a,\cdot),b)\ge\operatorname{mult}(R,(\mathbf a,b))$. Combining,

$$\operatorname{mult}\big(P,(\mathbf a,b)\big)\le m_{\mathbf a}+\operatorname{mult}\big(R(\mathbf a,\cdot),b\big),$$

and summing over $b\in S$ proves (2.1). Now sum (2.1) over $\mathbf a\in S^{n-1}$, using the induction hypothesis $\sum_{\mathbf a}m_{\mathbf a}\le(d-t)|S|^{n-2}$ for $P_t$:

$$\sum_{\mathbf a\in S^{n-1}}\sum_{b\in S}\operatorname{mult}\big(P,(\mathbf a,b)\big)\le|S|(d-t)|S|^{n-2}+t|S|^{n-1}=d|S|^{n-1}.\qquad\blacksquare$$

Lemma 2.6 is the case in which every multiplicity is replaced by $\min(\operatorname{mult},1)$. The multiplicity version costs nothing more than the bookkeeping of §2.3, and it is exactly what the Kakeya argument of §4.4 needs.

2.6 Rank

Lemma 2.9 (Rank). Let $A,B$ be finite sets, $\mathbb F$ a field, and $f:A\times B\to\mathbb F$. If $f(x,y)=\sum_{k=1}^rg_k(x)h_k(y)$ for some functions $g_k:A\to\mathbb F$, $h_k:B\to\mathbb F$, then the matrix $(f(x,y))_{x\in A,y\in B}$ has rank at most $r$.

Proof. Each summand $(g_k(x)h_k(y))_{x,y}$ is the outer product of two vectors and has rank at most $1$; rank is subadditive. ∎

The lemma is trivial; its force comes from the following observation of Croot, Lev, and Pach (2017), in the form given by Tao (2016).

Lemma 2.10 (Croot–Lev–Pach). Let $\mathcal M$ be a set of monomials in $\mathbb F[x_1,\dots,x_n]$ that is closed under division (if $\mathbf x^{\boldsymbol\alpha}\in\mathcal M$ and $\boldsymbol\beta\le\boldsymbol\alpha$ then $\mathbf x^{\boldsymbol\beta}\in\mathcal M$), and for $e\ge0$ let $M_e$ be the number of monomials in $\mathcal M$ of degree at most $e$, with $M_{-1}=0$. Let $P$ be a linear combination of monomials in $\mathcal M$ of degree at most $d$. Then for every finite $A\subseteq\mathbb F^n$ the matrix $\big(P(\mathbf x+\mathbf y)\big)_{\mathbf x,\mathbf y\in A}$ has rank at most

$$M_{\lfloor d/2\rfloor}+M_{\lceil d/2\rceil-1}\le2M_{\lfloor d/2\rfloor}.$$

Proof. Each monomial $(\mathbf x+\mathbf y)^{\boldsymbol\gamma}$ with $\mathbf x^{\boldsymbol\gamma}\in\mathcal M$, $|\boldsymbol\gamma|\le d$, expands as $\sum_{\boldsymbol\alpha+\boldsymbol\beta=\boldsymbol\gamma}\binom{\boldsymbol\gamma}{\boldsymbol\alpha}\mathbf x^{\boldsymbol\alpha}\mathbf y^{\boldsymbol\beta}$, and each term has $\mathbf x^{\boldsymbol\alpha},\mathbf y^{\boldsymbol\beta}\in\mathcal M$ (closure under division) and $|\boldsymbol\alpha|+|\boldsymbol\beta|\le d$. Hence

$$P(\mathbf x+\mathbf y)=\sum c_{\boldsymbol\alpha,\boldsymbol\beta}\,\mathbf x^{\boldsymbol\alpha}\mathbf y^{\boldsymbol\beta}$$

over pairs with $\mathbf x^{\boldsymbol\alpha},\mathbf y^{\boldsymbol\beta}\in\mathcal M$ and $|\boldsymbol\alpha|+|\boldsymbol\beta|\le d$. In every such pair, either $|\boldsymbol\alpha|\le\lfloor d/2\rfloor$ or $|\boldsymbol\beta|\le d-\lfloor d/2\rfloor-1=\lceil d/2\rceil-1$. Group the terms accordingly:

$$P(\mathbf x+\mathbf y)=\sum_{|\boldsymbol\alpha|\le\lfloor d/2\rfloor}\mathbf x^{\boldsymbol\alpha}F_{\boldsymbol\alpha}(\mathbf y)+\sum_{|\boldsymbol\beta|\le\lceil d/2\rceil-1}G_{\boldsymbol\beta}(\mathbf x)\,\mathbf y^{\boldsymbol\beta},$$

where the first sum collects all terms with $|\boldsymbol\alpha|\le\lfloor d/2\rfloor$ and the second the remaining terms. The number of summands is at most $M_{\lfloor d/2\rfloor}+M_{\lceil d/2\rceil-1}$, and Lemma 2.9 applies. ∎

The case that matters in Chapter 6 is $\mathbb F=\mathbb F_3$ and $\mathcal M$ the reduced monomials, those with every exponent in $\{0,1,2\}$, for which $M_e=m_e:=\#\{\boldsymbol\alpha\in\{0,1,2\}^n:|\boldsymbol\alpha|\le e\}$.

One further elementary lemma is needed there.

Lemma 2.11 (Support). Let $W\subseteq\mathbb F^{S}$ be a linear subspace of dimension $D$, where $S$ is a finite set. Then some $w\in W$ has at least $D$ nonzero coordinates.

Proof. Let $w\in W$ have support $T=\{s:w_s\ne0\}$ of maximal size, and suppose $|T|<D$. The projection $W\to\mathbb F^T$ has kernel of dimension at least $D-|T|>0$; let $v\ne0$ be in it, so $v_s=0$ for $s\in T$ and $v_{s_0}\ne0$ for some $s_0\notin T$. Then $w+v$ agrees with $w$ on $T$ and with $v$ off $T$, so its support is $T\cup\operatorname{supp}(v)\supsetneq T$, contradicting maximality. ∎

2.7 Summary

The dissertation uses: the dimension count $\binom{d+n}{n}$ (Lemma 2.1); the counting lemma with and without multiplicity (Lemma 2.2); the properties (i) to (vi) of Hasse derivatives (Lemma 2.5); the Schwartz–Zippel lemma (2.6) and its multiplicity form (2.8); the Combinatorial Nullstellensatz (Theorem 2.7); the rank lemma (2.9) with the Croot–Lev–Pach expansion (2.10); and the support lemma (2.11). Nothing else of a general nature is needed. Each subsequent chapter begins by saying which of these it uses.