Density increment

A density increment replaces a set by its intersection with a structured subset, translated back to a smaller ambient group, on which its relative density is larger. Iterating increments must stop before the density exceeds one.

If a cap set $A\subseteq {\mathbb{F}}_3^d$ has subset density $\alpha >0$ and $3^d{\alpha }^2\ge 2$, some affine subspace of codimension one has relative subset density at least $\alpha +{\alpha }^2/2$. The zero-sum count and the Parseval identity on a finite group give a nonzero finite abelian Fourier coefficient of magnitude at least ${\alpha }^2/2$. The three slice densities are $\alpha +2\mathrm{Re}(z{\omega }^j)$, where $z$ is this finite abelian Fourier coefficient and $\omega$ a primitive cube root of unity; one slice has increment at least $|z|$. Translation preserves the zero-sum condition because the characteristic is three.

There is an absolute constant $c>0$ such that, for every $\delta >0$ and all sufficiently large $N$, a subset $A\subseteq [N]$ whose density of a finite subset is $\delta$ and which has no nonconstant three-term arithmetic progression has an arithmetic progression $P\subseteq [N]$ satisfying

The Fourier transform of the balanced function $f=1_A-\delta 1_{[N]}$ has a coefficient of magnitude at least $c_0{\delta }^{2}N$. Indeed, the trilinear countsatisfies $\Lambda (1_A,1_A,1_A)=|A|$, whereas $\Lambda (1_{[N]},1_{[N]},1_{[N]})\gg N^2$. Expanding $1_A=\delta 1_{[N]}+f$ and using the Parseval identity and the Cauchy-Schwarz inequality to bound every error term forces $\Vert \hat{f}{\Vert }_{\infty }\gg {\delta }^{2}N$ once $N$ is sufficiently large in terms of $\delta$.

Choose $\theta$ at which this large coefficient occurs. The Dirichlet approximation theorem gives $1\le d\le \sqrt{N}$ with $\Vert d\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le N^{-1/2}$. Partition $[N]$ into progressions of common difference $d$ and lengths between $\eta \sqrt{N}$ and $2\eta \sqrt{N}$, where $\eta >0$ is a sufficiently small multiple of ${\delta }^2$. The linear phase $e(\theta x)$ varies by $O(\eta )$ on each cell. The large Fourier coefficient then givesSince ${\sum }_{x\in [N]}f(x)=0$, the total positive discrepancy is half the total absolute discrepancy, so at least one cell has average of $f$ at least $c{\delta }^2$. This is the required density increment.

For an indicator function of a subset of $[N]$ with subset density $\alpha$, a large Fourier coefficient of $1_A-\alpha 1_{[N]}$ gives a density increment on an arithmetic progression. The Dirichlet approximation theorem supplies a step $d\le \sqrt{N}$ on which the detected linear phase changes slowly. Split its residue classes into progressions of lengths comparable to ${\alpha }^2\sqrt{N}$. Replacing the phase by one constant on each cell preserves a fixed fraction of the Fourier correlation. Since the balanced function has total sum zero, positive discrepancies sum to half the total absolute discrepancy; one cell has the displayed increased density. One may take $c=1/(2304\pi )$ when $N$ is sufficiently large in terms of $\alpha$.

Let $I=[n]$ for odd $n\ge 3$, embed it in the cyclic group $G=\mathbb{Z}/(2n+1)\mathbb{Z}$, and let $A\subseteq I$ have density of a finite subset $\alpha$. If $A$ has no nonconstant three-term arithmetic progression and $n\ge 4{\alpha }^{-2}$, its balanced indicator function $f=1_A-\alpha 1_I$ satisfiesIndeed, the normalized trilinear arithmetic progression count has the Fourier analysis on a finite abelian group formula $\Lambda (h_1,h_2,h_3)={\sum }_r{\hat{h}}_1(r){\hat{h}}_2(-2r){\hat{h}}_3(r)$. Its values on $1_A$ and $\alpha 1_I$ are $\alpha n/|G{|}^2$ and ${\alpha }^3(n^2+1)/(2|G{|}^2)$. Telescoping their difference into three terms containing $f$, the Parseval identity and Cauchy-Schwarz inequality bound its magnitude by $3\max |\hat{f}|\alpha n/|G|$. The difference is at least ${\alpha }^3{n}^2/(4|G{|}^2)$, giving the claim. The zero Fourier coefficient vanishes by the definition of $\alpha$.

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

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)}$.