Non-multiplicative 6-colorings of Z^+

Question

First of all, congratulations to Dömötör! This question is related to an interesting problem he asked a while ago. (And it is an attempt to have people take a new look at that problem.)

Let me recall the setting of domotorp's question. Here I am only looking at colorings of ${\mathbb Z}^+$ using 6 colors. We require that, for any positive $a$, the numbers $a,2a,\dots,6a$ all receive different colors. We call such coloring $6$-satisfactory.

Trying to build a $6$-satisfactory coloring, it is easy to see that we only need to worry about coloring the set of positive integers of the form $2^a3^b5^c$ (that I call $K_6$, where the $K$ stands for `core').

There is a natural approach, suggested by Ewan Delanoy. Let's say that the $6$-satisfactory coloring $c$ is multiplicative if it is induced by a `partial homomorphism' from {$1,\dots,6$} to ${\mathbb Z}/6{\mathbb Z}$. This means that $$c(2^a3^b5^d)=ac(2)+bc(3)+dc(5)\mod6.$$

Multiplicative colorings can be represented in nice ways, see for example the suggestion by Victor Protsak.

Not all 6-satisfactory colorings are multiplicative, though. ($n=6$ is the least number of colors for which this happens.)

For example:

Theorem. There is a (unique) 6-satisfactory coloring of $K_6$ with $c(i)=i$ for $i\le 6$ and satisfying the following conditions:

• $c(2^3)=5$, $c(2^4)=2$, $c(2^5)=4$, $c(3^2)=2$,
• $c(12n)=c(27n)$, $c(20n)=c(45n)$ for any $n\in K_6$, and
• $c(2^6n)=c(n)$, $c(3^7n)=c(3n)$, and $c(5^7n)=c(5n)$ for any $n\in K_6$.

The coloring $c$ from the theorem is not multiplicative. (The only multiplicative $c$ with $c(8)=c(5)$ must have $c(9)=c(4)$.)

My question is whether there is a reasonable algebraic characterization of non-multiplicative colorings, or at least of some interesting subfamily of these. (And if the answer is yes, I wouldn't object to seeing something about general $n$.)

The examples I have, all come equipped with some obvious structure; for example, letting $d(n)=c(30n)$, then $d$ is a satisfactory coloring with $d(n^6)=d(n)$ for all $n$. I do not know if there are examples where this periodicity is not present.

I would like is to understand what is truly going on. What I would hope for is something akin to the notion of `partial homomorphism', but at the moment I really don't know what to expect.

Answer 1

First of all, thank you! (Sorry I am reading this a little late, but I have not noticed this question before...) Let me also congratulate your student! (To whom small note: on his slide 34 (from http://caicedoteaching.files.wordpress.com/2012/01/presentation-7.pdf) the modulos seem to be mistyped.)

Regarding your question, I am not sure what kind of characterization you are looking for, but here is another simple non-multiplicative 6-coloring:

$c(2^a3^b5^d\alpha)=(a \mod 3) + 3(b \mod 2) + $ any function of $d$ that differs on any two adjacent naturals.

Such constructions are easy to make if you think about the problem as poliomino tilings (see my original question). Imo algebra only gives a method to find nice colorings, but this problem might be closer to graph theory. Note that usually my intuitions are wrong...