Construct a coloring of the positive integers with finitely many colors such that there is no monochromatic solution to the equation $x + y = 3z$.

Question

I followed a hint but only got a partial solution: we use $4$ colors $a,b,c,d$, and for a number $k$ that is not a multiple of $5$, the coloring function $c(k)$ is determined by $k \text{ mod } 5$: $$\begin{array}{c|c} k\bmod5&c(k)\\ \hline 1&a\\ 2&b\\ 3&c\\ 4&d \end{array}$$ (As for the multiples of $5$, I'm still not sure.)

To check that this coloring is valid, we note that for $x$ and $y$ such that $c(x) \neq c(y)$, the statement is automatically true. So we check only the cases where $c(x) = c(y)$, and show that $c(z)$ is a different color. By inspecting $(x + y) \text{ mod } 5 = 3z \text{ mod } 5$, we can deduce the value of $z \text{ mod } 5$ and thus $c(z)$. The following table shows the results: $$\begin{array}{c|c|c|c} x\bmod5&2x\equiv3z\bmod5&c(x)=c(y)&c(z)\\ \hline 1&2&a&d\\ 2&4&b&c\\ 3&1&c&b\\ 4&3&d&a \end{array}$$ Is there any way to extend this coloring to the multiples of $5$? Also, is there any theorem/topic pertaining to this analysis? I found this exercise in a section about extremal combinatorics and arithmetic progression, so I'm not sure my solution is in the spirit of the question.

Answer 1

The multiples of $5$ pose little problem:

• if only $y$ (without loss of generality) is a multiple of $5$ we have $x\equiv3z\bmod5$ and it is easy to check that $x,z$ must have different colours with the given partial colouring
• if only $z$ is a multiple of $5$ it is similarly easy to check that $x,y$ have different colours
• if two of $x,y,z$ are multiples of $5$ then all three are, and in this case we can divide by $5$

Hence we can assign colours to the multiples of $5$ independently of the other colours, i.e. assign $5k$ the same colour as $k$. This leaves multiples of $25$ uncoloured, but no matter, we assign $25k$ the same colour as $5k$. And so on.

In short, if the colours are $1,2,3,4$, the colour assigned to $n$ is its rightmost non-zero digit in base $5$ (OEIS A277543). This is a $4$-colouring of the positive integers with no monochromatic $x+y=3z$.

---

Through SAT solving I've established the non-existence of monochromatic $x+y=3z$-avoiding $2$- and $3$-colourings of the natural numbers. The $2$-colour case is easy and the Ramsey number is $9$: suppose $1$ is black, then

• $2$ must be white to avoid a monochromatic $1+2=3\cdot1$
• $3$ is black because of $3+3=3\cdot2$
• $4$ is black because of $2+4=3\cdot2$
• $5$ is white because of $4+5=3\cdot3$
• $6$ is white because of $3+6=3\cdot3$
• $8$ is white because of $1+8=3\cdot3$
• $7$ is black because of $7+8=3\cdot5$

Now $9$ must be white because of $3+9=3\cdot4$ and black because of $9+9=3\cdot6$, which is a contradiction. This also gives the unique (to colour symmetry) avoiding colouring of length $8$ as $10110010$.

My code, CNF and DRAT proof for the $3$-colour case are here – the Ramsey number is $54$. Here is a monochromatic $x+y=3z$-avoiding length-$53$ sequence: $$010021022\\ 020021021\\ 020021022\\ 020021022\\ 020111011\\ 02001102$$ sharpSAT gives the number of non-equivalent length-$53$ solutions as $6784$.