A Pseudo Upper Bound for the van der Waerden Function

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 2n 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) 2k is always a positive integer. We show that the probability that a random 2-coloring of [1, f(k) 2k] produces a monochromatic k-term arithmetic progression tends to 1 as k→∞. We call f(k) 2k a pseudo upper bound for the van der Waerden function. We also prove the “density version” of this result.