wu :: forums « wu :: forums - Color positive integers » Welcome, Guest. Please Login or Register. Oct 3rd, 2023, 8:28am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Icarus, SMQ, towr, Grimbal, Eigenray, william wu)    Color positive integers « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Color positive integers  (Read 2216 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 #include #include #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<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(Nn = x-1;   }   for(x=2;x<=N;x++) for(s=x+2, p=2*x; s<2*x && p<=N; p+=x, s++) {     assert(nen = 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
 Re: Color positive integers   coloringintegers.cpp.txt « Reply #9 on: Jul 26th, 2009, 10:31am » Quote Modify

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »