RAINBOW 3-TERM ARITHMETIC PROGRESSIONS

Veselin Jungić

Department of Mathematics, Simon Fraser University, Burnaby, B.C., Canada

                             vjungic@sfu.ca

Radoš Radoičić

Department of Mathematics, MIT, Cambridge, MA 02139, U.S.A.

                           rados@math.mit.edu

Received: 8/7/03, Revised: 11/17/03, Accepted: 11/20/03, Published: 11/20/03

Abstract

Consider a coloring of {1, 2, …, n} in 3 colors, where n ≡ 0 (mod 3). If all the color classes have the same cardinality, then there is a 3-term arithmetic progression whose elements are colored in distinct colors. This rainbow variant of van der Waerden’s theorem proves the conjecture of the second author.

1. Introduction

Given a coloring of a set of natural numbers, we say that a subset is monochromatic if all of its elements have the same color and we say that it is rainbow if all of its elements have distinct colors. A classical result in Ramsey theory is van der Waerden’s theorem [vW27], which states that for every k and t and sufficiently large n, every k-coloring of [n] := {1, 2, …, n} contains a monochromatic arithmetic progression of length t. Jungić et. al. [JLMNR] considered, for the first time in the literature, a rainbow counterpart of van der Waerden’s theorem. They proved that every 3-coloring of the set of natural numbers ℕ with the upper density of each color greater than 1/6 contains a rainbow AP(3). They also asked whether the “finite” version of their theorem also holds, and, backed by the computer evidence (n ≤ 56), posed the following conjecture.

Conjecture 1 For every n ≥ 3, every partition of [n] into three color classes R, G, and B with min(|R|, |G|, |B|) > r(n), where

r(n) := \{ \begin{matrix}⌊(n + 2)/6⌋ & if n ≢ 2 (mod 6) \\ (n + 4)/6 & if n ≡ 2 (mod 6) \end{matrix}  (1)

contains a rainbow AP (3).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A18 2

Moreover, they constructed a 3-coloring of [n] with min(|R|, |G|, |B|) = r(n), where r is the function defined in (1), that contains no rainbow AP (3). This shows that Conjecture 1, if true, is the best possible.

A weaker form of this conjecture, due to the second author, was posed at the open problem session of the 2000 MIT Combinatorics Seminar [JLMNR].

Conjecture 2 Let n ≡ 0 (mod 3). For every equinumerous 3-coloring of [n], that is, a coloring in which all color classes have the same cardinality, there exists a rainbow AP (3).

In this paper, we prove Conjecture 2.

2. Proof of Conjecture 2

Given a 3-coloring of [n] with colors Red (R), Green (G) and Blue (B), a B-block is a string of consecutive elements of [n] that are colored Blue. R-block and G-block are defined similarly. We say that the coloring is rainbow-free if it contains no rainbow AP (3).

First, we show that every rainbow-free 3-coloring contains a dominant color, that is, a color z ∈ {B, G, R} such that for every two consecutive numbers that are colored with different colors, one of them is colored with z. We will need the following two lemmata.

Lemma 1 Let c : [n] → {B, G, R} be a 3-coloring of [n] such that every two different colors appear next to each other. Then there exist p, r ∈ [n], p < r, such that

1. c(p) = c(r),

2. c(p + 1) ≠ c(p),

3. c(r − 1) ∉ {c(p), c(p + 1)}, and

4. no element in the interval [p + 1, r − 1] is colored by the color c(p).

Proof. Let G be the first color to appear and let the first G-block be followed by an R-block. Since G appears next to B, there exists a G-block that is next to a B-block. If this G-block is preceded by a B-block,

G … G R … R … B … B G … G …
↑  ↑
p  r

then the lemma follows. So, suppose that G, the first G-block that is next to a B-block, is preceded by an R-block and followed by a B-block B.

G … G R … R … R … R G … G B … B …
↑  ↑
G  B

Suppose there is a B-block between the two G-blocks. Consider the last such B-block and denote it by B′. The lemma immediately follows, since we can take p and r to be the last element of B′ and the first element of B.

Now, suppose there is no B-block between the two G-blocks.

If B is followed by an R-block, then the lemma clearly follows. So, let B be followed by a G-block. The same reasoning as above, combined with the assumption that R appears next to B, implies that one of the following two scenarios happens:

… G … G R … R G … G B … B R … R
↑  ↑  ↑
GB  p  r

or

… G … G B … B G … G R … R B … B
↑  ↑  ↑
GB  p  r

which completes the proof. □

Lemma 2 Let c : [n] → {B, G, R} be a 3-coloring of [n] such that

min{|c^{−1}(B)|, |c^{−1}(G)|, |c^{−1}(R)|} ≥ 5

and every two different colors appear next to each other. Then there is a rainbow AP (3).

Proof. By Lemma 1, we can assume that there are p, q, r, such that

… G R … R B … B G …
↑  ↑ ↑  ↑  ↑
p  R/B q  B  r
only  only

If q = p + 1 or q = r − 2 we are done. So, we assume that p + 2 ≤ q < r − 2, c(p) = G, c(p + 1) = R, c(q) = R, c(r) = G, c(i) = B for all q < i < r and c(j) ≠ G for all p + 1 < j < q. Since |c^{−1}(G)| ≥ 5, then p ≥ 3 or r ≤ n − 2. Without loss of generality, assume p ≥ 3.^{1} If r + q is even, then q, \frac{r+q}{2}, r is a rainbow AP (3). So, let r + q be odd. It follows that an even number of elements between q and r are colored by B. If c(q − 1) = R then q − 1, \frac{r+q−1}{2}, r is a rainbow AP (3). Let c(q − 1) = B and let s = min{i ∈ [p, q]|c(i) = B}. Then,

… G R … R B … B R B … B G …
↑ ↑ ↑ ↑ ↑ ↑ ↑
p only R s R/B  q only B r

even#

Notice that s could be equal to q − 1. Now, if p + s is even, then p, \frac{p+s}{2}, s is a rainbow AP (3). Otherwise, an even number of elements between p and s are colored by R. If c(p−1) = G, then p−1, \frac{p+s−1}{2}, s is a rainbow AP (3). So, let c(p−1) = R. If c(s+1) = B (here, s ≠ q − 1), then p, \frac{p+s+1}{2}, s + 1 is a rainbow AP (3). Hence, let c(s + 1) = R. Then, the interval [p − 1, r] is colored as follows.

… R G R … R B R … B R B … B G …
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
p − 1 p only R s s + 1  q only B r
even#  even#

Suppose that p + r − 1 is even. If c(\frac{p+r−1}{2}) = R, then p, \frac{p+r−1}{2}, r − 1 is a rainbow AP (3). If c(\frac{p+r−1}{2}) = B, then p − 1, \frac{p+r−1}{2}, r is a rainbow AP (3).

So, let p + r − 1 be odd. If c(p − 2) = B then p − 2, p − 1, p is a rainbow AP (3). Suppose c(p − 2) = R. If c(\frac{p+r−2}{2}) = R, then p, \frac{p+r−2}{2}, r − 2 is a rainbow AP (3). If c(\frac{p+r−2}{2}) = B, then p − 2, \frac{p+r−2}{2}, r is a rainbow AP (3). Hence, the only remaining case is when c(p − 2) = G.

… G  R G R … R B R … B R B … B G …
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
p − 2 p − 1 p onlyR s s + 1  q onlyB r
even#  even#

Since an even number of elements between q and r are colored by B, there exists k, 2 ≤ k < \frac{r−p}{2}, such that c(p + 2k) = B. Suppose that k is the smallest number with this property. Now, consider elements \frac{p+p+2k}{2} = p + k and \frac{p−2+p+2k}{2} = p + k − 1. By the property of k and the fact that one of the elements k, k − 1 is even, we conclude that either c(p + k) = R or c(p + k − 1) = R. Then, either p − 2, p + k − 1, p + 2k or p, p + k, p + 2k is a rainbow AP (3). □

1Otherwise, consider the coloring c′ : [n] → {B, G, R}, defined by c′(i) = c(n − i + 1) for every i ∈ [n].

Lemma 2 immediately implies

Corollary 1 Let c : [n] → {B, G, R} be a rainbow-free 3-coloring of [n] such that

min{|c^{−1}(B)|, |c^{−1}(G)|, |c^{−1}(R)|} ≥ 5.

Then there exists a dominant color.

Clearly, there can be only one dominant color

The following lemma will be instrumental in showing that in every rainbow-free 3coloring of [n] there exists a recessive color, that is, a color w ∈ {B, G, R} such that no two consecutive numbers are colored by w.

Lemma 3 Let c : [n] → {B, G, R} be a 3-coloring of [n] such that R is the dominant color. Suppose there exist i and j, so that i + 2 < j, c(i) = c(i + 1) = B, c(i + 2) = c(j − 1) = R, c(j) = c(j + 1) = G. Suppose also that the interval [i + 2, j − 1] does not contain two consecutive elements that are both colored by B or by G. Then, there is a rainbow AP (3).

Proof. Suppose there exists a rainbow-free coloring c with the properties above. Consider the interval [i, j + 1].

… BB R  …  R GG …
↑  ↑  ↑  ↑ ↑
i  i + 2 no BB, no GG j − 1 j

Suppose no element of [i + 3, j − 2] is colored by R. Since R is the dominant color, [i + 3, j − 2] is either a B-block or a G-block. Then, either i + 1, i + 2, i + 3 or j − 2, j − 1, j is a rainbow AP (3), contradicting the assumption that c is rainbow-free.

Suppose no element of [i + 3, j − 2] is colored by G. Since c(j) = G and c(j − 1) = R, then c(j − 2) = R. Since c(j + 1) = G and c(j − 1) = R, then c(j − 3) = R. Iterating this reasoning from right to left, we conclude that [i + 2, j − 1] is an R-block. Then, clearly, there exists a rainbow AP (3), and, thus, we arrive at a contradiction. A symmetric argument shows that at least one of the elements of [i + 3, j − 2] is colored by B.

Therefore, there is at least one element of each color in [i + 3, j − 2].

Suppose i + j + 1 is odd. Since R is the dominant color and there are no consecutive elements in [i + 3, j − 2] both colored by B or by G, at least one of the elements ⌊\frac{i+j+1}{2}⌋, ⌊\frac{i+j+1}{2}⌋ + 1 is colored by R. This implies that one of the arithmetic progressions

i, \frac{i + j}{2} = ⌊\frac{i + j + 1}{2}⌋ , j or i + 1, \frac{i + j + 2}{2} = ⌊\frac{i + j + 1}{2}⌋ + 1, j + 1

is a rainbow AP (3).

Therefore, if c is rainbow-free then i + j + 1 is even. It follows that c (\frac{i+j+1}{2}) ≠ R, otherwise, i, \frac{i+j+1}{2}, j is a rainbow AP (3).

If there exists i+2 < k < \frac{i+j+1}{2}, with c(k) = G, then c(2k −i) ≠ R and c(2k −i−1) ≠ R, otherwise i, k, 2k−i or i+1, k, 2k−i−1 is a rainbow AP (3). Since R is the dominant color, it follows that 2k−i and 2k−i−1 are both colored by B or by G, which contradicts the assumed property of i and j. Therefore, if c(k) = G, where i + 2 < k < j − 1, then k ≥ \frac{i+j+1}{2}.

A symmetric argument implies that if c(k) = B, i + 2 < k < j − 1, then k ≤ \frac{i+j+1}{2}.

Without loss of generality, assume that c (\frac{i+j+1}{2}) = G, the other case being symmetric. Then, interval [i, j + 1] is colored as follows.

… BB R  … RGR …  R GG …
↑  ↑  ↑  ↑  ↑  ↑ ↑
i  i + 2 no BB \frac{i+j+1}{2} no GG j − 1 j
no G  no B

Hence, there are no elements colored by G in [i, \frac{i+j−1}{2}] and there are no elements colored by B in [\frac{i+j+1}{2}, j + 1]. Since an element of each color appears in [i + 2, j − 1], there exists p ≥ 2 such that c (\frac{i+j+1}{2} − l) = R for all l ∈ [1, p] and c (\frac{i+j+1}{2} − p − 1) = B. Moreover, since c is rainbow-free, p must be even. It follows that c (\frac{i+j+1}{2} + p + 1) = G.

Let x = \frac{i+j+1}{2} −p−1 and y = \frac{i+j+1}{2} +p+1. Define intervals I_{s} = [a_{s}, b_{s}], J_{s} = [c_{s}, d_{s}], s ∈ [0, r−1], where a_{s} = i+2(sp+s+1), b_{s} = i+2((s+1)p+s)+1, c_{s} = j−2((s+1)p+s), d_{s} = j−2(sp+s+1)+1, and r is the smallest index such that 1 ≤ c_{r−1}−y = x−b_{r−1} ≤ 2p. Notice that the number of elements in each of these intervals is 2p.

For each l ∈ [p], the following two arithmetic progressions

\begin{matrix}i, & \frac{i+j+1}{2} − l, & i + j + 1 − 2l − i = j − 2l + 1 \\ i + 1, & \frac{i+j+1}{2} − l, & i + j + 1 − 2l − i − 1 = j − 2l \end{matrix}

are not rainbow only if both j − 2l and j − 2l + 1 are red. Hence, J_{0} is an R-block. This implies that I_{0} is an R-block, since c(\frac{i+j+1}{2}) = G and c is rainbow-free. Since I_{0} is an R-block and c(x) = B, we conclude that J_{1} is an R-block. This, in turn, implies that I_{1} is an R-block, since c(\frac{i+j+1}{2}) = G. Iterating this argument, we conclude that all the intervals I_{s}, J_{s}, s ∈ [0, r − 1], are R-blocks. We have the following two cases.

• Case 1. 2 < c_{r−1} − y = x − b_{r−1} ≤ 2p. In this case, y + 2p + 2 ∈ J_{r−1} and x, y, y + 2p + 2 is a rainbow AP (3), contradicting our assumption that c is rainbow-free.

• Case 2. c_{r−1} − y = x − b_{r−1} = 1 or c_{r−1} − y = x − b_{r−1} = 2. In this case, x − p − 1 ∈ I_{r−1} and x − p − 1, x, \frac{i+j+1}{2} is a rainbow AP (3), thus, arriving at a contradiction.

Therefore, c cannot be rainbow-free. □

Corollary 2 Let c : [n] → {B, G, R} be a rainbow-free 3-coloring of [n] such that R is the dominant color. Then, either B or G is a recessive color.

Proof. Suppose that neither B nor G is a recessive color. Then, among all pairs of elements (i, j), such that c(i) = c(i + 1) = B and c(j) = c(j + 1) = G, choose the one where |j − i| is minimal. Without loss of generality, assume that i + 2 < j. Then, by the choice of i and j, c(i + 2) = R, c(j − 1) = R and interval [i + 2, j − 1] does not contain two consecutive elements both colored by B or by G. Lemma 3 implies that c contains a rainbow AP (3), which is a contradiction. □

Finally, we are in a position to prove Conjecture 2.

Theorem 1 Let n ≡ 0 (mod 3). For every equinumerous 3-coloring of [n] there exists a rainbow AP (3).

Proof. The claim is true for n ≤ 15 [JLMNR]. Let n ≥ 15, n ≡ 0 (mod 3), and let c : [1, n] → {B, G, R} be an equinumerous 3-coloring. Suppose that c is rainbow-free. By Corollary 1, there is a dominant color, say R. By Corollary 2, one of the remaining colors, say G, is recessive. It follows that every element colored by G is followed^{2} by an element colored by R. Since there are elements of [n] colored by B, there exists at least one pair i, j ∈ [n], such that c(i) = B, c(j) = G, and all the elements between i and j are colored with R. Since the number of elements between i and j must be greater than or equal to two, or else we have a rainbow 3-term arithmetic progression, at least one of these elements is such that both of its neighbors are not colored by G. It follows that |c^{−1}(G)| < |c^{−1}(R)|, which contradicts our assumption that c is equinumerous. Therefore, c is not rainbow-free. □

3. Concluding remarks

This note settles the question of the existence of a rainbow arithmetic progression in equinumerous 3-colorings of [n]. However, Conjecture 1 is still open. We hope that our lemmas in Section 2 with some additional ideas could prove that conjecture as well.

There are many directions and generalizations one might consider. For a discussion on this topic, as well as similar results for ℤ_{n}, consult [JLMNR]. One natural direction is imitating the well known Rado’s theorem for the monochromatic analogue [GRS90] and generalizing the problems above for rainbow solutions of other linear equations, under appropriate conditions on the cardinality of the color classes. The equation x+y = z has already been studied. Alekseev and Savchev [AS87, G94] proved that every equinumerous 3-coloring of [3n] contains a rainbow solution of this equation. Schönheim [Sch90, S95], answering the question of E. and G. Szekeres, proved that for every 3-coloring of [n], such that every color class has cardinality greater than n/4, the equation x + y = z has rainbow solutions. Here, n/4 is optimal.

2or preceded, if c(n) = G

Finally, it would be very interesting to prove similar rainbow-type results for longer arithmetic progressions and larger numbers of colors. For example, it is not known whether every equinumerous 4-coloring of [4n] contains a rainbow AP (4). However, note that for every n and k > 3, there exists a k-coloring of [n] with no rainbow AP (k) and with each color class of size at least ⌊\frac{n+2}{3⌊(k+4)/3⌋}⌋ [JLMNR].

References

[AS87] V. E. Alekseev, S. Savchev: Problem M. 1040, Kvant 4 (1987), 23.

[G94] R. K. Guy: Unsolved Problems in Number Theory, Springer-Verlag 1994. (E11–12)

[GRS90] R. L. Graham, B. L. Rothschild, J. H. Spencer: Ramsey Theory, John Wiley and Sons 1990.

[JLMNR] V. Jungić, J. Licht, M. Mahdian, J. Nešetřil, R. Radoičić: Rainbow arithmetic progressions and anti-Ramsey results, Combinatorics, Probability, and Computing, to appear.

[Sch90] J. Schönheim: On partitions of the positive integers with no x, y, z belonging to distinct classes satisfying x + y = z, in R. A. Mollin (ed.) Number theory (Proceedings of the First Conference of the Canadian Number Theory Association, Banff 1988), de Gruyter (1990), 515–528.

[S16] I. Schur: Über die Kongruenz x^{m} + y^{m} ≡ z^{m} mod p, Jahresb. Deutsche Math. Verein 25 (1916), 114–117.

[S95] G. Székely, ed.: Contests in Higher Mathematics, Miklós Schweitzer Competition 1962-1991, Problem Books in Mathematics, Springer 1995. (C.22)

[Sz75] E. Szemerédi: On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica 27 (1975), 199–245.

[vW27] B. L. van der Waerden: Beweis einer Baudetschen Vermutung, Nieuw Archief voor Wiskunde 15 (1927), 212–216.