[proofplan] We count three-term arithmetic progressions by Fourier analysis on the finite [vector space](/page/Vector%20Space) $\mathbb{F}_p^n$. If the ambient affine space is large compared with the density, the absence of non-degenerate progressions forces a nonzero Fourier coefficient of the balanced function $\mathbb{1}_A-\alpha$ to be large. A large Fourier coefficient gives a density increment on a codimension-one affine subspace. Iterating this increment either exhausts the dimension or makes the density exceed $1$, and the resulting dimension count gives $\alpha \leq C_p n^{-1}$. [/proofplan]

[step:Define the Fourier transform and count progressions]Let $V := \mathbb{F}_p^n$, let $N := |V| = p^n$, and let \begin{align*} \omega := e^{2\pi i/p}. \end{align*} For $\xi \in V$, define the character \begin{align*} \chi_\xi: V &\to \mathbb{C} \\ x &\mapsto \omega^{\xi \cdot x}, \end{align*} where $\xi \cdot x := \sum_{j=1}^n \xi_j x_j \in \mathbb{F}_p$ is interpreted in the exponent through its representative in $\{0,\dots,p-1\}$. For a function $g: V \to \mathbb{C}$, define its normalized [Fourier transform](/page/Fourier%20Transform) by \begin{align*} \widehat{g}: V &\to \mathbb{C} \\ \xi &\mapsto \mathbb{E}_{x \in V} g(x)\overline{\chi_\xi(x)} = \frac{1}{N}\sum_{x \in V} g(x)\overline{\chi_\xi(x)}. \end{align*} The character orthogonality relation is \begin{align*} \mathbb{E}_{x \in V}\chi_\xi(x) = \begin{cases} 1, & \xi = 0,\\ 0, & \xi \neq 0. \end{cases} \end{align*} Indeed, if $\xi \neq 0$, choose $h \in V$ with $\xi \cdot h \neq 0$; translation by $h$ gives \begin{align*} \mathbb{E}_{x \in V}\chi_\xi(x) = \mathbb{E}_{x \in V}\chi_\xi(x+h) = \chi_\xi(h)\mathbb{E}_{x \in V}\chi_\xi(x), \end{align*} and $\chi_\xi(h)\neq 1$, so the expectation is $0$. Let $a := \mathbb{1}_A:V \to \{0,1\}$. Define the normalized three-term progression count \begin{align*} T(a) := \mathbb{E}_{x,d \in V} a(x)a(x+d)a(x+2d). \end{align*} Fourier inversion, obtained from the orthogonality relation, gives \begin{align*} a(x)=\sum_{\xi \in V}\widehat{a}(\xi)\chi_\xi(x). \end{align*} Substituting this into $T(a)$ and using orthogonality in the variables $x$ and $d$ gives \begin{align*} T(a) &= \sum_{\xi,\eta,\zeta \in V} \widehat{a}(\xi)\widehat{a}(\eta)\widehat{a}(\zeta) \mathbb{E}_{x,d \in V} \chi_\xi(x)\chi_\eta(x+d)\chi_\zeta(x+2d)\\ &= \sum_{\xi,\eta,\zeta \in V} \widehat{a}(\xi)\widehat{a}(\eta)\widehat{a}(\zeta) \mathbb{E}_{x \in V}\chi_{\xi+\eta+\zeta}(x) \mathbb{E}_{d \in V}\chi_{\eta+2\zeta}(d)\\ &= \sum_{\zeta \in V}\widehat{a}(\zeta)^2\widehat{a}(-2\zeta). \end{align*} The last equality uses that $p$ is odd, so multiplication by $2$ is invertible in $\mathbb{F}_p$.[/step]

[guided]The purpose of the Fourier transform is to diagonalize the condition that three points form an arithmetic progression. We work with normalized averages, so all quantities are scale-free in the size $N=p^n$. For each frequency $\xi \in V$, the character \begin{align*} \chi_\xi: V &\to \mathbb{C} \\ x &\mapsto \omega^{\xi \cdot x} \end{align*} is a group homomorphism from the additive group of $V$ to the unit circle. The orthogonality identity says that a nontrivial character averages to zero. If $\xi\neq 0$, there is $h\in V$ with $\xi\cdot h\neq 0$. Since translation preserves the uniform average on $V$, \begin{align*} \mathbb{E}_{x \in V}\chi_\xi(x) = \mathbb{E}_{x \in V}\chi_\xi(x+h) = \chi_\xi(h)\mathbb{E}_{x \in V}\chi_\xi(x). \end{align*} Because $\chi_\xi(h)\neq 1$, the only possible value of the expectation is $0$. For $\xi=0$, the character is identically $1$, so the expectation is $1$. Now define $a:=\mathbb{1}_A$. The quantity \begin{align*} T(a):=\mathbb{E}_{x,d\in V}a(x)a(x+d)a(x+2d) \end{align*} is the normalized number of ordered three-term progressions in $A$, including the degenerate progressions with $d=0$. Fourier inversion writes \begin{align*} a(x)=\sum_{\xi\in V}\widehat a(\xi)\chi_\xi(x). \end{align*} Substituting this expression at $x$, $x+d$, and $x+2d$, we obtain \begin{align*} T(a) &= \sum_{\xi,\eta,\zeta \in V} \widehat{a}(\xi)\widehat{a}(\eta)\widehat{a}(\zeta) \mathbb{E}_{x,d \in V} \chi_\xi(x)\chi_\eta(x+d)\chi_\zeta(x+2d)\\ &= \sum_{\xi,\eta,\zeta \in V} \widehat{a}(\xi)\widehat{a}(\eta)\widehat{a}(\zeta) \mathbb{E}_{x \in V}\chi_{\xi+\eta+\zeta}(x) \mathbb{E}_{d \in V}\chi_{\eta+2\zeta}(d). \end{align*} The $x$-average vanishes unless $\xi+\eta+\zeta=0$, and the $d$-average vanishes unless $\eta+2\zeta=0$. Since $p$ is odd, $2$ is invertible, so these two equations force $\eta=-2\zeta$ and $\xi=\zeta$. Therefore \begin{align*} T(a)=\sum_{\zeta\in V}\widehat a(\zeta)^2\widehat a(-2\zeta). \end{align*} This is the Fourier formula that turns a shortage of progressions into information about nonzero Fourier coefficients.[/guided]

[step:Force a large nonzero Fourier coefficient from the missing progressions]Define the balanced function \begin{align*} f: V &\to \mathbb{R} \\ x &\mapsto a(x)-\alpha. \end{align*} Then $\widehat{a}(0)=\alpha$, $\widehat{f}(0)=0$, and $\widehat{a}(\xi)=\widehat{f}(\xi)$ for every $\xi \neq 0$. Since $A$ contains no non-degenerate three-term arithmetic progression, the only progressions counted by $T(a)$ have $d=0$. Hence \begin{align*} T(a)=\frac{|A|}{N^2}=\frac{\alpha}{N}. \end{align*} Assume first that \begin{align*} N \geq 2\alpha^{-2}. \end{align*} Then \begin{align*} T(a)\leq \frac{\alpha^3}{2}. \end{align*} Using the progression-count formula, \begin{align*} \left|\sum_{\zeta \in V\setminus\{0\}}\widehat{a}(\zeta)^2\widehat{a}(-2\zeta)\right| = |\alpha^3-T(a)| \geq \frac{\alpha^3}{2}. \end{align*} Let \begin{align*} M := \max_{\xi \in V\setminus\{0\}}|\widehat{f}(\xi)|. \end{align*} Since multiplication by $-2$ is a bijection of $V\setminus\{0\}$, \begin{align*} \frac{\alpha^3}{2} &\leq \sum_{\zeta \in V\setminus\{0\}} |\widehat{a}(\zeta)|^2|\widehat{a}(-2\zeta)|\\ &\leq M\sum_{\zeta \in V\setminus\{0\}}|\widehat{a}(\zeta)|^2. \end{align*} [Parseval's identity](/theorems/434) for the normalized Fourier transform gives \begin{align*} \sum_{\zeta \in V}|\widehat{a}(\zeta)|^2 = \mathbb{E}_{x \in V}|a(x)|^2 = \alpha. \end{align*} Therefore \begin{align*} M \geq \frac{\alpha^2}{2}. \end{align*}[/step]

[guided]The balanced function \begin{align*} f:V&\to\mathbb{R}\\ x&\mapsto a(x)-\alpha \end{align*} removes the constant density contribution from $a$. Since $\mathbb{E}_{x\in V}a(x)=\alpha$, we have $\widehat f(0)=0$, while for every nonzero $\xi$ the constant function $\alpha$ has zero Fourier coefficient, so $\widehat a(\xi)=\widehat f(\xi)$. The hypothesis that $A$ has no non-degenerate progression means that whenever $a(x)a(x+d)a(x+2d)=1$, we must have $d=0$. Thus the only contributing pairs are $(x,0)$ with $x\in A$, and therefore \begin{align*} T(a)=\frac{|A|}{N^2}=\frac{\alpha}{N}. \end{align*} If $N\geq 2\alpha^{-2}$, then this count is at most half of the random main term: \begin{align*} T(a)\leq \frac{\alpha^3}{2}. \end{align*} The Fourier formula separates the zero frequency from the nonzero frequencies: \begin{align*} T(a) = \widehat a(0)^2\widehat a(0) + \sum_{\zeta\in V\setminus\{0\}}\widehat a(\zeta)^2\widehat a(-2\zeta) = \alpha^3+ \sum_{\zeta\in V\setminus\{0\}}\widehat a(\zeta)^2\widehat a(-2\zeta). \end{align*} Since $T(a)\leq \alpha^3/2$, the nonzero frequencies must account for a cancellation of size at least $\alpha^3/2$: \begin{align*} \left|\sum_{\zeta\in V\setminus\{0\}}\widehat a(\zeta)^2\widehat a(-2\zeta)\right| \geq \frac{\alpha^3}{2}. \end{align*} Let \begin{align*} M:=\max_{\xi\in V\setminus\{0\}}|\widehat f(\xi)|. \end{align*} For $\zeta\neq 0$, both $\zeta$ and $-2\zeta$ are nonzero, because $p$ is odd. Hence \begin{align*} |\widehat a(-2\zeta)|=|\widehat f(-2\zeta)|\leq M. \end{align*} Therefore \begin{align*} \frac{\alpha^3}{2} &\leq \sum_{\zeta\in V\setminus\{0\}} |\widehat a(\zeta)|^2|\widehat a(-2\zeta)|\\ &\leq M\sum_{\zeta\in V\setminus\{0\}}|\widehat a(\zeta)|^2. \end{align*} Parseval's identity follows from character orthogonality and gives \begin{align*} \sum_{\zeta\in V}|\widehat a(\zeta)|^2 = \mathbb{E}_{x\in V}|a(x)|^2. \end{align*} Since $a$ is an indicator, $a^2=a$, so the right-hand side is $\alpha$. Thus \begin{align*} \frac{\alpha^3}{2}\leq M\alpha, \end{align*} and hence \begin{align*} M\geq \frac{\alpha^2}{2}. \end{align*} This is the key Fourier consequence: if the progression count is too small, then $A$ has a strong bias along some nonzero character.[/guided]

[step:Convert a large Fourier coefficient into a density increment]Let $\xi \in V\setminus\{0\}$ satisfy \begin{align*} |\widehat f(\xi)|\geq \frac{\alpha^2}{2}. \end{align*} For each $t\in \mathbb{F}_p$, define the affine hyperplane \begin{align*} H_t:=\{x\in V:\xi\cdot x=t\}. \end{align*} Each $H_t$ has cardinality $N/p$. Define the density of $A$ on $H_t$ by \begin{align*} \alpha_t:=\frac{|A\cap H_t|}{|H_t|}. \end{align*} Then \begin{align*} \widehat f(\xi) &= \frac{1}{N}\sum_{x\in V}(a(x)-\alpha)\omega^{-\xi\cdot x}\\ &= \frac{1}{p}\sum_{t\in\mathbb{F}_p}(\alpha_t-\alpha)\omega^{-t}. \end{align*} Let $\delta_t:=\alpha_t-\alpha$ for $t\in\mathbb{F}_p$. Since the hyperplanes $H_t$ partition $V$ into equal-size pieces, \begin{align*} \sum_{t\in\mathbb{F}_p}\delta_t=0. \end{align*} Thus \begin{align*} \frac{\alpha^2}{2} \leq |\widehat f(\xi)| \leq \frac{1}{p}\sum_{t\in\mathbb{F}_p}|\delta_t| = \frac{2}{p}\sum_{\delta_t>0}\delta_t \leq 2\max_{t\in\mathbb{F}_p}\delta_t. \end{align*} Therefore there exists $t_0\in\mathbb{F}_p$ such that \begin{align*} \alpha_{t_0}\geq \alpha+\frac{\alpha^2}{4}. \end{align*} So, provided $p^n\geq 2\alpha^{-2}$, a progression-free set of density $\alpha$ in $V$ has density at least $\alpha+\alpha^2/4$ on some affine hyperplane.[/step]

[guided]A nonzero Fourier coefficient measures correlation with the character $x\mapsto \omega^{\xi\cdot x}$. This character is constant on each affine hyperplane \begin{align*} H_t=\{x\in V:\xi\cdot x=t\}. \end{align*} Because $\xi\neq 0$, the [linear map](/page/Linear%20Map) $x\mapsto \xi\cdot x$ from $V$ to $\mathbb{F}_p$ is surjective, so each fiber $H_t$ has size $N/p$. Let \begin{align*} \alpha_t:=\frac{|A\cap H_t|}{|H_t|} \end{align*} be the density of $A$ on the fiber $H_t$. The Fourier coefficient can be grouped by these fibers: \begin{align*} \widehat f(\xi) &= \frac{1}{N}\sum_{x\in V}(a(x)-\alpha)\omega^{-\xi\cdot x}\\ &= \frac{1}{N}\sum_{t\in\mathbb{F}_p} \sum_{x\in H_t}(a(x)-\alpha)\omega^{-t}\\ &= \frac{1}{p}\sum_{t\in\mathbb{F}_p}(\alpha_t-\alpha)\omega^{-t}. \end{align*} Set $\delta_t:=\alpha_t-\alpha$. Since the $H_t$ partition $V$ into equal-size pieces, the average of the $\alpha_t$ is $\alpha$, and hence \begin{align*} \sum_{t\in\mathbb{F}_p}\delta_t=0. \end{align*} The positive deviations and negative deviations therefore have the same total magnitude: \begin{align*} \sum_{t\in\mathbb{F}_p}|\delta_t| = 2\sum_{\delta_t>0}\delta_t. \end{align*} Using the large Fourier coefficient and the triangle inequality, \begin{align*} \frac{\alpha^2}{2} \leq |\widehat f(\xi)| \leq \frac{1}{p}\sum_{t\in\mathbb{F}_p}|\delta_t| = \frac{2}{p}\sum_{\delta_t>0}\delta_t \leq 2\max_{t\in\mathbb{F}_p}\delta_t. \end{align*} Thus some fiber satisfies \begin{align*} \delta_{t_0}\geq \frac{\alpha^2}{4}, \end{align*} or equivalently \begin{align*} \alpha_{t_0}\geq \alpha+\frac{\alpha^2}{4}. \end{align*} This is the density increment step: a large Fourier bias lets us pass to a codimension-one affine subspace where the density has increased by a quadratic amount.[/guided]

[step:Iterate the density increment inside affine subspaces]The previous argument applies verbatim inside any affine subspace of $V$. More precisely, if $W\subset V$ is an affine subspace of dimension $m\geq 1$, if $B:=A\cap W$ has relative density $\gamma:=|B|/|W|>0$, and if \begin{align*} |W|=p^m\geq 2\gamma^{-2}, \end{align*} then there is an affine hyperplane $W'\subset W$ such that \begin{align*} \frac{|A\cap W'|}{|W'|} \geq \gamma+\frac{\gamma^2}{4}. \end{align*} This follows by choosing a point $w_0\in W$, writing $W=w_0+L$ for an $m$-dimensional linear subspace $L\subset V$, and applying the preceding Fourier argument to the set \begin{align*} B_0:=\{y\in L:w_0+y\in A\}\subset L. \end{align*} The set $B_0$ has no non-degenerate three-term arithmetic progression in $L$, because such a progression would translate to one in $A\cap W$. Starting with $W_0:=V$ and $\gamma_0:=\alpha$, construct affine subspaces \begin{align*} W_0 \supset W_1 \supset \cdots \supset W_r \end{align*} as long as the density increment step applies. Write \begin{align*} m_i:=\dim W_i, \qquad \gamma_i:=\frac{|A\cap W_i|}{|W_i|}. \end{align*} At each successful step, \begin{align*} m_{i+1}=m_i-1, \qquad \gamma_{i+1}\geq \gamma_i+\frac{\gamma_i^2}{4}. \end{align*} Since every $\gamma_i\leq 1$, \begin{align*} \frac{1}{\gamma_{i+1}} \leq \frac{1}{\gamma_i+\gamma_i^2/4} = \frac{1}{\gamma_i}\cdot \frac{1}{1+\gamma_i/4} \leq \frac{1}{\gamma_i}-\frac{1}{5}. \end{align*} The last inequality uses $0<\gamma_i\leq 1$. Therefore the number $r$ of successful increments satisfies \begin{align*} r<\frac{5}{\alpha}. \end{align*}[/step]

[guided]The density increment argument is not tied to the original ambient space $V$. If $W\subset V$ is an affine subspace, choose $w_0\in W$ and write $W=w_0+L$, where $L$ is a linear subspace. The translation map \begin{align*} L&\to W\\ y&\mapsto w_0+y \end{align*} identifies subsets of $W$ with subsets of $L$. Under this identification, a progression \begin{align*} y,\quad y+d,\quad y+2d \end{align*} in $L$ translates to \begin{align*} w_0+y,\quad w_0+y+d,\quad w_0+y+2d \end{align*} in $W$. If $d\neq 0$, non-degeneracy is preserved. Hence $A\cap W$ remains progression-free inside $W$. Thus, whenever $B=A\cap W$ has relative density $\gamma$ and $|W|=p^m\geq 2\gamma^{-2}$, the Fourier argument gives an affine hyperplane $W'\subset W$ with density at least \begin{align*} \gamma+\frac{\gamma^2}{4}. \end{align*} We now iterate. Define $W_0:=V$ and $\gamma_0:=\alpha$. After each successful increment, the dimension drops by exactly one and the density increases: \begin{align*} m_{i+1}=m_i-1, \qquad \gamma_{i+1}\geq \gamma_i+\frac{\gamma_i^2}{4}. \end{align*} The density can never exceed $1$, because it is the relative size of a subset. To turn this into a bound on the number of iterations, look at reciprocals. For $0<\gamma_i\leq 1$, \begin{align*} \frac{1}{\gamma_{i+1}} \leq \frac{1}{\gamma_i+\gamma_i^2/4} = \frac{1}{\gamma_i}\cdot\frac{1}{1+\gamma_i/4}. \end{align*} Also, \begin{align*} \frac{1}{\gamma_i}-\frac{1}{\gamma_i+\gamma_i^2/4} = \frac{1}{4+\gamma_i} \geq \frac{1}{5}. \end{align*} So every successful density increment decreases $1/\gamma_i$ by at least $1/5$. Since initially $1/\gamma_0=1/\alpha$ and reciprocals remain positive, there can be fewer than $5/\alpha$ successful increments: \begin{align*} r<\frac{5}{\alpha}. \end{align*}[/guided]

[step:Bound the terminal dimension and conclude the density estimate]When the iteration stops at $W_r$, either $\dim W_r=0$ or the size condition for another increment fails. In both cases, \begin{align*} m_r \leq \log_p 2 + 2\log_p(\alpha^{-1}). \end{align*} Indeed, if $m_r>0$ and the size condition fails, then \begin{align*} p^{m_r}<2\gamma_r^{-2}\leq 2\alpha^{-2}, \end{align*} because $\gamma_r\geq \alpha$. Now assume first that $N=p^n\geq 2\alpha^{-2}$. Combining the bounds for the number of increments and the terminal dimension gives \begin{align*} n = r+m_r < \frac{5}{\alpha} + \log_p 2 + 2\log_p(\alpha^{-1}). \end{align*} Multiplying by $\alpha$ and using \begin{align*} \sup_{0<u\leq 1} u\log_p(u^{-1}) = \frac{1}{e\ln p}, \end{align*} we obtain \begin{align*} \alpha n \leq 5+\log_p 2+\frac{2}{e\ln p}. \end{align*} It remains to handle the case $N<2\alpha^{-2}$. Then \begin{align*} \alpha<\sqrt{2}\,p^{-n/2}. \end{align*} Since \begin{align*} \sup_{x>0} xp^{-x/2}=\frac{2}{e\ln p}, \end{align*} we have \begin{align*} \alpha n < \frac{2\sqrt{2}}{e\ln p}. \end{align*} Therefore the theorem holds with, for example, \begin{align*} C_p := 5+\log_p 2+\frac{2}{e\ln p}+\frac{2\sqrt{2}}{e\ln p}. \end{align*} This constant depends only on $p$, and the desired estimate \begin{align*} \alpha\leq C_p n^{-1} \end{align*} follows.[/step]

[guided]At the end of the iteration, there are two possible reasons we cannot continue. Either the affine subspace has dimension $0$, or the hypothesis needed for the Fourier step, \begin{align*} |W_r|=p^{m_r}\geq 2\gamma_r^{-2}, \end{align*} has failed. If the dimension is $0$, then $m_r=0$, which is already bounded by the desired expression. If the size condition fails, then \begin{align*} p^{m_r}<2\gamma_r^{-2}. \end{align*} The densities only increase during the iteration, so $\gamma_r\geq\alpha$. Hence \begin{align*} p^{m_r}<2\alpha^{-2}, \end{align*} and taking logarithms base $p$ gives \begin{align*} m_r\leq \log_p2+2\log_p(\alpha^{-1}). \end{align*} In the main case $N=p^n\geq 2\alpha^{-2}$, the iteration starts legitimately. Since each successful step lowers the dimension by one, \begin{align*} n=r+m_r. \end{align*} Using the bound $r<5/\alpha$ and the terminal dimension estimate, \begin{align*} n < \frac{5}{\alpha} + \log_p2 + 2\log_p(\alpha^{-1}). \end{align*} Multiplying by $\alpha$ gives \begin{align*} \alpha n < 5+\alpha\log_p2+2\alpha\log_p(\alpha^{-1}). \end{align*} For $0<u\leq 1$, the function $u\ln(u^{-1})$ has maximum $1/e$, attained at $u=e^{-1}$. Therefore \begin{align*} \alpha\log_p(\alpha^{-1}) = \frac{\alpha\ln(\alpha^{-1})}{\ln p} \leq \frac{1}{e\ln p}. \end{align*} Also $\alpha\leq 1$, so $\alpha\log_p2\leq \log_p2$. Thus \begin{align*} \alpha n \leq 5+\log_p2+\frac{2}{e\ln p}. \end{align*} If the main size condition fails at the original level, then \begin{align*} p^n<2\alpha^{-2}, \end{align*} which implies \begin{align*} \alpha<\sqrt{2}\,p^{-n/2}. \end{align*} The function $x\mapsto xp^{-x/2}$ on $(0,\infty)$ has maximum $2/(e\ln p)$, so \begin{align*} \alpha n<\frac{2\sqrt{2}}{e\ln p}. \end{align*} Combining the two cases, the estimate holds with \begin{align*} C_p := 5+\log_p 2+\frac{2}{e\ln p}+\frac{2\sqrt{2}}{e\ln p}. \end{align*} This constant depends only on the prime $p$, and therefore \begin{align*} \alpha\leq C_p n^{-1}. \end{align*}[/guided]