6. Bogolyubov 引理

在 Ruzsa 建模引理 (定理 5.0.2) 中, 我们证明了对于任何小倍增集合 $A$, $A$ 的大部分元素构成的子集 Freiman 同构于 $\mathbb{Z}/N\mathbb{Z}$, 且 $N$ 的大小不会比 $A$ 大太多. 为了证明 Freiman 定理, 我们需要证明我们可以用 GAP 覆盖 $A$. 这就引出了一个自然的问题, 如何用 GAP 覆盖 $\mathbb{Z}/N\mathbb{Z}$ 的大子集? 在本节中, 我们首先展示如何在 $\mathbb{Z}/N\mathbb{Z}$ 的子集中找到加性结构. 稍后, 我们将展示如何使用这种加性结构来得到覆盖. 首先考虑有限域 ${\mathbb{F}}_2^n$ 中的类似问题会更容易些. 要说明的是, 大小为 $\alpha 2^n$ 的 ${\mathbb{F}}_2^n$ 的子集不一定包含任何例如子空间的大型结构. 本节的关键想法如下: 给定一个集合 $A$, 和集 $A+A$ 使 $A$ 的结构变得平滑. 这种想法与卷积平滑函数类似, 见图 ??. 借助这种想法, 我们得出以下自然问题:

问题 6.1. 假设 $A\subset {\mathbb{F}}_2^n$ 且 $|A|=\alpha 2^n$, 其中 $\alpha$ 是一个独立于 $n$ 的常数. $A+A$ 是否一定包含一个余维数 ¹为 $O_{\alpha }(1)$ 的子空间?

(...) 卷积使函数平滑

问题 6.1 的答案是否定的, 如下例所示.

例 6.2. 令 $A_n$ 为 ${\mathbb{F}}_2^n$ 中所有点的集合, Hamming 重量 (Hamming 重量是一串符号中非零符号的个数. ) 至多 $(n-c\sqrt{n})/2$. 根据中心极限定理$$\left|A_n\right|\sim k{2}^n$$其中 $k>0$ 是一个仅取决于 $c$ 的常数. 然而, $A_n+A_n$ 由布尔立方体中的点组成, 其汉明权重最多为 $n-c\sqrt{n}$, 因此不包含任何维度 $>n-c\sqrt{n}$ 的子空间. 证明留给读者.

回到加集 $A+A$ 平滑 $A$ 的结构这一思路上来, 我们很自然地想到, 更多 $A$ 副本的和能否有更好的效果. 事实上, 如果我们在问题 6.1 中将 $A+A$ 替换为 $2A-2A$, 那么问题答案是肯定的.

定理 6.3 (Bogolyubov 引理, 1939). 如果 $A\subset {\mathbb{F}}_2^n$ 且 $|A|=\alpha 2^n$, 其中 $\alpha$ 是一个独立于 $n$ 的常数, 则 $2A-2A$ 包含一个余维数至多为 $1/{\alpha }^2$ 的子空间.

证明. 令 $f=1_A\ast 1_A\ast 1_{-A}\ast 1_{-A}$, $2A-2A$ 是 $f$ 的支撑集. 根据卷积性质, $$\hat{f}={\hat{1}}_A^2{\hat{1}}_{-A}^2={\left|{\hat{1}}_A\right|}^4$$根据傅里叶反演, 我们有$$f(x)=\sum _{r\in {\mathbb{F}}_2^n}\hat{f}(r)(-1{)}^{r\cdot x}=\sum _{r\in {\mathbb{F}}_2^n}{\left|{\hat{1}}_A(r)\right|}^4(-1{)}^{r\cdot x}$$因为 $f(x)>0$ 将意味着 $x\in 2A-2A$, 所以我们只需找到 $f$ 为正的子空间即可. 我们将通过查看傅立叶系数的大小来选择这个子空间. 令$$R=\left\{r\in {\mathbb{F}}_2^n\backslash \{0\}:\left|{\hat{1}}_A(r)\right|>{\alpha }^{3/2}\right\}$$根据 Parseval 恒等式, $|R|<1/{\alpha }^2$. 注意到$$\sum _{r\notin R\cup \{0\}}{\left|{\hat{1}}_A(r)\right|}^4\le {\alpha }^3\sum _{r\notin R\cup \{0\}}{\left|{\hat{1}}_A(r)\right|}^2<{\alpha }^4$$如果 $x$ 在 $R^{\perp }$ 中, 那么$$\begin{array}{rl}f(x)& =\sum _{r\in {\mathbb{F}}_2^n}{\left|{\hat{1}}_A(r)\right|}^4(-1{)}^{r\cdot x}\\ & \ge {\left|{\hat{1}}_A(0)\right|}^4+\sum _{r\in R}{\left|{\hat{1}}_A(r)\right|}^4(-1{)}^{r\cdot x}-\sum _{r\notin R\cup \{0\}}{\left|{\hat{1}}_A(r)\right|}^4\\ & >{\alpha }^4+\sum _{r\in R}{\left|{\hat{1}}_A(r)\right|}^4-{\alpha }^4\\ & \ge 0\end{array}$$因此 $R^{\perp }\subset \mathrm{supp}(f)=2A-2A$ , 并且由于 $|R|<1/{\alpha }^2$, 我们找到了一个余维数最多为 $1/{\alpha }^2$ 的 $2A-2A$ 的子空间.

$\square$

我们现在的目标是在循环群 $\mathbb{Z}/N\mathbb{Z}$ 上给出一个类似的结果. 第一步是给循环群 $\mathbb{Z}/N\mathbb{Z}$ 找一个类似子空间的东西. 请注意, 我们在将 Roth 定理的证明从有限域转移到整数时遇到了类似的问题. 正确的类比是由 Bohr 集给出的. 回想一下 Bohr 集的定义:

定义 6.4. 假设 $R\subset \mathbb{Z}/N\mathbb{Z}$, 定义$$\mathrm{Bohr}(R,ϵ)=\left\{x\in \mathbb{Z}/N\mathbb{Z}:\Vert \frac{rx}{N}\Vert \le ϵ,\text{ for all }r\in R\right\}$$其中 $\Vert \cdot \Vert$ 表示到最近整数的距离. 我们称 $|R|$ 为 Bohr 集的维数, $ϵ$ 为宽度.

事实证明, 用适当维数的 Bohr 集替换子空间后, Bogolyubov 引理在 $\mathbb{Z}/N\mathbb{Z}$ 上成立. $\mathbb{Z}/N\mathbb{Z}$ 的 Bohr 集的维数对应于 ${\mathbb{F}}_2^n$ 的子空间的余维数.

定理 6.5 ($\mathbb{Z}/N\mathbb{Z})$ 上的 Bogolyubov 引理, 1939). 如果 $A\subset \mathbb{Z}/N\mathbb{Z}$ 且 $|A|=\alpha N$, 则 $2A-2A$ 包含玻尔集 $\mathrm{Bohr}(R,1/4)$ , 其中 $|R|<1/{\alpha }^2$.

回想一下 $\mathbb{Z}/N\mathbb{Z}$ 上的傅里叶变换的定义.

定义 6.6. $f:\mathbb{Z}/N\mathbb{Z}\to \mathbb{C}$ 的傅里叶变换是函数 $\hat{f}:\mathbb{Z}/N\mathbb{Z}\to \mathbb{C}$ , $$\hat{f}(r)={\mathbb{E}}_{x\in \mathbb{Z}/N\mathbb{Z}}f(x){\omega }^{-rx}$$其中 $\omega =e^{(2\pi i)/N}$

我们将其作为练习留给读者验证傅立叶反演公式、Parseval 恒等式、Plancherel 恒等式和傅里叶变换的其他基本性质. 现在我们来证明定理 6.5. 除了一些小细节外, 它与定理 6.3 的证明思路相同.

定理 6.5. 令 $f=1_A\ast 1_A\ast 1_{-A}\ast 1_{-A}$, $\mathrm{supp}(f)=2A-2A$ . 根据卷积性质, $$\hat{f}={\hat{1}}_A^2{\hat{1}}_{-A}^2={\left|{\hat{1}}_A\right|}^4$$根据傅立叶反演, $$f(x)=\sum _{r\in \mathbb{Z}/N\mathbb{Z}}\hat{f}(r){\omega }^{rx}=\sum _{r\in \mathbb{Z}/N\mathbb{Z}}{\left|{\hat{1}}_A(r)\right|}^4\cos \left(\frac{2\pi rx}{N}\right)$$因为 $f(x)>0$ 将意味着 $x\in 2A-2A$, 所以我们只需找到 $f$ 为正的子空间即可. 令$$R=\left\{r\in \mathbb{Z}/N\mathbb{Z}\backslash \{0\}:\left|{\hat{1}}_A(r)\right|>{\alpha }^{3/2}\right\}$$根据 Parseval 恒等式, $|R|<1/{\alpha }^2$. 注意到$$\sum _{r\notin R\cup \{0\}}{\left|{\hat{1}}_A(r)\right|}^4\le {\alpha }^3\sum _{r\notin R\cup \{0\}}{\left|{\hat{1}}_A(r)\right|}^2<{\alpha }^4$$因为条件 $x\in \mathrm{Bohr}(R,1/4)$ 正好等价于$$\cos \left(\frac{2\pi rx}{N}\right)>0\text{ for all }r\in R$$对于任意 $x\in \mathrm{Bohr}(R,1/4)$, 我们有$$\begin{array}{rl}f(x)& =\sum _{r\in \mathbb{Z}/N\mathbb{Z}}{\left|{\hat{1}}_A(r)\right|}^4\cos \left(\frac{2\pi rx}{N}\right)\\ & \ge {\left|{\hat{1}}_A(0)\right|}^4+\sum _{r\notin R\cup \{0\}}{\left|{\hat{1}}_A(r)\right|}^4\cos \left(\frac{2\pi rx}{N}\right)\\ & >0\end{array}$$因此 $\mathrm{Bohr}(R,1/4)\subset \mathrm{supp}(f)=2A-2A$ 且满足 $|R|<1/{\alpha }^2$.

$\square$

我们现在已经证明, 对于包含大部分 $\mathbb{Z}/N\mathbb{Z}$ 的集合 $A$, 集合 $2A-2A$ 必须包含一个维数小于 $1/{\alpha }^2$ 的 Bohr 集. 在下一节中, 我们将分析 Bohr 集中的加性结构. 特别是我们将证明低维的 Bohr 集包含大的 GAP.