# Zero-sum problem

(Redirected from Erdős–Ginzburg–Ziv theorem)

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

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

$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. This result is known as the Erdős–Ginzburg–Ziv theorem after its discoverers: it may 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]).