2. Plünnecke–Ruzsa 不等式

在我们证明 Freiman 定理 (定理 1.0.10) 或其有限域版本 (定理 1.0.14) 之前, 我们需要一些工具. 我们从以 Ruzsa 命名的众多结果之一开始.

定理 2.1 (Ruzsa 三角不等式). 如果 $A,B,C$ 是一个 Abel 群的有限子集, 那么$$|A||B-C|\le |A-B||A-C|$$

证明. 我们将构造一个单射$$\varphi :A\times (B-C)\hookrightarrow (A-B)\times (A-C)$$对于每个 $d\in B-C$, 我们可以选择 $b(d)\in B,c(d)\in C$ 使得 $d=b(d)-c(d)$. 定义 $\varphi (a,d)=(a-b(d),a-c(d))$, $\varphi$ 是单射. 因为如果 $\varphi (a,d)=(x,y)$, 那么我们可以用 $(x,y)$ 通过 $d=y-x$ 和 $a=x+b(y-x)$ 来恢复 $(a,d)$ .

$\square$

笔记 2.2. 通过将 $B$ 替换为 $-B$ 并将 $C$ 替换为 $-C$, 我们可以将不等式中的一些加号更改为减号. 但不幸的是, 这个技巧不能用来证明类似的不等式 $|A||B+C|\le |A+B\Vert A+C|$. 尽管如此, 我们很快就会看到该不等式仍然成立.

你可能会疑惑, 三角形在哪里? 如果我们定义 $\rho (A,B)=\log \frac{|AB|}{\sqrt{|A||B|}}$, 那么定理 2.1 表明 $\rho (B,C)\le \rho (A,B)+\rho (A,C)$. 这看起来像三角不等式, 但不幸的是 $\rho$ 并不是一个度量, 因为通常情况下 $\rho (A,A)\ne 0$ . 但如果限制在子群上, $\rho$ 是一个真正的度量.

我们使用定理 2.1 的方式是控制小倍增集合的进一步倍增. 下面的例子展示了它的用途.

例 2.3. 假设 $A$ 是满足 $|2A-2A|\le K|A|$ 的 Abel 群的有限子集, 在定理 2.1 中令 $B=C=2A-A$, 那么我们得到$$|3A-3A|\le \frac{|2A-2A{|}^2}{|A|}\le K^2|A|$$令 $B=C=3A-2A$ 我们得到$$|5A-5A|\le \frac{|3A-3A{|}^2}{|A|}\le K^4|A|$$依此类推, 所以对于所有 $m$, 我们发现, $|mA-mA|$ 被 $|A|$ 的常数倍控制.

条件 $|2A-2A|\le K|A|$ 强于条件 $|A+A|\le K|A|$. 如果我们想在给定条件 $|A+A|\le K|A|$ 的情况下实现上面的常数倍控制, 我们有以下定理.

定理 2.4 (Plünnecke-Ruzsa 不等式). 如果 $A$ 是一个 Abel 群的有限子集并且 $|A+A|\le K|A|$, 则$$|mA-nA|\le K^{m+n}|A|$$

Plünnecke (1970) 最初的定理证明没有受到太多关注. Ruzsa (1989) 后来给出了 Plünnecke 定理更更简单的证明. 他的证明涉及到对一个被称作可交换分层图的对象的研究, 并涉及到 Menger 定理和张量积的技巧. 最近, Petridis (2012) 给出了一个非常简单的证明, 我们将在下面展示.

在证明这个定理时, 我们将原定理推广到以下定理.

定理 2.5. 如果 $A$ 和 $B$ 是 Abel 群的有限子集并且 $|A+B|\le K|A|$, 则$$|mB-nB|\le K^{m+n}|A|$$

令 $B=A$ 我们得到原不等式.

Petridis 的证明依赖于以下关键引理.

引理 2.6. 假设 $A$ 和 $B$ 是 Abel 群的有限子集. 如果 $X\subseteq A$ 是将 $\frac{|X+B|}{|X|}$ 最小化的非空子集, 并且 $K^{\prime }=\frac{|X+B|}{|X|}$, 则对于任意有限集 $C$ , $|X+B+C|\le K^{\prime }|X+C|$.

我们可以借助二分图来考虑这个引理. 考虑顶点集 $G_1\bigsqcup G_2$ 上的二分图, 其中 $G_1,G_2$ 是环绕的 Abel 群 $G$ 的拷贝, 对于所有的 $g\in G_1,g+b\in G_2$ , $b\in B$, 有从 $g$ 到 $g+b$ 的边. 用集合 $N(S)$ 表示顶点 $S$ 的邻域, 扩展率 $\frac{|N(A)|}{|A|}=\frac{|A+B|}{|A|}$. 引理指出, 如果 $X$ 是一个集合, 并且其扩展率 $K^{\prime }$ 小于等于它的任何子集的扩展率, 则对于任何集合 $C$, $X+C$ 也最多有 $K^{\prime }$ 的扩展率.

(...) 引理 2.6 示意图

定理 2.5. 我们假设上述引理成立, 我们证明定理 2.5.

令 $X$ 是 $A$ 的非空子集, 并且 $X$ 最小化 $\frac{|X+B|}{|X|}$. 令 $K^{\prime }=\frac{|X+B|}{|X|}$. 注意到 $K^{\prime }\le K$ , 应用引理 2.6, 令 $C=rB$ , 其中 $r\ge 1$, 我们有 $|X+(r+1)B|\le K^{\prime }|X+rB|\le K|X+rB|$. 迭代该过程我们得到, 对于 $r\ge 0$, $|X+rB|\le K^r|X|$. 然后应用定理 2.1, 我们有 $|mB-nB|\le \frac{|X+mB||X+nB|}{|X|}\le K^{m+n}|X|\le K^{m+n}|A|$.

$\square$

引理 2.6.

我们归纳于 $|C|$. $|C|=1$ 时命题显然成立, 因为对于任意有限集 $S$, $S+C$ 相当于对 $S$ 进行平移, 所以 $|S+C|=|S|$, 因此 $|X+B+C|=|X+B|=K^{\prime }|X|=$ $K^{\prime }|X+C|$

现在假设 $|C|>1$, 令 $\gamma \in C$ , 令 $C^{\prime }=C\backslash \{\gamma \}$. 然后有$$X+B+C=\left(X+B+C^{\prime }\right)\cup ((X+B+\gamma )\backslash (Z+B+\gamma ))$$其中,$$Z=\left\{x\in X\mid x+B+\gamma \subseteq X+B+C^{\prime }\right\}$$$Z\subseteq X$ , 回顾最小化的条件我们发现 $|Z+B|\ge K^{\prime }|Z|$. 所以$$\begin{array}{rl}|X+B+C|& \le \left|X+B+C^{\prime }\right|+|(X+B+\gamma )\backslash (Z+B+\gamma )|\\ & =\left|X+B+C^{\prime }\right|+|X+B|-|Z+B|\\ & \le K^{\prime }\left|X+C^{\prime }\right|+K^{\prime }|X|-K^{\prime }|Z|\\ & =K^{\prime }\left(\left|X+C^{\prime }\right|+|X|-|Z|\right)\end{array}$$现在我们来关注引理中不等式的右边 $X+C$. 注意到$$X+C=\left(X+C^{\prime }\right)\bigsqcup ((X+\gamma )\backslash (W+\gamma ))$$其中$$W=\left\{x\in X\mid x+\gamma \in X+C^{\prime }\right\}$$注意到这里的并是不相交的, 所以$$|X+C|=\left|X+C^{\prime }\right|+|X|-|W|$$因为 $x+\gamma \in X+C^{\prime }$, 所以 $W\subseteq Z$ , 所以有 $x+B+\gamma \subseteq$ $X+B+C^{\prime }$. 因此 $|W|\le |Z|$, 所以$$|X+C|\ge \left|X+C^{\prime }\right|+|X|-|Z|$$结合上一不等式我们便能完成归纳.

$\square$

引理 2.6 还允许我们将定理 2.1 中的所有减号替换为加号.

推论 2.7. 如果 $A,B,C$ 是 Abel 群的有限子集, 则 $|A||B+C|\le |A+B\Vert A+C|$

证明. 令 $X\subseteq A$ 是非空的, 并且最小化 $\frac{|X+B|}{|X|}$ . 令 $K=\frac{|A+B|}{|A|},K^{\prime }=\frac{|X+B|}{|X|}\le K$. 则有$$\begin{array}{rl}|B+C|& \le |X+B+C|\\ & \le K^{\prime }|X+C|\\ & \le K^{\prime }|A+C|\\ & \le K|A+C|\\ & =\frac{|A+B||A+C|}{|A|}\end{array}$$

$\square$

其中, 第二个不等号是由引理 2.6 得到的.