Note on a conjecture of Graham

DOI10.1016/J.EJC.2011.06.004zbMATH Open1262.11007DBLPjournals/ejc/Grynkiewicz11arXiv0903.3200OpenAlexW2074498946WikidataQ39822551 ScholiaQ39822551MaRDI QIDQ648989FDOQ648989

Authors: David J. Grynkiewicz 

Publication date: 29 November 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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, ErdH{o}s 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 ErdH{o}s and Szemeredi and in a later survey by ErdH{o}s 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 ErdH{o}s, 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 this is nontrivial is $C_{2}oplus{C}_{2m}$.

Full work available at URL: https://arxiv.org/abs/0903.3200

Recommendations

• Distinct length modular zero-sum subsequences: a proof of Graham's conjecture
• The Proof of a Conjecture of Graham for Sequences Containing Primes
• A generalization of Graham's conjecture
• scientific article; zbMATH DE number 3544151
• On zero-sum subsequences of restricted size

zbMATH Keywords

cyclic groupzero-sum subsequences

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Sequences (mod (m)) (11B50) Finite abelian groups (20K01)

Cites Work

• Additive combinatorics
• Title not available (Why is that?)
• Non-unique factorizations. Algebraic, combinatorial and analytic theory
• Title not available (Why is that?)
• Long zero-free sequences in finite cyclic groups.
• Title not available (Why is that?)
• Zero-sum problems in finite Abelian groups: a survey
• On a partition analog of the Cauchy-Davenport Theorem
• A generalization of Kneser's addition theorem
• On some developments of the Erdős–Ginzburg–Ziv Theorem II
• On the Addition of Residue Classes
• Title not available (Why is that?)
• Distinct length modular zero-sum subsequences: a proof of Graham's conjecture
• Title not available (Why is that?)
• Representation of finite abelian group elements by subsequence sums

Cited In (15)

• Title not available (Why is that?)
• Concerning a conjecture of R. L. Graham
• On the existence of zero-sum subsequences of distinct lengths
• On a Conjecture of Graham
• On a theorem of Graham
• Long sequences having no two nonempty zero-sum subsequences of distinct lengths
• Notes on Glaisher's congruences
• Title not available (Why is that?)
• Distinct length modular zero-sum subsequences: a proof of Graham's conjecture
• On a conjecture of R. L. Graham
• Representing sequence subsums as sumsets of near equal sized sets
• Iterated sumsets and setpartitions
• A generalization of Graham's conjecture
• Zero-sum subsequences of distinct lengths
• On the lower bounds of Davenport constant

This page was built for publication: Note on a conjecture of Graham

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648989)