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 Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...

Abraham Ginzburg Abraham Ginzburg (Hebrew: אברהם גינזבורג) (1926–2020) was a Professor Emeritus of Computer Science. He served as Vice President of the Technion Institute, and President of the Open University of Israel. Biography Ginzburg was bo ...

, and

Abraham Ziv Abraham Ziv (; –) was an Israeli mathematician, known for his contributions to the Zero-sum problem as one of the discoverers of the Erdős–Ginzburg–Ziv theorem. Biography Abraham Zubkowski (later Ziv) was born in Avihayil to Haim and Zil ...

. 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 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 ...

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 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