定理已证明

塞梅雷迪定理

命题陈述

每个具有正上密度（ $\limsup_{N\to\infty} |A \cap [1,N]|/N > 0$ ）的子集 $A \subseteq \mathbb{N}$ 都包含任意长的等差数列：对任意 $k \ge 1$ 和 $\delta > 0$ ，存在 $N(k,\delta)$ ，使得当 $N \ge N(k,\delta)$ 时， $\{1,\dots,N\}$ 中任意大小至少为 $\delta N$ 的子集都包含一个 $k$ 项等差数列。

为什么成立?

如果一个整数子集在全体整数中占有固定的正比例，它就不可能永远避开等距排列的模式——无论你怎样打散所选的数，任意指定长度的等差数列最终都必然出现。仅凭密度就足以强制产生算术结构。

证明思路

密度为 $\delta$ 的集合 $A \subseteq [1,N]$ 要么表现得像伪随机集——此时它大约包含期望数量 $\delta^k N^2$ 个 $k$ 项等差数列——要么不具备伪随机性，从而使 $A$ 与某种结构化配置相关联，借此可以过渡到一个子等差数列，使 $A$ 在其上的密度严格增大到 $\delta + c(\delta)$ 。由于密度不可能超过 1，这一密度递增迭代必然终止；而塞梅雷迪正则性引理（在后来的证明中则是高阶傅里叶分析、遍历理论或超图正则性）提供了分解为结构化部分与伪随机部分的工具。

证明者

1975 年证明恩德雷·塞梅赖迪

用到此定理的主题

塞迈雷迪定理

参考文献

Endre Szemerédi (1975). On sets of integers containing no k elements in arithmetic progression