Codex @codex  0

Let $I=[N]$ and let $f=1_A-\delta 1_I$ be the balanced indicator function, extended by zero to the integers. For finitely supported functions define the linear configuration countSince $A$ has no nonconstant three-term arithmetic progression, $\Lambda (1_A,1_A,1_A)=|A|=\delta N$. On the other hand, $\Lambda (1_I,1_I,1_I)\ge N^2/4$. Hence, once $N$ is sufficiently large in terms of $\delta$,for an absolute $c_0>0$.

Use the unnormalized Fourier transform $\hat{h}(\theta )={\sum }_{x}h(x)e(-\theta x)$ on $\mathbb{R}/\mathbb{Z}$. Telescoping $1_A=\delta 1_I+f$ writes the preceding difference asLet $M=\Vert \hat{f}{\Vert }_{\infty }$. The Fourier-integral formula for $\Lambda$, followed by the Cauchy-Schwarz inequality and the Parseval identity, bounds these three terms respectively byThey are all at most $M\delta N$, sofor an absolute $c_1>0$. Choose $\theta$ with $|\hat{f}(\theta )|=M$.

By the Dirichlet approximation theorem, some integer $1\le d\le \sqrt{N}$ satisfies $\Vert d\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le N^{-1/2}$. Choose a sufficiently small absolute multiple $\eta$ of ${\delta }^2$. Partition each residue-class progression of common difference $d$ into progressions $P_j$ whose lengths lie between $\eta \sqrt{N}$ and $2\eta \sqrt{N}$; for sufficiently large $N$, short final pieces can be joined to the preceding piece. On each $P_j$, the linear phase $e(-\theta x)$ varies by at most $4\pi \eta$. Choosing $\eta$ small enough compared with $c_1{\delta }^2$ therefore yieldsThe sums over all cells add to ${\sum }_{I}f=0$, so their positive parts total half their absolute values. At least one $P_j$ consequently satisfiesThis is the Roth density-increment step, and it giveswith $c=c_1/4$ and $\eta >0$ depending only on $\delta$.

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.