Results 1 to 8 of 8

Thread: Erdos-Ginzburg-Ziv Theorem...

  1. #1
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    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$


    Please help.
    Last edited by Also sprach Zarathustra; Jan 3rd 2011 at 12:28 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Also sprach Zarathustra View Post
    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$


    Please help.
    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}? $
    Last edited by chiph588@; Jan 3rd 2011 at 09:42 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by chiph588@ View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Also sprach Zarathustra View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    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....
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by chiph588@ View Post
    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} $.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    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
    $?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Also sprach Zarathustra View Post
    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
    $?
    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 $.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Erdos-Szekeres Theorem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 6th 2010, 02:18 PM
  2. Erdos-Szekeres theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jun 25th 2010, 07:07 PM
  3. Erdos Ginzburg Ziv Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 7th 2010, 09:09 PM
  4. Erdos-Szekeres generalization
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Dec 18th 2009, 02:35 AM
  5. Erdos-Szekeres variation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Dec 17th 2009, 02:22 PM

Search Tags


/mathhelpforum @mathhelpforum