Sums of Residues

This chapter uses the Combinatorial Nullstellensatz (Theorem 2.7) and, in §3.4, the vanishing of power sums over a finite field. It uses no counting and no multiplicity. Throughout, $p$ is a prime and $\mathbb Z_p=\mathbb F_p$.

3.1 Cauchy–Davenport

Theorem 3.1 (Cauchy 1813; Davenport 1935). Let $A,B\subseteq\mathbb Z_p$ be nonempty. Then $|A+B|\ge\min(p,\,|A|+|B|-1)$.

Proof. Let $|A|=k$, $|B|=l$. Suppose first that $k+l-1\le p$ and, for contradiction, that $|A+B|\le k+l-2$. Since $k+l-2\le p-1$, we can choose $C\subseteq\mathbb Z_p$ with $A+B\subseteq C$ and $|C|=k+l-2$. Let

$$f(x,y)=\prod_{c\in C}(x+y-c)\in\mathbb Z_p[x,y].$$

Then $\deg f=k+l-2=(k-1)+(l-1)$, and the coefficient of $x^{k-1}y^{l-1}$ in $f$ is the coefficient of $x^{k-1}y^{l-1}$ in $(x+y)^{k+l-2}$, namely $\binom{k+l-2}{k-1}$, which is nonzero in $\mathbb Z_p$ because $k+l-2<p$ and $\binom{k+l-2}{k-1}$ is a quotient of products of integers less than $p$. By Theorem 2.7(b) with $S_1=A$, $S_2=B$, $t_1=k-1$, $t_2=l-1$, there is $(a,b)\in A\times B$ with $f(a,b)\ne0$, i.e. $a+b\notin C$. This contradicts $A+B\subseteq C$.

If $k+l-1>p$, choose $A'\subseteq A$ with $|A'|=k$ and $B'\subseteq B$ with $|B'|=p+1-k$, which is possible since $1\le p+1-k\le l$. The case already proved gives $|A'+B'|\ge\min(p,p)=p$, so $A+B\supseteq A'+B'=\mathbb Z_p$. ∎

The theorem is due to Cauchy, who used it in his work on Fermat's polygonal number theorem; Davenport rediscovered it and later acknowledged the priority (Davenport 1947). The proof above is from Alon, Nathanson, and Ruzsa (1995). The bound is attained by arithmetic progressions with the same common difference: if $A=\{0,1,\dots,k-1\}$ and $B=\{0,1,\dots,l-1\}$ then $A+B=\{0,\dots,k+l-2\}$. Vosper (1956) showed that for $2\le k,l$ and $k+l\le p-1$ these are essentially the only extremal pairs; the polynomial method does not give structural information of this kind, a point taken up in §8.2.

3.2 The Alon–Nathanson–Ruzsa theorem

The proof of Theorem 3.1 has an obvious generalisation: multiply $f$ by any polynomial $h(x,y)$ and one obtains a lower bound on the set of sums $a+b$ with $h(a,b)\ne0$.

Theorem 3.2 (Alon, Nathanson, and Ruzsa 1996). Let $A,B\subseteq\mathbb Z_p$ with $|A|=k\ge1$, $|B|=l\ge1$, let $h\in\mathbb Z_p[x,y]$ have degree exactly $m\ge0$, and suppose $m\le k+l-2$ and $k+l-1-m\le p$. Let

$$C=\{a+b:\ a\in A,\ b\in B,\ h(a,b)\ne0\}.$$

If the coefficient of $x^{k-1}y^{l-1}$ in $h(x,y)\,(x+y)^{k+l-2-m}$ is nonzero, then $|C|\ge k+l-1-m$.

Proof. Suppose $|C|\le k+l-2-m$. Since $k+l-2-m\le p-1$, choose $C'\supseteq C$ with $|C'|=k+l-2-m$ and let

$$f(x,y)=h(x,y)\prod_{c\in C'}(x+y-c),\qquad\deg f=m+(k+l-2-m)=k+l-2.$$

The homogeneous part of $f$ of degree $k+l-2$ is $h_m(x,y)(x+y)^{k+l-2-m}$, where $h_m$ is the degree-$m$ homogeneous part of $h$; the lower-degree parts of $h$ and the constants $c$ contribute only to monomials of lower degree. Hence the coefficient of $x^{k-1}y^{l-1}$ in $f$ equals its coefficient in $h_m(x+y)^{k+l-2-m}$, which equals its coefficient in $h(x+y)^{k+l-2-m}$, since $x^{k-1}y^{l-1}$ has degree $k+l-2$ and the parts of $h$ of degree less than $m$ produce only monomials of degree less than $k+l-2$. By hypothesis this coefficient is nonzero. Theorem 2.7(b) with $S_1=A$, $S_2=B$, $t_1=k-1$, $t_2=l-1$ gives $(a,b)\in A\times B$ with $f(a,b)\ne0$, so $h(a,b)\ne0$ and $a+b\notin C'\supseteq C$; but then $a+b\in C$, a contradiction. ∎

Theorem 3.1 is the case $h=1$. The next two corollaries are the cases $h=x-y$; they concern the restricted sumset $A\mathbin{\hat+}B=\{a+b:a\in A,b\in B,a\ne b\}$.

3.3 Restricted sums and the Erdős–Heilbronn conjecture

Erdős and Heilbronn (1964) conjectured that $|A\mathbin{\hat+}A|\ge\min(p,2|A|-3)$ for $A\subseteq\mathbb Z_p$. The conjecture was proved by Dias da Silva and Hamidoune (1994) by an argument in the exterior algebra (Grassmann derivatives); Alon, Nathanson, and Ruzsa (1995, 1996) gave the polynomial proof reproduced here, which also handles sets of different sizes.

Corollary 3.3 (Alon, Nathanson, and Ruzsa 1996). Let $A,B\subseteq\mathbb Z_p$ be nonempty with $|A|=k\ne l=|B|$. Then $|A\mathbin{\hat+}B|\ge\min(p,k+l-2)$.

Proof. Suppose first $k+l-2\le p$. Apply Theorem 3.2 with $h=x-y$, $m=1$. The coefficient of $x^{k-1}y^{l-1}$ in $(x-y)(x+y)^{k+l-3}=x(x+y)^{k+l-3}-y(x+y)^{k+l-3}$ is

$$\binom{k+l-3}{k-2}-\binom{k+l-3}{k-1}=\frac{(k+l-3)!}{(k-1)!\,(l-1)!}\,\big[(k-1)-(l-1)\big]=\frac{(k+l-3)!\,(k-l)}{(k-1)!\,(l-1)!},$$

where a binomial with a negative lower index is $0$ and the identity is checked by putting both terms over the common denominator $(k-1)!(l-1)!$. This is an integer (a difference of binomial coefficients) and its numerator $(k+l-3)!\,(k-l)$ is not divisible by $p$, because $k+l-3<p$ and $0<|k-l|<p$; its denominator is likewise prime to $p$. So the coefficient is nonzero in $\mathbb Z_p$, and the theorem gives $|A\mathbin{\hat+}B|\ge k+l-2$.

If $k+l-2>p$, then $k+l\ge p+3$ and we choose $A'\subseteq A$, $B'\subseteq B$ with $|A'|+|B'|=p+2$; since $p$ is odd (the case $p=2$ being trivial), $p+2$ is odd and $|A'|\ne|B'|$ automatically. The first case gives $|A'\mathbin{\hat+}B'|\ge p$, so $A\mathbin{\hat+}B=\mathbb Z_p$. ∎

When $k=l$ the coefficient above is $0$, and the argument must choose a different monomial.

Corollary 3.4 (Erdős–Heilbronn conjecture; Dias da Silva and Hamidoune 1994). Let $A\subseteq\mathbb Z_p$ with $|A|=k\ge2$. Then $|A\mathbin{\hat+}A|\ge\min(p,2k-3)$.

Proof. Suppose first $2k-3\le p$ and, for contradiction, that $|A\mathbin{\hat+}A|\le2k-4$. Since $2k-4\le p-1$, choose $C'\supseteq A\mathbin{\hat+}A$ with $|C'|=2k-4$, and let

$$f(x,y)=(x-y)\prod_{c\in C'}(x+y-c),\qquad\deg f=2k-3=(k-1)+(k-2).$$

The coefficient of $x^{k-1}y^{k-2}$ in $f$ is its coefficient in $(x-y)(x+y)^{2k-4}$, namely

$$\binom{2k-4}{k-2}-\binom{2k-4}{k-1}=\frac{(2k-4)!}{(k-1)!\,(k-2)!}\big[(k-1)-(k-2)\big]=\frac{(2k-4)!}{(k-1)!\,(k-2)!}=\frac{1}{k-1}\binom{2k-4}{k-2},$$

the $(k-2)$-nd Catalan number, an integer whose numerator $(2k-4)!$ is prime to $p$ because $2k-4<p$. So the coefficient is nonzero in $\mathbb Z_p$. Apply Theorem 2.7(b) with $S_1=S_2=A$, $t_1=k-1$, $t_2=k-2$; the hypotheses $|S_1|\ge k$ and $|S_2|\ge k-1$ hold. There is $(a,b)\in A\times A$ with $f(a,b)\ne0$, i.e. $a\ne b$ and $a+b\notin C'$, contradicting $C'\supseteq A\mathbin{\hat+}A$.

If $2k-3>p$, then $k\ge(p+4)/2>(p+3)/2$, so we may choose $A'\subseteq A$ with $|A'|=k'=(p+3)/2$ (an integer since $p$ is odd). Then $2k'-3=p$, and the first case gives $|A'\mathbin{\hat+}A'|\ge p$. ∎

The bound is attained by arithmetic progressions: for $A=\{0,1,\dots,k-1\}$ the restricted sumset is $\{1,\dots,2k-3\}$, since $0$ and $2k-2$ arise only from $0+0$ and $(k-1)+(k-1)$. The exact minimum of $|A\mathbin{\hat+}A|$ over all $k$-subsets of $\mathbb Z_p$ has been computed for $p\le17$ (Appendix A, Table A.1) and equals $\min(p,2k-3)$ for every $k\ge2$; likewise the minimum of $|A\mathbin{\hat+}B|$ over pairs with $|A|\ne|B|$ equals $\min(p,k+l-2)$ for $p\le11$. Both bounds are therefore sharp for every $k$, not merely asymptotically.

The general form of Theorem 3.2 allows other restrictions. Taking $h(x,y)=\prod_{\delta\in D}(x-y-\delta)$ for a set $D$ of forbidden differences gives $|\{a+b: a-b\notin D\}|\ge k+l-1-|D|$ whenever the corresponding coefficient is nonzero, which Alon, Nathanson, and Ruzsa verify for $|A|=|B|$ and $D$ of size less than $p$; I do not reproduce the coefficient computation.

3.4 Chevalley–Warning

The second application of the zeros principle in this chapter uses not the Nullstellensatz but the following property of power sums.

Lemma 3.5. For an integer $a\ge0$ (with $0^0=1$),

$$\sum_{t\in\mathbb F_q}t^a=\begin{cases}-1&\text{if }a\ge1\text{ and }(q-1)\mid a,\\ 0&\text{otherwise.}\end{cases}$$

Consequently, if a monomial $\mathbf x^{\boldsymbol\alpha}$ has $|\boldsymbol\alpha|<n(q-1)$ then $\sum_{\mathbf x\in\mathbb F_q^n}\mathbf x^{\boldsymbol\alpha}=0$, and the same holds for any polynomial of degree less than $n(q-1)$.

Proof. If $a=0$ the sum is $q\cdot1=0$. If $a\ge1$ and $(q-1)\mid a$, then $t^a=1$ for $t\ne0$ and the sum is $q-1=-1$. Otherwise let $g$ generate the cyclic group $\mathbb F_q^\times$; then $g^a\ne1$ and $\sum_{t\ne0}t^a=\sum_{j=0}^{q-2}g^{aj}=\frac{g^{a(q-1)}-1}{g^a-1}=0$. For the consequence, $\sum_{\mathbf x}\mathbf x^{\boldsymbol\alpha}=\prod_i\sum_{x_i}x_i^{\alpha_i}$; if $|\boldsymbol\alpha|<n(q-1)$ then some $\alpha_i<q-1$, and the $i$-th factor is $0$ by the first part (whether $\alpha_i=0$ or $1\le\alpha_i\le q-2$). ∎

Theorem 3.6 (Chevalley 1935; Warning 1935). Let $f_1,\dots,f_r\in\mathbb F_q[x_1,\dots,x_n]$ with $\sum_{i=1}^r\deg f_i<n$. Then the number $N$ of common zeros of $f_1,\dots,f_r$ in $\mathbb F_q^n$ is divisible by $p$. In particular, if the $f_i$ have a common zero, they have another.

Proof. Let $F(\mathbf x)=\prod_{i=1}^r\big(1-f_i(\mathbf x)^{q-1}\big)$. For $\mathbf x\in\mathbb F_q^n$, $F(\mathbf x)=1$ if every $f_i(\mathbf x)=0$ and $F(\mathbf x)=0$ otherwise, since $t^{q-1}=1$ for $t\ne0$. Hence $N\equiv\sum_{\mathbf x\in\mathbb F_q^n}F(\mathbf x)\pmod p$. But $\deg F\le(q-1)\sum\deg f_i<(q-1)n$, so the sum vanishes by Lemma 3.5. ∎

Warning's paper proves the stronger statement $N\ge q^{n-\sum\deg f_i}$ when $N>0$; Ax (1964) proved that $N$ is divisible by $q^{\lceil n/\sum\deg f_i\rceil-1}$. Neither is needed here.

3.5 Erdős–Ginzburg–Ziv

Theorem 3.7 (Erdős, Ginzburg, and Ziv 1961). Among any $2n-1$ integers there are $n$ whose sum is divisible by $n$.

Proof. First let $n=p$ be prime, and let $a_1,\dots,a_{2p-1}$ be the integers, regarded in $\mathbb F_p$. Consider

$$f_1=\sum_{i=1}^{2p-1}a_ix_i^{p-1},\qquad f_2=\sum_{i=1}^{2p-1}x_i^{p-1}\quad\in\mathbb F_p[x_1,\dots,x_{2p-1}].$$

Here $\deg f_1+\deg f_2\le2p-2<2p-1$, the number of variables, so by Theorem 3.6 the number of common zeros is divisible by $p$. The origin is a common zero, so there is another, $\mathbf x\ne\mathbf 0$. Let $I=\{i:x_i\ne0\}$, so $I\ne\emptyset$. Since $x_i^{p-1}=1$ for $i\in I$ and $0$ otherwise, $f_2(\mathbf x)=|I|\equiv0\pmod p$ with $1\le|I|\le2p-1$, whence $|I|=p$; and $f_1(\mathbf x)=\sum_{i\in I}a_i\equiv0\pmod p$. So the $p$ integers $a_i$, $i\in I$, have sum divisible by $p$.

For composite $n=uv$ with $u,v\ge2$, assume the theorem for $u$ and for $v$. Given $2uv-1$ integers, extract disjoint $u$-subsets with sum divisible by $u$ as long as at least $2u-1$ integers remain: after $j$ extractions, $2uv-1-ju\ge2u-1$ iff $j\le2v-2$, so we obtain $2v-1$ disjoint subsets $I_1,\dots,I_{2v-1}$, each of size $u$ with sum $us_j$. By the theorem for $v$, some $v$ of the integers $s_j$ have sum divisible by $v$; the union of the corresponding $I_j$ has $uv=n$ elements and sum $u\sum s_j$ divisible by $uv$. Induction on $n$ completes the proof. ∎

The theorem is sharp: $n-1$ zeros and $n-1$ ones contain no $n$ terms with sum divisible by $n$. The original proof of Erdős, Ginzburg, and Ziv (1961) uses the Cauchy–Davenport theorem; the proof of the prime case through Chevalley–Warning given above is due to Bailey and Richter (1989), and Alon (1999, §8) gives a third proof, through his permanent lemma. The theorem has been verified by exhaustive computation over all multisets of $2n-1$ residues for $n\le9$ (Appendix A). Its two-dimensional analogue, Kemnitz's conjecture (1983) that any $4n-3$ points of $\mathbb Z^2$ contain $n$ whose sum is divisible by $n$ in both coordinates, was proved by Reiher (2007) by an elaboration of the same method.

3.6 What the chapter shows

Every result in this chapter has the same shape. A set of sums is supposed small; a product $\prod_c(x+y-c)$ over the supposed sumset, times a restriction polynomial $h$, is a polynomial of degree exactly $\sum t_i$ whose value on $A\times B$ is forced to be zero by the smallness of the sumset; a single monomial coefficient, computed by a binomial identity, is nonzero; and the Nullstellensatz says the two are incompatible. The only place where number theory enters is in checking that the coefficient is nonzero modulo $p$, which reduces to the observation that factorials of numbers less than $p$ are prime to $p$. The method gives exact constants (the bounds are sharp for every $k$, as the computations of Appendix A confirm) but no structure: it does not say which sets attain the bounds.