Tao–Vu · 加性组合学 · 第 2 章 和集估计

2.3　Ruzsa 距离与加性能量Ruzsa distance and additive energy

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

倍增常数（doubling constant）\(\sigma[A]\) 度量的是单个加性集合 \(A\) 内部所拥有的加法结构的多少。现在我们引入两个有用的量，用来度量两个加性集合 \(A,B\) 之间共同拥有的加法结构的多少——它们分别是 Ruzsa 距离（Ruzsa distance）和加性能量（additive energy）。

本节目标前面我们已经会用 \(\sigma[A]=|A+A|/|A|\)、\(\delta[A]=|A-A|/|A|\) 描述一个集合“加起来会不会膨胀”。本节要回答两个新问题：
（1）怎样衡量两个集合 \(A,B\) 在加法上有多“接近”？答案是 Ruzsa 距离 \(d(A,B)\)，它居然满足三角不等式，像一把可以传递的尺子。
（2）怎样衡量两个集合之间有多少“凑数”的巧合（即 \(a+b=a'+b'\) 这样的等式有多少个）？答案是 加性能量 \(E(A,B)\)。
把这两个量和倍增常数、差常数联系起来，能得到一批互相控制的不等式，是后续整章估计的工具箱。

2.3.1　Ruzsa 距离

定义 2.5（Ruzsa 距离）设 \(A\) 与 \(B\) 是处于同一公共背景群（ambient group）\(Z\) 中的两个加性集合。我们定义 \(A,B\) 之间的 Ruzsa 距离 \(d(A,B)\) 为 \[ d(A,B):=\log\frac{|A-B|}{|A|^{1/2}\,|B|^{1/2}}. \] 例如，由此 \(d(A,A)=\log\delta[A]\)。

这里的对数把“比值”变成了“距离”：当 \(A,B\) 紧密关联时差集 \(|A-B|\) 很小，距离接近其下界；当二者毫无关系时差集很大，距离也大。下面这个例子帮你建立数感。

例：先把定义算具体 取整数集 \(A=\{0,1,2,3\}\)（一个长度为 4 的等差数列）。
  1. 差集 \(A-A=\{-3,-2,-1,0,1,2,3\}\)，共 \(7\) 个元素，\(|A-A|=7\)。
  2. 于是 \(d(A,A)=\log\dfrac{|A-A|}{|A|^{1/2}|A|^{1/2}}=\log\dfrac{7}{4}=\log\delta[A]\)，因为 \(\delta[A]=|A-A|/|A|=7/4\)。
  3. 再取 \(B=\{0,1,2,3\}\) 的一个平移 \(B=\{10,11,12,13\}\)。则 \(A-B=\{-13,\dots,-7\}\) 也是 \(7\) 个元素，\(d(A,B)=\log\frac{7}{4}\) 不变——平移不改变 Ruzsa 距离（见习题 2.3.1）。

现在我们来说明“Ruzsa 距离”这个术语是有道理的。

引理 2.6（Ruzsa 三角不等式）Ruzsa 距离 \(d(A,B)\) 是非负的、对称的，并且满足三角不等式 \[ d(A,C)\le d(A,B)+d(B,C) \] 对一切处于同一公共背景群 \(Z\) 中的加性集合 \(A,B,C\) 成立。
证明. 非负性来自 (2.1)（即 \(|A-B|\ge\max(|A|,|B|)\ge|A|^{1/2}|B|^{1/2}\)，故对数非负）。对称性来自 \(B-A=-(A-B)\)，因此 \(|B-A|=|A-B|\)，交换 \(A,B\) 距离不变。现在证明三角不等式，它可以改写成乘法形式 \[ |A-C|\le\frac{|A-B|\,|B-C|}{|B|}. \] 由恒等式 \[ a-c=(a-b)+(b-c) \] 我们看出：\(A-C\) 中的每个元素 \(a-c\)，都至少有 \(|B|\) 个互不相同的、形如 \(x+y\) 的表示，其中 \((x,y)\in(A-B)\times(B-C)\)。命题随即得证。♦

这一步是全节的“发动机”，但 OCR 般的一句话容易让人滑过去。我们把它拆开讲清楚。

  1. 固定 \(A-C\) 中一个元素 \(w=a-c\)（\(a\in A,\;c\in C\)）。
  2. 对任意一个 \(b\in B\)，令 \(x:=a-b\in A-B\)，\(y:=b-c\in B-C\)。则 \(x+y=(a-b)+(b-c)=a-c=w\)。这就为 \(w\) 造出了一个落在 \((A-B)\times(B-C)\) 里的表示 \((x,y)\)。
  3. 当 \(b\) 跑遍 \(B\) 的 \(|B|\) 个值时，得到的 \(|B|\) 个对子 \((x,y)\) 互不相同——因为从 \(x=a-b\) 就能反推出 \(b=a-x\)，不同的 \(b\) 给出不同的 \(x\)。所以 \(w\) 至少有 \(|B|\) 个不同表示。
  4. 不同的 \(w\) 所用的表示对子也不会撞车：因为对子 \((x,y)\) 的和 \(x+y\) 恰好就是 \(w\)，和不同则对子不同。
  5. 于是把所有 \(w\in A-C\) 各自的表示对子加起来，总数 \(\ge |A-C|\cdot|B|\)；而所有可用对子总共只有 \(|(A-B)\times(B-C)|=|A-B|\,|B-C|\) 个。两边一比：\(|A-C|\cdot|B|\le|A-B|\,|B-C|\)，即得乘法形式。再取对数就是三角不等式。♦
同一个 \(w=a-c\) 借助每个 b 都能写成 (a−b)+(b−c) a c w = a − c（A−C 中的一个元素） b₁ b₂ b₃ …（共 |B| 个） x=a−b ∈ A−B y=b−c ∈ B−C 每选一个 b 就得到一对 (x,y)，x+y=w；|B| 个 b 给出 |B| 个不同表示
每个 \(w\in A-C\) 至少有 \(|B|\) 种写法；总写法数不超过 \(|A-B||B-C|\)，故 \(|A-C|\,|B|\le|A-B||B-C|\)。

关于这一不等式的“近似版本”——把完整差集换成“几乎完整”的差集（至少用到 \(75\%\) 的差），见习题 2.5.4。

因此 Ruzsa 距离满足度量（metric）的全部公理，只差一条：我们并没有“对一切 \(A\) 都有 \(d(A,A)=0\)”这件事（另外，只要 \(G+x,G+y\) 是某个群 \(G\) 的陪集，就有 \(d(G+x,G+y)=0\)）。实际上，关于这个 Ruzsa 距离何时为零，我们有一个精确刻画。

命题 2.7设 \((A,Z)\) 是一个加性集合。则以下各条等价：
  • \(\sigma[A]=1\)（即 \(|A+A|=|A|\)）；
  • \(\delta[A]=1\)（即 \(|A-A|=|A|\)，或 \(d(A,A)=0\)）；
  • 对至少一个加性集合 \(B\) 有 \(d(A,B)=0\)；
  • 对至少一对满足 \(n+m\ge2\) 的非负整数 \(n,m\)，有 \(|nA-mA|=|A|\)；
  • 对所有非负整数 \(n,m\)，有 \(|nA-mA|=|A|\)；
  • \(A\) 是 \(Z\) 的某个有限子群 \(G\) 的一个陪集。
证明. 应用命题 2.2 与 Ruzsa 三角不等式即可。♦
例：哪种集合“加了也不膨胀” 命题 2.7 的核心信息是：一个集合“加自己也不变大”这件事极其苛刻，当且仅当它本质上是一个子群（的平移）。
  1. 取 \(Z=\mathbb{Z}/6\mathbb{Z}\)，\(G=\{0,2,4\}\) 是子群。则 \(G+G=\{0,2,4\}=G\)，\(|G+G|=|G|=3\)，\(\sigma[G]=1\)。陪集 \(A=G+1=\{1,3,5\}\) 同样 \(\sigma[A]=1\)。
  2. 反过来，若 \(A=\{0,1,2,3\}\subset\mathbb{Z}\) 不是任何子群的陪集，则 \(A+A=\{0,\dots,6\}\) 有 \(7\) 个元素，\(\sigma[A]=7/4>1\)，确实膨胀了。
直觉：只有“加法封闭”的结构（子群）才能在相加后不长大；其余任何集合都会冒出新元素。

本章后面我们会把这个命题推广到“Ruzsa 距离、差常数、倍增常数分别比 \(0,0,1\) 略大、但仍相当小”的情形；见命题 2.26。

尽管一般来说 \(d(A,A)\) 并不为零，把 Ruzsa 距离当作度量来想仍是一个有用的启发式（脚注：可以人为地把 Ruzsa 距离改造成真正的度量，办法是把 \(A\) 与它的所有平移 \(A+x\) 视为同一对象、并把 \(d(A,A)\) 重新定义为零；或者引入度量空间 \(X:=\{A\times\{j\}:A\subseteq Z;\,0<|A|<\infty;\,j\in\{1,2\}\}\)——它由 \(Z\) 的每个有限非空子集的两份拷贝组成（仍把 \(A\) 与它的各个平移视为同一对象）——并定义 \(d_X(A\times\{j\},B\times\{k\})\) 当 \(A\times\{j\}\ne B\times\{k\}\) 时等于 \(d(A,B)\)，否则等于 \(0\)。不过在这样人为的设定下工作似乎并无实质好处）。

下面我们把差常数与倍增常数联系起来。由 Ruzsa 距离与倍增常数的定义，我们有恒等式 \[ d(A,-A)=\log\sigma[A]. \tag{2.4} \] 特别地，由引理 2.6（取 \(B=-A\) 作中间集合）有 \[ \log\delta[A]=d(A,A)\le d(A,-A)+d(-A,A)=2\log\sigma[A], \] 于是得到估计 \[ \delta[A]\le\sigma[A]^2 \tag{2.5} \] 换句话说 \(\displaystyle|A-A|\le\frac{|A+A|^2}{|A|}\)。类似的论证给出更一般的估计 \[ |B-B|\le\frac{|A+B|^2}{|A|} \tag{2.6} \] 对任意两个处于同一公共背景群 \(Z\) 的加性集合 \(A,B\) 成立。

解读 (2.4)–(2.6)：为什么 \(\delta\le\sigma^2\)
  1. 先验证 (2.4)：\(d(A,-A)=\log\dfrac{|A-(-A)|}{|A|^{1/2}|{-A}|^{1/2}}=\log\dfrac{|A+A|}{|A|}=\log\sigma[A]\)。（用到 \(A-(-A)=A+A\) 与 \(|-A|=|A|\)。）
  2. 把三角不等式 \(d(A,A)\le d(A,-A)+d(-A,A)\) 中的两项都换成 \(\log\sigma[A]\)，得 \(\log\delta[A]\le2\log\sigma[A]\)，去掉对数即 (2.5)。
  3. 直觉：差集不会比和集“坏太多”——和集小（结构好），差集至多是它的平方量级。后面 (2.11) 会反过来用差集控制和集。

事实证明，我们也能反过来用一个集合的差常数去界定它的倍增常数；见下文 (2.11)。

2.3.2　加性能量

引入 Ruzsa 距离之后，我们转向与之密切相关的概念——两个加性集合之间的加性能量 \(E(A,B)\)。

定义 2.8（加性能量）若 \(A\) 与 \(B\) 是背景群为 \(Z\) 的两个加性集合，我们定义 \(A,B\) 之间的加性能量 \(E(A,B)\) 为 \[ E(A,B):=\bigl|\{(a,a',b,b')\in A\times A\times B\times B:\ a+b=a'+b'\}\bigr|. \]

用大白话说，\(E(A,B)\) 数的是“四元组的巧合”：从 \(A\) 取 \(a,a'\)、从 \(B\) 取 \(b,b'\)，问 \(a+b\) 恰好等于 \(a'+b'\) 的取法有多少。巧合越多，说明两集合在加法上越“纠缠”。

例：把加性能量数出来 取 \(A=B=\{0,1,2\}\)。我们数满足 \(a+b=a'+b'\) 的四元组 \((a,a',b,b')\)。
  1. 等价于数 \(a-a'=b'-b\)。记和 \(n=a+b\)，先统计每个和值 \(n\) 被表示成 \(a+b\)（\(a,b\in\{0,1,2\}\)）的次数 \(r(n)\)： \(r(0)=1,\ r(1)=2,\ r(2)=3,\ r(3)=2,\ r(4)=1\)。
  2. 对固定的和值 \(n\)，凑出 \(a+b=a'+b'=n\) 的四元组有 \(r(n)^2\) 个。
  3. 所以 \(E(A,B)=\sum_n r(n)^2=1^2+2^2+3^2+2^2+1^2=1+4+9+4+1=19\)。
  4. 核对平凡界：\(|A||B|=9\le 19\le|A||B|\min(|A|,|B|)=9\cdot3=27\)。落在区间内，符合 (2.7)。
这个“按和值平方求和”的算法正是下面引理 2.9 的内容。
A=B={0,1,2} 的加法表（格子里是 a+b） b\a 012 012 012 123 234 和值 n：表示次数 r(n) r(0)=1r(1)=2r(2)=3 r(3)=2r(4)=1 E=Σr(n)²=19
把加法表里每个和值出现的次数 \(r(n)\) 平方再求和，就是加性能量 \(E(A,B)\)。对角线方向（相同和值）越“扎堆”，能量越大。

我们注意到平凡的上下界 \[ |A||B|\le E(A,B)\le|A||B|\min(|A|,|B|). \tag{2.7} \] 下界成立是因为：只要 \((a,b)=(a',b')\)，就有 \(a+b=a'+b'\)，这已经贡献了 \(|A||B|\) 个四元组。要看上界：若固定 \(a,a',b\)，则 \(b'=a+a'-b\) 被完全确定，因此 \(E(A,B)\le|A|^2|B|\)；类似的论证给出 \(E(A,B)\le|A||B|^2\)。两者取较小，即得上界。注意命题 2.3 处理的正是 \(E(A,B)=|A||B|\)（即取到下界）的情形。

在第 4.2 节（发展出 Fourier 变换工具之后）以及第 2.5 节（建立 Balog–Szemerédi–Gowers 定理之后），我们会更全面地分析加性能量。眼下我们集中于它的初等性质。首先我们注意到对称性 \(E(A,B)=E(B,A)\) 与平移不变性 \(E(A+x,B+y)=E(A,B)\)（对一切 \(x,y\in Z\)）。由平凡的观察 \[ a+b=a'+b'\iff a-b'=a'-b \] （再把 \(b,b'\) 互换标号）还可看出 \(E(A,B)=E(A,-B)\)，同样地把 \(A\) 反射成 \(-A\) 也不改变能量。

加性能量反映了 \(A\) 与 \(B\)（或 \(-B\)）的平移相交的程度，下面这些简单的恒等式说明了这一点。

引理 2.9设 \(A,B\) 是背景群为 \(Z\) 的加性集合。则有恒等式 \[ |A||B|=\sum_{x\in A+B}|A\cap(x-B)|=\sum_{y\in A-B}|A\cap(B+y)| \] 以及 \[ E(A,B)=\sum_{x\in A+B}|A\cap(x-B)|^2=\sum_{y\in A-B}|A\cap(B+y)|^2=\sum_{z\in(A-A)\cap(B-B)}|A\cap(z+A)|\,|B\cap(z+B)|. \] 特别地，若用 \(r_{A+B}(n)\) 表示 \(n\) 写成 \(a+b\)（\(a\in A,b\in B\)）的表示个数，并类似地定义 \(r_{A-B}(n)\)，则有 \[ |A||B|=\sum_n r_{A+B}(n)=\sum_n r_{A-B}(n);\qquad E(A,B)=\sum_n r_{A+B}(n)^2=\sum_n r_{A-B}(n)^2. \]
证明. 一个简单的计数论证给出 \[ |A||B|=\sum_{x\in A+B}|\{(a,b)\in A\times B:a+b=x\}|=\sum_{x\in A+B}|A\cap(x-B)|; \] （因为 \(a+b=x\) 等价于 \(a\in A\) 且 \(a=x-b\in x-B\)，即 \(a\in A\cap(x-B)\)。）把 \(B\) 换成 \(-B\)，同理得到 \(|A||B|=\sum_{y\in A-B}|A\cap(B+y)|\)。这给出第一组恒等式。对于第二组，我们计算 \[ \begin{aligned} \sum_{x\in A+B}|A\cap(x-B)|^2&=\sum_{x\in A+B}|\{(a,b)\in A\times B:a+b=x\}|^2\\ &=\sum_{x\in A+B}|\{(a,a',b,b'):a+b=a'+b'=x\}|\\ &=|\{(a,a',b,b'):a+b=a'+b'\}|\\ &=|\{(a,a',b,b'):a-b'=a'-b\}|\\ &=\sum_{y\in A-B}|A\cap(B+y)|^2 \end{aligned} \] 以及 \[ \begin{aligned} \sum_{z\in(A-A)\cap(B-B)}|A\cap(z+A)|\,|B\cap(z+B)|&=\sum_{z}|\{(a,a',b,b'):z=a-a'=b-b'\}|\\ &=|\{(a,a',b,b'):a-a'=b-b'\}|\\ &=|\{(a,a',b,b'):a+b'=a'+b\}|. \end{aligned} \] 由 \(E(A,B)\) 的定义（并适当互换标号）即得各式。最后一组恒等式成立是因为 \(r_{A+B}(n)=|A\cap(n-B)|\) 且 \(r_{A-B}(n)=|A\cap(B+n)|\)。♦
为什么“平方求和”自然出现 关键一步是把“数四元组”转化为“按和值分桶后平方”。
  1. 把所有 \((a,b)\) 按其和 \(x=a+b\) 分到不同的桶里，第 \(x\) 桶里有 \(r_{A+B}(x)=|A\cap(x-B)|\) 个对子。
  2. 一个满足 \(a+b=a'+b'=x\) 的四元组，就是在第 \(x\) 桶里有序地取两个对子 \((a,b)\) 与 \((a',b')\)，共 \(r_{A+B}(x)^2\) 种。
  3. 对所有桶求和：\(E(A,B)=\sum_x r_{A+B}(x)^2\)。这正是上面例子里 \(\sum r(n)^2=19\) 的来历。
  4. 第三个表达式（按 \(z\) 求和）则换了个角度：把四元组按“差” \(z=a-a'=b-b'\) 分类，每类有 \(|A\cap(z+A)|\,|B\cap(z+B)|\) 个。

作为这个引理的推论，我们得到下列不等式：它们断言，Ruzsa 距离小的集合对，加性能量大；而加性能量大的集合对，（在适当平移、必要时反射之后）交集大。

推论 2.10设 \(A,B\) 是加性集合。则存在 \(x\in A+B\) 与 \(y\in A-B\)，使得对正负号 \(\pm\) 的任一选择都有 \[ |A\cap(x-B)|,\ |A\cap(B+y)|\ \ge\ \frac{E(A,B)}{|A||B|}\ \ge\ \frac{|A||B|}{|A\mp B|}. \tag{2.8} \] 特别地，上述各量都以 \(|(A-A)\cap(B-B)|\) 为上界。最后，我们有 Cauchy–Schwarz 不等式 \[ E(A,B)\le E(A,A)^{1/2}E(B,B)^{1/2}. \tag{2.9} \]
证明. 由引理 2.9 与 Cauchy–Schwarz， \[ \frac{E(A,B)}{|A||B|}\ge\frac{|A||B|}{|A\pm B|}. \] （这是因为 \((|A||B|)^2=\bigl(\sum_{x}r_{A+B}(x)\bigr)^2\le|A+B|\cdot\sum_x r_{A+B}(x)^2=|A+B|\cdot E(A,B)\)；对 \(A-B\) 同理。）又由引理 2.9 的最后部分， \[ E(A,B)\le|A||B|\max_{x\in A+B}r_{A+B}(x),\qquad E(A,B)\le|A||B|\max_{y\in A-B}r_{A-B}(y), \] （因为 \(\sum r^2\le(\max r)\sum r=(\max r)|A||B|\)）这就确立了 (2.8) 中存在性的那个 \(x\)（与 \(y\)）。要把 \(|A\cap(x-B)|\) 与 \(|A\cap(B+y)|\) 控制住，注意若 \(z\in A\cap(x-B)\)，则 \(A\cap(x-B)\subset z+\bigl((A-A)\cap(B-B)\bigr)\)，从而 \(|A\cap(x-B)|\le|(A-A)\cap(B-B)|\)，类似地 \(|A\cap(B+y)|\le|(A-A)\cap(B-B)|\)。最后，(2.9) 来自引理 2.9 中的公式 \(E(A,B)=\sum_{z\in(A-A)\cap(B-B)}|A\cap(z+A)|\,|B\cap(z+B)|\) 与 Cauchy–Schwarz 不等式。♦
读懂 (2.8)：能量大 ⇒ 有“热门和值”
  1. \(\dfrac{E}{|A||B|}=\dfrac{\sum_x r(x)^2}{\sum_x r(x)}\) 正是表示次数 \(r(x)\) 的加权平均。平均值一定 \(\le\) 最大值，所以存在某个 \(x\) 使 \(r_{A+B}(x)=|A\cap(x-B)|\ge E/(|A||B|)\)——即存在一个“热门和值”，它被很多对子凑出。
  2. 右边 \(\dfrac{|A||B|}{|A+B|}\) 又是“总对子数 ÷ 桶数”，是每桶平均装多少对。这串不等式说明：能量越大、和集越小，必有某个和值被异常多地凑出。
  3. 这正是“两集合在加法上纠缠”的定量体现，是后面 Balog–Szemerédi–Gowers 理论的种子。

另一个同一精神下的联系是：

引理 2.11设 \(A,B\) 是加性集合。则对任意 \(x\in A+B\) 有 \(\displaystyle|A\cap(x-B)|\le\frac{|A-B|^2}{|A+B|}\)。
证明.（Lev Vsevolod，私人通信）我们可以把待证不等式改写为 \[ |\{(a,b,c)\in A\times B\times(A+B):a+b=x\}|\le|(A-B)\times(A-B)|. \] 现在对左边集合中的每个 \((a,b,c)\)，把 \(c\) 写成 \(c=a_c+b_c\)，其中 \(a_c\in A,\ b_c\in B\)，然后构造对子 \((a-b_c,\ a_c-b)\in(A-B)\times(A-B)\)。利用恒等式 \(c=x-(a-b_c)+(a_c-b)\) 可以验证这个映射是单射。命题随之得证。♦
把引理 2.11 的两步看清
  1. 左边那个集合：因为约束是 \(a+b=x\)，满足它的 \((a,b)\) 恰有 \(|A\cap(x-B)|\) 个，而 \(c\) 在 \(A+B\) 里自由取，所以该集合大小 \(=|A\cap(x-B)|\cdot|A+B|\)。
  2. 右边 \(|(A-B)\times(A-B)|=|A-B|^2\)。单射保证“左 ≤ 右”，于是 \(|A\cap(x-B)|\cdot|A+B|\le|A-B|^2\)，移项即得结论。
  3. 为什么映射是单射：由 \(c=x-(a-b_c)+(a_c-b)\)，从像 \((a-b_c,\,a_c-b)\) 能还原 \(c\)（\(x\) 固定）；又 \(a+b=x\) 使 \(b=x-a\)，配合还原信息即可还原全部 \((a,b,c)\)。♦
推论 2.12设 \(A,B\) 是背景群为 \(Z\) 的加性集合。则存在 \(x\in A+B\)，使得 \[ \frac{|A-B|^2}{|A\cap(x-B)|}\le\frac{|A-B|^2|A||B|}{E(A,B)}\le\frac{|A-B|^3}{|A||B|}. \tag{2.10} \] 此外我们有 \[ d(A,-B)\le3\,d(A,B). \]
证明. (2.10) 中的不等式来自 (2.8)（具体地：\(|A\cap(x-B)|\ge E/(|A||B|)\) 给出第一个 \(\le\)；\(E\ge(|A||B|)^2/|A-B|\) 给出第二个 \(\le\)）。最后的不等式 \(d(A,-B)\le3d(A,B)\) 则由引理 2.11 与 Ruzsa 距离的定义推出（取使 \(|A\cap(x-B)|\) 最大的 \(x\)，结合 \(|A\cap(x-B)|\le|A-B|^2/|A+B|\) 得 \(|A+B|\le|A-B|^3/(|A||B|)\)，再代入距离定义即可）。♦

由 (2.10) 与 (2.5)，我们得到不等式 \[ \delta[A]^{1/2}\le\sigma[A]\le\delta[A]^3 \tag{2.11} \] 它们最早见于文献 [289]。因此，一个加性集合的倍增常数小，当且仅当它的差常数小。下界是否最优尚不清楚；不过，借助 Plünnecke 不等式，上界可以改进为 \(\sigma[A]\le\delta[A]^2\)，见习题 6.5.15。

小结 (2.11)：和集与差集“同生共死”
  1. 由 (2.5)，\(\delta[A]\le\sigma[A]^2\)，开方得 \(\delta[A]^{1/2}\le\sigma[A]\)（下界）。
  2. 在 \(d(A,-B)\le3d(A,B)\) 中取 \(B=A\)：\(d(A,-A)\le3d(A,A)\)，即 \(\log\sigma[A]\le3\log\delta[A]\)，得 \(\sigma[A]\le\delta[A]^3\)（上界）。
  3. 结论：和集小 \(\Leftrightarrow\) 差集小（只相差多项式幂次）。这在直觉上并不显然——加法与减法看似不同，却被 Ruzsa 距离绑在了一起。

2.3.3　用 Ruzsa 距离控制迭代和集

下面我们展示如何用 Ruzsa 距离来控制迭代和集（iterated sum sets）。我们先给出一个引理，它能控制 \(A+B\) 之“大部分”的迭代和集。

引理 2.13设 \(A\) 与 \(B\) 是同一公共背景群中的加性集合。则存在 \(S\subset A+B\)，使得 \[ |\{(a,b)\in A\times B:a+b\in S\}|\ge|A||B|/2 \tag{2.12} \] 并且 \[ |A+B+nS|\le\frac{2^n|A+B|^{2n+1}}{|A|^n|B|^n} \tag{2.13} \] 对一切整数 \(n\ge0\) 成立。注意 (2.12) 给出了 \(|S|\) 的下界，即 \[ |S|\ge\max(|A|,|B|)/2. \tag{2.14} \]
证明. 若我们把 \(S\) 定义为所有满足 \[ |\{(a,b)\in A\times B:a+b=x\}|\ge\frac{|A||B|}{2|A+B|} \] 的 \(x\in A+B\) 之集合（即“表示次数高于平均一半”的那些和值），那么 \[ |\{(a,b)\in A\times B:a+b\in(A+B)\setminus S\}|<|A+B|\cdot\frac{|A||B|}{2|A+B|}=\frac{|A||B|}{2}, \] 这就给出了 (2.12)（落在 \(S\) 上的对子至少占一半）。
现在证明 (2.13)。\(A+B+nS\) 的一个典型元素可以写成 \[ a_0+s_1+s_2+\cdots+s_n+b_{n+1} \] 其中 \(a_0\in A,\ b_{n+1}\in B,\ s_1,\dots,s_n\in S\)。由 \(S\) 的定义，我们可以把它至少用 \(\bigl(\tfrac{|A||B|}{2|A+B|}\bigr)^n\) 种不同方式展开成 \[ a_0+(b_1+a_1)+(b_2+a_2)+\cdots+(b_n+a_n)+b_{n+1}, \] 其中 \(b_i\in B,\ a_i\in A\) 且 \(b_i+a_i=s_i\)（\(1\le i\le n\)）。我们把它重新分组成 \(A+B\) 中 \(n+1\) 个元素之和： \[ (a_0+b_1)+(a_1+b_2)+\cdots+(a_n+b_{n+1}), \] 并注意到：对固定的 \(a_0,s_1,\dots,s_n,b_{n+1}\)，量 \(a_0+b_1,\ a_1+b_2,\dots,a_n+b_{n+1}\) 完全决定了所有变量 \(a_0,\dots,a_n,b_1,\dots,b_{n+1}\)。于是我们证明了：\(A+B+nS\) 的每个元素都至少有 \(\bigl(\tfrac{|A||B|}{2|A+B|}\bigr)^n\) 个形如 \(t_0+\cdots+t_n\)（每个 \(t_i\in A+B\)）的表示。命题随即得证（总表示对数最多 \(|A+B|^{n+1}\) 个，故 \(|A+B+nS|\cdot\bigl(\tfrac{|A||B|}{2|A+B|}\bigr)^n\le|A+B|^{n+1}\)）。♦
a₀+s₁+…+sₙ+bₙ₊₁ 重新分组为 (A+B) 的链 a₀+b₁ a₁+b₂ a₂+b₃ … aₙ+bₙ₊₁ 每块都属于 A+B，共 n+1 块 ⇒ 最多 |A+B|ⁿ⁺¹ 种链 每个元素 ≥ (|A||B|/2|A+B|)ⁿ 种链 ⇒ 个数被压住 表示越多 ⇒ 不同元素越少 ⇒ |A+B+nS| 有上界 (2.13)
把长和拆成 \(n+1\) 个 \(A+B\) 的块：每个元素表示方式很多，而总的链数有限，于是元素总数被牢牢压住。
直觉：为什么取“高表示次数”的 S
  1. 每个和值平均被 \(\dfrac{|A||B|}{|A+B|}\) 个对子凑出。\(S\) 只收下“高于平均一半”的和值。
  2. 这样做有两个好处：一是被丢弃的对子总数 \(<|A||B|/2\)，所以 \(S\) 仍“接住”了一半以上的对子（(2.12)）；二是 \(S\) 里每个元素的表示次数都很高，这让 \(A+B+nS\) 的元素拥有大量重复表示，从而个数稀少（(2.13)）。
  3. 一句话：用“热门和值”搭桥，迭代相加也不会爆炸。

这个结果再结合 Ruzsa 三角不等式，便可推出对 \(A,B\) 迭代和集的控制；见习题 2.3.10。不过在下一节，我们将采用一种能给出稍好界的方法（在第 6.5 节还会发展出更好的结果）。

习题

习题 2.3.1–2.3.18
  1. 若 \(\varphi:Z'\to Z\) 是核 \(\ker(\varphi):=\varphi^{-1}(\{0\})\) 有限的满同态，\(A,B\) 为 \(Z\) 中的加性集合，证明 \(d(\varphi^{-1}(A),\varphi^{-1}(B))=d(A,B)\)。并证明对任意 \(x,y\in Z\) 有 \(d(A+x,B+y)=d(A,B)\)。
  2. 若 \(A,B,C,D\) 是 \(Z\) 中的加性集合，证明 \[ d(A,B)-\tfrac12\log|C||D|\le d(A+C,B+D)\le d(A,B)+\log|C-D| \] 以及 \(d(A,B\cup C)\le\max(d(A,B),d(A,C))+\tfrac12\log2\)。若 \(A',B'\) 是 \(Z'\) 中的加性集合，证明 \(d(A\times A',B\times B')=d(A,B)+d(A',B')\)。
  3. 设 \(A,B\) 同背景群。证明 \(d(A,B)\le\tfrac12\log|A|+\tfrac12\log|B|\)，且等号成立当且仅当 \(d(A,-B)=\tfrac12\log|A|+\tfrac12\log|B|\)。
  4. 设 \(A,B,C\) 为 \(Z\) 中加性集合。证明当 \(C\subseteq B\) 时 \[ d(A,C)\le d(A,B)+\tfrac12\log\frac{|B|}{|C|}; \tag{2.15} \] 这说明 Ruzsa 距离 \(d(A,B)\) 在对 \(A,B\) 之一或二者作“加细”时是稳定的。把此不等式与三角不等式 \(d(A,-B)\le d(A,(x-A)\cap B)+d((x-A)\cap B,-B)\) 结合，可给出引理 2.11 的另一证明。
  5. 证明：对任意 \(n\ge1\)，存在加性集合 \(A\) 使 \(|A|=4^n,\ |A+A|=10^n,\ |2A-A|=28^n\)。从而不可能得到形如 \(|2A-A|=O(\sigma^2[A]|A|)\) 的估计。
  6. 设 \(A,B\) 同背景群。证明 \(e^{-2d(A,B)}|A|\le|B|\le e^{2d(A,B)}|A|\)。从而在 Ruzsa 距离下接近的集合，其基数也必然接近（反之远不成立）。
  7. 设 \(A,B\) 同背景群 \(Z\)。证明 \(d(A,B)=0\) 当且仅当 \(A,B\) 是 \(Z\) 的同一个有限子群 \(G\) 的陪集。（此结果稍后会被推广，见命题 2.27。）
  8. 设 \(A\) 是加性群 \(Z\) 中的加性集合，\(G\) 是 \(Z\) 的有限子群。证明 \(\sigma[A+G]\le\frac{|3A|}{|A|}\)。（提示：对 \(2A,-A,G\) 应用 Ruzsa 三角不等式。）由此推出：若 \(\pi:Z\to Z'\) 是群同态，则 \(\sigma[\pi(A)]\le\frac{|3A|}{|A|}\)。不能把三倍常数 \(\frac{|3A|}{|A|}\) 换成倍增常数，见习题 2.2.10；但参见习题 6.5.17。
  9. 设 \(K\) 为大整数，令 \(A=B=\{e_1,\dots,e_K\}\) 为 \(\mathbb{Z}^K\) 的标准基。证明若 \(S\) 是 \(A+B\) 中任何满足 (2.12) 的子集，则 \(|A+B+nS|=\Omega\!\left(\frac{|A+B|^{2n+1}}{|A|^n|B|^n}\right)\)（用 Landau 记号 \(\Omega\)）。这说明引理 2.13 无法被实质改进（或许只能改进界 (2.14)）。
  10. 设 \(A,B\) 同背景群且 \(|A+B|\le K|A|^{1/2}|B|^{1/2}\)（某 \(K\ge1\)）。用引理 2.13 与多次应用 Ruzsa 三角不等式，证明对一切整数 \(n_1,n_2,n_3,n_4\) \[ |n_1A-n_2A+n_3B-n_4B|=O_{n_1,n_2,n_3,n_4}\!\left(K^{O_{n_1,n_2,n_3,n_4}(1)}|A|^{1/2}|B|^{1/2}\right). \] 特别地，确立 \(d(n_1A-n_2A+n_3B-n_4B,\ n_5A-n_6A+n_7B-n_8B)\le O_{n_1,\dots,n_8}(1+d(A,B))\)。此界将在推论 2.23、2.24 略加改进；另见推论 2.19 中可消去低阶项的“张量幂技巧”。
  11. 设 \(G,H\) 为 \(Z\) 的子群。证明 \(d(G,H)=\log\frac{|G|^{1/2}|H|^{1/2}}{|G\cap H|}\)。由此推出 \(d(G,H)=d(G,G+H)+d(G+H,H)=d(G,G\cap H)+d(G\cap H,H)\)。又若 \(K\) 是另一子群，证明收缩性 \(d(G+K,H+K)\le d(G,H)\) 与 \(d(G\cap K,H\cap K)\le d(G,H)\)。注意：限制在 \(Z\) 的子群上时，Ruzsa 距离（凭命题 2.7）确实是一个真正的度量。另见习题 2.4.7、2.4.8。
  12. 设 \(A\) 为加性集合。证明 \(\sigma[A\cup(-A)]\le2\sigma[A]+\sigma[A]^2\)。从而小倍增的集合可嵌入一个小倍增的对称集合（即满足 \(-B=B\) 的集合 \(B\)）中，且基数至多翻倍。
  13. 设 \(A\) 为加性集合。证明 \(|A-A|\le|A+A|^{3/2}\) 与 \(|A+A|\le|A-A|^{3/2}\)。（提示：用 (2.11)、推论 2.12 与 (2.1)。）
  14. 设 \(A\) 为加性集合。证明存在 \(x\in A-A\)，使集合 \(F:=A\cap(x+A)\) 满足 \(|F|\ge|A|/\sigma[A]\) 且倍增常数 \(\sigma[F]\le\sigma[A]^2\)。从而每个小倍增的集合 \(A\) 都含有一个大的、小倍增的对称子集 \(F\)（它可能关于非零原点 \(x/2\) 对称）。
  15. 设 \(A,B\) 同背景群 \(Z\)。证明 \(\delta[A]\le e^{2d(A,B)}\) 与 \(\sigma[A]\le e^{6d(A,B)}\)。从而只有小倍增常数的集合才能在 Ruzsa 度量下接近别的集合。（其中 \(6\) 可降为 \(4\)，见习题 6.5.15。）
  16. 设 \(A,B\) 同背景群 \(Z\)。证明 \(\sigma[A\cup B]\le e^{d(A,B)}+2e^{4d(A,B)}\)。从而在 Ruzsa 度量下接近的一对集合可嵌入一个略大的小倍增集合中。反方向地，确立 \[ d(A,B)\le\log\sigma[A\cup B]+\tfrac12\log\frac{|A\cup B|}{|A|}+\tfrac12\log\frac{|A\cup B|}{|B|}. \]
  17. 设 \(A,B\) 同背景群 \(Z\)，且 \(\sigma[A],\sigma[B]\le K\)（某 \(K\ge1\)），\(A\cap B\) 非空。证明 \(\sigma[A\cup B]\le2K+K^3\frac{\min(|A|,|B|)}{|A\cap B|}\)。从而当两个小倍增的集合有相当大的交集时，它们的并仍是小倍增的。
  18. 设 \(K\ge1\)，\(A_1,A_2,A_3\) 同背景群 \(Z\)，且对 \(j=1,2,3\) 有 \(|A_j\cap A_3|\ge\frac1K|A_j|\) 与 \(|A_j+A_j|\le K|A_j|\)。证明 \(|A_1+A_2|\le K^6|A_3|\)。提示：用三角不等式 \(d(A_1,-A_2)\le d(A_1,-(A_1\cap A_3))+d(-(A_1\cap A_3),A_2\cap A_3)+d(A_2\cap A_3,-A_2)\)。

返回 全书目录