Author 
Topic: Color positive integers (Read 2201 times) 

Obob
Senior Riddler
Gender:
Posts: 489


Color positive integers
« on: Jun 25^{th}, 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 27^{th}, 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 x^{2}4y or y^{2}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 27^{th}, 2009, 10:13pm by Eigenray » 
IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Color positive integers
« Reply #2 on: Jun 27^{th}, 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 27^{th}, 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 y^{2}4x is a nonzero perfect square. There are certainly lots of 3cliques, for example {x,x+1,y} where 2x+1 = B^{2}  A^{2}, 4y = x^{2}  A^{2} (B > A+1). But I don't even know if there are any 4cliques at all; there are none below 10^{6}. Of course each vertex has finite degree so we can't just keep extending cliques. And because of the nonhomogeneity 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 27^{th}, 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 3clique already for n = 8 (6,7,8).

« Last Edit: Jun 27^{th}, 2009, 4:38pm by Obob » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Color positive integers
« Reply #5 on: Jun 27^{th}, 2009, 10:12pm » 
Quote Modify

on Jun 27^{th}, 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 3clique 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",i1); } 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 = x1; } 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 27^{th}, 2009, 10:24pm by Eigenray » 
IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Color positive integers
« Reply #6 on: Jul 25^{th}, 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 3coloring, 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 3coloration 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 4cliques 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 25^{th}, 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 26^{th}, 2009, 7:17am » 
Quote Modify

Here is a 4coloration 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}. Graphcoloring is a subtle art. (It's an NPcomplete 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_ lowvalence 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 bruteforce search works fast, because the search does not waste time adjusting the colors of "faraway" 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 veryfast 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 26^{th}, 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 26^{th}, 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 reductiontothepreviouscase 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 26^{th}, 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 4coloring 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 26^{th}, 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 Kclique of even nodes, and then two odd nodes, each connected to a different (K1)subset?


IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Color positive integers
« Reply #10 on: Jul 26^{th}, 2009, 5:05pm » 
Quote Modify

> Is this true though? Couldn't you have, e.g., a > Kclique of even nodes, and then two odd nodes, > each connected to a different (K1)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 26^{th}, 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 26^{th}, 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



