On sets of integers containing k elements in arithmetic progression
On sets of integers containing k elements in arithmetic progression
复制标题
DOI：
10.4064/aa-27-1-199-245
复制
发表时间：
1975
期刊：
影响因子：
0.7
通讯作者：
E. Szemerédi
中科院分区：
文献类型：
--
作者：
E. Szemerédi
1926年，van der Waerden[13]证明了以下惊人的定理：如果整数集合被任意划分为两类，那么至少有一类包含任意长的等差数列。众所周知，这两类都不能包含无限等差数列。事实上，很容易看出，对于任何数列an，存在另一个数列bn9，其中bn > an9不包含三个等差数列，但它与每个无限等差数列相交。van der Waerden定理的有限形式如下：对于每一个正整数n9，存在一个最小整数f{n)，其性质是：如果从1到/(/?)的整数被任意划分为两类，则至少有一个类包含«项的等差数列。（有关简短的证明，请参阅格雷厄姆和罗斯柴尔德的笔记。）然而，目前已知的f (n)的最佳上界是极差的。由于Berlekamp[3]，已知的最佳下界断言/（«）< nl9对于n素数，这改进了Erdös， Rado和W. Schmidt的先前结果。40多年前，Erdös和tur<s:1>[4]认为数量rk{n)9定义为存在整数序列0 < a\ < a2 <••••< a的最大整数/；^ n不包含k项的等差数列。他们对rk (n)的研究是由几件事引起的。首先，估计rk (n)的问题本身就很有趣。其次，rk{n) < n/2意味着f{k) < 77，即他们希望通过研究rk{n)来改善f{k)的穷上界。最后，数论中的一个老问题是，是否存在任意长的素数等差数列。从rk{n) < %{rì)，这将立即执行。希望这个质数问题可以被
In 1926 van der Waerden [13] proved the following startling theorem : If the set of integers is arbitrarily partitioned into two classes then at least one class contains arbitrarily long arithmetic progressions. It is well known and obvious that neither class must contain an infinite arithmetic progression. In fact, it is easy to see that for any sequence an there is another sequence bn9 with bn > an9 which contains no arithmetic progression of three terms, but which intersects every infinite arithmetic progression. The finite form of van der Waerden's theorem goes as follows: For each positive integer n9 there exists a least integer f{n) with the property that if the integers from 1 to /(/?) are arbitrarily partitioned into two classes, then at least one class contains an arithmetic progression of « terms. (For a short proof, see the note of Graham and Rothschild [5].) However, the best upper bound on f{n) known at present is extremely poor. The best lower bound known, due to Berlekamp [3], asserts that/(«) < nl9 for n prime, which improves previous results of Erdös, Rado and W. Schmidt. More than 40 years ago, Erdös and Turân [4] considered the quantity rk{n)9 defined to be the greatest integer / for which there is a sequence of integers 0 < a\ < a2 < ••• < a; ^ n which does not contain an arithmetic progression of k terms. They were led to the investigation of rk{n) by several things. First of all the problem of estimating rk{n) is clearly interesting in itself. Secondly, rk{n) < n/2 would imply f{k) < 77, i.e., they hoped to improve the poor upper bound on f{k) by investigating rk{n). Finally, an old question in number theory asks if there are arbitrarily long arithmetic progressions of prime numbers. From rk{n) < %{rì) this would follow immediately. The hope was that this problem on primes could be attacked not by