[proofplan]
We first turn the large Fourier coefficient into a positive real correlation between the balanced function $f_A$ and a nontrivial additive character. The phase circle is then partitioned into consecutive residue intervals of length comparable to $\eta N$; on each such interval the character is almost constant, so the original correlation is still visible after replacing the character by an interval-constant approximation. A zero-mean pigeonhole argument forces one interval to have positive average of $f_A$, which is exactly a density increment. Finally, multiplication by $r^{-1}$ converts the favourable phase interval into a proper arithmetic progression in $G$.
[/proofplan]
[step:Record the zero mean and the elementary size restrictions]
Since $r\ne 0$ in $G=\mathbb Z/N\mathbb Z$ and $N$ is prime, multiplication by $r$ is a bijection of $G$. Also,
\begin{align*}
\sum_{x\in G}e\left(-\frac{rx}{N}\right)=0,
\end{align*}
because this is the sum of all powers of a nontrivial $N$-th root of unity. Hence
\begin{align*}
\widehat{f_A}(r)=\sum_{x\in A}e\left(-\frac{rx}{N}\right).
\end{align*}
The same identity applied to $G\setminus A$ gives
\begin{align*}
\widehat{f_A}(r)=-\sum_{x\in G\setminus A}e\left(-\frac{rx}{N}\right).
\end{align*}
Therefore
\begin{align*}
\eta N\le |\widehat{f_A}(r)|\le |G\setminus A|=(1-\alpha)N.
\end{align*}
In particular,
\begin{align*}
\eta\le 1-\alpha.
\end{align*}
[/step]
[step:Handle the case where the required progression length is at most one]
Set
\begin{align*}
c:=10^{-3}.
\end{align*}
Suppose first that $\eta N\le 10^3$. Since $\eta>0$ and $|\widehat{f_A}(r)|\ge \eta N$, the set $A$ is nonempty. Choose $a\in A$, choose any $d\in G\setminus\{0\}$, and put
\begin{align*}
P:=\{a\}.
\end{align*}
Then $P=\{a+jd:0\le j\le 0\}$ is a proper arithmetic progression of length $L=1$, and
\begin{align*}
L=1\ge 10^{-3}\eta N=c\eta N.
\end{align*}
Moreover, by the estimate $\eta\le 1-\alpha$,
\begin{align*}
\frac{|A\cap P|}{|P|}=1\ge \alpha+\eta\ge \alpha+c\eta.
\end{align*}
The additional no-wraparound assertion is also satisfied, since the image of a singleton under multiplication by $r$ is a consecutive interval of length $1$.
[/step]
[step:Choose a phase so the Fourier coefficient has positive real part]
Assume from now on that $\eta N>10^3$. Choose $\lambda\in\mathbb C$ with $|\lambda|=1$ such that
\begin{align*}
\operatorname{Re}\left(\lambda\widehat{f_A}(r)\right)=|\widehat{f_A}(r)|.
\end{align*}
Define the real-valued function $\Phi:G\to\mathbb R$ by
\begin{align*}
\Phi(x):=\operatorname{Re}\left(\lambda e\left(-\frac{rx}{N}\right)\right).
\end{align*}
Then, because $f_A$ is real-valued,
\begin{align*}
\sum_{x\in G}f_A(x)\Phi(x)=\operatorname{Re}\left(\lambda\widehat{f_A}(r)\right)\ge \eta N.
\end{align*}
[guided]
The Fourier coefficient is complex, but a density increment is a real inequality. We therefore rotate the complex plane so that the coefficient points in the positive real direction. Choose $\lambda\in\mathbb C$ with $|\lambda|=1$ and
\begin{align*}
\operatorname{Re}\left(\lambda\widehat{f_A}(r)\right)=|\widehat{f_A}(r)|.
\end{align*}
Now define $\Phi:G\to\mathbb R$ by
\begin{align*}
\Phi(x):=\operatorname{Re}\left(\lambda e\left(-\frac{rx}{N}\right)\right).
\end{align*}
Since $f_A(x)\in\mathbb R$ for every $x\in G$, taking the real part may be passed through the finite sum:
\begin{align*}
\sum_{x\in G}f_A(x)\Phi(x)=\operatorname{Re}\left(\lambda\sum_{x\in G}f_A(x)e\left(-\frac{rx}{N}\right)\right).
\end{align*}
By the definition of the [Fourier transform](/page/Fourier%20Transform), the sum on the right is $\widehat{f_A}(r)$. Hence
\begin{align*}
\sum_{x\in G}f_A(x)\Phi(x)=\operatorname{Re}\left(\lambda\widehat{f_A}(r)\right)=|\widehat{f_A}(r)|\ge \eta N.
\end{align*}
This is the real positive correlation that will be localized to a long interval of phases.
[/guided]
[/step]
[step:Partition the phase residues into long consecutive intervals]
Let
\begin{align*}
M:=\left\lfloor \frac{\eta N}{100}\right\rfloor.
\end{align*}
Since $\eta N>10^3$, one has $M\ge 10$. Since $\eta\le 1$, one also has $M\le N/100$. Partition the integer interval $\{0,1,\dots,N-1\}$ into consecutive integer intervals $I_1,\dots,I_J$ such that
\begin{align*}
M\le |I_j|\le 2M
\end{align*}
for every $1\le j\le J$. For each $j$, let $b_j$ be the least integer in $I_j$, and define the function $\Psi:G\to\mathbb R$ as follows: if the integer representative $y\in\{0,\dots,N-1\}$ of $rx\in G$ lies in $I_j$, set
\begin{align*}
\Psi(x):=\operatorname{Re}\left(\lambda e\left(-\frac{b_j}{N}\right)\right).
\end{align*}
For $y\in I_j$, the elementary Lipschitz estimate $|e(u)-e(v)|\le 2\pi |u-v|$ gives
\begin{align*}
\left|e\left(-\frac{y}{N}\right)-e\left(-\frac{b_j}{N}\right)\right|\le \frac{2\pi |y-b_j|}{N}\le \frac{4\pi M}{N}\le \frac{\eta}{4}.
\end{align*}
Thus
\begin{align*}
|\Phi(x)-\Psi(x)|\le \frac{\eta}{4}
\end{align*}
for every $x\in G$. Since $|f_A(x)|\le 1$ for every $x\in G$,
\begin{align*}
\left|\sum_{x\in G}f_A(x)\Phi(x)-\sum_{x\in G}f_A(x)\Psi(x)\right|\le \frac{\eta N}{4}.
\end{align*}
Consequently,
\begin{align*}
\sum_{x\in G}f_A(x)\Psi(x)\ge \frac{3\eta N}{4}.
\end{align*}
[/step]
[step:Find one phase interval with positive balanced average]
For $1\le j\le J$, define the subset $B_j\subset G$ by
\begin{align*}
B_j:=\{x\in G:rx\text{ has integer representative in }I_j\}.
\end{align*}
Define the real number $F_j$ by
\begin{align*}
F_j:=\sum_{x\in B_j}f_A(x).
\end{align*}
The sets $B_1,\dots,B_J$ form a partition of $G$, and
\begin{align*}
\sum_{j=1}^J F_j=\sum_{x\in G}f_A(x)=0.
\end{align*}
Let $\beta\in\mathbb R$ be the maximal normalized positive average
\begin{align*}
\beta:=\max_{1\le j\le J}\frac{F_j}{|B_j|}.
\end{align*}
Since $\Psi$ is constant on each $B_j$ and $|\Psi|\le 1$, we have
\begin{align*}
\frac{3\eta N}{4}\le \sum_{j=1}^J \Psi(B_j)F_j\le \sum_{j=1}^J |F_j|.
\end{align*}
Here $\Psi(B_j)$ denotes the common value of $\Psi$ on $B_j$. Because $\sum_j F_j=0$,
\begin{align*}
\sum_{j=1}^J |F_j|=2\sum_{\substack{1\le j\le J, F_j>0}}F_j.
\end{align*}
For every $j$ with $F_j>0$, the definition of $\beta$ gives $F_j\le \beta |B_j|$. Therefore
\begin{align*}
\frac{3\eta N}{4}\le 2\beta\sum_{j=1}^J |B_j|=2\beta N.
\end{align*}
Hence
\begin{align*}
\beta\ge \frac{3\eta}{8}.
\end{align*}
Choose an index $j_0$ such that
\begin{align*}
\frac{F_{j_0}}{|B_{j_0}|}=\beta.
\end{align*}
Then
\begin{align*}
\frac{|A\cap B_{j_0}|}{|B_{j_0}|}=\alpha+\frac{F_{j_0}}{|B_{j_0}|}\ge \alpha+\frac{3\eta}{8}.
\end{align*}
[/step]
[step:Pull the favourable phase interval back to a proper arithmetic progression]
Write
\begin{align*}
I_{j_0}=\{b,b+1,\dots,b+L-1\}
\end{align*}
with integers $b,L$ satisfying $0\le b\le b+L-1<N$. Since multiplication by $r$ is a bijection of $G$, there is a unique $r^{-1}\in G$ such that $rr^{-1}=1$. Define
\begin{align*}
a:=r^{-1}\bar b
\end{align*}
and
\begin{align*}
d:=r^{-1}.
\end{align*}
Then $d\ne 0$ and
\begin{align*}
B_{j_0}=\{a+jd:0\le j\le L-1\}.
\end{align*}
The displayed elements are distinct, because their images under multiplication by $r$ are the distinct residues $\bar b,\overline{b+1},\dots,\overline{b+L-1}$. Also,
\begin{align*}
L=|I_{j_0}|\ge M\ge \frac{\eta N}{200}\ge c\eta N.
\end{align*}
Set $P:=B_{j_0}$. The density estimate from the previous step gives
\begin{align*}
\frac{|A\cap P|}{|P|}\ge \alpha+\frac{3\eta}{8}\ge \alpha+c\eta.
\end{align*}
Finally, by construction,
\begin{align*}
rP=\{\bar b,\overline{b+1},\dots,\overline{b+L-1}\},
\end{align*}
with $0\le b\le b+L-1<N$, so the phase-coordinate parametrisation is an interval without wraparound. This proves the theorem.
[/step]
