Distinct length modular zero-sum subsequences: a proof of Graham's conjecture (Q977132): Difference between revisions

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 \textit{S. Savchev} and \textit{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\): \textit{P. Erdős} and \textit{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 \textit{simple proof} auspicated by P. Erdős, E. Szemerédi and R. L. Graham. Nevertheless the \textit{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. [\texttt{http://www.youtube.com/watch?v=LftJj-E6aQA}]