范德瓦尔登定理 (van der Waerden's theorem) 的证明在之前Euler老师的帖子里面有介绍
https://tieba.baidu.com/p/9674514370
定理中n(k,l)能取的最小可能值可以记作W(k,l), 而当k=2时, 对给定的正整数a,b, 可以更具体地把满足以下条件的最小正整数n记作w(2;a,b), 或者简记为w(a,b):
只要将{1,2,…,n}划分成A,B两个不交子集的并集, 那要么A中含有长为a的算术级数, 要么B中含有长为b的算术级数 (*)
这样的定义明显满足w(a,b)=w(b,a), 并且当a=b=l时w(l,l)=W(2,l), 当a<b时, w(a,b)等价地相当于要求要么A,B中都有长为a的算术级数, 要么A,B中至少有一个含长为b的算术级数.
要确定某个w(a,b)的值等于m, 需要证明{1,2,…,m-1}存在不满足定义(*)要求的划分A,B, 并且证明{1,2,…,m}的任意划分都满足要求. 两者的构造基本都需要大量计算寻找, 但前者的验证比后者简单
另外对更大的k, 还可以类似地定义w(k; a_1, a_2 ,…, a_k), 其中a_1, a_2 ,…, a_k是大于1的整数. 要确定w(k; a_1, a_2 ,…, a_k)的值一般都很困难, 上世纪以来, 计算数论学家们的研究只确定了一些较小的情况下w的值, 并逐步改进了一般情况下w的上下界 (相差巨大)
其中如果a_1, a_2 ,…, a_k当中最多只有1个数大于2, 要确定w的值会相对简单, 而如果至少有2个大于2的数, 要确定w的值都可以称作非平凡, 其中k=2的非平凡情况就相当于w(a,b)当中a,b>2
这个帖子中w(a,b)的非平凡的已知结果整理自oeis的相关数列, 并且注明了最早记录对应数据的论文, 可能是因为这个问题研究年代跨度久远, 涉及领域也太广, 不同文献用的记号并不统一, 以至于oeis用的记号也有点混乱, 这个帖子里的w(a,b)是按照上面的定义(*), 后面的中括号表示发现者或最早出处
(只整理了k=2 (2染色)的情况, 如果能整理清楚的话帖子后面再补充一些k=3,k=4的已知结果)
https://tieba.baidu.com/p/9674514370
定理中n(k,l)能取的最小可能值可以记作W(k,l), 而当k=2时, 对给定的正整数a,b, 可以更具体地把满足以下条件的最小正整数n记作w(2;a,b), 或者简记为w(a,b):
只要将{1,2,…,n}划分成A,B两个不交子集的并集, 那要么A中含有长为a的算术级数, 要么B中含有长为b的算术级数 (*)
这样的定义明显满足w(a,b)=w(b,a), 并且当a=b=l时w(l,l)=W(2,l), 当a<b时, w(a,b)等价地相当于要求要么A,B中都有长为a的算术级数, 要么A,B中至少有一个含长为b的算术级数.
要确定某个w(a,b)的值等于m, 需要证明{1,2,…,m-1}存在不满足定义(*)要求的划分A,B, 并且证明{1,2,…,m}的任意划分都满足要求. 两者的构造基本都需要大量计算寻找, 但前者的验证比后者简单
另外对更大的k, 还可以类似地定义w(k; a_1, a_2 ,…, a_k), 其中a_1, a_2 ,…, a_k是大于1的整数. 要确定w(k; a_1, a_2 ,…, a_k)的值一般都很困难, 上世纪以来, 计算数论学家们的研究只确定了一些较小的情况下w的值, 并逐步改进了一般情况下w的上下界 (相差巨大)
其中如果a_1, a_2 ,…, a_k当中最多只有1个数大于2, 要确定w的值会相对简单, 而如果至少有2个大于2的数, 要确定w的值都可以称作非平凡, 其中k=2的非平凡情况就相当于w(a,b)当中a,b>2
这个帖子中w(a,b)的非平凡的已知结果整理自oeis的相关数列, 并且注明了最早记录对应数据的论文, 可能是因为这个问题研究年代跨度久远, 涉及领域也太广, 不同文献用的记号并不统一, 以至于oeis用的记号也有点混乱, 这个帖子里的w(a,b)是按照上面的定义(*), 后面的中括号表示发现者或最早出处
(只整理了k=2 (2染色)的情况, 如果能整理清楚的话帖子后面再补充一些k=3,k=4的已知结果)
