特殊篇章（数学定理）二

数学使徒（MathematicalApostle）

介绍：Balog-Szemerédi-Gowers 定理

我喜欢这个定理的证明，只用到基本的图论做一些简单的估计，但是这个定理用处很大，它可以把关于两个加集 A 和 B 的部分和/差的控制加之于两个子集 A′⊂A，B′⊂B 的完全和/差上去，而代价仅是对 A，B 常数级别的缩减

考虑二分图 G＝G(A，B，E) ，它的边集 E 定义了一个所谓部分和集合 A ᴳ＋B ，当且仅当 (α，b)∈E 的时候， α＋b∈G ，其中 α∈A，b∈B

Balog-Szemerédi 在1994年证明了这样的结果，如果 |A|＝|B|＝n ，并且 |E|≥n²/K 同时 |A ᴳ＋B|≤K′n ，其中 K，K′ 都是常数，那么可以找到子集 A′⊂A，B′⊂B 使得 |A′|，|B′|，|A′＋B′|＝Θᴋ，ᴋ′(n)

Gowers 后来的结果可以把 Θᴋ，ᴋ′(n) 中的系数取做 K，K′ 的多项式，甚至 K，K′ 都可以取做 nϵ ，这里 ϵ＞0

我们可以把 Balog-Szemerédi-Gowers 定理看作是关于稠密二分图的，如果一个二分图 G(A，B，E) 有足够多的边的话，将有很多的 α∈A，b∈B 被长度为一的 1 路径连接，继而就有很多的 α，α′∈A 被长度为二的 2 路径连接，继而就有很多的 α∈A，b∈B 被长度为三的 3 路径连接，等等，这是关于Balog-Szemerédi-Gowers 的直观

证明需要分别对图中的 2 路径和 3 路径做估计

引理1 2 路径的估计

给定 |E|≥|A||B|/K， K≥1 的二分图 G(A，B，E) ，对于任何 0≤ϵ≤1 都能找到 A′⊆A 使得 |A′|≥|A|

──

√2K

并且至少有 1−ϵ 比例的配对 α，α′∈A′ 被至少

ϵ

──

2K²|B| 条 G 中的 2 路径相连

证明

首先不妨减小 K 以后我们就假设 |E|＝|A||B|/K ，考虑恒等式

N(b) N(α) |E| 1

── ── ── ─

• 𝔼b∈B |A|＝𝔼α∈A |B|＝ |A||B|＝K

无非是从 B 和 A 的角度计算 |E|/|A||B|而已

|N(b)|²

──

• 𝔼b∈B |A|²

|N(α)∩N(α′)|

───────

＝𝔼α，α′∈A |B|

两边都是计算 2 路径 (α，b)，(b，α′) 的个数

使用 Cauchy-Schwarz 我们可以得到 𝔼α，α′∈A |N(α)∩N(α′)| 1

──────≥ ─

|B| K²

考察配对 α，α′∈A 的集合 Ω ，它们的连接比较弱 |N(α)∩N(α′) ϵ

|≤─── |B| 显然有

2K² ϵ

|N(α)∩N(α′)|＜──

────── 2K²

𝔼α，α′∈A𝕀[(α，α′)∈Ω] |B|

反过来就是

1 |N(α)∩N(α′)|

𝔼α，α′∈A(1−─ϵ𝕀[(α，α′)∈Ω])──────

ϵ |B|

1

≥──

2K²

左边按照 b∈B 重新排列得到

1

𝔼b∈B───

|A|² 1 1

∑α，α′∈N(b)(1−─ 𝕀[(α，α′)∈Ω])≥──

ϵ 2K²

所以必然存在 b∈B 使得

1

──

|A|² 1 1

∑α，α′∈N(b)(1−─ 𝕀[(α，α′)∈Ω])≥──

ϵ 2K²

此时 |N(b)|≥|A|

──

√2K 而且 |(α，α′)∈N(b)：(α，α′)∈Ω|≤ϵ|N(b)|²

，这很显然，因为左边求和非负值

于是我们只要令 A′：＝N(b) 命题便成立

注意我们其实把 A 缩减很多，甚至都缩减到某个 b 的邻域 N(b) ，但是只要是常数倍的缩减就都在一个数量级上，变化仍然不大

引理2 3 路径的估计

给定 |E|≥|A||B|/K，K≥1 的二分图 G(A，B，E) ，存在满足 |A′|≥|A|

──

4√2K 和 |B′|≥|B|

──的

4K A′⊆A， B′⊆B ，使得对任何 α∈A′，b∈B′ 至少有 |A||B|

───条 3 路径相连

2¹² K⁵

大体上我们要使用引理1，不过需要一点准备

证明

首先我们要缩减 A

从 A 中移除那些度小于 |B|/2K 的点剩下的就是 A~ ，因为从 G 到 G~ 最多移除 |A||B|/2K 条边， G~ 中至少还有|A||B| |A~||B|

───＝───＝

2K 2K|A~|/|A|

|A~||B| |A~||B|

───＝───

2K/L K′

条边，对此时的图 G~＝G~(A~，B，E~) 应用引理1，我们选择 ϵ：＝1

──

16K ，可得到子集 A~′⊆A~

|A~| |A|

|A~′|≥|A~|≥ ───＝───

── √2(2K/L) 2√2K

√2K′

1

满足条件至少有比例 1−─

16K 的配对(α，α′)∈A~′×A~′被至少 ϵ

─ |B| L²|B|

2K′²|B|＝───＝───

16K⋅2⋅(2K/L)² 128K³ 条 G~ 中的 2 路径相连

反过来最多有比例 1

─

16K 的配对(α，α′)∈A~′×A~′ 它们被少于 L²|B|

───

128K³ 条 G~ 中的 2 路径相连，我们称之为坏的配对

我们选取那些最多有 1

─

8K|A~′| 个坏的配对 (α，α′) 的 α∈A~′ ，这些点 α 构成集合 A′⊆A~′ ，显然有 |A~′|−|A′| 个 α 至少有 1

─

8K|A~′| 个坏的配对，于是

1

(|A~′|−|A′|)⋅─

8K|A~′| 1

≤─

16K(|A~′|)

( ₂ )×2＝|A~′|² ─── 16K

1 |A|

于是 |A′|≥─|A~′|≥───

2 4√2K

这一部分容易糊涂

这里的 1

─

8K|A~′| 不能太大，从后面的证明要求它小于 1

─

4K|A~′|

但是也不能太小，否则得到平凡的估计 |A′|≥0 没有用

我们再来缩减 B

从最开始 A~ 的构造可知 A~ 中所有的点的度都至少是 |B|/2K所以

∑b∈ʙ|{α∈A~′：(α，b)∈E}|＝|{(α，b)∈E：α∈A~′}|

|B|

≥ ──

2K|A~′|

如果我们选取 |A~′|

B′：＝{b∈B：|{α∈A~′： (α，b)∈E}|≥───} 4K 将会得到

|A~′||B′|≥∑b∈ʙ′|{α∈A~′：(α，b)∈E}|≥|A~′||B| ── 2K

−|A~′|

───

4K

|B|＝|A~′||B|

────

4K

由此可知 |B′|≥|B|/4K

这里缩减 B 并没有用到上面缩减到最后 A′ 的信息，用的是 A~′

最后考虑任意的 α∈A′，b∈B′

从 B′ 的构造过程可知， b 与至少 |A~′|/4K 个点 α′∈A~′ 相连

从 A′ 的构造过程可知，最多有 |A~′|/8K 对 (α，α′) 是坏的

于是至少有 |A~′|/4K−|A~′|/8K＝|A~′|/8K≥|A|/16√2K² 个 α′ 同时与 b 邻接，并且它们每个与 α 之间关系都不坏，都至少有 L²|B|

───

128K³

条 2 路径相连

于是我们就知道 α 与 b 之间 3 路径至少有

|A| L²|B| |A||B|

─── ─── ≥ ───

16√2K² 128K³ 2¹²K⁵

引理2到这里就证明结束

Balog-Szemerédi-Gowers 定理的证明

定理本身是关于加集的，所以先做个变换转为关于二分图的命题，具体就是把 A 视作 A×{0} ，把 B 视作 B×{1} ，都嵌入到 Z×Z 当中考虑，于是对于 G⊂A×B 就是个二分图

利用引理2，可以找到 A′⊂A， B′⊂B 使得对于所有的 α∈A′， b∈B′ 都有 |A||B|/2¹² K⁵ 条 3 路径相连

|{(α′，b′)∈A′×B′：(α，b′)，(b′，α′)，(α′，b)∈G} |A||B|

|≥ ───

2¹² K⁵

令 x：＝α＋b′，y：＝α′＋b′，z：＝α′＋b 便有

α＋b＝(α＋b′)−(b′＋α′)＋(α′＋b)＝x−y＋z

于是 |A||B|

|{(x，y，z)∈A ᴳ＋B：x−y＋z＝α＋b}| ≥ ── 2¹² K⁵

也即对于某个 α＋b 来说有至少对应着 |A||B| ─── 2¹² K⁵  个三元组 (x，y，z)

考虑到所有的三元组 (x，y，z) 数量的已知约束 |A ᴳ＋B|³≤(K′)³|A|³/²B³/²

所以一共有不超过下面数量的不同的 α＋b

(K′)³|A|³/²B³/²/|A||B|

───

2 ¹² K⁵

＝2¹² K⁵ K′³|A|¹/²|B|¹/²

到这里 Balog-Szemerédi-Gowers 定理就证完了

上一章 特殊篇章（数学定理）一 数学使徒（MathematicalApostle）最新章节 下一章 Tauber 定理（番外篇）