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.


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

  • $\begingroup$ Yes, I agree. That's more or less why I think examining this case may be worthwhile, trying to decide whether there is some algebraic or number theoretic structure behind the scenes, or if the problem is "really" combinatorial. $\endgroup$ – Andrés E. Caicedo Jan 13 '12 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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