Published in Discrete Mathematics 82 (1990), no. 1, pp. 53–56.

DISTANCES FORBIDDEN BY SOME TWO-COLORING OF ℚ^{2}

Michael Reid, Douglas S. Jungreis and Dave Witte

Harvard University, Harvard University, and Massachusetts Institute of Technology

Received 6 October 1986, Revised 15 March 1988

0. Introduction

In 1973, D. R. Woodall [3] showed that there is a 2-coloring of ℚ^{2} (the rational points in the plane) that forbids the distance 1 (i.e. no two points of the same color are at distance 1 apart). Recently, this result was strengthened by P. D. Johnson, Jr. [2], who showed there is a 2-coloring of ℚ^{2} that simultaneously forbids all Euclidean distances of the form \sqrt{p/q} with p and q odd positive integers. Johnson’s 2-coloring obviously forbids certain other distances (e.g. \sqrt{6}) because no two rational points in the plane are precisely that far apart. We show in Section 1 that Johnson’s coloring is optimal: for any distance d not covered by either of these two cases, no 2-coloring of ℚ^{2} forbids both of the distances 1 and d (see Theorem 1.5). This settles Problem 4 of [2]. In Section 2, we give a similar solution of Problems 2 and 3 of [2].

1. Two-colorings of ℚ^{2}

Definition. Let D ⊆ ℝ^{+}. A 2-coloring of ℚ^{2} forbids the distances D if for all x, y ∈ ℚ^{2}, with d(x, y) ∈ D, the two points x and y have different colors.

Definition. For any D ⊆ ℝ^{+}, we say there is an odd D-cycle (in ℚ^{2}) if there exist s_{1}, s_{2}, …, s_{n} ∈ ℚ^{2} such that s_{1} + s_{2} + ⋯ + s_{n} = 0 (under componentwise addition), ||s_{i}|| ∈ D for each i, and n is odd. (Not having an odd D-cycle means a certain subset of ℚ^{2} is “weakly two-free” in the language of [1, 2].)

The following lemma follows from the fact that a graph is bipartite iff it contains no odd cycle.

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 05C15 (51K05).

Lemma 1.1. (cf. [1]) Let D ⊆ ℝ^{+}. There is no 2-coloring of ℚ^{2} that forbids D iff there is an odd D-cycle.

Lemma 1.2. (cf. [2, Lemma 1]) Let d ∈ ℝ^{+} and set d′ = kd, where k is any odd positive integer. Then there is an odd {1, d}-cycle iff there is an odd {1, d′}-cycle.

Proof. (⇒) Suppose u_{1} + u_{2} + ⋯ + u_{l} + s_{1} + s_{2} + ⋯ + s_{m} = 0, with l + m odd, and where ||u_{i}|| = 1 for each i, and ||s_{j}|| = d for each j. Setting s′_{j} = k · s_{j}, we have

k · u_{1} + k · u_{2} + ⋯ + k · u_{l} + s′_{1} + s′_{2} + ⋯ + s′_{m} = 0,

and kl + m is odd.

(⇐) Suppose u_{1} + u_{2} + ⋯ + u_{l} + s′_{1} + s′_{2} + ⋯ + s′_{m} = 0. Setting s_{j} = \frac{1}{k} · s′_{j}, we have

u_{1} + u_{2} + ⋯ + u_{l} + k · s_{1} + k · s_{2} + ⋯ + k · s_{m} = 0,

and l + km is odd. □

Proposition 1.3. Let p, q ∈ ℤ^{+}, with p even and q odd, and assume d = \sqrt{p/q} occurs as a distance between rational points in the plane. Then there is an odd {1, d}-cycle.

Proof. By Lemma 1.2 it suffices to show there is an odd {1, qd}-cycle. Since d occurs as a distance, there are rational numbers α and β with α^{2} + β^{2} = pq. Any integer that is a sum of two rational squares is a sum of two integer squares, so we may assume that α and β are non-negative integers. Now α·(1, 0)+β·(0, 1)+(−α, −β) = 0, and ||(−α, −β)|| = \sqrt{pq} = qd. Since α^{2} + β^{2} = pq is even, α and β have the same parity, so α + β + 1 is odd. □

Lemma 1.4. Let D ⊆ ℝ^{+} and d_{0} ∈ ℝ^{+}. Assume d_{0} occurs as a distance between two rational points in the plane. Then there is an odd D-cycle iff there is an odd (d_{0} · D)-cycle (where d_{0} · D = {d_{0}d | d ∈ D}).

Proof. By assumption there are α, β ∈ ℚ with \sqrt{α^{2} + β^{2}} = d_{0}. Then \binom{α β}{−β α} ∈ GL_{2}(ℚ) is a linear transformation of the plane that preserves the set of rational points and expands all distances precisely by a factor of d_{0}. The lemma follows. □

Theorem 1.5. Let d ∈ ℝ^{+}. Assume there are x, y ∈ ℚ^{2} with d(x, y) = d, and that d can be written in the form d = \sqrt{p/q} with p, q ∈ ℤ^{+} and p + q odd. Then no 2-coloring of ℚ^{2} forbids both of the distances 1 and d.

Proof. By Lemma 1.1, we need only show there is an odd {1, d}-cycle in ℚ^{2}. By Lemma 1.4, there is an odd {1, d}-cycle iff there is an odd {1/d, 1}-cycle. So, replacing d by 1/d if necessary, we may assume d = \sqrt{p/q} where p is even and q is odd. Then Proposition 1.3 applies. □

Corollary 1.6. Let D ⊆ ℝ^{+}. No 2-coloring of ℚ^{2} forbids the distances D iff there are d_{1}, d_{2} ∈ D such that:

(1) Each of d_{1} and d_{2} occurs as a distance between rational points in the plane; and (2) There exist p, q ∈ ℤ^{+} such that d_{1}/d_{2} = \sqrt{p/q} and p + q is odd.

DISTANCES FORBIDDEN BY SOME TWO-COLORING OF ℚ^{2} 3

2. Two-colorings of A_{n} and ℚ^{3}

Let A_{n} = {(a_{1}/b_{1}, a_{2}/b_{2}, …, a_{n}/b_{n}) | a_{i}, b_{i} ∈ ℤ and each b_{i} is odd }. We now prove the natural analogue of Theorem 1.5 for A_{n} and for ℚ^{3}. This settles problems 2 and 3 of [2].

Proposition 2.1. Let p, q ∈ ℤ^{+}, with p even and q odd. Set d = \sqrt{p/q} and assume there are x, y ∈ A_{n} with d(x, y) = d. Then no 2-coloring of A_{n} forbids both of the distances 1 and d.

Proof. (cf. proof of Proposition 1.3) We need only show there is an odd {1, d}-cycle in A_{n} (see Lemma 1.1). Write d^{2} = α_{1}^{2} + α_{2}^{2} + ⋯ + α_{n}^{2}, where each α_{i} is rational with odd denominator. We may rescale in the manner of Lemma 1.2 to assume each α_{i} is an integer, so d^{2} is an even integer. Then

α_{1} · (1, 0, …, 0) + α_{2} · (0, 1, …, 0) + ⋯ + α_{n} · (0, 0, …, 1) + (−α_{1}, −α_{2}, …, −α_{n}) = 0,

and α_{1} + α_{2} + ⋯ + α_{n} + 1 is odd. □

Proposition 2.2. Let d ∈ ℝ^{+}. Assume there are x, y ∈ ℚ^{3} with d(x, y) = d, and that d can be written in the form d = \sqrt{p/q} with p, q ∈ ℤ^{+} and p + q odd. Then no 2-coloring of ℚ^{3} forbids both of the distances 1 and d.

Proof. We need only show there is an odd {1, d}-cycle in ℚ^{3} (see Lemma 1.1). Write p/q = α_{1}^{2} + α_{2}^{2} + α_{3}^{2} (with each α_{i} ∈ ℚ).

Case 1. p is even and q is odd. It follows that α_{1}, α_{2}, α_{3} have odd denominators (when written in lowest terms). Now apply the proof of Proposition 2.1.

Case 2. p is odd and q is even. At least one of α_{1}, α_{2}, α_{3} must have even denominator (when written in lowest terms). Assume it is α_{1} = p_{1}/q_{1}. Note

p_{1} · (1, 0, 0) + \frac{q_{1}}{2} · (−α_{1}, α_{2}, α_{3}) + \frac{q_{1}}{2} · (−α_{1}, −α_{2}, −α_{3}) = 0,

and p_{1} + q_{1} is odd. □

Question. Is the analogue of Lemma 1.4 (and, hence, also the analogue of Corollary 1.6) true for A_{n} and ℚ^{3}?

Acknowledgments

This work was done under the direction of Professor Joseph A. Gallian at the University of Minnesota, Duluth. Funding was provided by the Research at Undergraduate Institutions program of the National Science Foundation under Grant Number DMS8407498, with additional support from the University of Minnesota.

References

1. P. D. Johnson, Coloring abelian groups, Discrete Mathematics 40 (1982), 219–223, MR83k:20059.

2. Peter D. Johnson, Jr., Two-colorings of a dense subgroup of ℚ^{n} that forbid many distances, Discrete Mathematics 79 (1990), no. 2, 191–195, MR91d:05046.

3. D. R. Woodall, Distances realized by sets covering the plane, Journal of Combinatorial Theory, Series A 14 (1973), 187–200, MR46 #9868.