Zero-sum problem explained

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

Z/nZ

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

See also

References

External links

Further reading

Notes and References

  1. 0063.00009 . Erdős . Paul . Ginzburg . A. . Ziv . A. . Theorem in the additive number theory . Bull. Res. Council Israel . 10F . 41–43 . 1961 .
  2. Nathanson (1996) p.48
  3. .
  4. .