Additive combinatorics

Additive combinatorics studies how the cardinalities and sumset representation functions of sumsets reveal structure in finite sets contained in abelian groups. Write the group operation as addition: the ambient abelian group may be the integers $\mathbb{Z}$, a finite cyclic group, or another abelian group. The same definitions apply, but the ambient group changes which bounds are possible.

The basic experiment is to add every ordered pair of members of a finite set. The sumset records the distinct answers; the sumset representation function records how often each answer occurs; the additive energy counts coincidences between those answers. An arithmetic progression produces many repeated sums, so its sumset grows slowly and its additive energy is relatively large. The doubling constant measures that growth relative to the original cardinality.

The examples below compare the arithmetic progression $A=\{0,1,2,3\}$ with the more spread-out integer set $B=\{0,1,4,10\}$. Their four members give sixteen ordered pairs in each case, but different numbers of distinct sums. This small comparison illustrates the definitions; it does not establish a claim about arbitrarily large sets. For a systematic introduction, see Tao and Vu's author page for Additive Combinatorics, with free sample chapters on sum set estimates and additive geometry.

The multidimensional Szemerédi theorem says that a subset $A\subseteq {\mathbb{Z}}^d$ with positive upper density contains a translated positive integer dilate $a+tF$ of every finite set $F\subseteq {\mathbb{Z}}^d$. In the finite formulation, for every $\alpha >0$ and finite $F$, all sufficiently large integer boxes have this property for every subset occupying at least an $\alpha$ fraction of the box. The one-dimensional case for $F=\{0,1,\dots ,r-1\}$ is the Szemerédi theorem. The general result follows from multiple recurrence for commuting measure-preserving transformations.

A frequency function built from an affine variable and its fractional part. Irrational $\gamma$ and $\beta$ can give many exact additive relations because each pair sum has only two possible floor carries. For example $\beta =\sqrt{3}$, $\gamma =\sqrt{2}$ gives $\gg N^3$ additive quadruples on $[-N,N]$, but agreement with every ordinary affine function occurs on only $o(N)$ shifts. Integer floor points underlying affine agreement must be collinear.

Use four parts indexed by $0,1,2,3$ in a cyclic group $G$, and include the triple missing part $i$ when $L_i\in A$. A transversal three-uniform tetrahedron then has the four values $S_1-i{S}_0$, where $S_0={\sum }_j{x}_j$ and $S_1={\sum }_{j}j{x}_j$, so it encodes a four-term arithmetic progression. Constant progressions give $|A||G{|}^2$ edge-disjoint tetrahedra. This is the bridge from the tetrahedron removal lemma to the Szemerédi theorem.

For every $\delta >0$, every sufficiently long integer interval has a nonconstant three-term arithmetic progression in each subset of subset density at least $\delta$. This is a theorem about additive combinatorics, distinct from the Roth theorem on approximation of algebraic irrational numbers. The Roth density-increment step proves it by repeatedly increasing subset density on a shorter arithmetic progression.

If a density-$\delta$ subset of a sufficiently long integer interval has no nonconstant three-term arithmetic progression, Fourier expansion of the progression count gives a large coefficient of its balanced indicator. Dirichlet approximation supplies a step at most $\sqrt{N}$ on which that character varies slowly. Partitioning the interval into equal-length progressions of that step, and controlling the short tails, produces the displayed density increment. Iteration must terminate since density cannot exceed one. The same argument treats the three-point pattern with coefficients $2,-3,1$.

Embed $A\subseteq [N]$ in the odd cyclic group $G=\mathbb{Z}/(2N+1)\mathbb{Z}$, so additive three-term relations in $A$ cannot wrap around. Form three copies of $G$, putting edges $x\sim y$ when $y-x\in A$, $y\sim z$ when $z-y\in A$, and $x\sim z$ when $(z-x)/2\in A$. A triangle in a graph encodes $a+b=2c$ in $A$. If $A$ has no nonconstant arithmetic progression, every triangle in a graph has $a=b=c$; there are exactly $|G||A|$ triangles in a graph, and they are edge-disjoint. Thus at least $|G||A|$ edges must be removed to eliminate them. For fixed positive subset density of $A$, this is a positive fraction of the squared vertex count, whereas the triangle in a graph count is only quadratic. The triangle removal lemma permits deletion of an arbitrarily small quadratic fraction when the cubic triangle in a graph subset density is sufficiently small. This contradiction establishes Roth theorem on three-term arithmetic progressions.

Write $r_3(N)$ for the maximum cardinality of a subset of $[N]$ containing no nonconstant three-term arithmetic progression. There is an absolute constant $C$ such that every three-term-progression-free subset $A\subseteq [N]$ satisfies $|A|\le CN/\log \log N$ for $N\ge 3$. A quantitative Roth density-increment step gives, for subset density $\delta$ and $N\ge 4\cdot 10^6{\delta }^{-4}$, a arithmetic progression of length at least ${\delta }^2\sqrt{N}/2000$ and increased subset density at least $\delta +{\delta }^2/64$. The increment decreases reciprocal subset density by at least $1/65$, so fewer than $\lceil 65/\delta \rceil$ iterations are possible. If $N_j$ is the successive length, then $\log N_{j+1}\ge \frac{1}{2}\log N_j-\log (2000/{\delta }^2)$, using the initial subset density to bound all later ones. Hence $\log N_j\ge 2^{-j}\log N-2\log (2000/{\delta }^2)$. If $\delta \log \log N$ exceeds a sufficiently large absolute constant, all these intervals remain above the density increment threshold, a contradiction. This proves the displayed bound. The result is a classical quantitative version of Roth theorem on three-term arithmetic progressions, without asserting an optimal bound.

For fixed $\theta >0$, a sufficiently large finite set of integers with additive energy at least $\theta |A{|}^3$ has a nonconstant three-term arithmetic progression. The Balog-Szemerédi-Gowers theorem and Ruzsa modelling lemma reduce the problem to the Roth theorem on three-term arithmetic progressions in a dense cyclic model.

The product set of two sets of real numbers is $A\cdot B=\{ab:a\in A,b\in B\}$. It is a multiplicative counterpart of a sumset, not the Cartesian product $A\times B$.

For finite sets of nonzero real numbers, the multiplicative energy is the number of quadruples $(a,b,c,d)\in A\times B\times A\times B$ satisfying $a/b=c/d$. Swapping $b,d$ shows that it also counts quadruples with $ab=cd$. Thus $E(A,B)={\sum }_x{r}_{A\cdot B}(x{)}^2$, where $r_{A\cdot B}(x)$ counts product representations. The Cauchy-Schwarz inequality yields $E(A,B)\ge |A{|}^2|B{|}^2/|A\cdot B|$.

For finite sets of positive real numbers $A,B$ with $|B|\ge 2$, $E(A,B)\le 4\lceil \log |B|\rceil |A+A||B+B|$, with natural or binary logarithm. Partition ray occupancies of $A\times B$ into $\lceil \log |B|\rceil$ classes of multiplicative width $e$, or width $2$ for the binary convention. Injectivity of sums on two distinct rays and disjoint open planar sectors bound each class's sum of squared occupancies by $4|A+A||B+B|$. A singleton class contributes at most $|A||B|$. Combining this with the energy lower bound gives a sum-product inequality.

A corner consists of these three points in the integer grid, all contained in the set being studied. The displacement may be positive or negative, but must be nonzero, so the points are distinct. The corners theorem guarantees a corner in every subset of positive fixed density of a finite subset of a sufficiently large square grid.

For every $\delta >0$, all sufficiently large integers $n$ have the property that every $A\subseteq [n{]}^2$ with $|A|\ge \delta n^2$ contains a corner in an integer grid. The tripartite graph encoding of a grid turns the absence of a corner into a family of many edge-disjoint triangles but only quadratically many total triangles in a graph, contradicting the triangle removal lemma.

For a real-valued function $H$ on a nonempty finite Cartesian product $X\times Y$, its normalized cut norm is the maximum of $|{\mathbb{E}}_{x,y}H(x,y)1_A(x)1_B(y)|$ over $A\subseteq X,B\subseteq Y$. It measures all rectangular subset discrepancies. The convention using arbitrary test functions bounded by one is equivalent within a factor of four, by decomposing their positive and negative parts into indicator functions.

Non-abelian additive combinatorics studies product sets and configuration counts in noncommutative groups. Fourier analysis on a finite group and quasirandom groups connect small-dimensional group representations with multiplicative mixing.

For $f:G\to M_n(\mathbb{C})$ on a finite group, use uniform expectation over the solutions of $x{y}^{-1}z{w}^{-1}=e$ and the ordinary, unnormalized trace to define the displayed fourth-order quantity. If $T_{\rho }$ is its matrix Fourier block, this quantity equals ${\sum }_{\rho }{d}_{\rho }\mathrm{Tr}((T_{\rho }{T}_{\rho }^{\ast }{)}^2)$, so it is real and nonnegative. For a scalar function on an abelian group, it reduces to the usual fourth power of the Gowers uniformity norm of order two. The unnormalized trace means a unitary matrix-valued function can have fourth-order quantity as large as $n$.

If $\Vert f(x){\Vert }_{\mathrm{op}}\le 1$ and $\Vert f{\Vert }_{U^2}^4\ge cn>0$, select the singular values ${\lambda }_p\ge \sqrt{c/2}$ of the matrix Fourier blocks. Their weighted count $m={\sum }_p{d}_{{\rho }_p}$ lies between $cn/2$ and $2n/c$. Scaling unit right singular vectors and their corresponding unit left singular vectors by $\sqrt{d_{{\rho }_p}}$ gives matrices $U(p),V(p)$ satisfying ${\mathbb{E}}_{x}f(x)U(p){\rho }_p(x{)}^{\ast }={\lambda }_{p}V(p)$ and Hilbert-Schmidt inner product orthogonality within each chosen irreducible representation. The Schur averaging of rectangular matrices then gives ${\mathbb{E}}_x\Vert UP(x{)}^{\ast }b{\Vert }_2^2=\Vert b{\Vert }_2^2$ for the concatenated $U$ and the corresponding block diagonal matrix $P(x)$.

For $f:G\to M_n(\mathbb{C})$ and a degree-$d_{\rho }$ unitary irreducible representation, the matrix Fourier block is the operator $T_{\rho }$ on $M_{n\times d_{\rho }}(\mathbb{C})$ defined in the title. Its singular values ${\lambda }_{\rho ,j}$ satisfyPointwise operator norm at most one implies $\Vert T_{\rho }{\Vert }_{\mathrm{op}}\le 1$. These blocks are operators on a matrix space, rather than simply the entrywise scalar Fourier transform on a finite group without any reshaping.

A finite group is $m$-quasirandom if every nontrivial irreducible representation over the complex numbers has degree at least $m$. The trivial representation is excluded. Large $m$ suppresses correlations of products of arbitrary subsets, through product mixing in a quasirandom group.

For an $m$-quasirandom group, uniform expectations, and the normalized convolution on a finite group, a scalar mean-zero function $f$ satisfiesThe Fourier analysis on a finite group proof bounds each nontrivial matrix component of $f$ in operator norm using its weighted Hilbert-Schmidt norm. For subsets of subset density values $a,b,c$, the error in their normalized product count is at most $\sqrt{a(1-a)b(1-b)c(1-c)/m}$. In particular $abc>1/m$ guarantees a solution of $xy=z$ in the three subsets.

For a finite group, choose one unitary irreducible representation $\rho$ of degree $d_{\rho }$ from each equivalence class. One consistent normalized Fourier transform on a finite group convention is $\hat{f}(\rho )={\mathbb{E}}_{x}f(x)\rho (x)$. The Schur orthogonality relations giveThe normalized convolution on a finite group satisfies $\widehat{f\ast g}(\rho )=\hat{f}(\rho )\hat{g}(\rho )$ in this convention. Using $\rho (x{)}^{\ast }$ in the transform instead reverses that product order for scalar functions with the same normalized convolution on a finite group convention. The Fourier transform on a finite group has matrix-valued components even when the original function is scalar-valued.

For a scalar function on a group, use $(R_{a}f)(x)=f(xa)$ as the right-translation convention. For Fourier analysis on a finite group this gives $\widehat{R_{a}f}(\rho )=\hat{f}(\rho )\rho (a{)}^{\ast }$. Specifying whether $a$ or $a^{-1}$ appears in the definition avoids sign and multiplication-order ambiguity.

For a scalar function on a group, left translation by $a$ is $(L_{a}f)(x)=f(a^{-1}x)$. With the positive-representation convention for Fourier analysis on a finite group, $\widehat{L_{a}f}(\rho )=\rho (a)\hat{f}(\rho )$.

For a scalar function on a finite group, one normalized transform convention assigns the matrix ${\mathbb{E}}_{x}f(x)\rho (x)$ to each chosen unitary irreducible representation. This map is a weighted Hilbert space isomorphism by the Parseval identity on a finite group. Another common convention uses $\rho (x{)}^{\ast }$; the corresponding convolution theorem on a finite group then reverses the matrix product order for $(f\ast g)(x)={\mathbb{E}}_{y}f(y)g(y^{-1}x)$.

For the Fourier transform on a finite group, the displayed identity uses uniform expectation in the original function space and a weighted Hilbert-Schmidt inner product in the matrix components. In particular $\Vert f{\Vert }_2^2={\sum }_{\rho }{d}_{\rho }\Vert \hat{f}(\rho ){\Vert }_{\mathrm{HS}}^2$. For an abelian group, all $d_{\rho }=1$, and the identity becomes a sum of squared scalar coefficients.

The Fourier transform on a finite group convention $\hat{f}(\rho )={\mathbb{E}}_{x}f(x)\rho (x)$ has the displayed inversion formula. The sum is over one representative from each equivalence class of unitary irreducible representations. It follows from the Schur orthogonality relations and the regular representation decomposition, and holds at every group element without a limiting argument.

For scalar functions on a finite group, normalized convolution on a finite group is $(f\ast g)(x)=|G{|}^{-1}{\sum }_{y}f(y)g(y^{-1}x)$. It is associative and need not commute. Its identity is $|G|1_{\{e\}}$, rather than the unscaled indicator function of the identity element. The Fourier analysis on a finite group convention $\hat{f}(\rho )=\mathbb{E}f(x)\rho (x)$ turns it into matrix multiplication in the same order.

The normalized convolution on a finite group and the Fourier transform on a finite group convention with $\rho (x)$ satisfy the displayed identity. Substitute $x=yz$ in the defining expectation and use $\rho (yz)=\rho (y)\rho (z)$. With the convention using $\rho (x{)}^{\ast }$ instead, the scalar convolution has transform $\hat{g}(\rho )\hat{f}(\rho )$; multiplication order matters for noncommutative groups.

For nonempty finite sets $X,Y$ and a function $f:X\times Y\to \mathbb{C}$ on their Cartesian product, using uniform expectations, defineThis equals ${\mathbb{E}}_{y,y^{\prime }}|{\mathbb{E}}_{x}f(x,y)\overline{f(x,y^{\prime })}{|}^2$. Hence it is nonnegative, and vanishing forces $f=0$ by taking $y=y^{\prime }$. Absolute homogeneity and the box Cauchy-Schwarz inequality establish that it is a norm. For a real-valued function the complex conjugates can be omitted. The bilinear correlation bound for the box norm also holds for complex functions.

Give every entry of an $m$ by $n$ matrix an independent uniformly random sign. A four-entry rectangle product has expectation zero unless its two row indices coincide or its two column indices coincide; in those cases it is one. Counting the union of these diagonal cases gives $m{n}^2+m^{2}n-mn$ before normalization. Thus some sign matrix has box norm fourth power at most the displayed expectation, and its cut norm tends to zero when both dimensions tend to infinity.

For a real function $f$ bounded by one on a finite Cartesian product, the fourth power of its box norm is the mean of $f(x,y)f(x,y^{\prime })f(x^{\prime },y)f(x^{\prime },y^{\prime })$. Two applications of the Cauchy-Schwarz inequality bound every rectangular discrepancy by the box norm. Conversely, decompose each bounded real test function into positive and negative parts and use the layer cake representation. Its bilinear pairing with $f$ is at most four times the cut norm. Applying this to the row and column tests furnished by fixed $x^{\prime },y^{\prime }$ bounds the fourth moment by four times the cut norm. These dimension-independent estimates make the two notions of small discrepancy equivalent.

For a complex function on $X_1\times X_2\times X_3$, its eighth power is the average of the conjugated product over the eight vertices of a coordinate cube. Three successive applications of the Cauchy-Schwarz inequality show that it bounds correlation with a product of three bounded functions, each omitting one coordinate. This is the analytic estimate behind the tetrahedron counting lemma.

For a real function $g$ on $X\times Y\times Z$ and functions $a(y,z),b(x,z),c(x,y)$ bounded in absolute value by one,First apply Cauchy-Schwarz inequality in $(y,z)$ to remove $a$, duplicating $x$. Apply it in $(x_0,x_1,z)$ to remove $b(x_0,z)b(x_1,z)$, duplicating $y$. Finally apply it in $(x_0,x_1,y_0,y_1)$ to remove the four $c$ factors, duplicating $z$. The resulting eighth-power bound is exactly the eight-factor average defining the three-dimensional box norm. Functions depending on just one coordinate, or constants, can be incorporated in any of the three pair factors.

For a real-valued function $H$ on a nonempty finite Cartesian product, let $T_{H}v(x)={\mathbb{E}}_{y}H(x,y)v(y)$ with uniform inner products. The box norm obeys $\Vert H{\Vert }_{\square }^4=\mathrm{Tr}((T_H{T}_H^{\ast }{)}^2)={\sum }_j{\sigma }_j^4$, where ${\sigma }_j$ are its singular values. For a biregular graph this separates the constant component ${\gamma }^4$ from the other fourth powers.

With uniform expectations and real or complex functions,Apply the Cauchy-Schwarz inequality first in $y$. Expand the remaining square, and apply the Cauchy-Schwarz inequality in $(x,x^{\prime })$ to $u(x)u(x^{\prime })$ and ${\mathbb{E}}_{y}f(x,y)f(x^{\prime },y)$. Their squared averages are $\Vert u{\Vert }_2^4$ and $\Vert f{\Vert }_{\square }^4$, respectively.

Let a tripartite graph have nonempty parts $X,Y,Z$, pair edge density of a bipartite graph values $\alpha ,\beta ,\gamma$ on $XY,YZ,XZ$, and $\Vert G(X,Y)-\alpha {\Vert }_{\square }\le c$. If every $z\in Z$ has exactly $\beta |Y|$ neighbors in $Y$, its normalized triangle count $\tau$ obeysThe constant-degree assumption makes the contribution of the constant $\alpha$ exactly $\alpha \beta \gamma$. For each fixed $z$, apply the bilinear correlation bound for the box norm to the indicator functions of its two vertex neighbourhoods. Their squared $L^2$ norms are $\beta$ and the relative $X$-degree of $z$. Average over $z$ and use the Cauchy-Schwarz inequality to bound the mean square root of that degree by $\sqrt{\gamma }$.

For four real-valued functions on a finite Cartesian product, let $\Lambda (f_{00},f_{01},f_{10},f_{11})={\mathbb{E}}_{x_0,x_1,y_0,y_1}{\prod }_{i,j=0}^1{f}_{ij}(x_i,y_j)$. Repeated Cauchy-Schwarz inequalities giveFirst separate the two $y$ averages and apply Cauchy-Schwarz inequality in $(x_0,x_1)$. Each resulting squared factor is ${\mathbb{E}}_{y,y^{\prime }}({\mathbb{E}}_{x}f(x,y)f(x,y^{\prime }))({\mathbb{E}}_{x}g(x,y)g(x,y^{\prime }))$, bounded by $\Vert f{\Vert }_{\square }^2\Vert g{\Vert }_{\square }^2$ by another Cauchy-Schwarz inequality. Expanding the four factors of $f+g$ and applying this inequality to each of the sixteen terms gives the triangle inequality for the box norm.

The sum-product phenomenon says that a finite subset of a field cannot usually have both a small sumset and a small product set unless it has additional subfield-like structure.

Write $D(t)=|A+tA|/|A|$ and suppose some nonzero $b$ has $D(b)\le K$. The mixed-set Plünnecke-Ruzsa inequality gives $|3A-2A|\le K^5|A|$ and $|A+A|\le K^2|A|$. The Ruzsa covering lemma covers $tA$ by at most $D(t)$ translates of $A-A$. Covering two dilates proves the addition bound. First covering $sA$, then both copies of $rA$ in $r(A-A)$, proves the multiplication bound. The Ruzsa triangle inequality also gives $D(-r)\le K^{2}D(r)$. These bounds transfer controlled additive expansion through a bounded-complexity expression in scalars.

For positive $\alpha ,\beta$, suppose $p^{\alpha }\le |A|\le p^{1-\alpha }$ and $|B|\ge p^{\beta }$. Repeatedly replace a scalar set $S$ by $3SS-3SS$. Quadratic growth of a sixfold product difference set reaches size at least $p/2$ in a number of steps depending only on $\beta$. The closure bounds for small skew-sumset scalars transfer a putative bound $|A+bA|\le K|A|$ to all these scalars with exponent depending only on the number of steps. Averaging collisions over the resulting large scalar set then forces $K^L\ge \frac{1}{4}\min (|A|,p/|A|)\ge p^{\alpha }/4$. This supplies a positive exponent depending only on $\alpha ,\beta$. The finitely many smaller primes are covered by the strict inequality $|A+bA|>|A|$ for every nonzero $b$ when $1<|A|<p$.

For $S\subseteq {\mathbb{F}}_p$ with $|S|\ge 2$, put $R=(S-S)/(S-S)$ using nonzero denominators. If $R$ is proper, some $r\in R+1$ lies outside $R$, since invariance under addition of one would give all of the prime field. The map $(x,y)\mapsto x+ry$ on $S^2$ is injective. Clearing the denominator in a representation of $r-1$ puts a dilate of its image inside $3SS-3SS$. If $R$ is the full field, averaging the collision count of $S+rS$ gives some $r$ with $|S+rS|\ge \frac{1}{2}\min (p,|S{|}^2)$. Clearing its denominator puts a dilate inside $2SS-2SS\subseteq 3SS-3SS$. Here $SS$ is a product set, and the prefactors denote repeated sumsets, not scalar multiplication.

For finite $U,V,W\subseteq \mathbb{C}$ with $U\ne \{0\}$ and $W\ne \{0\}$,In particular, addition and multiplication cannot both expand a nontrivial finite set of complex numbers only slightly.

The density of $A$ in a nonempty finite ambient set $X$ is the proportion $|A|/|X|$.

For nonempty finite set $I$ and $A\subseteq I$, let $\alpha =|A|/|I|$ be the density of a finite subset. The balanced indicator function $f=1_A-\alpha 1_I$, extended by zero to an ambient finite group, has sum zero and vanishing zero Fourier coefficient. The sum of $f$ on a subset $P\subseteq I$ is $|A\cap P|-\alpha |P|$, measuring the excess density of a finite subset there.

A Sidon set in an abelian group is a subset $A$ for which an equality $a+b=c+d$ with $a,b,c,d\in A$ forces the unordered pairs $\{a,b\}$ and $\{c,d\}$ to be equal. Equivalently, the ordered nonzero differences $a-b$ with $a\ne b$ are all distinct.

For a Sidon set $A\subseteq [1,N]$, put $m=|A|$ and let $A_i$ count points in a window of $u$ consecutive integers. Each point occurs in $u$ windows, so $\sum A_i=um$. Cauchy-Schwarz gives $\sum \left(\genfrac{}{}{0ex}{}{A_i}{2}\right)\ge [u^2{m}^2/(N+u)-um]/2$. Each positive difference occurs at most once and contributes $u-d$ windows, giving the upper bound $u(u-1)/2$. Thus $m^2\le (N+u)(1+(m-1)/u)$. Taking $u=\lfloor N^{3/4}\rfloor$ gives the displayed estimate, which combines with the Bose-Chowla Sidon construction to determine the asymptotic maximum.

Choose a generator $\theta$ of the multiplicative group of the quadratic finite field extension. Its $p$ shifts $\theta +t$ define $p$ distinct exponents modulo $p^2-1$. Equality of two sums of exponents gives $(\theta +s)(\theta +t)=(\theta +u)(\theta +v)$. Since $1,\theta$ are independent over the prime field, $s+t=u+v$ and $st=uv$, so the unordered pairs coincide. Thus the exponents form a Sidon set in the cyclic group. Taking integer representatives preserves the Sidon property. Primes within $o(\sqrt{N})$ below $\sqrt{N}$ give $\sqrt{N}-o(\sqrt{N})$ representatives in an interval of length $N$.

A linear configuration count is a weighted sum over tuples satisfying prescribed linear equations. Orthogonality of complex exponentials often rewrites such a count as an integral of Fourier transforms.

Suppose a linear configuration count has a Fourier-integral representation with $k$ factors. If one has a uniform Fourier bound for the difference between two weights and compatible $L^{k-1}$ bounds for each weight, expanding the difference one factor at a time and applying Hölder's inequality bounds the change in the count.

A transference principle replaces a function bounded by a sparse pseudorandom majorant with a bounded dense model that is indistinguishable by a chosen family of tests. Results for bounded functions can then be transferred to the sparse setting.

For a family $\mathcal{F}$ of real-valued functions on a finite set and normalized inner product $⟨\cdot ,\cdot ⟩$, the test-function seminorm isIt measures the largest correlation of $g$ with an allowed test. It is a seminorm, and becomes a norm when the tests separate points.

The dual test-function norm isIf $\mathcal{F}$ is closed, convex, and symmetric, the Bipolar theorem for a dual pair identifies its dual unit ball with $\mathcal{F}$. Submultiplicativity under pointwise products allows a polynomial in one test function to remain controlled in this norm.

Let $\mathcal{F}$ be a closed, convex, symmetric family of functions into $[-1,1]$ that contains the constant function $1$, and suppose its dual test-function norm is submultiplicative under pointwise products. If a nonnegative majorant $\nu$ has average at most one and $\Vert \nu -1{\Vert }_{\mathcal{F}}$ is exponentially small in $1/\epsilon$, then every $0\le g\le \nu$ has a dense model $0\le \tilde{g}\le 1$ satisfyingThe proof separates $g$ from the convex set of dense models, then approximates the positive part of the separating test by a polynomial. Submultiplicativity controls every power in that polynomial.

On any fixed compact interval, the positive part of a real-valued function $t_{+}=\max (0,t)$ can be approximated uniformly by a real polynomial. Quantitative dense-model arguments use a version whose degree and coefficient growth are explicitly controlled in terms of the approximation error.

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.