[proofplan]
We count three-term progressions in $A$ in two ways. The progression-free hypothesis collapses the normalized progression count to the degenerate contribution, while the Fourier expansion of the same average has zero-frequency term $\alpha^3$ and all remaining terms involve nonzero Fourier coefficients of the balanced function $f_A$. Under the size hypothesis on $N$, the degenerate contribution is at most half of the zero-frequency term, so the nonzero Fourier contribution must be large. Parseval then converts that large aggregate contribution into a large individual Fourier coefficient.
[/proofplan]
[step:Define the normalized three-term progression average]
Let $\mathcal P(G)$ denote the power set of $G$, that is, the set of all subsets of $G$. Define the normalized progression-counting functional
\begin{align*}
\Lambda_3:\mathcal P(G)&\to[0,1]
\end{align*}
by
\begin{align*}
\Lambda_3(B):=\frac{1}{N^2}\sum_{x\in G}\sum_{d\in G}\mathbb{1}_B(x)\mathbb{1}_B(x+d)\mathbb{1}_B(x+2d)
\end{align*}
for every subset $B\subset G$. For the fixed set $A$, this gives $\Lambda_3(A)\in[0,1]$.
The hypothesis says that the summand is zero whenever $d\ne 0$. For $d=0$, the summand is $\mathbb{1}_A(x)$. Hence
\begin{align*}
\Lambda_3(A)=\frac{1}{N^2}\sum_{x\in G}\mathbb{1}_A(x)=\frac{|A|}{N^2}=\frac{\alpha}{N}.
\end{align*}
[guided]
We introduce a normalized average because Fourier inversion on a finite group naturally counts all pairs $(x,d)\in G\times G$ with equal weight. Let $\mathcal P(G)$ denote the power set of $G$, that is, the set of all subsets of $G$. Define the map
\begin{align*}
\Lambda_3:\mathcal P(G)&\to[0,1]
\end{align*}
by
\begin{align*}
\Lambda_3(B):=\frac{1}{N^2}\sum_{x\in G}\sum_{d\in G}\mathbb{1}_B(x)\mathbb{1}_B(x+d)\mathbb{1}_B(x+2d)
\end{align*}
for every subset $B\subset G$. Applying this definition to $B=A$, each summand is $1$ exactly when the three elements $x$, $x+d$, and $x+2d$ all lie in $A$, and it is $0$ otherwise.
The assumption rules out every such triple with $d\ne 0$. Therefore only the degenerate case $d=0$ can contribute. When $d=0$, the product becomes
\begin{align*}
\mathbb{1}_A(x)\mathbb{1}_A(x)\mathbb{1}_A(x)=\mathbb{1}_A(x).
\end{align*}
Thus
\begin{align*}
\Lambda_3(A)=\frac{1}{N^2}\sum_{x\in G}\mathbb{1}_A(x)=\frac{|A|}{N^2}.
\end{align*}
Since $\alpha=|A|/N$, this gives
\begin{align*}
\Lambda_3(A)=\frac{\alpha}{N}.
\end{align*}
[/guided]
[/step]
[step:Express the progression average by Fourier coefficients]
We identify the character group of $G$ with $G$ through the characters $\chi_r:G\to\mathbb C^\times$ defined in the theorem statement. Since $G$ is a finite abelian group of cardinality $N$, and since $\mathbb{1}_A:G\to\mathbb C$ is a complex-valued function, the [Fourier expansion for the normalized three-term progression average](/theorems/9088) applies.
[citetheorem:9088]
It gives
\begin{align*}
\Lambda_3(A)=\frac{1}{N^3}\sum_{r\in G}\widehat{\mathbb{1}_A}(r)^2\widehat{\mathbb{1}_A}(-2r).
\end{align*}
Here multiplication by $2$ is a bijection on $G$ because $N$ is odd, so $2$ is invertible modulo $N$.
Since
\begin{align*}
\widehat{\mathbb{1}_A}(0)=|A|=\alpha N
\end{align*}
and
\begin{align*}
\widehat{f_A}(0)=\sum_{x\in G}(\mathbb{1}_A(x)-\alpha)=|A|-\alpha N=0,
\end{align*}
we have $\widehat{\mathbb{1}_A}(r)=\widehat{f_A}(r)$ for every $r\ne 0$. Therefore
\begin{align*}
\Lambda_3(A)=\alpha^3+\frac{1}{N^3}\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r).
\end{align*}
[guided]
The Fourier theorem being used is the normalized three-term progression identity for a finite abelian group. Its hypotheses are satisfied here: $G=\mathbb Z/N\mathbb Z$ is finite abelian, its cardinality is $N$, and $\mathbb{1}_A:G\to\mathbb C$ is a complex-valued function. Under the identification of the character group with $G$ through $r\mapsto \chi_r$, the transform in that theorem is exactly the unnormalised transform from the statement, because
\begin{align*}
\overline{\chi_r(x)}=e\left(-\frac{rx}{N}\right).
\end{align*}
Thus the theorem applies.
[citetheorem:9088]
It gives
\begin{align*}
\Lambda_3(A)=\frac{1}{N^3}\sum_{r\in G}\widehat{\mathbb{1}_A}(r)^2\widehat{\mathbb{1}_A}(-2r).
\end{align*}
The oddness of $N$ is used here to ensure that multiplication by $2$ is an automorphism of $G$, since $2$ has a multiplicative inverse modulo $N$.
Now separate the zero frequency from all other frequencies. At $r=0$, the Fourier coefficient is
\begin{align*}
\widehat{\mathbb{1}_A}(0)=\sum_{x\in G}\mathbb{1}_A(x)=|A|=\alpha N.
\end{align*}
The balanced function has zero mean, because
\begin{align*}
\widehat{f_A}(0)=\sum_{x\in G}(\mathbb{1}_A(x)-\alpha)=|A|-\alpha N=0.
\end{align*}
For every nonzero $r\in G$, the constant function $x\mapsto \alpha$ has Fourier coefficient $0$, so $\widehat{\mathbb{1}_A}(r)=\widehat{f_A}(r)$. Therefore the zero-frequency term contributes $\alpha^3$, and the remaining terms give
\begin{align*}
\Lambda_3(A)=\alpha^3+\frac{1}{N^3}\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r).
\end{align*}
[/guided]
[/step]
[step:Force a large nonzero Fourier contribution]
Combining the exact value
\begin{align*}
\Lambda_3(A)=\frac{\alpha}{N}
\end{align*}
with the Fourier expansion gives
\begin{align*}
\frac{1}{N^3}\left|\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r)\right|=\left|\frac{\alpha}{N}-\alpha^3\right|.
\end{align*}
Since
\begin{align*}
N\ge 2\alpha^{-2},
\end{align*}
one has
\begin{align*}
\frac{\alpha}{N}\le \frac{\alpha^3}{2}.
\end{align*}
Hence
\begin{align*}
\frac{1}{N^3}\left|\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r)\right|\ge \frac{\alpha^3}{2}.
\end{align*}
[guided]
From the first step, the progression-free hypothesis gave the exact normalized count
\begin{align*}
\Lambda_3(A)=\frac{\alpha}{N}.
\end{align*}
From the Fourier expansion step, the same quantity is
\begin{align*}
\Lambda_3(A)=\alpha^3+\frac{1}{N^3}\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r).
\end{align*}
Equating these two expressions and subtracting $\alpha^3$ gives
\begin{align*}
\frac{1}{N^3}\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r)=\frac{\alpha}{N}-\alpha^3.
\end{align*}
Taking absolute values yields
\begin{align*}
\frac{1}{N^3}\left|\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r)\right|=\left|\frac{\alpha}{N}-\alpha^3\right|.
\end{align*}
The size hypothesis says
\begin{align*}
N\ge 2\alpha^{-2}.
\end{align*}
Since $\alpha>0$, this implies
\begin{align*}
\frac{1}{N}\le \frac{\alpha^2}{2}
\end{align*}
and therefore
\begin{align*}
\frac{\alpha}{N}\le \frac{\alpha^3}{2}.
\end{align*}
Thus $\alpha^3-\alpha/N\ge \alpha^3/2$, so
\begin{align*}
\frac{1}{N^3}\left|\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r)\right|\ge \frac{\alpha^3}{2}.
\end{align*}
This is the point where the lower bound on $N$ is used: it makes the degenerate progressions too few to cancel the zero-frequency term.
[/guided]
[/step]
[step:Bound the nonzero Fourier contribution by the largest balanced coefficient]
Define
\begin{align*}
M:=\max_{r\in G,\ r\ne 0}|\widehat{f_A}(r)|.
\end{align*}
Because multiplication by $-2$ is a bijection of $G$ and sends nonzero elements to nonzero elements, for every $r\ne 0$ one has
\begin{align*}
|\widehat{f_A}(-2r)|\le M.
\end{align*}
Therefore, by the triangle inequality,
\begin{align*}
\left|\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r)\right|\le M\sum_{r\in G}|\widehat{f_A}(r)|^2.
\end{align*}
We use the finite [Parseval identity](/theorems/248) for this unnormalised transform:
\begin{align*}
\sum_{r\in G}|\widehat{f_A}(r)|^2=N\sum_{x\in G}|f_A(x)|^2.
\end{align*}
Now
\begin{align*}
\sum_{x\in G}|f_A(x)|^2=|A|(1-\alpha)^2+(N-|A|)\alpha^2=N\alpha(1-\alpha).
\end{align*}
Thus
\begin{align*}
\sum_{r\in G}|\widehat{f_A}(r)|^2=N^2\alpha(1-\alpha)\le N^2\alpha.
\end{align*}
Combining this with the lower bound from the previous step yields
\begin{align*}
\frac{\alpha^3}{2}\le \frac{M\alpha N^2}{N^3}=\frac{M\alpha}{N}.
\end{align*}
Since $\alpha>0$, it follows that
\begin{align*}
M\ge \frac{1}{2}\alpha^2N.
\end{align*}
[guided]
The preceding step shows that the whole nonzero Fourier contribution has size at least $\alpha^3/2$ after division by $N^3$. To turn this into one large coefficient, define
\begin{align*}
M:=\max_{r\in G,\ r\ne 0}|\widehat{f_A}(r)|.
\end{align*}
Since $N$ is odd, multiplication by $-2$ is a bijection of $G$ and maps nonzero frequencies to nonzero frequencies. Hence, for each nonzero $r\in G$,
\begin{align*}
|\widehat{f_A}(-2r)|\le M.
\end{align*}
Applying the triangle inequality and then this definition of $M$ gives
\begin{align*}
\left|\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r)\right|\le \sum_{r\in G,\ r\ne 0}|\widehat{f_A}(r)|^2|\widehat{f_A}(-2r)|.
\end{align*}
Therefore
\begin{align*}
\left|\sum_{r\in G,\ r\ne 0}\widehat{f_A}(r)^2\widehat{f_A}(-2r)\right|\le M\sum_{r\in G}|\widehat{f_A}(r)|^2.
\end{align*}
We enlarged the summation domain from nonzero $r$ to all $r\in G$ in the last factor; this is valid because every term $|\widehat{f_A}(r)|^2$ is nonnegative.
The finite Parseval identity for the unnormalised transform states that
\begin{align*}
\sum_{r\in G}|\widehat{f_A}(r)|^2=N\sum_{x\in G}|f_A(x)|^2.
\end{align*}
We compute the spatial square norm directly from the definition of $f_A$. If $x\in A$, then $f_A(x)=1-\alpha$; if $x\notin A$, then $f_A(x)=-\alpha$. Hence
\begin{align*}
\sum_{x\in G}|f_A(x)|^2=|A|(1-\alpha)^2+(N-|A|)\alpha^2.
\end{align*}
Using $|A|=\alpha N$, this becomes
\begin{align*}
\sum_{x\in G}|f_A(x)|^2=N\alpha(1-\alpha)^2+N(1-\alpha)\alpha^2=N\alpha(1-\alpha).
\end{align*}
Thus
\begin{align*}
\sum_{r\in G}|\widehat{f_A}(r)|^2=N^2\alpha(1-\alpha)\le N^2\alpha.
\end{align*}
Combining this upper bound with the lower bound from the previous step gives
\begin{align*}
\frac{\alpha^3}{2}\le \frac{M\alpha N^2}{N^3}=\frac{M\alpha}{N}.
\end{align*}
Because $\alpha>0$, division by $\alpha$ is valid, and we obtain
\begin{align*}
M\ge \frac{1}{2}\alpha^2N.
\end{align*}
[/guided]
[/step]
[step:Choose the large nonzero frequency]
By the definition of $M$, there exists a nonzero $r\in G$ such that
\begin{align*}
|\widehat{f_A}(r)|=M.
\end{align*}
The previous step gives
\begin{align*}
|\widehat{f_A}(r)|\ge \frac{1}{2}\alpha^2N.
\end{align*}
Thus the theorem holds with the absolute constant given by
\begin{align*}
c:=\frac{1}{2}.
\end{align*}
[guided]
The number
\begin{align*}
M:=\max_{r\in G,\ r\ne 0}|\widehat{f_A}(r)|
\end{align*}
was defined as a maximum over the finite nonempty set $G\setminus\{0\}$. This set is nonempty because $N\ge 2\alpha^{-2}$ and $\alpha>0$ imply $N\ge 2$, while $N$ is an odd natural number. Hence there exists a nonzero $r\in G$ attaining the maximum, so
\begin{align*}
|\widehat{f_A}(r)|=M.
\end{align*}
The previous step proved
\begin{align*}
M\ge \frac{1}{2}\alpha^2N.
\end{align*}
Therefore this nonzero frequency satisfies
\begin{align*}
|\widehat{f_A}(r)|\ge \frac{1}{2}\alpha^2N.
\end{align*}
Taking the absolute constant to be
\begin{align*}
c:=\frac{1}{2}
\end{align*}
gives the claimed large-spectrum conclusion.
[/guided]
[/step]
