特殊篇章（数学定理）二 (6-5)

───

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

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。