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 Minkowski ...
) 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 commut ...
(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 semigr ...
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_ ...
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
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
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, f ...
*
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,c ...
*
Schnirelmann density
In additive number theory, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician Lev Schnirelmann, who was the first to study it.Schnirelmann, L.G. (1930).On the ...
*
Shapley–Folkman lemma
The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ros ...
*
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.
''Undark Magazine'' described ''Quanta Magazine'' as "highly regarded for ...
, language=en