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

2.7　非交换情形下的类比Non-commutative analogues

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步把直觉与每步动机讲清楚，不用比喻。本节是全章中较难的一节，建议先确保已熟悉前几节里“加法集合、加倍常数 \(K\)、Ruzsa 距离、加性能量、覆盖引理、Balog–Szemerédi–Gowers 定理”这些概念。

上面的许多论证都能搬到非交换（non-commutative）的情形，不过此时当然必须小心乘法的次序。我们在这里勾勒一些要点，把细节留作习题。更多细节可参见 [362]。

本节目标前面六节里集合都生活在交换群里（\(a+b=b+a\)），所以 \(A+B=B+A\)、能量有大量对称性、各种估计都很顺手。本节要问：如果群不交换（比如矩阵乘法 \(MN\neq NM\)），把“加法”换成“乘法”，这些结论还成立吗？答案是：大部分能搬过去，但要付出代价——\(A\cdot B\) 和 \(B\cdot A\) 可能差很多、能量的对称性几乎全丢、有些命题（如 \(nA-mA\) 控制）会直接失效。本节系统地交代“哪些活下来、为什么、以什么形式”。

2.7.1　乘法集合与积集

定义 2.37（乘法群、乘法集合）乘法群是指任意一个群 \(G\)（不必是阿贝尔的），带有群运算 \(\cdot\)、求逆运算 \(x\mapsto x^{-1}\) 以及单位元 \(1\)。一个乘法集合是一个对 \((A,G)\)，其中 \(G\) 是乘法群，\(A\) 是 \(G\) 的一个有限非空子集。我们常把乘法集合 \((A,G)\) 简记为 \(A\)，并称 \(G\) 为环绕群（ambient group）。

若 \(A\) 与 \(B\) 是共享同一环绕群 \(G\) 的乘法集合，我们定义它们的积集 \[A\cdot B:=\{ab:a\in A,\ b\in B\}\] 以及逆集 \[A^{-1}:=\{a^{-1}:a\in A\}.\]
例：把"加"换成"乘"在交换群（如整数加法）里，过去写 \(A+B=\{a+b\}\)。现在群运算记成乘法，于是 \(A\cdot B=\{ab\}\)。唯一真正新出现的麻烦是：\(ab\) 与 \(ba\) 可能不同。

取最小的非交换群——三元置换群 \(S_3\)。设 \(s=(1\,2)\)（交换 1、2），\(t=(2\,3)\)（交换 2、3）。直接复合：\(st=(1\,2\,3)\)，而 \(ts=(1\,3\,2)\)，二者不等。所以一旦群不交换，"先乘谁、后乘谁"就成了必须时刻盯着的事。

我们也照常对 \(x\in G\) 定义右平移 \(A\cdot x\) 与左平移 \(x\cdot A\)。注意一般地有 \(x\cdot A\neq A\cdot x\) 以及 \(A\cdot B\neq B\cdot A\)，不过我们仍然有 \[|A|=|x\cdot A|=|A\cdot x|=|A^{-1}|.\] 我们还定义迭代积集 \(A^{\cdot n}:=A\cdot\ldots\cdot A\)（\(n\) 个 \(A\)，\(n\ge 1\)），约定 \(A^{\cdot 0}:=\{1\}\) 以及 \(A^{\cdot -n}:=(A^{\cdot n})^{-1}=(A^{-1})^{\cdot n}\)。

为什么 \(|A\cdot x|=|A|\) 而 \(A\cdot B\) 却可能膨胀
  1. 用单个元素 \(x\) 去平移：映射 \(a\mapsto ax\) 是个一一对应（逆映射是 \(a'\mapsto a'x^{-1}\)），所以 \(A\) 里有几个元素，\(A\cdot x\) 里就有几个，个数不变。同理左平移、求逆都不改变个数。
  2. 但用一整个集合 \(B\) 去乘 \(A\)，不同的乘积 \(ab\) 可能撞在一起（碰撞），也可能全不相同，所以 \(|A\cdot B|\) 介于 \(\max(|A|,|B|)\) 与 \(|A||B|\) 之间——这正是"加倍/膨胀"现象的来源。

我们要提醒：\(A\cdot B\) 与 \(B\cdot A\) 的基数可能相差悬殊。例如设 \(H\) 是 \(G\) 的有限子群，\(x\) 是 \(G\) 中一个不落在 \(H\) 的正规化子 \[N(H):=\{x\in G:xH=Hx\}\] 里的元素，那么 \(H\cdot(x\cdot H)\) 与 \((x\cdot H)\cdot H\) 的基数可以非常不同。然而，我们仍然有 (2.1) 的类比： \[\max(|A|,|B|)\le |A\cdot B|,\ |B\cdot A|\le |A||B|;\] 见习题。

同样两块料 \(H\) 与 \(xH\)，左乘右乘大小天差地别 \(H\cdot(xH)\)：可大到 \(|H|^2\) 乘积几乎两两不同 → 几乎填满 \((xH)\cdot H\)：仅一个陪集 \(=|H|\) \(xH\cdot H=xH\)（\(H\) 是群，\(HH=H\)）
同一对集合，左乘 \(H\cdot(xH)\) 可膨胀到 \(|H|^2\)，右乘 \((xH)\cdot H\) 却只有 \(|H|\) 个。这是交换情形里绝不会发生的事，提醒我们：非交换世界里"次序"决定一切。

2.7.2　Ruzsa 距离与近似群

我们定义两个乘法集合之间的（左不变）Ruzsa 距离 \(d(A,B)\)： \[d(A,B):=\log\frac{|A\cdot B^{-1}|}{|A|^{1/2}|B|^{1/2}}.\] 这个距离仍然满足 Ruzsa 三角不等式，主要得益于恒等式 \((ab^{-1})(bc^{-1})=ac^{-1}\)。它在每个变量上都是左不变的，即 \[d(x\cdot A,B)=d(A,x\cdot B)=d(A,B),\] 并且是联合右不变的，\(d(A\cdot x,B\cdot x)=d(A,B)\)，但不是分别在各变量上右不变。此外它也不具有反射不变性；度量 \(d^*(A,B):=d(A^{-1},B^{-1})\) 是右不变的 Ruzsa 距离，我们这里不会用到它。

为什么那个恒等式撑起三角不等式三角不等式 \(d(A,C)\le d(A,B)+d(B,C)\) 的核心是要把 "\(A\cdot C^{-1}\) 不太大" 这件事，借道 \(B\) 拆开。关键观察：每个 \(ac^{-1}\) 都能写成 \[ac^{-1}=(ab^{-1})\cdot(bc^{-1}),\] 即先经过 \(A\cdot B^{-1}\) 再经过 \(B\cdot C^{-1}\)。注意这里 \(b^{-1}\) 与 \(b\) 在中间"相消"，次序排得严丝合缝——这正是为什么必须用 \(B^{-1}\) 而不是 \(B\) 来定义距离，也是为什么距离是左不变（左边乘 \(x\) 时 \(x\) 出现在 \(ac^{-1}\) 最前端，被 \(|\cdot|\) 吸收）而非右不变。

定义一个乘法 \(K\)-近似群为任意满足下列条件的乘法集合 \(H\)：它是对称的（即 \(H=H^{-1}\)），包含单位元，并且存在一个基数 \(|X|\le K\) 的集合 \(X\)，使得有如下包含关系 \[H\cdot H\subseteq X\cdot H\subseteq H\cdot X\cdot X;\qquad H\cdot H\subseteq H\cdot X\subseteq X\cdot X\cdot H.\]

"近似群"在说什么真正的群 \(H\) 满足 \(H\cdot H=H\)（乘起来不变大）。近似群是"差一点点的群"：\(H\cdot H\) 不一定等于 \(H\)，但能被少数几个（至多 \(K\) 个）\(H\) 的平移覆盖住——\(H\cdot H\subseteq X\cdot H\)。\(K=1\) 时就退化成真正的群。它是非交换世界里替代"小加倍集合"的标准结构对象。要求 \(H=H^{-1}\) 且 \(1\in H\)，是为了让它像群一样"封闭、对称、含单位"。

我们可以刻画 \(d(A,B)\) 何时为零：

命题 2.38设 \(A,B\) 是环绕群 \(G\) 中的乘法集合。则 \(d(A,B)=0\) 当且仅当 \(A\) 与 \(B\) 都是同一个有限子群 \(H\) 的左陪集，即对某 \(x,y\in G\) 有 \(A=x\cdot H\)，\(B=y\cdot H\)。

证明留作习题。注意 \(d(A,B)=0\) 并不一定蕴含 \(A\) 或 \(B\) 具有小加倍：若 \(x\) 或 \(y\) 落在 \(H\) 的正规化子之外，则 \(A^2\) 或 \(B^2\) 可以显著大于 \(A\) 或 \(B\)。类似地我们看到 \(d(A,B)=0\) 并不蕴含 \(d(A,B^{-1})=0\)。所以似乎不存在推论 2.12 的类比。然而，只要再小心一些、引入若干新论证，我们仍能得到第 2.4 与 2.5 节诸结果的类比。让我们从 Ruzsa 覆盖引理的类比开始，它可用相同的论证证明。

把这段"反常"讲透在交换情形里，距离为 0 基本意味着集合就是某个子群的平移、加倍很小。这里却出现两处"失灵"：
  1. 距离 0 不保证小加倍：\(A=xH\) 时 \(A\cdot B^{-1}=xH\cdot Hy^{-1}=xHy^{-1}\)，个数恰为 \(|H|\)，距离为 0；但 \(A\cdot A=xH\cdot xH=x(Hx)H\)，若 \(x\notin N(H)\) 则 \(Hx\neq xH\)，这块可大到 \(|H|^2\)。所以"贴得很近"与"自乘不膨胀"在非交换世界是两回事。
  2. \(d(A,B)=0\) 不给出 \(d(A,B^{-1})=0\)：因为求逆把左陪集 \(xH\) 变成右陪集 \(Hx^{-1}\)，左右陪集结构不再吻合。这正是交换情形推论 2.12 失效的根源。
应对之道：不再指望"距离 0 = 子群平移 = 小加倍"三者等价，而是改用三次积集 \(|A\cdot A\cdot A|\) 小这一更强的假设（见命题 2.40）。
引理 2.39（覆盖引理）设 \(A,B\) 是环绕群 \(G\) 中的乘法集合，满足 \(|A\cdot B|\le K|A|\)。则在 \(B\) 中存在一个基数至多为 \(K\) 的有限集 \(X\)，使得 \[B\subset A^{-1}\cdot A\cdot X.\]

2.7.3　为什么"三次积"是正确的假设

由第 2.4 节我们知道，若 \(A\) 是交换群 \(G\) 的子集且 \(|A+A|\le K|A|\)，则对任意 \(n,m\) 有 \(|nA-mA|\le O(K^{O(m+n)}|A|)\)。在非交换情形这不再成立。例如考虑 \(A:=H\cup\{x\}\)，其中 \(H\) 是 \(G\) 的子群，\(x\) 落在 \(H\) 的正规化子 \(N(H)\) 之外。那么 \[A\cdot A=H\cup(x\cdot H)\cup(H\cdot x)\cup\{x^2\},\] 所以 \(|A\cdot A|\le 3|A|-2\)；但 \(A\cdot A\cdot A\) 包含 \(H\cdot x\cdot H\)，后者可以大到 \(|H|^2=(|A|-1)^2\)。有趣的是，事实证明：如果我们改为假设 \(|A\cdot A\cdot A|\) 很小，则这个问题消失，于是能得到命题 2.26 的如下类比。

\(A=H\cup\{x\}\)：自乘一次温和，自乘两次爆炸 \(A\cdot A\)：\(\le 3|A|-2\)（小） \(H\) \(xH\) \(Hx\) \(\{x^2\}\) 四块拼起来 ≈ \(3|H|\)，仍是线性大小 \(A\cdot A\cdot A\supseteq H\cdot x\cdot H\)：可达 \(|H|^2\) \(hxh'\) 两两不同 → 平方级膨胀
反例 \(A=H\cup\{x\}\)（\(x\notin N(H)\)）：\(|A\cdot A|\) 只有线性大小，可是 \(A\cdot A\cdot A\) 里塞进了整块 \(HxH\)，大小蹿到 \(|A|^2\)。结论：在非交换世界，"\(A\cdot A\) 小"太弱，必须用"\(A\cdot A\cdot A\) 小"才能锁住结构。
命题 2.40设 \(A\) 是群 \(G\) 中的乘法集合，\(K\ge 1\)。则下述命题在相差常数的意义下等价，即：若第 \(j\) 条对某正绝对常数 \(C_j\) 成立，则第 \(k\) 条也对某依赖于 \(C_j\) 的绝对常数 \(C_k\) 成立：
  1. \(|A\cdot A\cdot A|\le K^{C_1}|A|\)；
  2. 对所有 \(n\ge 1\) 及所有符号 \(\varepsilon_1,\dots,\varepsilon_n\in\{-1,1\}\)，有 \(|A^{\varepsilon_1}\cdots A^{\varepsilon_n}|\le K^{C_2 n}|A|\)；
  3. 存在一个包含 \(A\) 的 \(K^{C_3}\)-近似群 \(H\)，且 \(|H|\le K^{C_3}|A|\)。
证明. 首先证明 (i) 蕴含 (ii)。假设 (i) 成立，则 \(|A\cdot A|\le|A\cdot A\cdot A|\le K^{C_1}|A|\)。由此 \(d(A,A^{-1})\)（它等于 \(d(A^{-1},A)\)）以及 \(d(A\cdot A,A^{-1})\) 都是 \(O(\log K)\)。由三角不等式 \(d(A\cdot A,A)=O(\log K)\)，这给出 \(|A\cdot A\cdot A^{-1}|\le K^{O(1)}|A|\) 以及 \(d(A,A\cdot A^{-1})=O(\log K)\)。再用三角不等式，得 \(d(A\cdot A^{-1},A^{-1})=O(\log K)\)，从而 \(|A\cdot A^{-1}\cdot A|\le K^{O(1)}|A|\)。用类似论证可证 \(|A^{-1}\cdot A\cdot A|\le K^{O(1)}|A|\)。有了这些界（并取逆），我们就得到了 (ii) 在 \(n=3\) 时的陈述。由此出发，对 \(n\) 作归纳即可轻松完成证明，\(n=3\) 是归纳基础。（\(n=2\) 时，(ii) 的陈述是平凡的。）

其次，我们证明 (ii) 蕴含 (iii)。令 \(H':=A\cup\{1\}\cup A^{-1}\)，\(H:=H'\cdot H'\cdot H'\)。显然 \(H\) 是对称的且包含 \(A\)。由 (ii)，\(|H|\le K^{O(1)}|A|\)。于是只剩下证明 \(H\) 是一个 \(K^{O(1)}\)-近似群。注意 \(|H'\cdot H\cdot H'|\le K^{O(1)}|A|\)（因 \(H=H'\cdot H'\cdot H'\)，故 \(H'\cdot H\cdot H'=(H')^5\)，按 (ii)，这至多是五个 \(A^{\pm 1}\) 相乘）。由覆盖引理，在 \(H\cdot H\) 中存在一个基数为 \(K^{O(1)}\) 的集合 \(Y\)，使得 \[H\cdot H\subset H^{-1}\cdot H'\cdot Y.\] 注意右端是 \(H\cdot Y\) 的子集。现令 \(X=Y\cup Y^{-1}\)。由于 \(H\) 与 \(X\) 都对称，\(H\cdot H\) 同时含于 \(H\cdot X\) 与 \(X\cdot H\) 之中。再者，由于 \(X\subset H\cdot H\)， \[H\cdot X\subset H\cdot H\cdot H\subset X\cdot H\cdot H\subset X\cdot X\cdot H,\] 证毕。

其余的蕴含关系是直接的，留作习题。♦
这条命题在讲什么直觉三句话其实是从三个角度说"同一件事——\(A\) 几乎是个群"：
  1. (i) 三次自乘不膨胀——最易验证的"小加倍"判据（且如上所述，用三次而非两次才稳）。
  2. (ii) 任意长、任意带逆的乘积都只线性增长——最强的"封闭性"描述。关键技巧：所有这些复杂乘积的大小，都能用 Ruzsa 三角不等式从 \(n=3\) 的几个基本量"传播"出去，再对长度归纳。
  3. (iii) 能被一个不大的近似群 \(H\) 装住——最有用的"结构对象"。构造极朴素：把 \(A\)、单位元、\(A^{-1}\) 并起来记作 \(H'\)，再令 \(H=H'^{\,3}\)，它自动对称、含 \(A\)，由 (ii) 不太大，最后用覆盖引理把 \(H\cdot H\) 压进少数几个 \(H\) 的平移里，验证近似群定义。

现在我们要证明：在"存在某集合 \(B\) 使 \(d(A,B)=O(\log K)\)"的假设下，仍能得到 (iii)。我们将需要引理 2.13 的如下变体，其证明留作习题。

引理 2.41设 \(A\) 是乘法集合。则存在一个对称集 \(S\subset A^{-1}\cdot A\)，满足 \(|S|\ge|A|/2\)，且对所有整数 \(n\ge 0\) 有 \[|A\cdot S^{\cdot n}\cdot A^{-1}|\le\frac{2^n\,|A\cdot A^{-1}|^{n+1}\,|A^{-1}\cdot A|^{n}}{|A|^{2n}}.\]

由于 \(d(A,A)\le 2d(A,B)\)，这蕴含

推论 2.42设 \(A\) 是乘法集合，对某 \(K\ge 1\) 满足 \(d(A,B)\le\log K\)。则存在一个对称集 \(S\)，满足 \(|S|\ge(K^{-O(1)}|A|)\)，且对所有整数 \(n\ge 0\) 有 \[|A\cdot S^{\cdot n}\cdot A^{-1}|\le O(K)^{O(1+n)}|A|.\]
命题 2.43设 \(A,B\) 是群 \(G\) 中的乘法集合，\(K\ge 1\)。则下述命题在相差常数的意义下等价（含义同前：若第 \(j\) 条对某绝对常数 \(C_j\) 成立，则第 \(k\) 条也对某依赖于 \(C_j\) 的绝对常数 \(C_k\) 成立）：
  1. \(d(A,B)\le C_1(1+\log K)\)；
  2. 存在一个 \(C_2 K^{C_2}\)-近似群 \(H\)，满足 \(|H|\le C_2 K^{C_2}|A|\)，且对某些基数至多 \(C_2 K^{C_2}\) 的乘法集合 \(X,Y\) 有 \(A\subset X\cdot H\) 与 \(B\subset Y\cdot H\)。
证明. 我们只需证明 (i) 蕴含 (ii)，因为反方向是平凡的。注意 (i) 蕴含 \(d(A,A)=O(\log K)\)。于是我们有一个基数为 \(K^{O(1)}|A|\) 的对称集 \(S\)，满足 \[|A\cdot S^{\cdot 3}\cdot A^{-1}|\le K^{O(1)}|A|.\] 这蕴含 \(|A\cdot S|\le K^{O(1)}|A|\)，从而 \(d(A,S)=O(\log K)\)。此外，\(|S^3|\le K^{O(1)}|S|\)，所以我们能找到一个含 \(S\) 的、大小为 \(K^{O(1)}|A|\) 的 \(O(K^{O(1)})\)-近似群 \(H\)。这尤其蕴含 \(d(S,H^{-1})=O(\log K)\)。由三角不等式 \(d(A,H^{-1})=O(\log K)\)，由此 \(|A\cdot H|\le K^{O(1)}|A|\)。由覆盖引理，存在一个基数 \(K^{O(1)}\) 的集合 \(Y\) 使得 \(A\subset Y\cdot H\cdot H^{-1}\)。但由于 \(H\) 是近似群，\(H^{-1}=H\)，且 \(H\cdot H\subset Z\cdot H\) 对某大小 \(K^{O(1)}\) 的集合 \(Z\) 成立。于是 \(A\subset(Y\cdot Z)\cdot H\)，其中 \(|Y\cdot Z|\le|Y||Z|=K^{O(1)}\)。关于 \(B\) 的结论可类似地证明。♦
命题 2.43 的脉络它把命题 2.40 升级成"两个集合之间距离小"的版本：只要 \(A\)、\(B\) 离得近，它们就能被同一个近似群 \(H\) 的少数平移同时覆盖。证明链条是一串三角不等式的接力："\(A\) 离 \(B\) 近 ⟹ \(A\) 离自己近 ⟹ 由引理造出对称集 \(S\) ⟹ \(S\) 三次积小、能装进近似群 \(H\) ⟹ \(A\) 离 \(H\) 近 ⟹ 用覆盖引理把 \(A\) 压进 \(H\) 的少量平移"。每一步都在搬运同一句话：膨胀受 \(K\) 的多项式控制。

2.7.4　Balog–Szemerédi–Gowers 定理与乘法能量

现在我们来考虑 Balog–Szemerédi–Gowers 定理的非交换版本。当环绕群 \(Z\) 非交换时，定理 2.29 仍然成立。该定理的证明纯粹是图论的（见第 6.4 节），与群的交换性几乎无关。

定理 2.44（Balog–Szemerédi–Gowers 定理，非交换版本）设 \(A,B\) 是环绕群 \(Z\) 中的乘法集合，\(G\subseteq A\times B\) 满足 \[|G|\ge|A||B|/K\quad\text{且}\quad |A\overset{G}{\cdot}B|\le K'|A|^{1/2}|B|^{1/2}\] 对某 \(K\ge 1\) 与 \(K'>0\) 成立。则存在子集 \(A'\subseteq A\)，\(B'\subseteq B\)，使得 \[|A'|\ge\frac{|A|}{4\sqrt{2}K}\tag{2.37}\] \[|B'|\ge\frac{|B|}{4K}\tag{2.38}\] \[|A'\cdot B'|\le 2^{12}K^4(K')^3|A|^{1/2}|B|^{1/2}.\tag{2.39}\] 特别地我们有 \[d(A',B'^{-1})\le 5\log K+3\log K'+O(1).\]
这里的记号 \(|A\overset{G}{\cdot}B|\) 与定理的意思部分积集 \(A\overset{G}{\cdot}B:=\{ab:(a,b)\in G\}\) 只统计被"图 \(G\)"挑中的那些乘积对。定理在说：哪怕只有一部分乘积对（占比 \(\ge 1/K\)）表现良好（部分积集小），也能提纯出仍占大比例的子集 \(A',B'\)，使它们的整个积集 \(A'\cdot B'\) 都小。一句话：局部的好行为可以升级为整体的好行为。证明是图论的，所以群交不交换无所谓。

定义共享同一环绕群的两个乘法集合 \(A,B\) 之间的乘法能量 \(E(A,B)\) 为 \[E(A,B):=\big|\{(a,a',b,b')\in A\times A\times B\times B:ab=a'b'\}\big|.\tag{2.40}\] 这里一个重大困难是：在非交换情形下，\(E(A,B)\) 所满足的对称性远少于交换情形；事实上，唯一可用的对称性是 \(E(A,B)=E(B^{-1},A^{-1})\)。然而，在 \(B=A^{-1}\) 这一情形下，我们有一个关键的额外恒等式 \(E(A,A^{-1})=E(A^{-1},A)\)（见习题），它可被视作一种非常弱的、受限的交换性。

交换情形丢了哪些对称性在交换群里能量定义为四元组 \(a+b=a'+b'\)，等价于 \(a-a'=b'-b\)，于是可以随意交换 \(a\leftrightarrow b\)、\(a\leftrightarrow a'\) 等，对称性极多，许多估计因此唾手可得。非交换时 \(ab=a'b'\) 不能改写成"差相等"那种对称形式，能交换的只剩 \(E(A,B)=E(B^{-1},A^{-1})\) 这一条（把等式两边同时取逆：\(b^{-1}a^{-1}=b'^{-1}a'^{-1}\)）。唯独当 \(B=A^{-1}\) 时多出一条 \(E(A,A^{-1})=E(A^{-1},A)\)，这点"残存的交换性"恰好够把后面的推论 2.47 推出来。
引理 2.45设 \(A,B\) 是环绕群 \(Z\) 中的乘法集合，\(G\) 是 \(A\times B\) 的非空子集。则 \[E(A,B)\ge\frac{|G|^2}{|A\overset{G}{\cdot}B|}.\] 反之，若对某 \(K\ge 1\) 有 \(E(A,B)\ge|A|^{3/2}|B|^{3/2}/K\)，则存在 \(G\subseteq A\times B\) 使得 \[|G|\ge|A||B|/2K;\qquad |A\overset{G}{\cdot}B|\le 2K|A|^{1/2}|B|^{1/2}.\]
能量 = 大量"乘积相等"的四元组 ⟺ 存在稠密的好图 \(G\) \(A\) \(B\) 每条边 \((a,b)\in G\) 给出一个乘积 \(ab\)；边多而乘积值少 ⟹ 必有大量碰撞 \(ab=a'b'\) ⟹ 能量大
引理 2.45 是能量与"好图"之间的双向翻译：边数 \(|G|\) 大、落点 \(|A\overset{G}{\cdot}B|\) 少，按鸽笼原理必然制造大量相等乘积，即能量大；反之能量大也能反提取出这样一张稠密的好图。这正是把 BSG 定理接到能量上的桥。

最后，注意由三角不等式 \[d(A',A')\le d(A',B'^{-1})+d(B'^{-1},A')=2d(A',B'^{-1}),\] 这意味着若 \(d(A',B'^{-1})\) 小，则 \(d(A',A')\) 也小。由此出发，我们可以用与交换情形相同的论证来推出

推论 2.46设 \(A,B\) 是环绕群 \(Z\) 中的乘法集合，对某 \(K>1\) 满足 \(E(A,B)\ge|A|^{3/2}|B|^{3/2}/K\)。则存在子集 \(A'\subset A\)，使得 \(|A'|=(K^{-O(1)}|A|)\) 且 \(|A'\cdot(A')^{-1}|=O(K^{O(1)}|A|)\)（对某绝对常数 \(C\)）。

把它与恒等式 \(E(A,A^{-1})=E(A^{-1},A)\) 结合，我们得到 \(A\) 与 \(A^{-1}\) 之间如下的弱交换性质：

推论 2.47设 \(A\) 是乘法集合，对某 \(K\ge 1\) 满足 \(|A\cdot A|\le K|A|\)。则存在子集 \(A'\subset A\)，使得 \(|A'|=(K^{-O(1)}|A|)\) 且 \(|A'\cdot(A')^{-1}|=O(K^{O(1)}|A|)\)。

现在不难得到下面的定理。

定理 2.48设 \(A,B\) 是群 \(G\) 中的乘法集合，\(K\ge 1\)。则下述命题在相差常数的意义下等价（含义同前）：
  1. \(E(A,B)\ge C_1^{-1}K^{-C_1}|A|^{3/2}|B|^{3/2}\)；
  2. 存在子集 \(G\subset A\cdot B\)，满足 \(|G|\ge C_2^{-1}K^{-C_2}|A||B|\)，且 \(|A\overset{G}{\cdot}B|\le C_2 K^{C_2}|A|^{1/2}|B|^{1/2}\)；
  3. 存在一个 \(C_3 K^{C_3}\)-近似群 \(H\) 以及 \(x,y\in G\)，满足 \(|H|\le C_3 K^{C_3}|A|^{1/2}|B|^{1/2}\)，且 \(|A\cap(x\cdot H)|,\ |B\cap(H\cdot y)|\ge C_3^{-1}K^{-C_3}|H|\)。

这些陈述的证明留作习题。尽管有了这些刻画，关于非交换群中积集的研究仍有大量工作有待完成。例如，目前我们还没有一个令人满意的、一般情形下的 Freiman 定理版本。然而，在加倍非常小的情形 [172] 以及某些特殊群（如 \(SL_2(\mathbb{Z})\) 或自由群）中已有一些进展；参见例如 [78]、[182]。

本节地图：交换 vs 非交换对照
  1. 能搬过去的：Ruzsa 距离与三角不等式、覆盖引理、Balog–Szemerédi–Gowers 定理（图论证明，与交换性无关）、以及"小加倍 ⟺ 装进近似群 ⟺ 高能量"这一组等价刻画（命题 2.40、2.43，定理 2.48）。
  2. 必须付代价：要用三次积 \(A\cdot A\cdot A\) 小代替两次积小；能量几乎丢光对称性；距离 0 不再等于小加倍。
  3. 彻底失效的：\(nA-mA\) 型控制（反例 \(H\cup\{x\}\)）；推论 2.12 的反射类比；以及一般的 Freiman 定理。
一句话总结：非交换世界里"小加倍集合 ≈ 近似群"这个核心信念依然成立，但通往它的每条路都要对乘法次序格外当心。

习题

习题 2.7
  1. 2.7.1　证明引理 2.1 的乘法版本。
  2. 2.7.2　证明引理 2.6 的乘法版本。
  3. 2.7.3　证明命题 2.38。
  4. 2.7.4　设 \((A,G)\) 是乘法集合。证明：\(|A\cdot A|=|A|\) 当且仅当 \(A\) 是 \(H\) 的一个正规陪集，即对某 \(x\in N(H)\) 有 \(A=x\cdot H=H\cdot x\)。
  5. 2.7.5　设 \(A\) 是对称乘法集合，即 \(A=A^{-1}\)，并以 \(\sigma_n[A]\) 记 \(n\) 重加倍数 \(|A^n|/|A|\)。利用 Ruzsa 三角不等式，证明对所有 \(m,n\ge 2\) 有 \(\sigma_{m+n-2}[A]\le\sigma_m[A]\sigma_n[A]\)。
  6. 2.7.6　设 \(A,B\) 是乘法集合。建立恒等式 \(E(A,B)=E(B^{-1},A^{-1})\) 与 \(E(A,A^{-1})=E(A^{-1},A)\)，以及不等式 \(E(A,B)\ge\dfrac{|A|^2|B|^2}{|A\cdot B|}\)。
  7. 2.7.7　设 \(A,B,C\) 是环绕群 \(Z\) 中的加法集合，\(0<\varepsilon<1/4\)，且 \(G\subset A\times B^{-1}\)，\(H\subset B\times C^{-1}\) 满足 \(|G|\ge(1-\varepsilon)|A||B|\) 与 \(|H|\ge(1-\varepsilon)|B||C|\)。通过修改习题 2.5.4 的解，证明存在子集 \(A'\subseteq A\) 与 \(C'\subseteq C\)，满足 \(|A'|\ge(1-\varepsilon^{1/2})|A|\) 与 \(|C'|\ge(1-\varepsilon^{1/2})|C|\)，使得 \(|A'\cdot(C')^{-1}|\le\dfrac{|A\overset{G}{\cdot}B^{-1}|\,|B\overset{H}{\cdot}C^{-1}|}{(1-2\varepsilon^{1/2})|B|}\)。
  8. 2.7.8　设 \(A\) 是乘法集合，满足 \(|A\cdot A^{-1}|\le K|A|\) 与 \(|A^{-1}\cdot A|\le K|A|\)。证明存在 \(A\) 的子集 \(\tilde A\)，满足 \(|\tilde A|\ge|A|/2K\) 且对所有 \(n\ge 2\) 有 \[|\tilde A\cdot\tilde A^{-1}\cdot\ldots\cdot\tilde A^{(-1)^{n+1}}|\le 2^{n-2}K^{2n-3}|A|,\] 其中乘积由 \(n\) 个在 \(\tilde A\) 与 \(\tilde A^{-1}\) 之间交替的因子组成。
  9. 2.7.9　若 \(A,B\) 是群 \(G\) 中的乘法集合，证明存在集合 \(X_1,X_2\subseteq A\)，满足 \(|X_1|\le\dfrac{|A\cdot B|}{|B|}\)，\(|X_2|\le\dfrac{|B\cdot A|}{|B|}\)，且 \(A\subseteq X_1\cdot B\cdot B^{-1}\) 与 \(A\subseteq B^{-1}\cdot B\cdot X_2\)，方法是修改引理 2.14 的证明。
  10. 2.7.10　证明引理 2.41。
  11. 2.7.11　证明命题 2.18 的直接类比在非交换情形下失效，即使在 \(A=B=A^{-1}\) 时也是如此。
  12. 2.7.12　设 \(A,B\) 是环绕群 \(G\) 中的乘法集合，令 \(\tilde A\) 为集合 \[\tilde A:=\Big\{a\in A:\big|\{(a',b,b')\in A\times B\times B:a=a'b'b^{-1}\}\big|\ge\frac{|A||B|^2}{2|A\cdot B|}\Big\}.\] 建立界 \(|\tilde A|\ge\dfrac{|A|^2}{2|A\cdot B|}\)。

返回 全书目录