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
In geometry, the Minkowski sum (also known as dilation) 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'', i.e., the set
: A + B = \.
Analogously, the Minkowsk ...
) 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 com ...
(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
Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares. That is, the squares form an additive basis of order four.
p = a_0^2 + a_1^2 + a_2^2 + a_3 ...
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.
See also
*
Restricted sumset
*
Sidon set
*
Sum-free set
*
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 comparis ...
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
Computer science is the study of computation, automation, and i ...
, language=en