Cauchy-Davenport Theorem

Cauchy-Davenport Theorem says that given a prime $p$ and non-empty subsets $A$ and $B$ of $\mathbb{Z}_p$, the minimum possible size of $A+B\equiv\{c|a+b=c,a\in A, b\in B\}\subset\mathbb{Z}_p$ is $\min\{p, |A|+|B|-1\}$.

I learned a few interesting things.

1. For $|A|+|B|>p$, this implies every number in $\mathbb{Z}_p$ is in $A+B$, which does not rely on $p$ being a prime. This is because every number $c$ can be written as $c=a+b$ in exactly $p$ ways, so at least one $\left(a,b\right)$ is covered, i.e., $a\in A$ and $b\in B$. Hence the theorem is only non-trivial when $|A|+|B|\leq p$.

2. A quick proof uses Combinatorial Nullstellensatz. Consider  a polynomial $f(x,y)=\prod_{i=1}^{|A|+|B|-2}(x+y-c_i)\in\mathbb{Z}_p(x,y)$ where all $c_i$ are distinct. It has a highest-degree term $x^{|A|-1}y^{|B|-1}$, so there is $(x,y)\in A\times B$ such that $f(x,y)\ne 0$.

3. It leads to another result: given $t$ elements in $\mathbb{Z}_p$ which are not necessarily distinct, they have at least $\min\{p, t+1\}$ distinct partial sums: grab $t_1$ elements that produce at least $t_1+1$ partial sums including $0$, which is always possible when $t_1=1$. Similarly grab another $t_2$ elements. Applying the theorem on them yields a set of $t_1+t_2$ elements with at least $t_1+t_2+1$ partial sums. Keep doing it until all $t$ elements have been enumerated or bound $p$ has been hit.

4. Finally, here is the ingenious proof of Cauchy-Davenport Theorem with minimum algebra found here.

Proof:
Consider the following two operations that do not change $|A|+|B|$ and do not increase $|A+B|$.

(i) rotate $A$ and $B$ by replacing each element $a\in A$ and $b\in B$ with $a+r_A$ and $b+r_B$, respectively.

(ii) whenever $A$ and $B$ overlap, replace them with $A\cup B$ and $A\cap B$.

When $A$ and $B$ are disjoint, do (i) until they overlap.

When $|A\cap B|>1$, do (ii) to get $A'\subset B'$ and then rotate $A'$ so that it has fewer but non-zero overlap with $B'$. If it is impossible, then every rotation of $A'$ either has $0$ or $|A'|$ overlap with $|B'|$, and eventually $|B'|=p$ is implied because $p$ is prime and $|A'|>1$.

After finite operations we have $|A\cap B|=1$. We rotate both so that they overlap at $0$ only and we are done.

$\diamond$