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

coloringcombinatoricsmodular arithmeticramsey-theory

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.

Best Answer

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

Related Question