Tao–Vu · 加性组合学 · 第 5 章 逆和集定理

5.3　Freiman 同态Freiman homomorphisms

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

本节目标普通的“群同态”要求映射保持整个加法运算，太严格了。我们想要一种更宽松的对应方式：只要它能把关于和与差的信息原封不动地搬到另一个群里就行。这种对应叫 Freiman 同态。本节给出它的定义、大量例子，并证明它确实能保持“和集、差集的大小”等加性组合学最关心的量；最后证明两件大事：无挠群里的有限集本质上不比整数集更复杂（引理 5.25），以及任何加性集都能被压缩进一个只比它本身大一点点的循环群里（引理 5.26）。

现在我们引入一个基本概念——Freiman 同态。它使我们能够把一个群 \(Z\) 中的某个加性问题，以一种比通常的代数“群同态”更灵活的方式，搬运到另一个群 \(Z'\) 中去。粗略地说，Freiman 同态之于加性集，正如群同态之于加性群。为避免混淆，我们常把加性集 \(A\) 更完整地写作 \((A,Z)\)，其中 \(Z\) 是 \(A\) 所处的环境群（ambient group）。

定义 5.21（Freiman 同态）设 \(k\ge 1\)，又设 \(A,B\) 是加性集，其环境群分别为 \(Z\) 与 \(W\)。一个从 \((A,Z)\) 到 \((B,W)\)（更简洁地说，从 \(A\) 到 \(B\)）的 \(k\) 阶 Freiman 同态 \(\varphi\) 是一个映射 \(\varphi:A\to B\)，满足 \[a_1+\cdots+a_k=a_1'+\cdots+a_k'\ \Longrightarrow\ \varphi(a_1)+\cdots+\varphi(a_k)=\varphi(a_1')+\cdots+\varphi(a_k')\] 对一切 \(a_1,\dots,a_k,a_1',\dots,a_k'\in A\) 成立。如果此外还存在一个逆映射 \(\varphi^{-1}:B\to A\)，它是一个从 \((B,W)\) 到 \((A,Z)\) 的 \(k\) 阶 Freiman 同态，那么我们称 \(\varphi\) 为 \(k\) 阶 Freiman 同构，并称 \((A,Z)\) 与 \((B,W)\) 是 \(k\) 阶 Freiman 同构的。

关于 Freiman 同构的一个等价刻画，见习题 5.3.1。

把定义读懂

定义只盯住一件事：“\(k\) 个元素相加得到的和”是否相等。它说：原来在 \(A\) 里凑出相同和的两组元素，搬到 \(B\) 里以后，对应的像仍然凑出相同的和。它不要求 \(\varphi(a+a')=\varphi(a)+\varphi(a')\)（那是群同态），它甚至不要求 \(a+a'\) 还在 \(A\) 里。

用最小的例子（\(k=2\)）看：若 \(A\) 中有 \(a_1+a_2=a_1'+a_2'\)，则像必须满足 \(\varphi(a_1)+\varphi(a_2)=\varphi(a_1')+\varphi(a_2')\)。下图就是一个“相等的和”被同态保持的画面。

A（在 Z 中） B（在 W 中） a₁ + a₂ ‖ a₁′ + a₂′ φ(a₁)+φ(a₂) ‖ φ(a₁′)+φ(a₂′) φ
“左边相等”被搬运为“右边相等”——这就是 Freiman 同态的全部承诺。

容易验证，一个 \(k\) 阶 Freiman 同态同时也是所有更低阶 \(k'等价关系。于是，所有加性集连同它们之间固定阶数 \(k\) 的 Freiman 同态，构成一个范畴（category）。

为什么“高阶蕴含低阶”
  1. 设 \(\varphi\) 是 \(k\) 阶同态，要证它也是 \(k-1\) 阶同态。
  2. 取 \(A\) 中任一元素 \(a_0\)。若 \(a_1+\cdots+a_{k-1}=a_1'+\cdots+a_{k-1}'\)，两边各添上同一个 \(a_0\)，得到 \(a_1+\cdots+a_{k-1}+a_0=a_1'+\cdots+a_{k-1}'+a_0\)，这是 \(k\) 项的等式。
  3. 用 \(k\) 阶同态性质得 \(\varphi(a_1)+\cdots+\varphi(a_{k-1})+\varphi(a_0)=\varphi(a_1')+\cdots+\varphi(a_{k-1}')+\varphi(a_0)\)。
  4. 两边消去公共的 \(\varphi(a_0)\)，正好得到 \(k-1\) 阶所需的结论。所以阶数越高，限制越强。
注记 5.22我们岔开话题，给出一个与流形微分几何的类比。流形既可以从外在角度看待（嵌入到某个环境空间——例如欧氏空间 \(\mathbb{R}^d\)——之中），也可以从内在角度看待（作为一个赋予了某些结构，如拓扑、黎曼度量等的集合）。从前一种观点过渡到后一种很容易：只要把环境空间上的某些结构限制到嵌入的子集上即可；而要把这个过程反过来——把一个内在流形嵌入到给定的环境空间中——往往要难得多。在本书中我们一直采取外在的做法，把加性集 \(A\) 嵌入到一个环境群 \(Z\) 之中。然而我们也可以采取纯内在的观点：固定 Freiman 同态的阶数 \(k\)，把加性集看作 \((A,\sim_k)\)，其中 \(A\) 现在被视为一个抽象集合（而非某个加性群的子集），而 \(\sim_k\) 是定义在 \(A^k\) 上的等价关系——（外在地）规定 \((a_1,\dots,a_k)\sim_k(a_1',\dots,a_k')\) 当且仅当 \(a_1+\cdots+a_k=a_1'+\cdots+a_k'\)。这已足以发展 Freiman 同态与同构的理论，并且可以在这种内在框架下定义诸如和集、加性能量等概念。不过这种做法似乎没有什么重大优势，尤其因为这里的嵌入问题相对容易解决（与黎曼流形的情形形成对照）。见下面的习题 5.5.6。

Freiman 同态的例子

现在我们给出一些 Freiman 同态的例子。

例：为什么商映射 \(\psi\) 要 \(M\ge kN\) 才同构

取 \(N=4\)，\(M=5\)，\(k=2\)。\(\psi\) 把 \([0,4)=\{0,1,2,3\}\) 送进 \(\mathbb{Z}_5\)，即对 \(5\) 取余。\(2\) 阶同构要求“两元素之和的等同关系完全一致”。在 \(\mathbb{Z}_5\) 中可能发生“折回”：\(3+3=6\equiv 1\pmod 5\)，而在整数里 \(3+3=6\ne1\)。要让这种折回不影响 \(\{0,1,2,3\}\) 里任意两元素之和（最大为 \(3+3=6\)），就要求模数 \(M\) 大到容得下这些和。两元素之和最多是 \((N-1)+(N-1)=2(N-1)<2N=kN\)，所以条件 \(M\ge kN\) 恰好保证 \(\{0,\dots,2N-2\}\) 内不发生折回，加法在取余前后“看起来一样”。

0 1 2 3 A=[0,4) 的元素 4 5 6 和最大到 6 = 3+3 若 M=5，则 6 折回到 1，破坏“和相等”的一致性
只要模数 \(M\ge kN\)，所有阶为 \(k\) 的和都落在 \([0,M)\) 内、不折回，取余前后判断“和是否相等”结果一致，故为 \(k\) 阶同构。
例：\(\{0,1,10,11\}\) 与 \(\{0,1,100,101\}\) 为何在 \(k=10\) 处“断裂”

这两个集合都长得像“二维方格 \(\{0,1\}\times\{0,1\}\) 的数字编码”：前者以 \(10\) 为进位基，后者以 \(100\) 为进位基。对应 \(\varphi:0\mapsto0,\;1\mapsto1,\;10\mapsto100,\;11\mapsto101\)。只要 \(k\) 个元素相加时各位不进位，两边的“和相等”关系就完全一致。第一个集合用基 \(10\)，要做 \(k\) 个元素相加而不在个位/十位进位，需要 \(k<10\)。一旦 \(k\ge 10\)，比如 \(k=10\)：在第一个集合里 \(\underbrace{1+\cdots+1}_{10}=10\)，恰好等于元素 \(10\)；但在第二个集合里 \(\underbrace{1+\cdots+1}_{10}=10\ne100\)。于是“和相等”的关系对不上，同构在 \(k=10\) 处断裂。

Freiman 同态与和集理论的关联

Freiman 同态与和集理论的关联在于下面的引理：

引理 5.23设 \((A,G)\) 为加性集，又设 \(\varphi:(A,G)\to(\varphi(A),H)\) 为一个满的 \(k\) 阶 Freiman 同态。那么对 \(A\) 的任意非空子集 \(A_1,\dots,A_k\) 以及 \(\varepsilon_1,\dots,\varepsilon_k=\pm 1\)，有 \[|\varepsilon_1\varphi(A_1)+\cdots+\varepsilon_k\varphi(A_k)|\le|\varepsilon_1 A_1+\cdots+\varepsilon_k A_k|.\] 如果 \(\varphi\) 实际上是 \(k\) 阶 Freiman 同构，那么不等号可以换成等号。特别地，若 \(A\) 与 \(B\) 是 \(k\) 阶 Freiman 同构的，则只要 \(l,m\ge 0\) 且 \(l+m\le k\)，就有 \[|lB-mB|=|lA-mA|.\]
证明. 在 \(A_1\times\cdots\times A_k\) 上定义等价关系 \(\sim\)： \[(a_1,\dots,a_k)\sim(a_1',\dots,a_k')\iff \varepsilon_1 a_1+\cdots+\varepsilon_k a_k=\varepsilon_1 a_1'+\cdots+\varepsilon_k a_k'.\] 注意 \(A_1\times\cdots\times A_k\) 中等价类的个数恰好是 \(|\varepsilon_1 A_1+\cdots+\varepsilon_k A_k|\)。再注意，上述条件 \[\varepsilon_1 a_1+\cdots+\varepsilon_k a_k=\varepsilon_1 a_1'+\cdots+\varepsilon_k a_k'\] 可以改写成正向的形式（把带负号的项移到等号另一侧）： \[\sum_{j:\varepsilon_j=1}a_j+\sum_{j:\varepsilon_j=-1}a_j'=\sum_{j:\varepsilon_j=1}a_j'+\sum_{j:\varepsilon_j=-1}a_j.\] 由此可见，这个等价关系被任何 \(k\) 阶 Freiman 同态所尊重（即等价的元组在 \(\varphi\) 下仍映到等价的元组）。把这些观察合在一起即得引理。♦
把证明的逻辑摊开
  1. 关键翻译：和集的大小 = 等价类的个数。集合 \(\varepsilon_1 A_1+\cdots+\varepsilon_k A_k\) 里的每个元素，是某个“带符号的和”\(s=\varepsilon_1 a_1+\cdots+\varepsilon_k a_k\)。把所有产生同一个 \(s\) 的元组 \((a_1,\dots,a_k)\) 归为一类，那么不同的 \(s\) 一一对应不同的类，所以类的个数就是和集的元素个数。
  2. 同态只会“合并”，不会“拆分”。若两个元组在 \(A\) 里同类（和相等），定义 5.21 保证它们的像在 \(B\) 里也同类。于是 \(B\) 那边的类数 \(\le\) \(A\) 这边的类数（原本就同类的，过去还是同类；原本不同类的，过去可能撞成同类）。类数即和集大小，故 \(|\cdots\varphi(A_i)\cdots|\le|\cdots A_i\cdots|\)。
  3. 同构时两个方向都成立，故相等。同构意味着 \(\varphi^{-1}\) 也是同态，于是反方向也有 \(\le\)，两者夹出等号。
  4. 正向改写为什么必要。定义 5.21 里的蕴含写的是“纯加法”的等式 \(a_1+\cdots+a_k=\cdots\)，而带符号的和里有减号。把减号项搬到对面变加号后，左右两侧都成了 \(k\) 项纯加法和，正好套进定义 5.21，蕴含才用得上。

因此，Freiman 同构会保持迭代和集与差集的基数（以及诸如倍增常数、差常数、能量等相关量）；见习题 5.3.5。当然，在许多应用中，人们想取的是环境群 \(Z\) 中两个加性集 \(A,B\)（而非一个）的和集。解决办法之一是处理它们的并集 \(A\cup B\)，因为引理 5.23 表明 \(A\cup B\) 的 Freiman 同构将保持诸如 \(A+B\) 或 \(A-B\) 这类集合的基数（只要同构的阶至少为 \(2\)）。但这有一个小缺点：人们失去了独立平移 \(A\) 与 \(B\) 的自由。绕开它的一个办法是定义 \(A\) 与 \(B\) 的不交并 \(A\sqcup B\)，它定义在环境群 \(Z\times Z\) 中为 \[A\sqcup B:=(A\times\{0\})\cup(B\times\{1\}).\] 这样，不交并的任何 Freiman 同构都将保持和集（见习题 5.3.7）。注意，从 \(A\sqcup B\) 到 \(A\cup B\) 的显然投影映射是任意阶的 Freiman 同态。

普通并集 A∪B（同一层，会粘连） A 与 B 的点重合，无法分辨来源 不交并 A⊔B（分两层，永不粘连） 层 0 层 1 A 放层 0，B 放层 1，可独立平移
不交并用第二个坐标（\(0\) 或 \(1\)）给两集合贴上“出身标签”，于是即便数值相同也不会混淆，从而保留独立平移 \(A,B\) 的自由。

Freiman 同态保持“数列”结构

Freiman 同态还保持“成为一个广义等差数列”的性质：

命题 5.24设 \(\varphi:A\to B\) 为阶至少为 \(2\) 的 Freiman 同态，又设 \(P=a+[0,N]\cdot v\) 为 \(A\) 中的一个广义等差数列（progression）。那么 \(\varphi(P)\) 是 \(B\) 中的一个广义等差数列，且与 \(P\) 具有相同的秩、维数和体积。此外，若 \(\varphi\) 实际上是阶至少为 \(2\) 的 Freiman 同构，则 \(\varphi(P)\) 为真（proper）当且仅当 \(P\) 为真。
证明. 我们可以假设 \(N\) 的各个分量 \(N_j\) 都严格为正，因为如果某个分量 \(N_j\) 为零，我们只需把它去掉并把秩降低 \(1\)。由平移不变性，可设基点 \(a\) 等于 \(0\)，且 \(\varphi(0)\) 也为零。特别地，\(P\)（从而 \(A\)）包含所有的基向量 \(v_1,\dots,v_d\)。 由于 \(\varphi\) 是 \(2\) 阶 Freiman 同态且 \(\varphi(0)=0\)，我们看到：只要 \(x\) 与 \(x+v_j\) 都落在 \(A\) 中且 \(1\le j\le d\)，就有 \(\varphi(x+v_j)=\varphi(x)+\varphi(v_j)\)。反复迭代，由归纳法可知对任意 \(n\in[0,N]\) 有 \(\varphi(n\cdot v)=n\cdot\varphi(v)\)，其中 \(\varphi(v)\in B^{\oplus d}\) 是 \(d\) 元组 \(\varphi(v):=(\varphi(v_1),\dots,\varphi(v_d))\)。于是 \(\varphi(P)=[0,N]\cdot\varphi(v)\)，从而是一个与 \(P\) 具有相同秩、维数与体积的广义等差数列。为证命题的最后一部分，注意若 \(\varphi\) 是 Freiman 同构，则 \(|P|=|\varphi(P)|\)，因而 \(|P|=|[0,N]|\) 当且仅当 \(|\varphi(P)|=|[0,N]|\)（即两者同时为真）。♦
为什么 \(\varphi(0)=0\) 时 \(2\) 阶同态就能“拆开加法”

设 \(x\) 与 \(x+v_j\) 都在 \(A\) 中。考虑整数等式 \[(x+v_j)+0=x+v_j,\] 左边是 \(A\) 中两元素 \((x+v_j)\) 与 \(0\) 之和，右边是 \(A\) 中两元素 \(x\) 与 \(v_j\) 之和（这里要用到 \(0,v_j\in A\)）。两边都是 \(2\) 项和且相等，套用 \(2\) 阶同态： \[\varphi(x+v_j)+\varphi(0)=\varphi(x)+\varphi(v_j).\] 因 \(\varphi(0)=0\)，得 \(\varphi(x+v_j)=\varphi(x)+\varphi(v_j)\)。这就是“沿一根坐标方向走一步，像也正好走一步”。把它沿每个方向、走 \(N_j\) 步逐步拼起来，整条数列 \(P\) 的格状结构就被完整搬到 \(\varphi(P)\)。

P = 0 + [0,2]·(v₁,v₂) φ φ(P) = 0 + [0,2]·φ(v)，同样 3×3 的格
秩（坐标方向数）、维数（各方向步数 \(N_j\)）、体积（格点总数）全部不变；同构时还保证“无重叠 = 真”这一性质也对应过去。

无挠群本质上不比整数复杂

下面我们要说明：就理解有限集的和与差而言，无挠加性群并不比整数集更丰富。

引理 5.25设 \(A\) 为无挠加性群 \(Z\) 的有限子集。那么对任意整数 \(k\)，都存在一个 \(k\) 阶 Freiman 同构 \(\varphi:A\to\varphi(A)\)，把 \(A\) 映到整数集 \(\mathbb{Z}\) 的某个有限子集 \(\varphi(A)\)。如果把 \(\mathbb{Z}\) 换成 \(\mathbb{Z}_N\)（只要 \(N\) 充分大，依赖于 \(A\)），结论同样成立。

注意，逆命题是平凡的：我们总能把整数集嵌入任何别的无挠加性群中，从而整数集中的任何加性集都能嵌入任何别的无挠加性群（如 \(\mathbb{R}^d\)）中。然而，这些嵌入中有许多是平凡的，落在 \(\mathbb{R}^d\) 的某个子空间里。“能把一个加性集非平凡地嵌入的最大维数是多少”这一问题，将引出 Freiman 维数的概念，我们将在 5.5 节研究它。

证明. 由推论 3.6，我们可以取 \(Z=\mathbb{Z}^n\)（某个 \(n\ge 0\)）。通过平移 \(A\)，可以假设 \(A\) 实际上落在 \((\mathbb{Z}^+)^n\) 中，即所有坐标都非负。由于 \(A\) 是有限的，我们看到 \(A\) 是 \([0,M/k)^n\) 的子集（对某个大整数 \(M\)，取作 \(k\) 的倍数）。现在定义映射 \(\varphi:A\to\mathbb{Z}\) 为 \[\varphi(a_1,\dots,a_n):=a_1+a_2 M+a_3 M^2+\cdots+a_n M^{n-1}.\] 换句话说，我们把 \(A\) 的元素视为以 \(M\) 为底的整数数字串。这是一个 \(k\) 阶 Freiman 同构（其中 \(\varphi_k\) 与 \(\varphi\) 定义方式相同，但限制在 \(kA\) 上）；关键在于：若 \(M\) 足够大，我们就永远不必“进位”。这表明我们可以经由一个 Freiman 同构把 \(A\) 映到整数集；同样的论证表明，只要 \(N\ge M^n\)，就能映到 \(\mathbb{Z}/(N\cdot\mathbb{Z})\)。♦
例：把二维集合编码成一维整数

取 \(n=2\)，\(k=2\)，集合 \(A=\{(0,0),(1,0),(0,1),(1,1)\}\subseteq\mathbb{Z}^2\)。这里坐标最大为 \(1\)，要做 \(2\) 个元素相加，每个坐标的和最大为 \(1+1=2\)。取底 \(M=4\)（满足 \(M\ge kN=4\) 的大数，足以容纳坐标和 \(2\) 而不进位）。编码 \(\varphi(a_1,a_2)=a_1+a_2\cdot4\)： \[\varphi(0,0)=0,\quad\varphi(1,0)=1,\quad\varphi(0,1)=4,\quad\varphi(1,1)=5.\] 于是 \(A\) 被一一对应到整数集合 \(\{0,1,4,5\}\)。

  1. 在 \(\mathbb{Z}^2\) 里 \((1,0)+(0,1)=(1,1)\)；编码后 \(1+4=5\)，正是 \(\varphi(1,1)\)。和的关系被保持。
  2. 因为底 \(M=4\) 比任意一位坐标的两元素之和（最大 \(2\)）都大，不同坐标永远不会在加法里互相“串位”，所以“在 \(\mathbb{Z}^2\) 里和相等”与“在 \(\mathbb{Z}\) 里和相等”完全一致——这就是 \(2\) 阶同构。
  3. 底取 \(M\ge kN\) 的作用，正是把每个坐标分配到一段宽度为 \(M\) 的“数位”，相加时各数位互不干涉，如同竖式加法不进位。
(0,0) (1,0) (0,1) (1,1) φ, 底 M=4 0 1 4 5 {0,1,4,5}⊂ℤ，加法结构完全一致
把多维坐标当作大底数 \(M\) 下的各位数字，只要不进位，多维的“和相等”就忠实地变成一维整数的“和相等”。

压缩引理：搬进一个仅略大的循环群

正如我们稍后将看到的，Freiman 同态与同构这套机制在处理有挠群时也非常有用，例如我们可以用它把整数上的问题转移到循环群上的问题，反之亦然。如果我们只愿意处理加性集 \(A\) 的一个固定比例的部分，那么下面的压缩引理使我们能在一个阶数只比 \(A\) 本身大一点点的循环群中工作。

引理 5.26设 \(A\) 为加性集，其环境群 \(Z\) 要么是无挠的，要么是素数阶循环群；又设 \(n\ge 1\) 为正整数。设 \(N\) 为满足 \[2n|nA-nA|
证明. 由引理 5.25，只需考虑 \(Z\) 是素数阶循环群 \(\mathbb{Z}_p\) 的情形。 我们将使用一阶矩方法（first moment method，即概率期望法）。设 \(\lambda\in\mathbb{Z}_p\setminus\{0\}\) 为从 \(\mathbb{Z}_p\) 的可逆元中均匀随机选取的元素。映射 \(x\mapsto\lambda\cdot x\) 因而是 \(\mathbb{Z}_p\) 上的一个加性群同构，特别地是 \(\mathbb{Z}_p\) 上所有阶的 Freiman 同构。这种“按任意倍数放缩 \(A\)”的自由，将用来避免一种“碰撞”问题（稍后即明）。 现在我们定义投影 \(\pi:\mathbb{Z}_p\to\mathbb{Z}_N\) 为 \[\pi(m):=\iota(m)\bmod N,\] 其中 \(\iota:\mathbb{Z}_p\to[0,p)\) 是把剩余类 \(m+(p\cdot\mathbb{Z})\) 送到 \(m\)（\(m=0,\dots,p-1\)）的显然映射。 映射 \(\pi\) 并不完全是一个加性同态；然而注意，对 \(j=0,1,\dots,n-1\)，当 \(\pi\) 限制在集合 \(Z_j:=\big(jp/n,(j+1)p/n\big]\) 上时，它是一个 \(n\) 阶 Freiman 同态——而 \(Z_j\) 大致占据了原来域 \(\mathbb{Z}_p\) 的 \(\frac1n\)。由鸽笼原理，对每个 \(\lambda\)，存在某个 \(0\le j=j(\lambda)同构。唯一可能的障碍是 \(nA'\) 中可能出现碰撞，即存在 \(x_1,\dots,x_n,x_1',\dots,x_n'\in A'\)，使得 \[\pi(x_1)+\cdots+\pi(x_n)=\pi(x_1')+\cdots+\pi(x_n')\] 而 \(x_1+\cdots+x_n\ne x_1'+\cdots+x_n'\)。幸运的是，若 \(N\) 足够大且 \(\lambda\) 随机选取，这类碰撞很少发生。事实上，如果出现上述碰撞，那么 \[\iota(x_1)+\cdots+\iota(x_n)-\big(\iota(x_1')+\cdots+\iota(x_n')\big)\] 必为 \(N\) 的某个非零倍数。由于 \(x_1,\dots,x_n,x_1',\dots,x_n'\) 落在 \(A'\) 中，从而落在 \(\lambda A\) 中，我们因此看到：碰撞只有当 \(n\,\iota(\lambda A)-n\,\iota(\lambda A)\) 含有 \(N\) 的某个非零倍数时才可能发生。然而我们可以计算它发生的概率： \[\begin{aligned} &\mathbb{P}\big(\exists k\in\mathbb{Z}\setminus 0:\,kN\in n\,\iota(\lambda A)-n\,\iota(\lambda A)\big)\\ &\le\sum_{|k|\le np/N;\,k\ne 0}\mathbb{P}\big(kN\in n\,\iota(\lambda A)-n\,\iota(\lambda A)\big)\\ &\le\sum_{|k|\le np/N;\,k\ne 0}\mathbb{P}\big(kN+p\cdot\mathbb{Z}\in n\lambda A-n\lambda A\big)\\ &=\sum_{|k|\le np/N;\,k\ne 0}\ \sum_{x\in nA-nA}\mathbb{P}\big(kN=\lambda x\bmod p\big)\\ &=\sum_{|k|\le np/N;\,k\ne 0}\ \sum_{x\in nA-nA}\mathbb{P}\big(\lambda=(kN)^{-1}x\bmod p\big)\\ &\le\sum_{|k|\le np/N;\,k\ne 0}\ \sum_{x\in nA-nA}\frac{1}{p-1}\\ &\le\frac{2np}{N}\,|nA-nA|\,\frac{1}{p-1}, \end{aligned}\] 其中我们用到了 \(p\) 是素数这一事实（以便在模 \(p\) 下求 \(kN\) 的逆）。由我们对 \(N\) 的假设，我们于是看到这个概率严格小于 \(1\)。因此我们可以选取这样一个 \(\lambda\)，使得 \(\pi:A'\to B\) 如所声称的那样成为 \(n\) 阶 Freiman 同构。♦

上面的论证应当与定理 1.3 的证明相比较。

压缩引理的思路拆解
  1. 目标。把住在巨大的 \(\mathbb{Z}_p\)（\(p\) 可能非常大）里的集合 \(A\)，搬进一个小得多的 \(\mathbb{Z}_N\)（\(N\) 只比 \(|A|\) 的和差信息大一点），同时不破坏 \(n\) 阶以内的和差结构。代价是只能保住 \(A\) 的 \(1/n\)。
  2. 第一步：切成 \(n\) 段。把 \([0,p)\) 等分为 \(n\) 段 \(Z_0,\dots,Z_{n-1}\)，每段长约 \(p/n\)。\(A\)（放缩后）的点分落各段，鸽笼原理保证至少有一段装下了 \(\ge|A|/n\) 个点，取这段里的点为 \(A'\)。在同一段内，\(n\) 个数相加之和不会超过 \(n\cdot(p/n)=p\)，所以“\(\bmod N\) 再取”不会把段内的加法搞乱——这保证 \(\pi\) 在 \(A'\) 上是同态。
  3. 第二步：随机放缩避免碰撞。同态还不够，要同构（即“\(\bmod N\) 后和相等”能反推“原来和也相等”）。坏情况是两组不同的和恰好相差 \(N\) 的倍数而被 \(\bmod N\) 抹平。先用随机 \(\lambda\) 把 \(A\) 整体乘一个随机倍数，再算“出现碰撞”的概率。
  4. 第三步：期望法收尾。逐项估计：每个“坏的 \(k\) 与差 \(x\)”使 \(\lambda\) 恰好落到一个特定值的概率是 \(\frac1{p-1}\)；坏 \(k\) 约 \(\frac{2np}{N}\) 个，差 \(x\) 共 \(|nA-nA|\) 个。乘起来得概率 \(\le\frac{2np}{N}|nA-nA|\frac1{p-1}\)。由假设 \(2n|nA-nA|必有某个 \(\lambda\) 让碰撞一次都不发生——那个 \(\lambda\) 给出真正的同构。
ℤ_p 切成 n 段 最密的一段 → A′ π = mod N 小循环群 ℤ_N B = π(A′)，n 阶同构
切段保证段内不折回（同态），随机放缩 + 期望法保证 \(\bmod N\) 不制造假碰撞（同构）。

习题

习题 5.3.1 设 \(\varphi:A\to B\) 为两个加性集之间的映射，\(k\ge 1\)。证明：\(\varphi\) 是 \(k\) 阶 Freiman 同构，当且仅当 \(\varphi\) 是满射且 \[a_1+\cdots+a_k=a_1'+\cdots+a_k'\iff\varphi(a_1)+\cdots+\varphi(a_k)=\varphi(a_1')+\cdots+\varphi(a_k')\] 对一切 \(a_1,\dots,a_k,a_1',\dots,a_k'\in A\) 成立。
习题 5.3.2 [257] 设 \(n>1\)。证明 \(\{0,1,n+1\}\) 与 \(\{0,1,n\}\) 是 \(n\) 阶 Freiman 同构的，但不是 \(n+1\) 阶 Freiman 同构的。
习题 5.3.3 证明：给定任意 \(k\ge 1\) 以及任意加性集 \(A\)，则 \(A\) 与某个有限阿贝尔群的某个子集是 \(k\) 阶 Freiman 同构的。
习题 5.3.4 设 \((A,Z)\) 与 \((B,W)\) 为加性集，又设 \(\varphi:A\to B\) 是一个任意阶 \(k\) 的 Freiman 同态。再假设 \(Z\) 是由 \(A\) 生成的群。证明：存在唯一的群同态 \(\psi:Z\to W\) 与元素 \(c\in W\)，使得 \(\varphi(x)=\psi(x)+c\) 对一切 \(x\in A\) 成立。
习题 5.3.5 设 \((A,Z)\) 与 \((B,W)\) 是阶至少为 \(2\) 的 Freiman 同构。证明 \(\sigma[A]=\sigma[B]\)、\(\delta[A]=\delta[B]\)，以及 \(E(A,A)=E(B,B)\)。又证明对任意 \(\alpha\in\mathbb{R}\) 有 \(|\mathrm{Sym}_\alpha(A)|=|\mathrm{Sym}_\alpha(B)|\)。（这些记号的含义见定义 2.4、2.8、2.32。）
习题 5.3.6 设 \((A,Z)\) 与 \((B,W)\) 为含有原点 \(0\) 的加性集，又设 \(\varphi:(A,Z)\to(B,W)\) 为阶至少为 \(3\) 且固定原点的 Freiman 同构，即 \(\varphi(0)=0\)。证明：对任意 \(K\ge 1\)，\(A\) 是 \(K\)-近似群当且仅当 \(B\) 是。又证明：若把“\(K\)-近似群”换成“\(K\)-近似群的平移”，则可去掉 \(\varphi(0)=0\) 以及 \(A,B\) 含 \(0\) 的要求。
习题 5.3.7 设 \((A,Z),(B,Z),(A',Z'),(B',Z')\) 为加性集，并设 \(\varphi:A\sqcup B\to A'\sqcup B'\) 是一个 \(k\) 阶 Freiman 同构，它把 \(A\) 映到 \(A'\)、把 \(B\) 映到 \(B'\)。证明：只要 \(|n_1|+|n_2|+|n_3|+|n_4|\le k\)，就有 \(|n_1 A-n_2 A+n_3 B-n_4 B|=|n_1 A'-n_2 A'+n_3 B'-n_4 B'|\)。若 \(k\ge 2\)，证明 \(d(A,B)=d(A',B')\) 且 \(E(A,B)=E(A',B')\)。又证明：\(A\) 能被 \(B\) 的 \(K\) 个平移覆盖，当且仅当 \(A'\) 能被 \(B'\) 的 \(K\) 个平移覆盖。
习题 5.3.8 假设两个加性集 \(A\) 与 \(B\) 是 \(k\) 阶 Freiman 同构的。若 \(n,m,k'\ge 0\) 满足 \(k'(n+m)\le k\)，证明 \(nA-mA\) 与 \(nB-mB\) 是 \(k'\) 阶 Freiman 同构的。
习题 5.3.9 证明：固定基数 \(N\) 的所有 Sidon 集彼此都是 \(2\) 阶 Freiman 同构的。更一般地，对任意 \(h\ge 2\)，证明基数为 \(N\) 的所有 \(B_h\) 集彼此都是 \(h\) 阶 Freiman 同构的，并且一个 \(B_h\) 集在 Freiman 同构下的像仍是一个 \(B_h\) 集。于是人们可以只用一个阶为 \(N\) 的“标准” \(B_h\) 集（例如 \(\mathbb{Z}^N\) 的基 \(e_1,\dots,e_N\)），许多关于这个标准集的加性结果就会自动转移到任意 \(B_h\) 集上。

返回 全书目录