For \(0\lt \delta\lt 1\text{,}\) define

\begin{equation*}
\varepsilon=\frac{\delta}{81}
\end{equation*}

and let

\(N_0:= n_0(\varepsilon,1)/9\) where

\(n_0\) is as in

Corollary 5.2.4. For

\(n\geq n_0\text{,}\) we suppose that there exists

\(A\subseteq [n]\) of cardinality at least

\(\delta n\) without any non-trivial

\(3\)-term arithmetic progression and derive a contradiction.

Let us start by building a graph \(G\) based on \(A\) as follows. Let \(X=\{x_0,\dots,x_{3n}\}\text{,}\) \(Y=\{y_0,\dots,y_{3n}\}\) and \(Z=\{z_0,\dots,z_{3n}\}\) be disjoint sets of vertices.

Add an edge from \(x_i\) to \(y_j\) if \(j-i\in A\text{.}\)

Add an edge from \(y_i\) to \(z_j\) if \(j-i\in A\text{.}\)

Add an edge from \(x_i\) to \(z_j\) if \((j-i)/2\in A\text{.}\)

(Note that, here, all arithmetic is viewed modulo \(3n+1\)).

Let \(t(G)\) denote the number of triangles in \(G\text{.}\) For \(a\in A\) and \(b\in\{0,\dots,n\}\text{,}\) we have that \(x_b,y_{b+a},z_{b+2a}\) forms a triangle in \(G\text{,}\) by construction. Therefore,

\begin{equation*}
t(G) \geq |A|(n+1) > \frac{\delta |V(G)|^2}{81} = \varepsilon |V(G)|^2\text{.}
\end{equation*}

(Here, we used that \(|V(G)|=9n+3\) and \(|A|\geq \delta n\)).

Now, we will show that every edge of

\(G\) is contained in at most one triangle. If this is true, then, by

Corollary 5.2.4 and the fact that

\(|V(G)|\geq 9n \geq n_0(\varepsilon,1)\text{,}\) we will have that

\(G\) contains at most

\(\varepsilon|V(G)|^2\) triangles, which will contradict the lower bound on the number of triangles proved above; thus, the proof will be complete.

Consider any triangle \(x_i,y_j,z_k\) in \(G\) with \(x_i\in X,y_j\in Y\) and \(z_k\in Z\text{.}\) By construction, we must have

\begin{equation*}
j-i\in A\text{,}
\end{equation*}

\begin{equation*}
\frac{k-i}{2}\in A
\end{equation*}

and

\begin{equation*}
k-j\in A\text{.}
\end{equation*}

Thus, \(j-i,\frac{k-i}{2}\) and \(k-j\) form a \(3\)-term arithmetic progression in \(A\) with common difference \(\frac{i-2j+k}{2}\text{.}\) Since we are assuming that all \(3\)-term arithmetic progressions in \(A\) are trivial, we must have

\begin{equation}
i-2j+k=0\text{.}\tag{5.2.1}
\end{equation}

Thus, for any choice of two of \(i,j,k\text{,}\) the third is uniquely determined. Thus, every edge of \(G\) is contained in at most one triangle and we are done.