×

Distinct length modular zero-sum subsequences: a proof of Graham’s conjecture. (English) Zbl 1203.11015

Let \(p\) be a prime, and let \(a_1, \ldots ,a_p\) be nonzero residues (mod \(p\)) such that, if \(\sum \varepsilon_ia_i\) (\(\varepsilon_i=0\) or 1, not all \(\varepsilon_i=0\)) is a multiple of \(p\), then \(\sum \varepsilon_i\) is uniquely determined. Under these conditions R. L. Graham conjectured that there are at most two distinct residues among the \(a_i\).
Such a conjecture can be reformulated in the following equivalent way.
Let \(n\) be a positive integer and let \(S\) be a sequence of \(n\) integers in the interval \([0,n-1]\). If there is an \(r\) such that any nonempty subsequence with sum \(\equiv 0\) \(\pmod n\) has length \(=r,\) then \(S\) has at most two distinct values.
With a sufficiently clear exposition this conjecture is proved by using S. Savchev and F. Chen’s structure theorem for zero-sum free sequences of long length in \(C_n\) [Discrete Math. 307, No. 22, 2671–2679 (2007; Zbl 1148.20038)].
The present authors offer a full theorem different from the previous partial proof supplied by P. Erdős and E. Szemerédi who verified the validity of Graham’s conjecture for all sufficiently large prime \(n\): P. Erdős and E. Szemerédi [Publ. Math. 23, 123–127 (1976; Zbl 0349.10046)].
With commendable honesty the three authors admit that, although based on elementary methods, their theorem proving seems too elaborate to be presented as the simple proof auspicated by P. Erdős, E. Szemerédi and R. L. Graham.
Nevertheless the Gao-Hamidoune-Wang Theorem is a bright page in the history of Combinatorial Number Theory.
A brief video summary of the paper is available on YouTube, JournalNumberTheory’s Channel. [http://www.youtube.com/watch?v=LftJj-E6aQA]

MSC:

11B50 Sequences (mod \(m\))
20D60 Arithmetic and combinatorial problems involving abstract finite groups
11B75 Other combinatorial number theory
05E15 Combinatorial aspects of groups and algebras (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Erdős, P.; Graham, R. L., Old and New Problems and Results in Combinatorial Number Theory, Monogr. Enseign. Math., vol. 28 (1980), Université de Genève, L’Enseignement Mathématique: Université de Genève, L’Enseignement Mathématique Geneva, 128 pp. (Reviewer: L.C. Eggan) · Zbl 0434.10001
[2] Erdős, P.; Heilbronn, H., On the addition of residue classes mod \(p\), Acta Arith., 9, 149-159 (1964) · Zbl 0156.04801
[3] Erdős, P.; Szemerédi, E., On a problem of Graham, Publ. Math. Debrecen, 23, 1-2, 123-127 (1976) · Zbl 0349.10046
[4] Geroldinger, A.; Halter-Koch, F., Non-unique Factorizations. Algebraic, Combinatorial and Analytic Theory, Pure Appl. Math. (Boca Raton), vol. 278 (2006), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, FL, xxii+700 pp · Zbl 1113.11002
[5] Savchev, S.; Chen, F., Long zero-free sequences in finite cyclic groups, Discrete Math., 307, 2671-2679 (2007) · Zbl 1148.20038
[6] Scherk, P., Distinct elements in a set of sums, Amer. Math. Monthly, 62, 46-47 (1955)
[7] Yuan, P. Z., On the index of minimal zero-sum sequences over finite cyclic groups, J. Combin. Theory Ser. A, 114, 1545-1551 (2007) · Zbl 1128.11011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.