Cauchy–Davenport theorem

Remarks

One proof is by induction on $\abs{B}$. It replaces $(A, B)$ by $(A \cup (B + e), \ B \cap (A - e))$ for a suitable $e$, which keeps $\abs{A} + \abs{B}$ and does not enlarge the sumset. Another proof uses the combinatorial Nullstellensatz with a polynomial that vanishes on a too small set $C \supseteq A + B$. The bound is sharp: for $A = \set{0, 1, \dots, k-1}$ and $B = \set{0, 1, \dots, l-1}$ with $k + l - 1 \le p$, the sumset is $\set{0, \dots, k + l - 2}$. The hypothesis that $p$ is prime is needed. In $\Z/4\Z$, take $A = B = \set{0, 2}$; then $A + B = \set{0, 2}$ has $2$ elements, while $\min(4, 3) = 3$.

Going deeper

For a student

The Cauchy–Davenport theorem is the analogue for $\Z/p\Z$ of the easy bound $\abs{A + B} \ge \abs{A} + \abs{B} - 1$ for sets of integers. Over composite moduli, subgroups give smaller sumsets, and Kneser's theorem describes this. The Dias da Silva–Hamidoune theorem bounds the set of sums of two distinct elements of $A$ by $\min(p, 2\abs{A} - 3)$, as conjectured by Erdős and Heilbronn.