A sum of two sets modulo a prime cannot be small

Take two sets of numbers, $A$ and $B$, and form every sum $a + b$ with $a$ in $A$ and $b$ in $B$. The set of all those sums is written $A + B$, and it is called a sumset. If $A$ has 4 elements and $B$ has 3 there are 12 sums, and the question is how many of them can coincide — how small $A + B$ can be.

Over the whole numbers the answer is immediate. List $A$ in increasing order as $a_1 < a_2 < a_3 < a_4$ and $B$ as $b_1 < b_2 < b_3$. Then

$$a_1 + b_1 < a_2 + b_1 < a_3 + b_1 < a_4 + b_1 < a_4 + b_2 < a_4 + b_3$$

is a chain of six different sums, so $A + B$ has at least $4 + 3 - 1 = 6$ elements. In general $|A + B| \geq |A| + |B| - 1$, and two arithmetic progressions with the same step, such as $\{0, 1, 2, 3\}$ and $\{0, 1, 2\}$, give exactly that many.

Now do the same arithmetic modulo a prime $p$. The chain argument breaks immediately, because residues have no order that addition respects: a sum can pass $p$ and wrap round to a small residue, and the chain can come back on itself. Sums that were forced apart over the whole numbers are free to collide. And yet, modulo a prime, they collide no more than they did before. That is the Cauchy–Davenport theorem, and the reason it holds modulo a prime and fails modulo 12 is the same reason a line in every direction cannot fit in a small set: a polynomial whose degree is too low to vanish where it would have to.

Sums on a clock #

Modulo 13, the sets $\{0, 1, 2, 3\}$ and $\{0, 4, 5\}$ have nine distinct sums, $0$ to $8$. The whole-number bound would ask for six, and the modular version of the theorem asks for the same six, with one adjustment: a sumset cannot have more elements than there are residues, so the bound is

$$|A + B| \geq \min(p,\ |A| + |B| - 1).$$

Augustin-Louis Cauchy proved this in 1813, as a lemma on the way to a theorem about sums of polygonal numbers, and it was forgotten. Harold Davenport proved it again in 1935, for a question about sequences, without knowing Cauchy had, and the theorem carries both names. Both proofs are inductions: shrink one of the sets by a clever exchange with the other, keeping the sum of the sizes fixed and the sumset from growing, until one set has a single element and the bound is obvious. The exchange is short but it is not transparent, and it gives no hint of why primality should matter.

The minimum with $p$ is not decoration. If $|A| + |B| > p$, then for any residue $c$ the sets $A$ and $c - B$ together have more than $p$ elements, so they must share one, say $a = c - b$, and then $c = a + b$. Every residue is a sum, and $A + B$ is everything. The interesting range is the other one, where the sizes add up to at most $p$ and the sums have room to collide.

Every pair of sets modulo seven #

The statement is about every pair of sets, and for a small prime every pair can be tried.

The table records, for each pair of sizes $a \leq b$, the smallest sumset over every pair of subsets of the residues modulo 7 with those sizes. Shifting either set by a constant shifts the sumset by the same constant and does not change its size, so both sets may be taken to contain 0, which leaves $2^6 \times 2^6 = 4{,}096$ pairs of sets to try. Every entry is exactly $\min(7, a + b - 1)$. No pair of sets modulo 7 has fewer sums than the theorem allows, and for every pair of sizes some pair of sets — two runs of consecutive residues — has exactly that many.

The search is a check of the theorem at one prime, and a complete one there, since nothing is left untried. It is also a check of sharpness: the bound is not merely true, it is the answer. A. G. Vosper proved in 1956 that, away from the extremes, runs with a common step are the only way to reach it — if $|A + B| = |A| + |B| - 1$ and the sumset is not nearly everything, then $A$ and $B$ are arithmetic progressions with the same difference. The equality cases are as rigid as the whole-number ones, even though the whole-number proof that explained them no longer applies.

That rigidity is the first appearance of a theme that runs through additive combinatorics: a set with few sums must be structured, and the structure is a progression. Freiman’s theorem, from the 1960s, says the same thing over the whole numbers in a weaker and much harder form — a set whose sumset is at most a constant times its own size sits inside a generalised progression not much larger than itself. The opposite direction, finding progressions inside large sets rather than large sets inside progressions, is where van der Waerden’s colourings live, and the two directions meet in Szemerédi’s theorem.

A polynomial that vanishes on every sum #

The proof that shows where the prime is used is from 1995, by Noga Alon, Melvyn Nathanson and Imre Ruzsa, and it runs on a single polynomial.

The pairs $(a, b)$ form a grid, $|A|$ wide and $|B|$ tall, and each cell has a sum. Suppose, to reach a contradiction, that the sums take at most $|A| + |B| - 2$ values, and that $|A| + |B| \leq p$ so the minimum in the bound is not the prime. Enlarge the set of sums, if necessary, to a set $C$ of exactly $|A| + |B| - 2$ residues, and form

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

Every cell of the grid has its sum in $C$, so $f$ vanishes at every point of the grid. Its degree is $|A| + |B| - 2$, which is $(|A| - 1) + (|B| - 1)$: one less than the width of the grid plus one less than its height. Expanding the product, the coefficient of $x^{|A|-1} y^{|B|-1}$ counts the ways of choosing $x$ from $|A| - 1$ of the factors and $y$ from the rest, which is the binomial number

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

The top of that binomial is less than $p$, so no factor of $p$ appears in it, and the prime does not divide it. The coefficient is not zero modulo $p$. For the grid in the figure it is $\binom{5}{3} = 10$, not a multiple of 11.

The theorem the polynomial runs into #

The contradiction comes from a theorem Alon published in 1999 and called the Combinatorial Nullstellensatz. In its two-variable form it says: if a polynomial $f(x, y)$ over a field has total degree $s + t$, and its coefficient of $x^s y^t$ is not zero, then on any grid $A \times B$ with more than $s$ columns and more than $t$ rows there is a point where $f$ is not zero.

The reason is the same root count that drives the Kakeya argument. Reduce $f$ on the grid: wherever $x$ appears to a power of $|A|$ or more, replace $x^{|A|}$ using the polynomial $\prod_{a \in A}(x - a)$, which is zero on the grid, and likewise for $y$. The reduced polynomial agrees with $f$ on the grid, has degree below $|A|$ in $x$ and below $|B|$ in $y$, and — because the replacement only ever lowers the total degree — still carries the same top coefficient on $x^{|A|-1} y^{|B|-1}$. A polynomial of degree below $|A|$ in $x$ that vanished on every column would, by the root count, be zero in $x$ for each fixed row, and then zero outright. So it cannot vanish on the whole grid.

Here $s = |A| - 1$ and $t = |B| - 1$, the grid has exactly $|A|$ columns and $|B|$ rows, and the coefficient is the binomial number. So $f$ is non-zero somewhere on the grid. But every point of the grid is a pair whose sum lies in $C$, where $f$ vanishes. The assumption was false, and $|A + B| \geq |A| + |B| - 1$.

The prime entered at exactly one place: to guarantee that a binomial coefficient is not zero. The rest of the argument needs only a field, and a field in which that one number survives.

That second condition is not automatic even in a field. The field with four elements has characteristic 2: adding any element to itself gives zero, so $\{0, 1\}$ is closed under addition, and $\{0, 1\} + \{0, 1\}$ has two elements, not three. The proof sees exactly this. With $|A| = |B| = 2$ the binomial is $\binom{2}{1} = 2$, which is zero in characteristic 2, and the Nullstellensatz has nothing to work with. Over any finite field the theorem holds with the characteristic in place of $p$ — $|A + B| \geq \min(\text{char},\ |A| + |B| - 1)$ — and it is the characteristic, not the size of the field, that the binomial number has to escape. Modulo 12 there is no field at all, and the argument has no ground to stand on.

What goes wrong modulo twelve #

The residues modulo 12 are not a field, and the theorem genuinely fails there.

The multiples of 3 modulo 12 are $\{0, 3, 6, 9\}$, and adding two of them gives another. They form a subgroup — a set of residues closed under addition — and any two sets chosen inside it add to a set inside it, which has only four elements however large the sets are. Two sets of three add to four sums. Modulo a prime nothing like this can happen, because a subgroup’s size must divide the whole, and a prime has no divisors to offer but 1 and itself.

The search modulo 12 shows how often. Of the 78 pairs of sizes, 22 have sumsets smaller than the Cauchy–Davenport bound, and every shortfall comes from sets packed into a whole number of translates of one subgroup. Two sets of four can add to four, inside the multiples of 3; two sets of six can add to six, inside the even residues; a set of two and a set of ten can add to ten, as five translates of $\{0, 6\}$ that the smaller set only shuffles among themselves.

Martin Kneser proved in 1953 that this is the only way the bound fails, in every finite abelian group. If $A + B$ is small, it is a union of whole translates of some subgroup $H$ — its stabiliser, the subgroup that shifts it onto itself — and then

$$|A + B| \geq |A + H| + |B + H| - |H|.$$

Modulo a prime the only subgroups are the trivial one and everything, and Kneser’s inequality reduces to Cauchy and Davenport’s. So the prime version is not a lucky special case; it is what remains of the general theorem when the only obstruction is removed. The table’s shaded cells are the obstruction made visible.

Sums with the diagonal removed #

The polynomial proof was not the first proof of Cauchy–Davenport, but it was the first that bent easily to the question next to it. Paul Erdős and Hans Heilbronn asked in the 1960s what happens if only sums of different elements are allowed: the restricted sumset $\{a + a' : a, a' \in A,\ a \neq a'\}$, where the diagonal of the grid is thrown away. They conjectured that it has at least $\min(p, 2|A| - 3)$ elements.

The whole-number analogue is again easy and the modular version resisted for thirty years. José António Dias da Silva and Yahya Ould Hamidoune proved it in 1994 with the representation theory of symmetric groups. A year later Alon, Nathanson and Ruzsa proved it with the polynomial

$$(x - y) \prod_{c \in C} (x + y - c),$$

in which the extra factor $x - y$ vanishes on exactly the diagonal that the restricted sum leaves out. The top coefficient is again a number the prime cannot divide, the Nullstellensatz again finds a point where the polynomial survives, and the contradiction is the theorem. The difference between thirty years and a paragraph was a single factor that encodes the restriction as a zero.

Where the bound is used: sums divisible by a prime #

The theorem earns its keep on questions that do not mention sumsets. Among any $2p - 1$ whole numbers, some $p$ of them have a sum divisible by $p$: that is the Erdős–Ginzburg–Ziv theorem for a prime, proved by counting solutions of equations over a finite field. Cauchy–Davenport gives it a second proof, in a few lines.

Sort the $2p - 1$ numbers by their remainders, $a_1 \leq a_2 \leq \dots \leq a_{2p-1}$. If some remainder occurs $p$ times, those $p$ numbers already have a sum divisible by $p$. Otherwise $a_i$ and $a_{i+p-1}$ have different remainders for each $i$ from 1 to $p - 1$, and each pair forms a set $A_i$ of two residues. Adding the $p - 1$ two-element sets one at a time, Cauchy–Davenport says each addition raises the size by at least one until it reaches $p$, so $A_1 + A_2 + \dots + A_{p-1}$ is every residue. In particular it contains $-a_{2p-1}$: choosing one number from each pair gives $p - 1$ numbers whose sum is $-a_{2p-1}$, and with $a_{2p-1}$ added the total is divisible by $p$.

The two proofs are worth setting side by side, because both use the prime and neither uses it in an obvious way. One counts solutions of a polynomial system and finds the count divisible by $p$; the other grows a sumset and finds it cannot stall. Both are, underneath, statements about polynomials of low degree over a field of prime order.

A cousin: many sums or many products #

The Cauchy–Davenport bound is met by arithmetic progressions, which are sets built for addition. Multiply instead of adding and the roles reverse: a geometric progression $1, g, g^2, \dots$ has as few products as a progression has sums.

The figure measures three kinds of set modulo 1009. The arithmetic progression has exactly $2k - 1$ sums, the Cauchy–Davenport minimum, and hundreds of products. The geometric progression has exactly $2k - 1$ products — it is an arithmetic progression in the exponents, through a primitive element — and hundreds of sums. The random set is large under both. No set drawn is small under both operations at once.

That is the sum-product phenomenon. Erdős and Szemerédi conjectured in 1983 that a set of whole numbers always has nearly $|A|^2$ sums or nearly $|A|^2$ products. Modulo a prime the question only makes sense for sets that are neither tiny nor nearly everything, and Jean Bourgain, Nets Katz and Terence Tao proved in 2004 that every set of intermediate size grows by a definite power under one operation or the other. Their proof does not use the Nullstellensatz, and the growth they obtain is far below what the figure’s sets show: the conjecture’s strength is still out of reach, over the primes and over the whole numbers alike.

What the searches cannot show #

The exhaustive tables stop at the primes 7 and the composite 12. The theorem at 7 is checked completely, pair of sets by pair of sets; at every other prime it is proved, and the figures do not check it. The clock and the grid are single examples chosen to show the mechanism, not evidence for it.

The sum-product figure measures three chosen families, not every set. It shows that these sets are large under one operation; that no set is small under both is Bourgain, Katz and Tao’s theorem, quoted and not reproduced, and the figure’s random sets happen to grow far faster than the theorem guarantees.

And Kneser’s theorem is read off the table, not proved by it. The shaded cells of the search modulo 12 sit at subgroup sizes, which is what Kneser’s inequality predicts; that nothing else can ever cause a failure is his proof, not the search’s.

The restricted sums are not drawn. The Erdős–Heilbronn bound is stated and its polynomial described, but no figure lists restricted sumsets or checks the bound $2|A| - 3$ against a search; it is quoted from Dias da Silva and Hamidoune.

A polynomial of degree too low to vanish #

Over the whole numbers, sums of two sets are kept apart by order. Modulo a prime there is no order, and they are kept apart instead by a polynomial: if the sums fitted into too few residues, a product of linear factors of low degree would vanish on a whole grid while carrying a top coefficient the prime cannot divide, and Alon’s Nullstellensatz says no such polynomial exists. Modulo 12, subgroups let the sums collapse, and Kneser’s theorem says that is the only way they can.

The same shape carried the argument about lines in every direction, and it will carry more: count the degree a polynomial would need, and show that the configuration would force it to vanish where it cannot. Nothing in the proof looks at the sets themselves — it never asks which residues they hold, only how many — which is why a single paragraph covers every pair of sets modulo every prime at once, where the search needed four thousand pairs to settle one prime.

When a combinatorial bound holds modulo a prime and fails modulo a composite, look for a polynomial whose top coefficient is a number the prime cannot divide — the prime’s only job is to keep that one coefficient alive.