In 1927, van der Waerden [15] proved that every finite coloring of the positive integers contains arbitrarily long monochromatic arithmetic progressions

ON THE DEGREE OF REGULARITY OF GENERALIZED VAN DER WAERDEN TRIPLES

Jacob Fox

Massachusetts Institute of Technology, Cambridge, MA 02139, USA

[email protected] Radoˇs Radoiˇci´c

Department of Mathematics, Rutgers, The State University of New Jersey, Piscataway, NJ 08854, USA

[email protected]

Received: 6/9/05, Accepted: 11/28/05, Published: 12/13/05

Abstract

Letaandbbe positive integers such thata≤band (a, b)"= (1,1). We prove that there exists a 6-coloring of the positive integers that does not contain a monochromatic (a, b)-triple, that is, a triple (x, y, z) of positive integers such thaty=ax+dandz =bx+ 2dfor some positive integer d. This confirms a conjecture of Landman and Robertson.

1. Introduction

In 1916, Schur [13] proved that for every finite coloring of the positive integers there is a monochromatic solution to x+y = z. In 1927, van der Waerden [15] proved that every finite coloring of the positive integers contains arbitrarily long monochromatic arithmetic progressions. Rado’s 1933 thesis [12] was a seminal work in Ramsey theory, generalizing the earlier theorems of Schur and van der Waerden. Rado called a linear homogenous equation a1x1 +. . .+anxn = 0 (ai’s are nonzero integers) r-regular if every r-coloring of N contains a monochromatic solution to that equation. An equation is regular if it is r-regular for all positive integers r. Rado’s theorem for a linear homogeneous equation states that an equation is regular if and only if a non-empty subset of ai’s sums to 0. Rado also made a conjecture [12] that further differentiates between those linear homogeneous equations that are regular and those that are not.

Conjecture 1 (Rado’s Boundedness Conjecture, 1933) For every positive integer n, there exists an integerk :=k(n)such that every linear homogeneous equation a₁x₁+. . .+a_nx_n = 0 that is k-regular must be regular as well.

This outstanding conjecture has remained open except in the trivial cases (n = 1,2) until recently, when the first author and Kleitman settled the first nontrivial case n = 3 [4], [9].

They proved thatk(3) ≤24.

Van der Waerden’s theorem has been strengthened and generalized in numerous other ways [1], [2], [6], [7], [8], [11], [14]. In this note, we consider one of the generalizations, proposed by Landman and Robertson in [10].

Let a and b be positive integers such that a ≤b. A triple (x, y, z) of positive integers is called an (a, b)-triple if there exists a positive integerdsuch thaty=ax+dandz =bx+ 2d.

Thedegree of regularityof an (a, b)-triple, denoted by dor(a, b), is the largest positive integer r, if it exists, such that for every r-coloring of the positive integers there is a monochromatic (a, b)-triple. If no such r exists, that is, for every finite coloring of the positive integers there is a monochromatic (a, b)-triple, then set dor(a, b) = ∞. Note that van der Waerden’s theorem for 3-term arithmetic progressions is equivalent to dor(1,1) =∞.

Landman and Robertson proved that dor(a, b) = 1 if and only if b = 2a. They also showed that dor(a,2a −1) = 2 for a ≥ 2. For small values of a and b, they provide few additional results:

dor(1,3)≤3, dor(2,2)≤5, dor(2,5)≤3, dor(2,6)≤3, dor(3,3)≤5, dor(3,4)≤5, dor(3,8)≤3, dor(3,9)≤3.

Finally, they conjectured that if (a, b)"= (1,1), then dor(a, b) is finite [10], [11].

We confirm and further strengthen their conjecture.

Theorem 1 If (a, b)"= (1,1), then dor(a, b)<6.

Our proof that dor(a, b) is finite uses Rado’s theorem for a homogenous linear equation.

Proving a specific upper bound of 6, regardless of parameters a and b, relies on the above mentioned proof of Fox and Kleitman [4].

2. Proof of Theorem 1

First, notice that if (x, y, z) is an (a, b)-triple, then (x, y, z) satisfies the equation

−(b−2a)x−2y+z = 0.

By Rado’s theorem [12], this equation is regular if and only if b ∈ {2a−2,2a−1,2a+ 1}. Therefore, if b−2a "∈ {−2,−1,1}, then dor(a, b) is finite. Moreover, since k(3) ≤ 24 [4], if b−2a "∈ {−2,−1,2}, then dor(a, b)≤23. As mentioned in the introduction, Landman and Robertson [10] proved that dor(a,2a−1) = 2 for a≥2.

For the remaining cases, we use Lemma 1, which is stated and proved next.

Lemma 1 Let α and β be real numbers such that 1 < α < β. Set r = 'log_αβ(. Then every r-coloring of the positive integers contains integers x and y of the same color with αx ≤ y ≤ βx. Moreover, there is an (r+ 1)-coloring of the positive integers that contains no integers x and y of the same color with αx≤y≤βx.

Proof. Consider a coloring of N without x and y of the same color with αx ≤ y ≤ βx.

Since r ='log_αβ(, then α^r−1 < β. Let x₁ >!r−2

k=0α^k/(β−α^r−1) be a positive integer. For i > 1, set xi+1 = 'αxi(. We have αxi ≤ xi+1 < αxi + 1. Repeatedly using the inequality xi+1 < αxi+ 1, we obtainxr < α^r−1x1+!r−2

k=0α^k. Since we appropriately chose x1, the last inequality yields xr < βx1. Hence, αxi ≤xj ≤βxi for 1 ≤i < j ≤r, sox1, . . . , xr must all have different colors. Therefore, the number of colors is at least r+ 1.

Next, we construct a coloring of the positive integers by the elements of Zr+1 such that there do not existxandyof the same color withαx ≤y ≤βx. For every nonnegative integer n, integers in the interval [αⁿ, αⁿ⁺¹) receive color n (modr+ 1). Within each interval, every pair of integers x and y have the same color, buty < αx. For monochromatic xand y from different intervals, withy > x, we havey > α^rx≥βx. Therefore, this (r+ 1)-coloring of the integers has no monochromatic xand y such thatαx≤y ≤βx. !

Now, we continue with the proof of Theorem 1. We have two cases.

Case 1. b= 2a+ 1.

In this case, we have y =ax+d and z = (2a+ 1)x+ 2d. Therefore, 2y < z <(^2a+1_a )y.

Using Lemma 1 and noting a≥1, we obtain

dor(a,2a+ 1)≤ 'log₂(2 + 1

a)(= 2.

Hence, for all positive integers a, we have dor(a,2a+ 1) = 2.

Case 2. b= 2a−2.

Since b must be a positive integer, then a ≥ 2. As mentioned in the introduction, Landman and Robertson [10] proved that dor(2,2) ≤ 5. If a > 2, then y = ax+d and z = (2a−2)x+ 2d. So, (^2a−2_a )y < z <2y. Using Lemma 1 and a≥3, we obtain

dor(a,2a−2)≤ 'log₂₋²

a 2(. We have 2 − ²_a > √

2 when a > 3. Therefore, 2 ≤ dor(a,2a − 2) ≤ 3 for a = 3 and dor(a,2a−2) = 2 for a >3.

At this stage, we have dor(a, b) < 24, whenever (a, b) "= (1,1). Next, we improve the upper bound using some sophisticated tools from the paper of Fox and Kleitman [4]. For the sake of completeness and clarity, we repeat some of their analysis that applies in our context. We need the following bit of notation.

Definition: Let p be a prime number. For every integer n, let vp(n) denote the largest power of p that divides n. If n= 0, let vp(n) = +∞.

Notice that vp(m1m2) = vp(m1) +vp(m2) for every prime p, and integers m1 and m2. The following straightforward lemma (Lemma 3 in [4]) gives basic properties of the function v_p, which we will repeatedly use.

Lemma 2 If m₁, m₂, m₃ are integers with v_p(m₁) ≤ v_p(m₂) ≤ v_p(m₃) and v_p(m₁) <

vp(m1+m2+m3), then vp(m1) =vp(m2). Furthermore, if vp(m3)< vp(m1+m2+m3), then also vp(m1+m2) =vp(m3).

Recall that if (x, y, z) is an (a, b)-triple, then (x, y, z) satisfies the equation (b−2a)x+ 2y−z = 0. Lettx =b−2a,ty = 2, and tz =−1 denote the coefficients ofx,y, andz in this equation, respectively. We have three cases to consider, depending on tx.

Case A. t_x is a multiple of 4.

Clearly, we havev2(tx)> v2(ty) = 1> v2(tz) = 0. LetS ={v2(tx), v2(ty), v2(tx)−v2(ty)}, and let Γ(S) be the undirected Cayley graph of the group (Z,+) with generators being the elements of S. Since every vertex of Γ(S) has degree 2|S|, there exists a proper (greedy) (|S|+1)-coloringχ^" of its vertices. This result is “folklore” and we refer the reader to Lemma 2 in [4] for details. Now, define χ(n) = χ^"(v₂(n)), for every n ∈ N. We claim that in the 4-coloring χ of N there are no x, y, and z, all of the same color and v2(txx+tyy+tzz) >

min{v2(txx), v2(tyy), v2(tzz)}. Indeed, otherwise (by Lemma 2) we have v2(txx) = v2(tyy);

or v2(txx) = v2(tzz); or v2(tyy) = v2(tzz). This implies v2(y)−v2(x) = v2(tx)−v2(ty); or v2(z)−v2(x) =v2(tx); orv2(z)−v2(y) =v2(ty). However, this contradicts thatχ^" is a proper coloring of Γ(S) and v2(x), v2(y), and v2(z) are all of the same color.

Since v2(0) = +∞, by definition, and since there are no x, y, z, all of the same color and v₂(t_xx+t_yy+t_zz) > min{v₂(t_xx), v₂(t_yy), v₂(t_zz)}, then, in particular, there are no monochromatic solutions to txx+tyy+tzz = 0 (i.e. (b−2a)x+ 2y−z = 0) in χ. Case A is equivalent to Lemma 4 (with p= 2) in [4].

Case B. tx has an odd prime factorp.¹

In this case we have vp(tx) > vp(ty) = vp(tz) = 0. Let d = vp(tx). We construct a 6-coloring χ that is a product of a 2-coloring χ1 and a 3-coloring χ2. For n ∈ N define χ1(n) ≡ +^vp_d⁽ⁿ⁾, (mod 2). The coloring χ1(n) colors intervals of vp values of length d, open on one side, periodically in 2 colors with period 2. Let Γ be the undirected Cayley graph on Z^p \ {0} such that (u, v) is an edge of Γ if and only if u−2v ≡ 0 (mod p) or 2u−v ≡0 (mod p). Since every vertex of Γ has degree 2, there exists a proper 3-coloring

χ^"₂ :V(Γ)→ {0,1,2}. For n ∈N define χ₂(n) =χ^"₂(m modp), where n =mp^vp(n). Finally,

for n∈N define χ(n) = (χ1(n), χ2(n)).

1Note that Cases A and B overlap. However, it is only important that Cases A, B, and C cover all the possibilities.

We claim that in the 6-coloringχ ofN there are nox,y, andz, all of the same color and vp(txx+tyy+tzz)>max{vp(txx), vp(tyy), vp(tzz)}. Indeed, otherwise (by Lemma 2) we have vp(txx) =vp(tyy) ≤ vp(tzz); or vp(txx) = vp(tzz) ≤ vp(tyy); or vp(tyy) = vp(tzz) ≤ vp(txx).

If vp(txx) = vp(tyy), then d +vp(x) = vp(y), hence, χ1(x) "= χ1(y), which contradicts χ(x) = χ(y). If vp(txx) = vp(tzz), then d+vp(x) = vp(z), hence, χ1(x) "= χ1(z), which contradicts χ(x) = χ(z). So, assume that vp(tyy) = vp(tzz) ≤ vp(txx). Recalling our coefficients, we obtainv_p(y) = v_p(z)≤d+v_p(x). By (the second part of) Lemma 2, we also havevp(2y−z) = d+vp(x). Lete denote the common value ofvp(y) and vp(z). Lety =y^"p^e

and z = z^"p^e. Since χ2(y) = χ2(z), then χ^"₂(y^" mod p) = χ^"₂(z^" modp), hence, 2y^" −z^" "≡ 0

(mod p). However, this implies vp(2y−z) =e, sovp(y) =vp(z) =e=d+vp(x). It follows from here thatχ1(x) is different fromχ1(y) andχ1(z), which contradictsχ(x) =χ(y) = χ(z).

Sincev_p(0) = +∞and there are nox,y,z, all of the same color andv_p(t_xx+t_yy+t_zz)>

max{vp(txx), vp(tyy), vp(tzz)}, then, in particular, there are no monochromatic solutions to txx+tyy+tzz = 0 (i.e. (b−2a)x+ 2y−z = 0) in χ. Case B is essentially equivalent to Lemma 6 (with s= 1) in [4].

Notice that one can define χ2 to be a 2-coloring in the proof above, as long as the order of 2 mod p is even.

Case C. tx ∈ {−2,−1,1,2}

Case tx = −1 is taken care of in [10], as mentioned before, while cases tx = 1 and tx = −2 correspond to Cases 1 and 2, respectively. The only remaining case istx = 2.² In this case, we have y = ax+d and z = (2a + 2)x+ 2d. Therefore, 2y < z < 4y. Using Lemma 1, we obtain dor(a,2a+ 2) ≤ 'log₂4( = 2. Hence, for all positive integers a, we

have dor(a,2a+ 2) = 2. !

3. Concluding remarks

As a consequence of our proof, we obtained

dor(1,3) = 2, dor(2,5) = 2, dor(2,6) = 2, dor(3,3)≤3, dor(3,4)≤3, dor(3,8) = 2.

These results improve the corresponding entries in the table provided by Landman and Robertson [10] for small values of a and b.

After submission, we learned that Frantzikinakis, Landman, and Robertson [5] indepen- dently showed that dor(a, b) is finite unless (a, b) = (1,1).

2The equation is not regular in this case, however this possibility is not covered by Cases A and B of the improved upper bound analysis.

References

[1] V. Bergelson and A. Leibman, Polynomial extensions of van der Waerden’s and Szemer´edi’s theorems, J. Amer. Math. Soc.9(1996) 725–753.

[2] T. C. Brown, R. L. Graham, and B. M. Landman, On the set of common differences in van der Waerden’s theorem on arithmetic progressions, Canad. Math. Bull.42(1999), 25–36.

[3] T. C. Brown, B. M. Landman, and M. Mishna, Monochromatic homothetic copies of{1,1 +s,1 +s+t}, Canadian Math. Bull.40(1997), 149–157.

[4] J. Fox and D. Kleitman, On Rado’s Boundedness Conjecture, Journal of Combinatorial Theory, Series A, accepted.

[5] N. Frantzikinakis, B. Landman, A. Robertson, On the degree of regularity of generalized van der Waerden triples, Advances in Applied Math., accepted.

[6] H. Furstenberg,Recurrences in Ergodic Theory and Combinatorial Number Theory. Princeton University Press, Princeton, 1981.

[7] T. Gowers, A new proof of Szemer´edi’s theorem,Geometric and Functional Analysis,11(2001) 465–588.

[8] R. L. Graham, B. L. Rothschild, and J. Spencer, Ramsey Theory. John Wiley & Sons Inc., New York, 1990.

[9] N. Hindman, I. Leader, and D. Strauss, Open problems in partition regularity, Combinatorics, Proba- bility, and Computing,12(2003) 571–583.

[10] B. M. Landman and A. Robertson, On generalized van der Waerden triples, Discrete Mathematics256 (2002) 279–290.

[11] B. M. Landman and A. Robertson, Ramsey theory on the integers. Student Mathematical Library, 24.

American Mathematical Society, Providence, RI, 2004. (Research Problem 5.4, p. 159.) [12] R. Rado, Studien zur Kombinatorik, Math. Zeit.36(1933) 242–280.

[13] I. Schur, Uber die Kongruenze x^m+y^m ≡ z^m (mod p), Jber. Deutsch. Math.-Verein. 25 (1916), 114–117.

[14] E. Szemer´edi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199–245.

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