Author |
Topic: Color positive integers (Read 2238 times) |
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Color positive integers
« on: Jun 25th, 2009, 1:12am » |
Quote Modify
|
Is it possible to color the positive integers using finitely many colors so that x + y and xy are colored differently for all distinct positive x,y?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Color positive integers
« Reply #1 on: Jun 27th, 2009, 10:27am » |
Quote Modify
|
Probably not Is it possible to construct arbitrarily large cliques? A set where for any two elements x,y either x2-4y or y2-4x is a perfect square. With 2 colors you will fail at 98. With 3 colors, 100. With more colors, lower bounds are 224, 1728, 29808, 238400, ... This would suggest the minimal number of colors for [1,n] is asymptotically logarithmic.
|
« Last Edit: Jun 27th, 2009, 10:13pm by Eigenray » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Color positive integers
« Reply #2 on: Jun 27th, 2009, 11:36am » |
Quote Modify
|
Nice work, Eigenray! I should mention that I don't know if this question is open or not. Your criterion for x and y to be adjacent is very nice, though.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Color positive integers
« Reply #3 on: Jun 27th, 2009, 1:24pm » |
Quote Modify
|
By the compactness theorem, k colors suffice iff k colors suffice for all finite subsets. But this seems unlikely. My program has only shown that 4 colors are enough for [1,223], etc., not that [1,224] needs 5, but the fact that it makes to it 223 near instantaneously but not to 224 after several hours is suggestive. One can try to find cliques. To be precise, a clique is a set S such that for all x,y S, with x>y, either x=y+1 or y2-4x is a non-zero perfect square. There are certainly lots of 3-cliques, for example {x,x+1,y} where 2x+1 = B2 - A2, 4y = x2 - A2 (B > A+1). But I don't even know if there are any 4-cliques at all; there are none below 106. Of course each vertex has finite degree so we can't just keep extending cliques. And because of the non-homogeneity I don't see a way to make a "copy" of a clique to try to extend. Maybe some sort of Ramsey result will help but I'm not too knowledgeable about those.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Color positive integers
« Reply #4 on: Jun 27th, 2009, 4:38pm » |
Quote Modify
|
How did you come up for your estimates as to when you need more colors? For instance, there is a 3-clique already for n = 8 (6,7,8).
|
« Last Edit: Jun 27th, 2009, 4:38pm by Obob » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Color positive integers
« Reply #5 on: Jun 27th, 2009, 10:12pm » |
Quote Modify
|
on Jun 27th, 2009, 4:38pm, Obob wrote:How did you come up for your estimates as to when you need more colors? For instance, there is a 3-clique already for n = 8 (6,7,8). |
| Brute force. But I had been initializing [1,8] WLOG as {1,2,0,1,2,0,1,2} without realizing there was a very large LOG when K=2. Code: #include<stdio.h> #include<stdlib.h> #include<assert.h> #define MN 1000001 #define ME 10000000 struct edge { int n; edge* p; } E[ME], *A[MN]; int C[MN], N, K, max; #define KK ((1<<K)-1) void recurse(int i) { if(i>max) { max=i; printf("colored [1,%d]\n",i-1); } if(i>N) { for(i=1;i<=N;i++) printf("%d,",C[i]); printf("\n"); exit(0); } int X=0; for(edge *p=A[i];p;p=p->p) X|=C[p->n]; X^=KK; for(int j=1;j<=X;j<<=1) if(X&j) { C[i]=j; recurse(i+1); } } int main(int ac, char** av) { N=(ac>1)?atoi(av[1]):100; K=(ac>2)?atoi(av[2]):3; assert(N<MN); int x,s,p,ne=0; for(x=3;x<=N;x++) { assert(ne<ME); A[x]=&E[ne++]; A[x]->n = x-1; } for(x=2;x<=N;x++) for(s=x+2, p=2*x; s<2*x && p<=N; p+=x, s++) { assert(ne<ME); edge *e=&E[ne++]; e->n = s; e->p = A[p]; A[p] = e; } printf("%d edges\n",ne); if(K>=3) { for(x=1;x<=8;x++) C[x]=1<<(x%3); recurse(9); } else recurse(1); printf("failed\n"); } |
|
|
« Last Edit: Jun 27th, 2009, 10:24pm by Eigenray » |
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Color positive integers
« Reply #6 on: Jul 25th, 2009, 7:49am » |
Quote Modify
|
I hadn't done it this way: in order to show that 3 colors were insufficient, I tried to find a set of 4 mutually joined vertices (i.e. a copy of the complete graph K_4 inside the graph you are creating). I haven't found such a set of 4 vertices, nor proved they cannot exist. I believe you are correct that 4 colors are necessary by the time we get to coloring the graph {1, 2, ..., 100}. I worked on it some by hand, except I forgot that there is only an edge between x+y and x*y when x and y were distinct, so my answer is just a little different: when we also insert edges between 2x and x^2, it seems to me we need 4 colors even just to color the subgraph with vertices {6, 7, 8, 9, 12, 13, 14, 15, 20, 36} (with vertices joining 6 to 9 and 12 to 36). The integers 18 & 2 show that there is an edge between the vertices labelled 18+2=20 and 18*2=36; briefly, 18,2 => 20 L 36 . We similarly have 6, 6 => 12 L 36 10, 2 => 12 L 20 so the graph contains a triangle {20,12,36}. If there is a 3-coloring, we can use the colors A,B,C for these vertices, say. Since also 12, 1 => 13 L 12 9, 4 => 13 L 36 there is another triangle {12,13,36} which shares an edge with this first triangle, forcing vertices 13 and 20 to have the same color, or in short: " 13 = 20 = A " We have another pair of triangles {6,7,8} and {7,8,12} sharing an edge: 4, 2 => 6 L 8 6, 1 => 6 L 7 7, 1 => 7 L 8 4, 3 => 12 L 7 6, 2 => 12 L 8 from which we conclude " 6 = 12 = B ". Next we can deduce the colors of vertices 9, 8 and 14: 3, 3 => 9 L 6 = B 5, 4 => 9 L 20 = A so 9 = C; 6, 2 => 8 L 12 = B (already noted) 8, 1 => 8 L 9 = C so 8 = A; 13, 1 => 14 L 13 = A 7, 2 => 14 L 9 = C so 14 = B. But now there's no color left for vertex 15: 5, 3 => 15 L 8 = A 14, 1 => 15 L 14 = B 12, 3 => 15 L 36 = C contradiction. So no 3-coloration is possible for this graph. (This argument uses 18 edges among the 10 vertices. That's probably not a minimal subgraph requiring 4 colors, but the reasoning is not difficult this way.) > I don't even know if there are any 4-cliques at all Nor do I. It's equivalent to asking whether there are (positive) integer points on an affine variety of dimension 4. That's a hard question to answer. I am inclined to think there are such cliques, in fact I'd guess they exist of arbitrarily high cardinality; but that's pure speculation, and if my guess is wrong that doesn't answer the question of the chromatic number anyway. Nice nugget.
|
« Last Edit: Jul 25th, 2009, 7:50am by Michael Dagg » |
IP Logged |
Regards, Michael Dagg
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Color positive integers
« Reply #7 on: Jul 26th, 2009, 7:17am » |
Quote Modify
|
Here is a 4-coloration of [1,224] (actually I continued it to [1, 234]) : 1, 2, 1, 2, 1, 3, 2, 1, 2, 4, 1, 3, 4, 3, 4, 3, 1, 4, 3, 1, 3, 2, 1, 2, 1, 2, 4, 2, 1, 2, 3, 1, 4, 2, 1, 2, 3, 1, 2, 1, 4, 2, 4, 1, 2, 3, 1, 4, 2, 1, 2, 3, 1, 2, 4, 1, 3, 2, 1, 2, 1, 2, 1, 4, 1, 2, 3, 1, 3, 2, 1, 3, 4, 1, 4, 2, 1, 2, 3, 1, 3, 1, 3, 2, 3, 1, 2, 1, 4, 2, 3, 1, 4, 3, 1, 3, 4, 1, 3, 2, 1, 2, 3, 1, 3, 1, 3, 4, 3, 1, 2, 3, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 2, 1, 3, 2, 1, 4, 2, 1, 4, 3, 1, 3, 4, 1, 3, 2, 1, 3, 2, 1, 3, 1, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 2, 3, 1, 2, 4, 3, 1, 2, 1, 3, 2, 1, 4, 1, 3, 1, 2, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 2, 1, 4, 1, 2, 1, 4, 2, 1, 4, 3, 1, 4, 2, 1, 3, 2, 1, 2, 4, 1, 2, 3, 1, 2, 3, 1, 3, 2, 1, 3, 2, 3, 1, 4, 1, 3, 2, 1, 3, 2, 1, 2, 3, 1, 2, 1, 2, 4 You might want to check that this satisfies your conditions. For example it assigns colors 3,2,1,2 to 6,7,8,9 respectively, reflecting the fact that all pairs of these vertices are contiguous except {7,9}. Graph-coloring is a subtle art. (It's an NP-complete problem.) The process of coloring goes a lot faster if you assign colors to the "difficult" vertices first and then, if there is no obstruction among them, work on the "easier" vertices. For example, a vertex with at most 3 neighbors will never pose a problem -- color the rest of the graph first and then assign any unused color to it. So we discard the vertices with valence 3 or less. Then of course some vertices _become_ low-valence vertices when some of their neighbors are removed; that is, we can apply this reduction recursively. In the case of the graph [1,224] this process stops when only 101 vertices remain. These I sorted according to their valence, their distance from 224, and the numbers of triangles to which they belong; my ordered list of vertices is then 224, 30, 36, 60, 39, 114, 25, 20, 16, 23, 29, 32, 31, 17, 19, 15, 12, ... Now, a brute-force search works fast, because the search does not waste time adjusting the colors of "far-away" vertices. I got essentially instantaneous results for N=224, so I tinkered a bit to extend it to N=233, which was also very fast. I tinkered a bit more but could not get a very-fast answer for N=234; nonetheless it was obvious from inspection that the very solution I had created for N=233 could be extended to N=234! (Evidently the inclusion of N=234 forced a sufficiently important permutation in the "importance" of the other vertices. I can't say more than that.) I have used here my slightly denser graph, the one with edges between x+x and x*x . That was harder to color than your sparser graph; in order to get a fast coloring I had to treat the vertex "8" as a "difficult" one, i.e. move it up in my ordered list.
|
« Last Edit: Jul 26th, 2009, 7:17am by Michael Dagg » |
IP Logged |
Regards, Michael Dagg
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Color positive integers
« Reply #8 on: Jul 26th, 2009, 9:50am » |
Quote Modify
|
> This would suggest the minimal number of colors for [1,n] is asymptotically > logarithmic. This is quite likely true, because you can achieve a rough approximation of a coloring of your graph by simply coloring each integer of the form 2^r * s (where s is odd) with color r ; this process uses log_2(N) colors to color [1,N] . In particular, you can always start by coloring all the odd integers with the same color. (I didn't see that earlier: if x,y are both odd, then xy is odd while x+y is even, so such an edge joins vertices of opposite parity. Same when x,y are of opposite parity. When x,y are both even, then the edge joins two vertices of the same parity -- both even. ) More generally EVERY edge joins two vertices divisible by different powers of 2 except when x = 2^r s1 and y = 2^r ( 2^r s2 - s1 ) for some r > 0 and some odd integers s1, s2, in which case x+y and xy are both of the form 2^(2r) * odd . So you can use one color for the odd vertices, one for the 2*odd's, one for the 8*odds, one for the 32*odds, etc., and then just worry about the subgraph consisting of the 4*odds, 16*odds, 64*odds, etc. Maybe you can even look at each of these subsets individually and use some kind of reduction-to-the-previous-case to show that each graph { 4^r, 4^r*3, 4^r*5, 4^r*7, ... 4^r*N } takes at most log(N) colors; then use that many (separate) colors on each of log(N) subgraphs, and you can at least conclude that no more than ( log(N) )^2 colors are needed for [1,N]. I started to work this out, for example, in the first and hardest part of this: the set of odd multiple of 4 . Various things have to have appropriate powers of 2 in them in order for there to be edges, so maybe this set of vertices stratifies in a way similar to the previous paragraph.
|
« Last Edit: Jul 26th, 2009, 9:50am by Michael Dagg » |
IP Logged |
Regards, Michael Dagg
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
Thanks for the tips. I modified my program (attached) to prune unnecessary vertices and sort by degree. It now finds a 4-coloring of 265 in a reasonable time: 0,1,0,1,0,1,0,2,1,3,2,3,2,3,0,2,3,0,1,0,1,0,1,0,1,2,0,1,0,1,0,1,0,2,0,1, 0,2,0,1, 3,0,1,2,1,0,1,0,1,2,1,0,1,2,0,2,1,3,2,0,2,1,3,1,3,2,1,0,1,2,0,1,0,1,3,0, 1,2,0,2, 0,2,0,3,1,2,0,3,0,2,3,1,3,0,1,3,1,0,2,3,0,2,3,0,1,2,0,3,1,3,0,2,1,0,3,2, 1,0,1,3, 0,1,0,2,3,2,0,3,1,2,0,2,1,0,2,0,1,2,0,2,0,2,1,0,1,0,2,1,0,2,0,1,0,2,0,3, 0,1,0,3, 0,2,0,2,0,2,0,1,0,1,2,0,2,1,0,3,0,1,0,2,0,1,0,1,3,2,0,2,0,2,0,3,1,0,3,2, 0,2,0,3, 0,1,0,2,1,2,0,1,0,2,1,0,2,0,1,2,0,2,1,3,2,0,1,2,0,1,0,1,0,2,0,2,0,2,1,0, 3,1,0,3, 0,1,2,0,1,0,2,1,0,1,0,2,0,2,0,3,0,2,0,3,0,2,0,1,0 But the time required ranges from a fraction of a second to several minutes (or more) depending on the value of N and how ties are broken when sorting. It would probably benefit from either randomization or better heuristics. But then I don't know much about graph coloring. on Jul 26th, 2009, 9:50am, Michael Dagg wrote:In particular, you can always start by coloring all the odd integers with the same color. (I didn't see that earlier: if x,y are both odd, then xy is odd while x+y is even, so such an edge joins vertices of opposite parity. Same when x,y are of opposite parity. When x,y are both even, then the edge joins two vertices of the same parity -- both even. ) |
| Is this true though? Couldn't you have, e.g., a K-clique of even nodes, and then two odd nodes, each connected to a different (K-1)-subset?
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Color positive integers
« Reply #10 on: Jul 26th, 2009, 5:05pm » |
Quote Modify
|
> Is this true though? Couldn't you have, e.g., a > K-clique of even nodes, and then two odd nodes, > each connected to a different (K-1)-subset? Sure (if I understand what you mean); so you'd need K colors for the even nodes, and then one more for the two odd nodes. Maybe I should have made it clear that when I said "start by coloring all the odd integers with the same color", I meant that this color would never be used again for any even vertex.
|
|
IP Logged |
Regards, Michael Dagg
|
|
|
Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Color positive integers
« Reply #11 on: Jul 26th, 2009, 5:17pm » |
Quote Modify
|
But then you are using K+1 colors when only K are necessary...
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Color positive integers
« Reply #12 on: Jul 26th, 2009, 7:34pm » |
Quote Modify
|
> But then you are using K+1 colors when only K are necessary... Oh, sure. This argument is only to be used when your goal is to obtain an asymptotic bound on the chromatic number. I was trying to show that roughly log(N) colors would suffice; adding one or even doubling the number of colors used is kind of inconsequential in such an arena.
|
|
IP Logged |
Regards, Michael Dagg
|
|
|
|