First of all, congratulations to [Dömötör](http://arxiv.org/abs/1009.4641)! This question is related to an interesting [problem](https://mathoverflow.net/questions/26358/can-we-color-z-with-n-colors-such-that-a-2a-na-all-have-different-colors) 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.



Non-multiplicative 6-colorings of Z^+
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...


