A Pseudo Upper Bound for the van der Waerden Function

✍ Scribed by Tom C. Brown

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 89 KB
• Volume: 87
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1998.2936

✦ Synopsis

For each positive integer n, let the set of all 2-colorings of the interval [1, n]= [1, 2, ..., n] be given the uniform probability distribution, that is, each of the 2 n colorings is assigned probability 2 &n . Let f be any function such that f (k)Âlog k Ä as k Ä . For convenience we assume that f (k) 2 k is always a positive integer. We show that the probability that a random 2-coloring of [1, f (k) 2 k ] produces a monochromatic k-term arithmetic progression tends to 1 as k Ä . We call f (k) 2 k a pseudo upper bound for the van der Waerden function. We also prove the ``density version'' of this result.

1999 Academic Press 81000 (see [4]) for a proof that w(k)<2 2 . . . 2 , a tower of height k. Let f be any function such that f (k)Âlog k Ä as k Ä . For convenience we assume that f (k) 2 k is always a positive integer.

In this note we show that ``almost all'' of the 2-colorings of [1, f (k) 2 k ] produce a monochromatic k-term arithmetic progression.