Number coloring of the rational plane General forum

12 replies. Last post: 2016-07-21

Reply to this topic Return to forum

Number coloring of the rational plane
  • Carroll at 2016-07-21

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

  • wccanard at 2016-07-21

    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.

  • wccanard at 2016-07-21

    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.

  • Tom Ace at 2016-07-21

    http://webbuild.knu.ac.kr/~trj/HN.pdf addresses the rational plane problem starting on page 17.

  • wccanard at 2016-07-21

    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.

  • Carroll at 2016-07-21

    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.

  • Tasmanian Devil at 2016-07-21

    The last link is for a regular polygon, which is not required for the application, only that all side lengths are equal.

  • wccanard at 2016-07-21

    I googled “pentagon in the plane” but all I got was 9/11 references :-( That was “plane in the pentagon” google!

  • wccanard at 2016-07-21

    Tasmanian Devil: I think the *answer* to that stackexchange question only assumes equal side lengths, so I think it's OK and another argument.

  • Tasmanian Devil at 2016-07-21

    Ah yes, this is true.

  • Carroll at 2016-07-21

    More on coloring for the holidays, a bunch of 9 simple problems:

    http://www.cut-the-knot.org/proofs/two_color.shtml

  • Tasmanian Devil at 2016-07-21

    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

Return to forum

Reply to this topic