Ruzsa 三角不等式与覆盖引理

形式陈述

设 $G$ 是加法记号下的阿贝尔群，以下集合都是 $G$ 内的有限非空子集。约定

A+B=\{a+b:a\in A,\ b\in B\},\qquad A-B=\{a-b:a\in A,\ b\in B\}.

这里 $A-B$ 是差集，不是集合差 $A\setminus B$ ； $-B=\{-b:b\in B\}$ ，所以 $A-B=A+(-B)$ 。同一个群内的平移和取负都是双射，因而保持有限集合的基数。

Ruzsa 三角不等式断言，对任意这样的 $A,B,C$ ，

|A-C|\,|B|\le |A-B|\,|B-C|. \tag{1}

中间集 $B$ 可以自行选择；除以 $|B|$ 后，两个经过 $B$ 的差集大小给出直接差集 $A-C$ 的上界。

Ruzsa 覆盖引理断言，若

|A+B|\le K|B|,

则存在 $T\subseteq A$ ，使

|T|\le K,\qquad A\subseteq T+(B-B). \tag{2}

覆盖中心来自原集合 $A$ ，覆盖块是 $B-B$ 的平移。假设自动蕴含 $K\ge1$ ：固定一个 $a\in A$ ，有 $a+B\subseteq A+B$ 且 $|a+B|=|B|$ 。两条结论都不要求 $G$ 有限、无挠或带有次序。

直觉

不等式 (1) 把一个差 $d=a-c$ 拆成两段 $(a-b)+(b-c)$ 。如果允许每次任意改选 $a,c$ ，拆分后的数据未必能指回原输入；证明先为每个 $d$ 固定一组表示，随后两个分量的和恢复 $d$ ，固定表示再恢复 $b$ 。中间集的每个元素因此都贡献一个可区分的编码。

覆盖引理则从互不相交的 $t+B$ 出发。每加入一个中心，就在 $A+B$ 中占据恰好 $|B|$ 个新点，所以中心不能太多。当无法继续加入时，任意剩余的 $a+B$ 都碰到某个已选平移；一次相交足以把中心差 $a-t$ 写成 $B-B$ 中的元素。计数约束由此变成覆盖结构。

例子与边界

在整数群中取

X=\{0,1,4,5\},\qquad B=\{0,1\}.

直接列举得

X+B=\{0,1,2,4,5,6\},\qquad B-B=\{-1,0,1\}.

因此 $|X+B|=6=3|B|$ ，引理保证至多三个平移已经足够。实际按 $0,1,4,5$ 的次序扫描中心，可选

T=\{0,4\}.

两块 $0+B=\{0,1\}$ 与 $4+B=\{4,5\}$ 不交；中心 $1$ 的平移 $\{1,2\}$ 碰到前一块，中心 $5$ 的平移 $\{5,6\}$ 碰到后一块，所以不能继续加入。所得覆盖为

T+(B-B)=\{-1,0,1,3,4,5\}\supseteq X.

下面逐点给出 $x=t+b'-b$ 的证书，且每个 $b,b'$ 都属于 $B$ 。

$x$	$t$	$b'$	$b$	核对
$0$	$0$	$0$	$0$	$0=0+0-0$
$1$	$0$	$1$	$0$	$1=0+1-0$
$4$	$4$	$0$	$0$	$4=4+0-0$
$5$	$4$	$1$	$0$	$5=4+1-0$

图中上行只画选中的两块 $t+B$ ；下行画扩张后的 $t+(B-B)$ 。实心圆点标出 $X$ ，空心圆点 $-1,3$ 是覆盖允许引入的点。一个 $B-B$ 平移的最大值与最小值之差只有 $2$ ，无法同时覆盖 $0$ 和 $4$ ，所以这个例子至少需要两块，实际证书达到两块。

同一组集合还可核对三角不等式：

\begin{aligned} X-X&=\{-5,-4,-3,-1,0,1,3,4,5\},\\ X-B&=\{-1,0,1,3,4,5\},\\ B-X&=\{-5,-4,-3,-1,0,1\}. \end{aligned}

代入 $A=C=X$ ，得到 $9\cdot2\le6\cdot6$ 。例如差 $d=3$ 固定表示为 $4-1$ ，中间元素 $b=0,1$ 分别编码成 $(4,-1)$ 、 $(3,0)$ ；两对分量的和都是 $3$ ，但第一分量不同，仍能恢复所用的 $b$ 。

“无法再加中心”是按包含关系极大，不要求中心数最多。取 $A=\{0,1,2\}$ 、 $B=\{0,1\}$ ，只选 $T=\{1\}$ 已经极大，因为另外两个平移都与 $\{1,2\}$ 相交；另一个不交族 $T'=\{0,2\}$ 却有两个中心。覆盖证明对前者同样有效， $1+(B-B)=A$ 。中心越多也未必让最终覆盖更经济。

不能把结论中的 $B-B$ 随意换成 $B$ 。在 $G=\mathbb Z/3\mathbb Z$ 中取 $A=G$ 、 $B=\{0,1\}$ ，有 $|A+B|/|B|=3/2$ ，所以中心数至多为 $1$ 。任意一个 $B$ 平移只有两个点，无法覆盖三个点的 $A$ ；但 $B-B=G$ ，一个差集平移便已足够。

推论与应用

固定表示给出三角注入

对每个 $d\in A-C$ ，选定一次 $a_d\in A,c_d\in C$ ，满足 $d=a_d-c_d$ 。集合有限，所以逐项选择即可。定义

\Phi:(A-C)\times B\longrightarrow(A-B)\times(B-C), \qquad \Phi(d,b)=(a_d-b,\ b-c_d).

若输出为 $(u,v)$ ，则

d=u+v,\qquad b=a_{u+v}-u.

第一步恢复差，第二步使用事先固定的 $a_d$ 恢复中间元素。故输出至多有一个原像， $\Phi$ 为注入。比较有限定义域和值域的基数便得到 (1)。证明没有要求一个差只有一种表示，要求的只是先固定一种。

不交平移给出覆盖

从空集开始扫描 $A$ ；仅当新平移 $a+B$ 与所有已选的 $t+B$ 不交时，才把 $a$ 加入 $T$ 。有限扫描终止后，这些平移两两不交，并且它们都在 $A+B$ 内。因此

|T|\,|B| =\left|\bigcup_{t\in T}(t+B)\right| \le |A+B| \le K|B|,

约去正数 $|B|$ 得到中心数上界。

任取 $a\in A$ 。若 $a\in T$ ，它的平移当然与已选族相交；若 $a\notin T$ ，扫描拒绝它时已存在这样的相交，而后续只会增加中心。于是总能找到 $t\in T$ 及 $b,b'\in B$ ，满足

a+b=t+b'.

移项即得 $a=t+(b'-b)\in T+(B-B)$ ，完成 (2)。这里保证不交的是较小的块 $t+B$ ；扩张后的覆盖块 $t+(B-B)$ 可以互相重叠。

小倍增同时控制差集与能量

设 $|A+A|\le K|A|$ 。在 (1) 中把三个集合依次取为 $A,-A,A$ ，利用取负保持基数，得到

|A-A|\,|A| \le |A+A|\,|(-A)-A| =|A+A|^2,

故

|A-A|\le K^2|A|.

这一步说明小和集也限制差集增长。对四点例子， $X+X=\{0,1,2,4,5,6,8,9,10\}$ ，可取 $K=9/4$ ；所得界为 $|X-X|\le81/4$ ，而实际值为 $9$ 。一般上界不必在每个例子中紧。

加性能量用另一种计数方式描述小和集：把每个和的表示次数平方求和，Cauchy–Schwarz 给出

E(A)\ge\frac{|A|^4}{|A+A|} \ge\frac{|A|^3}{K}.

这条能量下界、差集上界与覆盖引理分别提供碰撞数量、集合大小和实际平移证书。能量页中的两条坐标轴例子表明，大能量本身不能倒推整个集合有小倍增；本页也没有从有限覆盖进一步推出完整的结构分类。

参考资料

Ben Green, Additive Combinatorics, §§4.1–4.2, pp. 29–30：和差集记号、固定表示的三角注入与不交平移覆盖。
Terence Tao, Metric entropy analogues of sum set theory, 2014-03-19, Lemmas 1–2：有限集合版本的覆盖与三角不等式及其计数证明。

形式陈述 ​

固定表示给出三角注入 ​

不交平移给出覆盖 ​

小倍增同时控制差集与能量 ​

反向链接

形式陈述

固定表示给出三角注入

不交平移给出覆盖

小倍增同时控制差集与能量