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.

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

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.