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

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.


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.


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!