Distances Forbidden by Some Two-coloring of Q²

Distances Forbidden by Some Two-coloring of Q², by Michael Reid, Douglas S. Jungreis and Dave Witte
Discrete Mathematics 82 (1990), no. 1, pp. 53-56.
[DOI] [Math Reviews] [Zentralblatt]
.dvi (13k) .ps (222k) .ps.gz (105k) .pdf (74k)
Woodall [2] has shown that the rational points in the plane may be colored with two colors so that any two points at distance 1 have different colors. Johnson [1] extended this to show that there is a two-coloring that "forbids" not only the distance 1 , but also every distance of the form √(p/q) , where p and q are odd positive integers. Johnson's coloring also forbids some other distances, such as √6 , because no two rational points are precisely that far apart. We show that Johnson's coloring is optimal, in the sense that, if d actually occurs as a distance, and d is not of the form √(p/q) , for odd positive integers p and q , then no two-coloring of Q² forbids both the distance 1 and d . This settles one of Johnson's questions. We also consider two-colorings of Q³ , and solve two more of his problems.
[1] Peter D. Johnson, Jr., Two-colorings of a dense subgroup of Qn, Discrete Mathematics 79 (1990), no. 2, pp. 191-195. [Math Reviews] [Zentralblatt]
[2] D. R. Woodall, Distances realized by sets covering the plane, Journal of Combinatorial Theory, Series A 14 (1973) pp. 187-200. [Math Reviews] [Zentralblatt]
Research page Home page E-mail
Updated January 8, 2008.