Is there a dense subset of the real plane with all pairwise distances rational?

Question

I heard the following two questions recently from Carl Mummert, who encouraged me to spread them around. Part of his motivation for the questions was to give the subject of computable model theory some traction on complete metric spaces, by considering the countable objects as stand-ins for the full spaces, to the extent that they are able to do so.

Question 1. Is there a countable subset $D$ of the real plane $\mathbb{R}^2$ that is dense and has the property that the Euclidean distance $d(x,y)$ is a rational number for all $x,y\in D$?

The one dimensional analogue of this question has an easy affirmative answer, since the rationals $\mathbb{Q}$ sits densely in $\mathbb{R}$ and the distance between any two rationals is rational.

Question 2. More generally, does every separable complete metric space have a countable dense set $D$ with all distances between elements of $D$ rational? [Edit: Tom Leinster has pointed out that if the space has only two points, at irrational distance, this fails. So let us consider the case of connected spaces, generalizing the situation of Question 1.]

If one is willing to change to an equivalent metric (giving rise to the same topology), then the answer to Question 1 is Yes, since the rational plane $\mathbb{Q}\times\mathbb{Q}$ is dense in the real plane $\mathbb{R}\times\mathbb{R}$, and has all rational distances under the Manhattan metric, which gives rise to the same topology. Is the answer to the correspondingly weakened version of Question 2 also affirmative, if one is willing to change the metric?

Note that one cannot find an equivalent metric such that all distances in $\mathbb{R}^2$ become rational, since omitted values in the distance function lead to disconnectivity in the space. This is why the questions only seek to find a dense subset with the rational condition.

The question seems related to the question of whether it is possible to find large non-linear arrangements of points in the plane with all pair-wise distances being integers. For example, this is true of the integers $\mathbb{Z}$ sitting inside $\mathbb{R}$, but can one find a 2 dimensional analogue of this? Clearly, some small arrangements (triangles, etc.) are possible, but I am given to understand that there is a finite upper bound on the size of such arrangements. What is the precise statement about this that is known?

Answer 1

Let me answer Question 2.

Strong version: no. Consider $[0,1]$ with distance $d(x,y)=|x-y|^{1/3}$. There is no even a triple of points with rational distances - otherwise there would be a nonzero rational solution of $x^3+y^3=z^3$.

Weak version: yes. Let $(X,d)$ be the space in question. Construct sets $S_1\subset S_2\subset\dots$ such that each $S_k$ is a maximal $(2^{-k})$-separated net in $X$. Let $S$ be the union of these nets; then $S$ is countable and dense in $X$.

Now construct the following metric graph on $S$. For every $k$, connect every pair of points $x,y\in S_k$ by an edge whose length is $(1-10^{-k})d(x,y)$ rounded down to a multiple of $10^{-2k}$. The new distance $d'$ on $S$ is the induced length distance in this graph. It is easy to see that the edges outside $S_k$ do not affect the distances in $S_k$, hence all these distances are rational (multiples of $10^{-2k}$). The new metric $d'$ on $S$ satisfies $\frac12d\le d'\le d$, hence the completion of $(S,d')$ is the same set $X$ with an equivalent metric.

UPDATE. Here is a more detailed description without the term "metric graph".

For each $k$, define a function $f_k:\mathbb R_+\to\mathbb R_+$ by $$ f_k(t) = 10^{-2k}\left\lfloor 10^{2k}(1-10^{-k})t \right\rfloor . $$ The actual form of $f_k$ does not matter, we only need the following properties:

• $f_k$ takes only rational values with bounded denominators (by $10^{-k}$).

• Let $a_k$ and $b_k$ denote the infimum and the supremum of $f_k(t)/t$ over the set $\{t\ge 2^{-k}\}$. Then $\frac12\le a_k\le b_k\le a_{k+1}\le 1$ for all $k$. (Indeed, we have $1-2\cdot10^k\le a_k\le b_k\le 1-10^k$.)

For every $x,y\in S_k$, define $\ell(x,y)=f_k(d(x,y))$ where $k=k(x,y)$ is the minimum number such that $x,y\in S_k$. Note that $$ a_k d(x,y) \le \ell(x,y) \le b_k d(x,y) $$ for all such pairs $x,y$, since $S_k$ is a $(2^{-k})$-separated set. For a finite sequence $x_0,x_1,\dots,x_n\in S$ define $$ \ell(x_0,x_1,\dots,x_n) = \sum_{i=1}^n \ell(x_{i-1},x_i) . $$ I will refer to this expression as the $\ell$-length of the sequence $x_0,\dots,x_n$. Define $$ d'(x,y) = \inf\{ \ell(x_0,x_1,\dots,x_n) \} $$ where the infimum is taken over all finite sequences $x_0,x_1,\dots,x_n$ in $S$ such that $x_0=x$ and $x_n=y$. Clearly $d'$ is a metric and $\frac12d\le d'\le d$. It remains to show that $d'$ takes only rational values.

Lemma: If $x,y\in S_k$, then $d'(x,y)$ equals the infimum of $\ell$-lengths of sequences contained in $S_k$.

Proof: Consider any sequence $x_0,\dots,x_n$ in $S$ such that $x_0=x$ and $y_0=y$. Remove all points that do not belong to $S_k$ from this sequence. I claim that the $\ell$-length became shorter. Indeed, it suffices to prove that $$ \ell(x_r,x_s) \le \ell(x_r,x_{r+1},\dots,x_{s-1},x_s) $$ if $x_r$ and $x_s$ are in $S_k$ and the intermediate points are not. By the second property of the functions $f_k$, the left-hand side is bounded above by $b_k d(x_r,x_s)$ and every term $\ell(x_i,x_{i+1})$ in the right-hand side is bounded below by $b_k d(x_i,x_{i+1})$. So it suffices to prove that $$ b_k d(x_r,x_s) \le b_k\sum_{i=r}^{s-1} d(x_i,x_{i+1}), $$ and this is a triangle inequality multiplied by $b_k$. Q.E.D.

All $\ell$-lengths of sequences in $S_k$ are multiples of some fixed rational number (namely $10^{-2k}$). Hence $d'(x,y)$ is a multiple of the same number if $x,y\in S_k$. Thus all values of $d'$ are rational.

Answer 2

The question as to whether there is an infinite dense set in the plane with rational distances was posed by Ulam in 1945 and swiftly attracted the attention of Erdos. It is still an unsolved problem. One can construct examples of dense subsets of the unit circle with rational distances. In a recent preprint http://arxiv.org/abs/0806.3095 Solymosi and de Zeeuw prove that the only algebraic curves in the plane having dense subsets with rational distances are lines and circles.

Answer 3

Regarding the question in the final paragraph, one can't find infinitely many non-collinear points, that's the Erdős–Anning theorem. It's one of those marvellous results where the mathematical review contains the entire proof...

However, it is possible to find any finite number - eg by finding an integer which can be written as the difference of two squares in lots of ways and then drawing the corresponding right-angled triangles on top of each other. It doesn't help at all with your earlier questions though. An interesting follow up question is to find points with no 3 on a line and no 4 on a circle - this is Section D20 of Guy's Unsolved Problems in Number Theory - apparently no 7 point set is known.

Edit: change that 7 to an 8, cf Tony Huynh's answer!

Answer 4

This sort of addresses the question in your last paragraph, but it is actually a bit tangential. Hopefully it is still of interest.

It is well known that every planar graph has an embedding such that each edge is a straight line segment. It is therefore natural to ask if every planar graph has an embedding in $\mathbb{R}^2$ such that the length of each edge is integral. This was first conjectured by Kemnitz and Harborth. It was proved for cubic planar graphs by Geelen, Kuo, and McKinnon here.

Edit: After reading the paper a bit more carefully, I see that it is more related to the question at hand than I initially thought. Apparently, Erdos posed the following question:

How many points can we find in the plane with pairwise rational distances such that no three are on a line and no four are on a circle?

A collection of seven such points has been found by Kriesel and Kurz, but it remains open whether a collection of 8 such points exists.

Also, Theorem 2.1 of the paper, proven by Berry seems to be of interest.

Theorem. Let $A,B,C$ be non-colinear points of $\mathbb{R}^2$ such that $d(A,B), d(A,C)^2$, and $d(B,C)^2$ are rational. Then the set of points of $\mathbb{R}^2$ that are rational distance from each of $A,B$, and $C$ forms a dense subset of $\mathbb{R}^2$.

Theorem 2.2 of the same paper seems to be quite pertinent as well.

Answer 5

Victor Klee and Stan Wagon write about this and other fun problems in their book: Old and New Unsolved Problems in Plane Geometry and Number Theory