2. Roth 对整数 Roth 定理的证明

在第 6.1 节中, 我们看到了 Roth 定理在有限域中 (特别是对于集合 ${\mathbb{F}}_3^n$) 的证明. 现在我们对它进行扩展来证明下面给出的上界, 即整数的 Roth 定理:

定理 2.1. $$r_3([N])=O\left(\frac{N}{\log \log N}\right)$$

这个上界的原始证明由 Roth 本人给出. 回想一下, 有限域中 Roth 定理的证明有以下 3 个步骤:

1.	证明一个 3-AP-free 的集合允许一个大的 Fourier 系数.
2.	推导出一定存在一个密度增大的子空间.
3.	迭代密度增量, 得到 3-AP-free 集大小的上界.

关于整数 Roth 定理的证明将同样遵循以上 3 个步骤. 但是, 具体的执行将大不相同. 其中, 主要的区别在于第 2 步, $[N]$ 子空间的概念在这里并不好找到.

之前我们在群 ${\mathbb{F}}_3^n$ 上定义了 Fourier 分析. 事实上, 在任何 Abel 群上均有 Fourier 分析理论, 它将群 $G$ 与其对偶群 $\hat{G}$ 联系起来. 现在我们来考虑群 $\mathbb{Z}$.

$\mathbb{Z}$ 的对偶群为 $\hat{\mathbb{Z}}=\mathbb{R}/\mathbb{Z}$. $f:\mathbb{Z}\to \mathbb{C}$ 的 Fourier 变换是如下函数 $\hat{f}:\mathbb{R}/\mathbb{Z}\to \mathbb{C}$, 它满足$$\hat{f}(\theta )=\sum _{x\in \mathbb{Z}}f(x)e(-x\theta )$$其中 $e(t)=e^{2\pi it}$. 这通常被称为 $f$ 的 Fourier 级数.

和在 ${\mathbb{F}}_3^n$ 中一样, 以下恒等式在 $\mathbb{Z}$ 中也成立, 其证明也相同:

•	$\hat{f}(0)={\sum }_{x\in \mathbb{Z}}f(x)$;
•	(Parseval) ${\sum }_{x\in \mathbb{Z}}f(x)\overline{g(x)}={\int }_0^1\hat{f}(\theta )\overline{\hat{g}(\theta )}d\theta$;
•	(反演) $f(x)={\int }_0^1\hat{f}(\theta )e(x\theta )d\theta$;
•	定义 $\Lambda (f,g,h)={\sum }_{x,y\in \mathbb{Z}}f(x)g(x+y)h(x+2y)$, 则$$\Lambda (f,g,h)={\int }_0^1\hat{f}(\theta )\hat{g}(-2\theta )\hat{h}(\theta )d\theta .$$

在有限域的版本中, 我们有一条计数引理, 用来表明如果两个函数具有相似的 Fourier 变换, 则它们具有相似数量的 3-AP. 同样的, 在 $\mathbb{Z}$ 中我们有类似的计数引理.

定理 2.2 (计数引理). 令 $f,g:\mathbb{Z}\to \mathbb{C}$ 满足 ${\sum }_{n\in \mathbb{Z}}|f(n){|}^2\le M,{\sum }_{n\in \mathbb{Z}}|g(n){|}^2\le M$. 定义 ${\Lambda }_3(f)=\Lambda (f,f,f)$, 则有$$\left|{\Lambda }_3(f)-{\Lambda }_3(g)\right|\le 3M\Vert \widehat{f-g}{\Vert }_{\infty }$$

证明. 注意到$${\Lambda }_3(f)-{\Lambda }_3(g)=\Lambda (f-g,f,f)+\Lambda (g,f-g,f)+\Lambda (g,g,f-g)$$我们考虑上式第一项的上界$$\begin{array}{rl}|\Lambda (f-g,f,f)|& =\left|{\int }_0^1(\widehat{f-g})(\theta )\hat{f}(-2\theta )\hat{f}(\theta )d\theta \right|\\ & \le \Vert \widehat{f-g}{\Vert }_{\infty }\left|{\int }_0^1\hat{f}(-2\theta )\hat{f}(\theta )d\theta \right|\\ & \le \Vert \widehat{f-g}{\Vert }_{\infty }{\left({\int }_0^1|\hat{f}(-2\theta ){|}^{2}d\theta \right)}^{1/2}{\left({\int }_0^1|\hat{f}(\theta ){|}^{2}d\theta \right)}^{1/2}\text{ (Cauchy-Schwarz) }\\ & \le \Vert \widehat{f-g}{\Vert }_{\infty }\left(\sum _{x\in \mathbb{Z}}|f(x){|}^2\right)\text{ (Parseval) }\\ & \le M\Vert \widehat{f-g}{\Vert }_{\infty }\end{array}$$第二项、第三项的处理是完全相同的.

$\square$

我们现在来证明 Roth 定理 (定理 2.1 ) . 我们的证明步骤与有限域版本的相同.

第 1 步: 如果集合是 3-AP-free 的, 则有一项大的 Fourier 系数.

引理 2.3. 令 $A\subset [N]$ 是一个 3-AP-free 集, $|A|=\alpha N,N\ge 5/{\alpha }^2$. 那么存在 $\theta \in \mathbb{R}$ 使得$$\left|\sum _{n=1}^N\left(1_A-\alpha \right)(n)e(\theta n)\right|\ge \frac{{\alpha }^2}{10}N$$

证明. 由于 $A$ 无 3-AP, 因此 $1_A(x)1_A(x+y)1_A(x+2y)$ 当且仅当 $y=0$ 时非零. 因此 ${\Lambda }_3\left(1_A\right)=|A|=\alpha N$. 现在考虑 ${\Lambda }_3\left(1_{[N]}\right)$, 该式计算了 $[N]$ 中 3-AP 的数量. 我们可以通过从 $[N]$ 中选出两个相同奇偶的元素来构成 3-AP 中的第一项和第三项. 因此 ${\Lambda }_3\left(1_{[N]}\right)=[N/2{]}^2+[N/2{]}^2\ge N^2/2$. 现在, 应用计数引理, 取 $f=1_A,g=\alpha 1_{[N]}$ (我们使用记号 $f^{\wedge }=\hat{f}$ ) ,$$\frac{{\alpha }^3{N}^2}{2}-\alpha N\le 3\alpha N{\Vert {\left(1_A-\alpha 1_{[N]}\right)}^{\wedge }\Vert }_{\infty },$$因此$$\begin{array}{rl}{\Vert {\left(1_A-\alpha 1_{[N]}\right)}^{\wedge }\Vert }_{\infty }& \ge \frac{\frac{1}{2}{\alpha }^3{N}^2-\alpha N}{3\alpha N}\\ & =\frac{1}{6}{\alpha }^{2}N-\frac{1}{3}\\ & \ge \frac{1}{10}{\alpha }^{2}N.\end{array}$$最后一个不等号成立时是因为 $N\ge 5/{\alpha }^2$. 因此存在 $\theta$ 使得$$\left|\sum _{n=1}^N\left(1_A-\alpha \right)(n)e(\theta n)\right|={\left(1_A-\alpha 1_{[N]}\right)}^{\wedge }(\theta )\ge \frac{1}{10}{\alpha }^{2}N.$$

$\square$

注 2.4. 整个证明的核心是关于结构与伪随机性, 我们在讨论图的正则性中也看到了这种想法. 如果 $A$ 是 “伪随机的”, 那么我们希望证明 $A$ 具有小的 Fourier 系数. 但这将表明 $f$ 和 $g$ 具有相似的 Fourier 系数, 这意味着 $A$ 具有许多个 3-AP 从而矛盾. 因此 $A$ 不能是伪随机的, 它必须具有某种结构.

第 2 步, 大的 Fourier 系数会产生密度增量.

在有限域版本中, 我们的 Fourier 系数对应于超平面, 然后我们能够证明在某个超平面陪集上密度很大. 然而, 现在 $\theta$ 是一个实数. $[N]$ 中没有超平面的概念, 那么我们如何将 $[N]$ 细分从而使用密度增量?

我们将 $[N]$ 划分为子级数 (sub-progression) , 同时保证 $x\mapsto e(x\theta )$ 在每个子级数上大致恒定.

举一个简单的例子, 假设 $\theta$ 是一个有理数 $a/b$, 其中 $b$ 相当小. 那么 $x\mapsto e(x\theta )$ 在具有公差 $b$ 的算术级数上可近似为常数.

在正式写出这个想法之前, 我们需要介绍 Dirichlet 的经典引理.

引理 2.5. 令 $\theta \in \mathbb{R}$ , $0<\delta <1$, 则存在正整数 $d\le 1/\delta$ 满足 $\Vert d\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le \delta$, 其中 $\Vert \cdot {\Vert }_{\mathbb{R}/\mathbb{Z}}$ 是到最近整数的距离.

证明. 令 $m=\lfloor \frac{1}{\delta }\rfloor$. 考虑 $m+1$ 个数 $0,\theta ,\cdots ,m\theta$, 根据鸽巢原理, 存在 $i,j$ 使得 $i\theta$ 和 $j\theta$ 的小数部分最多相差 $\delta$. 令 $d=|i-j|$ , 则有 $\Vert d\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le \delta$.

$\square$

下一个引理描述了我们之前将 $[N]$ 划分为子级数的想法, 映射 $x\mapsto e(x\theta )$ 在每个子级数上大致恒定.

引理 2.6. 令 $0<\eta <1$ , $\theta \in \mathbb{R}$. 假设 $N>\mathrm{C}{\eta }^{-6}$ ( $\mathrm{C}$ 为某常数) . 可以将 $[N]$ 划分为多个 sub-AP $P_i$, 每个 sub-AP 的长度满足 $N^{1/3}\le \left|P_i\right|\le 2N^{1/3}$, 且 $P_i$ 满足对于任意的 $i$ 有 ${\sup }_{x,y\in P_i}|e(x\theta )-e(y\theta )|<\eta$.

证明. 根据引理 2.5, 存在一个整数 $d\le \frac{4\pi N^{1/3}}{\eta }$ 使得 $\Vert d\theta {\Vert }_{\mathbb{R}/\mathbb{N}}\le \frac{\eta }{4\pi N^{1/3}}$. 由于 $N>C{\eta }^{-6}$, 取 $C=(4\pi {)}^6$ 我们得到 $d<\sqrt{N}$. 因此, 我们可以将 $[N]$ 划分为多个具有公差 $d$ 的 sub-AP, 并且保证每个 sub-AP 的长度在 $N^{1/3}$ 和 $2N^{1/3}$ 之间. 然后, 在每个 sub-AP $P$ 中, 我们有$$\underset{x,y\in P}{\sup }|e(x\theta )-e(y\theta )|\le \left|P\right|\left|e(d\theta )-1\right|\le 2N^{1/3}\cdot 2\pi {\Vert d\theta \Vert }_{\mathbb{R}/\mathbb{Z}}\le \eta$$不等式 $|e(d\theta )-1|\le 2\pi \Vert d\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}$ 成立是因为弦长小于等于对应的弧长.

$\square$

我们现在可以应用这个引理来得到密度增量.

引理 2.7. 令 $A\subset [N]$ 是 3-AP-free 的, 且 $|A|=\alpha N$ , $N>C{\alpha }^{-12}$. 一定存在一个 sub-AP $P\subset [N]$ , 其中 $|P|\ge N^{1/3}$ 且 $|A\cap P|\ge$ $\left(\alpha +{\alpha }^2/40\right)|P|$.

证明. 根据引理 2.3, 一定存在 $\theta$ 满足 $\left|{\sum }_{x=1}^N\left(1_A-\alpha \right)(x)e(x\theta )\right|\ge$ ${\alpha }^{2}N/10$. 然后, 使用引理 2.6 , 取 $\eta ={\alpha }^2/20$ 我们得到 $[N]$ 的一个划分 $P_1,\dots ,P_k$ , 该划分满足 $N^{1/3}\le \left|P_i\right|\le 2N^{1/3}$. 所以我们有$$\frac{{\alpha }^2}{10}N\le \left|\sum _{x=1}^N\left(1_A-\alpha \right)(x)e(x\theta )\right|\le \sum _{i=1}^k\left|\sum _{x\in P_i}\left(1_A-\alpha \right)(x)e(x\theta )\right|$$对于 $x,y\in P_i$, $|e(x\theta )-e(y\theta )|\le {\alpha }^2/20$. 因此$$\left|\sum _{x\in P_i}\left(1_A-\alpha \right)(x)e(x\theta )\right|\le \left|\sum _{x\in P_i}\left(1_A-\alpha \right)(x)e(x_0\theta )\right|+\frac{{\alpha }^2}{20}\left|P_i\right|\le \left|\sum _{x\in P_i}\left(1_A-\alpha \right)(x)\right|+\frac{{\alpha }^2}{20}\left|P_i\right|$$其中, $x_0$ 是 $P_i$ 中任意一元素. 注意到$$\begin{array}{rl}\frac{{\alpha }^2}{10}N& \le \sum _{i=1}^k\left(\left|\sum _{x\in P_i}\left(1_A-\alpha \right)(x)\right|+\frac{{\alpha }^2}{20}\left|P_i\right|\right)\\ & =\sum _{i=1}^k\left|\sum _{x\in P_i}\left(1_A-\alpha \right)(x)\right|+\frac{{\alpha }^2}{20}N\end{array}$$所以$$\frac{{\alpha }^2}{20}N\le \sum _{i=1}^k\left|\sum _{x\in P_i}\left(1_A-\alpha \right)(x)\right|$$因此$$\frac{{\alpha }^2}{20}\sum _{i=1}^k\left|P_i\right|\le \sum _{i=1}^k\left||A\cap P_i|-\alpha |P_i|\right|$$我们想证明存在 $P_i$ 使得 $A$ 在限制在 $P_i$ 时具有密度增量. 我们使用以下技巧$$\begin{array}{rl}\frac{{\alpha }^2}{20}\sum _{i=1}^k\left|P_i\right|& \le \sum _{i=1}^k\left||A\cap P_i|-\alpha |P_i|\right|\\ & =\sum _{i=1}^k\left(\left||A\cap P_i|-\alpha |P_i|\right|+\left|A\cap P_i\right|-\alpha \left|P_i\right|\right)\end{array}$$所以存在 $i$ 满足$$\frac{{\alpha }^2}{20}\left|P_i\right|\le ||A\cap P_i|-\alpha |P_i||+\left|A\cap P_i\right|-\alpha \left|P_i\right|$$当 $|x|+x$ 总是严格大于 0 时 $x$ 一定大于等于零, 所以一定有 $\left|A\cap P_i\right|-\alpha \left|P_i\right|\ge 0$, 因此我们有$$\frac{{\alpha }^2}{20}\left|P_i\right|\le 2\left(\left|A\cap P_i\right|-\alpha \left|P_i\right|\right)$$整理后得到$$\left|A\cap P_i\right|\ge \left(\alpha +\frac{{\alpha }^2}{40}\right)\left|P_i\right|$$因此, 我们找到了具有密度增量的 sub-AP, 这是我们想要的.

$\square$

第 3 步, 迭代密度增量.

第 3 步与有限域版本的非常相似. 设初始密度为 ${\alpha }_0=\alpha$, 每次迭代后的密度为 ${\alpha }_i$. 我们有 ${\alpha }_{i+1}\ge {\alpha }_i+{\alpha }_i^2/40$, 并且 ${\alpha }_i\le 1$.

考虑从 ${\alpha }_0$ 开始到第一次翻倍的迭代次数 $i_1$, ${\alpha }_{i_1}>2{\alpha }_0$. 显然 $i_1\le \frac{40}{\alpha }$. 接着我们考虑从 ${\alpha }_{i_1}$ 到下一次翻倍的迭代次数 $i_2$, ${\alpha }_{i_2}>2^2{\alpha }_0$, 整理得到 $i_2\le \frac{20}{\alpha }$. 依次类推, 第 $k$ 次翻倍需要的迭代次数 $i_k\le \frac{40}{\alpha 2^{k-1}}$. 对于任意的 $k$, 有$$\frac{40}{\alpha }+\frac{20}{\alpha }+\cdots +\frac{40}{2^{k-1}\alpha }\le \frac{80}{\alpha }$$所以在 $\frac{80}{\alpha }$ 次迭代后一定终止. 所以总迭代次数必须是 $O(1/\alpha )$.

引理 2.7 表明我们可以向下传递给 sub-AP , 并且 $N_i>C{\alpha }^{-12}$ 时密度增加. 假设迭代过程在第 $i$ 步终止, 我们必须有 $N_i\le C{\alpha }_i^{-12}\le C{\alpha }^{-12}$. 每次迭代我们的集合的大小都会减少为立方根, 所以$$N\le N_i^{3^i}\le {\left(C{\alpha }^{-12}\right)}^{3^{O(1/\alpha )}}=e^{e^{O(1/\alpha )}}$$两边取对数得到 $\alpha =O(1/\log \log N)$ , $|A|=\alpha N=O(N/\log \log N)$, 这是我们想要的.

我们来比较 ${\mathbb{F}}_3^n$ 和 $[N]$ 的证明策略. 我们看到 $r_3\left({\mathbb{F}}_3^n\right)=O(N/\log N)$. 然而, $[N]$ 上的上界为 $O(N/\log \log N)$, 它相比于有限域的结果弱了一个对数因子. 这从何而来? 在 ${\mathbb{F}}_3^n$ 的密度增量步骤中, 我们能够向下传递到一个子集, 该子集的大小是原始子集的常数因子. 然而, 在 $[N]$ 中, 每次迭代都会给我们一个子级数, 它的大小等于前一个子空间的立方根. 一个自然的问题是——是否有可能向下传递到一个看起来更像子空间的子级数? 事实证明, 这是可以做到的.

对于子集 $S\subset {\mathbb{F}}_3^n$, 我们可以将其正交补写作$$U_S=\left\{x\in {\mathbb{F}}_3^n:\text{ 对所有的 }s\in S,x\cdot s=0\right\}$$在 $[N]$ 中, 类似的概念被称为 Bohr 集. 这是 Bourgain 在 1999 年提出的一个想法, 用于将有限域版本的证明转移到 $\mathbb{Z}$ 上. 这需要我们在 $\mathbb{Z}/N\mathbb{Z}$ 上工作. 对于子集 $S\subset \mathbb{Z}/N\mathbb{Z}$, 我们可以将其 Bohr 集定义为$$\mathrm{Bohr}(S,ϵ)=\left\{x\in \mathbb{Z}/N\mathbb{Z}:\text{ 对所有的 }s\in S,\Vert \frac{sx}{N}\Vert \le ϵ\right\}$$这为子空间提供了更自然的类比, 并且是现代改进 Roth 定理上界的基础. 在第 7 章研究 Freiman 定理时我们还会遇到 Bohr 集.