# Math Help - Erdos-Ginzburg-Ziv Theorem...

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

Hello!

I have proved the following lemma:

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

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

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

By repeating process with the lemma I need to conclude:

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

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

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

2. Originally Posted by Also sprach Zarathustra
Hello!

I have proved the following lemma:

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

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

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

By repeating process with the lemma I need to conclude:

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

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

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

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

3. Originally Posted by chiph588@
Don't we know there are at most $\displaystyle p$ elements in the sum of these sets since we're working in $\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 $|A_2+A_3+...+A_p|> p
$
is impossible or $|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 $|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:

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

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

8. Originally Posted by Also sprach Zarathustra

Need to prove:

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

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

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

then $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 $|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 $|A_1+A_2+A_3|$ to at most $3$.