93
$\begingroup$

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?

$\endgroup$
10
  • 12
    $\begingroup$ Am I being dense (ha!) or is the answer to 2 "no" for trivial reasons? Take a two-point metric space with the points an irrational distance apart. $\endgroup$ Mar 23, 2010 at 18:29
  • 1
    $\begingroup$ Yes, "connected" (or maybe "path-connected") would certainly make it more interesting. But the weakened version of question 2 (in its original form) is also interesting. $\endgroup$ Mar 23, 2010 at 18:50
  • 3
    $\begingroup$ Congrats on reaching 10k! $\endgroup$ Mar 23, 2010 at 18:50
  • 6
    $\begingroup$ I think of people with 10k as "made", in the mafia sense. Not that I didn't respect you already. $\endgroup$ Mar 23, 2010 at 18:55
  • 2
    $\begingroup$ There is a blog post by Terence Tao on this problem at terrytao.wordpress.com/2014/12/20/… . The summary is that the Bombieri-Lang conjecture would give a negative answer to Question 1, and so in particular no positive solution is expected. Thank you for publicizing this problem, @Joel. $\endgroup$ Jul 6, 2016 at 21:52

5 Answers 5

62
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I am likely to accept this answer, since it seems to completely settle Question 2. Could you explain a bit more about d', particularly when x and y are in different S_k's by several levels? $\endgroup$ Mar 27, 2010 at 15:45
  • $\begingroup$ The sets $S_k$ are nested, so every pair of points $x,y\in S$ have a common $S_k$ to which they both belong (actually, infinitely many of such $S_k$'s and hence infinitely many edges between them, but only the first and the shortest one is in effect). The point is that $d'(x,y)$ is realized by path in $S_k$ - if you decide to go outside $S_k$ and return back later, you save less distance (compared to $d$) than if you go through an edge in $S_k$. Would you like to see a formal argument with sums and inequalities? $\endgroup$ Mar 27, 2010 at 16:23
  • $\begingroup$ I added more details about $d'$. $\endgroup$ Mar 27, 2010 at 22:29
82
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you, Robin, for this extremely interesting answer. I accepted Sergei's answer, because he provided a full answer to my question 2, whereas you provided an answer to a fascinating question that I however did not actually ask. (Nevertheless, I point out that a consolation for you is the realistic possibility of a 'populist' gold badge, relatively rare here on MO.) $\endgroup$ Apr 2, 2010 at 1:52
  • 1
    $\begingroup$ Wikipedia: Erdős–Ulam problem $\endgroup$ Oct 3, 2017 at 7:40
20
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Thanks very much for this answer, which surely addresses my last paragraph. $\endgroup$ Mar 23, 2010 at 18:47
  • 1
    $\begingroup$ Indeed, +1. The link to the 7 point configuration is here. $\endgroup$
    – Tony Huynh
    Mar 23, 2010 at 18:50
16
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Regarding Joel's final paragraph, one can't find infinitely many non-collinear points, see eg en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Anning_theorem. 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. $\endgroup$
    – dke
    Mar 23, 2010 at 18:22
  • $\begingroup$ DKE, why don't you post your answer as an answer, so that we can vote it up appropriately? I understand that it doesn't answer Question 1 or 2, but it does answer the question in my final paragraph. $\endgroup$ Mar 23, 2010 at 18:25
  • $\begingroup$ Okay, will do... $\endgroup$
    – dke
    Mar 23, 2010 at 18:31
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.