wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Color positive integers
        
(Message started by: Obob on Jun 25^th, 2009, 1:12am)

Title: Color positive integers
Post by Obob on Jun 25^th, 2009, 1:12am

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?

Title: Re: Color positive integers
Post by Eigenray on Jun 27^th, 2009, 10:27am

Probably not :-/
Is it possible to construct arbitrarily large cliques? A set where for any two elements x,y either x²-4y or y²-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.

Title: Re: Color positive integers
Post by Obob on Jun 27^th, 2009, 11:36am

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.

Title: Re: Color positive integers
Post by Eigenray on Jun 27^th, 2009, 1:24pm

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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifS, with x>y, either x=y+1 or y²-4x is a non-zero perfect square. There are certainly lots of 3-cliques, for example {x,x+1,y} where 2x+1 = B² - A², 4y = x² - A² (B > A+1). But I don't even know if there are any 4-cliques at all; there are none below 10⁶.

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.

Title: Re: Color positive integers
Post by Obob on Jun 27^th, 2009, 4:38pm

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

Title: Re: Color positive integers
Post by Eigenray on Jun 27^th, 2009, 10:12pm

on 06/27/09 at 16:38:01, 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");
}

Title: Re: Color positive integers
Post by Michael Dagg on Jul 25^th, 2009, 7:49am

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.

Title: Re: Color positive integers
Post by Michael Dagg on Jul 26^th, 2009, 7:17am

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.

Title: Re: Color positive integers
Post by Michael Dagg on Jul 26^th, 2009, 9:50am

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

Title: Re: Color positive integers
Post by Eigenray on Jul 26^th, 2009, 10:31am

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 07/26/09 at 09:50:14, 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?

Title: Re: Color positive integers
Post by Michael Dagg on Jul 26^th, 2009, 5:05pm

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

Title: Re: Color positive integers
Post by Eigenray on Jul 26^th, 2009, 5:17pm

But then you are using K+1 colors when only K are necessary...

Title: Re: Color positive integers
Post by Michael Dagg on Jul 26^th, 2009, 7:34pm

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