In number theory, zero-sum problems are certain kinds of combinatorial problems about the structure of a finite abelian group. Concretely, given a finite abelian group G and a positive integer n, one asks for the smallest value of k such that every sequence of elements of G of size k contains n terms that sum to 0.
The classic result in this area is the 1961 theorem of Paul Erdős, Abraham Ginzburg, and Abraham Ziv.[1] They proved that for the group \( \mathbb {Z} /n\mathbb {Z} \) of integers modulo n,
\( {\displaystyle k=2n-1.} \)
Explicitly this says that any multiset of 2n − 1 integers has a subset of size n the sum of whose elements is a multiple of n, but that the same is not true of multisets of size 2n − 2. (Indeed, the lower bound is easy to see: the multiset containing n − 1 copies of 0 and n − 1 copies of 1 contains no n-subset summing to a multiple of n.) This result is known as the Erdős–Ginzburg–Ziv theorem after its discoverers. It may also be deduced from the Cauchy–Davenport theorem.[2]
More general results than this theorem exist, such as Olson's theorem, Kemnitz's conjecture (proved by Christian Reiher in 2003[3]), and the weighted EGZ theorem (proved by David J. Grynkiewicz in 2005[4]).
See also
Davenport constant
Subset sum problem
References
Erdős, Paul; Ginzburg, A.; Ziv, A. (1961). "A theorem in additive number theory". Bull. Res. Council Israel. 10F: 41–43. Zbl 0063.00009.
Nathanson (1996) p.48
Reiher, Christian (2007), "On Kemnitz' conjecture concerning lattice-points in the plane", The Ramanujan Journal, 13 (1–3): 333–337, arXiv:1603.06161, doi:10.1007/s11139-006-0256-y, Zbl 1126.11011.
Grynkiewicz, D. J. (2006), "A Weighted Erdős-Ginzburg-Ziv Theorem" (PDF), Combinatorica, 26 (4): 445–453, doi:10.1007/s00493-006-0025-y, Zbl 1121.11018.
Geroldinger, Alfred (2009). "Additive group theory and non-unique factorizations". In Geroldinger, Alfred; Ruzsa, Imre Z. (eds.). Combinatorial number theory and additive group theory. Advanced Courses in Mathematics CRM Barcelona. Elsholtz, C.; Freiman, G.; Hamidoune, Y. O.; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Solymosi, J.; Stanchescu, Y. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse). Basel: Birkhäuser. pp. 1–86. ISBN 978-3-7643-8961-1. Zbl 1221.20045.
Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. 165. Springer-Verlag. ISBN 0-387-94655-1. Zbl 0859.11003.
External links
"Erdős-Ginzburg-Ziv theorem", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
PlanetMath Erdős, Ginzburg, Ziv Theorem
Sun, Zhi-Wei, "Covering Systems, Restricted Sumsets, Zero-sum Problems and their Unification"
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
