57. Roth 三项等差数列定理

Roth 的三项等差数列定理: Fourier 级数的另一个应用

我们给出 Fourier 级数的基本思想的另一个应用. 经典的 Roth 三项等差数列定理讲的是:

定理 57.1 (Roth). 任给自然数的集合 $A\subset {\mathbb{Z}}_{⩾0}$, $A$ 在自然数中的上密度定义为$$\overline{\rho }(A)=\underset{n\to \infty }{\mathrm{limsup}}\frac{|\{x\in A\mid x⩽A\}|}{n}.$$如果 $\overline{\rho }(A)>0$, 那么 $A$ 中一定包含 $3$ 项的等差数列, 即存在 $x,y,z\in A$, 使得 $y-x=z-y$.

假设 $x<z<y$ 是这样的一个等差数列, 那么, $x+y=2z$; 反之, 在整数集中, $x+y=2z$ 意味着 $\{x,z,y\}$ 构成等差数列.

我们将证明这个定理的一个量化形式 (Roth 的定理是下面命题的推论) , 即

命题 57.2. 存在常数 $C>0$ ($C=99$ 就可以) , 使得对任意给定 $\delta >0$, 只要$$N>e^{e^{C{\delta }^{-1}}},$$对任意的 $A\subset \{0,1,\cdots ,N-1\}$, 如果 $|A|⩾\delta N$, 那么 $A$ 中必然有 $3$ 项的等差数列.

在后面的证明中, 我们假设 $N$ 是奇数 (纯技术性假设) .

离散集合 $\{0,1,2,\cdots ,N-1\}$ 上的 Fourier 级数

给定自然数 $N$, 我们令 ${\mathbf{T}}_N=\{0,1,2,\cdots ,N-1\}$, 这是 $\mathbb{Z}$ 在除 $N$ 的意义下的一个完全剩余类 (余数的集合) . 我们现在考虑 $\mathbb{Z}$ 上以 $N$ 为周期的函数 $f$ (复值函数) , 即 $f(x+N)=f(x)$, 其中 $x\in \mathbb{Z}$. 这个函数可以被看作是 ${\mathbf{T}}_N$ 上的函数.

很明显, ${\mathbf{T}}_N$ 上复值函数的全体是有限维复线性空间, 我们把它记做 $L^2({\mathbf{T}}_N)$. 另外, ${\dim }_{\mathbb{C}}{L}^2({\mathbf{T}}_N)=N$. 在 $L^2({\mathbf{T}}_N)$ 我们可以定义如下自然的内积: $$(f,g)=\frac{1}{N}\sum _{x=0}^{N-1}f(x)\overline{g(x)}.$$与 Fourier 级数类似, 我们有一组标准正交基: $\left\{e^{i\frac{2\pi i}{N}kx}\right|k=0,1,\cdots ,N-1\}$ (请自己验证这一点) .

对任意的 $f\in L^2({\mathbf{T}}_N)$, 我们定义 $f$ 的 Fourier 变换: $$\hat{f}:{\mathbf{T}}_N\to \mathbb{C},\hat{f}(k)=\sum _{x=0}^{N-1}f(x)e^{-\frac{2\pi i}{N}kx}.$$

对任意的 $f,g\in L^2({\mathbf{T}}_N)$, 我们定义它们的卷积: $$f\ast g(x)=\sum _{y=0}^{N-1}f(x-y)g(y).$$

我们总结关于 Fourier 变换和内积的性质:

1)	我们有 Fourier 逆变换公式 (用 Fourier 系数来写出函数本身) : $$f(x)=\frac{1}{N}\sum _{k=0}^{N-1}\hat{f}(k)e^{\frac{2\pi i}{N}kx}.$$ 实际上, 上面的表达式可以写成$$f=\sum _{k=0}^{n-1}\left(f,e^{i\frac{2\pi i}{N}kx}\right)e^{i\frac{2\pi i}{N}kx}.$$这就是在内积空间中把向量用标准正交基来表示.
2)	勾股定理仍然成立: $$\frac{1}{N}\sum _{k=0}^{N-1}|\hat{f}(k){|}^2=\sum _{x=0}^{N-1}|f(x){|}^2.$$根据 1) 中的表达式, 我们应该有$$(f,f)=\sum _{k=0}^{N-1}|\frac{\hat{f}(k)}{N}{|}^2.$$整理即得.
3)	在差一个常数的意义下, Fourier 变换保持内积, 即$$(\hat{f},\hat{g})=N(f,g)\iff \frac{1}{N}\sum _{k=0}^{N-1}\hat{f}(k)\overline{\hat{g}(k)}=\sum _{x=0}^{N-1}f(x)\overline{g(x)}.$$ 根据 1) 和 $e^{\frac{2\pi i}{N}kx}$ 之间的相互正交性, 我们有$$\begin{array}{rl}(f,g)& =\left(\sum _{k=0}^{N-1}\frac{\hat{f}(k)}{N}{e}^{\frac{2\pi i}{N}kx},\sum _{\ell =0}^{N-1}\frac{\hat{g}(\ell )}{N}{e}^{\frac{2\pi i}{N}\ell x}\right)\\ & =\sum _{k=0}^{N-1}\sum _{\ell =0}^{N-1}\frac{\hat{f}(k)}{N}\frac{\hat{g}(\ell )}{N}\underset{\ell =k}{\underbrace{\left(e^{\frac{2\pi i}{N}kx},e^{\frac{2\pi i}{N}\ell x}\right)}}\\ & =\sum _{k=0}^{N-1}\frac{\hat{f}(k)}{N}\frac{\hat{k}(\ell )}{N}\\ & =\frac{1}{N}(\hat{f},\hat{g}).\end{array}$$
4)	在频率空间来看, 卷积就是正常的乘法: $$\widehat{f\ast g}=\hat{f}\cdot \hat{g}.$$我们利用 Fubini 公式 (交换求和顺序) : $$\begin{array}{rl}\widehat{f\ast g}(k)& =\sum _{x=0}^{N-1}\left(\sum _{y=0}^{N-1}f(x-y)g(y)e^{-\frac{2\pi i}{N}kx}\right)\\ & =\sum _{x=0}^{N-1}\sum _{y=0}^{N-1}f(x-y)e^{-\frac{2\pi i}{N}k(x-y)}g(y)e^{-\frac{2\pi i}{N}ky}\\ & =\sum _{y=0}^{N-1}\left(\sum _{x=0}^{N-1}f(x-y)e^{-\frac{2\pi i}{N}k(x-y)}\right)g(y)e^{-\frac{2\pi i}{N}ky}\\ & =\sum _{y=0}^{N-1}\hat{f}(k)g(y)e^{-\frac{2\pi i}{N}ky}\\ & =\hat{f}(k)\cdot \hat{g}(k).\end{array}$$
5)	卷积之后的 $L^2$ 范数: $$\frac{1}{N}\sum _{k=0}^{N-1}|\hat{f}(k){|}^2|\hat{g}(k){|}^2=\sum _{x=0}^{N-1}|f\ast g(x){|}^2.$$这是前面几个结论的直接推论.

Roth 定理的 Fourier 化

现在给定 $A\subset {\mathbf{T}}_N$, $|A|=\delta N$, 我们用 $\mathfrak{N}$ 表示 $A$ 中的 $3$ 项的等差数列的数目 (总假定公差不是 $0$) . 我们现在 $\mathrm{mod}N$ 的意义下考虑三项等差数列的方程$$x+y\equiv 2z\mathrm{mod}N\iff z-x\equiv y-z\mathrm{mod}N.$$我们想要在 $A^3\subset {\mathbf{T}}_N^3$ 中来找到 $(x,y,z)$, 使得上面的方程成立. 为此, 我们定义$${\mathfrak{N}}_1=|\{(x,y,z)\in A^3\mid x+y\equiv 2z\mathrm{mod}N\}|.$$我们把注意力集中在 ${\mathfrak{N}}_1$ 上, 暂且不考虑它与 $\mathfrak{N}$ 之间的关联. 根据频率函数之间的正交性, 我们有$$\begin{array}{r}{\mathfrak{N}}_1=\sum _{x\in A}\sum _{y\in A}\sum _{z\in A}\frac{1}{N}\sum _{k=0}^{N-1}{e}^{-\frac{2\pi i}{N}k(x+y-2z)}\end{array}$$这因为如果当 $x+y\not\equiv 2z\mathrm{mod}N$ 时, 对 $k$ 求和给出零. 所以, $$\begin{array}{rl}{\mathfrak{N}}_1& =\sum _{x\in {\mathbf{T}}_N}\sum _{y\in {\mathbf{T}}_N}\sum _{z\in {\mathbf{T}}_N}\frac{1}{N}\sum _{k=0}^{N-1}{e}^{-\frac{2\pi i}{N}k(x+y-2z)}{1}_A(x)1_A(y)1_A(z)\\ & =\frac{1}{N}\sum _{k=0}^{N-1}\left(\right(\sum _{x\in {\mathbf{T}}_N}{e}^{-\frac{2\pi i}{N}kx}{1}_A(x)\left)\right(\sum _{y\in {\mathbf{T}}_N}{e}^{-\frac{2\pi i}{N}ky}{1}_A(y)\left)\right(\sum _{z\in {\mathbf{T}}_N}{e}^{\frac{2\pi i}{N}2kz}{1}_A(z)\left)\right)\\ & =\frac{1}{N}\sum _{k=0}^{N-1}\widehat{1_A}(k{)}^2\widehat{1_A}(-2k),\end{array}$$其中 $1_A$ 是集合 $A\subset {\mathbf{T}}_N$ 的示性函数. 利用 $\widehat{1_A}(0)=\delta N$, 最终, 我们得到如下的等式: $$\begin{array}{r}{\mathfrak{N}}_1={\delta }^3{N}^2+\frac{1}{N}\sum _{k=1}^{N-1}\widehat{1_A}(k{)}^2\widehat{1_A}(-2k).\end{array}$$

注记. 我们有如下两个直观 (并不直观的直观) :

1)	上面计数问题的首项有可以利用随机性给出如下的解释: 假设 $A$ 在 $N$ 中是随机选取的, 也就是说我们随机地从 $0,1,\cdots ,N-1$ 中选取数, 以概率为 $\delta$ 地机会选到了 $A$. 此时, $x$ 和 $z$ 可以随便从 $A$ 中挑选, 所以一共有 ${\delta }^2{N}^2$ 种选择, 此时 $y=2z-x$ 还要落在 $A$ 中, 这个概率就只有 $\delta$, 所有一共有 ${\delta }^3{N}^2$ 中选择. 根据这种看法, 如果 $A$ 在 ${\mathbf{T}}_N$ 中是非常均匀分布的, 那么我们期盼有很多三项 $\mathrm{mod}N$-等差数列 (大约有 ${\delta }^2{N}^3$ 个) .
2)	假设 $A\subset {\mathbf{T}}_N$ 是随机分布的 (不管怎么定义) , 当 $N$ 很大的时候, 如果把 $A$ 看成是 ${\mathbf{T}}_N$ 中的数列, 我们直观上可以认为它们是等分布的, 根据 Weyl 的等分布判据, $1_A$ 这个函数的 Fourier 系数 (任意一个非零系数) 是 $o(|A|)$ 的, $|A|$ 算是这个序列的项数.
3)	假设 $1_A$ 的非零 Fourier 系数很小, 即存在 $\epsilon >0$ 很小, 使得对任意的 $k\ne 0$, 我们都有 $|\widehat{1_A}(k)|⩽\epsilon N$. 此时, 我们有$$\begin{array}{rl}|\sum _{k=1}^{N-1}\widehat{1_A}(k{)}^2\widehat{1_A}(-2k)|& ⩽(\underset{k\ne 0}{\max }|\widehat{1_A}(-2k)|)\sum _{k=1}^{N-1}|\widehat{1_A}(k){|}^2\\ & ⩽\epsilon N\sum _{k=0}^{N-1}|\widehat{1_A}(k){|}^2\\ & =\epsilon \delta N^2.\end{array}$$所以, 如果 $\epsilon$ 足够的小, 我们就得到$${\mathfrak{N}}_1⩾{\delta }^3{N}^2-\epsilon \delta N^2=\delta N^2({\delta }^2-\epsilon )>0.$$那么, ${\mathfrak{N}}_1$ 是大于 $0$ 的 (实际上有 ${\delta }^3{N}^2$ 那么多, 如果 $\epsilon \approx 0.5\times {\delta }^2$) .

根据上面的讨论, 我们引入如下概念:

定义 57.3. 给定 ${\mathbf{T}}_N$ 的子集 $A$. 如果存在 $\epsilon >0$, 使得对任意的 $k\ne 0$, 都有$$|\widehat{1_A}(k)|⩽\epsilon N,$$我们就称 $A$ 是 $\mathbf{\epsilon }$-随机的或者是 $\mathbf{\epsilon }$-等分布的.

我们现在给出 Roth 定理证明的梗概. 有两种情形需要处理:

1)	$A$ 是随机分布的. 我们先证明有很多三项的 $\mathrm{mod}N$-等差数列, 然后在证明等差数列也存在.
2)	$A$ 的分布不随机. 在这个条件下, 我们证明能在 ${\mathbf{T}}_N$ 中 (不是 $A$ 中) 找到很长的一个等差数列 $P_1$, 使得 $A_1=A\cap P_1$ 在 $P_1$ 中的密度要相对于 $A$ 在 ${\mathbf{T}}_N$ 中的密度大一些, 即存在 ${\epsilon }^{\prime }>0$ 只依赖于 $\delta$, 使得$$|A_1|⩾(\delta +{\epsilon }^{\prime })|P|,$$我们把 ${\mathbf{T}}_N$ 替换为 $P$, 把 $A$ 替换为 $A_1$. 此时, 子集密度增长了 ${\epsilon }^{\prime }$.

我们不停地进行 2) 这个操作: 如果 1) 在某一步成立, 我们就完成了 Roth 定理的证明; 否则, 经过 $m$ 次之后, 最终导致某个 $A_m$ ($m\gg 1$) 在 $P_m$ 的密度 $>1$, 矛盾.

$A$ 是相对随机分布的情形: $|\widehat{1_A}(k)|⩽\epsilon N$, 其中 $\epsilon <\frac{1}{8}{\delta }^2$

在这种情况下, 根据前面的计算, 我们有$${\mathfrak{N}}_1⩾{\delta }^3{N}^2-\epsilon \delta N^2⩾\frac{7}{8}{\delta }^3{N}^2.$$其中, ${\mathfrak{N}}_1$ 是三项的 $\mathrm{mod}N$-等差数列的个数, 我们想得到真正的三项等差数列的个数的下界估计.

我们有如下的观察:

令 $A_{\frac{1}{3}}=A\cap [\frac{N}{3},\frac{2N}{3})$, 如果 $x,z\in A_{\frac{1}{3}}$, 那么满足 $x+y\equiv 2z\mathrm{mod}N$ 的 $y\in A$, 一定满足 $x+y=2z$.

所以, 我们令$$\begin{array}{rl}& {\mathfrak{N}}_0=\left|\right\{(x,y,z)\in A^3|x+y=2z\}|,\\ & {\mathfrak{N}}_2=\left|\right\{(x,y,z)\in A_{\frac{1}{3}}\times A\times A_{\frac{1}{3}}|x+y\equiv 2z\mathrm{mod}N\}|.\end{array}$$那么$${\mathfrak{N}}_0⩾{\mathfrak{N}}_2.$$利用三角函数之间的相互正交性, 我们仿照 ${\mathfrak{N}}_1$ 的计算, 就有$$\begin{array}{rl}{\mathfrak{N}}_2& =\sum _{x\in A_{\frac{1}{3}}}\sum _{y\in A}\sum _{z\in A_{\frac{1}{3}}}\frac{1}{N}\sum _{k=0}^{N-1}{e}^{-\frac{2\pi i}{N}k(x+y-2z)}\\ & =\frac{1}{N}\sum _{k=0}^{N-1}\hat{1_{A_{\frac{1}{3}}}}(k)\widehat{1_A}(k)\hat{1_{A_{\frac{1}{3}}}}(-2k)\\ & =\delta |A_{\frac{1}{3}}{|}^2+\frac{1}{N}\sum _{k\ne 0}^{N-1}\hat{1_{A_{\frac{1}{3}}}}(k)\widehat{1_A}(k)\hat{1_{A_{\frac{1}{3}}}}(-2k)\end{array}$$我们对后一项进行下面的控制 ( $N$ 是奇数, 所以 $k\mapsto -2k$ 是 ${\mathbf{T}}_N$ 到自身的双射 ($\mathrm{mod}N$) ) : $$\begin{array}{rl}& |\sum _{k\ne 0}^{N-1}\hat{1_{A_{\frac{1}{3}}}}(k)\widehat{1_A}(k)\hat{1_{A_{\frac{1}{3}}}}(-2k)|\\ ⩽& \underset{k\ne 0}{\max }|\widehat{1_A}(k)|\times \sum _{k\ne 0}^{N-1}|\hat{1_{A_{\frac{1}{3}}}}(k)\hat{1_{A_{\frac{1}{3}}}}(-2k)|\\ ⩽& \epsilon N\left(\sum _{k\ne 0}^{N-1}\right|\hat{1_{A_{\frac{1}{3}}}}(k){|}^2{)}^{\frac{1}{2}}\left(\sum _{k\ne 0}^{N-1}\right|\hat{1_{A_{\frac{1}{3}}}}(-2k){|}^2{)}^{\frac{1}{2}}\\ =& \epsilon N\sum _{k\ne 0}^{N-1}|\hat{1_{A_{\frac{1}{3}}}}(k){|}^2\\ ⩽& \epsilon N\sum _{k=0}^{N-1}|\hat{1_{A_{\frac{1}{3}}}}(k){|}^2\\ =& \epsilon N^2|A_{\frac{1}{3}}|.\end{array}$$从而, $$\begin{array}{rl}{\mathfrak{N}}_2& ⩾\delta |A_{\frac{1}{3}}{|}^2-\epsilon N|A_{\frac{1}{3}}|⩾\delta |A_{\frac{1}{3}}{|}^2-\frac{{\delta }^2}{8}N|A_{\frac{1}{3}}|.\end{array}$$最终, 我们得到$${\mathfrak{N}}_0⩾\delta \left|A_{\frac{1}{3}}\right|(|A_{\frac{1}{3}}|-\frac{\delta }{8}N).$$我们根据 $A_{\frac{1}{3}}$ 的元素数目的多少, 作以下的考虑:

•

假设 $|A_{\frac{1}{3}}|⩾\frac{1}{4}\delta N$. 此时, 我们有$${\mathfrak{N}}_0⩾\frac{1}{32}{\delta }^3{N}^2.$$ 我们注意到 ${\mathfrak{N}}_0$ 中可能还计算了公差是零的三项等差数列 (即 $x=y=z$) , 这样的等差数列个数至多有 $|A|=\delta N$ 个, 所以, $$\mathfrak{N}⩾\frac{1}{32}{\delta }^3{N}^2-\delta N=\delta N(\frac{1}{32}{\delta }^{2}N-1).$$ 所以, 为了保证有三项等差数列, 我们总是假设 $N>33{\delta }^{-2}$, 此时, $$\mathfrak{N}⩾\frac{1}{32}\delta N>0.$$

•

假设 $|A_{\frac{1}{3}}|<\frac{1}{4}\delta N$. 根据定义, $A_{\frac{1}{3}}=A\cap [\frac{N}{3},\frac{2N}{3})$. 我们考虑两个等差数列 $P_1=[0,\frac{N}{3})$ 和 $P_2=[\frac{2N}{3},N)$ (中的整数) , 从而$$|A\cap P_1|+|A\cap P_2|⩾\frac{3}{4}\delta N.$$所以至少有一个数列, 不妨设是 $P=P_1$, 使得 $|A\cap P|⩾\frac{3}{8}\delta N$. $P$ 中的元素个数不超过 $\frac{N}{3}$ 个, 从而, $A\cap P$ 在 $P$ 中的占的比例至少是$$\frac{3}{8}\delta N÷\frac{1}{3}N=\delta +\frac{1}{8}\delta .$$

作为总结, 我们证明了

引理 57.4. 假设 $N$ 是奇数, $A\subset \{0,1,\cdots ,N-1\}$, $|A|⩾\delta N$ 并且 $N>33{\delta }^{-2}$. 如果 $A$ 中不含三项等差数列, 那么如下两种情形必居其一:

(a)	对任意的 $\epsilon ⩽\frac{{\delta }^2}{8}$, $A$ 在 $\{0,1,\cdots ,N-1\}$ 中不是 $\epsilon$-随机的;
(b)	存在一个长度至少是 $\frac{1}{3}N$ 的等差数列 $P$, 使得$$|A\cap P|⩾\delta (1+\frac{1}{8})|P|.$$即 $A$ 在 $P$ 中密度比以前增长了至少 $12.5\%$.

$A$ 不是相对随机分布的情形: 对任意的 $\epsilon <\frac{1}{8}{\delta }^2$, 存在 $k=k(\epsilon )\ne 0$, 使得 $|\widehat{1_A}(k)|>\epsilon N$

先证明一个引理:

引理 57.5. 对于任意的 $f,g\in L^2({\mathbf{T}}_N)$, 我们有$$|\hat{f}(k)||\hat{g}(k)|⩽\sum _{x\in {\mathbf{T}}_N}|\sum _{y\in {\mathbf{T}}_N}f(y)\overline{g(y-x)}|.$$

证明. 令 $F(x)=\sum _{y\in {\mathbf{T}}_N}f(y)\overline{g(y-x)}$, 我们计算它的 Fourier 系数 (和卷积的 Fourier 系数的计算一样) : $$\begin{array}{rl}\hat{F}(k)& =\sum _{x\in {\mathbf{T}}_N}\sum _{y\in {\mathbf{T}}_N}f(y)\overline{g(y-x)}{e}^{-\frac{2\pi i}{N}kx}\\ & =\sum _{x\in {\mathbf{T}}_N}\sum _{y\in {\mathbf{T}}_N}f(y)\overline{g(y-x)e^{\frac{2\pi i}{N}k(x-y)}}{e}^{-\frac{2\pi i}{N}ky}\\ & =\sum _{y\in {\mathbf{T}}_N}f(y)e^{-\frac{2\pi i}{N}ky}\\ & =\left(\sum _{x\in {\mathbf{T}}_N}\overline{g(y-x)e^{\frac{2\pi i}{N}k(x-y)}}\right)\\ & =\hat{f}(k)\overline{\hat{g}(k)}.\end{array}$$根据 $\Vert \hat{F}{\Vert }_{L^{\infty }}⩽\Vert F{\Vert }_{L^1}$ (因为 $|\hat{f}(k)|⩽\sum _{x=0}^{N-1}|F(x)|$.) , 我们就得到了结论.

$\square$

注记. 这个不等式表明 (利用抽屉原理) , 如果 $f$ 和 $g$ 在某个共同的频率上都是大的 ($⩾cN$) , 那么 $f$ 和 $g$ 的某个平移的内积就会很大 ($⩾c^2$) .

我们的目标是说明在此情形下 (即上面引理 A 中的 $(a)$ 情形) , 上一步引理中的 $(b)$ 也成立 (密度的增长可能比 $12.5\%$ 要少) , 即我们要找一个 $L$ 项等差数列 $P_0$ (公差为 $d$) , 使得 $|A\cap P_0|⩾(\delta +{\epsilon }^{\prime })|P_0|$, 其中 $L$ 要相对比较大. 当 $\epsilon$ 给定的情况下, 我们将会取 ${\epsilon }^{\prime }=\frac{1}{4}\epsilon$, 所以, 根据 $\epsilon <\frac{1}{8}{\delta }^2$, 我们知道 $\delta$ 将增长 $O({\delta }^2)$.

我们分两步来完成这个情况的分析:

第一)

对任意的非零频率 $k\ne 0$, 我们都能找到 ${\mathbf{T}}_N$ 中的准等差数列 ($\mathrm{mod}N$ 的意义下) : $$B=\{{\xi }_i{\}}_{i=1,2,\cdots ,m+m^{\prime }},$$其中$$0⩽{\xi }_1<{\xi }_2<\cdots {\xi }_m⩽N-1,0⩽{\xi }_{m+1}<{\xi }_{m+2}<\cdots <{\xi }_{m+m^{\prime }}⩽N-1,$$并且除了 $i=m$ 之外, ${\xi }_{i+1}={\xi }_i+d$; ${\xi }_{m+1}={\xi }_m+d-N$, $d(m+m^{\prime })⩽N-1$, 使得该准等差数列的项数$$m+m^{\prime }⩾\frac{1}{4}\sqrt{N}$$而且$$|\widehat{1_B}(k)|⩾\frac{1}{2}|B|.$$ 现在证明上面的论述: 对于固定的 $k$, 我们知道存在 ${\ell }_1,{\ell }_2\in {\mathbf{T}}_N$, 使得下面两个不等式同时成立: $$0<{\ell }_2-{\ell }_1⩽\sqrt{N},k({\ell }_2-{\ell }_1)\mathrm{mod}N⩽\sqrt{N}.$$(考虑平面上 $N$ 个点 $\{(s,sk\mathrm{mod}N)\mid s=0,1,\cdots ,N-1\}$, 它们都落在 $[0,N-1]\times [0,N-1]$ 中, 我们将 $[0,N-1]\times [0,N-1]$ 平均分成 ${\lfloor \sqrt{N-1}\rfloor }^2$ 份, 总共小于 $N$ 份, 那么必有两个点落在同一个小格子中, 它们就满足要求) 令 $d={\ell }_2-{\ell }_1$, 我们现在定一个 ${\mathbf{T}}_N$ 中的准等差数列 (在考虑 $\mathrm{mod}N$ 的意义下) : $$\begin{array}{rl}B& =\{\cdots ,-2d,-d,0,d,2d,\cdots \}\\ & =\{{\xi }_1=N-(m-1)d,{\xi }_2=N-(m-2)d,\cdots ,{\xi }_m=N\}\\ & \cup \{{\xi }_{m+1}=d,{\xi }_{m+2}=2d,\cdots ,{\xi }_{m+m^{\prime }}=m^{\prime }d\},\end{array}$$其中 $m=m^{\prime }=\frac{1}{8}\lfloor \frac{N}{d}\rfloor$, 从而上面两个集合不相交 (看长度) , 这表明$$|B|⩾\frac{1}{4}\lfloor \frac{N}{d}\rfloor =\frac{1}{4}\sqrt{N}.$$我们现在将 $B$ 选取的短一点, 使得 $|B|=\lfloor \frac{1}{4}\sqrt{N}\rfloor +1$. 现在计算$$\begin{array}{rl}|\widehat{1_B}(k)-|B||& ⩽|\sum _{x\in B}{1}_B(x)(e^{-\frac{2\pi i}{N}kx}-1)|⩽\sum _{x\in B}|e^{-\frac{2\pi i}{N}kx}-1|\\ & =\sum _{1⩽|j|⩽m=\frac{|B|}{2}}|e^{-\frac{2\pi i}{N}jkd}-1|\end{array}$$我们下面运用不等式 $|e^{ix}-1|⩽|x|$ (看弧长并利用两点之间线段最短, 上学期已经证明) . 由于 (请参考 $d$ 的构造) $$0⩽dk\mathrm{mod}N⩽\sqrt{N},$$所以存在整数 $s$, 使得 $0⩽dk-sN⩽\sqrt{N}$, 从而 $e^{-\frac{2\pi i}{N}jkd}=e^{-\frac{2\pi i}{N}j(kd-sN)}$, 从而$$\begin{array}{rl}|\widehat{1_B}(k)-|B||& ⩽\sum _{|j|⩽\frac{|B|}{2}}\frac{2\pi |j|(kd-sN)}{N}\\ & ⩽\frac{2\pi }{\sqrt{N}}\sum _{|j|⩽\frac{|B|}{2}}|j|\\ & ⩽\frac{2\pi }{\sqrt{N}}\frac{1}{2}(\frac{|B|}{2}{)}^2=\frac{1}{2}|B|\times \frac{\pi }{4}\frac{|B|}{\sqrt{N}}.\end{array}$$根据 $B$ 的构造, 后一个因子 $\frac{\pi }{4}\frac{|B|}{\sqrt{N}}<1$, 从而$$\begin{array}{r}|\widehat{1_B}(k)-|B||⩽\frac{1}{2}|B|.\end{array}$$这就给出了第一步的证明.

第二)

对于上一步中构造出来的 $B$, 我们能找到它的一个平移 $B+x$ (仍然落在 ${\mathbf{T}}_N$ 中, $N-1$ 被平移成了 $x-1$) , 使得$$|A\cap (B+x)|⩾(\delta +\frac{1}{4}\epsilon )|B|.$$ 我们首先将上面的这个叙述翻译成分析的语言, 要证明的不等式等价于存在 $x\in {\mathbf{T}}_N$, 使得$$\sum _{y\in {\mathbf{T}}_N}{1}_A(y)1_B(y-x)⩾(\delta +\frac{1}{4}\epsilon )|B|.$$如果令 $f_A(x)=1_A(x)-\delta$, 那么, $$|A\cap (B+x)|⩾(\delta +\frac{1}{4}\epsilon )|B|\iff \sum _{y\in {\mathbf{T}}_N}{f}_A(y)1_B(y-x)⩾\frac{1}{4}\epsilon |B|.$$另外, $f_A$ 除了零频率以外, 和 $1_A$ 是一样的. 特别地, 对某个给定的 $k=k(\epsilon )\ne 0$, 我们有$$|\widehat{f_A}(k)|>\epsilon N.$$ 我们现在令 $H(x)=\sum _{y\in {\mathbf{T}}_N}{f}_A(y)1_B(y-x)$, 根据已经证明的引理, 我们得到 (在频率 $k$ 上考虑) : $$\sum _{x\in {\mathbf{T}}_N}|H(x)|⩾|\widehat{f_A}(k)||\widehat{1_B}(k)|⩾\frac{\epsilon N}{2}|B|.$$利用 $\sum _{x\in {\mathbf{T}}_N}H(x)=0$ (因为 $f_A$ 没有频率为零的分量) , 我们得到$$\sum _{x\in {\mathbf{T}}_N}|H(x)|+H(x)⩾\frac{\epsilon N}{2}|B|.$$从而存在某个 $x$, 使得$$|H(x)|+H(x)⩾\frac{\epsilon }{2}|B|.$$所以, $$H(x)⩾\frac{\epsilon }{4}|B|.$$ 我们注意到, 经过平移之后, $B+x$ 仍然形如$$B=\{{\xi }_i{\}}_{i=1,2,\cdots ,m+m^{\prime }},$$其中, $$0⩽{\xi }_1<{\xi }_2<\cdots {\xi }_m⩽N-1,0⩽{\xi }_{m+1}<{\xi }_{m+2}<\cdots <{\xi }_{m+m^{\prime }}⩽N-1.$$

综合上面两个步骤的结论, 我们就得到了 ${\mathbf{T}}_N$ 中的准等差数列$$B=\{{\xi }_i{\}}_{i=1,2,\cdots ,m+m^{\prime }},$$其中$$0⩽{\xi }_1<{\xi }_2<\cdots {\xi }_m⩽N-1,0⩽{\xi }_{m+1}<{\xi }_{m+2}<\cdots <{\xi }_{m+m^{\prime }}⩽N-1.$$并且, 除了 $i=m$ 之外, ${\xi }_{i+1}={\xi }_i+d$; ${\xi }_{m+1}={\xi }_m+d-N$, $d(m+m^{\prime })⩽N-1$ 并且该准等差数列的项数 $m+m^{\prime }⩾\frac{1}{4}\sqrt{N}$, 使得$$|A\cap B|⩾(\delta +\frac{1}{4}\epsilon )|B|.$$

然而, 我们需要找到等差数列而不是准等差数列, 我们再修正一下. $B$ 可以分成两个真正的等差数列: $$P_1=\{{\xi }_1<{\xi }_2<\cdots {\xi }_m\},P_2=\{{\xi }_{m+1}<{\xi }_{m+2}<\cdots <{\xi }_{m+m^{\prime }}\}.$$我们再分两种情况来讨论:

•	$P_1$ 和 $P_2$ 之中有某个序列特别短, 即长度不超过 $\frac{1}{8}\epsilon |B|$. 不妨假设 $|P_1|⩽\frac{1}{8}\epsilon |B|$, 此时$$|P_2\cap A|⩾|B\cap A|-|P_1\cap A|⩾(\delta +\frac{1}{8}\epsilon )|B|⩾(\delta +\frac{1}{8}\epsilon )|P_2|.$$此时, $A$ 在 $P_2$ 中占了相当大的比重并且 $P_2$ 也足够长: $$|P_2|⩾(\frac{1}{4}-\frac{\epsilon }{8})\sqrt{N}\approx \frac{1}{4}\sqrt{N}.$$
•	$P_1$ 和 $P_2$ 都比较长, 即 $\min \{|P_1|,|P_2|\}⩾\frac{1}{8}\epsilon |B|$. 此时, 因为 $A$ 在 $P_1\cup P_2$ 中的密度是至少是 $(\delta +\frac{1}{8}\epsilon )|B|$, 所以, $A$ 至少在某一个 $P_i$ 中的密度是 $(\delta +\frac{1}{8}\epsilon )|B|$.

作为总结, 我们证明了

引理 57.6. 如果有某个非零的频率 $k\ne 0$, 使得 $|\widehat{1_A}(k)|>\epsilon N$, 那么一定存在一个长度至少是 $\frac{\epsilon }{32}\sqrt{N}$ 等差数列 $P$, 使得$$|A\cap P|⩾(\delta +\frac{1}{8})|P|.$$

综合上面两种情况的结论 (取 $\epsilon =\frac{1}{8}{\delta }^2$) , 我们证明了:

命题 57.7. 假设 $A\subset \{0,1,\cdots ,N-1\}$, $|A|⩾\delta N$ 并且 $N>33{\delta }^{-2}$. 那么, 如下两种情形必居其一:

(a)	$A$ 中含三项等差数列;
(b)	存在一个长度至少是 $\frac{{\delta }^2}{256}\sqrt{N}$ 的等差数列 $P$, 使得 $|A\cap P|⩾(\delta +\frac{{\delta }^2}{64})|P|$.

Roth 定理证明的完成

我们要对之前得到结论进行迭代. 我们不停地利用上面的性质并假设第一种情况不能发生. 第一次迭代, 我们得到一个等差数列 $P_1$, $N_1=|P_1|⩾\frac{{\delta }^2}{256}\sqrt{N}$, $|A\cap P_1|={\delta }_1|P_1|$, 其中新的密度 ${\delta }_1⩾\delta +\frac{1}{64}{\delta }^2$. 只要新得到的等差数列的长度不是零, 我们就可以迭代. 所以, 连续做 $k=\frac{62}{\delta }$ 次, 密度就从 $\delta$ 变成了 ${\delta }_k⩾2\delta$.

我们再做 $k=\frac{62}{2\delta }$ 次, 密度就从 $2\delta$ 变成了 $4\delta$; 再做 $k=\frac{62}{4\delta }$ 次, 密度就从 $4\delta$ 变成了 $8\delta$; 以此类推, 通过不超过$$\frac{64}{\delta }(1+\frac{1}{2}+\cdots +\frac{1}{2^{\ell -1}})⟶\frac{128}{\delta }$$次, 密度就变成了 $2^{\ell }\delta$.

当然, 我们不可能做 $K=\frac{128}{\delta }$ 次操作, 否则密度变成了无穷大 (超过 $1$) 就不行.

第一次操作后, 等差数列的长度 $N$ 变成了 $N_1⩾\frac{{\delta }^2}{256}\sqrt{N}$; 第二次操作, 我们得到的等差序列的长度是$$N_2⩾\frac{{\delta }_1^2}{256}\sqrt{N_1}⩾\frac{{\delta }^2}{256}\sqrt{N_1}$$我们这里用到了每一次操作, 密度 ${\delta }_k$ 是增长的. 所以, 做了 $K$ 次操作之后, 等差数列的长度至少是 $\frac{1}{256^2}{\delta }^4{N}^{\frac{1}{2^K}}$.

我们希望做到第 $K$ 次时, $\frac{1}{256^2}{\delta }^4{N}^{\frac{1}{2^K}}⩾1$, 这就给出了矛盾. 这等价于$$\log N⩾2^{\frac{128}{\delta }}(16\log 2-4\log \delta ).$$从而, $N⩾e^{e^{C{\delta }^{-1}}}$ (可以具体算出 $C$ 的大小) . 这就完成了定理的证明.

Fourier 级数的另一个应用: Poisson 核

我们首先叙述如下关于调和函数的经典问题, 这个问题在数学和物理中都有举足轻重的地位 (然而, 我们没有太多的时间深入了解) :

假定 $f$ 是 $\mathbf{T}={\mathbf{S}}^1$ 上的 (复数或者实数值) 连续函数, 能否在单位圆盘 $D=\{z\in \mathbb{C}||z|⩽1\}$ 上面找到连续函数 $u$, 使得 $u$ 在 $D$ 的内部 $\mathring{D}$ 是 $C^2$ 的并且$$\{\begin{array}{ll}△u(x)& =0,x\in \mathring{D},\\ u{|}_{\partial D}& =f,\end{array}$$其中 $△u=\frac{{\partial }^{2}u}{\partial x^2}+\frac{{\partial }^{2}u}{\partial y^2}$.

我们的基本想法来自于 Fourier 分析和线性代数. Fourier 级数的理论表明, $f$ 可以用一组基 $e^{2\pi ikx}$ 的线性组合来表示, 我们先假设 $f=e^{2\pi kx}$, 如果能对这样的情形解决问题, 也就说对任意的 $k\in \mathbb{Z}$, 能找到$$\{\begin{array}{ll}△u_k& =0,x\in \mathring{D},\\ u_k{|}_{\partial D}& =e^{2\pi ikx}.\end{array}$$那么, 由于 $f(x)=\sum _{k\in \mathbb{Z}}\hat{f}(k)e^{2\pi ikx}$ (当然, 更准确的说法需要对 $f$ 的正则性有限制或者在 $L^2$ 中谈论这个等式, 但是我们直观上可以这样来考虑问题) , 我们有理由相信$$f(x)=\sum _{k\in \mathbb{Z}}\hat{f}(k)u_k(x).$$

我们先假设 $k\in {\mathbb{Z}}_{⩾0}$, 此时, 从复变量函数的观点, 我们有$$z^k{|}_{r=1}=e^{2\pi ikx}.$$(参考第十一次作业中的 s 与 S 组习题, 特别是 s10)) 首先, 我们有$$△z^k=0.$$这个直接计算可得 (从复变函数的观点这个很自然) . 实际上, 对于上述计算在 $z\ne 0$ 处, 但是, $z^k$ 在 $0$ 处是不良好定义. 为此, 当 $k<0$ 时, 我们考虑复共轭 $\overline{z^{|k|}}$, 此时, 我们仍然有$$\overline{z^{|k|}}{|}_{r=1}=e^{2\pi ikx},k<0.$$综合上述, 我们有$$\{\begin{array}{ll}△u_k& =0,\\ u_k{|}_{\partial D}& =e^{2\pi ikx},\end{array}\Rightarrow u_k=\{\begin{array}{ll}{z}^k,& k⩾0;\\ \overline{z^{|k|}},& k<0.\end{array}.$$所以, 我们期望有$$\begin{array}{rl}u(z)& =-\hat{f}(0)+\sum _{k⩾0}\hat{f}(k)z^k+\sum _{k⩾0}\hat{f}(-k){\overline{z}}^k\\ & =-\hat{f}(0)+\sum _{k⩾0}{\int }_0^{2\pi }f(t)(e^{-it}z{)}^k+f(x)(e^{it}\bar{z}{)}^k\frac{dt}{2\pi }\\ & \stackrel{|z|<1}{=}-\hat{f}(0)+{\int }_0^{2\pi }f(t)(\frac{1}{1-e^{-it}z}+\frac{1}{1-e^{it}\bar{z}})\frac{dt}{2\pi }\\ & ={\int }_0^{2\pi }f(t)(\frac{1}{1-e^{-it}z}+\frac{1}{1-e^{it}\bar{z}}-1)\frac{dt}{2\pi }\end{array}$$如果令 $z=r{e}^{i\theta }$, 那么$$\begin{array}{rl}u(z)& ={\int }_0^{2\pi }f(t)\frac{1-r^2}{1+r^2-2r\cos (\theta -t)}\frac{dt}{2\pi }.\end{array}$$据此, 我们引入 Poisson 核: $$P_r(\theta )=\frac{1-r^2}{1+r^2-2r\cos (\theta )},r\in [0,1)$$那么, $$u(z)=P_r\ast f.$$根据构造方式, 我们知道 $P_r(\theta )>0$ 并且$$P_r(\theta )=\sum _{k\in \mathbb{Z}}{r}^{|k|}{e}^{ik\theta }.$$利用一致收敛性与 Lebesgue 控制收敛, 我们知道$${\int }_0^{2\pi }{P}_r(\theta )\frac{d\theta }{2\pi }=1.$$我们声明, 实际上 $P_r(\theta )$ 满足下面的性质: $${\int }_{\delta ⩽|\theta |⩽\pi }|P_r(\theta )|\frac{dx}{2\pi }\to 0,r\to 1.$$按照定义, 我们知道$$\begin{array}{rl}{P}_r(\theta )& =\frac{1-r^2}{1+r^2-2r\cos (\theta )}=\frac{1-r^2}{(1-r{)}^2+2r(1-\cos \theta )}\\ & ⩽\frac{1-r^2}{2r(1-\cos \theta )}⩽\frac{1-r^2}{2r(1-\cos \delta )}\to 0.\end{array}$$这说明, $P_r(\theta )$ 是一个好的积分核, 所以有一致收敛: $$\underset{r\to 1}{\lim }{P}_r\ast f=f.$$这表明, $P_r\ast f{|}_{{\mathbf{S}}^1}=f$.

下面证明当 $r<1$ 的时候, 如果将 $P_r(\theta )$ 视作是 $(x,y)$ (或者 $(r,\theta )$) 的函数, 我们有$$△P_r(\theta )=0.$$我们知道$$△=\frac{{\partial }^2}{\partial r^2}+\frac{1}{r}\frac{\partial }{\partial r}+\frac{1}{r^2}\frac{{\partial }^2}{\partial {\theta }^2}.$$然而, 要直接验证 $△P_r(\theta )=0$ 的计算并不是很简单. 我们可以采取有两种方式来验证, 一种是用 $P_r(\theta )$ 的定义: $$P_r(\theta )=\sum _{k\in \mathbb{Z}}{r}^{|k|}{e}^{ik\theta }.$$每个分量 $z^k$ 或 ${\overline{z}}^k$ 均为调和函数. 为了证明 $△$ 与求和可交换 (从而可以放到和式里面) , 我们利用 Lebesgue 控制收敛的推论即可; 第二种方法是观察到, 如果 $△f=0$, 那么将 $f$ 旋转之后仍然成立 (参考第十二次习题的 s) , 从而, 我们只要对对 $\theta =0$ 验证即可, 此时直接计算会简单很多.

最终, 为了证明在 $|z|<1$ 处有 $△P_r\ast f=0$, 再用 Lebesgue 控制收敛的推论.

综上所述, 我们找到了$$\{\begin{array}{ll}△u(x)& =0,x\in \mathring{D},\\ u{|}_{\partial D}& =f,\end{array}$$的 (唯一解) $u(r,\theta )=P_r\ast f$.