5. 建模引理

当我们试图在整数上证明 Freiman 定理时, 主要困难是倍增常数较小的子集 $A$ 可能分散在 $Z$ 上. 我们可以使用 Freiman 同构在更小的空间内对 $A$ 进行建模, 同时保留相应的加性结构. 在这个更小的空间里, 我们有更好的工具, 例如傅立叶分析. 为了建立这个模型, 我们首先证明一个建模引理.

定理 5.1 (有限域上的建模引理). 令 $A \subset F_{2}^{n}$ 且对于某个正整数 $m$ , 有 $2^{m} \geq ∣ s A - s A ∣$ . 则存在从 $A$ 到 $F_{2}^{m}$ 某子集的 Freiman $s$ -同构.

如果

∣ A + A ∣ \leq K ∣ A ∣

, 由 Plünnecke-Ruzsa 不等式 (定理 2.0.4) 我们有

∣ s A - s A ∣ \leq K^{2 s} ∣ A ∣

, 因此存在

m = O (s lo g K + lo g ∣ A ∣)

满足该定理.

证明. 对于线性映射 $ϕ : F_{2}^{n} \to F_{2}^{m}$ , 以下是等价的:

1.	$ϕ$ 限制在 $A$ 上时, $ϕ$ 是 Freiman $s$ -同构的.
2.	$ϕ$ 在 $s A$ 上是单射的.
3.	对于所有非零的 $x \in s A - s A$ , $ϕ (x) \neq = 0$ .

令

ϕ : F_{2}^{n} \to F_{2}^{m}

为均匀随机线性映射. 每个

x \in s A - s A

违反 (3) 的概率为

2^{- m}

. 因此如果

2^{m} \geq ∣ s A - s A ∣

, 则满足 (3) 的概率是非零的. 这意味着存在 Freiman

s

-同构.

$□$

这个证明不能直接在 $Z$ 中工作. 事实上, $Z$ 上的建模引理表明, 如果 $A \subset Z$ 有小的倍增常数, 则很大一部分 $A$ 可以在一个小的循环群上建模, 该循环群的大小与 $∣ A ∣$ 相当. 所以我们可以对 $A$ 的一个大的子集进行建模, 之后我们再使用 Ruzsa 覆盖引理来恢复整个集合 $A$ 的结构.

定理 5.2 (Ruzsa 建模引理 1992). 令 $A \subset Z, s \geq 2, N$ 为正整数, 满足 $N \geq ∣ s A - s A ∣$ . 则存在 $A^{'} \subset A$ 并且 $∣ A^{'} ∣ \geq ∣ A ∣/ s$ 使得 $A^{'}$ 是 Freiman $s$ -同构于 $Z / N Z$ 的子集.

证明. 令 $q > max (s A - s A)$ 为素数. 对于每一个 $λ \in [q - 1]$ , 我们将 $ϕ$ 定义为如下函数的组合, $ϕ : Z \to Z / q Z ⟶ \times λ Z / q Z \to [q]$ 未指明的两个映射指的是自然嵌入. 前两个映射是群同态, 因此它们也是 Freiman $s$ -同态. 最后一个映射不是整个域上的群同态, 而是在小区间上的. 根据鸽巢原理, 对于所有的 $λ$ , 都存在一个长度小于 $q / s$ 的区间 $I_{λ} \subset [q]$ , 使得 $A_{λ} = {a \in A : ϕ (a) \in I_{λ}}$ 有超过 $∣ A ∣/ s$ 个元素. 因此, 当限制在 $A_{λ}$ 上时, $ϕ$ 是一个 Freiman $s$ -同态.

我们定义 $ψ : Z \to ϕ [q] \to Z / N Z$

引理 5.3. 如果 $ψ$ 没有将 $A_{λ}$ Freiman $s$ -同构映射到它的像, 那么存在非零 $d = d_{λ} \in s A - s A$ 使得 $ϕ (d) \equiv 0 (mod N)$ .

证明. 假设 $ψ$ 没有将 $A_{λ}$ Freiman 同构映射到它的像. 则存在 $a_{1}, \dots, a_{s}, a_{1}^{'}, \dots, a_{s}^{'} \in A_{λ}$ 使得 $a_{1} + \dots + a_{s} \neq = a_{1}^{'} + \dots + a_{s}^{'}$ 但 $ϕ (a_{1}) + \dots + ϕ (a_{s}) \equiv ϕ (a_{1}^{'}) + \dots + ϕ (a_{s}^{'}) (mod N)$ 由于 $ϕ (A_{λ}) \subset I_{λ}$ , 这是一个长度小于 $q / s$ 的区间, 我们有 $∣ ϕ (a_{1}) + \dots + ϕ (a_{s}) - ϕ (a_{1}^{'}) - \dots - ϕ (a_{s}^{'}) ∣ \in (- q, q)$ 我们假设上式左边是非负的, 即位于区间 $[0, q)$ . 否则我们可以交换 $(a_{1}, \dots, a_{s})$ 与 $(a_{1}^{'}, \dots, a_{s}^{'})$ .

设

d = a_{1} + \dots + a_{s} - a_{1}^{'} - \dots - a_{s}^{'}

. 因此

d \in (s A - s A) \ {0}

. 由于构成

ϕ

的所有函数都是群同态 (

mod q

) , 所以有

ϕ (d) \equiv ϕ (a_{1}) + \dots + ϕ (a_{s}) - ϕ (a_{1}^{'}) - \dots - ϕ (a_{s}^{'}) (mod q)

根据

ϕ

的定义,

ϕ (d)

位于

[0, q)

. 因此

ϕ (a_{1}) + \dots + ϕ (a_{s}) = ϕ (a_{1}^{'}) + \dots + ϕ (a_{s}^{'})

. 因此,

ϕ (d) \equiv 0 (mod N)

$□$

现在我们回到原来的证明路线上, 对于每个 $d \in (s A - s A) \ {0}$ , 满足 $ϕ (d) \equiv 0 (mod N)$ 的 $λ$ 数量等于 $[q - 1]$ 中可被 $N$ 整除的数量. 这个数字最多为 $(q - 1) / N$ .

因此, 满足如下条件的 $λ$ 的总数最多为 $(∣ s A - s A ∣ - 1) (q - 1) / N < q - 1$ : 存在 $d \in (s A - s A) ∖ {0}$ 且 $ϕ (d) \equiv 0 (mod N)$ . 所以存在 $λ$ 使得映射 $ψ$ , 从 $A_{λ}$ Freiman $s$ - 同构映射到它的像上. 取 $A^{'} = A_{λ}$ , 我们的证明就完成了.

$□$

通过总结到目前为止我们所知道的一切, 我们建立了一个有助于我们证明 Freiman 定理的结果.

推论 5.4. $A \subset Z$ 且 $∣ A + A ∣ \leq K ∣ A ∣$ , 则存在素数 $N \leq 2 K^{16} ∣ A ∣$ 和 $A^{'} \subset A$ , $∣ A^{'} ∣ \geq ∣ A ∣/8$ , 使得 $A^{'}$ 是 Freiman $8$ - 同构于 $Z / N Z$ 的子集.

证明. 根据 Plünnecke-Ruzsa 不等式 (定理 2.0.4) ,

∣8 A - 8 A ∣ \leq

K^{16} ∣ A ∣

. 我们根据 Bertrand 假设 ¹, 可以选到素数

K^{16} \leq N < 2 K^{16}

. 然后我们应用建模引理, 取

s = 8

和

N \geq ∣8 A - 8 A ∣

. 建模引理告诉我们, 存在一个子集

A^{'} \subset A

同时

∣ A^{'} ∣ \geq ∣ A ∣/8

, 并且

A^{'}

是 Freiman

8

-同构于

Z / N Z

的子集.

$□$

名字空间

视图

5. 建模引理