Timeline for Can we color Z^+ with n colors such that a, 2a, ..., na all have different colors for all a?
Current License: CC BY-SA 2.5
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 17, 2012 at 19:47 | comment | added | Fedor Petrov | Well, it maybe was just a high-level joke and I am looking stupid with my comment, but once you found an element $(c_1,\dots,c_r)$ of $N$, which does not belong to any of $N_k$, you may just color each positive integer $x=x'\prod q_i^{u_i}$ ($x'$ being coprime to $\prod q_i$) to the color $\sum c_i u_i$ modulo $n$. So, Chebotarev density theorem is completely helpless here (as could be expected). | |
| Jun 27, 2010 at 21:49 | comment | added | Andrés E. Caicedo | I ran some examples to see how this behaves in practice. The first n for which n+1,2n+1 are not prime is n=7. The least p that works here is 659=7*94+1. The next n is 13, with least p=2578733=13*198364+1. Then n=17, with p=48611161=17*2859480+1, and n=19, with p=10134791=19*533410+1. I would be curious to know if there is a reasonable "expected bound" on p in terms of n. | |
| May 30, 2010 at 23:43 | comment | added | Greg Kuperberg | Oh wait, I guess I did not properly grasp the last sentence of the revised post, which makes a similar point. | |
| May 30, 2010 at 22:23 | comment | added | Greg Kuperberg | A key step in the extended argument strikes me as circular. As I understand it, if $n$ is prime, then a suitable conjugacy class $C$ is exactly equivalent to a linear coloring of domotorp. If $C$ exists, then I can believe that Cebotarev's theorem applies. But (a) if it exists, then you can solve the problem directly without modern number theory; and (b) how do you know that it exists? I maintain that it does not exist, in your notation, for $n=7$, $r=2$, and $(k_1,k_2) \in \{(0,0),(1,0),(2,0),(3,0),(0,1),(1,1),(0,2)\}$. | |
| May 30, 2010 at 21:42 | comment | added | Victor Protsak | I have added a few details so you can hopefully see for yourself whether it's true or not. Small $n$ may have to be treated separately, but that's hardly surprising in analytic arguments. Just to make it clear: I like the tiling idea, but it seems to make the problem more complex than the original one. | |
| May 30, 2010 at 21:35 | history | edited | Victor Protsak | CC BY-SA 2.5 |
added details of Chebotarev's density
|
| May 30, 2010 at 21:12 | comment | added | Greg Kuperberg | Somehow I am not seeing a complete explanation of the properties of $\{1,2,\ldots,n\}$ that you use in your argument. For instance, if my tiling criterion is correct, then it is not possible to color the integers with 7 colors so that the multiples $na$ with $n \in \{1,2,3,4,6,8,9\}$ are all different colors, even though the ratio of any 2 is not a 7th power. Ex post facto, $\{1,2,3,4,5,6,7\}$ is a different case, but why? | |
| May 30, 2010 at 20:37 | comment | added | Victor Protsak |
Greg: Well, it's always hard to answer questions of the type "why does this argument work for X if Y is wrong?" In the specific example you asked about, $n=3$ and $8=1=2^3$ is a cube, so obviously you can't avoid $a/b$ being a cube $\mod p$. More generally, if the multiplier set consists of $k_1,k2,\ldots,k_n$th powers of $g$ then the argument still works if $k_i$s are all different $\mod n$ (in which case you can easily tile $\mathbb{Z}_+$). For you a more acceptable explanation may be that none of $a/b$ for $S=\{1,2,\ldots,n\}$ is an $n$th power? But this is what the proof already says.
|
|
| May 30, 2010 at 15:46 | comment | added | Greg Kuperberg | I guess the answer to my question is too short for me to follow what is going, because $\{1,2,\ldots,n\}$ does include many composite numbers. So I don't know why some of the characters, whatever is meant here by that, aren't also linearly dependent. | |
| May 30, 2010 at 14:27 | comment | added | François G. Dorais | (@Victor: Nice to see you on MO!) | |
| May 30, 2010 at 14:26 | comment | added | François G. Dorais | @domotorp: For an elementary argument, see this answer by Victor Miller - mathoverflow.net/questions/15220/… - and the more general answer of Bjorn Poonen. | |
| May 30, 2010 at 12:45 | comment | added | domotorp | I can understand how you give the coloring once you have such a prime, unfortunately I cannot follow the argument why such a prime must exist due to my poor algebraic knowledge. But Greg's comment suggest that maybe there is an interesting connection, if we know that we cannot tile with certain poliominos (which is easy to see for small examples), then we get that there is no prime such that... | |
| May 30, 2010 at 9:56 | comment | added | Victor Protsak | Wadim: I don't remember it myself. As you said, we are so democratic nowadays:) Greg: The short answer is that they are all powers of 2 , so their characters are linearly dependent. This does not happen for the "hopeful" set. | |
| May 30, 2010 at 6:33 | comment | added | Greg Kuperberg | There is something that I don't understand about this argument. It is certainly not possible to color the positive integers with 3 colors so that every triple $a,2a,8a$ has 3 different colors. (Even to just color 2,4,8, and 16, a fourth color is needed.) There are many other examples of this. Why does your argument apply to the hopeful sets $\{1,2,\ldots,n\}$, but not to inadmissible sets such as $\{1,2,8\}$? | |
| May 30, 2010 at 6:18 | comment | added | Wadim Zudilin | Victor, I have to learn your patronimic name to address you! :-) +1. | |
| May 30, 2010 at 4:37 | history | answered | Victor Protsak | CC BY-SA 2.5 |