Sumset ($A+B$)

For finite sets $A,B\subseteq G$ in an abelian group $G$, their sumset isEach distinct value occurs only once in this set, even if many ordered pairs produce it. When $B=A$, repetitions are allowed: $a+a$ belongs to $A+A$. For the two integer sets introduced above,For $A$, the value $3$ comes from $(0,3),(1,2),(2,1),(3,0)$. For $B$, two ordered pairs give the same sum only when one reverses the other, apart from a pair being identical to itself. Thus its four pairs $(b,b)$ and six pairs with distinct members, counted without regard to order, produce ten distinct sums.

Every nonempty finite set of integers $S\subseteq \mathbb{Z}$ satisfies $|S+S|\ge 2|S|-1$. To see this, list its members as $s_1<\cdots <s_n$. The $2n-1$ distinct sumsall belong to $S+S$. A nonconstant arithmetic progression attains this bound. The ordered list is essential: in the cyclic group $\mathbb{Z}/6\mathbb{Z}$, the subgroup $H=\{0,2,4\}$ instead satisfies $H+H=H$, of cardinality three. Addition wraps around, for example $4+4=2$ in this group.

For finite sets $A,B\subseteq G$ in an abelian group $G$, the sumset representation function isIt counts ordered pairs in the Cartesian product, so $(a,b)$ and $(b,a)$ are different when $a\ne b$, even though commutativity makes their sums equal. It is zero outside the sumset, andFor $A=\{0,1,2,3\}$, its values at $s=0,1,\dots ,6$ are $1,2,3,4,3,2,1$. For $B=\{0,1,4,10\}$, its values at the increasing elements of $B+B$ are $1,2,1,2,2,1,2,2,2,1$. Both lists total sixteen, but the first concentrates more ordered pairs on fewer sums. This distinction is what additive energy quantifies.

For a subset $A$ of density $\alpha$ in a finite cyclic group, put $F=1_A\ast 1_A\ast 1_A$ using normalized convolution on a finite group. Its average is ${\alpha }^3$, so choose $t_0$ with $F(t_0)\ge {\alpha }^3$. Retain the large spectrum where $|\widehat{1_A}|\ge {\alpha }^2/8$. The Parseval identity on a finite group gives at most $64{\alpha }^{-3}$ frequencies. Their phases change by at most $\alpha /4$ on the associated Bohr set, contributing at most ${\alpha }^3/4$ to the change of $F$. The discarded frequencies contribute at most another ${\alpha }^3/4$, since $\sum |\widehat{1_A}{|}^2=\alpha$. Therefore $F(t_0+b)\ge {\alpha }^3/2>0$ on the Bohr set, proving the containment.

For fixed positive density $\delta$, every sufficiently large $A\subseteq [1,N]$ of size at least $\delta N$ has a long arithmetic progression in its triple sumset. Embed it in $\mathbb{Z}/(8N)\mathbb{Z}$, where its density is at least $\delta /8$. A translated Bohr neighborhood in a triple sumset has bounded rank and fixed positive radius depending only on $\delta$. A torus pigeonhole principle argument supplies a nonzero step whose small multiples stay in the Bohr set, with polynomially many multiples. All resulting residues have representatives in $[3,3N]$, an interval shorter than half the modulus, so their successive ordinary integer differences agree and give an actual integer arithmetic progression. The positive constant prefactor is absorbed by reducing the exponent for sufficiently large $N$.

Given numbers $s_1,\dots ,s_n$, the sum associated with a subset $A$ of indices is ${\sum }_{i\in A}{s}_i$. The empty subset gives zero. The set of all these values is the sumset $\{0,s_1\}+\cdots +\{0,s_n\}$.

For $0<s_1<\cdots <s_n$, adding the largest integer creates at least $n$ new sums of subsets. If $P={\sum }_{i<n}{s}_i$ is the previous maximum, the values $P+s_n$ and $P+s_n-s_i$ for $i<n$ are distinct new sums above $P$. Induction gives the displayed bound. Equality holds for $s_i=i$, whose subset sums fill the interval of integers from zero to $n(n+1)/2$.

Represent each element of $S_1+\cdots +S_n$ by the lexicographically least tuple with that sum. Every coordinate projection of the resulting tuple set is itself lexicographically least for its partial sum: replacing it by a smaller representative would improve the original tuple without changing its sum. Consequently projected cardinalities are at most the corresponding partial sumset cardinalities. Projection inequalities, including the box theorem, therefore give sumset inequalities.

For finite sets in an abelian group and a bipartite graph $\Gamma \subseteq A\times B$, the restricted sumset is $\{a+b:(a,b)\in \Gamma \}$. It retains only sums corresponding to graph edges.

For nonempty finite subsets $A,B$ of an abelian group, $|A+B|\le K|A|$ implies that some nonempty $X\subseteq A$ satisfies this bound simultaneously for every integer $m\ge 0$, with $0B=\{0\}$. The Petridis minimal-growth lemma proves this by choosing $X$ to minimize $|X+B|/|X|$. The Ruzsa triangle inequality then gives the Plünnecke-Ruzsa inequality $|kB-\ell B|\le K^{k+\ell }|A|$.

For a nonnegative integer $m$, the iterated sumset $mA$ is the sum of $m$ copies of $A$, with $0A=\{0\}$. Repetitions are allowed, so its elements are sums $a_1+\cdots +a_m$ with each $a_i\in A$.