In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...
, 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
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
''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
of integers
modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is t ...
''n'',
Explicitly this says that any
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that ...
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
In additive number theory and combinatorics, a restricted sumset has the form
:S=\,
where A_1,\ldots,A_n are finite nonempty subsets of a field ''F'' and P(x_1,\ldots,x_n) is a polynomial over ''F''.
If P is a constant non-zero function, for ...
.
[Nathanson (1996) p.48]
More general results than this theorem exist, such as
Olson's theorem,
Kemnitz's conjecture (proved by
Christian Reiher
Christian Reiher (born 19 April 1984 in Starnberg) is a German mathematician. He is the fifth most successful participant in the history of the International Mathematical Olympiad, having won four gold medals in the years 2000 to 2003 and a br ...
in 2003), and the
weighted EGZ theorem (proved by
David J. Grynkiewicz in 2005
[.]).
See also
*
Davenport constant
*
Subset sum problem The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T''.'' ...
References
*
*
External links
* {{springer, title=Erdős-Ginzburg-Ziv theorem, id=p/e110100
* PlanetMat
Erdős, Ginzburg, Ziv Theorem*
Sun, Zhi-Wei"Covering Systems, Restricted Sumsets, Zero-sum Problems and their Unification"
Combinatorics
Paul Erdős
Mathematical problems