= Solution
First derive the <triangle removal lemma> from the <Szemerédi regularity lemma>. Given an allowed deletion fraction $0<\eta<1$, take $d=\eta/10$, $m_0=\lceil10/\eta\rceil$, and $0<\varepsilon\leq\min(d/4,\eta/100,1/8)$. Apply part (i), with upper class bound $M$. Delete <edges> incident with $V_0$, inside each nonexceptional class, between <irregular pairs>, and between <regular pairs> of <subset density> less than $d$. Their total number is at most
$$
\left(2\varepsilon+\frac1{2m_0}+\frac d2\right)n^2<\eta n^2.
$$
These four terms are bounded respectively by $\varepsilon n^2$, $n^2/(2m_0)$, $\varepsilon n^2$, and $dn^2/2$.
If a <triangle in a graph> remains, its three <vertices> lie in three distinct equal classes, all three <regular pairs> with <subset density> at least $d$. The permitted <regular triangle counting lemma> gives at least $(d^3/4)t^3$ <triangles in a graph> in the original <graph>, where $t$ is the class size. This lower bound can also be checked directly: all but $2\varepsilon t$ <vertices> of the first class have at least $(d-\varepsilon)t$ neighbors in each of the other two. Those neighborhoods are large enough to use the <regular pair> condition on the remaining pair, giving at least $(d-\varepsilon)^3t^2$ <edges> between them. Hence the total is at least $(1-2\varepsilon)(d-\varepsilon)^3t^3\geq(d^3/4)t^3$.
Since $t\geq n/(2M)$, a surviving <triangle in a graph> forces at least $d^3n^3/(32M^3)$ original <triangles in a graph>. Thus a <graph> with fewer than $\xi n^3$ <triangles in a graph>, where $\xi=d^3/(64M^3)>0$, can be made <triangle-free> by deleting fewer than $\eta n^2$ <edges>, for all sufficiently large $n$. This proves the removal lemma needed here.
Now use the <triangle-removal proof of Roth theorem>. Fix a <subset density> lower bound $\delta>0$ and suppose $A\subseteq[N]$, $|A|\geq\delta N$, has no nonconstant three-term <arithmetic progression>. Set $m=2N+1$ and $G=\mathbb Z_m$. Use three disjoint copies $X,Y,Z$ of $G$ and put <edges> according to
$$
xy\in E\iff y-x\in A,\qquad yz\in E\iff z-y\in A,\qquad xz\in E\iff (z-x)/2\in A.
$$
Division by two is valid because $m$ is odd. A <triangle in a graph> corresponds to $a=y-x$, $b=z-y$, $c=(z-x)/2$ with $a,b,c\in A$ and $a+b=2c$. Since $A\subseteq[N]$ and $|a+b-2c|<m$, this congruence is an <integer> equality. Progression-freeness therefore forces $a=b=c$.
Every <triangle in a graph> is consequently of the form $(x,x+a,x+2a)$ with $x\in G,a\in A$, so there are exactly $m|A|$ <triangles in a graph>. These <triangles in a graph> are edge-disjoint: an $XY$ <edge> determines $(x,a)$; a $YZ$ <edge> determines $a$ and then $x$; and an $XZ$ <edge> determines $a=(z-x)/2$ and $x$. Eliminating them all requires at least $m|A|$ <edge> deletions.
The <graph> has $3m$ <vertices> but only $m|A|\leq mN=O(m^2)$ <triangles in a graph>. Take $\eta=\delta/100$. For large enough $N$ its <triangle in a graph> count is below $\xi(3m)^3$, so removal requires fewer than $\eta(3m)^2=9\delta m^2/100$ deletions. Yet
$$
m|A|\geq\delta mN\geq\frac{\delta m^2}{3}>\frac{9\delta m^2}{100},
$$
a contradiction. Therefore \b[every fixed positive-density <subset> of a sufficiently long interval contains a nonconstant three-term <arithmetic progression>].
This proves the qualitative <Roth theorem on three-term arithmetic progressions>. The quantitative bound from part 2(i) came from the explicit Fourier iteration; the regularity-removal argument gives a density-dependent threshold without that double-logarithmic estimate.
Back to article page
