Contents / Combinatorics / Algebraic and Additive Combinatorics

Chapter 9

Algebraic and Additive Combinatorics

Polynomials as a counting tool — the Combinatorial Nullstellensatz — and the structure of sumsets from Cauchy–Davenport onward.

Introduction

Polynomials as a counting tool — the Combinatorial Nullstellensatz — and the structure of sumsets from Cauchy–Davenport onward.

Two subjects share this chapter, and they share it for a reason. The first is the polynomial method: encode a combinatorial question as a polynomial, and let the rigidity of polynomials — chiefly the fact that a nonzero polynomial cannot have too many roots — do the counting. The second is additive combinatorics: the study of how large $A+B$ must be, and of what a set looks like when its sumset is unexpectedly small. The bridge between them is the Cauchy–Davenport theorem, the first nontrivial theorem of additive combinatorics, whose cleanest modern proof is three lines of the polynomial method. Everything before that section builds the algebraic tool; everything after it uses the result the tool produced.

9.1The Combinatorial Nullstellensatz

One fact about polynomials in one variable is used more often than all the others combined: a nonzero polynomial of degree $d$ over a field has at most $d$ roots. It is a counting statement — it bounds the size of a set (the roots) by an algebraic quantity (the degree) — and that is exactly the shape of statement a combinatorialist wants. The whole of this chapter's first half is the search for a multivariate version.

Theorem 9.1 (Root bound in one variable). Let $F$ be a field and let $f \in F[x]$ be a nonzero polynomial of degree $d$ . Then $f$ has at most $d$ roots in $F$ .

Proof. Induct on $d$ . A nonzero constant has no roots. If $d \ge 1$ and $f(a) = 0$ , divide $f$ by $x - a$ with remainder: $f(x) = (x-a)q(x) + r$ with $r \in F$ constant, and substituting $x = a$ gives $r = 0$ . So $f = (x-a)q$ with $\deg q = d - 1$ . Any root $b \neq a$ of $f$ satisfies $(b-a)q(b) = 0$ , and since $F$ is a field and $b - a \neq 0$ , it is a root of $q$ . By induction $q$ has at most $d-1$ roots, so $f$ has at most $d$ .∎

The field hypothesis is not decoration: the proof uses that $F$ has no zero divisors, and without it the statement is false. Over $\mathbb{Z}/8\mathbb{Z}$ the quadratic $x^{2} - 1$ has the four roots $1, 3, 5, 7$ .

The naive multivariate generalisation is false at once. The polynomial $xy \in \mathbb{Q}[x,y]$ has degree $2$ but vanishes at infinitely many points. What survives is not a bound on the number of roots but a statement about grids — product sets $S_1 \times \cdots \times S_n$ — and it constrains the degree in each variable separately.

Lemma 9.2 (Vanishing on a grid). Let $F$ be a field, let $S_1, \ldots, S_n \subseteq F$ be nonempty finite sets, and let $f \in F[x_1,\ldots,x_n]$ satisfy $\deg_{x_i} f < |S_i|$ for every $i$ . If $f(s_1,\ldots,s_n) = 0$ for every $(s_1,\ldots,s_n) \in S_1 \times \cdots \times S_n$ , then $f$ is the zero polynomial.

Proof. Induct on $n$ . For $n = 1$ the hypothesis says $f$ has degree less than $|S_1|$ and at least $|S_1|$ roots, so by Theorem Root bound in one variable it must be zero.

For $n > 1$ , write $f$ as a polynomial in $x_n$ with coefficients in $F[x_1,\ldots,x_{n-1}]$ :

f = \sum_{k=0}^{m} c_k(x_1,\ldots,x_{n-1})\, x_n^{k}, \qquad m = \deg_{x_n} f < |S_n|.

Fix any

(s_1,\ldots,s_{n-1}) \in S_1 \times \cdots \times S_{n-1}

. Substituting it leaves a univariate polynomial in

x_n

of degree at most

m < |S_n|

which vanishes on all of

S_n

, hence is identically zero: every coefficient

c_k(s_1,\ldots,s_{n-1})

0

. As the point was arbitrary, each

c_k

vanishes on the grid

S_1\times\cdots\times S_{n-1}

, and

\deg_{x_i} c_k \le \deg_{x_i} f < |S_i|

, so by induction every

c_k

is the zero polynomial. Hence

f = 0

.∎

Pitfall. The hypothesis is on $\deg_{x_i} f$ , the degree in each variable separately, never on the total degree. The polynomial $x_1 x_2 \cdots x_n$ has total degree $n$ , which may dwarf $|S_i| = 2$ , yet its degree in each variable is $1 < 2$ — and indeed it does not vanish on all of $\{0,1\}^n$ .

The lemma is already useful, but it is an all-or-nothing statement: a polynomial vanishing everywhere on a large enough grid is zero. Alon's Combinatorial Nullstellensatz is the quantitative refinement. It replaces " $f$ is nonzero" by a check on one coefficient, and in exchange it lets the grid be much smaller in the directions where the exponent is small.

Theorem 9.3 (Combinatorial Nullstellensatz). (Alon, 1999.) Let $F$ be a field and let $f \in F[x_1,\ldots,x_n]$ be a polynomial of total degree $\deg f = d_1 + \cdots + d_n$ , where $d_1,\ldots,d_n$ are non-negative integers. Suppose the coefficient of the monomial $x_1^{d_1}\cdots x_n^{d_n}$ in $f$ is nonzero. Then for any subsets $S_1,\ldots,S_n \subseteq F$ with $|S_i| > d_i$ for every $i$ , there exist $s_1 \in S_1, \ldots, s_n \in S_n$ with

f(s_1,\ldots,s_n) \neq 0.

Two hypotheses carry the theorem and both are easy to misread. First, $x_1^{d_1}\cdots x_n^{d_n}$ must be a top-degree monomial: its exponents are required to sum to the total degree of $f$ , so it is one of the monomials of maximal degree, not any monomial one pleases. Second, the sets must beat the exponents coordinatewise, $|S_i| > d_i$ ; there is no condition relating $|S_i|$ to $\deg f$ .

Proof. Shrinking the $S_i$ only makes the conclusion stronger, so assume $|S_i| = d_i + 1$ exactly. Suppose, for contradiction, that $f$ vanishes at every point of $S_1 \times \cdots \times S_n$ .

For each $i$ put

g_i(x_i) = \prod_{s \in S_i}(x_i - s) = x_i^{d_i+1} - \sum_{j=0}^{d_i} g_{ij}\,x_i^{\,j},

a monic polynomial of degree

d_i + 1

vanishing exactly on

S_i

. The displayed identity lets us rewrite $x_i^{d_i+1}$ as a combination of lower powers of $x_i$ , at the cost of adding a multiple of

g_i

Apply that rewriting repeatedly to $f$ : whenever a monomial of the current polynomial contains $x_i^{e}$ with $e > d_i$ , replace that occurrence of $x_i^{d_i+1}$ by $\sum_j g_{ij}x_i^{\,j}$ , which amounts to subtracting a multiple of $g_i$ whose cofactor has degree at most $\deg f - d_i - 1$ . Each step strictly decreases the total degree of the term it rewrites, so the process terminates, and it produces polynomials $h_1,\ldots,h_n$ and a polynomial $\bar f$ with

f = \sum_{i=1}^{n} h_i\,g_i + \bar f, \qquad \deg(h_i g_i) \le \deg f, \qquad \deg_{x_i}\bar f \le d_i \ \text{ for every } i.

Every $g_i$ vanishes on $S_i$ , so $\sum_i h_i g_i$ vanishes on the whole grid; since $f$ does too, $\bar f$ vanishes on the grid. As $\deg_{x_i}\bar f \le d_i < |S_i|$ , Lemma Vanishing on a grid forces $\bar f = 0$ .

Now compare the coefficient of $x_1^{d_1}\cdots x_n^{d_n}$ on the two sides of $f = \sum_i h_i g_i + \bar f$ . That monomial has degree $\deg f$ , the largest degree occurring anywhere in the identity, so only top-degree homogeneous parts can contribute to it. The top-degree part of $h_i g_i$ is (top-degree part of $h_i$ ) times $x_i^{d_i+1}$ , every monomial of which is divisible by $x_i^{d_i+1}$ and therefore has degree at least $d_i + 1$ in $x_i$ — so none of them equals $x_1^{d_1}\cdots x_n^{d_n}$ , whose degree in $x_i$ is $d_i$ . Hence each $h_i g_i$ contributes $0$ , and $\bar f = 0$ contributes $0$ , so the coefficient of $x_1^{d_1}\cdots x_n^{d_n}$ in $f$ is $0$ — contradicting the hypothesis.∎

Intuition. Think of the grid $S_1\times\cdots\times S_n$ as a box of sample points and of $f$ as a signal measured on it. The rewriting step in the proof is reduction modulo the box: any polynomial can be replaced, without changing a single one of its values on the box, by one whose degree in $x_i$ is below $|S_i|$ — the visible part of the signal. The grid lemma says the visible part is determined by the values, so a signal that is zero everywhere on the box has zero visible part. The Nullstellensatz adds one observation: reduction can never disturb a top-degree coefficient whose exponents already sit below the box dimensions. That coefficient is visible, so if it is nonzero the signal is not identically zero on the box.

Example 9.4 (The theorem in one variable). Take $n = 1$ and $f$ of degree $d$ with leading coefficient $c \neq 0$ . What does the Combinatorial Nullstellensatz say?

Solution. The only top-degree monomial is $x^d$ , so $d_1 = d$ and the coefficient condition is exactly $c \neq 0$ , which holds. The conclusion is: for any $S$ with $|S| > d$ there is $s \in S$ with $f(s) \neq 0$ .

That is a restatement of Theorem Root bound in one variable — $f$ has at most $d$ roots, so it cannot vanish on a set of more than $d$ elements. The Combinatorial Nullstellensatz is precisely the multivariate generalisation of the root bound, and it degenerates to it.□

Example 9.5 (Choosing the grid). Let $f(x,y) = x^{2}y - xy + 3$ over $\mathbb{Q}$ . Which grids does the theorem apply to, and what does it promise?

Solution. The total degree is $3$ . The monomial $x^{2}y$ has exponents summing to $2 + 1 = 3 = \deg f$ , so it is top-degree, and its coefficient is $1 \neq 0$ . Take $d_1 = 2$ , $d_2 = 1$ .

The theorem therefore applies to any $S_1$ with $|S_1| \ge 3$ and any $S_2$ with $|S_2| \ge 2$ , and promises a point of $S_1\times S_2$ where $f$ does not vanish. With $S_1 = \{0,1,2\}$ and $S_2 = \{0,1\}$ one such point is easy to exhibit: $f(2,1) = 4 - 2 + 3 = 5 \neq 0$ .

Note what the theorem does not say. The monomial $xy$ has coefficient $-1 \neq 0$ but exponents summing to $2 < 3$ , so it is not top-degree and gives no information; in particular it does not license the smaller grid $|S_1| \ge 2$ , $|S_2| \ge 2$ .□

Pitfall. Over a ring that is not a field the theorem collapses. In $\mathbb{Z}/4\mathbb{Z}$ take $f(x) = 2x^{2} + 2x$ , of degree $2$ with leading coefficient $2 \neq 0$ , and $S = \{0,1,2,3\}$ with $|S| = 4 > 2$ . But $f(x) = 2x(x+1)$ and $x(x+1)$ is always even, so $f$ vanishes at every point of $S$ . What fails is the root bound: $2x^{2}+2x$ is a nonzero quadratic with four roots, which a field forbids.

Remark. The theorem is purely existential. It certifies that a good point exists in the grid without producing one, and the proof suggests no search better than inspecting the grid. This is the same trade the probabilistic method makes, and as there, turning the existence proof into a construction is a separate and usually harder problem.

Exercises for §9.1 →

9.2The Polynomial Method

The Combinatorial Nullstellensatz is one instrument; the polynomial method is the technique it belongs to. The technique has a fixed shape, and once seen it is recognisable in arguments that otherwise look unrelated.

Method 9.6 (The polynomial method).

Encode. Choose a polynomial $f$ whose vanishing at a point of some grid means "this configuration is bad", so that a nonvanishing point is the object to be produced. Alternatively, choose $f$ to vanish on a set suspected of being small.
Bound the degree. Count how large $\deg f$ can be, either from the construction or by interpolation: the space of polynomials in $n$ variables of total degree at most $D$ has dimension $\binom{D+n}{n}$ , so any set of fewer than $\binom{D+n}{n}$ points carries a nonzero polynomial of degree at most $D$ vanishing on it.
Spend the rigidity. Either identify a top-degree monomial with nonzero coefficient and apply the Combinatorial Nullstellensatz, or restrict $f$ to a line and apply the root bound in one variable.
Conclude. A polynomial with more roots than its degree allows is zero; if the construction says it is nonzero, the contradiction is the combinatorial theorem.

Step 2 is where the size of the combinatorial object enters, and step 3 is where the rigidity of polynomials is spent. The rest of this section runs the recipe three times, on problems that share no combinatorial content whatever.

Counting solutions modulo $p$

The first application uses no Nullstellensatz at all — only the root bound and one character-sum identity — and it shows the method in its plainest form.

Lemma 9.7 (Power sums over a finite field). Let $F_q$ be the field with $q$ elements, of characteristic $p$ , and let $k \ge 0$ be an integer. Then, with the convention $0^0 = 1$ ,

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

Proof. If $k = 0$ the sum is $q \cdot 1 = 0$ , since $q$ is a power of the characteristic.

If $k > 0$ then $0^k = 0$ and the sum runs effectively over $F_q^{\times}$ , a cyclic group of order $q-1$ . If $(q-1) \mid k$ then $t^k = 1$ for every $t \neq 0$ , so the sum is $q - 1 = -1$ . Otherwise pick a generator $g$ of $F_q^\times$ , so that $g^k \neq 1$ . Multiplying the summation index by $g$ permutes $F_q^{\times}$ , so $S = \sum_{t \neq 0} t^k$ satisfies $g^k S = S$ , whence $(g^k - 1)S = 0$ and $S = 0$ .∎

Theorem 9.8 (Chevalley–Warning). Let $F_q$ have characteristic $p$ and let $f_1,\ldots,f_m \in F_q[x_1,\ldots,x_n]$ satisfy

\deg f_1 + \cdots + \deg f_m < n.

Then the number

N

of common zeros of

f_1,\ldots,f_m

F_q^{\,n}

is divisible by

p

. In particular (Chevalley's theorem) if every

f_j

has zero constant term, so that the origin is a common zero, there is a second, nonzero common zero.

Proof. Set

P(x_1,\ldots,x_n) = \prod_{j=1}^{m}\bigl(1 - f_j(x)^{\,q-1}\bigr).

For

x \in F_q^n

: if

f_j(x) = 0

for every

j

then every factor is

1

and

P(x) = 1

; if some

f_j(x) \neq 0

then

f_j(x)^{q-1} = 1

because

F_q^{\times}

has order

q-1

, that factor is

0

, and

P(x) = 0

. So

P

is the indicator function of the common zero set, and summing over the whole space gives, as an element of

F_q

\sum_{x \in F_q^{n}} P(x) = N \cdot 1 = N \bmod p .

Now bound the degree: $\deg P = (q-1)\sum_j \deg f_j < (q-1)n$ . It therefore suffices to show that every monomial $x_1^{k_1}\cdots x_n^{k_n}$ with $k_1 + \cdots + k_n < (q-1)n$ sums to zero over $F_q^n$ . The sum factors,

\sum_{x \in F_q^n} x_1^{k_1}\cdots x_n^{k_n} = \prod_{i=1}^{n}\Bigl(\sum_{t \in F_q} t^{k_i}\Bigr),

and since

\sum_i k_i < (q-1)n

some

k_i

is strictly less than

q-1

. For that

i

, Lemma Power sums over a finite field gives

\sum_t t^{k_i} = 0

: the exceptional case needs

k_i > 0

and

(q-1) \mid k_i

, impossible for

0 < k_i < q-1

, while

k_i = 0

also gives

0

. So the product vanishes.

Hence $N = 0$ in $F_q$ , which says $p \mid N$ . For the last sentence, $N \ge 1$ because the origin is a common zero, and $p \mid N$ then forces $N \ge p \ge 2$ .∎

Example 9.9 (Erdős–Ginzburg–Ziv for a prime). Prove that among any $2p-1$ integers, $p$ prime, some $p$ of them have a sum divisible by $p$ .

Solution. Work in $F_p$ and let $a_1,\ldots,a_{2p-1}$ be the residues. Introduce $n = 2p-1$ variables and the two polynomials

f_1 = \sum_{i=1}^{2p-1} x_i^{\,p-1}, \qquad f_2 = \sum_{i=1}^{2p-1} a_i\,x_i^{\,p-1}.

Both have degree

p-1

and zero constant term, and

\deg f_1 + \deg f_2 = 2(p-1) = 2p - 2 < 2p-1 = n,

so Theorem Chevalley–Warning supplies a common zero

x \neq 0

By Fermat's little theorem $x_i^{p-1} \in \{0,1\}$ , equal to $1$ exactly when $x_i \neq 0$ . Let $I = \{i : x_i \neq 0\}$ , which is nonempty. Then $f_1(x) = |I| \bmod p = 0$ , so $p$ divides $|I|$ ; since $1 \le |I| \le 2p-1$ , this forces $|I| = p$ . And $f_2(x) = \sum_{i \in I} a_i = 0$ in $F_p$ , so those $p$ integers sum to a multiple of $p$ . $\checkmark$

The count $2p-1$ cannot be lowered: take $p-1$ copies of $0$ and $p-1$ copies of $1$ . Among these $2p-2$ numbers, any $p$ of them have a sum strictly between $0$ and $p$ , hence never divisible by $p$ .□

Kakeya sets over a finite field

The next application is Dvir's 2008 solution of the finite field Kakeya problem — a question that had resisted analytic attack for a decade and fell to a page of the polynomial method, using nothing beyond Lemma Vanishing on a grid.

Definition 9.10 (Kakeya set). A set $K \subseteq F_q^{\,n}$ is a Kakeya set if for every direction $b \in F_q^{\,n}\setminus\{0\}$ there is a point $a \in F_q^{\,n}$ with the whole line $\{a + tb : t \in F_q\}$ contained in $K$ .

A Kakeya set contains a line in each of the $(q^n-1)/(q-1)$ directions, so it certainly has at least about $q^{n-1}$ points; the question is whether those lines can be packed so as to overlap heavily, keeping $|K|$ near that bound. They cannot: $K$ must have nearly the full dimension $n$ .

Theorem 9.11 (Dvir's theorem). Every Kakeya set $K \subseteq F_q^{\,n}$ satisfies

|K| \ \ge\ \binom{q + n - 1}{n} \ \ge\ \frac{q^{\,n}}{n!}.

Proof. Suppose $|K| < \binom{q+n-1}{n}$ . The space of polynomials in $F_q[x_1,\ldots,x_n]$ of total degree at most $q-1$ has dimension $\binom{q-1+n}{n} = \binom{q+n-1}{n}$ , a basis being the monomials $x_1^{k_1}\cdots x_n^{k_n}$ with $\sum_i k_i \le q-1$ . Requiring such a polynomial to vanish at each point of $K$ imposes $|K|$ homogeneous linear conditions on its coefficients, and there are more unknowns than conditions, so a nonzero $g$ of some degree $d \le q-1$ exists with $g$ vanishing on $K$ .

Note $d \ge 1$ , since a nonzero constant does not vanish on the nonempty set $K$ . Write $g = g_d + (\text{terms of degree} < d)$ with $g_d$ the homogeneous part of degree $d$ , nonzero by the definition of $d$ .

Fix a direction $b \neq 0$ and a line $\{a + tb : t \in F_q\} \subseteq K$ . The univariate polynomial $t \mapsto g(a + tb)$ has degree at most $d \le q-1$ and vanishes at all $q$ values $t \in F_q$ , so by Theorem Root bound in one variable it is identically zero. Its coefficient of $t^{d}$ is $g_d(b)$ — only the degree- $d$ part of $g$ can produce $t^d$ , and it produces exactly $g_d(b)\,t^d$ . Hence $g_d(b) = 0$ .

This holds for every $b \neq 0$ , and $g_d(0) = 0$ as well because $g_d$ is homogeneous of degree $d \ge 1$ . So $g_d$ vanishes on all of $F_q^{\,n}$ . But $\deg_{x_i} g_d \le d \le q-1 < q = |F_q|$ for each $i$ , so Lemma Vanishing on a grid, applied with every $S_i = F_q$ , gives $g_d = 0$ — a contradiction.

For the second inequality, $\binom{q+n-1}{n} = \frac{(q+n-1)(q+n-2)\cdots q}{n!} \ge \frac{q^n}{n!}$ , since each of the $n$ factors in the numerator is at least $q$ .∎

Intuition. The contradiction is a tug of war over a single polynomial. Making $K$ small makes it easy to find a low-degree polynomial vanishing on $K$ : few constraints, many coefficients. But a Kakeya set contains a line in every direction, and a polynomial that dies on a whole line dies, at top order, in that direction — its leading form vanishes at the direction vector. Lines in every direction kill the leading form everywhere, and a form vanishing everywhere on a grid as large as $F_q^n$ is zero. So $K$ cannot be small and be a Kakeya set at the same time.

The cap set problem

The third application is stated, not proved, because its proof introduces machinery this chapter does not develop.

Definition 9.12 (Cap set). A cap set is a subset $A \subseteq \mathbb{F}_3^{\,n}$ containing no three-term arithmetic progression of distinct elements — equivalently, no three distinct $x,y,z \in A$ with $x+y+z = 0$ , since in characteristic $3$ the progression condition $x + z = 2y$ is the same as $x + y + z = 0$ .

Theorem 9.13 (Ellenberg–Gijswijt). There is a constant $c < 3$ , and one may take $c = 2.756$ , such that every cap set $A \subseteq \mathbb{F}_3^{\,n}$ satisfies $|A| \le c^{\,n}$ for all sufficiently large $n$ . In the other direction, cap sets of size at least $2.217^{\,n}$ exist.

Proof. Sketch only. The full argument is beyond this chapter. It is a polynomial-method argument of a different flavour from the two above. Croot, Lev and Pach observed that if $A$ is progression-free then the indicator of $x + y \in -A$ , restricted to $A \times A$ , is supported on the diagonal, and that this function agrees with a polynomial of degree at most $2n$ because every coordinate of $\mathbb{F}_3^n$ satisfies $x_i^{3} = x_i$ . Ellenberg and Gijswijt made the counting work by measuring such a function not by its matrix rank but by its slice rank: the least number of terms needed to write it as a sum of products, each a function of one variable times a function of the remaining ones. The two facts the argument rests on are that a function supported exactly on the diagonal of $A \times A$ has slice rank $|A|$ , and that a polynomial of degree at most $d$ has slice rank at most three times the number of monomials of degree at most $d/3$ . Comparing the two counts at $d = 2n$ produces the exponential saving.∎

Remark. The corresponding question over $\mathbb{Z}$ — must a subset of $\{1,\ldots,N\}$ with no three-term progression have size $o(N)$ ? — is Roth's theorem, discussed at the end of this chapter. It is not a polynomial-method result, and the $\mathbb{F}_3^n$ case is easier precisely because the ambient group is full of subgroups and because $x^{3} = x$ holds identically on it.

Exercises for §9.2 →

9.3Applications of the Nullstellensatz

The Nullstellensatz is used by writing down a polynomial whose nonvanishing is the thing to be proved, and then hunting for a top-degree monomial whose coefficient can be shown nonzero. That second step is where the combinatorics lives: the coefficient is almost always a signed count of some family of combinatorial objects, and proving it nonzero is proving that two such families have different sizes. This section carries out the hunt three times — for graph colourings, for restricted sumsets, and for regular subgraphs.

List colouring and the graph polynomial

Definition 9.14 (Graph polynomial). Let $G$ be a graph on the vertex set $\{v_1,\ldots,v_n\}$ with a fixed ordering. Its graph polynomial is

f_G(x_1,\ldots,x_n) = \prod_{\substack{v_iv_j \in E(G) \\ i < j}} (x_i - x_j),

a homogeneous polynomial of degree

|E(G)|

The point of the definition is a translation: assigning colour $x_i$ to vertex $v_i$ gives a proper colouring exactly when no factor vanishes, that is, when $f_G \neq 0$ at that point. So a proper colouring out of prescribed lists $S_1,\ldots,S_n$ is precisely a nonvanishing point of $f_G$ on the grid $S_1\times\cdots\times S_n$ — the exact conclusion the Nullstellensatz delivers.

Definition 9.15 (List chromatic number). $G$ is $k$ -choosable if for every assignment of lists $S_v$ with $|S_v| = k$ to the vertices there is a proper colouring with each $c(v) \in S_v$ . The least such $k$ is the list chromatic number $\mathrm{ch}(G)$ .

Choosability is strictly harder than colourability: $K_{3,3}$ is $2$ -colourable but not $2$ -choosable. The Nullstellensatz gives a sufficient condition for choosability that is blind to the distinction, because it never looks at the lists — only at their sizes.

Lemma 9.16 (Coefficients of the graph polynomial count orientations). Let $D$ be an orientation of $G$ with outdegrees $d^{+}(v_1),\ldots,d^{+}(v_n)$ . Then, up to sign, the coefficient of $x_1^{d^{+}(v_1)}\cdots x_n^{d^{+}(v_n)}$ in $f_G$ equals $|\mathcal{E}\mathcal{E}(D)| - |\mathcal{E}\mathcal{O}(D)|$ , the number of Eulerian sub-digraphs of $D$ with an even number of edges minus the number with an odd number of edges. (A sub-digraph is Eulerian if every vertex has equal in- and outdegree in it.)

Proof. Sketch only. Expanding the product $\prod_{i<j}(x_i - x_j)$ chooses, from each edge, one of its two endpoints, and the monomial produced records how many edges chose each vertex — that is, expansion terms correspond exactly to orientations of $G$ , with the exponent of $x_i$ being an outdegree, and with sign $(-1)^{\#\text{edges reversed}}$ relative to $D$ . Two orientations produce the same monomial precisely when they differ on a set of edges forming an Eulerian sub-digraph of $D$ , since reversing a set of edges preserves every outdegree exactly when that set is Eulerian. Grouping the expansion by monomial and tracking the signs turns the coefficient into the even-minus-odd count. The full proof is a bookkeeping argument on those signs and is omitted.∎

Theorem 9.17 (Alon–Tarsi). Let $D$ be an orientation of $G$ in which the number of even Eulerian sub-digraphs differs from the number of odd ones. Then $G$ is colourable from any lists with $|S_v| \ge d^{+}(v) + 1$ for every vertex $v$ . In particular, if such an orientation has maximum outdegree $k-1$ , then $G$ is $k$ -choosable.

Proof. Put $d_i = d^{+}(v_i)$ . The graph polynomial $f_G$ is homogeneous of degree $|E| = \sum_i d^{+}(v_i) = \sum_i d_i$ , so the monomial $\prod_i x_i^{d_i}$ is top-degree, and by Lemma Coefficients of the graph polynomial count orientations its coefficient is $\pm(|\mathcal{E}\mathcal{E}(D)| - |\mathcal{E}\mathcal{O}(D)|) \neq 0$ by hypothesis. (Working over a field of characteristic $0$ , or of characteristic larger than that difference, keeps it nonzero there too.)

Given lists with $|S_v| \ge d^{+}(v) + 1 > d_v$ , Theorem Combinatorial Nullstellensatz produces a point of $\prod_v S_v$ at which $f_G \neq 0$ . No factor $x_i - x_j$ vanishes there, so adjacent vertices received different colours: it is a proper colouring from the lists.∎

Example 9.18 (The four-cycle is $2$ -choosable at two of its vertices). Take $C_4$ with vertices $1,2,3,4$ in cyclic order. Show directly, from the Nullstellensatz, that $C_4$ can be coloured whenever vertices $1$ and $3$ have lists of size $3$ and vertices $2$ and $4$ have nonempty lists.

Solution. The graph polynomial is $f = (x_1-x_2)(x_2-x_3)(x_3-x_4)(x_1-x_4)$ , homogeneous of degree $4$ .

Look for the coefficient of $x_1^2x_3^2$ : exponents $d_1 = d_3 = 2$ , $d_2 = d_4 = 0$ , summing to $4 = \deg f$ , so it is top-degree. To produce $x_1^2x_3^2$ the expansion must take $x_1$ from both factors containing $x_1$ and $x_3$ from both factors containing $x_3$ ; that is a single expansion term. Reading it off factor by factor — $(x_1-x_2)\to x_1$ , $(x_2-x_3)\to -x_3$ , $(x_3-x_4) \to x_3$ , $(x_1-x_4)\to x_1$ — the signs multiply to $(+1)(-1)(+1)(+1) = -1$ , so the coefficient is $-1 \neq 0$ .

The Nullstellensatz now needs $|S_1| > 2$ , $|S_3| > 2$ , $|S_2| > 0$ , $|S_4| > 0$ , which is the hypothesis. It returns a point where $f \neq 0$ , that is, a proper colouring. $\checkmark$

The choice of monomial was not free: the coefficient of $x_1^2x_2^2$ , sitting on an adjacent pair, is $0$ , because no expansion term can take $x_1$ twice and $x_2$ twice from these four factors — the factor $(x_1-x_2)$ can only supply one of them. A monomial with zero coefficient carries no information, which is why the search for the right one is the real work in every application.□

The Erdős–Heilbronn problem

Cauchy–Davenport, proved in the next section, bounds $|A+B|$ where all pairs $(a,b)$ are allowed. Erdős and Heilbronn conjectured in 1964 that forbidding $a = b$ costs only two elements. The conjecture stood for thirty years and was proved by Dias da Silva and Hamidoune with linear algebra; the Nullstellensatz proof below, due to Alon, Nathanson and Ruzsa, is the argument that made the result routine.

Definition 9.19 (Restricted sumset). For $A$ in an abelian group, the restricted sumset is

A \,\hat{+}\, A = \{\,a + a' \ :\ a, a' \in A,\ a \neq a'\,\}.

Theorem 9.20 (Erdős–Heilbronn). Let $p$ be a prime and $A \subseteq \mathbb{Z}/p\mathbb{Z}$ nonempty. Then

|A \,\hat{+}\, A| \ \ge\ \min\bigl(p,\ 2|A| - 3\bigr).

Proof. Write $k = |A|$ . For $k = 1$ the restricted sumset is empty and $2k-3 = -1$ , so there is nothing to prove; assume $k \ge 2$ .

Main case: $2k - 3 \le p$ . Suppose for contradiction that $|A\,\hat{+}\,A| \le 2k-4$ . Choose $C \subseteq \mathbb{Z}/p\mathbb{Z}$ with $A\,\hat+\,A \subseteq C$ and $|C| = 2k-4$ , possible since $2k - 4 < p$ . Define

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

For any

a, a' \in A

: if

a = a'

the first factor vanishes, and if

a \neq a'

then

a + a' \in A\,\hat+\,A \subseteq C

and one of the other factors vanishes. So

f

vanishes on the whole grid

A \times A

Consider the monomial $x^{k-1}y^{k-2}$ , whose exponents sum to $2k-3 = \deg f$ : it is top-degree, so its coefficient in $f$ is its coefficient in the top-degree part $(x-y)(x+y)^{2k-4}$ . Expanding,

[x^{k-1}y^{k-2}]\,(x-y)(x+y)^{2k-4} = \binom{2k-4}{k-2} - \binom{2k-4}{k-1},

the first term taking

x

from the linear factor and

x^{k-2}y^{k-2}

from the power, the second taking

-y

and

x^{k-1}y^{k-3}

. Since

\binom{2k-4}{k-1} = \frac{k-2}{k-1}\binom{2k-4}{k-2}

, the difference equals

\binom{2k-4}{k-2}\Bigl(1 - \frac{k-2}{k-1}\Bigr) = \frac{1}{k-1}\binom{2k-4}{k-2},

which is the Catalan number

C_{k-2}

, in particular a positive integer. Is it nonzero modulo

p

? Write

(k-1)\,C_{k-2} = \binom{2k-4}{k-2}

. Every factor of

(2k-4)!

and of

(k-2)!

is at most

2k-4 < p

, so

\binom{2k-4}{k-2}

is a ratio of integers none of whose prime factors is

p

; hence it is nonzero mod

p

. And

0 < k - 1 < p

, so

k-1

is invertible mod

p

. Therefore

C_{k-2} \neq 0

\mathbb{Z}/p\mathbb{Z}

Apply Theorem Combinatorial Nullstellensatz with $d_1 = k-1$ , $d_2 = k-2$ and $S_1 = S_2 = A$ : indeed $|A| = k > k-1$ and $|A| = k > k-2$ . It yields $a, a' \in A$ with $f(a,a') \neq 0$ , contradicting the vanishing established above. So $|A\,\hat+\,A| \ge 2k-3$ .

Boundary case: $2k-3 > p$ , $p$ odd. Then $k > (p+3)/2$ , and $(p+3)/2$ is an integer, so $A$ has a subset $A'$ with $|A'| = (p+3)/2$ . The main case applies to $A'$ , since $2|A'|-3 = p$ , and gives $|A\,\hat+\,A| \ge |A'\,\hat+\,A'| \ge p$ . For $p = 2$ the claim reads $|A\,\hat+\,A| \ge \min(2, 2k-3)$ , which is checked directly on the four subsets of $\mathbb{Z}/2\mathbb{Z}$ .∎

Example 9.21 (The bound is attained). Take $A = \{0,1,2,3\} \subseteq \mathbb{Z}/11\mathbb{Z}$ . Compare $|A \hat+ A|$ with the bound.

Solution. The distinct pairs give sums $0{+}1 = 1$ , $0{+}2 = 2$ , $0{+}3 = 3$ , $1{+}2 = 3$ , $1{+}3 = 4$ , $2{+}3 = 5$ , so $A \hat+ A = \{1,2,3,4,5\}$ and $|A\hat+A| = 5$ .

The theorem promises $\min(11,\ 2\cdot 4 - 3) = 5$ . The bound is attained exactly. $\checkmark$ The same computation for any arithmetic progression $A$ of length $k$ gives $|A\hat+A| = 2k-3$ as long as $2k-3 \le p$ , which is why the $-3$ cannot be improved: the unrestricted sumset of a progression has $2k-1$ elements, and deleting the two sums $2a_1$ and $2a_k$ — attainable only by $a + a$ — removes exactly two of them.□

Regular subgraphs

The last application returns to Chevalley–Warning, and shows how a divisibility theorem about equations becomes a structure theorem about graphs.

Theorem 9.22 (Alon–Friedland–Kalai). Every loopless $4$ -regular multigraph with one additional edge added contains a $3$ -regular subgraph.

Proof. Let $G$ have vertex set $V$ , $|V| = n$ , and edge set $E$ . Since $G$ is $4$ -regular plus one edge, $|E| = 2n + 1$ , and every vertex has degree $4$ or $5$ .

Work over $\mathbb{F}_3$ with one variable $x_e$ per edge, and for each vertex $v$ set

f_v = \sum_{e \ni v} x_e^{\,2}, \qquad \deg f_v = 2 .

There are

n

such polynomials, each with zero constant term, and

\sum_{v} \deg f_v = 2n < 2n+1 = |E|,

which is the number of variables. Theorem Chevalley–Warning therefore gives a common zero

x \neq 0

Let $H$ be the subgraph with edge set $\{e : x_e \neq 0\}$ , which is nonempty. In $\mathbb{F}_3$ every nonzero element squares to $1$ , so for each $v$ ,

0 = f_v(x) = \#\{e \ni v : x_e \neq 0\} = \deg_H(v) \pmod 3 .

Thus

3 \mid \deg_H(v)

for every

v

, while

\deg_H(v) \le \deg_G(v) \le 5

. Hence

\deg_H(v) \in \{0, 3\}

for every vertex. Deleting the isolated vertices of

H

leaves a nonempty

3

-regular subgraph.∎

Intuition. The square in $f_v$ is doing all the work. A linear form $\sum_{e\ni v}x_e$ would have said nothing about how many edges are chosen, only about a weighted sum; squaring turns every chosen edge into a $1$ regardless of its value, so the equation literally reads "the degree in $H$ is divisible by $3$ ". Chevalley–Warning then only has to beat the degree budget $2n < |E|$ — and that is why a single extra edge, which raises $|E|$ from $2n$ to $2n+1$ , is exactly what the theorem needs.

Remark. The Nullstellensatz has a long application list beyond these: zero-sum problems and the Davenport constant, the existence of orthogonal Latin squares, hyperplane coverings of the cube, and the Alon–Füredi theorem on the number of points a hypersurface must miss. In almost all of them the difficulty is the same one seen above — proving that a specific coefficient is nonzero.

Exercises for §9.3 →

9.4Sumsets and the Elementary Bounds

The second half of the chapter changes subject. Let $G$ be an abelian group, written additively, and let $A, B \subseteq G$ be finite and nonempty. The question is entirely elementary to state and surprisingly deep to answer: how small can $A + B$ be?

Definition 9.23 (Sumset, difference set, dilate).

A + B = \{a + b : a \in A,\ b \in B\}, \qquad A - B = \{a - b : a \in A,\ b \in B\}.

Write

hA = A + A + \cdots + A

(

h

summands) for the $h$ -fold sumset, and

\lambda \cdot A = \{\lambda a : a \in A\}

for the dilate.

Pitfall. $2A$ and $2\cdot A$ are different sets, and the notation is standard enough that it must simply be learnt. For $A = \{0,1\}$ in $\mathbb{Z}$ : $2A = A + A = \{0,1,2\}$ has three elements while $2\cdot A = \{0,2\}$ has two. In general $2 \cdot A \subseteq 2A$ and the containment is usually strict — indeed $|2\cdot A| = |A|$ always (in a torsion-free group), while $|2A|$ grows.

Proposition 9.24 (Trivial bounds). For finite nonempty $A, B$ in an abelian group,

\max(|A|, |B|) \ \le\ |A + B| \ \le\ |A|\,|B| .

Proof. For the upper bound, $A+B$ is the image of the map $A \times B \to G$ , $(a,b)\mapsto a+b$ , so it has at most $|A||B|$ elements. For the lower bound, fix $b_0 \in B$ ; the translates $a + b_0$ for $a \in A$ are $|A|$ distinct elements of $A+B$ , so $|A+B| \ge |A|$ , and symmetrically $|A+B| \ge |B|$ .∎

Both bounds are attained. The upper bound holds with equality when all $|A||B|$ sums are distinct, which is the generic situation for random sets. The lower bound is attained too, and understanding when is the beginning of the whole theory.

Example 9.25 (The lower bound is attained). Exhibit sets in an abelian group with $|A+B| = \max(|A|,|B|)$ .

Solution. Let $H$ be a finite subgroup of $G$ and take $B = H$ and $A$ any union of cosets of $H$ . Then $A + H = A$ , since each coset absorbs $H$ , so $|A+B| = |A| = \max(|A|,|B|)$ whenever $|A| \ge |H|$ .

Concretely, in $\mathbb{Z}/6\mathbb{Z}$ take $A = B = \{0,2,4\}$ . Then $A + B = \{0,2,4\} = A$ , of size $3$ , though $|A| + |B| - 1 = 5$ .

This one example is the reason every theorem in this half of the chapter carries a hypothesis: torsion-freeness in $\mathbb{Z}$ , primality in $\mathbb{Z}/p\mathbb{Z}$ , or an explicit stabiliser term. A subgroup is a set that does not grow when added to itself, and no theorem can outlaw it.□

In $\mathbb{Z}$ , where there are no subgroups other than $\{0\}$ and infinite ones, the truth is as clean as it could be.

Theorem 9.26 (The elementary sumset bound). Let $A, B$ be finite nonempty subsets of $\mathbb{Z}$ , or of any torsion-free abelian group. Then

|A + B| \ \ge\ |A| + |B| - 1 .

Proof. A torsion-free abelian group admits a linear order compatible with addition, so it is enough to argue in $\mathbb{Z}$ (order the finitely many elements involved and relabel). Write $A = \{a_1 < a_2 < \cdots < a_m\}$ and $B = \{b_1 < b_2 < \cdots < b_n\}$ . The $m + n - 1$ sums

a_1 + b_1 < a_1 + b_2 < \cdots < a_1 + b_n < a_2 + b_n < \cdots < a_m + b_n

form a strictly increasing chain — each step increases either the

B

-term or the

A

-term — so they are distinct elements of

A+B

. Hence

|A+B| \ge m + n - 1

.∎

Figure 9.27. The chain of distinct sums for

A = \{0,1,3\}

and

B = \{0,2,5\}

. The proof walks up the left column and then along the top row, and every step strictly increases

a + b

(the number written beside each point), so the

|A| + |B| - 1 = 5

points visited carry

5

distinct sums. Any monotone staircase from the bottom-left to the top-right corner does as well, which is why the bound is forced by nothing more than the ordering.

Intuition. The chain is the whole proof, and it explains the shape of the answer. To keep $A+B$ small one wants many coincidences $a + b = a' + b'$ , that is, $a - a' = b' - b$ : the two sets must repeat each other's gaps. Two arithmetic progressions with the same common difference repeat every gap, and they are the only sets that do so perfectly — which is exactly the equality case below.

Lemma 9.28 (Equality against a two-element set). Let $A \subseteq \mathbb{Z}$ be finite with $|A| = m \ge 1$ and let $B = \{0, d\}$ with $d > 0$ . Then $|A + B| = m + 1$ if and only if $A$ is an arithmetic progression with common difference $d$ .

Proof. $A + B = A \cup (A + d)$ , so by inclusion–exclusion

|A+B| = 2m - |A \cap (A+d)| .

Thus

|A+B| = m+1

if and only if

|A \cap (A+d)| = m - 1

, that is, all but one element of

A

lies in

A + d

Suppose that holds and write $A = \{a_1 < \cdots < a_m\}$ . The element $a_1$ cannot lie in $A+d$ (it would force a smaller element $a_1 - d \in A$ ), so it is the unique exception, and $a_2,\ldots,a_m \in A + d$ . Hence for each $i \ge 2$ there is a unique $\varphi(i)$ with $a_i = a_{\varphi(i)} + d$ , and $\varphi(i) < i$ since $d > 0$ . So $\varphi$ maps $\{2,\ldots,m\}$ into $\{1,\ldots,m-1\}$ , two sets of the same size, and it is injective (distinct $a_i$ give distinct $a_i - d$ ), hence a bijection; it is strictly increasing because $i \mapsto a_i - d$ is. The only strictly increasing bijection between those two sets is $\varphi(i) = i - 1$ . So $a_i - a_{i-1} = d$ for all $i$ , and $A$ is an arithmetic progression of difference $d$ .

Conversely, if $A$ is such a progression then $A \cap (A+d) = A \setminus \{a_1\}$ has $m-1$ elements, giving $|A+B| = m+1$ .∎

Theorem 9.29 (Equality in the elementary bound). Let $A, B \subseteq \mathbb{Z}$ be finite with $|A|, |B| \ge 2$ . Then $|A+B| = |A| + |B| - 1$ if and only if $A$ and $B$ are arithmetic progressions with the same common difference.

Proof. Sketch only for the forward direction. The converse is a computation: if $A = \{a, a+d, \ldots, a+(m-1)d\}$ and $B = \{b, b+d,\ldots,b+(n-1)d\}$ then $A + B = \{a+b, a+b+d, \ldots, a+b+(m+n-2)d\}$ , of size $m+n-1$ .

For the forward direction, the case $|B| = 2$ is Lemma Equality against a two-element set after translating $B$ to $\{0,d\}$ . The general case follows by induction on $|B|$ , or as the extremal case of Freiman's $3k-4$ theorem — stated in the last section of this chapter — which describes all $A$ with $|A+A| \le 3|A|-4$ and in particular pins down the sets achieving $2|A|-1$ . The induction is not hard but it is long, and it is omitted here.∎

Example 9.30 (Failing the equality case). Compute $A + A$ for $A = \{1,2,4\} \subseteq \mathbb{Z}$ and compare with the bound.

Solution. The sums are $1{+}1 = 2$ , $1{+}2 = 3$ , $1{+}4 = 5$ , $2{+}2 = 4$ , $2{+}4 = 6$ , $4{+}4 = 8$ , so $A + A = \{2,3,4,5,6,8\}$ and $|A+A| = 6$ .

The bound gives $|A+A| \ge 2|A| - 1 = 5$ , and the equality case says $5$ is attained only by progressions. Since the gaps of $A$ are $1$ then $2$ , it is not a progression, so strict inequality was forced; $6 > 5$ . $\checkmark$ For contrast $\{1,2,3\}$ gives $\{2,3,4,5,6\}$ , exactly $5$ .□

What replaces Theorem The elementary sumset bound in a group with subgroups is Kneser's theorem, which does not forbid the coset obstruction but measures it.

Theorem 9.31 (Kneser). Let $A, B$ be finite nonempty subsets of an abelian group $G$ and let

H = \{g \in G : g + (A+B) = A+B\}

be the stabiliser of

A + B

, a subgroup of

G

. Then

|A + B| \ \ge\ |A + H| + |B + H| - |H| .

Proof. Sketch only. The standard proof is an induction on $|A| + |B|$ driven by the $e$ -transform: replacing the pair $(A,B)$ by $(A \cup (B+e),\ B \cap (A-e))$ for a suitable $e$ , an operation that preserves the sumset's containment and decreases $|B|$ unless the pair is already stabilised. The induction terminates at a pair where $A$ and $B$ are unions of $H$ -cosets, where the inequality is an identity. It is a page of careful case analysis and is not reproduced here.∎

If $H$ is trivial, Kneser's bound reads $|A+B| \ge |A| + |B| - 1$ — the elementary bound again. The coset example above is the other extreme, where $H = A + B$ itself and the inequality is tight but says nothing. In $\mathbb{Z}/p\mathbb{Z}$ with $p$ prime there are only two subgroups, and that dichotomy is the next section's theorem.

Exercises for §9.4 →

9.5Cauchy–Davenport

The Cauchy–Davenport theorem is where the two halves of this chapter meet. It is the correct analogue of Theorem The elementary sumset bound in a prime cyclic group, it is the oldest theorem in additive combinatorics, and its shortest proof is an application of the Combinatorial Nullstellensatz — one page of algebra replacing a century of transform arguments.

Theorem 9.32 (Cauchy–Davenport). (Cauchy 1813; Davenport 1935.) Let $p$ be prime and let $A, B \subseteq \mathbb{Z}/p\mathbb{Z}$ be nonempty. Then

|A + B| \ \ge\ \min\bigl(p,\ |A| + |B| - 1\bigr).

The $\min$ with $p$ is unavoidable bookkeeping: $A+B$ lives in a group of $p$ elements and cannot be larger. The content is the other branch, and it says that in $\mathbb{Z}/p\mathbb{Z}$ the coset obstruction of the previous section — the only way a sumset can fail to grow — simply does not exist, because the group has no proper nontrivial subgroup.

Lemma 9.33 (Large sets cover the group). If $A, B \subseteq \mathbb{Z}/p\mathbb{Z}$ are nonempty with $|A| + |B| > p$ , then $A + B = \mathbb{Z}/p\mathbb{Z}$ .

Proof. Fix $c \in \mathbb{Z}/p\mathbb{Z}$ . The sets $A$ and $c - B = \{c - b : b \in B\}$ have sizes $|A|$ and $|B|$ with $|A| + |B| > p$ , so they cannot be disjoint inside a group of $p$ elements. Pick $a \in A \cap (c-B)$ ; then $a = c - b$ for some $b \in B$ , so $c = a + b \in A + B$ .∎

Proof. Proof of Cauchy–Davenport. If $|A| + |B| - 1 \ge p$ then $|A| + |B| > p$ and Lemma Large sets cover the group gives $A + B = \mathbb{Z}/p\mathbb{Z}$ , whose size is $p = \min(p, |A|+|B|-1)$ . So assume $|A| + |B| - 1 \le p$ and suppose, for contradiction, that

|A+B| \le |A| + |B| - 2 .

Choose $C \subseteq \mathbb{Z}/p\mathbb{Z}$ with $A + B \subseteq C$ and $|C| = |A| + |B| - 2$ , which is possible because $|A|+|B|-2 < p$ . Set

f(x,y) = \prod_{c \in C}(x + y - c), \qquad \deg f = |A| + |B| - 2 .

For every

a \in A

and

b \in B

the value

a + b

lies in

C

, so one factor vanishes:

f

is zero on the whole grid

A \times B

Now look at the monomial $x^{|A|-1}y^{|B|-1}$ . Its exponents sum to $|A| + |B| - 2 = \deg f$ , so it is top-degree, and its coefficient in $f$ is its coefficient in the top-degree part $(x+y)^{|A|+|B|-2}$ , namely

\binom{|A| + |B| - 2}{|A| - 1} \bmod p .

Because

|A| + |B| - 2 < p

, every factor in the numerator and denominator of that binomial coefficient is a positive integer smaller than

p

, so

p

divides neither; the coefficient is nonzero in

\mathbb{Z}/p\mathbb{Z}

Apply Theorem Combinatorial Nullstellensatz with $d_1 = |A|-1$ , $d_2 = |B|-1$ , $S_1 = A$ , $S_2 = B$ . The size conditions $|A| > |A|-1$ and $|B| > |B|-1$ hold trivially, so there are $a \in A$ , $b \in B$ with $f(a,b) \neq 0$ — contradicting the vanishing on the grid. Therefore $|A+B| \ge |A| + |B| - 1$ .∎

Intuition. Every ingredient in that proof is doing one identifiable job. The product over $C$ encodes the assumption "the sumset is small" as a vanishing condition on a rectangle. The degree of the product is small precisely because $C$ was assumed small. The binomial coefficient is where primality enters — over $\mathbb{Z}/6\mathbb{Z}$ the analogous coefficient can be divisible by the modulus and the argument dies, exactly as it must, since the theorem is false there. And the Nullstellensatz converts "the top coefficient survives" into "the polynomial cannot vanish on this rectangle", which is the contradiction.

Figure 9.34. Why the theorem needs

p

prime. In

\mathbb{Z}/6\mathbb{Z}

the three highlighted residues form the subgroup

\{0,2,4\}

; adding it to itself returns the same three points, so

|A+A| = 3

, far below

2|A| - 1 = 5

. A prime modulus has no such subgroup to hide in, and that single fact is the whole difference between Cauchy–Davenport and its failure in a composite modulus.

Example 9.35 (Sharp and slack). In $\mathbb{Z}/7\mathbb{Z}$ , compare the bound with the truth for two choices of $A$ and $B$ .

Solution. Slack. Take $A = \{0,1,3\}$ and $B = \{0,2\}$ . Then

A + B = \{0,1,3\} \cup \{2,3,5\} = \{0,1,2,3,5\},

|A+B| = 5

, while the bound promises only

\min(7, 3+2-1) = 4

. The sets are not progressions with a common difference, so the theorem's floor is not reached.

Sharp. Take $A = \{0,1,2\}$ and $B = \{0,1\}$ , both progressions of difference $1$ . Then $A + B = \{0,1,2,3\}$ , of size $4 = 3 + 2 - 1$ exactly. $\checkmark$ □

Corollary 9.36 (Iterated sumsets in a prime field). Let $A \subseteq \mathbb{Z}/p\mathbb{Z}$ with $|A| \ge 1$ and let $h \ge 1$ . Then

|hA| \ \ge\ \min\bigl(p,\ h(|A|-1) + 1\bigr).

In particular, if

|A| \ge 2

then

hA = \mathbb{Z}/p\mathbb{Z}

as soon as

h \ge (p-1)/(|A|-1)

: every element of

\mathbb{Z}/p\mathbb{Z}

is a sum of at most that many elements of

A

Proof. Induct on $h$ . The case $h = 1$ is trivial. Assume $|hA| \ge \min(p, h(|A|-1)+1)$ . If $|hA| = p$ then $(h+1)A = \mathbb{Z}/p\mathbb{Z}$ too and we are done. Otherwise Theorem Cauchy–Davenport applied to $hA$ and $A$ gives

|(h+1)A| \ge \min\bigl(p,\ |hA| + |A| - 1\bigr) \ge \min\bigl(p,\ h(|A|-1) + 1 + |A| - 1\bigr) = \min\bigl(p,\ (h+1)(|A|-1)+1\bigr).

For the last statement,

h(|A|-1) + 1 \ge p

exactly when

h \ge (p-1)/(|A|-1)

.∎

Example 9.37 (A two-element set generates fast). In $\mathbb{Z}/11\mathbb{Z}$ let $A = \{0,1\}$ . How many summands are needed before $hA$ is all of $\mathbb{Z}/11\mathbb{Z}$ , and does the corollary predict it?

Solution. Directly, $hA = \{0,1,\ldots,h\}$ , so $hA = \mathbb{Z}/11\mathbb{Z}$ first at $h = 10$ .

The corollary predicts $|hA| \ge \min(11, h+1)$ and coverage once $h \ge (11-1)/(2-1) = 10$ . Both match exactly, so the corollary is sharp for this $A$ — as it must be, since $\{0,1\}$ is a progression and progressions are the extremal sets throughout. $\checkmark$ □

Cauchy–Davenport says how small $|A+B|$ can be; Vosper's theorem says which pairs actually achieve it. It is the $\mathbb{Z}/p\mathbb{Z}$ analogue of Theorem Equality in the elementary bound, and it needs genuine exceptions, because a prime cyclic group has a few degenerate ways to be extremal that $\mathbb{Z}$ does not.

Theorem 9.38 (Vosper). Let $p$ be prime and let $A, B \subseteq \mathbb{Z}/p\mathbb{Z}$ satisfy $|A|, |B| \ge 2$ and $|A+B| = |A| + |B| - 1 \le p - 2$ . Then $A$ and $B$ are arithmetic progressions with the same common difference.

Proof. Sketch only. The result is not proved here. The standard route derives it from Kneser's theorem — stated in the previous section as Theorem Kneser — together with an analysis of the $e$ -transform: one shows that a critical pair is stable under every transform, and that stability in $\mathbb{Z}/p\mathbb{Z}$ forces the progression structure. Hamidoune's isoperimetric method gives a second proof. Both arguments are longer than the Nullstellensatz proof of the bound itself, which is typical: an extremal bound is usually far easier than the classification of its extremal cases.∎

Pitfall. Vosper's hypotheses are not decoration. The condition $|A+B| \le p-2$ rules out the genuine exceptions: if $A + B$ is everything, or everything but one point, then $A$ and $B$ need not be progressions at all — take $B$ to be the complement of $-A$ shifted, and the sumset is forced to be almost the whole group regardless of structure. Likewise $|A|,|B| \ge 2$ is needed because a singleton $A$ makes $|A+B| = |B| = |A|+|B|-1$ for every $B$ whatsoever.

Exercises for §9.5 →

9.6Structure Theory of Sets with Small Doubling

Cauchy–Davenport and its relatives answer "how small can a sumset be?". The modern subject asks the converse question — an inverse problem: if $|A+A|$ is small, what must $A$ look like? The examples so far all point the same way: progressions and cosets are the sets that fail to grow. The structure theory makes that into a theorem.

Definition 9.39 (Doubling constant). For a finite nonempty $A$ in an abelian group, the doubling constant is

K = \frac{|A+A|}{|A|} .

Proposition 9.40 (Range of the doubling constant). For finite nonempty $A \subseteq \mathbb{Z}$ with $|A| = n$ ,

2 - \frac{1}{n} \ \le\ K \ \le\ \frac{n+1}{2},

the lower bound attained exactly by arithmetic progressions and the upper bound by sets with all

\binom{n+1}{2}

pairwise sums distinct, such as a Sidon set.

Proof. The lower bound is Theorem The elementary sumset bound with $B = A$ , which gives $|A+A| \ge 2n-1$ , hence $K \ge (2n-1)/n = 2 - 1/n$ ; the equality case is Theorem Equality in the elementary bound. The upper bound holds because $a + a'$ depends only on the multiset $\{a,a'\}$ , so at most $\binom{n}{2} + n = \binom{n+1}{2}$ sums occur, and $K \le \binom{n+1}{2}/n = (n+1)/2$ . A Sidon set — one in which all pairwise sums are distinct, for example $\{1, 2, 4, 8, \ldots, 2^{n-1}\}$ — attains it.∎

Pitfall. The doubling constant of a progression is close to $2$ , never close to $1$ . Doubling below $2$ is impossible in $\mathbb{Z}$ for a set with more than one element, so "small doubling" always means " $K$ bounded by an absolute constant", not " $K$ near $1$ ". In a group with subgroups the situation differs: a coset of a finite subgroup has $K = 1$ exactly.

Example 9.41 (Three doubling constants). Compute $K$ for $A = \{1,\ldots,n\}$ , for $A = \{1,2,4,\ldots,2^{n-1}\}$ , and for $A = \{1,4,9,\ldots,n^{2}\}$ as $n$ grows.

Solution. For the progression, $A + A = \{2,\ldots,2n\}$ has $2n-1$ elements, so $K = 2 - 1/n \to 2$ .

For the powers of $2$ , every sum $2^i + 2^j$ with $i \le j$ has a distinct binary representation, so all $\binom{n+1}{2}$ sums are distinct and $K = (n+1)/2 \to \infty$ linearly — the maximum possible.

For the squares, a classical estimate of Erdős and Szemerédi gives $|A+A| = n^{2}/(\log n)^{c + o(1)}$ for a constant $c > 0$ : almost as large as possible, so $K$ grows like $n$ up to a logarithmic factor. Squares are additively unstructured, which is why none of the structure theory below applies to them, even though they are highly structured multiplicatively. $\checkmark$ □

The engine of the whole theory is one inequality with a two-line proof.

Theorem 9.42 (Ruzsa triangle inequality). For finite nonempty subsets $A, B, C$ of an abelian group,

|A|\;|B - C| \ \le\ |B - A|\;|A - C| .

Proof. For each $d \in B - C$ fix once and for all a representation $d = b(d) - c(d)$ with $b(d) \in B$ , $c(d) \in C$ . Define

\Phi : A \times (B-C) \longrightarrow (B-A) \times (A-C), \qquad \Phi(a, d) = \bigl(b(d) - a,\ a - c(d)\bigr).

The two coordinates do lie in the stated sets.

\Phi

is injective: from the image pair

(u,v)

we recover

u + v = b(d) - c(d) = d

, hence the chosen

b(d)

, hence

a = b(d) - u

. An injection gives

|A||B-C| \le |B-A||A-C|

.∎

Intuition. Rewriting the inequality as

\log\frac{|B-C|}{\sqrt{|B||C|}} \ \le\ \log\frac{|B-A|}{\sqrt{|B||A|}} + \log\frac{|A-C|}{\sqrt{|A||C|}}

shows what it really is: the quantity

d(X,Y) = \log\bigl(|X-Y|/\sqrt{|X||Y|}\bigr)

, the Ruzsa distance, satisfies the triangle inequality. Sets are points in a metric-like space, and two sets are close when their difference set is small — that is, when they are additively similar. It is not a metric (

d(A,A)

need not be

0

), but every subsequent result is a statement about this geometry.

Theorem 9.43 (Plünnecke–Ruzsa). Let $A, B$ be finite nonempty sets in an abelian group with $|A + B| \le K|A|$ . Then for all integers $m, n \ge 0$ ,

|mB - nB| \ \le\ K^{\,m+n}\,|A| .

In particular, if

|A + A| \le K|A|

then

|hA| \le K^{h}|A|

for every

h \ge 1

Proof. Sketch only. Two proofs are standard and neither is short. Plünnecke's original argument builds a layered directed graph whose vertices are the sets $A, A+B, A+2B, \ldots$ and applies a magnification-ratio inequality proved with Menger's theorem. Petridis's proof, which is the one now usually taught, chooses a nonempty $X \subseteq A$ minimising the ratio $|X+B|/|X|$ and shows by induction on $n$ that $|X + nB| \le (|X+B|/|X|)^n |X|$ ; the Ruzsa triangle inequality above then converts sums into differences and transfers the bound from $X$ back to $A$ . The result rests on: the triangle inequality of Theorem Ruzsa triangle inequality, and the covering argument that lets a minimising subset stand in for the whole set.∎

Example 9.44 (From doubling to tripling). Suppose $|A + A| \le 2|A|$ . What bound does Plünnecke–Ruzsa give for $|3A|$ , and how far is it from the truth for a progression?

Solution. Take $B = A$ and $K = 2$ ; then $|3A| \le 2^3|A| = 8|A|$ .

For $A = \{1,\ldots,n\}$ the hypothesis holds ( $K = 2 - 1/n < 2$ ) and $3A = \{3,\ldots,3n\}$ has $3n-2$ elements, so the truth is about $3|A|$ against a guarantee of $8|A|$ . The constant is not sharp, and improving such constants is an active industry; the content of the theorem is the shape of the bound — bounded doubling forces every higher sumset to stay within a constant factor, with the constant depending only on $K$ and not at all on $|A|$ . $\checkmark$ □

With higher sumsets under control, the inverse problem can be answered. The answer needs a notion of "approximate progression".

Definition 9.45 (Generalised arithmetic progression). A generalised arithmetic progression (GAP) of dimension $d$ is a set of the form

P = \{\,x_0 + \ell_1 v_1 + \cdots + \ell_d v_d \ :\ 0 \le \ell_i < L_i\,\}

for some

x_0, v_1,\ldots,v_d

in the group and positive integers

L_1,\ldots,L_d

. Its size is

L_1\cdots L_d

, and it is proper if all those elements are distinct, so that

|P|

equals its size.

A GAP of dimension $d$ and size $L$ has $|P + P| \le 2^d |P|$ , since each $\ell_i$ can only double its range: small doubling is automatic. Freiman's theorem is the converse, and it is one of the landmark theorems of the subject.

Theorem 9.46 (Freiman). Let $A \subseteq \mathbb{Z}$ be finite with $|A + A| \le K|A|$ . Then $A$ is contained in a proper generalised arithmetic progression of dimension at most $d(K)$ and size at most $f(K)\,|A|$ , where $d(K)$ and $f(K)$ depend only on $K$ and not on $A$ .

Proof. Sketch only. Ruzsa's proof, the standard one, runs in four stages, and naming them is the honest way to state what the theorem rests on. (i) Plünnecke–Ruzsa bounds $|nA - mA|$ by $K^{O(1)}|A|$ , so all the iterated sumsets are under control. (ii) Freiman modelling: a set of small doubling is Freiman-isomorphic — additively indistinguishable up to the relevant number of summands — to a subset of a finite group $\mathbb{Z}/N\mathbb{Z}$ of size $O_K(|A|)$ , which replaces $\mathbb{Z}$ by a compact setting. (iii) Bogolyubov's lemma, a Fourier-analytic argument, shows that $2A - 2A$ inside $\mathbb{Z}/N\mathbb{Z}$ contains a large Bohr set. (iv) A geometry of numbers argument (Minkowski's second theorem) finds a large proper GAP inside that Bohr set, and pulling back through the modelling covers $A$ . Each stage is a chapter in its own right, and the bounds $d(K), f(K)$ coming out of this route are exponential in $K$ ; Sanders and Schoen have improved them, and the conjecturally correct polynomial bounds are open.∎

Theorem 9.47 (Freiman's $3k-4$ theorem). Let $A \subseteq \mathbb{Z}$ be finite with $|A| = k \ge 3$ and $|A+A| \le 3k - 4$ . Then $A$ is contained in an arithmetic progression of length at most $|A+A| - k + 1$ .

Proof. Sketch only. This is the exact, one-dimensional case of Freiman's theorem, and unlike the general theorem it is proved by elementary combinatorial arguments on the ordered set $A$ — no Fourier analysis is involved — but the case analysis is long and is not reproduced here. Taking $|A+A| = 2k-1$ recovers the equality case of Theorem Equality in the elementary bound: $A$ lies in a progression of length $k$ , so it is a progression.∎

Intuition. The three theorems fit into one sentence. Plünnecke–Ruzsa says small doubling is inherited by all higher sumsets — a quantitative statement. Freiman's theorem says small doubling has a cause: the set is a chunk of a bounded-dimensional grid. And $3k-4$ says that when the doubling is very small, dimension one suffices and the description is exact. The progression is not one example of a set with small doubling; up to bounded distortion it is the only one.

The frontier

Two questions define the modern subject, and both are beyond the techniques developed here.

Theorem 9.48 (Roth; Szemerédi). (Roth 1953; Szemerédi 1975.) Let $k \ge 3$ and let $A \subseteq \{1,2,\ldots,N\}$ contain no $k$ -term arithmetic progression. Then $|A| = o(N)$ as $N \to \infty$ . Equivalently, every set of integers of positive upper density contains arbitrarily long arithmetic progressions.

Remark. No proof of either statement is given in this chapter, and neither is within reach of the polynomial method. Roth's case $k=3$ is proved by a Fourier-analytic density increment: a progression-free set has a large Fourier coefficient, which locates a subprogression on which the set is denser, and iterating must terminate. Szemerédi's general $k$ was first proved by a combinatorial argument that introduced the regularity lemma; Furstenberg gave an ergodic-theoretic proof via multiple recurrence, and Gowers gave a quantitative proof introducing the uniformity norms that carry his name. Green and Tao then combined a transference principle with Szemerédi's theorem to show that the primes, of density zero, contain arbitrarily long progressions. Each of these is a course, not a section.

Remark. The other open frontier is the sum–product phenomenon. Erdős and Szemerédi conjectured that for finite $A \subseteq \mathbb{Z}$ ,

\max\bigl(|A+A|,\ |A\cdot A|\bigr) \ \ge\ |A|^{2-o(1)},

the point being that a set cannot be additively structured and multiplicatively structured at once: an arithmetic progression has a huge product set, a geometric progression has a huge sum set. The conjecture is open; the best exponents come from incidence geometry — the Szemerédi–Trotter theorem on point–line incidences, via Elekes's argument — and finite-field analogues from Bourgain–Katz–Tao. The polynomial method touches this area too, through the Guth–Katz solution of the Erdős distinct distances problem.

Exercises for §9.6 →

Common Mistakes

Using a monomial that is not top-degree. The Combinatorial Nullstellensatz requires $\sum_i d_i = \deg f$ exactly. A nonzero coefficient on a lower-degree monomial says nothing at all, and this is by far the commonest misapplication.
**Checking $|S_i| > \deg f$ instead of $|S_i| > d_i$ . ** The size condition is coordinatewise. Demanding grids larger than the total degree throws away most of the theorem's strength — in the Cauchy–Davenport proof the grids are $A$ and $B$ themselves, both far smaller than $\deg f$ .
Applying the theorem over a ring. $\mathbb{Z}/4\mathbb{Z}$ , $\mathbb{Z}/6\mathbb{Z}$ and $\mathbb{Z}$ modulo a composite are not fields, and the theorem fails there: $2x^{2}+2x$ vanishes on all of $\mathbb{Z}/4\mathbb{Z}$ .
Confusing it with the Hilbert Nullstellensatz. Hilbert's theorem is about the ideal of polynomials vanishing on a variety over an algebraically closed field. Alon's is a finite, quantitative non-vanishing statement on a grid, and neither implies the other in any useful direction.
Expecting a construction. Both the Nullstellensatz and Chevalley–Warning are existence theorems. Chevalley–Warning in particular tells you a second solution exists and gives no way to find it.
**Writing $2A$ for the dilate.** $2A = A+A$ ; the dilate is $2 \cdot A = \{2a\}$ . For $A = \{0,1\}$ these have sizes $3$ and $2$ .
**Assuming $|A+B| \approx |A||B|$ . ** That is the generic case, not a theorem. For structured sets — progressions, cosets, GAPs — the sumset is linear in $|A|$ , and the whole inverse theory exists to describe exactly those sets.
Quoting Cauchy–Davenport in the wrong group. It needs $\mathbb{Z}/p\mathbb{Z}$ with $p$ prime. In $\mathbb{Z}/6\mathbb{Z}$ the subgroup $\{0,2,4\}$ satisfies $|A+A| = 3 < 2|A|-1$ , and in $\mathbb{Z}$ the correct statement is the elementary bound with no $\min$ .
**Forgetting the $\min(p,\cdot)$ . ** A sumset in $\mathbb{Z}/p\mathbb{Z}$ can never exceed $p$ elements, so the bound $|A|+|B|-1$ is only meaningful below that ceiling.
**Reading small doubling as $K \approx 1$ . ** In $\mathbb{Z}$ the doubling constant is always at least $2 - 1/|A|$ . Small doubling means $K = O(1)$ .
Treating Freiman's theorem as effective. The dimension and size bounds it produces are enormous functions of $K$ , and the sharp polynomial versions are conjectural. Quoting the theorem is legitimate; quoting a specific constant from it usually is not.
Expecting the polynomial method to reach Roth's theorem. It settles the cap set problem in $\mathbb{F}_3^n$ and says nothing about progression-free subsets of $\{1,\ldots,N\}$ . The $\mathbb{F}_3^n$ case is easier because $x^{3} = x$ holds identically and the group is full of subspaces.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

← The Probabilistic Method Matroids and Matchings →

Helpful?