Name
Abstract | ||
|---|---|---|
An old conjecture of Graham stated that if n is a prime and S is a sequence of n terms from the cyclic group C"n such that all (nontrivial) zero-sum subsequences have the same length, then S must contain at most two distinct terms. In 1976, Erdos and Szemeredi gave a proof of the conjecture for sufficiently large primes n. However, the proof was complicated enough that the details for small primes were never worked out. Both in the paper of Erdos and Szemeredi and in a later survey by Erdos and Graham, the complexity of the proof was lamented. Recently, a new proof, valid even for non-primes n, was given by Gao, Hamidoune and Wang, using Savchev and Chen's recently proved structure theorem for zero-sum free sequences of long length in C"n. However, as this is a fairly involved result, they did not believe it to be the simple proof sought by Erdos, Graham and Szemeredi. In this paper, we give a short proof of the original conjecture that uses only the Cauchy-Davenport Theorem and pigeonhole principle, thus perhaps qualifying as a simple proof. Replacing the use of the Cauchy-Davenport Theorem with the Devos-Goddyn-Mohar Theorem, we obtain an alternate proof, albeit not as simple, of the non-prime case. Additionally, our method yields an exhaustive list detailing the precise structure of S and works for an arbitrary finite abelian group, though the only non-cyclic group for which the hypotheses are non-void is C"2@?C"2"m. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.ejc.2011.06.004 | Eur. J. Comb. |
Keywords | Field | DocType |
cauchy-davenport theorem,simple proof,non-primes n,large primes n,new proof,alternate proof,short proof,arbitrary finite abelian group,devos-goddyn-mohar theorem,n term,cyclic group,number theory | Structured program theorem,Analytic proof,Prime (order theory),Discrete mathematics,Abelian group,Combinatorics,Cyclic group,Furstenberg's proof of the infinitude of primes,Conjecture,Mathematics,Pigeonhole principle | Journal |
Volume | Issue | ISSN |
32 | 8 | 0195-6698 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David J. Grynkiewicz | 1 | 42 | 10.33 |