1. ## Erdos-Ginzburg-Ziv Theorem...

Hello!

I have proved the following lemma:

If $\displaystyle p$ is a prime number and $\displaystyle A,B$ are subsets of $\displaystyle \mathbb{Z}_p$ and $\displaystyle \emptyset \neq A \neq \mathbb{Z}_p$, $\displaystyle |B|=2$, then $\displaystyle |A+B| \geq |A|+1$ when $\displaystyle A+B=\{a+b|a \in A, b \in B \}$.

With that lemma I'm trying to prove the following:

If $\displaystyle 0 \leq a_1 \leq a_2 \leq...\leq a_{2p-1}<p$ and if $\displaystyle a_i \neq a_{i+p-1}$ for all $\displaystyle 1<i \leq p$. Let us now define $\displaystyle A_1=\{a_1\}$, $\displaystyle A_i=\{a_i,a_{i+p-1}\}$ for $\displaystyle 1<i \leq p$.

By repeating process with the lemma I need to conclude:

$\displaystyle |A_1+A_2+...+A_p|=p$

But I have some difficulties proving that... I could have proved only the inequality:

$\displaystyle |A_1+A_2+...+A_p|\geq p$

2. Originally Posted by Also sprach Zarathustra
Hello!

I have proved the following lemma:

If $\displaystyle p$ is a prime number and $\displaystyle A,B$ are subsets of $\displaystyle \mathbb{Z}_p$ and $\displaystyle \emptyset \neq A \neq \mathbb{Z}_p$, $\displaystyle |B|=2$, then $\displaystyle |A+B| \geq |A|+1$ when $\displaystyle A+B=\{a+b|a \in A, b \in B \}$.

With that lemma I'm trying to prove the following:

If $\displaystyle 0 \leq a_1 \leq a_2 \leq...\leq a_{2p-1}<p$ and if $\displaystyle a_i \neq a_{i+p-1}$ for all $\displaystyle 1<i \leq p$. Let us now define $\displaystyle A_1=\{a_1\}$, $\displaystyle A_i=\{a_i,a_{i+p-1}\}$ for $\displaystyle 1<i \leq p$.

By repeating process with the lemma I need to conclude:

$\displaystyle |A_2+A_3+...+A_p|=p$

But I have some difficulties proving that... I could have proved only the inequality:

$\displaystyle |A_2+A_3+...+A_p|\geq p$

Don't we know there are at most $\displaystyle \displaystyle p$ elements in the sum of these sets since we're working in $\displaystyle \displaystyle \mathbb{Z}/p\mathbb{Z}?$

3. Originally Posted by chiph588@
Don't we know there are at most $\displaystyle \displaystyle p$ elements in the sum of these sets since we're working in $\displaystyle \displaystyle \mathbb{Z}/p\mathbb{Z}?$
I am not completely understand you...

What if in |A_2+A_3+...+A_p| has repeating elements?

4. Originally Posted by Also sprach Zarathustra
I am not completely understand you...

What if in |A_2+A_3+...+A_p| has repeating elements?
I was under the impression that they would be 'absorbed' into one element.

5. If I just could find a logical explanation that $\displaystyle |A_2+A_3+...+A_p|> p$ is impossible or $\displaystyle |A_2+A_3+...+A_p|\leq p$

hmmm....

6. Originally Posted by chiph588@
I was under the impression that they would be 'absorbed' into one element.
If we don't 'absorb' the dupliactes, then $\displaystyle |A_2+A_3+\ldots+A_p| = |A_2|\cdot|A_3|\cdots|A_p| = 2^{p-1}$.

7. Some typo that I made!

Need to prove:

$\displaystyle |A_1+A_2+A_3+...+A_p|={p}$

Is it still $\displaystyle |A_1+A_2+A_3+...+A_p|=2^{p}$
in $\displaystyle \mathbb{Z}_p$?

8. Originally Posted by Also sprach Zarathustra

Need to prove:

$\displaystyle |A_1+A_2+A_3+...+A_p|={p}$

Is it still $\displaystyle |A_1+A_2+A_3+...+A_p|=2^{p}$
in $\displaystyle \mathbb{Z}_p$?
It would still be $\displaystyle 2^{p-1}$ since $\displaystyle |A_1|=1$.

Suppose $\displaystyle p=3$ and $\displaystyle A_1=\{a\}, \; A_2 = \{b,c\}, \; A_3=\{d,e\}$,

then $\displaystyle A_1+A_2 = \{a+b,a+c\} \implies A_1+A_2+A_3 = \{a+b+d,a+b+e,a+c+d,a+c+e\}$.

Hence $\displaystyle |A_1+A_2+A_3| = 4 = 2^{3-1}$.

So this is why I think we need to 'absorb' identical elements into one, which would limit $\displaystyle |A_1+A_2+A_3|$ to at most $\displaystyle 3$.