4. Roth 定理与流行公差

多项式方法给出了 ${\mathbb{F}}_3^n$ 上 Roth 定理更好的上界, 现在我们将给出另一个不同的证明. 该证明给出的上界稍差, 但是方法有很强的启发性和影响力. 这个证明涉及到 “流行公差” (popular common difference) .

定理 4.1 (Green (2005)). 对于任意 $ϵ>0$, 存在 $n_0=n_0(ϵ)$ 使得以下成立: 对于 $n\ge n_0$ 和任意满足 $|A|=\alpha 3^n$ 的 $A\subseteq {\mathbb{F}}_3^n$, 存在 $y\ne 0$ 满足$$\left|\{x:x,x+y,x+2y\in A\}\right|\ge \left({\alpha }^3-ϵ\right)3^n$$

这里的 $y$ 是流行公差. 该定理给出了在 $A$ 中具有公差为 $y$ 的 3-AP 的数量的下界. 请注意, 如果 $A$ 是 ${\mathbb{F}}_3^n$ 中大小为 $\alpha 3^n$ 的随机子集, 则公差为 $y$ 的 3-AP 的期望数量大致是 ${\alpha }^3{3}^n$. 该定理表明我们可以找到一些 $y$, 使得公差为 $y$ 的 3-AP 的数量接近我们在随机集中的所期望的那样.

Green 证明了 $n_0=\mathrm{tow}\left((1/ϵ{)}^{O(1)}\right)$ 这个定理是正确的. Fox-Pham 在 2019 年使用正则性方法将这个下界改进为 $n_0=\mathrm{tow}\left(O\left(\log \frac{1}{ϵ}\right)\right)$. 同时, 他们证明了他们的下界是紧的.

引理 4.2 (有界增量). 令 $\alpha ,ϵ>0$. 如果 ${\alpha }_0,{\alpha }_1,\dots \in [0,1]$ 满足 ${\alpha }_0\ge \alpha$, 则存在 $k\le \lceil lo{g}_2\frac{1}{ϵ}\rceil$ 使得 $2{\alpha }_k-{\alpha }_{k+1}\ge {\alpha }^3-ϵ$.

证明. 反证法. 假设不存在, 则 ${\alpha }_1\ge 2{\alpha }_0-{\alpha }^3+ϵ\ge {\alpha }^3+ϵ$. 同理有 ${\alpha }_2\ge 2{\alpha }_1-{\alpha }^3+ϵ\ge {\alpha }^3+2ϵ$. 继续这个过程, 我们会发现对于所有 $1\le k\le \lceil {\log }_2\frac{1}{ϵ}\rceil +1$ 有 ${\alpha }_k\ge {\alpha }^3+2^{k-1}ϵ$. 取 $k=\lceil {\log }_2\frac{1}{ϵ}\rceil +1$ 我们得到 ${\alpha }_k>1$, 矛盾.

$\square$

令 $f:{\mathbb{F}}_3^n\to \mathbb{C}$. 令 $U\le {\mathbb{F}}_3^n$, 这个符号的意思是 $U$ 是 ${\mathbb{F}}_3^n$ 的一个子空间. 令 $f_U(x)$ 是 $U$ 的陪集上 $f(x)$ 的平均值.

下面的引理类似正则性引理.

引理 4.3. 对于任意 $ϵ>0$, 存在 $m=\mathrm{tow}\left(O\left(\log \frac{1}{ϵ}\right)\right)$ 使得对于所有 $f:{\mathbb{F}}_3^n\to [0,1]$, 存在子空间 $W\le U\le {\mathbb{F}}_3^n$ (并且满足 $\mathrm{codim}W\le m$) 使得$${\Vert \widehat{f-f_W}\Vert }_{\infty }\le \frac{ϵ}{\left|U^{\perp }\right|}$$和$$2{\Vert f_U\Vert }_3^3-{\Vert f_W\Vert }_3^3\ge (\mathbb{E}f{)}^3-ϵ$$同时成立.

证明. 令 ${ϵ}_0:=1$ , ${ϵ}_{k+1}:=ϵ3^{-1/{ϵ}_k^2}$ , 整数 $k\ge 0$. 我们发现有递归表示 ${ϵ}_{k+1}^{-2}={ϵ}^{-2}{3}^{2/{ϵ}_k^2}$, 所以对于足够大的 $k$, 我们有$${ϵ}_{k+1}^{-2}\le 2^{2^{e_k^{-2}}}$$令$$R_k:=\left\{r\in {\mathbb{F}}_3^n:|\hat{f}(r)|\ge {ϵ}_k\right\}$$根据 Parseval 的恒等式, ${\sum }_r|\hat{f}(r){|}^2=\mathbb{E}\left[f^2\right]\le 1$, 所以 $\left|R_k\right|\le {ϵ}_k^{-2}$. 我们定义 $U_k:=R_k^{\perp }$ 和 ${\alpha }_k:={\Vert f_{U_k}\Vert }_3^3$. 根据凸性, 容易验证 ${\alpha }_k\ge (\mathbb{E}f{)}^3$ . 根据前面引理, 存在 $k=O\left(\log \frac{1}{ϵ}\right)$ 使得 $2{\alpha }_k-{\alpha }_{k+1}\ge (\mathbb{E}f{)}^3-ϵ$. 对于所选的 $k$ , 令 $m:={ϵ}_{k+1}^{-2}$. 整理后我们发现 $m=\mathrm{tow}\left(O\left(\log \frac{1}{ϵ}\right)\right)$.

我们直接给出下述结论 (容易验证) . $$\widehat{f_W}(r)=\{\begin{array}{ll}\hat{f}(r)& \text{ if }r\in W^{\perp }\\ 0& \text{ if }r\notin W^{\perp }\end{array}$$所以$${\Vert \widehat{f-f_{U_{k+1}}}\Vert }_{\infty }\le \underset{r\notin R_{k+1}}{\max }|\hat{f}(r)|\le {ϵ}_{k+1}\le 3^{-|R_k|}ϵ\le ϵ/\left|U_k^{\perp }\right|$$因此, 如果我们取 $W=U_{k+1}$ 和 $U=U_k$, $\text{codim }{U}_{k+1}\le 3^{|R_{k+1}|}\le m$, 证明完成.

$\square$

这个正则性引理带来了一个计数引理, 证明留作练习. 定义$${\Lambda }_3(f;U)={\mathbb{E}}_{x\in {\mathbb{F}}_3^n,y\in U}f(x)f(x+y)f(x+2y)$$

引理 4.4 (计数引理).

令 $f,g:{\mathbb{F}}_3^n\to [0,1]$ , $U\le {\mathbb{F}}_3^n$. 则$$\left|{\Lambda }_3(f;U)-{\Lambda }_3(g;U)\right|\le 3\left|U^{\perp }\right|\cdot \Vert \widehat{f-g}{\Vert }_{\infty }$$

引理 4.5. 令 $f:{\mathbb{F}}_3^n\to [0,1]$, 子空间 $W\le U\le {\mathbb{F}}_3^n$. 则$${\Lambda }_3\left(f_W;U\right)\ge 2{\Vert f_U\Vert }_3^3-{\Vert f_W\Vert }_3^3$$

证明. 回顾 Schur 不等式: $$a^3+b^3+c^3+3abc\ge a^2(b+c)+b^2(a+c)+c^2(a+b)$$其中 $a,b,c\ge 0$. 我们发现$$\begin{array}{rl}\Lambda \left(f_W;U\right)& ={\mathbb{E}}_{\begin{array}{c}x,y,z\\ \text{form a 3-AP in }\\ \text{ the same }U-\mathrm{coset}\end{array}}{f}_W(x)f_W(y)f_W(z)\\ & \ge 2{\mathbb{E}}_{\genfrac{}{}{0ex}{}{x,y}{\text{ in same }U-\mathrm{coset}}}{f}_W(x{)}^2{f}_W(y)-\mathbb{E}{f}_W^3\\ & \ge 2\mathbb{E}{f}_W^2{f}_U-\mathbb{E}{f}_W^3\\ & \ge 2\mathbb{E}{f}_U^3-\mathbb{E}{f}_W^3\end{array}$$其中第一个不等号来自 Schur 不等式, 最后一个不等号来自凸性.

$\square$

定理 4.6. 对于任意 $ϵ>0$, 存在 $m=\mathrm{tow}\left(O\left(\log \frac{1}{ϵ}\right)\right)$ 满足: 如果 $f$ 是从 ${\mathbb{F}}_3^n$ 到 $[0,1]$ 的映射, 则存在维数至多为 $m$ 的 $U\le {\mathbb{F}}_3^n$ 满足$${\Lambda }_3(f;U)\ge (\mathbb{E}f{)}^3-ϵ$$

证明. 选择正则性引理中的 $U,W$, 然后有$${\Lambda }_3(f;U)\ge {\Lambda }_3\left(f_W;U\right)-3ϵ\ge 2{\Vert f_U\Vert }_3^3-{\Vert f_W\Vert }_3^3-3ϵ\ge (\mathbb{E}f{)}^3-4ϵ$$

$\square$

流行公差在 $\mathbb{Z}$ 中的类似概念在也成立.

定理 4.7. 对于任意的 $ϵ>0$, 一定存在 $N_0=N_0(ϵ)$ 满足: 如果 $N>N_0$ 且 $A\subseteq [N]$ ( $|A|=\alpha N$ ) , 则一定存在 $y>0$ 满足$$|\{x:x,x+y,x+2y\in A\}|\ge \left({\alpha }^3-ϵ\right)N$$

$\mathbb{Z}$ 中相应的陈述对于 4-AP 也是成立的:

定理 4.8. 对于任意的 $ϵ>0$, 一定存在 $N_0=N_0(ϵ)$ 满足: 如果 $N>N_0$ 且 $A\subseteq [N]$ ( $|A|=\alpha N$) , 则一定存在 $y>0$ 满足$$|\{x:x,x+y,x+2y,x+3y\in A\}|\ge \left({\alpha }^4-ϵ\right)N$$

注 4.9. 令人惊讶的是, $\mathbb{Z}$ 中关于 5-AP (或更大) 的相应的陈述是错的.