In
additive combinatorics
Additive combinatorics is an area of combinatorics in mathematics. One major area of study in additive combinatorics are ''inverse problems'': given the size of the sumset is small, what can we say about the structures of and ? In the case of th ...
, the sumset (also called the
Minkowski sum
In geometry, the Minkowski sum of two sets of position vectors ''A'' and ''B'' in Euclidean space is formed by adding each vector in ''A'' to each vector in ''B'':
A + B = \
The Minkowski difference (also ''Minkowski subtraction'', ''Minkowsk ...
) of two
subset
In mathematics, a 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 a ...
s
and
of an
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 commu ...
(written additively) is defined to be the set of all sums of an element from
with an element from
. That is,
:
The
-fold iterated sumset of
is
:
where there are
summands.
Many of the questions and results of additive combinatorics and
additive number theory
Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigro ...
can be phrased in terms of sumsets. For example,
Lagrange's four-square theorem
Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number, nonnegative integer can be represented as a sum of four non-negative integer square number, squares. That is, the squares form an additive basi ...
can be written succinctly in the form
:
where
is the set of
square number
In mathematics, a square number or perfect square is an integer that is the square (algebra), square of an integer; in other words, it is the multiplication, product of some integer with itself. For example, 9 is a square number, since it equals ...
s. A subject that has received a fair amount of study is that of sets with ''small doubling'', where the size of the set
is small (compared to the size of
); see for example
Freiman's theorem.
See also
*
Restricted sumset
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 ...
*
Sidon set
*
Sum-free set
In additive combinatorics and number theory, a subset ''A'' of an abelian group ''G'' is said to be sum-free if the sumset ''A'' + ''A'' is disjoint from ''A''. In other words, ''A'' is sum-free if the equation a + b = c has no solution with a,b, ...
*
Schnirelmann density
*
Shapley–Folkman lemma
The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of set (mathematics), sets in a vector space. The lemma may be intuitively understood as saying that, if the number of summed sets exceeds the dime ...
*
X + Y sorting
X, or x, is the twenty-fourth Letter (alphabet), letter of the Latin alphabet, used in the English alphabet, modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is Wikt:ex#En ...
References
*
*
*
*Terence Tao and Van Vu, ''Additive Combinatorics'', Cambridge University Press 2006.
External links
*
{{algebra-stub