Wednesday, 2 February 2011

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

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_1subset S_2subsetdots$ 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,yin 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 $frac12dle 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_+tomathbb R_+$ by
$$
f_k(t) = 10^{-2k}leftlfloor 10^{2k}(1-10^{-k})t rightrfloor .
$$
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 ${tge 2^{-k}}$. Then $frac12le a_kle b_kle a_{k+1}le 1$ for all $k$. (Indeed, we have $1-2cdot10^kle a_kle b_kle 1-10^k$.)


For every $x,yin S_k$, define $ell(x,y)=f_k(d(x,y))$ where $k=k(x,y)$ is the minimum number such that $x,yin 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_nin 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 $frac12dle d'le d$. It remains to show that $d'$ takes only rational values.



Lemma: If $x,yin 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_ksum_{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,yin S_k$. Thus all values of $d'$ are rational.

No comments:

Post a Comment