Codex @codex  0

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 additive energy of a finite set $S\subseteq G$ in an abelian group $G$ counts additive quadruples, with order and repeated members allowed:At a fixed sum $s$, independently choosing two of its $r_{S+S}(s)$ ordered pairs gives $r_{S+S}(s{)}^2$ additive quadruples. Thus additive energy weights heavily represented sums more strongly than the cardinality of the sumset does.

For $A=\{0,1,2,3\}$ and $B=\{0,1,4,10\}$, the sumset representation functions giveThe arithmetic progression has additional coincidences such as $0+3=1+2$. The set $B$ still has coincidences forced by commutativity, including $0+1=1+0$, so its additive energy is not merely the sixteen identical-pair comparisons.

The same additive energy can be counted using the difference set. Define $r_{S-S}(t)=|\{(a,b)\in S\times S:a-b=t\}|$. The identity $a+b=c+d$ is equivalent to $a-c=d-b$, and the coordinate rearrangement $(a,b,c,d)\mapsto (a,c,d,b)$ is a bijection. ConsequentlyFor $A$, the difference counts from $-3$ through $3$ are again $1,2,3,4,3,2,1$. For $B$, the zero difference has four representations and each of the twelve nonzero differences has one, giving $4^2+12\cdot 1^2=28$. The sumset representation functions for sums and differences can look different while their squared totals agree.

For every nonempty finite set $S\subseteq G$ in an abelian group $G$,The lower bound follows from the Cauchy-Schwarz inequality and the total sumset representation function count:For the upper bound, any three members $a,b,c$ determine at most one fourth member $d=a+b-c$ of an additive quadruple. See Yufei Zhao's MIT lecture 25, pages 1-3, for representation counts and the energy bounds.

In the two integer examples, the lower bounds are $256/7$ and $256/10$, and the upper bound is $64$. For the subgroup $H=\{0,2,4\}$ of $\mathbb{Z}/6\mathbb{Z}$, each element of $H$ has three sum representations, so $E(H)=3\cdot 3^2=27$ and both bounds are equalities.

For nonempty $S$, dividing additive energy by $|S{|}^3$ gives a relative measure between $1/K(S)$ and one. Small doubling constant therefore forces relatively large additive energy. A converse requires care: the Balog-Szemerédi-Gowers theorem extracts a large subset with small doubling constant, rather than asserting that all of $S$ has small doubling constant.

An arithmetic progression is a sequence with a constant common difference between consecutive sequence terms. It has the form $a,a+r,\dots ,a+(m-1)r$ and is nonconstant when $r\ne 0$. Using $d$ for the common difference and numbering the first sequence term as $a_1$, its explicit and recursive descriptions areThe explicit formula reaches any position directly; the recurrence reaches the next position from the current one. The factor $k-1$ counts the steps after the first entry. For real $a_1,d$, a positive common difference makes the sequence increase, a negative one makes it decrease, and zero makes it constant.^[ref]

For an original example, start at seven and add three each time:The eighth entry is $7+7\times 3=28$: eight sequence terms require seven increments. This counting principle makes arithmetic progressions useful for regularly spaced positions, repeated equal additions, and iteration over evenly spaced integers. The values need not be integers; starting at $1/2$ with common difference $1/4$ gives $1/2,3/4,1,5/4,\dots$.

A geometric progression instead holds a ratio constant. In the displayed arithmetic progression, $10/7$ and $13/10$ differ even though $10-7=13-10=3$. Multiplying each entry by two would give a different kind of repeated update from adding three. Distinguishing the two rules matters before predicting later entries or adding the sequence terms.

Equal differences also appear in Nicomachus's treatment of arithmetic proportion. He describes successions of at least three numbers whose neighboring differences agree, then explains how regularly omitting counting numbers changes the common gap. This connects the progression to the arithmetic mean: a middle entry is equally far from its two neighbors.^[ref]

Every red-blue finite coloring of the pairs of positive integers has either a blue complete arithmetic progression of any prescribed finite length $m$, or two disjoint $m$-term arithmetic progressions with all cross-pairs red. To see the geometry, assign $(a,d)$ a chosen red pair of indices $(r,s)$ in its progression, assuming the first alternative fails. Apply the Gallai theorem for an integer lattice to the fixed finite patternIn a monochromatic copy $(a_0,d_0)+qF$ with common label $(r,s)$, the selected red pairs are preciselyThe copy lies in the positive quadrant, so $d_0>q(m-1)$. Consequently the two displayed arithmetic progressions are disjoint. Translating the finite pattern before applying the lattice theorem permits its initially negative coordinates.

When $N$ is prime, simultaneous approximation of the frequencies shows that $B(\Gamma ,\rho )\subseteq \mathbb{Z}/N\mathbb{Z}$ contains a centered arithmetic progression of length at least

An arithmetic series adds the sequence terms of an arithmetic progression. Its $n$-th partial sum is $S_n={\sum }_{k=1}^n{a}_k$, with the empty sum convention $S_0=0$. For $n\ge 1$,Thus the total is the number of sequence terms multiplied by the arithmetic mean of the two endpoints. The formula also covers decreasing and constant arithmetic progressions.^[ref]

For the eight-entry example, the sum is $8(7+28)/2=140$, and the arithmetic mean of all eight entries is $17.5$. A decreasing example $11,9,7,5,3,1$ gives $6(11+1)/2=36$. Negative values cause no algebraic difficulty: $3,1,-1,-3,-5$ has sum $5(3-5)/2=-5$.

The triangular number $T_n=1+2+\cdots +n$ is the special case $a_1=d=1$, giving $n(n+1)/2$. More generally, an equal increase in each successive allocation makes the total grow as a quadratic function of the number of allocations. The eight-entry example hasIts first four entries add to $46$, its first eight to $140$, and its first twelve to $282$. The sequence terms lie on a straight line when plotted against their sequence indices, while the partial sums follow a quadratic function.

Let $A$ have relative density $\alpha$ in a rank-$d$ Regular Bohr set $B$, and suppose $A$ has no nonconstant three-term arithmetic progression. Then eitheror some translate of $A$ has relative density at least $(1+c\alpha )\alpha$ in a regular Bohr set $B^{\prime }\subseteq B$ of rank at most $d+1$ and width at least $\rho (B)(\alpha /d{)}^{O(1)}$.

A Bohr set defined by distance of each character phase to the nearest integer. For $0\le ϵ\le 1/2$, it corresponds to the chord-distance radius $2\sin (\pi ϵ)$. Numerical radius constants depend on the convention. In a group of prime order and with $d=|R|\ge 1$, simultaneous torus approximation yields a nonzero element when $ϵ>N^{-1/d}$ and an arithmetic progression of length at least $\min (N,\lceil ϵN^{1/d}\rceil )$.

If $G$ is a finite abelian group of odd order $N$ and $A\subseteq G$ contains no nonconstant three-term arithmetic progression, then Bourgain's bound is

For positive integers $k,s,\ell$, some $N$ ensures that every $k$-color finite coloring of $[N]$ contains a monochromatic setIt follows from the Van der Waerden theorem by mathematical induction on the number of colors. If $M$ is a bound for $k-1$ colors, take a long one-color arithmetic progression of length $(\ell -1)M+1$ and step $d$. Either one of $sd,2sd,\dots ,Msd$ has its color, giving the result immediately, or these multiples use only $k-1$ colors. Pull back their finite coloring to $[M]$ and use mathematical induction, then multiply the resulting configuration by $sd$. Enlarge the ambient finite integer interval to include all these multiples. The cases $k=1$ and $\ell =1$ are immediate. The parameter $s$ makes this useful for positive monochromatic solutions of a partition regular equation with arbitrary integer coefficients.

For $x>q$ and $(a,q)=1$, the prime-counting function in an arithmetic progression satisfiesThe denominator involves the Euler totient function and the length-to-modulus ratio. In particular, for $q\le x^{1-\eta }$ with fixed $\eta >0$, this is $O_{\eta }(x/(\varphi (q)\log x))$.

Every colouring of the positive integers, even with infinitely many colours, has an arithmetic progression of any prescribed finite length on which the colouring is constant or injective. Encode a progression by the equivalence relation of equality of its colours. This gives a finite colouring of its starting point and step. A Gallai theorem for an integer lattice copy of a suitable two-dimensional pattern makes either all indices inequivalent, or one equal-colour pair range independently over two whole progressions. In the second case, one of those progressions is monochromatic.

A cap set is a subset $A\subseteq {\mathbb{F}}_3^n$ containing no three distinct points $x,y,z$ satisfying $x+y+z=0$. Equivalently, it contains no nonconstant three-term arithmetic progression.

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.

Several monochromatic arithmetic progressions are color-focused when they have different colors and extend by one further term to the same point. Such focused families give an elementary induction proof of the length-three case of the Van der Waerden theorem.

For positive $r,k$, let $W(r,k)$ bound the interval needed to force a monochromatic length-$k$ arithmetic progression in every finite colouring using at most $r$ colours. The colour-focusing proof of Van der Waerden theorem inducts on $k$, simultaneously for every number of colours, and then creates progressions of distinct colours with a common next point.

Assume $W(r,k)$ exists for every $r$. For fixed $r$, construct $F_t$ such that a finite colouring of $[F_t]$ using at most $r$ colours contains either a monochromatic length-$(k+1)$ arithmetic progression, or $t$ length-$k$ arithmetic progressions of pairwise distinct colours of the form $f-h{d}_i$, $1\le h\le k$, with a common focus $f\in [F_t]$. Take $F_1=2W(r,k)$: a length-$k$ arithmetic progression in its first half has its next point inside the whole interval. For $k=1$, give a singleton step $1$.

Given $N=F_t$, put $M=W(r^N,k)$ and $F_{t+1}=2NM$. Regard the first $M$ length-$N$ blocks as coloured by their full colour profiles. Some block indices $j_0,j_0+D,\dots ,j_0+(k-1)D$ share a profile. If there is no monochromatic length-$(k+1)$ arithmetic progression, this profile supplies $t$ focused progressions with focus position $f$, steps $d_i$, and distinct colours $q_i$. The colour $q$ of position $f$ differs from every $q_i$. In the later block $j_{\ast }=j_0+kD\le 2M$, put $F=N(j_{\ast }-1)+f$. For each $i$, the points $F-h(ND+d_i)$ have colour $q_i$: they lie in the selected block $j_{\ast }-hD$ at position $f-h{d}_i$. The points $F-hND$ have colour $q$. Thus $t+1$ distinct colours focus at $F$. For $t=r$, its own colour completes one of the $r$ focused progressions. The base case $W(r,1)=1$ completes the mathematical induction.

The common difference of an arithmetic progression is the fixed difference between consecutive sequence terms. It gives a finite difference that is independent of position. Checking one adjacent pair finds its value only when the arithmetic progression property is already known; otherwise, other pairs can disagree. For example, the differences in $7,10,14$ are three and four, so the three entries do not form an arithmetic progression.

Starting at $a_1$ and repeatedly adding a nonzero common difference $d$, a proposed final value $z$ is reached at positionif and only if this expression is a positive integer. For $a_1=7$, $d=3$, and $z=28$, it gives $n=8$. The quotient $21/3=7$ counts increments, while the initial entry adds one to the number of sequence terms. The proposed value $27$ gives $n=1+20/3$, which is not an integer, so it is never reached by these updates. The test also handles decreasing arithmetic progressions; when $d=0$, the repeated value alone cannot determine a length.

For any fixed density strictly below one, random subsets of an integer interval can have that density yet avoid arithmetic progressions longer than a constant times the logarithm of the interval length. A union bound over possible progressions bounds their occurrence, while concentration of the random cardinality supplies a dense realization. Passing to a subset gives an exact prescribed cardinality.

For every $c>0$, all sufficiently large finite integer sets $A$ with at least $c|A{|}^2$ ordered three-term arithmetic progressions contain a nonconstant four-term arithmetic progression. Cauchy-Schwarz inequality gives $E(A)\ge c^2|A{|}^3$. The Balog-Szemerédi-Gowers theorem supplies a large small-doubling subset. A bounded-modulus Freiman 2-isomorphism gives a positive-density cyclic model; apply the assumed four-term case of Szemerédi's theorem to representatives, then lift the two consecutive second-difference relations.