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$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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