zero-sum problem

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.{{cite journal | zbl=0063.00009 | last1=Erdős | first1=Paul | last2=Ginzburg | first2=A. | last3=Ziv | first3=A. | title=Theorem in the additive number theory | journal=Bull. Res. Council Israel | volume=10F | pages=41–43 | year=1961 }} They proved that for the group $\mathbb{Z}/n\mathbb{Z}$ of integers modulo n,

$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.Nathanson (1996) p.48

More general results than this theorem exist, such as Olson's theorem, Kemnitz's conjecture (proved by Christian Reiher in 2003{{Citation |last=Reiher |first=Christian |title=On Kemnitz' conjecture concerning lattice-points in the plane |journal=The Ramanujan Journal |volume=13 |issue=1–3 |year=2007 |doi=10.1007/s11139-006-0256-y |pages=333–337 | zbl=1126.11011 |arxiv=1603.06161 |s2cid=119600313 }}.), and the weighted EGZ theorem (proved by David J. Grynkiewicz in 2005{{Citation |last=Grynkiewicz |first=D. J. |title=A Weighted Erdős-Ginzburg-Ziv Theorem |journal=Combinatorica |volume=26 |issue=4 |pages=445–453 |year=2006 |doi=10.1007/s00493-006-0025-y | zbl=1121.11018 |s2cid=33448594 |url=http://diambri.org/Mathpdfs/caroconjv5.pdf }}.).

References

{{cite book | last=Geroldinger | first=Alfred | chapter=Additive group theory and non-unique factorizations | pages=[https://archive.org/details/combinatorialnum00gero_834/page/n13 1]–86 | editor1-last=Geroldinger | editor1-first=Alfred | editor2-last=Ruzsa | editor2-first=Imre Z. | others=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) | title=Combinatorial number theory and additive group theory | url=https://archive.org/details/combinatorialnum00gero_834 | url-access=limited | series=Advanced Courses in Mathematics CRM Barcelona | location=Basel | publisher=Birkhäuser | year=2009 | isbn=978-3-7643-8961-1 | zbl=1221.20045 }}
{{cite book | first=Melvyn B. | last=Nathanson | title=Additive Number Theory: Inverse Problems and the Geometry of Sumsets | volume=165 | series=Graduate Texts in Mathematics | publisher=Springer-Verlag | year=1996 | isbn=0-387-94655-1 | zbl=0859.11003 }}

External links

{{springer|title=Erdös-Ginzburg-Ziv theorem|id=p/e110100}}
PlanetMath [https://web.archive.org/web/20120805174718/http://planetmath.org/encyclopedia/ErdHosGinzburgZivTheorem.html Erdős, Ginzburg, Ziv Theorem]
Sun, Zhi-Wei, [http://math.nju.edu.cn/~zwsun/csz.htm "Covering Systems, Restricted Sumsets, Zero-sum Problems and their Unification"]

zero-sum problem

See also

References

External links

Further reading