← 返回 资料库 › 组合数学与离散数学 › 加性组合 组合数学与离散数学
塞迈雷迪定理 任何具有正密度的整数集合都包含任意长度的等差数列。
直观 直觉:密集集合中隐藏的等差数列 选取一个不太稀疏的正整数集合——比如它在任何规模下都保持固定比例。直觉告诉我们,这样的集合不可能永远避开所有模式:迟早它必须包含三个等间隔的数,然后四个,然后你想要多少个都可以。塞迈雷迪定理精确地表达了这一点:仅仅是「丰富性」——在整数中占正比例,不假设任何代数结构——就已经迫使该集合包含任意有限长度的等差数列。
塞迈雷迪正则性引理:任何大图都可以划分为有限个部分,使得几乎每对部分看起来都是伪随机的 大学 密度与精确表述 定义: 上密度
对正整数集合 A A A d ( A ) d(A) d ( A ) N N N A A A { 1 , … , N } \{1,\dots,N\} { 1 , … , N } d ( A ) = lim sup N → ∞ ∣ A ∩ [ 1 , N ] ∣ N d(A) = \limsup_{N \to \infty} \frac{|A \cap [1,N]|}{N} d ( A ) = lim sup N → ∞ N ∣ A ∩ [ 1 , N ] ∣
d ( A ) = lim sup N → ∞ ∣ A ∩ [ 1 , N ] ∣ N d(A) = \limsup_{N \to \infty} \frac{|A \cap [1,N]|}{N} d ( A ) = N → ∞ lim sup N ∣ A ∩ [ 1 , N ] ∣ 这里 A ∩ [ 1 , N ] A \cap [1,N] A ∩ [ 1 , N ] N N N A A A lim sup \limsup lim sup N N N d ( A ) d(A) d ( A )
d ( A ) > 0 ⟹ ∀ k ≥ 1 , ∃ a , r > 0 : { a , a + r , … , a + ( k − 1 ) r } ⊆ A d(A) > 0 \implies \forall\, k \ge 1,\ \exists\, a, r > 0 : \{a, a+r, \dots, a+(k-1)r\} \subseteq A d ( A ) > 0 ⟹ ∀ k ≥ 1 , ∃ a , r > 0 : { a , a + r , … , a + ( k − 1 ) r } ⊆ A 这就是完整的表述:只要 d ( A ) > 0 d(A) > 0 d ( A ) > 0 k k k { a , a + r , … , a + ( k − 1 ) r } \{a, a+r, \dots, a+(k-1)r\} { a , a + r , … , a + ( k − 1 ) r } k k k k = 3 k=3 k = 3 k k k
关于等差数列的三个定理比较 定理 对集合的假设 结论 范德瓦尔登 (1927) 对 Z + \mathbb{Z}^+ Z + 总有一个颜色类对任意 k k k k k k 塞迈雷迪 (1975) d ( A ) > 0 d(A) > 0 d ( A ) > 0 A A A k k k k k k 格林–陶 (2004) A A A A A A k k k k k k
进阶 证明思路:正则化方法 对任意整数 k ≥ 3 k \ge 3 k ≥ 3 δ > 0 \delta > 0 δ > 0 N ( k , δ ) N(k,\delta) N ( k , δ ) N ≥ N ( k , δ ) N \ge N(k,\delta) N ≥ N ( k , δ ) ∣ A ∣ ≥ δ N |A| \ge \delta N ∣ A ∣ ≥ δ N A ⊆ { 1 , … , N } A \subseteq \{1,\dots,N\} A ⊆ { 1 , … , N } k k k
为什么成立? 这个有限版本通过一个简单的紧致性论证在逻辑上等价于无限密度命题,而实际被证明的正是这个形式:不必处理一个无限集合,只需在一个大而有限的窗口中控制有限多种构型即可。
证明 第一步(归约到有限窗口)。假设无限版本对某个不含任何长度为 k k k d ( A 0 ) > 0 d(A_0) > 0 d ( A 0 ) > 0 N N N A 0 ∩ [ 1 , N ] A_0 \cap [1,N] A 0 ∩ [ 1 , N ] { 1 , … , N } \{1,\dots,N\} { 1 , … , N } k k k δ \delta δ δ \delta δ N N N N N N
第二步(正则划分)。把 { 1 , … , N } \{1,\dots,N\} { 1 , … , N } k k k ( k − 1 ) (k-1) ( k − 1 )
第三步(计数引理)。一旦划分是正则的,相应的计数引理表明任何具有正相对密度的部分组合都必须包含预期数量的完整构型——特别地,至少存在一个真正长度为 k k k
第四步(移除论证)。如果 A A A k k k A A A A A A N N N δ \delta δ k k k N ( k , δ ) N(k,\delta) N ( k , δ )
若 A ⊆ { 1 , … , N } A \subseteq \{1,\dots,N\} A ⊆ { 1 , … , N } ∣ A ∣ ≥ δ N |A| \ge \delta N ∣ A ∣ ≥ δ N N N N δ \delta δ A A A
为什么成立? 这是塞迈雷迪定理第一个非平凡的情形,由罗斯于1953年用傅里叶分析证明,而非一般 k k k
证明 第一步(用傅里叶方法计数数列)。假设 A ⊆ { 1 , … , N } A \subseteq \{1,\dots,N\} A ⊆ { 1 , … , N } δ \delta δ 1 A ^ ( θ ) = ∑ n ∈ A e ( θ n ) \hat{1_A}(\theta) = \sum_{n \in A} e(\theta n) 1 A ^ ( θ ) = ∑ n ∈ A e ( θ n ) A A A ( x , x + r , x + 2 r ) ∈ A 3 (x, x+r, x+2r) \in A^3 ( x , x + r , x + 2 r ) ∈ A 3 θ \theta θ 1 A ^ ( θ ) 2 1 A ^ ( 2 θ ) ‾ \hat{1_A}(\theta)^2 \, \overline{\hat{1_A}(2\theta)} 1 A ^ ( θ ) 2 1 A ^ ( 2 θ )
第二步(伪随机情形)。若 1 A 1_A 1 A δ 2 \delta^2 δ 2 θ = 0 \theta = 0 θ = 0 δ 3 N 2 \delta^3 N^2 δ 3 N 2 A A A
第三步(密度递增)。因此必有某个非零系数很大;这意味着 1 A 1_A 1 A e ( θ n ) e(\theta n) e ( θ n ) A A A A A A
第四步(迭代与结论)。密度不可能超过1,因此经过有限多轮密度递增步骤后过程必须终止——这意味着第二步的伪随机情形最终被迫出现,从而产生缺失的三项数列,与不存在的假设矛盾。罗斯最初的估计给出形如 N ( 3 , δ ) ≲ exp ( exp ( 1 / δ ) ) N(3,\delta) \lesssim \exp(\exp(1/\delta)) N ( 3 , δ ) ≲ exp ( exp ( 1/ δ )) N ( 3 , δ ) ≲ exp ( − c ( log N ) 1 / 12 ) N N(3,\delta) \lesssim \exp\!\big(-c(\log N)^{1/12}\big) N N ( 3 , δ ) ≲ exp ( − c ( log N ) 1/12 ) N
大学 实际应用与典型例题 作为这一证明的副产品而发明的塞迈雷迪正则性引理,后来成为理论计算机科学中使用最广泛的工具之一:它是图性质测试算法(仅通过检查有限大小的随机样本来判断一个巨大的图是否接近满足某性质)的基础,给出通信复杂度中的下界,并出现在组合设计与编码理论中。在数论方面,该定理位于一个谱系的一端,另一端是构造稠密无数列集合的贝伦德构造,而它的有限形式正是支撑素数中格林–陶定理的组合引擎。
例题: 具体集合中的三项数列
设 A = { 1 , 2 , 4 , 5 , 7 , 8 , 10 , 11 } ⊆ { 1 , … , 12 } A = \{1,2,4,5,7,8,10,11\} \subseteq \{1,\dots,12\} A = { 1 , 2 , 4 , 5 , 7 , 8 , 10 , 11 } ⊆ { 1 , … , 12 } d d d ∣ A ∣ / 12 = 2 / 3 |A|/12 = 2/3 ∣ A ∣/12 = 2/3 A A A
解答 第一步:由于 A A A A A A
第二步:取公差 r = 3 r=3 r = 3 a , a + r , a + 2 r a, a+r, a+2r a , a + r , a + 2 r
第三步:取 a = 1 a=1 a = 1 1 , 4 , 7 1, 4, 7 1 , 4 , 7 1 , 4 , 7 ∈ A 1,4,7 \in A 1 , 4 , 7 ∈ A
例题: 鸽笼原理迫使某个颜色类稠密——从而具有结构
将奇数染成红色,偶数染成蓝色。在 { 1 , … , 9 } \{1,\dots,9\} { 1 , … , 9 } { 1 , 3 , 5 , 7 , 9 } \{1,3,5,7,9\} { 1 , 3 , 5 , 7 , 9 } 5 / 9 5/9 5/9
解答 第一步:用2种颜色划分9个整数,两个颜色类的大小之和为9,由鸽笼原理较大的类至少有 ⌈ 9 / 2 ⌉ = 5 \lceil 9/2 \rceil = 5 ⌈ 9/2 ⌉ = 5 { 1 , 3 , 5 , 7 , 9 } \{1,3,5,7,9\} { 1 , 3 , 5 , 7 , 9 }
第二步:9个数的窗口中有5个,意味着红色类在此有限窗口上密度已为 5 / 9 > 0 5/9 > 0 5/9 > 0 Z + \mathbb{Z}^+ Z + 1 / 2 1/2 1/2
第三步:由于奇数具有正密度,塞迈雷迪定理(取 k = 3 k=3 k = 3 1 , 3 , 5 1,3,5 1 , 3 , 5
常见错误. 两个常见误解:(1) 正密度只保证某处存在等差数列,并不意味着 A A A d ( A ) > 0 d(A) > 0 d ( A ) > 0 N ( k , δ ) N(k,\delta) N ( k , δ ) k k k 历史注记
1936年,Paul Erdős 与 Pál Turán 猜想任何上密度为正的集合都必须包含任意长度的等差数列——这就是今天所称的塞迈雷迪定理。Klaus Roth 于1953年用傅里叶分析解决了 k = 3 k=3 k = 3 k = 4 k=4 k = 4
保罗·爱尔特希
研究前沿 截至 2026 年
正则化/超图方法证明了定理,但给出的 N ( k , δ ) N(k,\delta) N ( k , δ ) k k k 1 / δ 1/\delta 1/ δ k k k k = 3 k=3 k = 3 N ( 3 , δ ) ≲ exp ( − c ( log N ) 1 / 12 ) N N(3,\delta) \lesssim \exp\!\big(-c(\log N)^{1/12}\big) N N ( 3 , δ ) ≲ exp ( − c ( log N ) 1/12 ) N k ≥ 4 k \ge 4 k ≥ 4 k k k N ( k , δ ) N(k,\delta) N ( k , δ )
利用 d ( A ) = lim sup N → ∞ ∣ A ∩ [ 1 , N ] ∣ N d(A) = \limsup_{N \to \infty} \frac{|A \cap [1,N]|}{N} d ( A ) = lim sup N → ∞ N ∣ A ∩ [ 1 , N ] ∣ A A A d ( A ) d(A) d ( A )
0 1/2 1 未定义,因为比例会振荡
对于满足 d ( A ) > 0 d(A) > 0 d ( A ) > 0 A ⊆ Z + A \subseteq \mathbb{Z}^+ A ⊆ Z +
A 本身就是一个等差数列 A 包含任意有限长度的等差数列 A 必须是有限的 A 包含所有素数
为什么塞迈雷迪定理能推出关于有限染色的范德瓦尔登定理?
二者是不相关的结果 在有限颜色下,鸽笼原理给出某个颜色类具有正密度,再由塞迈雷迪定理保证其中存在等差数列 范德瓦尔登定理更强,能推出塞迈雷迪定理 两个定理都要求集合密度为零
为什么不能直接应用塞迈雷迪定理来证明素数包含任意长度的等差数列?
由素数定理,素数密度为0,因此假设 d ( A ) > 0 d(A) > 0 d ( A ) > 0 素数不是整数 塞迈雷迪定理只对有限集合成立 素数中不可能存在等差数列