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 ''A'' + ''B'' is small, what can we say about the structures of A ...
, the sumset (also called the
Minkowski sum) of two subsets
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 comm ...
(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 can be phrased in terms of sumsets. For example,
Lagrange's four-square theorem 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 of an integer; in other words, it is the product of some integer with itself. For example, 9 is a square number, since it equals and can be written as .
The u ...
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
In additive combinatorics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if , A+A, /, A, is small, then A can be contained in a small generalized arithmetic p ...
.
See also
*
Restricted sumset
*
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
*
X + Y sorting
In computer science, \boldsymbol+\boldsymbol sorting is the problem of sorting pairs of numbers by their sums. Applications of the problem include transit fare minimisation, VLSI design, and sparse polynomial multiplication. As with compar ...
References
*
*
*
*Terence Tao and Van Vu, ''Additive Combinatorics'', Cambridge University Press 2006.
External links
* {{Cite web , last=Sloman , first=Leila , date=2022-12-06 , title=From Systems in Motion, Infinite Patterns Appear , url=https://www.quantamagazine.org/infinite-patterns-appear-in-numbers-described-as-moving-systems-20221205/ , website=
Quanta Magazine
''Quanta Magazine'' is an editorially independent online publication of the Simons Foundation covering developments in physics, mathematics, biology and computer science.
''Undark Magazine'' described ''Quanta Magazine'' as "highly regarded for ...
, language=en