Let $P(n)$ be the statement "any $n$ coloring of $\mathbb{N}$ contains a monochromatic progression $a, a+d, a+2d$ such that $d>a$".

For which $n$ is $P(n)$ true?

It's easy to see that $P(2)$ is true by a simple modification of the color focusing argument that is used in the traditional proof of van der Waerden's theorem. However, this argument does not seem to generalize to more colors, or at least not very easily.

It's also easy to see that a similar statement is not true for progressions of length $4$, even in the $2$ color case: just color $[2^n,2^{n+1}-1]$ red if $n$ is even and blue if $n$ is odd. If $2^n<d<2^{n+1}$ then $a+d$ or $a+2d$ is in $2^{n+1}$ but $a+2d$ or $a+3d$ is in $2^{n+2}$.

I asked the same question on math stack exchange a little over a week ago but got no replies or comments, so I figured I'd ask here as well.


$P(n)$ is false for all $n > 2$. To see this, it suffices to show that $P(3)$ is false, because if we start with a $3$-coloring that witnesses the failure of $P(3)$, then we can always add a few more colors, say by using each of the new colors on just one or two numbers each, to obtain a witness to the failure of $P(n)$ for larger $n$.

Here is a coloring that shows $P(3)$ is false, inspired by your example for $2$ colors and length-$4$ progressions. Let $F_n$ denote the $n^{th}$ term of the Fibonacci sequence (with $F_1 = 1$ and $F_2 = 2$), and then

color $m$ red if $m \in [F_{3k},F_{3k+1})$ for some $k$,

color $m$ green if $m \in [F_{3k+1},F_{3k+2})$ for some $k$,

color $m$ blue if $m \in [F_{3k+2},F_{3k+3})$ for some $k$.

To see that this coloring really is a counterexample, let's suppose that $a$, $a+d$, and $a+2d$ all have the same color, and that $a < d$. Notice that this implies $$\frac{3}{2} < \frac{a+2d}{a+d} < 2.$$ This does not immediately give us a contradiction, but it does tell us that $a+d$ and $a+2d$ must both lie in a single interval of the form $[F_n,F_{n+1})$. (This is because $2(F_n-1) < F_{n+3}$ for all $n$. This isn't too hard to prove -- for large $n$ it follows from the fact that $F_{n+3}/F_n \approx \varphi^3 \approx 4.2$.) Once we know that $F_n \leq a+d < a+2d < F_{n+1}$, we get that $$a = 2(a+d) - (a+2d) > 2F_n - F_{n+1} = 2F_n - (F_n+F_{n-1}) = F_n - F_{n-1} = F_{n-2}.$$ This tells us that if $a$ is to have the same color as $a+d$ and $a+2d$, then we must also have $a \in [F_n,F_{n+1})$. But now this is absurd: we have $\frac{a+2d}{a} > 3$ while $\frac{F_{n+1}}{F_n} \leq 2$ for all $n$.

| cite | improve this answer | |
  • $\begingroup$ Nice example. However, if you alter colors from two of the original three classes, you may end up undoing your work. If you add colors by recoloring just one of the original three classes, then you preserve the property of being a counterexample. Gerhard "Don't Forget The Painters Tape" Paseman, 2020.02.01. $\endgroup$ – Gerhard Paseman Feb 1 at 19:49
  • $\begingroup$ @GerhardPaseman: Good point -- I've now laid down some tape. $\endgroup$ – Will Brian Feb 1 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy