The Erdős Discrepancy Problem is whether in any two-coloring of the naturals for any $C$ there is a sequence $d, 2d, \ldots nd$ such that the difference of red and blue numbers in it is more than $C$. This was recently shown to be true by Tao (building on Polymath5).

Now consider the following stronger conjecture, which also generalizes van der Waerden.

In any $k$-coloring of the naturals for any $n$ there is a monochromatic sequence $(i+1)d, (i+2)d, \ldots (i+n)d$.

If true, this would of course be quite a strong result, so I more expect that someone might be able to show a simple counterexample to it. What about the even stronger density version?


This is false already for $k=2,n=4$. Color an integer $m$ according to the parity of the exponent of $2$ in the prime factorization. Among $i+1,i+2,i+3,i+4$ at least one number is odd, and at least one is divisible by $2$ and not by $4$. Those two numbers have the parity of the exponent different, hence so do the corresponding two among $(i+1)d,(i+2)d,(i+3)d,(i+4)d$. Hence those four numbers can't have the same color.

Edit: for completeness, it's false for $k=2,n=3$ as well. For integer $m$, write it as $3^i\cdot j,3\nmid j$ and color $m$ according to $j\mod 3$. Then among $i+1,i+2,i+3$ the two which are not divisible by $3$ will have different remainders, do multiplying them by $d$ gives numbers of different colors. Hence your conjecture only holds in trivial cases $k=1$ and $n\leq 2$.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.