3. 有限域上的 Freiman 定理

在我们可以证明 Freiman 定理的有限域版本 (定理 1.0.14) 之前, 我们介绍最后一个引理.

定理 3.1 (Ruzsa 覆盖引理, 1999). 令 $X$ 和 $B$ 是一个 Abel 群的子集. 如果 $|X+B|\le K|B|$, 则存在一个子集 $T\subset X$ 且 $|T|\le K$ , 满足 $X\subset T+B-B$.

覆盖的类比为我们的证明提供了灵感. 我们将覆盖集视为度量空间中的球, 如果我们有一个半尺寸球 (半径为 0.5 的球) 的最大堆积, 将每个球扩展成一个单位球应该会产生该区域的覆盖. 这里的最大意味着不能放置更多的球, 同时要保证圆心在区域内. 下面我们将其形式化从而证明 Ruzsa 覆盖引理.

(...) 半尺寸球的最大堆积

(...) 将半尺寸球扩展为单位球, 构成一个覆盖

证明. 令 $T\subset X$ 是一个满足如下条件的最大子集: 对于任意的 $t\in T$, $t+B$ 都是不相交的. 因此, $|T||B|=|T+B|\le |X+B|\le K|B|$. 所以, $|T|\le K$.

由于 $T$ 是最大子集, 对于任意的 $x\in X$ , 存在 $t\in T$ 使得 $(t+B)\cap (x+B)\ne \varnothing$. 换句话说, 存在 $b,b^{\prime }\in B$ 使得 $t+b=x+b^{\prime }$. 因此, 对于某一 $t\in T$, $x\in t+B-B$. 由于这适用于所有 $x\in X$, 我们有 $X\subset T+B-B$.

$\square$

Ruzsa 覆盖引理是我们在有限域上证明 Freiman 定理 (定理 1.0.14) 所需的最后一个工具. 有限域模型比处理 $\mathbb{Z}$ 更简单, 因此与原始 Freiman 定理 (定理 1.0.10) 相比, 它可以使用更少的工具来完成.

现在, 我们将在有限指数群中证明 Freiman 定理. 这个限制比有限域稍大些.

定义 3.2. Abel 群的指数 $r$ 是满足如下条件的最小正整数 (如果存在的话) : 对于该群的所有元素 $x$, $rx=0$.

我们使用 $⟨A⟩$ 来指代由 $G$ 的某个子集 $A$ 生成的群 $G$ 的子群. 借助这种表示法, 群 $G$ 的指数是 ${\max }_{x\in G}|⟨x⟩|$. 下面我们在有有限指数 Abel 群上证明 Ruzsa 对于 Freiman 定理的类比.

定理 3.3 (Ruzsa 1999). 令 $A$ 为指数 $r<\infty$ 的 Abel 群中的有限集. 如果 $|A+A|\le K|A|$, 则$$|⟨A⟩|\le K^2{r}^{K^4}|A|$$

证明. 根据 Plünnecke-Ruzsa 不等式 (定理 2.0.4) , 我们有$$|A+(2A-A)|=|3A-A|\le K^4|A|$$根据 Ruzsa 覆盖引理 (令 $X=2A-A,B=A$ ), 存在 $T\subset 2A-A$ 且 $|T|\le K^4$ 满足$$2A-A\subset T+A-A$$两边同时加上 $A$, 我们得到$$3A-A\subset T+2A-A\subset 2T+A-A$$重复上一操作, 对任意正整数 $n$, 我们有$$(n+1)A-A\subset nT+A-A\subset ⟨T⟩+A-A$$对于足够大的 $n$, 我们有 $nA=⟨A⟩$. 因此, $$⟨A⟩\subset ⟨T⟩+A-A$$由于指数是有限的, $$|⟨T⟩|\le r^{|T|}\le r^{K^4}$$根据 Plünnecke-Ruzsa 不等式 (定理 2.0.4) , $$|A-A|\le K^2|A|$$因此$$|⟨A⟩|\le |⟨T⟩||A-A|\le r^{K^4}{K}^2|A|$$

$\square$

例 3.4. 在 ${\mathbb{F}}_2^n$ 中, 如果 $A$ 是一个独立集 (例如, $A$ 是某个子群的基) , 则 $A$ 具有倍增常数 $K\approx |A|/2$ 且 $|⟨A⟩|=2^{|A|}\approx 2^{2K}|A|$. 因此, $|⟨A⟩|$ 的上界至少是 $K$ 的指数.

最近, 我们已经非常精确地确定了 $|⟨A⟩|/|A|$ 的最大可能值. 对任意 $A\subset {\mathbb{F}}_2^{\infty }$ 和 $|A+A|/|A|\le K$ , 答案是 $\Theta \left(2^{2K}/K\right)$ (Even-Zohar , 2012) . 对于一般的 $r$, 我们猜测会有类似的现象. Ruzsa 推测 $|⟨A⟩|\le r^{CK}|A|$ (1999) . 对于部分 $r$, 比如素数, 这一猜测得到了验证 (Even-Zohar 和 Lovett , 2014) .

我们对有限指数 Abel 群的 Freiman 定理 (定理 3.3) 的证明没有推广到整数.