Tao–Vu · 加性组合学 · 第 6 章 图论方法

6.5　普吕内克定理Plünnecke’s theorem

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

研究和集（sum set）最有用的工具之一，便是普吕内克定理（Plünnecke’s theorem）。为了陈述这条定理，我们先要准备一些记号。

本节目标本节是普吕内克定理的“搭台子”部分。我们想要一个工具，能从“一小步相加 \(A+B\) 把集合放大了多少”这件事，推断出“连加很多步 \(A+kB\) 会放大多少”。为此，本节把和集这件代数的事，翻译成一张有向二部图，并定义一个度量放大程度的数——放大比 \(\|G\|\)。再给出一类特殊的图（普吕内克图），它恰好抓住了和集“可交换”的结构。把这些零件备齐，下一步就能陈述并证明主定理。

6.5.1　有向二部图与放大比

定义 6.23（放大比 Magnification ratio） 一个有向二部图（directed bipartite graph）是一个三元组 \(G(A,B,E)\)，其中 \(A,B\) 是有限集合（不一定不相交），而 \(E\subset A\times B\) 是若干来自 \(A\) 与 \(B\) 的有序对 \((a,b)\) 组成的集合。我们写 \(G:A\to B\) 以强调这张图的有向性，并用 \(a\to_G b\) 表示命题 \((a,b)\in E\)。若 \(X\subset A\)，记 \[G(X):=\{b\in B:\ a\to b\ \text{对某个}\ a\in X\}\] 为 \(X\) 的像（image）。于是定义 \(G\) 的放大比 \(\|G\|\) 为 \[\|G\|=\min_{X\subseteq A:\ X\neq\varnothing}\frac{|G(X)|}{|X|}.\] 等价地，\(\|G\|\) 是使得 \(|G(X)|\ge \|G\|\,|X|\) 对一切 \(X\subseteq A\) 都成立的最小那个数。

把这个定义拆开来读，它说的只是三件事：

  1. 左边一堆点叫 \(A\)，右边一堆点叫 \(B\)。每条带箭头的边从 \(A\) 里某点 \(a\) 指向 \(B\) 里某点 \(b\)，写成 \(a\to_G b\)。
  2. 给定 \(A\) 的一个子集 \(X\)，它的“像” \(G(X)\) 就是：从 \(X\) 里的点至少能被一条箭头指到的所有右边点。
  3. 对每个非空 \(X\)，算比值 \(\dfrac{|G(X)|}{|X|}\)（“指出去比指进来涨了几倍”），再在所有 \(X\) 上取最小。这个最小值就是放大比 \(\|G\|\)。

这里关键的字眼是“最小”。放大比由那个被压缩得最厉害（涨得最少）的子集决定——它是一个保证：无论你挑哪个非空 \(X\)，像至少也有 \(\|G\|\) 倍那么大。下面用一个具体小图把这个 min 算一遍。

例（手算放大比） 取 \(A=\{a_1,a_2,a_3\}\)，\(B=\{b_1,b_2,b_3,b_4\}\)，边为 \[a_1\to b_1,\ a_1\to b_2,\quad a_2\to b_2,\ a_2\to b_3,\quad a_3\to b_4.\] 我们把每个非空 \(X\) 的 \(|G(X)|/|X|\) 全列出来：
  1. 单点：\(X=\{a_1\}\) 像 \(\{b_1,b_2\}\) 比值 \(2\)；\(\{a_2\}\) 比值 \(2\)；\(\{a_3\}\) 像 \(\{b_4\}\) 比值 \(\mathbf{1}\)。
  2. 两点：三种取法的像都有 \(3\) 个点，比值都是 \(3/2\)。
  3. 三点：\(X=A\) 像是 \(\{b_1,b_2,b_3,b_4\}\)，比值 \(4/3\)。
  4. 取所有比值里的最小：\(\min\{2,2,1,\tfrac32,\tfrac32,\tfrac32,\tfrac43\}=1\)。故 \(\|G\|=1\)。♦
是 \(\{a_3\}\)（只连一条边）拖低了整张图的放大比。
A（左） B（右） a₁ a₂ a₃ b₁ b₂ b₃ b₄ \(\|G\|=\min_X |G(X)|/|X|=1\)（由 a₃ 决定）
有向二部图：从左点指向右点的箭头。子集 \(X\) 的像 \(G(X)\) 是它能指到的全部右点。放大比取所有非空 \(X\) 比值的最小值。

若 \(G:A\to B\) 与 \(H:B\to C\) 是两张有向二部图，且 \(A,B,C\) 两两不相交，我们定义复合（composition）\(H\circ G:A\to C\) 为如下有向图：在 \(H\circ G\) 中 \(a\to_{H\circ G}c\) 当且仅当存在 \(b\in B\) 使得 \(a\to_G b\to_H c\)。

也可以把有向二部图 \(G:A\to B\) 看成一个从 \(A\) 到 \(B\) 的多值函数（multiply-valued function）：一个 \(a\) 可以同时被送到好几个 \(b\)。这样一来，放大比就是在度量这个函数的多重性（一个输入平均能产生多少个输出）。复合 \(H\circ G\) 则正是“先走 \(G\) 一步，再走 \(H\) 一步”的两段路：能从 \(a\) 经某个中转点 \(b\) 走到 \(c\)，就在 \(H\circ G\) 里连一条 \(a\to c\)。

6.5.2　由和集造出来的图

例 6.24 设 \(A,B\) 是位于同一个母群（ambient group）中的加性集合。我们可以造出有向二部图 \(G_{A,B}:A\to A+B\)，方法是：当且仅当 \(a\in A\) 且 \(b\in B\) 时，连边 \(a\to_{G_{A,B}} a+b\)。注意到 \[\|G_{A,B}\|:=\min_{X\subseteq A:\ X\neq\varnothing}\frac{|X+B|}{|X|}\ \le\ \frac{|A+B|}{|A|}.\] 另外注意：若 \(A,B,C\) 是加性集合且 \(A,\ A+B,\ A+B+C\) 两两不相交，则 \[G_{A+B,C}\circ G_{A,B}=G_{A,B+C}.\]

这一步是全节的桥梁：它把纯代数的对象（和集 \(A+B\)）翻译成了图。逐条看清楚：

  1. 左点集是 \(A\)，右点集是和集 \(A+B\)。对每一个 \(a\in A\) 和每一个 \(b\in B\)，从 \(a\) 拉一条边指向 \(a+b\)。所以从 \(a\) 出发的所有箭头，正好指到 \(a+B=\{a+b:b\in B\}\)。
  2. 子集 \(X\subseteq A\) 的像就是 \(G_{A,B}(X)=X+B\)。于是比值 \(|G_{A,B}(X)|/|X|=|X+B|/|X|\)，放大比就是它在所有非空 \(X\) 上的最小值。
  3. 取 \(X=A\) 这一个特例就给出 \(|A+B|/|A|\)；而 min 是对所有 \(X\) 取的，自然不超过其中任何一个特例。这就是不等式 \(\|G_{A,B}\|\le |A+B|/|A|\) 的由来。
  4. 最后那个复合恒等式说：先加 \(B\)（\(G_{A,B}\)）、再加 \(C\)（\(G_{A+B,C}\)），合起来恰好就是一次性加 \(B+C\)（\(G_{A,B+C}\)）。这正是 \((a+b)+c=a+(b+c)\) 在图语言里的样子。
例（验证那个不等式取等） 在整数群 \(\mathbb Z\) 中取 \(A=\{0,1\}\)，\(B=\{0,10\}\)，则 \(A+B=\{0,1,10,11\}\)。边为 \(0\to0,\ 0\to10,\ 1\to1,\ 1\to11\)。
  1. \(X=\{0\}\)：像 \(\{0,10\}\)，比值 \(2\)。
  2. \(X=\{1\}\)：像 \(\{1,11\}\)，比值 \(2\)。
  3. \(X=\{0,1\}=A\)：像 \(\{0,1,10,11\}\)，比值 \(4/2=2\)。
  4. 故 \(\|G_{A,B}\|=2\)，恰等于 \(|A+B|/|A|=4/2=2\)。♦
此例中 \(\le\) 取到了等号；一般情况只能保证 \(\le\)。
A=\{0,1\} A+B=\{0,1,10,11\} 0 1 0 10 1 11 每个 \(a\) 指向 \(a+B\)；\(X\) 的像即 \(X+B\)。
把和集 \(A+B\) 画成图：边 \(a\to a+b\)。子集的像 \(=X+B\)，于是放大比与“和集放大了几倍”直接挂钩。

6.5.3　复合的放大比与普吕内克图

对一般的有向二部图，我们有不等式 \[\|H\circ G\|\le \|G\|\,\|H\|.\] 然而，对于某一类特殊的有向二部图——所谓的普吕内克图（Plünnecke graphs）——存在一个更深刻的不等式。虽然这个概念可以对抽象的图给出，但当图的顶点落在一个加性群里（在我们的应用中总是如此）时，描述起来最为容易。

读到这里要抓住的对比
  1. 对任意两张图，复合后的放大比只满足 “相乘”上界 \(\|H\circ G\|\le\|G\|\,\|H\|\)。直觉：走两步路，放大倍数至多是两步各自放大倍数之积。
  2. 普吕内克图的“更深刻不等式”要的是反过来的、更强的控制——这正是下一节主定理威力的来源。本节先把“普吕内克图”这个条件定义清楚。
定义 6.25（普吕内克图 Plünnecke graphs） 设 \(A_0,A_1,A_2\) 是加性群 \(Z\) 中的三个加性集合。称两张有向二部图 \(G_1:A_0\to A_1\) 与 \(G_2:A_1\to A_2\) 是可交换的（commutative），如果：每当 \(a,b,c\in Z\) 满足 \[a\to_{G_1} a+b\to_{G_2} a+b+c\quad(\text{在 }G_2\text{ 中}),\] 就也有 \[a\to_{G_1} a+c\to_{G_2} a+b+c.\] 更一般地，若 \(k\ge 2\)，且 \(A_0,\dots,A_k\) 是 \(Z\) 中的加性集合，我们定义一个\(k\) 阶普吕内克图为一个由二部图组成的 \(k\) 元组 \((G_1,\dots,G_k)\)，其中 \(G_j:A_{j-1}\to A_j\)，并且对每一对相邻的 \(G_j,G_{j+1}\)（\(1\le j

下面用一种更通俗的方式描述“可交换”：若一个平行四边形的两条相邻的边落在 \(G_1\cup G_2\) 中，那么这个平行四边形的另外两条边也落在其中。

把这句话和符号对上：四个顶点是 \(a,\ a+b,\ a+c,\ a+b+c\)。它们确实构成一个平行四边形——因为从 \(a\) 到 \(a+b\) 与从 \(a+c\) 到 \(a+b+c\) 都是“加上 \(b\)”这同一个位移，从 \(a\) 到 \(a+c\) 与从 \(a+b\) 到 \(a+b+c\) 都是“加上 \(c\)”这同一个位移。可交换性说的是：

  1. 已知两条相邻的边在图里：\(a\to_{G_1}a+b\)（先加 \(b\)）与 \(a+b\to_{G_2}a+b+c\)（再加 \(c\)）。
  2. 那么沿平行四边形另一条路走的两条边也必在图里：\(a\to_{G_1}a+c\)（先加 \(c\)）与 \(a+c\to_{G_2}a+b+c\)（再加 \(b\)）。
  3. 也就是说，到达同一个终点 \(a+b+c\) 的“先 \(b\) 后 \(c\)”与“先 \(c\) 后 \(b\)”两条路，在图里是同时存在的。这把加法的交换律编码进了图的结构。
a a+b a+c a+b+c +b（已知） +c（已知） +c（必然存在） +b（必然存在）
可交换性：蓝色实线两条相邻边在图里（先 \(+b\) 再 \(+c\)），则橙色虚线两条边（先 \(+c\) 再 \(+b\)）也必在图里。四点 \(a,a+b,a+c,a+b+c\) 构成平行四边形。
例 6.26 设 \(A,B\) 是加性集合。则由 \(k\) 张有向二部图组成的 \(k\) 元组 \[(G_{A,B},\ G_{A+B,B},\ \dots,\ G_{A+(k-1)B,B})\] （按例 6.24 的方式定义）构成一个普吕内克图。

把这个例子读懂，本节就贯通了：第 \(j\) 张图 \(G_{A+(j-1)B,\,B}\) 把第 \(j-1\) 层的集合 \(A+(j-1)B\) 通过“再加一个 \(B\)”送到第 \(j\) 层 \(A+jB\)。整串图就是“一次又一次地加 \(B\)”：

\[A\ \xrightarrow{+B}\ A+B\ \xrightarrow{+B}\ A+2B\ \xrightarrow{+B}\ \cdots\ \xrightarrow{+B}\ A+kB.\]

相邻两张图为什么可交换？因为它们都是“加上 \(B\) 里的某个元素”，而群里 \(b+c=c+b\)：先加 \(b\) 再加 \(c\)，与先加 \(c\) 再加 \(b\)，到达同一点、且两条路都由合法的边组成——这正是定义 6.25 里平行四边形条件。于是这一串“逐层加 \(B\)”的图天然满足可交换性，构成普吕内克图。它把“\(A+kB\) 究竟比 \(A\) 大多少”这一问题，安放进了图的框架里。

A A+B A+2B A+kB ⋯ +B+B+B \(G_{A+(j-1)B,B}:\ A+(j-1)B\to A+jB\)，相邻两张图可交换。
例 6.26 的普吕内克图：每张图都是“再加一个 \(B\)”。整串图把 \(A\) 一层层放大到 \(A+kB\)，相邻图因群加法可交换而满足平行四边形条件。

至此记号与概念已备齐。我们现在可以陈述普吕内克定理了。

小结：这节给了什么
  1. 放大比 \(\|G\|\)：一张有向二部图把子集“至少放大几倍”的保证，取所有非空子集比值的最小。
  2. 由和集造图 \(G_{A,B}\)：边 \(a\to a+b\)，使 \(\|G_{A,B}\|\le|A+B|/|A|\)，把代数问题翻译成图问题。
  3. 普吕内克图：相邻图满足“平行四边形（可交换）”条件的图串；逐层加 \(B\) 是其典型例子。
下一步（主定理）将利用普吕内克图的这种结构，给出比一般的 \(\|H\circ G\|\le\|G\|\|H\|\) 强得多的、对多步和集大小的控制。

返回 全书目录