In
additive number theory and
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, a restricted sumset has the form
:
where
are finite
nonempty
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other t ...
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s of a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
''F'' and
is a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
over ''F''.
If
is a constant non-zero function, for example
for any
, then
is the usual
sumset which is denoted by
if
When
:
''S'' is written as
which is denoted by
if
Note that , ''S'', > 0 if and only if there exist
with
Cauchy–Davenport theorem
The Cauchy–Davenport theorem, named after
Augustin Louis Cauchy and
Harold Davenport, asserts that for any
prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
''p'' and nonempty subsets ''A'' and ''B'' of the prime
order
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...
cyclic group we have the
inequality[Geroldinger & Ruzsa (2009) pp.141–142]
:
where
, i.e. we're using
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book ...
.
We may use this to deduce the
Erdős–Ginzburg–Ziv theorem 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'' suc ...
: given any sequence of 2''n''−1 elements in the cyclic group
, there are ''n'' elements that sum to zero modulo ''n''. (Here ''n'' does not need to be prime.)
[Geroldinger & Ruzsa (2009) p.53]
A direct consequence of the Cauchy-Davenport theorem is: Given any sequence ''S'' of ''p''−1 or more nonzero elements, not necessarily distinct, of
, every element of
can be written as the sum of the elements of some subsequence (possibly empty) of ''S''.
Kneser's theorem generalises this to general
abelian group
In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commut ...
s.
[Geroldinger & Ruzsa (2009) p.143]
Erdős–Heilbronn conjecture
The Erdős–Heilbronn conjecture posed by
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 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 ...
and
Hans Heilbronn
Hans Arnold Heilbronn (8 October 1908 – 28 April 1975) was a mathematician.
Education
He was born into a German-Jewish family. He was a student at the universities of Berlin, Freiburg and Göttingen, where he met Edmund Landau, who supervised ...
in 1964 states that
if ''p'' is a prime and ''A'' is a nonempty subset of the field Z/''p''Z. This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994
who showed that
:
where ''A'' is a finite nonempty subset of a field ''F'', and ''p''(''F'') is a prime ''p'' if ''F'' is of
characteristic ''p'', and ''p''(''F'') = ∞ if ''F'' is of characteristic 0. Various extensions of this result were given by
Noga Alon, M. B. Nathanson and
I. Ruzsa in 1996,
Q. H. Hou and
Zhi-Wei Sun
Sun Zhiwei (, born October 16, 1965) is a Chinese mathematician, working primarily in number theory, combinatorics, and group theory. He is a professor at Nanjing University.
Biography
Sun Zhiwei was born in Huai'an, Jiangsu. Sun and his twi ...
in 2002,
and G. Karolyi in 2004.
Combinatorial Nullstellensatz
A powerful tool in the study of lower bounds for
cardinalities of various restricted sumsets is the following fundamental principle: the combinatorial
Nullstellensatz.
Let
be a polynomial over a field
. Suppose that the
coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves var ...
of the
monomial
In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered:
# A monomial, also called power product, is a product of powers of variables with nonnegative integer exponent ...
in
is nonzero and
is the
total degree of
. If
are finite subsets of
with
for
, then there are
such that
.
The method using the combinatorial Nullstellensatz is also called the polynomial method. This tool was rooted in a paper of
N. Alon and M. Tarsi in 1989,
and developed by Alon, Nathanson and Ruzsa in 1995–1996,
and reformulated by Alon in 1999.
See also
*
Polynomial method in combinatorics In mathematics, the polynomial method is an algebraic approach to combinatorics problems that involves capturing some combinatorial structure using polynomials and proceeding to argue about their algebraic properties. Recently, the polynomial method ...
References
*
*
External links
*{{mathworld , urlname = Erdos-HeilbronnConjecture , title = Erdős-Heilbronn Conjecture
Augustin-Louis Cauchy
Sumsets
Additive combinatorics
Additive number theory