Zero-sum problem
In number theory, zero-sum problems are a certain class of combinatorial questions. In general, a finite abelian group G is considered. The zero-sum problem for the integer n is the following: Find the smallest integer k such that every sequence of elements of G with length contains n terms that sum to 0.
In 1961 Paul Erdős, Abraham Ginzburg, and Abraham Ziv proved the general result for (the integers mod n) that[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. This result is known as the Erdős–Ginzburg–Ziv theorem after its discoverers: it may 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]).
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, doi:10.1007/s11139-006-0256-y, Zbl 1126.11011.
- ^ Grynkiewicz, D. J. (2006), "A Weighted Erdős-Ginzburg-Ziv Theorem", Combinatorica, 26 (4): 445–453, doi:10.1007/s00493-006-0025-y, Zbl 1121.11018.
- Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. Vol. 165. Springer-Verlag. ISBN 0-387-94655-1. Zbl 0859.11003.