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 any sequence of elements of "G" with length $k$ contains "n" terms that sum to 0.

In 1961 Paul Erdős, A. Ginzburg, and A. Ziv proved the general result for $mathbb\{Z\}/nmathbb\{Z\}$ (the integers mod n) that

:"k" = 2"n" − 1.

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". This result is generally known as the EGZ theorem after its discoverers.

More general results than this theorem exist, such as Olson's theorem, Kemnitz's conjecture (proved by C. Reiher in 2003), and the weighted EGZ theorem (proved by D. J. Grynkiewicz in 2005).

References

*Sun, Zhi-Wei, [http://math.nju.edu.cn/~zwsun/csz.htm "Covering Systems, Restricted Sumsets, Zero-sum Problems and their Unification"]

External links

* PlanetMath [http://planetmath.org/encyclopedia/ErdHosGinzburgZivTheorem.html Erdős, Ginzburg, Ziv Theorem]
* The EGZT in the Hungarian Wikipedia
* Zhi-Wei Sun: " [http://math.nju.edu.cn/~zwsun/zerosum.pdf On zero-sum problems] "
* Zhi-Wei Sun: " [http://math.nju.edu.cn/~zwsun/Cover-Zerosum.pdf Covering systems and their connections to zero-sums] " (PDF) An article about the relation of covering systems and zero-sum problems