塞迈雷迪定理(有限形式)

第一步(归约到有限窗口)。假设无限版本对某个不含任何长度为 $k$ 数列的 $d(A_0) > 0$ 不成立。那么对每个 $N$,限制 $A_0 \cap [1,N]$ 是 $\{1,\dots,N\}$ 中不含长度为 $k$ 数列的子集,其大小对固定的 $\delta$ > 0 按 $\delta$$N$ 增长。若有限版本成立,则 $N$ 可以任意大时这样的族不可能存在——矛盾,因此两个命题等价。

第二步(正则划分)。把 $\{1,\dots,N\}$ 中潜在的长度为 $k$ 的数列看作 $(k-1)$-一致超图的边。超图正则性引理将顶点集划分为有限个部分,除了一小部分例外,任意几个部分之间都呈伪随机:它们之间的边密度几乎是常数,不存在异常稠密或稀疏的子簇。

第三步(计数引理)。一旦划分是正则的,相应的计数引理表明任何具有正相对密度的部分组合都必须包含预期数量的完整构型——特别地,至少存在一个真正长度为 $k$ 的数列,因为具有正密度的正则伪随机结构无法避开正在被检验的模式。

第四步(移除论证)。如果 $A$ 完全不含长度为 $k$ 的数列,计数引理将迫使正则划分所计数的构型几乎全部退化,这意味着只需从 $A$ 中删去极少数元素就能消灭所有近似数列——这与 $A$ 在任意大的 $N$ 上保持密度 $\delta$ 矛盾。因此长度为 $k$ 的数列必然存在。(1977 年弗斯滕伯格的遍历理论证明与高尔斯的高阶傅里叶分析证明沿着完全不同的路径得到同样的结论,二者都给出了关于 $N(k,\delta)$ 的显式但天文数字般巨大的界。)