Results 1 to 8 of 8

Math Help - 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 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}<p and if a_i \neq a_{i+p-1} for all 1<i \leq p. Let us now define A_1=\{a_1\}, A_i=\{a_i,a_{i+p-1}\} for 1<i \leq p.

    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


    Please help.
    Last edited by Also sprach Zarathustra; January 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 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}<p and if a_i \neq a_{i+p-1} for all 1<i \leq p. Let us now define A_1=\{a_1\}, A_i=\{a_i,a_{i+p-1}\} for 1<i \leq p.

    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


    Please help.
    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}?
    Last edited by chiph588@; January 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 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?
    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 |A_2+A_3+...+A_p|> p<br />
is impossible or |A_2+A_3+...+A_p|\leq p<br />

    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  |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:

    |A_1+A_2+A_3+...+A_p|={p}<br />


    Is it still |A_1+A_2+A_3+...+A_p|=2^{p}
    in \mathbb{Z}_p<br />
?
    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:

    |A_1+A_2+A_3+...+A_p|={p}<br />


    Is it still |A_1+A_2+A_3+...+A_p|=2^{p}
    in \mathbb{Z}_p<br />
?
    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 .
    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: November 6th 2010, 02:18 PM
  2. Erdos-Szekeres theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 25th 2010, 07:07 PM
  3. Erdos Ginzburg Ziv Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 7th 2010, 09:09 PM
  4. Erdos-Szekeres generalization
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 18th 2009, 02:35 AM
  5. Erdos-Szekeres variation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 17th 2009, 02:22 PM

Search Tags


/mathhelpforum @mathhelpforum