Tao–Vu · 加性组合学 · 第 3 章加性几何

3.2　广义算术级数Progressions

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

本节目标认识本书最重要的一类“加性集合”——广义算术级数（generalized arithmetic progression，简称级数）。它是“格点”和“凸体（盒子）”的混合物：长得像一个高维的长方形点阵。本节要弄清楚两件事：（1）这种集合在加法、减法下几乎是封闭的（相加相减后仍是同类级数，规模只放大一个可控的倍数）；（2）给一个级数再添上少数几个点，仍能塞进一个稍大的级数里。这些性质让级数在“无挠群”里扮演着子群的替身。

什么是广义算术级数（回顾定义 0.2）

在正式开始之前，先把记号摆清楚（这是第 0 章定义 0.2 的内容）。设 $Z$ 是一个加性群（即只关心加法的交换群）。取一个基点 $a\in Z$、一组基向量（也叫步长）$v=(v_1,\dots,v_d)$，其中每个 $v_i\in Z$，再取一组非负整数边长 $N=(N_1,\dots,N_d)$。所谓盒子 $[0,N]$ 是所有满足 $0\le n_i\le N_i$ 的整点 $(n_1,\dots,n_d)$ 组成的集合；记号 $n\cdot v=n_1v_1+\dots+n_dv_d$。于是

\[ P=a+[0,N]\cdot v=\Big\{\,a+n_1v_1+\dots+n_dv_d\ :\ 0\le n_i\le N_i\ \Big\}. \]

这里 $d$ 称为级数的秩（rank，也叫维数）。它的体积定义为 $\operatorname{vol}(P)=(N_1+1)(N_2+1)\cdots(N_d+1)$，也就是盒子里整点的总数。如果这些不同的整点 $(n_1,\dots,n_d)$ 经过 $a+n\cdot v$ 映射后两两不相等（即没有任何“撞车”），就称 $P$ 是真级数（proper），此时 $|P|=\operatorname{vol}(P)$；否则会有重合，$|P|<\operatorname{vol}(P)$。

例（一个具体的二阶级数）取 $Z=\mathbb{Z}$，基点 $a=0$，基向量 $v=(1,10)$，边长 $N=(2,3)$。那么 \[P=\{\,n_1\cdot 1+n_2\cdot 10\ :\ 0\le n_1\le 2,\ 0\le n_2\le 3\,\}.\] 把它列成表格：每一行固定 $n_2$，每一列固定 $n_1$。

$n_2\backslash n_1$	0	1	2
0	0	1	2
1	10	11	12
2	20	21	22
3	30	31	32

这 $12$ 个数互不相同，所以 $P$ 是真级数，$|P|=\operatorname{vol}(P)=(2+1)(3+1)=12$。它“长得像”一个 $3\times 4$ 的长方形点阵——这正是把它叫做“格与凸体的混合物”的原因。

秩为 $d$ 的真级数就是一个 $d$ 维盒子里的整点，被基向量 $v_1,\dots,v_d$ 撑成的“平行点阵”。这里 $d=2$，盒子是 $3\times4$，共 $12$ 个点。

级数之间怎样相加、相减

我们现在研究一个加性集合的基本例子，即广义算术级数（或简称级数），它在定义 0.2 中已经给出。它们是带有大量加性结构的加性集合的范本；可以把它们看作格（lattice）与凸体（convex set）之间的混合体。（关于这一启发式的更定量的实现，见下面的引理 3.36。）

请注意，具有相同基向量的两个级数相加非常容易： \[ (a+[0,N]\cdot v)+(a'+[0,N']\cdot v)=(a+a')+[0,N+N']\cdot v \tag{3.1} \] （特别地，秩和基向量都不发生变化）；而具有不同基向量的两个级数相加，则要用如下公式： \[ (a+[0,N]\cdot v)+(a'+[0,N']\cdot v')=(a+a')+[0,N\oplus N']\cdot(v\oplus v'). \tag{3.2} \] 这里 $N\oplus N'$ 表示把两组边长拼接成 $(N_1,\dots,N_d,N'_1,\dots,N'_{d'})$，$v\oplus v'$ 同理拼接两组基向量。请注意，若 $v$ 与 $v'$ 共用了一些基向量，则 (3.2) 右端的级数很可能是高度非真（improper）的（因为会出现大量重合）。此外，还可以把盒子 $[0,N]$ 换成另一个盒子，同样得到一个级数： \[ a+[N,M]\cdot v=(a+N\cdot v)+[0,M-N]\cdot v. \] 若使用形如 $[N,M)$ 等的盒子，也类似。特别地，一个级数的相反集仍是级数： \[ -(a+[0,N]\cdot v)=(-a)+[0,N]\cdot(-v)=(-a-N\cdot v)+[0,N]\cdot v. \tag{3.3} \]

例（公式 (3.1) 验算）在 $\mathbb{Z}$ 中取相同步长 $v=3$。设 $P=\{0,3,6\}=0+[0,2]\cdot 3$，$P'=\{1,4\}=1+[0,1]\cdot 3$。逐项相加： $P+P'=\{0,3,6\}+\{1,4\}=\{1,4,7,10\}$（去掉重复的 $4,7$）。而 (3.1) 预言 $(0+1)+[0,2+1]\cdot3=1+\{0,3,6,9\}=\{1,4,7,10\}$。两者一致，秩和步长都没变。

例（公式 (3.3) 取相反集）取 $P=\{0,3,6\}=0+[0,2]\cdot3$。它的相反集是 $\{0,-3,-6\}$。按 (3.3)：先用步长 $-v=-3$ 得 $0+[0,2]\cdot(-3)=\{0,-3,-6\}$；再把它整理成步长仍为正的标准写法 $(-6)+[0,2]\cdot3=\{-6,-3,0\}$。同一个集合，只是把基点挪到最小元、步长翻正而已。

由此以及 (3.2)，我们看到两个级数的和或差仍是级数。最后，我们做一个简单的观察：两个级数的笛卡儿积仍是级数。

直觉小结级数这个家族对“加、减、取相反、作笛卡儿积”都是封闭的——做完这些运算，结果还是同一类对象。唯一要小心的是：运算后体积会变大，而且如果基向量有重叠，得到的级数可能不再是“真”的（出现撞车重合）。下面两条引理就是要把“体积放大多少”这件事说成精确的不等式。

引理 3.10：级数在加法下几乎封闭

我们现在证明：在 $O(1)^d$ 的误差范围内，秩为 $d$ 的级数在加法下本质上是封闭的。

引理 3.10 设 $P=a+[0,N]\cdot v$ 是加性群 $Z$ 中一个秩为 $d$ 的级数；我们不要求 $P$ 是真的（见定义 0.2）。那么对任意整数 $n平移副本覆盖 \(b+[nN,mN]\cdot v$。特别地，对任意满足 $(n,m)\neq(0,0)$ 的 $n,m\ge 0$，可以用 $(n+m)^d$ 个 $P$ 的平移副本覆盖 $nP-mP$，从而 \[ |nP-mP|\le (n+m)^d\,|P|. \] 此外，$nP-mP$ 也是一个秩为 $d$ 的级数，其体积至多为 \[ \operatorname{vol}(nP-mP)\le (n+m)^d\,\operatorname{vol}(P). \]

（这里 $nP$ 指 $n$ 个 $P$ 相加的和集 $\underbrace{P+\dots+P}_{n}$；$nP-mP$ 指 $n$ 个 $P$ 之和再减去 $m$ 个 $P$ 之和。）

证明. 第一个论断是显然的，因为 \[ [n\cdot N,m\cdot N]\cdot v=[0,N]\cdot v+[(n,\dots,n),(m,\dots,m)]\cdot(N_1v_1,\dots,N_dv_d). \] 由 (3.1) 我们有 \[ nP-mP=(na-ma-mN\cdot v)+[0,(n+m)N]\cdot v, \] 其余的论断都由此推出。♦

这条证明很短，但每一步都值得拆开看清楚。先看第一个论断：为什么一个“长盒子”可以被若干个“标准盒子”覆盖。

逐坐标看。在第 $i$ 个方向上，长盒子的边是从 $nN_i$ 到 $mN_i$ 的整数区间 $[nN_i,\,mN_i]$。
把这条长边切成若干段标准长度 $N_i$ 的小段： \[ [nN_i,mN_i]=\bigcup_{k=n}^{m-1}\big(kN_i+[0,N_i]\big), \] 即 $nN_i+[0,N_i],\ (n+1)N_i+[0,N_i],\dots,(m-1)N_i+[0,N_i]$，一共 $m-n$ 段。每一段都是基本盒子 $[0,N_i]$ 的一次平移。
$d$ 个方向各自独立地有 $m-n$ 种选择，按笛卡儿积一搭配，整个 $d$ 维长盒子就被 $(m-n)\times(m-n)\times\dots=(m-n)^d$ 个标准盒子覆盖。每个标准盒子对应的就是 $P$ 的一次平移。

把长区间 $[nN,mN]$ 切成 $m-n$ 个长度为 $N$ 的标准段，每段是 $[0,N]$ 的一次平移。$d$ 维方向相乘得 $(m-n)^d$ 个覆盖盒。

再看第二个关键等式，即把 $nP-mP$ 写成一个级数。这一步只是把前面三条公式串起来用：

用 (3.1) 把 $n$ 个相同基向量的 $P$ 相加：$nP=na+[0,nN]\cdot v$。同理 $mP=ma+[0,mN]\cdot v$。
用 (3.3) 取相反集：$-mP=(-ma-mN\cdot v)+[0,mN]\cdot v$。
再用一次 (3.1) 把 $nP$ 和 $-mP$ 相加（它们基向量相同，都是 $v$）： \[ nP-mP=(na-ma-mN\cdot v)+[0,nN+mN]\cdot v=(na-ma-mN\cdot v)+[0,(n+m)N]\cdot v. \] 这正是一个新的级数：基点是 $na-ma-mN\cdot v$，基向量仍是 $v$（所以秩仍是 $d$），边长是 $(n+m)N$。

有了这个级数表达式，剩下两个不等式立刻得到：

覆盖数与基数。 在第一个论断里取 $b=na-ma-mN\cdot v$、取 $n'=0,\ m'=n+m$：于是 $nP-mP=b+[0,(n+m)N]\cdot v$ 可被 $(n+m-0)^d=(n+m)^d$ 个 $P$ 的平移覆盖。每个平移副本至多含 $|P|$ 个元素，故 $|nP-mP|\le(n+m)^d|P|$。
体积。 新级数体积为 $\prod_{i=1}^d\big((n+m)N_i+1\big)$。由于 $n+m\ge 1$，有 $(n+m)N_i+1\le(n+m)(N_i+1)$，逐项相乘得 \[ \operatorname{vol}(nP-mP)\le(n+m)^d\prod_{i=1}^d(N_i+1)=(n+m)^d\operatorname{vol}(P). \]

例（取 $n=m=1$，即 $P-P$）取 $P=\{0,1,2,3\}=0+[0,3]\cdot1$（一维，$d=1$）。则 $P-P=\{-3,\dots,3\}$，含 $7$ 个元素。引理给出的上界是 $(1+1)^1|P|=2\cdot4=8$，确实 $7\le 8$。同时 $P-P=-3+[0,6]\cdot1$ 仍是一维级数，体积 $7\le 2\cdot4=8$。可见“差集”只比原集大一个 $2^d$ 量级的常数倍，这正是级数“几乎封闭”的精确含义。

由这条引理我们尤其看到：若 $P$ 是一个秩为 $d$ 的对称级数且含原点（例如 $P=[-N,N]\cdot v$），则 $P$ 是定义 2.25 意义下的 $2^d$-近似群（approximate group）。事实上，可以把（对称的）小秩级数视为在无挠（torsion-free）情形下子群的替身（因为无挠群不可能含有限子群）。它们也是欧氏空间中盒子（更一般地，平行六面体）的算术类比；而且实变量调和分析中关于用盒子覆盖（在物理空间、傅里叶空间，或两者中）的许多结果，对级数都有对应的版本。

“近似群”是什么意思（定义 2.25 提要）普通子群 $H$ 满足 $H+H=H$：加法完全封闭。一个对称、含原点的集合 $A$ 称为 $K$-近似群，是说 $A+A$ 虽不一定等于 $A$，但能被 $K$ 个 $A$ 的平移副本盖住——“差不多封闭，只差 $K$ 倍”。对对称且含原点的 $P$，有 $P+P=P-P$，由引理 3.10（$n=m=1$）它被 $2^d$ 个平移覆盖，故 $P$ 是 $2^d$-近似群。秩 $d$ 越小，它就越像真正的子群。

秩 1 的特殊情形：普通算术级数

在秩 $d$ 等于 $1$ 的特殊情形下，一个广义算术级数就等同于一个普通算术级数（或简称算术级数） \[ P=a+[0,N]\cdot v=\{\,a+nv:0\le n\le N\,\}, \] 它有基点 $a\in Z$、基向量或步长 $v\in Z$、以及长度 $N+1$。再次注意，如果 $P$ 不是真的，则 $P$ 的基数可能小于 $N+1$；不过在无挠群中，只有当步长 $v=0$ 时才会发生这种情况。

秩 1 级数就是中学里的等差数列：从 $a$ 出发，每次加同一个步长 $v$，共 $N+1$ 项。

引理 3.11：级数 + 少量点，仍装得进一个级数

我们记录一条平凡的引理，它断言：一个级数与一个小集合的和集，可以（虽然有点浪费地）被包含在另一个级数之中。

引理 3.11 若 $P$ 是一个秩为 $d$ 的级数，而 $P+w_1,\dots,P+w_K$ 是 $P$ 的 $K$ 个平移副本，则所有这些平移副本 $P+w_1,\dots,P+w_K$ 都可以被包含在单个秩为 $d+K-1$、体积为 $2^{K-1}\operatorname{vol}(P)$ 的级数之中。

证明. 写 $P=a+[0,N]\cdot v$。由平移不变性，我们可以设 $w_K=0$。那么结论由使用如下级数即可得到： \[ a+[0,N]\cdot v+[0,1]^{K-1}\cdot(w_1,\dots,w_{K-1}). \tag{$\ast$} \] ♦

这条证明的要点在于那个新添的盒子 $[0,1]^{K-1}$。把它拆开来看：

为什么能设 $w_K=0$。 把每个 $w_i$ 都减去 $w_K$（整体平移），不改变“能否被同一个级数装下”这件事；平移完后 $w_K$ 就变成 $0$。
新级数 $(\ast)$ 长什么样。 它在原来的 $d$ 个基向量 $v_1,\dots,v_d$ 之外，又添了 $K-1$ 个新基向量 $w_1,\dots,w_{K-1}$，每个新方向的边长只取 $0$ 或 $1$（即盒子 $[0,1]$）。所以秩变成 $d+(K-1)=d+K-1$，体积变成 $\operatorname{vol}(P)\cdot 2^{K-1}$。
为什么每个 $P+w_i$ 都在里面。 在新方向上，让第 $i$ 个系数取 $1$、其余取 $0$，那一项恰好等于 $w_i$，于是 $a+[0,N]\cdot v+w_i=P+w_i$ 落在 $(\ast)$ 中；新方向系数全取 $0$ 时得到 $P+w_K=P$（因 $w_K=0$）。所以 $K$ 个平移副本全被装下。

每个平移副本 $P+w_i$（不同颜色的线段）是同一个 $P$ 沿新方向 $w_i$ 挪了一步。给级数增添 $K-1$ 个“只走 0 或 1 步”的新方向，就能把全部 $K$ 个副本同时罩住，代价是秩加 $K-1$、体积乘 $2^{K-1}$。

因此，如果给一个级数添上少数几个元素，仍能把合并后的集合放进一个秩与体积都略大的级数中，尽管体积可能随 $|A|$ 呈指数增长。这是不可避免的：见习题 3.2.2。正因为这种指数损失，有时不调用本引理反而更好——宁可分别处理单个级数的多个平移，也不要硬把所有东西塞进一个级数。还要注意，我们并未保证引理 3.11 中的级数是真的；我们将在 3.6 节回到这一点。

即时自测

在 $\mathbb{Z}$ 中取 $P=\{0,2,4,6\}$（步长 $2$，长度 $4$）。用 (3.1) 写出 $2P$，再列出它的全部元素并核对。
对上面的 $P$，引理 3.10 给出 $|P-P|$ 的上界是多少？实际 $|P-P|$ 又是多少？
设 $P$ 是秩 $2$、体积 $20$ 的级数，再添上 $K=3$ 个点。引理 3.11 保证可装进一个秩为多少、体积至多为多少的级数？

习题

习题 3.2.1 设 $N=(N_1,\dots,N_d)$ 是一组非负整数。证明：每一个长度为 $(N_1+1)\cdots(N_d+1)$ 的真普通算术级数，（作为集合）都等于某个维数为 $N$ 的真广义算术级数。（这个例子表明：即便限定级数为真，级数的秩也无法仅由它的元素集合唯一确定。）

习题 3.2.2 设 $K\ge 1$ 与 $d\ge 0$ 为整数，$P=a+[0,N]\cdot v$ 是加性群 $Z$ 中一个秩为 $d$ 的级数，基向量为 $v=(v_1,\dots,v_d)$，又设 $X=\{e_1,\dots,e_K\}$ 是 $Z$ 中 $K$ 个元素的集合。假设元素 $v_1,\dots,v_d,e_1,\dots,e_K$ 在 $\mathbb{Z}$ 上线性无关。证明：任何包含 $P+X$ 的级数都必然秩至少为 $d+K-1$ 且体积至少为 $2^{K-1}\operatorname{vol}(P)$，这表明引理 3.11 是最优的（sharp）。

习题 3.2.3 证明：在无挠加性群中，两个普通算术级数的交集仍是一个普通算术级数。如果去掉无挠假设会怎样？如果允许其中一个或两个级数的秩大于 $1$，又会怎样？

习题 3.2.4 证明：每一个有限加性群本身也是一个真级数。

习题 3.2.5 设 $P$ 是一个秩为 $d$ 的级数。证明：$P$ 包含一个算术级数 $Q$，满足 $|Q|\ge|P|^{1/d}$；并且进一步，若 $P$ 是真的则 $Q$ 也可取为真的，若 $P$ 关于原点对称则 $Q$ 也可取为关于原点对称。

习题导读（3.2.1 的直觉）一个长度为 $L=(N_1+1)\cdots(N_d+1)$ 的普通算术级数（秩 1），公差为 $v$，形如 $\{a,a+v,\dots,a+(L-1)v\}$。要把它“重新打包”成一个维数为 $N$ 的高阶级数，可用混合进制下标：令第 $i$ 个基向量为 $v_i=(N_1+1)\cdots(N_{i-1}+1)\cdot v$。这样 $\sum_i n_iv_i$（其中 $0\le n_i\le N_i$）恰好不重不漏地跑遍 $0,v,2v,\dots,(L-1)v$——这正是十进制把 $0$ 到 $999$ 写成“百位、十位、个位”三段的高维版本。它说明同一个点集可以有秩 1 和秩 $d$ 两种合法写法，所以“秩”是级数的属性而非点集的属性。

返回全书目录

\(n_2\backslash n_1\)	0	1	2
0	0	1	2
1	10	11	12
2	20	21	22
3	30	31	32