number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

, zero-sum problems are certain kinds of

combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

problems about the structure of a finite abelian group. Concretely, given a finite abelian group ''G'' and a positive

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

''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. They proved that for the group

\mathbb/n\mathbb

of integers

modulo In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation. Given two positive numbers and , mo ...

''n'',

k = 2n - 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'', 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.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), and the weighted EGZ theorem (proved by David J. Grynkiewicz in 2005.).

References

* *

External links

* * PlanetMat
Erdős, Ginzburg, Ziv Theorem
* Sun, Zhi-Wei
"Covering Systems, Restricted Sumsets, Zero-sum Problems and their Unification"

See also

References

External links

Further reading