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

replaced http://mathoverflow.net/ with https://mathoverflow.net/

Source Link

edited Apr 13, 2017 at 12:58

1
2
3

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

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 question. However, though my examples are non-multiplicative, one can define multiplicative colorings from them. The situation for $n=195$ is very much open.

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.

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.

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.

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.

added 3 characters in body

Source Link

edited Jan 13, 2012 at 2:16

Andrés E. Caicedo

32.5k
5
133
240

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.

Source Link

created Jan 12, 2012 at 22:53

Andrés E. Caicedo

32.5k
5
133
240

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

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

Stack Exchange Network

Return to Answer