# Zero-sum problem

## From Wikipedia, the free encyclopedia

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 of integers modulo *n*,

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.^{[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]}).

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.