INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A29

ON THE GROWTH OF A VAN DER WAERDEN-LIKE FUNCTION

Ron Graham^{1}

Department of Computer Science & Engineering, University of California, San Diego.

Received: 8/7/06, Accepted: 10/1/06, Published: 10/13/06

Abstract

Let \overline{W} (3, k) denote the largest integer w such that there is a red/blue coloring of \{1, 2, …, w\} which has no red 3-term arithmetic progression and no block of k consecutive blue integers. We show that for some absolute constant c, \overline{W} (3, k) ≥ k^{c log k} for all k.

AMS Mathematics Subject Classification: 05D10

Keywords: van der Waerden function

1. Introduction

A classic theorem of van der Waerden [13], [8] asserts that for all k and r, there is a least integer W_{r}(k) such that any r-coloring of [W_{r}(k)] := {1, 2, …, W_{r}(k)} contains a monochromatic k-term arithmetic progression (k -AP). The true order of growth of W_{r}(k) (and especially W (k) := W_{2}(k)) has attracted the interest of many researchers since van der Waerden’s theorem first appeared in 1927 ([1], [3], [4], [6], [7], [11], [12]). The best current upper bound on W (k) is the striking result of Gowers [7]:

W (k) < 2^{2^{2^{2^{2^{k+9}}}}} .

On the other hand, the best lower bound available is due to Berlekamp in 1968 ([3]), and asserts that

W (p + 1) ≥ p 2^{p}

for p prime.

In order to obtain a better understanding of W (k), it is natural to study the so-called “off-diagonal” van der Waerden number W (k, l), which is defined to be the least integer w such that any red/blue coloring of [w] either has a red k -AP or a blue l -AP.

1Research supported in part by NSF Grant CCR-0310991

A complete list of the known values of W (k, l) appears in the recent paper of Landman, Robertson and Culver [10]. In particular, they have computed the following values of W (3, k):

\begin{matrix}k & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ W (3, k) & 6 & 18 & 22 & 32 & 46 & 58 & 77 & 97 & 114 & 135 & 160 \end{matrix}

In [10], it is suggested that W (3, k) might be bounded by some polynomial in k (perhaps even a quadratic!). We don’t resolve this question here. Instead we study the related function \overline{W} (3, k), defined to be the least integer w such that any red/blue coloring of [w] either has a red 3-AP or a block of k consecutive blue integers. Since a block of k consecutive integers is a k -AP, then we have \overline{W} (3, k) ≥ W (3, k).

What we show in this note is that \overline{W} (3, k) grows faster than any polynomial in k.

We note that the function \overline{W} (3, k) is closely related to the function Γ_{k}(3) discussed in Nathanson [11] as well as Landman and Robertson [9]. This is defined to be the least integer t such that any sequence x_{1} < x_{2} < ⋯ < x_{t} with x_{i+1} − x_{i} ≤ k for 1 ≤ i ≤ t − 1 must contain a 3 -AP. Since it is easy to show that \overline{W} (3, k) ≤ k Γ_{k}(3), then our result also gives non-polynomial growth bounds to this function as well.

2. The Main Result

Theorem. For all m > 0,

\overline{W} (3, 3m) ≥ 2m (W_{r_{3}(m)}(3) − 1).

where r_{3}(m) is defined by

r_{3}(m) = max_{S⊆[m]}{|S| : S has no 3 -AP}.

Proof. By definition, there is a set S(m) = {s_{1}, s_{2}, …, s_{r}} ⊆ [m] with no 3 -AP, where r = r_{3}(m). Also, by definition, with w := W_{r}(3) − 1, there is an r-coloring χ : [w] → [r] with no monochromatic 3 -AP. Let I_{k} denote the interval {2(k − 1)m + 1, …, (2k − 1)m} for 1 ≤ k ≤ w.

For 1 ≤ k ≤ w, select the element

x_{k} = 2(k − 1)m + s_{χ(k)}.

In other words, thinking of each I_{k} as a copy of [m], x_{k} corresponds to

s_{χ(k)} ∈ S(m) = {s_{1}, …, s_{r}} ⊆ [m].

We claim that the set X = {x_{1}, x_{2}, …, x_{w}} contains no 3 -AP. Suppose to the contrary that x_{i}, x_{j} and x_{k}, i < j < k, form a 3 -AP. Thus,

x_{i} ∈ I_{i} = [2(i − 1)m + 1, (2i − 1)m],
x_{j} ∈ I_{j} = [2(j − 1)m + 1, (2j − 1)m],
x_{k} ∈ I_{k} = [2(k − 1)m + 1, (2k − 1)m].

Therefore,

2(j − 1)m + 1 − (2i − 1)m ≤ x_{j} − x_{i} ≤ (2j − 1)m − 2(i − 1)m − 1,
2(k − 1)m + 1 − (2j − 1)m ≤ x_{k} − x_{j} ≤ (2k − 1)m − 2(j − 1)m − 1,

i.e.,

2(j − i)m − m + 1 ≤ x_{j} − x_{i} ≤ 2(j − i)m + m − 1,
2(k − j)m − m + 1 ≤ x_{k} − x_{j} ≤ 2(k − j)m + m − 1.

However, since x_{i}, x_{j} and x_{k} form a 3 -AP then x_{j}−x_{i} = x_{k}−x_{j}. This implies that j−i = k−j, i.e., i, j and k form a 3 -AP. Furthermore, since

x_{i} = 2(i − 1)m + s_{χ(i)},
x_{j} = 2(j − 1)m + s_{χ(j)},
x_{k} = 2(k − 1)m + s_{χ(k)},

then we can conclude that s_{χ(i)}, s_{χ(j)} and s_{χ(k)} form a 3 -AP. However, by definition, S has no non-trivial 3 -AP. Hence, the only possibility is that s_{χ(i)} = s_{χ(j)} = s_{χ(k)}, which implies χ(i) = χ(j) = χ(k). Thus, i, j and k form a monochromatic 3 -AP, which is a contradiction.

Note that since every interval I_{k} contains a point of X, then the difference between consecutive terms of X is less than 3m.

Finally, define the red/blue coloring χ^{∗} : [2mw] → {red, blue} by:

χ^{∗}(i) = \{ \begin{matrix}red : & if i = x_{k} for some k, \\ blue : & otherwise. \end{matrix}

Thus, χ^{∗} has no red 3 -AP and no blue 3m -block. Therefore,

\overline{W} (3, 3m) > 2mw = 2m(W_{r}(3) − 1) = 2m(W_{r_{3}(m)}(3) − 1)

and the theorem is proved. □

Corollary. For some absolute constant c,

\overline{W} (3, k) > k^{c log k}.

Proof. It is known [8] that

W_{k}(3) > k^{c_{1} log k}

for a suitable constant c_{1} > 0. Also, it is known [2] that

r_{3}(k) > k exp(−c_{2}\sqrt{log k})

for a suitable constant c_{2} > 0. Thus,

W_{r_{3}(k)}(3) > r_{3}(k)^{c_{1} log r_{3}(k)}
= exp(c_{1} log^{2}(r_{3}(k)))
> exp(c_{1}(log k − c_{2}\sqrt{log k})^{2})
> exp((c_{1}/2) log^{2} k)
= k^{(c_{1}/2) log k}

for k > k_{0}(c_{2}) sufficiently large. Now setting m = k/3 in the preceding theorem (together with a little algebra) gives the desired inequality. This completes the proof. □

3. Concluding Remarks.

The best available upper bound on \overline{W} (3, k) comes from the upper bound estimate on r_{3}(k) due to Bourgain [5]:

r_{3}(k) = O(k\sqrt{\frac{log log k}{log k}} ).

Using this estimate, we can obtain an upper bound for \overline{W} (3, k) as follows. First, suppose [N] is red/blue-colored, and let x_{1} < x_{2} < ⋯ < x_{t} denote the red integers in [N]. Hence, by Bourgain’s estimate, if t > cN\sqrt{\frac{log log N}{log N}} for a sufficiently large c, then we have a red 3 -AP. If not, then we must have

x_{i+1} − x_{i} > c′ \sqrt{\frac{log N}{log log N}}

for some i and suitable constant c′. Hence, if N > k^{ck^{2}} for a suitable constant c, then the RHS is greater than k, i.e., we have a block of k consecutive blue integers. This shows that \overline{W} (3, k) < k^{ck^{2}} for a suitable constant c > 0.

Whether this is close to the true behavior of \overline{W} (3, k), and whether our result suggests that the function W (3, k) is also non-polynomial, we leave for the reader to decide.

The author would like to thank Steve Butler, Fan Chung, and Bruce Landman for useful comments in preparing the final version of this note.

References

[1] N. Alon and A. Zaks, Progessions in sequences of nearly consecutive integers, J. Combin. Theory, Ser. A 84 (1998), 99–109.

[2] F. A. Behrend, On sets of integers which contain no three in arithmetic progression, Proc. Nat. Acad. Sciences 32 (1946), 331–332.

[3] E. R. Berlekamp, A construction for partitions which avoid long arithmetic progressions, Canad. Math. Bull. 11 (1968), 409–414.

[4] T. C. Brown and D. R. Hare, Arithmetic progressions in sequences with bounded gaps, J. Combin. Theory, Ser. A 77 (1997), 222–227.

[5] J. Bourgain, On triples in arithmetic progression, Geom. Funct. Anal. 9 (1999), 968–984.

[6] P. Erdős and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.

[7] W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), 465–588.

[8] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory. Second edition. John Wiley & Sons, Inc., New York, (1990), xii+196 pp.

[9] B. Landman and A. Robertson, Ramsey Theory on the Integers. Amer. Math. Soc., Providence, R.I., (2004), xvi+317pp.

[10] B. Landman, A. Robertson and C. Culver, Some new exact van der Waerden numbers, Integers 5 (2005), A10, 11pp.

[11] M. B. Nathanson, Arithmetic progressions contained in sequences with bounded gaps, Canad. Math. Bull. 23 (1980), 491–493.

[12] S. Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1988), 683–697.

[13] B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wiskunde 15 (1927), 212–216.