INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5(1) (2005), #A32

ON THE DEGREE OF REGULARITY OF GENERALIZED VAN DER WAERDEN TRIPLES

Jacob Fox

Massachusetts Institute of Technology, Cambridge, MA 02139, USA

                               licht@mit.edu

Radoš Radoičić

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

                           rados@math.rutgers.edu

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

Abstract

Let a and b be positive integers such that a ≤ b and (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 that y = ax+d and z = bx+2d for 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 a_{1}x_{1} + … + a_{n}x_{n} = 0 (a_{i}’s are nonzero integers) r-regular if every r-coloring of ℕ 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 a_{i}’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 integer k := k(n) such that every linear homogeneous equation a_{1}x_{1} +…+a_{n}x_{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 that k(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 integer d such that y = ax+d and z = bx+2d. The degree of regularity of 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 ℕ without x and y of the same color with αx ≤ y ≤ βx. Since r = ⌈log_{α} β⌉, then α^{r−1} < β. Let x_{1} > ∑_{k=0}^{r−2} α^{k}/(β − α^{r−1}) be a positive integer. For i > 1, set x_{i+1} = ⌈αx_{i}⌉. We have αx_{i} ≤ x_{i+1} < αx_{i} + 1. Repeatedly using the inequality x_{i+1} < αx_{i} + 1, we obtain x_{r} < α^{r−1}x_{1} + ∑_{k=0}^{r−2} α^{k}. Since we appropriately chose x_{1}, the last inequality yields x_{r} < βx_{1}. Hence, αx_{i} ≤ x_{j} ≤ βx_{i} for 1 ≤ i < j ≤ r, so x_{1}, …, x_{r} 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 ℤ_{r+1} such that there do not exist x and y of the same color with αx ≤ y ≤ βx. For every nonnegative integer n, integers in the interval [α^{n}, α^{n+1}) receive color n (mod r + 1). Within each interval, every pair of integers x and y have the same color, but y < αx. For monochromatic x and y from different intervals, with y > x, we have y > α^{r}x ≥ βx. Therefore, this (r + 1)-coloring of the integers has no monochromatic x and 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 < (\frac{2a+1}{a})y. Using Lemma 1 and noting a ≥ 1, we obtain

dor(a, 2a + 1) ≤ ⌈log_{2}(2 + \frac{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, (\frac{2a−2}{a})y < z < 2y. Using Lemma 1 and a ≥ 3, we obtain

dor(a, 2a − 2) ≤ ⌈log_{2− \frac{2}{a}} 2⌉.

We have 2 − \frac{2}{a} > \sqrt{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 v_{p}(n) denote the largest power of p that divides n. If n = 0, let v_{p}(n) = +∞.

Notice that v_{p}(m_{1}m_{2}) = v_{p}(m_{1}) + v_{p}(m_{2}) for every prime p, and integers m_{1} and m_{2}. 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_{1}, m_{2}, m_{3} are integers with v_{p}(m_{1}) ≤ v_{p}(m_{2}) ≤ v_{p}(m_{3}) and v_{p}(m_{1}) < v_{p}(m_{1} + m_{2} + m_{3}), then v_{p}(m_{1}) = v_{p}(m_{2}). Furthermore, if v_{p}(m_{3}) < v_{p}(m_{1} + m_{2} + m_{3}), then also v_{p}(m_{1} + m_{2}) = v_{p}(m_{3}).

Recall that if (x, y, z) is an (a, b)-triple, then (x, y, z) satisfies the equation (b − 2a)x + 2y − z = 0. Let t_{x} = b − 2a, t_{y} = 2, and t_{z} = −1 denote the coefficients of x, y, and z in this equation, respectively. We have three cases to consider, depending on t_{x}.

Case A. t_{x} is a multiple of 4.

Clearly, we have v_{2}(t_{x}) > v_{2}(t_{y}) = 1 > v_{2}(t_{z}) = 0. Let S = {v_{2}(t_{x}), v_{2}(t_{y}), v_{2}(t_{x})−v_{2}(t_{y})}, and let Γ(S) be the undirected Cayley graph of the group (ℤ, +) 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_{2}(n)), for every n ∈ ℕ. We claim that in the 4-coloring χ of ℕ there are no x, y, and z, all of the same color and v_{2}(t_{x}x + t_{y}y + t_{z}z) > min{v_{2}(t_{x}x), v_{2}(t_{y}y), v_{2}(t_{z}z)}. Indeed, otherwise (by Lemma 2) we have v_{2}(t_{x}x) = v_{2}(t_{y}y); or v_{2}(t_{x}x) = v_{2}(t_{z}z); or v_{2}(t_{y}y) = v_{2}(t_{z}z). This implies v_{2}(y) − v_{2}(x) = v_{2}(t_{x}) − v_{2}(t_{y}); or v_{2}(z)−v_{2}(x) = v_{2}(t_{x}); or v_{2}(z)−v_{2}(y) = v_{2}(t_{y}). However, this contradicts that χ′ is a proper coloring of Γ(S) and v_{2}(x), v_{2}(y), and v_{2}(z) are all of the same color.

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

Case B. t_{x} has an odd prime factor p.^{1}

In this case we have v_{p}(t_{x}) > v_{p}(t_{y}) = v_{p}(t_{z}) = 0. Let d = v_{p}(t_{x}). We construct a 6-coloring χ that is a product of a 2-coloring χ_{1} and a 3-coloring χ_{2}. For n ∈ ℕ define χ_{1}(n) ≡ ⌊\frac{v_{p}(n)}{d}⌋ (mod 2). The coloring χ_{1}(n) colors intervals of v_{p} values of length d, open on one side, periodically in 2 colors with period 2. Let Γ be the undirected Cayley graph on ℤ_{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 χ′_{2} : V (Γ) → {0, 1, 2}. For n ∈ ℕ define χ_{2}(n) = χ′_{2}(m mod p), where n = mp^{v_{p}(n)}. Finally, for 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 χ of ℕ there are no x, y, and z, all of the same color and v_{p}(t_{x}x+t_{y}y+t_{z}z) > max{v_{p}(t_{x}x), v_{p}(t_{y}y), v_{p}(t_{z}z)}. Indeed, otherwise (by Lemma 2) we have v_{p}(t_{x}x) = v_{p}(t_{y}y) ≤ v_{p}(t_{z}z); or v_{p}(t_{x}x) = v_{p}(t_{z}z) ≤ v_{p}(t_{y}y); or v_{p}(t_{y}y) = v_{p}(t_{z}z) ≤ v_{p}(t_{x}x). If v_{p}(t_{x}x) = v_{p}(t_{y}y), then d + v_{p}(x) = v_{p}(y), hence, χ_{1}(x) ≠ χ_{1}(y), which contradicts χ(x) = χ(y). If v_{p}(t_{x}x) = v_{p}(t_{z}z), then d + v_{p}(x) = v_{p}(z), hence, χ_{1}(x) ≠ χ_{1}(z), which contradicts χ(x) = χ(z). So, assume that v_{p}(t_{y}y) = v_{p}(t_{z}z) ≤ v_{p}(t_{x}x). Recalling our coefficients, we obtain v_{p}(y) = v_{p}(z) ≤ d + v_{p}(x). By (the second part of) Lemma 2, we also have v_{p}(2y − z) = d + v_{p}(x). Let e denote the common value of v_{p}(y) and v_{p}(z). Let y = y′p^{e} and z = z′p^{e}. Since χ_{2}(y) = χ_{2}(z), then χ′_{2}(y′ mod p) = χ′_{2}(z′ mod p), hence, 2y′ − z′ ≢ 0 (mod p). However, this implies v_{p}(2y − z) = e, so v_{p}(y) = v_{p}(z) = e = d + v_{p}(x). It follows from here that χ_{1}(x) is different from χ_{1}(y) and χ_{1}(z), which contradicts χ(x) = χ(y) = χ(z).

Since v_{p}(0) = +∞ and there are no x, y, z, all of the same color and v_{p}(t_{x}x+t_{y}y +t_{z}z) > max{v_{p}(t_{x}x), v_{p}(t_{y}y), v_{p}(t_{z}z)}, then, in particular, there are no monochromatic solutions to t_{x}x + t_{y}y + t_{z}z = 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. t_{x} ∈ {−2, −1, 1, 2}

Case t_{x} = −1 is taken care of in [10], as mentioned before, while cases t_{x} = 1 and t_{x} = −2 correspond to Cases 1 and 2, respectively. The only remaining case is t_{x} = 2.^{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_{2} 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] independently 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édi’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édi’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, Probability, and Computing, 12 (2003) 571–583.

[10] B. M. Landman and A. Robertson, On generalized van der Waerden triples, Discrete Mathematics 256 (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édi, 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.