Can we color Z^+ with n colors such that a, 2a, ..., na all have different colors for all a?

Question

For example for n=2 coloring odd numbers red, numbers of the form 4k+2 blue and so on works.

This problem was posed in the KoMaL for n+1 prime, by Peter Pach Pal. I verified it for all n<30, I think with a computerprogram one can easily verify it for much bigger numbers by trying certain periodic colorings.

Ideas. As there is a lot of discussion going on, I thought I share here my attempts as Ewan and Gowers took similar paths. First of all, if we denote the primes by $p_i$ and the largest prime not bigger than $n$ by $p_d$, then it is sufficient to color the numbers of the form $\Pi p_i^{\alpha_i}$. This is equivalent to coloring $\mathbb Z^d$ with n colors such that the translates of a special poliomino are all rainbow colored, meaning they contain all $n$ colors. This is also equivalent to tiling the space with translates of this poliomino. The easiest way to give a coloring is if we have some nice periodicity, eg. if n+1 is prime, then $\Pi p_i^{\alpha_i} \mod (n+1)$ is such, whenever we go in a direction, it corresponds to an authomorphism of $Z_{n+1}^*$. Another possibility is to give a "linear" coloring using the addition $\mod n$, for example for $n=5$, one can take $x+3y+4z \mod 5$. So far I could always find such a linear coloring but I cannot prove that it always exist, eg. we have too many constraints to use the combinatorial nullstellensatz.

Answer 1

This is not an answer, but an update (with side remarks) indicating limitations of approaches suggested in other answers.

I suggested to my Master student Thomas Chartier to work on this problem. You can find a copy of his thesis here, together with a short description of its contents.

Given $n$, let $K_n$, the $n$-core, denote the set of positive integers whose prime factorization only involves primes less than or equal to $n$.

It should be clear that the question has a positive answer for $n$ iff it has a positive answer when ${\mathbb Z}^+$ is replaced with $K_n$, so I will focus on $K_n$ in what follows. In fact, if there is a coloring of $K_n$ as in the question (a satisfactory $n$-coloring), then there are as many such colorings of ${\mathbb Z}^+$ using $n$ colors as there are real numbers.

Given a group $G$ of order $n$, say that a group structure $(\{1,\dots,n\},\cdot)$ is $G$-satisfactory iff it is isomorphic to $G$ and extends the partial graph of multiplication, i.e., whenever $i,j$ and $ij$ are all of size at most $n$, then the group operation satisfies $ij=i\cdot j$. (In particular, $1$ is the identity of the group.)

Suppose that, for some abelian $G$ of order $n$, there is a $G$-satisfactory group. Then there is a satisfactory $n$-coloring of $K_n$: In effect, we can assign to $p_1^{m_1}\dots p_k^{m_k}\in K_n$ the 'color' $p_1^{m_1}\dots p_k^{m_k}$ where now exponents and products are computed in the sense of the $G$-satisfactory group.

This generalizes Ewan Delanoy's suggestion (where $G={\mathbb Z}/n{\mathbb Z}$). (It is a true generalization, in that we have examples where $G\not\cong{\mathbb Z}/n{\mathbb Z}$.)

In turn, Ewan's approach generalizes Victor Protsak's. This is because if $p=nk+1$ is prime, then the nonzero $k$-th powers modulo $p$ form a group isomorphic to ${\mathbb Z}/n{\mathbb Z}$, and if $1^k,\dots,n^k$ are all different modulo $p$, then the identification $i\mapsto(i^k\mod p)$ induces a ${\mathbb Z}/n{\mathbb Z}$-satisfactory group structure on $\{1,\dots,n\}$. (Again, this is a true generalization, in that we have examples of ${\mathbb Z}/n{\mathbb Z}$-satisfactory groups that are not induced by any $p$.)

Some comments:

• Of course, in order to define the coloring as above, we need $G$ to be abelian. Independently of the problem at hand, the question of whether the partial graph of multiplication on $\{1,\dots,n\}$ can be extended to a group structure (regardless of whether it is abelian or not) is interesting in its own right. It turns out that if $n$ is odd, any such group structure must be abelian. This is proved in "Groups formed by redefining multiplication", by K. Chandler. Canadian Mathematics Bulletin, 31 (4) (1988), 419-423. As far as I know, it is open whether this must always be the case. (I would appreciate any updates in this regard.)

• Not every ${\mathbb Z}/n{\mathbb Z}$-satisfactory group is induced by a prime $p=nk+1$ as in Protsak's condition. (In Chartier's thesis, we call such a prime $p$ a strong representative.) The question of when there are such primes is also interesting in its own right. This is essentially addressed by a theorem of Mills that in turn extends a result of Kummer, see "Characters with preassigned values", by W.H. Mills. Canadian Journal of Mathematics, 15 (1963), 169-171. Mills characterization shows that, in particular, not every $n$ admits a strong representative $p$. The proof of Mills's theorem makes strong use of Chebatorev's theorem. As a consequence of this result, we know (for example) that for $n=34$ there must be such a strong representative $p$, but extensive computer search has not found it. As an indication of the difficulties of the search, the smallest $p$ for $n=32$ is $p=5209690063553$, and we expect any $p$ for $34$ to be orders of magnitude larger.

• If $n+1$ or $2n+1$ is prime, then Protsak's condition is automatically satisfied. For other values of $k$, this is no longer the case. In fact, $k$ can never be 3, for example, and for any $k$ there are only finitely many possible $n$, see this question.

As mentioned by Fedor Petrov, domotorp's question immediately implies the Balasubramanian-Soundararajan theorem (formerly, Graham's conjecture). Sure enough, Delanoy's and Protsak's suggestions had been previously considered in connection with Graham's conjecture. In

• "What is special about 195? Groups, $n$th power maps and a problem of Graham", by R. Forcade and A. Pollington. Proceddings of the First Conference of the Canadian Number Theory Association, Ban, 1988, R.A. Mollin, ed., Walter de Gruyter, Berlin, 1990, 147-155,

it is shown that $n=195$ is the least integer for which there is no $G$-satisfactory structure for any $G$. Forcade provided us with the list of all $n\le 500$ for which this is the case. In Chartier's thesis, these $n$ are called groupless. The existence of groupless numbers unfortunately shows that Greg Kuperberg's probabilistic suggestion cannot be formalized.

The first few are listed below:

195, 205, 208, 211, 212, 214, 217, 218, 220, 227, 229, 235, 242, 244, 246, 247, 248, 252, 253, 255, 257, 258, 259, 263, 264, 265, 266, 267, 269, 271, 274, 275, 279, 283, 286, 287, 289, 290, 291, 294, 295, 297, 298, ...

(The sequence is not currently listed in OEIS.)

We do not know if there is a satisfactory $n$-coloring for any/some groupless $n$. In particular, the first open instance of domotorp's question is when $n=195$.

In Chartier's thesis a coloring induced by a $G$-satisfactory group is called multiplicative (so, of course, any coloring for $n=195$ would be non-multiplicative). We know that non-multiplicative colorings exist (at least, for $n=6$), see this question. However, though my examples are non-multiplicative, one can define multiplicative colorings from them. The situation for $n=195$ is very much open.

To close, let me remark that it has been suggested, for example, in

• "Constructing $k$-radius sequences", by S. Blackburn and J. McKee. Mathematics of computation, to appear,

that (at least for $n$ large enough) it is the case that $n$ is groupless iff neither $n+1$ nor $2n+1$ is a prime number. This also seems interesting to investigate on its own.

Answer 2

For n=3 I think one can argue as follows. Let's first find a colouring of N^2 with three colours such that every triangle of the form (x,y), (x+1,y), (x,y+1) gets different colours. That we can do e.g. by colouring (x,y) by x+2y mod 3. Let's call that colouring phi.

Now write any integer uniquely in the form 2^a3^bm and colour it phi(a,b). I claim that this works. Indeed, if we take this integer, twice this integer and three times this integer, then the three colours will be phi(a,b), phi(a+1,b) and phi(a,b+1).

This feels pretty similar to a special case of what Ewan was saying, but I'm not sure it's identical. And I think it may generalize quite nicely. The crucial lemma seems to be that if we define a set of points in Z^d by letting T be the intersection of Z^d with a triangle bounded by the coordinate hyperplanes and a hyperplane of the form $a_1x_1+...+a_dx_d\leq C$, then we can colour Z^d with |T| colours in such a way that every integer translate of T gets |T| different colours. I haven't checked that statement but it feels plausible.

Answer 3

Here is an extension of François's argument that seems to work for any $n.$ Choose a natural number $d$ so that (1) $p=nd+1$ is prime and (2) $a/b$ is not a $d$th root of unity $\mod p$ (equivalently: not an $n$th power $\mod p$) for any unequal $a,b$ from $\{1,2,\ldots,n\}$. Color a natural number $x$ by $(x')^d,$ which is an $n$th root of unity $\mod p$. By assumption (1), there are $n$ colors, and by assumption (2), $ax$ and $bx$ have different colors for $a,b$ as above. The existence of such a prime $p$ follows from the Chebotarev density theorem for the extension $K/\mathbb{Q},$ where $K$ is obtained by adjoining the $n$th roots of $1,2,\ldots,n.$ We require that $p$ split completely in $K_n=\mathbb{Q}(\zeta_n)$, which is equivalent to (1), and that each factor remain prime not split completely in every extension $K_n(\sqrt[n]{a/b})/K_n$ with $a,b$ as above, which implies is equivalent to (2).

EDIT Judging by some comments, I am far from the only one whose algebraic number theory is out of shape, so let me give a few details about Chebotarev's density. The extension $K/K_n$ is the composite of Kummer's extensions $K_n(\sqrt[n]{q})/K_n$ corresponding to primes $q\leq n.$ The Galois group $G=\operatorname{Gal}(K/\mathbb{Q})$ is the semidirect product

$$1\to(\mathbb{Z}_n)^r\to G\to (\mathbb{Z}_n)^{*}\to 1,$$

where $r$ is the number of such primes. The requirement (1) that $p$ split in $K_n$, i.e. that $\mathbb{Z}/p\mathbb{Z}$ contains the $n$th roots of unity (which happens iff $p\equiv 1 (\mod n)$) means that the Frobenius element $Fr_p$ projects to 1, i.e. it lies in the subgroup $N=(\mathbb{Z}_n)^r.$ Assuming (1), the requirement that $a/b=q_1^{k_1}\ldots q_r^{k_r}$ not be $n$th power $\mod p$ translates into "$Fr_p$ avoids the subgroup $N_{k}$ of $N$," where

$$ N_k = \{(a_1,\ldots,a_r): k_1 a_1 + \ldots +k_r a_r=0\}.$$

The Chebotarev density theorem says that for any conjugacy class $C$ of $G$, the primes $p$ such that $Fr_p\in C$ have density $|C|/|G|.$ In particular, such $p$ exists! A slight unusual feature of our situation is that we apply Chebotarev's theorem in the case of a non-abelian extension. Finally, we need to see that the union of various $N_k$s is not all of $N$. I have a truly marvelous proof of this proposition, but the margins of MO are too thin to contain it.

Answer 4

Definition I say that a function $f : \lbrace 1, \ldots ,n \rbrace \to \frac{\mathbb Z} {n \mathbb Z} $ is multiplicative iff whenever $x=yz$ for $x,y,z$ in the range of $f$, then $f(x)=f(y)+f(z)$ in $\frac{\mathbb Z}{n \mathbb Z} $. (note :this reminds one of "Freiman homomorphisms").

Let $A_n$ denote the set of integers all of whose prime factors are $\leq n$, and $B_n$ the set of integers all of whose prime factors are $> n$. Any integer can be written as a product of an element of $A_n$ by an element of $B_n$.

Lemma 1 If $f : \lbrace 1, \ldots ,n \rbrace \to \frac{\mathbb Z} {n \mathbb Z} $ is multiplicative, then $f$ may be extended uniquely to a mapping $g: {\mathbb Z}^{+} \to \frac{\mathbb Z} {n \mathbb Z} $ such that $g$ is multiplicative on $A_n$ (i.e. $g(aa')=g(a)+g(a')$ for any $a,a' \in A_n$) and $g(ab)=g(a)$ for any $a\in A_n,b \in B_n$.This map $g$ has the property that the image of $g(x),g(2x), \ldots ,g(nx)$ is exactly $\frac{\mathbb Z}{n \mathbb Z} $ for any $x$.

Lemma 2 Multiplicative functions $f : \lbrace 1, \ldots ,n \rbrace \to \frac{\mathbb Z} {n \mathbb Z} $ do exist.

Proof of lemma 2 : first set $f(1)=0$. Now set $f(2)$ to any nonzero value. By multiplicativity, this determines the value of $f$ on all powers of $2$ that are $ \leq n$. Let us call $V_1$ the set of all values of $f$ obtained so far. Now set $f(3)$ to any value . By multiplicativity, this determines the value of $f$ on numbers $\leq n$ that are only divisible by $2$ or $3$. Let us call $V_2$ the set of all values of $f$ obtained so far, etc.

Continuing like this until all values are determined, we eventually reach a multiplicative function.

Answer 5

This is not a solution, but ideally a clarification of the question. The semigroup $\mathbb{Z}_+$ under addition is equivalent to the semigroup $\mathbb{Z}_{\ge 0}^\infty$ under addition. We are interested in certain special subsets $A_n$ of the latter, which in multiplicative form correspond to $\{1,2,\ldots,n\}$. Each $A_n$ is a certain $n$-element lower set in the natural partial ordering on $\mathbb{Z}_{\ge 0}^\infty$. We would like to color $\mathbb{Z}_{\ge 0}^\infty$ with $n$ colors such that each translate of $A_n$ uses $n$ different colors.

By a compactness argument, we can find a sequence of translates of $\mathbb{Z}_{\ge 0}^\infty$ in $\mathbb{Z}^n$ such that the colorings converge to a coloring of all of $\mathbb{Z}^\infty$. In other words, in multiplicative form, we could equally well have asked the question in $\mathbb{Q}_+$ as in $\mathbb{Z}_+$.

Also, I think that the subset of $\mathbb{Z}^\infty$ with color 1 is a set of vectors that yields a tiling of $\mathbb{Z}^\infty$ by translates of $-A_n$. For instance, if two of these translates intersect at $x$, then you correspondingly $x+A_n$ contains two elements with color 1. (Technically this only shows that it is a packing, not a tiling. However, the cracks that are not tiled must have density 0, and you can translate them away by the same compactness argument.) Moreover, if you have such a tiling, then you can color each element of each tile in the same way, and then for that coloring each translate $x+A_n$ has all different colors. Again, in multiplicative form, you're tiling the positive rational numbers by arithmetic progressions $a,2a,3a,\ldots,na$.

---

To summarize my understanding of this problem:

1. Every admissible coloring of $\mathbb{Z}_+$ yields a tiling of $\mathbb{Q}_+$ by subsets of the form $T_a = \{a,2a,3a,\ldots,na\}$, and vice versa.
2. There is a special interest in lattice tilings, in which the set of choices of $a$ is a subgroup of $\mathbb{Q}_+$ of index $n$. In particular, if $n+1$ or $2n+1$ is prime, then such a subgroup exists, and the quotient group is isomorphic to $\mathbb{Z}/n$.
3. It is easy to make variations that do not tile $\mathbb{Q}_+$, for example multiples of $\{1,2,3,4,6,8,9\}$. However, these variations generally span abelian groups in $\mathbb{Q}_+$ of lower rank than the span of $\{1,2,3,\ldots,n\}$. For the stated question, the rank is $\pi(n)$, and we may as well work in the subgroup of $P_n$ of $\mathbb{Q}_+$ generated by the $\pi(n)$ primes up to $n$.

I decided to look at the problem this way: Among all $n^{\pi(n)}$ homomorphisms from $P_n$ to $\mathbb{Z}/n$, can we heuristically estimate the number that are a bijection when restricted to $\{1,2,\ldots,n\}$? Let's say that the restriction of such a homomorphism is not particularly more likely or less likely to be a bijection than a random function. The latter probability is $n!/n^n$, so we can expect roughly $n!\cdot n^{\pi(n)-n}$ solutions. We can now take a logarithm and apply Stirling's approximation and a sufficiently careful version of the prime number theorem, $\pi(n) \approx \text{Li}(n)$. The answer is that there is plenty of entropy to have solutions; the predicted log of the number of solutions is roughly $n/(\ln n)$. This heuristic can be checked for small $n$. If the heuristic is reliable, then there should be solutions for all $n$.

It would be nice to have an effective construction of such a homomorphism for all $n$, but my impression is that the other answers so far don't find one. Note the last remark in Victor's answer: "I have a truly marvelous proof of this proposition, but the margins of MO are too thin to contain it."

Answer 6

I suggested in a comment, to look for colorings that are the same for each a, except for a fixed permutation.

Suppose the colors are given by function c(x), for x ≥ 1. And a permutation function p(i,j), where i,j ∈ [1..n]. Where i is the index of the permutation, and j the index of the permutation of the color.

If n = 4 and the coloring starts with abcd, then p(1,1) = a, p(1,2) = b, p(1,3) = c, p(1,4) = d, p(2,1) = b, p(2,2) = d.

If the coloring is the same for each a, then we get the following equation:

c(an) = p(c(a),c(n))

It is more important to give a condition when the above condition is met.

Lemma 1: If p(x,y) is reflexive (p(x,y)=p(y,x)) and associative (p(x,p(y,z))=p(p(x,y),z)) and p(x,y)=p(1,xy) for xy ≤ n, then a coloring can be constructed.

Lemma 2: For each n a permutation exists such that it reflexive and associative and for p(x,y)=p(1,xy) for xy ≤ n.

To see how this works, for n = 4, we start the following permutation matrix:
abcd
bd..
c...
d...

Fill in the second row:
abcd
bdac
ca..
dc..

And complete it:
abcd
bdac
cadb
dcba

From this construct the coloring: abcdxaxcdxxbxxxa

By each prime number a > n (the x values in the coloring), you can choose a color for c(a), but you have to continue with the permutation of that color for c(ma).

Lemma 1 is trivial to prove, because the associative and reflexive conditions makes that reaching a number by different values of a, factoring the number and re-arranging makes that it must have the same value. For the values xy ≤ n, you can't factor anymore, and the condition must just met.

I haven't proven lemma 2 fully. A permutation matrix with reflexive and associative conditions, can be constructed by starting with 1 permutation that has a single cycle. The full matrix can be constructed by applying this permutation multiple times, up to n. It can be proven, that such matrix has the reflexive and associative condition, but not necessary the condition that p(x,y)=p(1,xy) for xy ≤ n;

The solution of François as matrix looks like this:
abcdef
bdface
cfbead
daebfc
ecafdb
fedcba

The permutation from first row to second row is not a permutation with a single cycle. It brings you from row 1, to row 2 to row 4, back to row 1. However, this can still be categorized as 1 cycle permutation, because the permutation from first row to third row, is a permutation with a single cycle.

Instead of looking at the permutation per color, it is better to look which colors are passed, when the permutation is applied multiple times. In above example the cycle is (first row to third row) a->c->b->f->d->e->a.

If we just make the second row a permutation with one cycle, then the cycle starts with: 1->2->4->8->16->32->64 etc. Then we can add 3 and the other primes.

For n = 27 we can get:
1->2->4->8->16->3->6->12->24->x->9->18->5->10->20->27->x->15->7->14->11->22->x->21->25->13->26->1

In above sequence, multiplications with 2, have 1 step, multiplication with 3, 5 steps, multiplications with 5 have 12 steps. The remaining primes 17, 19, 23 can be placed on any of the x values. The short parts 11->22 and 13->26 can easily be exchanged. From this cycle, you can make a permutation and permutation matrix that has the condition that p(x,y) = p(1,xy) for xy ≤ n. From that permutation the coloring can be constructed.

As you can see, it is not very difficult to construct a coloring this way. But, the sequence is also rather crowded. It is not a prove yet that it is always possible.