Chapter 33: Additive Combinatorics

What does a small sumset tell us about the original set?

Four elements generate sixteen ordered pairs, but those pairs need not generate sixteen different sums. Repeated sums reveal relations among the original elements. Additive combinatorics asks how many such relations force a set to resemble a progression, a subgroup, or a combination of these structures.

For the chapter foundation, work with nonempty finite subsets of an abelian group, written additively. Define $A+B=\{a+b:a\in A,b\in B\}$ and $A-B=\{a-b:a\in A,b\in B\}$. The doubling constant is $K=\lvert A+A\rvert/\lvert A\rvert$. The additive energy $E(A)$ counts ordered quadruples satisfying $a_1+a_2=a_3+a_4$. If $r(s)$ counts ordered pairs summing to $s$, then $E(A)=\sum_s r(s)^2$. The distinction between distinct sums and their multiplicities will drive the investigation.

Two tools suffice for the foundation comparison: Cauchy–Schwarz gives $E(A)\geq\lvert A\rvert^4/\lvert A+A\rvert$, and Fourier orthogonality on a finite group of order $N$ gives $E(A)=N^{-1}\sum_\chi\lvert\widehat{1_A}(\chi)\rvert^4$, using the unnormalized transform defined in 33.8. These are exact identities and bounds. The optional sections develop their structural consequences and proofs; the graduate extensions are not required to complete the foundation investigation.

33.1 Sumsets and difference sets

Optional extension; not required to complete the chapter foundation. Set addition combines all pairs and then forgets multiplicity. Its behavior depends both on the set and on the ambient group.

For an integer $m\geq1$, write $mA=A+\cdots+A$ with $m$ summands; set $0A=\{0\}$. This is not the same as the dilation $m\cdot A=\{ma:a\in A\}$, which uses one element repeatedly. Translation preserves doubling and energy: $(A+t)+(A+t)=(A+A)+2t$ and $(A+t)-(A+t)=A-A$. An additive bijective homomorphism preserves all additive equations. Multiplicative statistics generally change under translation.

For nonempty finite $A,B$, a fixed translate of each lies inside $A+B$, so $\lvert A+B\rvert\geq\max(\lvert A\rvert,\lvert B\rvert)$. In the integers, the stronger lower bound $\lvert A+B\rvert\geq\lvert A\rvert+\lvert B\rvert-1$ follows by arranging $a_1\lt\cdots\lt a_r$ and $b_1\lt\cdots\lt b_s$: the increasing chain

$$ a_1+b_1\lt a_2+b_1\lt\cdots\lt a_r+b_1 \lt a_r+b_2\lt\cdots\lt a_r+b_s $$

contains $r+s-1$ sums. Ordered-group reasoning does not transfer unchanged to a finite cyclic group.

Solved example. If $A=\{u,u+d,\ldots,u+(n-1)d\}\subseteq\mathbb Z$ with $d\neq0$, then $A+A$ has $2n-1$ elements and $A-A$ has $2n-1$ elements. Every sum corresponds to an index sum between zero and $2n-2$, and every difference to an index difference between $-(n-1)$ and $n-1$. For $A=\{1,2,3,4\}$, $2A=\{2,3,4,5,6,7,8\}$ but $2\cdot A=\{2,4,6,8\}$.

In $\mathbb Z/6\mathbb Z$, the subgroup $H=\{0,3\}$ satisfies $H+H=H$ and $H-H=H$. Its doubling constant is one. This is genuine subgroup structure, not an exception caused by an incorrect computation.

Exercise. Compute sums and differences for $\{0,1,4\}$ in the integers and modulo five. Hint: Reduce only after recording the integer possibilities. Solution: The integer sumset is $\{0,1,2,4,5,8\}$ and the difference set is $\{-4,-3,-1,0,1,3,4\}$. Modulo five both become all five residues. Relations can appear after reduction, so an embedding must be checked before transporting energy counts.

33.2 Cauchy–Davenport theorem

Optional extension; not required to complete the chapter foundation. In a prime cyclic group there are no proper nontrivial subgroups to account for unexpectedly small sumsets. Cauchy–Davenport quantifies that fact.

For a prime $p$ and nonempty $A,B\subseteq\mathbb F_p$,

$$ \lvert A+B\rvert\geq\min(p,\lvert A\rvert+\lvert B\rvert-1). $$

Here addition is modulo $p$; the field structure will enter the proof. Let $a=\lvert A\rvert$ and $b=\lvert B\rvert$. If $a+b\gt p$, every residue $t$ lies in $A+B$: the sets $A$ and $t-B$ must intersect. It remains to prove the unsaturated lower bound when $a+b\leq p$.

Polynomial proof. Assume for contradiction that $\lvert A+B\rvert\leq a+b-2$. Enlarge this sumset to a set $C\subseteq\mathbb F_p$ of size $d=a+b-2$, and put

$$ F(X,Y)=\prod_{c\in C}(X+Y-c). $$

This vanishes on $A\times B$. Its coefficient of $X^{a-1}Y^{b-1}$ is $\binom d{a-1}$, which is nonzero modulo $p$ because $d\lt p$.

The grid coefficient formula, valid for any polynomial of total degree at most $a+b-2$, is

$$ [X^{a-1}Y^{b-1}]F =\sum_{x\in A,y\in B} \frac{F(x,y)}{\prod_{x'\in A\setminus\{x\}}(x-x')\prod_{y'\in B\setminus\{y\}}(y-y')}. $$

All denominators are nonzero in the field. To justify the formula, apply one-variable Lagrange interpolation to monomials: the weighted evaluation sum vanishes for degrees below the corresponding set size minus one and equals one at that degree. For a bivariate monomial of total degree at most $d$, the only term surviving both tests is the target monomial. By linearity the formula follows. Its right side is zero because $F$ vanishes on the grid, contradicting the nonzero coefficient. This completes the proof.

Exercise. Take $A=\{0,1,2\}$ and $B=\{0,2,4\}$ in $\mathbb F_5$. Determine the sumset without enumerating every pair. Hint: Their sizes add to six. Solution: Since $3+3\gt5$, every translate $t-B$ intersects $A$, so $A+B=\mathbb F_5$. The saturation argument itself proves all five residues occur.

33.3 Kneser's addition theorem

Optional extension; not required to complete the chapter foundation. In a composite-order group, periodicity can compress a sumset. Kneser's theorem corrects the lower bound by identifying its stabilizing subgroup.

For a nonempty subset $S$ of a finite abelian group $G$, define $\operatorname{Stab}(S)=\{g\in G:S+g=S\}$. This is a subgroup: zero fixes $S$, translations compose, and an inverse translation also fixes it. A set fixed by a subgroup $H$ is a union of $H$-cosets.

For nonempty $A,B\subseteq G$ and $H=\operatorname{Stab}(A+B)$, Kneser's theorem states

$$ \lvert A+B\rvert\geq\lvert A+H\rvert+\lvert B+H\rvert-\lvert H\rvert. $$

Proof mechanism, with the main addition lemma omitted. Project to $G/H$. The image of $A+B$ has trivial stabilizer; any nontrivial stabilizing quotient translation would lift to a larger stabilizer upstairs. The aperiodic form of Kneser's theorem gives $\lvert\overline A+\overline B\rvert\geq\lvert\overline A\rvert+\lvert\overline B\rvert-1$. Multiplying by $\lvert H\rvert$ yields the displayed bound. Proving that aperiodic form requires a separate addition argument, usually an induction using set transforms; quotienting alone is not a proof of it.

Solved example. In $\mathbb Z/12\mathbb Z$, take $H=\{0,4,8\}$ and $A=B=H\cup(1+H)=\{0,1,4,5,8,9\}$. Then

$$ A+B=H\cup(1+H)\cup(2+H),\qquad \lvert A+B\rvert=9. $$

In the quotient $G/H\cong\mathbb Z/4\mathbb Z$, this is $\{0,1\}+\{0,1\}=\{0,1,2\}$. The latter has trivial stabilizer, so the original sumset's stabilizer is exactly $H$. Kneser's bound is $6+6-3=9$, attained. A naive Cauchy–Davenport substitution would give eleven and be false.

The diagram groups all twelve residues into their exact cosets. The left grid marks $A=B$, and the right grid marks their sumset. Each occupied quotient class contributes three original residues; the omitted class is $3+H$.

When $G$ has prime order, the stabilizer is either trivial or the whole group. The first case gives the unsaturated Cauchy–Davenport bound, and the second gives the whole group. Thus Kneser explains precisely the subgroup obstruction absent in prime order.

Exercise. In $\mathbb Z/8\mathbb Z$, let $A=B=\{0,2,4,6\}$. Find the stabilizer and compare Kneser's bound. Hint: The set is already a subgroup. Solution: $A+B=A$, its stabilizer is the same four-element subgroup, and the bound is $4+4-4=4$, attained. Counting cosets rather than individual residues makes the compression transparent.

33.4 Plünnecke inequalities

Optional extension; not required to complete the chapter foundation. Small one-step growth controls repeated addition, but the statement must specify whether the original set or a carefully chosen subset is being expanded.

For nonempty finite $A,B$ in an abelian group, if $\lvert A+B\rvert\leq K\lvert A\rvert$, there is a nonempty $X\subseteq A$ such that for every $m\geq0$,

$$ \lvert X+mB\rvert\leq K^m\lvert X\rvert. $$

A convenient proof chooses $X$ minimizing $\kappa=\lvert X+B\rvert/\lvert X\rvert$ among nonempty subsets of $A$. Then $\kappa\leq K$, and every subset $Y\subseteq X$ satisfies $\lvert Y+B\rvert\geq\kappa\lvert Y\rvert$, including the empty case.

For any finite nonempty $C=\{c_1,\ldots,c_t\}$, partition $X+C$ into the new portions of successive translates. Write $X_i=\{x\in X:x+c_i\notin X+\{c_1,\ldots,c_{i-1}\}\}$. The portions $X_i+c_i$ are disjoint and their sizes sum to $\lvert X+C\rvert$. The corresponding new portion of $X+B+c_i$ excludes $(X\setminus X_i)+B+c_i$, since that entire set already occurred. Therefore its size is at most

$$ \lvert X+B\rvert-\lvert(X\setminus X_i)+B\rvert \leq\kappa\lvert X_i\rvert. $$

Summing proves $\lvert X+B+C\rvert\leq\kappa\lvert X+C\rvert$. Induct with $C=(m-1)B$ to obtain the theorem. This is the minimal-growth mechanism developed in Petridis' primary proof.

Combining these estimates with the Ruzsa triangle inequality from 33.5 gives

$$ \lvert mB-nB\rvert\leq K^{m+n}\lvert A\rvert\qquad(m,n\geq0). $$

Indeed apply that triangle inequality with middle set $-X$, bounding the two sumsets $mB+X$ and $nB+X$, then divide by $\lvert X\rvert$. In particular small doubling $\lvert A+A\rvert\leq K\lvert A\rvert$ controls $mA-nA$. The subset theorem does not automatically assert $\lvert A+mB\rvert\leq K^m\lvert A\rvert$ for the original $A$.

Solved example. For $A=B=\{0,1,2,3\}\subseteq\mathbb Z$, $K=7/4$. Here $X=A$ works, and $X+mB=\{0,\ldots,3(m+1)\}$ has size $3m+4$. At $m=2$, the estimate gives $10\leq(7/4)^2\cdot4=49/4$. Also $2A-A=\{-3,\ldots,6\}$ has size ten, bounded by $(7/4)^3\cdot4=343/16$. These valid bounds need not be sharp.

Exercise. Apply the estimates when $A=B=H$ is a finite subgroup. Hint: $K=1$. Solution: Every positive iterated sumset is $H$, and every difference of positive iterates is $H$. Choose $X=H$; the estimates are equalities whenever the resulting set is $H$. For $m=n=0$ the result is $\{0\}$, of size one, still bounded by $\lvert H\rvert$.

33.5 Ruzsa distance and covering lemmas

Optional extension; not required to complete the chapter foundation. Ruzsa's inequalities compare additive growth through a third set, while covering turns a growth bound into a finite family of translates.

For nonempty finite $A,B,C$ in an abelian group, the triangle inequality is

$$ \lvert A-C\rvert\lvert B\rvert\leq\lvert A-B\rvert\lvert B-C\rvert. $$

Proof by injection. For each $z\in A-C$, fix one representation $z=a_z-c_z$. Map $(z,b)$ to $(a_z-b,b-c_z)$. Its coordinates sum to $z$, so the image determines $z$, then the fixed representative determines $b$. It is injective into $(A-B)\times(B-C)$, proving the inequality.

Define the Ruzsa distance

$$ d_R(A,B)=\log\frac{\lvert A-B\rvert}{\sqrt{\lvert A\rvert\lvert B\rvert}}. $$

It is symmetric, nonnegative, and satisfies a triangle inequality. Symmetry uses $\lvert A-B\rvert=\lvert B-A\rvert$; nonnegativity follows from the translate lower bounds; the triangle inequality is the logarithmic form of the injection bound. It is not an ordinary metric: $d_R(A,A)=\log(\lvert A-A\rvert/\lvert A\rvert)$ generally need not vanish.

The covering lemma says that if $\lvert A+B\rvert\leq K\lvert B\rvert$, there is $T\subseteq A$ with $\lvert T\rvert\leq K$ and

$$ A\subseteq T+(B-B). $$

Choose a maximal collection of disjoint translates $t+B$, $t\in T$. They lie inside $A+B$, so $\lvert T\rvert\lvert B\rvert\leq\lvert A+B\rvert$. Maximality means every $a+B$ intersects one of them, so $a=t+b'-b$. This proves the covering inclusion. “Maximal” means no further translate can be added; it need not be a largest collection.

Solved example. Take $A=\{0,1,2,3,4,5\}$ and $B=\{0,1,2\}$ in $\mathbb Z$. Then $\lvert A+B\rvert=8$, so $K=8/3$. Choose $T=\{0,3\}$, whose two translates of $B$ are disjoint. Every other allowed translate intersects one. Since $B-B=\{-2,-1,0,1,2\}$, the translates centered at zero and three cover $A$. Also for the interval $C=\{0,1,2,3\}$, $d_R(C,C)=\log(7/4)\gt0$.

Exercise. Prove that $\lvert A-A\rvert\leq\lvert A+B\rvert^2/\lvert B\rvert$. Hint: Use the middle set $-B$ in the triangle inequality. Solution: With the first and third sets both $A$, the factors are $\lvert A+B\rvert$ and $\lvert-B-A\rvert$, equal by negation. Dividing by $\lvert B\rvert$ gives the claim. This is an upper bound on a difference set, unlike the elementary lower bound from Cauchy–Schwarz energy.

33.6 Freiman's theorem

Optional extension; not required to complete the chapter foundation. Repeated-growth bounds predict structure, but a structure theorem must specify its ambient group and the form of the containing object.

A generalized arithmetic progression, or GAP, in $\mathbb Z$ is

$$ P=\{x_0+n_1v_1+\cdots+n_dv_d:0\leq n_i\lt L_i\}, $$

with integer parameters, positive integer lengths, and rank $d$. Its volume is $\prod_iL_i$. It is proper when the parameter map is injective on this box, so volume equals cardinality. Properness on the original box does not promise injectivity on a larger box such as the doubled one.

Freiman's theorem for integers states: for every $K\geq1$, there are constants $d(K),C(K)$ such that any nonempty finite $A\subseteq\mathbb Z$ with $\lvert A+A\rvert\leq K\lvert A\rvert$ is contained in a proper GAP of rank at most $d(K)$ and size at most $C(K)\lvert A\rvert$. The constants depend only on $K$, not on the location or diameter of $A$. This qualitative formulation makes no claim about best current quantitative dependence.

Proof sketch; prerequisites omitted. Ruzsa inequalities first control iterated sums and differences. A modeling step preserves additive relations in a bounded ambient model. Fourier arguments find a structured neighborhood inside an iterated difference set; covering and geometry of numbers then package that structure into a bounded-rank progression containing $A$. The modeling, structured-neighborhood, and progression-construction lemmas are substantial omitted steps. The elementary tools alone do not constitute a full proof. Green–Ruzsa's primary paper gives a structural theorem in arbitrary abelian groups, where the containing objects are coset progressions rather than just integer GAPs.

A Freiman isomorphism of order two is a bijection preserving, in both directions, equations $a_1+a_2=a_3+a_4$. It need not be a group homomorphism on the whole ambient group. It preserves sumset representation multiplicities and energy, making it suitable for modeling.

Solved example. Let $A=\{0,1,2,10,11,12\}$. It is exactly the proper rank-two progression $\{i+10j:0\leq i\leq2,\ 0\leq j\leq1\}$, of size six. Its sumset is the three disjoint blocks $\{0,\ldots,4\}$, $\{10,\ldots,14\}$, $\{20,\ldots,24\}$, so $K=15/6=5/2$. The coordinate map from the $3\times2$ grid preserves all two-term additive equations because the doubled coordinate box still maps injectively. The large gap between blocks does not destroy bounded-rank additive structure.

In a finite group, a subgroup can already have doubling one and arbitrarily large size. A coset progression includes such a subgroup together with a progression of quotient directions. Applying an integer-only formulation to arbitrary torsion groups would miss that component.

Exercise. For $L\geq3$, describe $A=\{0,1,L,L+1\}$ by a GAP and compute its doubling. Hint: Use two directions, one and $L$. Solution: The original $2\times2$ box is proper, and the sumset has three disjoint length-three blocks starting at $0,L,2L$. Hence $\lvert A+A\rvert=9$ and $K=9/4$. At $L=2$ the doubled blocks overlap, and the set is an interval with sumset size seven; the hypothesis on $L$ matters.

33.7 Additive energy

Optional extension; not required to complete the chapter foundation. Energy counts additive collisions rather than distinct outcomes. It is simultaneously a combinatorial count and a norm of a convolution.

For sets $A,B$, let $r_{A+B}(s)=\#\{(a,b)\in A\times B:a+b=s\}$. Define

$$ E(A,B)=\sum_s r_{A+B}(s)^2 =\#\{(a_1,a_2,b_1,b_2):a_1+b_1=a_2+b_2\}. $$

Write $E(A)=E(A,A)$. Rearranging the equation also gives $E(A)=\sum_t r_{A-A}(t)^2$. The ordered convention includes diagonal and trivial solutions; excluding them would define another statistic.

Since $\sum_s r_{A+B}(s)=\lvert A\rvert\lvert B\rvert$, Cauchy–Schwarz proves

$$ E(A,B)\geq\frac{\lvert A\rvert^2\lvert B\rvert^2}{\lvert A+B\rvert}. $$

For one set, $E(A)\leq\lvert A\rvert^3$, since three entries determine the fourth, which may or may not lie in $A$. Thus doubling at most $K$ implies $E(A)\geq\lvert A\rvert^3/K$. The converse for the whole set does not follow by reversing Cauchy–Schwarz.

Solved example. An integer interval of length $n$ has triangular sum multiplicities, so

$$ E(A)=n^2+2\sum_{j=1}^{n-1}j^2=\frac{2n^3+n}{3}. $$

For $n=4$ this is 44. The difference multiplicities are four at zero, three at each of $\pm1$, two at each of $\pm2$, and one at each of $\pm3$, giving the same answer. The lower bound is $4^4/7=256/7\lt44$; representation multiplicities are not uniform, so Cauchy–Schwarz is not an equality.

For the geometric progression $\{1,2,4,8\}$, all six positive pair differences are distinct. Zero has multiplicity four and the twelve nonzero differences have multiplicity one, giving $16+12=28$. This agrees with the sum-based count from the opening card.

Exercise. Compute energy of a finite subgroup $H$ and of a translate $x+H$. Hint: Every sum in the appropriate coset has $\lvert H\rvert$ representations. Solution: Both energies are $\lvert H\rvert^3$, attaining the upper bound. Translation moves the sum coset from $H$ to $2x+H$, but does not change multiplicities.

33.8 Fourier analysis on finite abelian groups

Optional extension; not required to complete the chapter foundation. Fourier characters convert convolution into pointwise multiplication and turn additive collisions into a fourth moment. Fix one normalization before using any identity.

Let $G$ be a finite abelian group of order $N$, and let $\widehat G$ be its characters $\chi:G\to\{z\in\mathbb C:\lvert z\rvert=1\}$. Use the unnormalized transform and convolution

$$ \widehat f(\chi)=\sum_{x\in G}f(x)\overline{\chi(x)},\qquad (f\ast g)(x)=\sum_{y\in G}f(y)g(x-y). $$

Orthogonality gives $\sum_{x\in G}\chi(x)\overline{\psi(x)}=N\delta_{\chi\psi}$. For a nontrivial character, translating the sum multiplies it by a value other than one, forcing zero. The character-basis theorem supplies $N$ characters; its finite-abelian-group classification argument is an omitted algebra prerequisite.

Consequently inversion, Parseval, and the convolution formula are

$$ f(x)=\frac1N\sum_\chi\widehat f(\chi)\chi(x),\qquad \sum_x\lvert f(x)\rvert^2=\frac1N\sum_\chi\lvert\widehat f(\chi)\rvert^2,\qquad \widehat{f\ast g}=\widehat f\,\widehat g. $$

The convolution identity follows by substituting $x=y+z$ and separating the two sums. Apply Parseval to $1_A\ast1_A=r_{A+A}$ to obtain

$$ E(A)=\frac1N\sum_\chi\lvert\widehat{1_A}(\chi)\rvert^4. $$

If $a=\lvert A\rvert$ and $\beta=\max_{\chi\neq1}\lvert\widehat{1_A}(\chi)\rvert$, the principal character contributes $a^4/N$, while Parseval gives $\sum_{\chi\neq1}\lvert\widehat{1_A}(\chi)\rvert^2=Na-a^2$. Hence

$$ \frac{a^4}{N}\leq E(A)\leq\frac{a^4}{N}+\beta^2\left(a-\frac{a^2}{N}\right). $$

A large excess above the baseline forces a large nonprincipal coefficient. This is a statement about bias toward a character, not by itself a theorem locating a containing progression.

Solved example. Return to $G=\mathbb Z/12\mathbb Z$ and $A=\{0,1,4,5,8,9\}$. For $\chi_k(x)=e^{2\pi ikx/12}$, only frequencies $k=0,3,6,9$ can be nonzero because $A$ is invariant under translation by four. Their transforms are respectively $6,3(1-i),0,3(1+i)$. Thus

$$ E(A)=\frac{6^4+2\cdot\lvert3(1-i)\rvert^4}{12} =\frac{1296+648}{12}=162. $$

Directly, each of the three residues in the sum cosets $H,1+H,2+H$ has respectively $3,6,3$ representations. Their squared sum is $3(9+36+9)=162$. Periodicity in physical space and restricted Fourier support describe the same structure.

Exercise. Use Fourier orthogonality to recover $E(H)=\lvert H\rvert^3$ for a subgroup. Hint: The transform is $\lvert H\rvert$ on characters trivial on $H$ and zero elsewhere. Solution: There are $N/\lvert H\rvert$ such characters, so the fourth-moment formula gives $N^{-1}(N/\lvert H\rvert)\lvert H\rvert^4=\lvert H\rvert^3$. A different Fourier normalization would require different powers of $N$.

33.9 Balog–Szemerédi–Gowers theorem

Optional extension; not required to complete the chapter foundation. High energy can come from a structured part of a set surrounded by irregular elements. The theorem extracts such a part rather than asserting a reverse Cauchy–Schwarz inequality for the whole set.

A polynomial-dependence form states that there are absolute constants $c\gt0$ and $C\geq1$ such that, for any nonempty finite $A$ in an abelian group and $K\geq1$, if $E(A)\geq\lvert A\rvert^3/K$, then some $A'\subseteq A$ satisfies

$$ \lvert A'\rvert\geq cK^{-C}\lvert A\rvert,\qquad \lvert A'+A'\rvert\leq CK^C\lvert A'\rvert. $$

The constants are deliberately not optimized. The polynomial improvement is part of Gowers' primary work; the formulation here concerns ordinary additive energy, not a higher-order Gowers norm.

Proof mechanism, with the graph extraction lemma omitted. Put $n=\lvert A\rvert$ and call a sum popular if its representation count is at least $n/(2K)$. Unpopular sums contribute at most $(n/(2K))\sum_s r(s)=n^3/(2K)$ to energy, so popular sums carry at least $n^3/(2K)$. Since every count is at most $n$, at least $n^2/(2K)$ ordered pairs have a popular sum. There are at most $2Kn$ popular sums, by the total pair count $n^2$.

Form a bipartite graph on two copies of $A$, joining pairs with popular sums. It is dense and its edge labels come from a controlled set. A combinatorial extraction lemma finds a substantial vertex subset with many short paths between pairs; writing differences as alternating combinations of path labels controls its difference set. Ruzsa and Plünnecke estimates convert this into small doubling. The extraction and path-counting lemmas are the substantive omitted steps; merely finding a dense graph is not yet the full theorem.

Solved example. The set $A=\{0,1,2,3,100,10000\}$ has sumset size eighteen and energy 82. Its interval core contributes 44; the eight core/outlier sums contribute $8\cdot2^2=32$; the two outlier diagonal sums contribute two; and the cross-outlier sum contributes four. With $K=6^3/82=108/41$, the energy hypothesis is an equality, but the whole-set doubling is three, larger than $K$. This explicitly rules out the false conclusion $\lvert A+A\rvert\leq K\lvert A\rvert$. The core $A'=\{0,1,2,3\}$ has size four and doubling $7/4$, illustrating the kind of extraction the theorem promises.

Combining BSG with Freiman's theorem describes a large structured subset of a high-energy integer set. The composition uses the extracted subset's doubling constant; it does not directly place the entire original set into the same progression.

Exercise. For $A=\{1,2,3,4\}$, verify an energy hypothesis with $K=2$ and exhibit a small-doubling subset. Hint: No extraction is necessary in this instance. Solution: $44\geq4^3/2=32$. Choose $A'=A$, whose doubling is $7/4$. This concrete witness verifies the example without knowing the unspecified universal constants or proving the general extraction theorem.

33.10 Sum-product phenomena

Optional extension; not required to complete the chapter foundation. Additive structure and multiplicative structure are usually incompatible in the real numbers. The ambient algebra is crucial: finite fields contain subfields and saturation phenomena that can obstruct naive growth statements.

For a finite set $A$ in a field, write $AA=\{ab:a,b\in A\}$. For positive real $A$, multiplicative energy is

$$ E_\times(A)=\#\{(a,b,c,d)\in A^4:ab=cd\} =\sum_t r_{AA}(t)^2\geq\frac{\lvert A\rvert^4}{\lvert AA\rvert}. $$

Positivity permits division and geometric ordering. Rearranging multiplicative equations also expresses this energy through repeated ratios. It is distinct from additive energy; the symbols and ambient operations must remain explicit.

A classical theorem of Solymosi gives, for finite positive real sets of size at least two and an absolute constant $c\gt0$,

$$ \lvert A+A\rvert^2\lvert AA\rvert \geq c\frac{\lvert A\rvert^4}{\log(2\lvert A\rvert)}. $$

It follows that at least one of the two sets has size at least $c'\lvert A\rvert^{4/3}/\log(2\lvert A\rvert)^{1/3}$. This is a proved classical bound, not a claim about the current record.

Proof sketch; geometric counting details omitted. Regard $A\times A$ as points on rays through the origin, whose slopes are ratios from $A/A$. Divide rays into classes with comparable numbers of points. Sums of points on two distinct rays have unique decompositions along those rays; for consecutive selected slopes, their sums occupy disjoint angular sectors inside $(A+A)\times(A+A)$. Counting these points bounds multiplicative energy by a constant times $\lvert A+A\rvert^2\log(2\lvert A\rvert)$. Combine with the energy lower bound above. The dyadic selection and endpoint handling are the omitted details, and the order/positivity assumptions are used essentially in this argument.

Solved example. For $A=\{1,2,3,4\}$, $\lvert A+A\rvert=7$ and

$$ AA=\{1,2,3,4,6,8,9,12,16\},\qquad\lvert AA\rvert=9. $$

For $B=\{1,2,4,8\}$, the sumset has ten elements but the productset has seven. Its product multiplicities are triangular by exponent sums, so $E_\times(B)=44$, while $E(B)=28$. Taking logarithms turns its multiplicative progression into an additive interval; logarithms do not preserve the original addition operation.

No superlinear estimate of the same form can hold without restrictions over every finite field: taking $A$ to be an entire finite subfield gives $A+A=AA=A$. Even in prime fields, taking $A$ to be the whole field forces saturation at $p$. Finite-field sum-product theorems therefore require size and, where applicable, subfield-avoidance hypotheses. This chapter makes no unverified claim about the best bounds or any current open status.

Exercise. Explain why translation preserves additive energy but can change productset size. Hint: Compare $\{0,1,2,3\}$ with its translate $\{1,2,3,4\}$. Solution: Both have energy 44, because additive equations survive a common translation. The first productset is $\{0,1,2,3,4,6,9\}$ of size seven, while the second has nine products. Additive normalization is not automatically harmless in a sum-product problem.

Compute additive energy and compare structural and Fourier bounds

The investigation compares exact finite counts, a structural certificate, and a Fourier identity on the same additive data. Its foundation uses the definitions and two tools in the opening section; deeper inverse theorems are optional. Distinguish a verified containing progression from an inference that requires Freiman's or BSG's theorem.

Worked solutions. For $A$, the seven sum multiplicities are $1,2,3,4,3,2,1$, so energy is 44. For $B$, the sumset is $\{2,3,4,5,6,8,9,10,12,16\}$; its diagonal sums $2,4,8,16$ have multiplicity one and its remaining six sums multiplicity two, giving 28. Its positive pair differences are $1,2,3,4,6,7$, all distinct. Thus the difference set has thirteen elements, compared with seven for the interval.

All additive sums remain distinct as values under reduction except for the collisions already present in the integers, because they lie in the interval $[2,16]$. Thus both exact energies transfer to the cyclic group. The integer differences lie between minus seven and seven and also remain distinct as residues, validating the difference-based cross-check.

Using double-precision transforms, the illustrative numerical results are:

The table's decimals are numerical checks, not exact certificates. The principal baseline is the same because the sets have equal cardinality, while the interval's larger nonprincipal fourth moment records its greater additive concentration. Cauchy–Schwarz lower bounds and the maximum-coefficient upper bounds leave different amounts of slack; neither determines energy by itself. An appropriate computation should have small inversion and Parseval residuals, but the final integers come from exact counting and the proved Fourier identity.

A rank-one progression $\{1,2,3,4\}$ contains $A$ with no overhead. The interval $\{1,\ldots,8\}$ contains $B$ with overhead two, so its moderately larger doubling is compatible with Freiman's qualitative conclusion too. Small examples do not demonstrate asymptotic separation of all possible containing ranks or constants. The productsets and multiplicative energies instead expose the two particular structures directly.

A cross-disciplinary application is discrete autocorrelation of an event-location signal. For $f=1_S$, the correlation at lag $t$ is $\sum_x f(x)f(x-t)=r_{S-S}(t)$, and its squared total is additive energy. Fourier multiplication computes correlation efficiently and identifies periodic components, as the twelve-residue example shows. The chosen cyclic embedding must avoid aliasing if integer-lag conclusions are intended. This links sumsets, difference multiplicities, and Fourier analysis in a concrete computation; productset behavior addresses a separate question about multiplicative scaling and cannot be inferred from autocorrelation alone.