Number coloring of the rational plane General forum
12 replies. Last post: 2016-07-21
Reply to this topic Return to forumReturn to forum
You have 0 new messages
You have 0 games on move.
You have 0 invitations to game.
12 replies. Last post: 2016-07-21
Reply to this topic Return to forumAt the end of his monthly column in the October 1960 issue of Scientific American, Martin Gardner asked how many colors are needed to color the plane in such a way that no two points that are unit distance apart have the same color. He quoted L. Moser as saying, what is in any case easy to prove, that four colors are necessary and seven sufficient.
I am interested in coloring of the rational plane. I have read that two coloring is possible, but I'm not sure how.
Let say that a rational point (a/b,c/d) in its lower term is either White or Black, how to determine its color based on the parity of a,b,c,d ?
The unit circle can be parametrized by a rational t by (t²-1/t²+1, 2t/t²+1) which yields only odd denominators, but how to deal with rationals with even denominators?
For the general case there is a known solution used based on a convex map of the plane with seven colors which I believe is the best solution, any argument for the existence of a six colors solution?
Spoiler below for a solution for points with odd denominators:
points with numerators both odd or even are White, the others are Black.
Colouring with two colours is equivalent to proving that there is no polygon in the plane with rational coordinates for vertices, unit side lengths, and an odd number of sides, right? Because you're just asking that the graph be bipartite. I'd never heard that result before. Do you remember your source? You could ask on math.stackexchange.com maybe.
You can't colour points depending only on the parity of a,b,c,d. For example (1/2,1/2) and (11/10,13/10) are distance 1 apart but both have a,c odd and b,d even.
http://webbuild.knu.ac.kr/~trj/HN.pdf addresses the rational plane problem starting on page 17.
Thanks Tom. So in fact Carroll essentially had it. He's already explained how to do it for pairs (x,y) where x and y both have odd denominator, or are equivalently in the subring Z_(2) of Q (Z_(2) just means rationals with odd denominator – the 2-adically integral rational numbers). To do the general case just observe that (Z_(2))2 is a sub*group* of Q2 and if two points are a unit distance apart they must be in the same coset, so just colour every coset by translating a fixed point in it to the origin and then using Carroll's colouring.
Thanks both for reference and clarifications!
On the impossible odd-sided rational polygon there is a nice direct proof here: http://math.stackexchange.com/questions/735767/how-to-show-that-a-regular-pentagon-cant-have-all-coordinates-rational.
The last link is for a regular polygon, which is not required for the application, only that all side lengths are equal.
I googled “pentagon in the plane” but all I got was 9/11 references :-( That was “plane in the pentagon” google!
Tasmanian Devil: I think the *answer* to that stackexchange question only assumes equal side lengths, so I think it's OK and another argument.
More on coloring for the holidays, a bunch of 9 simple problems:
http://www.cut-the-knot.org/proofs/two_color.shtml
This 7-colouring of the cells of the hexagonal grid has the property that any 3 colours induce connected components with at most 9 cells. (The optimum is either 8 or 9.) http://www.neutreeko.net/h7/abcdefg.htm