While trying to prove the prime case of Erdős–Ginzburg–Ziv theorem:
Theorem: For every prime number $p$, in any set of $2p-1$ integers, the sum $p$ of them divisible by $p$.
I came across with the following lemma:
Lemma 1: If $p$ is a prime number and $A,B$ are subsets of $\mathbb{Z}_p$ with $\varnothing\neq A\neq \mathbb{Z}_p $ and $\left |B\right | =2$, then $\left |A+B \right | \geq\left |A\right |+1 $, where $ A+B=\{a+b: a \in A, b \in B \} $.
Proof: Without loss of generality $B=\{ 0,\beta\}$, where $\beta \neq 0$ and then $A\subseteq A+B$. Let us assume by contradiction that $A+B=A$. Let $a\in A$. Therefore $a+\beta\in A+B$, and thus $a+\beta\in A$. By this manner we can deduce that $a+k\beta\in A$ for every $k$ and from here that
$$\mathbb{Z}_p=\{a,a+\beta, a+2\beta,\dots , a+(p-1)\beta\}\subseteq A $$
But we assume $A\neq \mathbb{Z}_p$.■
Question 1: How we deduce that $\left |A+B \right | \geq\left |A\right |+1$ by such contradiction?
Here I decided to prove this lemma by my own, and I came up with some more general result:
Lemma 2: If $p$ is a prime number and $A,B$ are subsets of $\mathbb{Z}_p$ with $\varnothing\neq A,B$, then $\left |A+B \right | \geq\left |A\right |+\left |B\right | -1 $
Proof: Since the set of integer numbers is ordered set, we can translate $A$ and $B$ to new sets $A'$ and $B'$, so that $\sup(A')=0$ and $\inf(B')=0$ and still preserve the cardinalities of these two sets, thus $\left |A\right|=\left |A'\right |$ and $\left |B\right|=\left |B'\right |$. Now, since $0\in A',B'$ we can deduce that $A\cup B\subseteq A+B$. Small observation about the nature of $A'$ and $B'$ revivals that $\left |A\cup B\right|=\left |A\right|+\left |B\right|-1$. Combining the last result with $\left |A\cup B\right|\leq\left |A+B\right |$ we get the desired result. ■
Now, returning to text where lemma 1 is used,
Proof(EGZ for primes): Without loss of generality let
$$(1) \ \ \ \ \ \ \ 0\leq a_1\leq a_2\leq\dots \leq a_{2p-1}<p$$
If $a_i=a_{i+p-1}$ for certain $1\leq i\leq p$, then
$$\sum^{i+p-1}_{j=i}=pa_i$$
And that is what we looked for.
Now suppose that $a_i\neq a_{i+p-1}$ for all $1\leq i\leq p$, then we define $A_1=\{ a_1\}$ and $A_i=\{a_i,a_{i+p-1}\}$for $1\leq i\leq p $, then by repeating the lemma above one can conclude that in $\mathbb{Z}_p$:
$$\left|A_1+A_2+\cdots +A_p \right|=p$$
Thus, every element in $\mathbb{Z}_p$ is the sum of exact $p$ terms of our ordered set, and that the sum of $p$ elements of that set divisible by $p$. ■
Question 2: How really one can deduce $\left|A_1+A_2+\cdots +A_p \right|=p$ from the lemma, and how can one conclude that every element in $\mathbb{Z}_p$ is the sum of exact $p$ terms of our ordered set, and that the sum of $p$ elements of that set divisible by $p$?
Searching for more information, I came up with Noga Alon and Moshe Duniner article, which proved EGZ theorem in five different ways. The first proof that they begin with is the related one. They states the Cauchy-Davenport theorem:
Cauchy-Davenport theorem: If $p$ is a prime number and $A,B$ are two nonempty subsets of $\mathbb{Z}_p$, then $\left | A+B \right|\geq \min\{p,\left|A \right|+ \left | B \right |-1 \}$
And proving in the same matter the prime case of EGZ.
Question 3: Do we really need the Cauchy-Davenport theorem to prove EGZ theorem for primes?
Thank you.
Question 1: From the contradiction we get that $A$ is a proper subset of $A + B$ and hence $|A + B| > |A|$, or equivalently, $|A + B| \geq |A| + 1$.
Question 2: We should define $A_1 = \{a_1, a_{p - 1}\}$. Then by an induction argument that has the following crucial part $|A_1 + \dots + A_{i + 1}| \geq |A_1 + \dots + A_i| + |A_{i + 1}| - 1 \geq \min \{p, i + 1\}$, implies that $|A_1 + \dots + A_p| \geq \min \{p, p + 1\} = p$.
Question 3: No, we do not need Cauchy-Davenport to prove EGZ. As Alon-Dubiner have showed, it can be proved in several ways not all of which require Cauchy-Davenport. One of the most recent proofs of EGZ is that involving Restricted Variable Chevalley-Warning theorem, which follows from a result of Alon-Furedi: http://arxiv.org/abs/1404.7793, http://www.davidbrink.dk/Chevalley.pdf.
Here's the argument. Let $f= \sum x_i$ and $g = \sum a_ix_i$, where $a_i$'s are the $2p−1$ numbers modulo $p$. Then $(1−f^{p−1})(1−g^{p−1})$ has degree $2p−2$ and hence at least one non-zero $e = (e_1, \dots, e_{2p-1}) \in \{0,1\}^{2p−1} \subseteq \mathbb{Z}_p^{2p - 1}$ besides the origin, which corresponds to a common zero of $f$ and $g$. This non-zero corresponds to a subsequence of length $p$ (length is insured by the fact that $f(e_1, \dots, e_{2p-1}) = 0$) that sums up to $0$ (this is ensured by the fact that $g(e_1, \dots, e_{2p-1}) = 0$).