2.6　对称集与不平衡部分和集Symmetry sets and imbalanced partial sum sets

本页为译文 + 讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 引理 / 定理 / 例 / 分步推演）与配图为帮助理解而加的详解，逐步推演、举例、画图，不用比喻。

2.6.0　问题从哪里来

Balog–Szemerédi–Gowers 定理在研究加性能量 \(\E(A,B)\) 接近 \(|A|^{3/2}|B|^{3/2}\) 的两个加性集合 \(A,B\) 时是一件非常强大的工具；然而由 (2.7) 我们看到，这种情形只在 \(|A|\) 与 \(|B|\) 大小相当时才会出现。于是留下一个问题：当 \(|A|\gg|B|\)（比方说）、而 \(\E(A,B)\) 接近由 (2.7) 给出的上界 \(|A||B|^2\) 时，会发生什么？由 (2.8)，这个问题有一个特殊子情形，即 \(|A+B|\) 或 \(|A-B|\) 与 \(|A|\) 相当的情形。

注意，命题 2.2 已经回答了极端情形：当 \(|A+B|=|A|\) 或 \(|A-B|=|A|\)（等价地 \(\E(A,B)=|A||B|^2\)；见习题 2.3.22）时的情况。然而 Ruzsa 的一个例子 [297] 表明，当 \(|A|\) 与 \(|B|\) 相差极其悬殊时，情况会变糟（见习题）。

不过，如果我们准备好承受关于比值 \(|A|/|B|\) 的对数型损失（更确切地说，是形如 \((|A|/|B|)^\varepsilon\) 的损失，其中 \(\varepsilon\) 可取得很小），那么就能恢复一套合理的理论。仿照命题 2.2，我们期望：若 \(|A+B|\) 与 \(|A|\) 相当，或 \(\E(A,B)\) 接近 \(|A||B|^2\)，则应当存在一个近似群 \(H\)，使得 \(A\) 近似是 \(H\) 的若干平移之并，而 \(B\) 近似包含在 \(H\) 的单个平移之中。实现这一点正是本节的主要目标。

在极端情形 \(|A+B|=|A|\) 或 \(\E(A,B)=|A||B|^2\) 中，近似群 \(H\) 事实上是一个精确的群，并且在命题 2.2 的证明里它被构造为较大集合 \(A\) 的对称群 \(\Sym_1(A)\)。在一般情形下，这个对称群很可能是平凡的（只剩零元）。然而，一个更一般的概念仍然有用。

2.6.1　对称集

注意 \(\Sym_1(A)=\{h\in Z:\ A+h=A\}\) 正是命题 2.2 证明中所用的那个对称群。其他对称集一般不是群，但它们仍然是对称的（即 \(-\Sym_\alpha(A)=\Sym_\alpha(A)\)），并且含有原点；它们还满足嵌套性质：当 \(\alpha\ge\beta\) 时 \(\Sym_\alpha(A)\subseteq\Sym_\beta(A)\)。同样清楚的是，对一切 \(0<\alpha\le1\) 有 \(\Sym_\alpha(A)\subseteq A-A\)。又因为当 \(\alpha>1\) 时 \(\Sym_\alpha(A)\) 为空、当 \(\alpha\le0\) 时它等于整个 \(Z\)，所以我们将主要把注意力限制在非平凡区域 \(0<\alpha\le1\)。

对称集的大小与加性能量挂钩

我们现在把这些对称集的大小与加性能量联系起来。由引理 2.9 我们有 \[\E(A,A)=\sum_{h\in A-A}|A\cap(A+h)|^2,\] 于是对任意 \(0<\alpha\le1\)，利用粗略界：当 \(h\in\Sym_\alpha(A)\) 时 \(|A\cap(A+h)|\le|A|\)、当 \(h\notin\Sym_\alpha(A)\) 时 \(|A\cap(A+h)|\le\alpha|A|\)，我们得到 \[\alpha^2|A|^2\,|\Sym_\alpha(A)|\ \le\ \E(A,A)\ \le\ \alpha^2|A|^2\,|A-A|+|A|^2\,|\Sym_\alpha(A)|,\] 这表明只要能量大，\(\Sym_\alpha(A)\) 就应当大。特别地，由 (2.7) 我们有 \[|\Sym_\alpha(A)|\le|A|/\alpha^2.\tag{2.21}\]

1. 下界：只保留 \(h\in\Sym_\alpha(A)\) 的那些项，每项 \(|A\cap(A+h)|^2\ge(\alpha|A|)^2=\alpha^2|A|^2\)，共 \(|\Sym_\alpha(A)|\) 项，故 \(\E(A,A)\ge\alpha^2|A|^2|\Sym_\alpha(A)|\)。
2. 上界：把求和拆成“\(h\in\Sym_\alpha\)”与“\(h\notin\Sym_\alpha\)”两部分。前者每项 \(\le|A|^2\)，至多 \(|\Sym_\alpha(A)|\) 项；后者每项 \(\le\alpha^2|A|^2\)，至多 \(|A-A|\) 项。相加即得。
3. 得 (2.21)：用 \(\E(A,A)\le|A|^3\)（即 (2.7) 取 \(A=B\)）配合下界 \(\alpha^2|A|^2|\Sym_\alpha(A)|\le|A|^3\)，两边除以 \(\alpha^2|A|^2\)。

现在设 \(A,B\) 是加性群 \(Z\) 中的加性集合。再次由引理 2.9 我们有 \[\E(A,B)=\sum_{b,b'\in B}|A\cap(A+b-b')|,\] 于是对任意 \(0<\alpha\le1\) 有 \[\E(A,B)\le|B|^2\,\alpha|A|+|A|\cdot\bigl|\{(b,b')\in B:\ b-b'\in\Sym_\alpha(A)\}\bigr|.\] 特别地，如果 \(\E(A,B)\ge2\alpha|A||B|^2\)，那么我们便可断定存在一个基数 \(|G|\ge\alpha|B|^2\) 的集合 \(G\subset B\times B\)，使得 \[B\overset{G}{-}B\subseteq\Sym_\alpha(A).\tag{2.22}\]

乍一看，现在似乎可以应用对称版的 Balog–Szemerédi–Gowers 定理了。然而，\(A\) 远大于 \(B\) 这一事实意味着 \(B\overset{G}{-}B\) 可能远大于 \(B\)（把 (2.22) 与 (2.21) 比较：(2.21) 允许对称集大到 \(|A|/\alpha^2\)，远超 \(|B|\)）。为绕开这一困难，我们需要迭代这个构造，并利用 \(\Sym_\alpha(A)\) “像一个群一样”这一性质。这在 \(\alpha=1\) 时已经很清楚——此时 \(\Sym_1(A)\) 确实是一个真正的群；下面的引理表明，对小于 \(1\) 的 \(\alpha\)，这一行为在近似意义下依然保持。

2.6.2　对称集“近似成群”

证明. 为验证第一个论断，注意若 \(x\in\Sym_{1-\varepsilon}(A)\) 且 \(y\in\Sym_{1-\varepsilon'}(A)\)，则 \[|(A+x)\setminus A|=|A|-|A\cap(A+x)|\le\varepsilon|A|\] 且 \[|(A+x)\setminus(A+x+y)|=|A|-|A\cap(A+y)|\le\varepsilon'|A|,\] 于是 \[|A\cap(A+x+y)|\ge|(A+x)\cap A\cap(A+x+y)|\ge(1-\varepsilon-\varepsilon')|A|,\] 这就证明了 (2.23)。

现在证明第二个论断。由 \(S\) 的定义，对每个 \(x\in S\)，至少存在 \(\alpha|A|\) 个元素 \(a\in A\) 使得 \(a+x\in A\)。对所有 \(x\) 求和便得 \[\sum_{a\in A}|\{x\in S:\ a+x\in A\}|\ge\alpha|A||S|.\] 应用 Cauchy–Schwarz，我们推出 \[\sum_{(x,y)\in S\times S}|\{a\in A:\ a+x,\,a+y\in A\}|=\sum_{a\in A}|\{x\in S:\ a+x\in A\}|^2\ge\alpha^2|A||S|^2.\] 若我们令 \(G\subseteq S\times S\) 为所有满足 \[|\{a\in A:\ a+x,\,a+y\in A\}|\ge\alpha^2|A|/2\] 的对 \((x,y)\)，则有 \[|A||G|\ge\sum_{(x,y)\in G}|\{a\in A:a+x,a+y\in A\}|\ge\alpha^2|A||S|^2-\frac{\alpha^2|A|}{2}|S|^2,\] 这给出 (2.24)。又若 \((x,y)\in G\)，则由 \(G\) 的定义 \(|A\cap(A+x-y)|\ge\alpha^2|A|/2\)，这给出 (2.25)。♦

2.6.3　一条技术引理：二进鸽笼

在着手主定理之前，我们需要一条技术性引理，用来把部分差集 \(A\overset{G}{-}A\) 的纤维（fibers）\(\{(a,a')\in G:a-a'=x\}\) 的大小均匀化。

重要的是要注意，对 \(L\) 的依赖仅以对数方式进入。

证明. 令 \(D\) 为所有满足 \[|\{(a,a')\in G:\ a-a'=x\}|\ge\frac{\alpha|A|^2}{2L|A|}=\frac{\alpha|A|}{2L}\] 的 \(x\) 之集合（于是 \(D\) 是“流行差”的集合），并令 \(\tilde G\) 为 \(G\) 中那些 \(a-a'\in D\) 的对 \((a,a')\)。则 \[|G\setminus\tilde G|\le\frac{\alpha}{2L}|A|\cdot|A\overset{G}{-}A|\le\alpha|A|^2/2,\] 因此 \(|\tilde G|\ge\alpha|A|^2/2\)。另一方面，我们有粗略上界 \[|\{(a,a')\in\tilde G:\ a-a'=x\}|\le\sum_{a'\in A}|\{a\in A:\ a=x+a'\}|\le|A|.\] 于是若令 \(M\) 为使得 \(2^{-M}<\frac{\alpha}{2L}\) 成立的最小整数，我们可以把 \(\tilde G\) 分拆为 \(\tilde G=G_1\cup\dots\cup G_M\)，其中 \(G_m:=\{(a,a')\in\tilde G:\ a-a'\in D_m\}\)，而 \[D_m:=\Bigl\{x\in A\overset{\tilde G}{-}A:\ 2^{-m}|A|<|\{(a,a')\in\tilde G:\ a-a'=x\}|\le2^{-m+1}|A|\Bigr\}.\] 由鸽笼原理，存在 \(1\le m\le M\) 使得 \[|G_m|\ge\frac1M|G|\ge\frac{\alpha}{C\bigl(1+\log\frac1\alpha+\log L\bigr)}|A|^2.\] 由 \(D_m\) 的定义，我们有 \[\frac{|G_m|}{2^{-m+1}|A|}\le|D_m|\le\frac{|G_m|}{2^{-m}|A|};\] 由于 \(D_m=A\overset{G_m}{-}A\)，我们因此看到对所有 \(x\in A\overset{G_m}{-}A\) \[|\{(a,a')\in G':\ a-a'=x\}|\ge2^{-m}|A|\ge\frac{|G'|}{2|A\overset{G}{-}A|}.\] 取 \(G':=G_m\)，论断随之成立。♦

2.6.4　主定理：非对称 BSG

现在我们给出本节的主定理。

反方向观察：若本定理的结论成立，则 \(\E(A,B)=\Omega_\varepsilon(\alpha^{O_\varepsilon(1)}L^{-O(\varepsilon)}|A||B|^2)\)（见本节末习题 2.6.3）。因此本定理在 \(\alpha\) 的多项式损失以及 \(L^\varepsilon\)（其中 \(\varepsilon\) 可任意小）的意义下是尖锐的；习题 2.6.1 中的例子经改造可以表明这种损失是必要的（习题 2.6.2）。

证明的主线索

证明. 直接套用定理 2.31 会损失太多个 \(L\) 的幂。诀窍在于：把 \(B\) 嵌入一条不断增长的集合序列 \(B_0,B_1,B_2,\dots\) 中，其中每个 \(B_j\)（粗略地说）是前一个的部分差集，再用鸽笼原理表明在某一阶段比值 \(|B_{j+1}|/|B_j|\) 被 \(L\) 的一个小幂所控制。这样便可以以可接受的损失应用定理 2.31，并由此推出本定理。（这一证法受到 [40] 中类似论证的启发。）

我们转入细节。方便起见，使用 Landau 记号 \(O()\) 与 \(\Omega()\) 的一个变体，它能吸收 \(\alpha\) 与 \(\log L\) 的因子（我们把它们看作相对接近 \(1\)）。若 \(X,Y\) 是非负量、\(j\) 是一个参数，我们说 \(X=\tilde O_j(Y)\) 或 \(Y=\tilde\Omega_j(X)\)，如果有形如 \[X\le C(j)\,\alpha^{-C(j)}\,Y\,\log^{C(j)}L\] 的估计，其中 \(C(j)>0\) 只依赖于 \(j\)。

令 \(J=J(\varepsilon)\gg1\) 为一待定的大整数。令 \(1>\alpha_1>\dots>\alpha_{J+1}>0\) 为递归定义的序列：\(\alpha_1:=\alpha\) 且 \(\alpha_{j+1}:=\alpha_j^2/2\)（对一切 \(1\le j\le J\)）。由归纳法可见 \(\alpha_j=\tilde\Omega_j(1)\)。我们断言可以找到 \(Z\) 中一列加性集合 \(B_0,B_1,\dots,B_J,B_{J+1}\)，具有以下性质。

• \(B_0=B\)，且对所有 \(1\le j\le J+1\) 有 \[B_j\subseteq\Sym_{\alpha_j}(A).\tag{2.26}\]
• 对所有 \(0\le j\le J+1\) 有 \[\alpha_j^{-2}L|B|\ge|B_j|=\tilde\Omega_j(|B|).\tag{2.27}\]
• 对所有 \(0\le j\le J\)，存在 \(G_j\subseteq B_j\times B_j\) 使得 \[|G_j|=\tilde\Omega_j(|B_j|^2)\tag{2.28}\] 且 \[B_{j+1}=B_j\overset{G_j}{-}B_j.\tag{2.29}\] 此外，对所有 \(x\in B_{j+1}\) 有 \[|\{(b,b')\in G_j:\ b-b'=x\}|=\tilde\Omega_j\!\left(\frac{|B_j|^2}{|B_{j+1}|}\right).\tag{2.30}\]

我们如下构造 \(B_j\)。令 \(B_0:=B\)。由 (2.22) 接着用引理 2.34，我们可以构造 \(G_0\subseteq B_0\times B_0\) 与 \(B_1:=B_0\overset{G_0}{-}B_0\)，使之满足 (2.26)、(2.28)、(2.29)、(2.30)。由于 \(B_0\overset{G_0}{-}B_0\) 中的每个元素至多能由 \(G\) 中的一对以 \(|B_0|\) 种方式表示，我们有 \[|B_1|=|B_0\overset{G_0}{-}B_0|\ge|G_0|/|B_0|=\tilde\Omega_j(|B|),\] 这就是 (2.27) 中的下界；上界则由 (2.26) 与 (2.21) 得到。

接下来，归纳地假设对某个 \(1\le j\le J\) 已经选好 \(B_j\subseteq\Sym_{\alpha_j}(A)\)。应用引理 2.33（取 \(S:=B_j\)）接着用引理 2.34，并利用 (2.27) 中已得到的基数界以及 \(\alpha_j\) 的构造 \(\alpha_{j+1}:=\alpha_j^2/2\)，我们便能找到 \(G_j\subseteq B_j\times B_j\) 与 \(B_{j+1}:=B_j\overset{G_j}{-}B_j\)，使之满足 (2.26)、(2.28)、(2.29)、(2.30)。这就闭合了归纳，于是我们能构造出所有 \(0\le j\le J+1\) 的 \(B_j\)，并类似地得到所有 \(1\le j\le J\) 的 \(G_j\)。

现在到了关键的一步（它解释了为什么我们要把上述过程迭代如此多次）。由 (2.27) 与鸽笼原理，存在 \(1\le j\le J\) 使得 \[|B_{j+1}|=\tilde O_J\!\left(L^{O(1/J)}|B_j|\right);\] 要点在于我们设法把 \(L\) 替换成了小得多的量 \(L^{O(1/J)}\)。现在若应用 (2.29)、(2.28) 与定理 2.31，我们便能找到一个 \(\tilde O_J(L^{O(1/J)})\)-近似群 \(H\)，其基数为 \[|H|=\tilde O_J\!\left(L^{O(1/J)}|B_j|\right)\tag{2.31}\] 以及一个 \(x_j\in Z\)，使得 \[|B_j\cap(H+x_j)|=\tilde\Omega_J\!\left(L^{-C_0/J}|B_j|\right)\tag{2.32}\] 其中 \(C_0\) 是某个绝对常数。

把 \(H\) 与 \(B\)、\(A\) 联系起来

剩下的是把 \(H\) 与 \(B\) 以及 \(A\) 联系起来。我们从 \(B\) 开始。由 (2.32) 与 (2.30)（其中 \(j\) 换成 \(j-1\)）我们有 \[|\{(b,b')\in G_{j-1}:\ b-b'\in B_j\cap(H+x_j)\}|=\tilde\Omega_J\!\left(L^{-C_0/J}|B_{j-1}|^2\right),\] 于是特别地 \[|\{(b,b')\in B_{j-1}\times B_{j-1}:\ b\in H+x_j+b'\}|=\tilde\Omega_J\!\left(L^{-C_0/J}|B_{j-1}|^2\right).\] 因此由鸽笼原理，存在某个 \(b'\) 使得 \[|\{b\in B_{j-1}:\ b\in H+x_j+b'\}|=\tilde\Omega_J\!\left(L^{-C_0/J}|B_{j-1}|\right).\] 于是若令 \(x_{j-1}:=x_j+b'\)，则有 \[|B_{j-1}\cap(H+x_{j-1})|=\tilde\Omega_J\!\left(L^{-C_0/J}|B_{j-1}|\right).\tag{2.33}\]

现在我们对“\(j\) 换成 \(j-1\)、(2.32) 换成 (2.33)”重复这一论证。如此至多迭代 \(J\) 次，我们最终找到一个 \(x=x_0\in Z\)，使得 \[|B\cap(H+x)|=\tilde\Omega_J\!\left(L^{-C_0/J}|B|\right),\] 只要 \(J\)（依赖于 \(\varepsilon\)）取得足够大，这就给出了对 \(B\) 所需的控制。

剩下的是控制 \(A\)。由 (2.32)、(2.31) 与 (2.26)，我们有 \[|\{y\in H+x_j:\ y\in\Sym_{\alpha_j}(A)\}|=\tilde\Omega_J\!\left(L^{-O(1/J)}|H|\right),\] 从而由 \(\Sym_{\alpha_j}(A)\) 与 \(\alpha_j\) 的定义 \[|\{(a,y)\in A\times(H+x_j):\ a+y\in A\}|=\tilde\Omega_J\!\left(L^{-O(1/J)}|H||A|\right).\] 我们把它改写为 \[\sum_{x\in x_j+A}|A\cap(H+x)|=\tilde\Omega_J\!\left(L^{-O(1/J)}|H||A|\right).\] 我们因此能找到 \(x_j+A\) 的一个子集 \(X_0\)，其基数为 \[|X_0|=\tilde\Omega_J\!\left(L^{-O(1/J)}|A|\right)\tag{2.34}\] 使得 \[|A\cap(H+x)|=\tilde\Omega_J\!\left(L^{-O(1/J)}|H|\right)\quad\text{对所有 }x\in X_0.\]

现在我们使用一个类似于证明 Ruzsa 覆盖引理（引理 2.14）时所用的论证。令 \(X\) 为 \(X_0\) 的一个子集，使得诸集合 \(\{H+x:x\in X\}\) 两两不交，且关于集合包含关系是极大的。则我们有 \[|A\cap(H+X)|=\sum_{x\in X}|A\cap(H+x)|=\tilde\Omega_J\!\left(L^{-O(1/J)}|H||X|\right).\tag{2.35}\] 另一方面，若 \(y\in X_0\)，则由 \(X\) 的极大性，存在 \(x\in X\) 使得 \(x+H\) 与 \(y+H\) 相交。换句话说，\(X_0\) 被 \(X+H-H\) 覆盖，因而（由于 \(H\) 是 \(\tilde O(L^{O(1/J)})\)-近似群） \[|X_0|\le|X||H-H|=\tilde O\!\left(|X|L^{O(1/J)}|H|\right).\tag{2.36}\] 合并 (2.34)、(2.35)、(2.36)，我们看到 \(X\) 满足所有所需的性质，只要 \(J\) 依赖于 \(\varepsilon\) 取得足够大。♦

上述定理也可以写成一个类似定理 2.29 的形式：

证明. 应用定理 2.35，并令 \(A':=A\cap(X+H)\) 与 \(B':=B\cap(x+H)\)。♦

由于 (2.8)，上述结果对“\(|A+B|\le K|A|\) 且 \(|A|\) 远大于 \(|B|\)”这一情形给出了一些部分结果，不过这些结果相当弱。一旦我们在第 6.5 节发展出 Plünnecke 不等式，就将给出关于该问题的一个更好的结果。

2.6.5　习题

返回 全书目录