主题
Search

范德瓦尔登数

范德瓦尔登定理的一种形式指出，对于所有正整数 k 和 r，存在一个常数 n(r,k) 使得如果 n_0>=n(r,k) 且 {1,2,...,n_0} subset C_1 union C_2 union ... union C_r，那么某个集合 C_i 包含一个长度为 k 的等差数列。 n(r,k) 的最小可能值被称为范德瓦尔登数。 唯一已知的非平凡范德瓦尔登数总结在下表中。 如表所示，n(2,k) 的前几个值，对于 k=1, 2, ... 分别是 1, 3, 9, 35, 178, 1132, ... (OEIS A005346)，其中最后一个值是由 M. Kouril 和 J. L. Paul 于 2007 年发现的 (Kouril and Paul 2008)。

r\k3456
29351781132
327
476

Shelah (1988) 证明了范德瓦尔登数是原始递归函数。 已知

n(r,3)<=e^(r^(c_1))
(1)

且

n(r,4)<=e^(e^(e^(r^(c_2))))
(2)

对于某些常数 c_1 和 c_2。 1998 年，T. Gowers 宣布他已证明一般结果

n(r,k)<=e^(e^(r^(e^(e^(k+110)))))
(3)

(Gowers 2001)。 Berlekamp (1968) 表明，对于素数 p，

n(2,p+1)>p·2^p.
(4)

使用 Lovász 局部引理 的概率论证表明

n(r,k)>((r^k)/(erk))(1+o(1)).
(5)

Heule (2008) 给出了新的下界。

另请参阅

塞迈雷迪定理, 范德瓦尔登定理

此条目的部分内容由 Kevin O'Bryant 贡献

使用 Wolfram|Alpha 探索

参考文献

Berlekamp, E. A. "用于避免长等差数列的划分构造。" 加拿大数学公报 11, 409-414, 1968.Goodman, J. E. 和 O'Rourke, J. (编辑). 离散与计算几何手册。 Boca Raton, FL: CRC Press, p. 159, 1997.Gowers, W. T. "傅里叶分析与塞迈雷迪定理。" 载于国际数学家大会论文集，第 1 卷。 Doc. Math. 1998, Extra Vol. 1. 柏林, pp. 617-629, 1998. 可从 http://www.mathematik.uni-bielefeld.de/documenta/xvol-icm/Fields/Fields.html 在线获取。Gowers, W. T. "塞迈雷迪定理对长度为 4 的等差数列的新证明。" Geom. Funct. Anal. 8, 529-551, 1998.Gowers, W. T. "塞迈雷迪定理的新证明。" Geom. Func. Anal. 11, 465-588, 2001.Heule, M. J. H. "提高几率：范德瓦尔登数的新下界。" 2008 年 3 月 4 日。 http://www.st.ewi.tudelft.nl/sat/slides/waerden.pdf.Honsberger, R. 更多数学拾零。 Washington, DC: Math. Assoc. Amer., p. 29, 1991.Kouril, M.  和 Paul, J. L. "范德瓦尔登数 W(2,6) 为 1132。" 实验数学 17, 53-61, 2008.Shelah, S. "范德瓦尔登数的原始递归界限。" 美国数学会杂志 1, 683-697, 1988.Sloane, N. J. A. 序列 A005346/M2819，出自 "整数序列在线百科全书"。

在 Wolfram|Alpha 上被引用

范德瓦尔登数

请引用为

O'Bryant, Kevin 和 Weisstein, Eric W. "范德瓦尔登数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/vanderWaerdenNumber.html

学科分类