imported>David Eppstein: see also Barycentric-sum problem

2025-05-12T02:07:36Z

New page

{{Short description|Mathematical 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 [[identity element|0]].

The classic result in this area is the 1961 theorem of [[Paul Erdős]], [[Abraham Ginzburg]], and [[Abraham Ziv]].<ref>{{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 }}</ref> They proved that for the group <math>\mathbb{Z}/n\mathbb{Z}</math> of integers [[modular arithmetic|modulo]] ''n'',

<math display=block>k = 2n - 1.</math>

Explicitly this says that any [[multiset]] of 2''n'' − 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 2''n'' − 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]].<ref name=N48>Nathanson (1996) p.48</ref>

More general results than this theorem exist, such as [[Olson's theorem]], [[Kemnitz's conjecture]] (proved by [[Christian Reiher]] in 2003<ref>{{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 }}.</ref>), and the [[weighted EGZ theorem]] (proved by [[David J. Grynkiewicz]] in 2005<ref>{{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 }}.</ref>).

==See also==
* [[Barycentric-sum problem]]
* [[Davenport constant]]
* [[Subset sum problem]]
* [[Zero-sum Ramsey theory]]

==References==
{{Reflist}}
* {{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.; [[József Solymosi |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]
* [[Zhi-Wei Sun|Sun, Zhi-Wei]], [http://math.nju.edu.cn/~zwsun/csz.htm "Covering Systems, Restricted Sumsets, Zero-sum Problems and their Unification"]

==Further reading==
* [https://reader.elsevier.com/reader/sd/pii/0012365X94003086?token=D07E2F4366DCB07436B2F9E8B77B86A934B887686F4DE8DD8F3100DCC0F2B468BF05D0B508A461498F7E0FEE721AB245&originRegion=us-east-1&originCreation=20230521193840 Zero-sum problems - A survey] (open-access journal article)
* [https://www.birs.ca/events/2019/5-day-workshops/19w5132 Zero-Sum Ramsey Theory: Graphs, Sequences and More] (workshop homepage)
* [[Arie Bialostocki]], "[https://link.springer.com/chapter/10.1007/978-94-011-2080-7_2 Zero-sum trees: a survey of results and open problems]" N.W. Sauer (ed.) R.E. Woodrow (ed.) B. Sands (ed.), ''Finite and Infinite Combinatorics in Sets and Logic'', ''Nato ASI Ser.'', Kluwer Acad. Publ. (1993) pp. 19–29
* Y. Caro, "[https://www.sciencedirect.com/science/article/pii/0012365X94003086 Zero-sum problems: a survey]" ''Discrete Math.'', '''152''' (1996) pp. 93–113
{{combin-stub}}
[[Category:Ramsey theory]]

[[Category:Combinatorics]]
[[Category:Paul Erdős]]
[[Category:Mathematical problems]]

Zero-sum problem - Revision history

imported>David Eppstein: see also Barycentric-sum problem