Approximate a metric on a finite set by one having rational distance

Question

Let $(X,d)$ be a finite metric space, and let $\varepsilon>0$ be given. In this question I would like to understand

how to show in detail the existence of a metric $\tilde{d}$ on $X$ that is "$\varepsilon$-close to $d$": \begin{align} |\tilde{d}(x,y)-d(x,y)|\leq\varepsilon,\qquad\forall x,y\in X \end{align} and "has rational distance": \begin{align} \tilde{d}(x,y)\in\mathbb{Q},\qquad\forall x,y\in X \end{align}

My motivation comes from the encounter with the Gromov-Hausdorff metric space $(\mathcal{M},d_{GH})$. In the proof of separability of $(\mathcal{M},d_{GH})$, the countable dense subset is given by the collection of all such finite metric spaces with rational distance (up to isometry). The idea is that any compact metric space can be "approximated" by a finite metric space, but the collection of all finite metric spaces (up to isometry) may still be uncountable (due to the many choices of metric on the same underlying set), so we restrict ourselves to those that have rational distance. Then we need to make sure that any metric on a finite space can be "approximated" by one that has rational distance. It is here where I am unable to spell out the detail.

My attempt was a constructive proof: Denote $X=\{x_i\}_{i=1}^N$, and denote $d(x_i,x_j)=|x_ix_j|$. Clearly, the interval $\big(|x_ix_j|-\varepsilon,|x_ix_j|+\varepsilon\big)$ always contains some rational number $q_{ij}$. The problem is how to choose them in order to make the triangle inequality \begin{align} q_{ij}\leq q_{ik}+q_{jk} \end{align} holds, so that we can define $\tilde{d}(x_i,x_j)=\tilde{d}(x_j,x_i)=q_{ij}$. For $i<j$ we always have $|x_ix_j|>0$, so I was thinking of diminishing it a little to get $q_{ij}$ while enlarging $|x_ix_k|$, $|x_jx_k|$ a little to get $q_{ik},q_{jk}$, but this seems not to work because the same $q_{ij}$ needs to appear in both sides of the triangle inequality (e.g. $q_{12}$ is on the L.H.S. of $q_{12}\leq q_{13}+q_{23}$ while on the R.H.S. of $q_{23}\leq q_{12}+q_{13}$).

Any comment, hint or answer is welcome and greatly appreciated.

Answer 1

Here are the steps of the proof, all quite elementary.

1. Suppose $X$ has cardinality $n$. Then each pseudometric on $X$ is encoded by a vector in ${\mathbb R}^N$, $N=n(n-1)/2$. The semipositivity conditions and triangle inequalities satisfied by the pseudometrics amount to a system of nonstrict linear (homogeneous) inequalities $f_k({\mathbf v})\ge 0$, $k=1,...,K$. Thus, the space of possible pseudometrics on $X$ is a closed convex cone $C$ in ${\mathbb R}^N$. Let $C^\circ\subset C$ denote the subset given by the strict inequalities $f_k({\mathbf v})> 0$, $k=1,...,K$. Then each vector in $C^\circ$ corresponds to a genuine metric on $X$ and $C^\circ$ is open in ${\mathbb R}^N$.

2. Show that the cone $C$ has nonempty interior. For instance, the discrete metric belongs to $C^\circ$, which is contained in the interior of $C$ (in fact, it equals to the interior of $C$ but we will not need this).

3. Use the fact that each closed convex subset of ${\mathbb R}^N$ (with nonempty interior) is the closure of its interior. (This is true in much greater generality of convex subsets in topological vector spaces, see here.)

4. Lastly, use density of rational points in the interior of $C$.

Answer 2

I have accepted Moishe Kohan's answer (thanks for the answer), but I reckon it doesn't hurt to supply an alternative solution. The following approach is inspired by the discussion above with CyclotomicField, though it may be slightly different from his/her original idea, and perhaps it may look less elegant.

---

I shall construct $\tilde{d}$ by a direct modification of $d$. First, let me begin with an informal discussion. By drawing pictures of triangles, it seems intuitively clear that as long as $r>0$ is chosen to satisfies \begin{align} r<\frac{1}{2}\min_{1\leq i<j\leq N}d(x_i,x_j) \end{align} then if we modify by choosing $\tilde{d}(x_i,x_j)$ to be a rational number $r$-close to $d(x_i,x_j)$, then the picture still looks like a triangle and $\tilde{d}$ could possibly be a metric. However, there is a small catch here. When we're drawing a picture of triangle, we have implicitly restricted ourselves to the case where the triangle inequalities on any three distinct points are all strict. However, we know that this may not always be the case; the triangle inequality is allowed to hold as an equality. In this case, no matter how small $r>0$ is chosen, it is always possible for a triangle inequality failing to hold for some three points.

For example, consider $X=\{x_1,x_2,x_3\}$ with \begin{align} d(x_1,x_2)=d(x_2,x_3)=1,\qquad d(x_1,x_3)=2 \end{align} If we now choose \begin{align} \tilde{d}(x_1,x_2)=\tilde{d}(x_2,x_3)=1-q,\qquad\tilde{d}(x_1,x_3)=2+q \end{align} (where $q\in\mathbb{Q}$ with $0<q<r$) then it is indeed true that $\tilde{d}(x_i,x_j)$ is always $r$-close to $d(x_i,x_j)$, but it also follows that \begin{align} \tilde{d}(x_1,x_3)>\tilde{d}(x_1,x_2)+\tilde{d}(x_2,x_3) \end{align} no matter how small the $r$ (hence $q$) is chosen. (Of course, for such three-point metric space, it is clear how to modify the metric correctly. What I wish to emphasize is that simply choosing $\tilde{d}(x_i,x_j)$ to be any rational number that is $r$-close to $d(x_i,x_j)$ does not always work.)

---

This motivates me to separate the problem into two cases. The first one is where the triangle inequalities on three distinct points are all strict. Since the metric space is finite, the number of triangle inequalities is also finite. Thus in this case, we have \begin{align} \delta:=\min\big\{d(x_i,x_k)+d(x_k,x_j)-d(x_i,x_j):1\leq i,j,k\leq N\text{ are all distinct}\big\} \end{align} is always positive. Now we may choose $r>0$ to satisfies \begin{align} r\leq\min\left\{\epsilon,\frac{\delta}{3}\right\} \end{align} Then, using the density of $\mathbb{Q}$ in $\mathbb{R}$, for each $1\leq i<j\leq N$ we choose a rational number $q_{ij}$ in the open interval $\big(d(x_i,x_j)-r,d(x_i,x_j)+r\big)$. Define $\tilde{d}$ by \begin{align} \tilde{d}(x_i,x_i)&=0,\qquad\forall 1\leq i\leq N \\ \tilde{d}(x_i,x_j)=\tilde{d}(x_j,x_i)&=q_{ij},\qquad\forall 1\leq i<j\leq N \end{align} To prove that $\tilde{d}$ is a metric on $X$, the only nontrivial thing remains to show is the triangle inequality. Due to our choice of $r$, we see that for each distinct $1\leq i,j,k\leq N$ \begin{align} \tilde{d}(x_i,x_j) &<d(x_i,x_j)+r \\ &\leq d(x_i,x_j)+\delta-2r \\ &\leq d(x_i,x_k)-r+d(x_k,x_j)-r \\ &<\tilde{d}(x_i,x_k)+\tilde{d}(x_k,x_j) \tag{*} \end{align} and the triangle inequality clearly holds if (at least) two of $i,j,k$ are equal. Hence, $\tilde{d}$ is a metric. It is clear that $\tilde{d}$ is $\epsilon$-close to $d$ and has rational distance.

---

The second case is that for some set of three distinct points in $X$, some triangle equality holds on them. In this case, the strategy is to first modify the metric into $d_{*}$ which belongs to the previous case. However, we need to be a little bit more careful. We shall first modify the smallest distance, then proceed in the ascending order. Formally, let \begin{align} S:=\left\{d(x_i,x_j):i\neq j\text{, and }d(x_i,x_j)=d(x_i,x_k)+d(x_k,x_j)\text{ for some }k\neq i,j\right\} \end{align} After reindexing if necessary, wlog suppose $d(x_1,x_2)=\min S$. Then there is some $k_1\neq 1,2$ such that \begin{align} d(x_1,x_2)=d(x_1,x_{k_1})+d(x_{k_1},x_2) \end{align} Modify $d$ into $d_1$ by \begin{align} d_1(x_1,x_{k_1}):&=d(x_1,x_{k_1})+\frac{\epsilon}{2} \\ d_1(x_{k_1},x_2):&=d(x_{k_1},x_2)+\frac{\epsilon}{2} \\ d_1(x,y):&=d(x,y) & \text{otherwise} \end{align} Then $d_1$ is $(\epsilon/2)$-close to $d$ and has one less triangle equality. If we define $S_1$ in the same way as $S$ but by using $d_1$, then we see that \begin{align} S_1=S\setminus\{d(x_1,x_2)\}=S\setminus\{d_1(x_1,x_2)\} \end{align} If $S_1=\emptyset$, then we are done: Choose $d_{*}=d_1$. Otherwise, we repeat the process. Note that by the minimality of $d(x_1,x_2)$ in $S$, we have \begin{align} d(x_1,x_{k_1}),d(x_{k_1},x_2)\notin S \end{align} Let $d_1(x_{i_1},x_{j_1})=d(x_{i_1},x_{j_1})=\min S_1$. Then there is a $k_2\neq i_1,j_1$ such that
\begin{align} d_1(x_{i_1},x_{j_1})=d_1(x_{i_1},x_{k_2})+d_1(x_{k_2},x_{j_1}) \end{align} Modify $d_1$ into $d_2$ by \begin{align} d_2(x_{i_1},x_{k_2}):&=d_1(x_{i_1},x_{k_2})+\frac{\epsilon}{4}, & \text{if } \{x_{i_1},x_{k_2}\}\neq\{x_1,x_{k_1}\},\{x_{k_1},x_2\} \\ d_2(x_{k_2},x_{j_1}):&=d_1(x_{k_2},x_{j_1})+\frac{\epsilon}{4}, & \text{if } \{x_{k_2},x_{j_1}\}\neq\{x_1,x_{k_1}\},\{x_{k_1},x_2\} \\ d_2(x,y):&=d_1(x,y) \end{align} We have imposed the conditions to ensure that $d_1(x_1,x_{k_1})$ and $d_1(x_{k_1},x_2)$ will not be further modified again. Then $d_2$ has one less triangle equality than $d_1$, and remains to be $(\epsilon/2)$-close to $d$.

Continue this process. It must end in finite number of steps, and we obtain $d_n$ for some $n\leq N$. Choose $d_{*}=d_n$. Then $d_{*}$ satisfies no any triangle equality on any set of three distinct points of $X$, so we are back to the first case. It then tells us that there is a metric $\tilde{d}$ with rational distance such that $\tilde{d}$ is $(\epsilon/2)$-close to $d_{*}$. Hence, $\tilde{d}$ is $\epsilon$-close to $d$.

To illustrate, let me provide an example. Let $X=\{x_1,x_2,x_3,x_4\}$ and suppose \begin{align} d(x_1,x_2)=d(x_2,x_3)=d(x_3,x_4)=1,\qquad d(x_1,x_3)=d(x_2,x_4)=2,\qquad d(x_1,x_4)=3 \end{align} Then $S=\big\{d(x_1,x_3),d(x_2,x_4),d(x_1,x_4)\big\}$.

1. The 1st step deals with \begin{align} d(x_1,x_3)=d(x_1,x_2)+d(x_2,x_3) \end{align} Define $d_1(x_1,x_2)=1+\epsilon/2$ and $d_1(x_2,x_3)=1+\epsilon/2$, and $d_1(x,y)=d(x,y)$ otherwise.

2. The 2nd step deals with \begin{align} d_1(x_2,x_4)&=d(x_2,x_4) \\ &=d(x_2,x_3)+d(x_3,x_4) \\ &=d_1(x_2,x_3)-\frac{\epsilon}{2}+d_1(x_3,x_4) \end{align} Since $\{x_2,x_3\}$ has already appeared in Step 1, we shall only modify $d_1(x_3,x_4)$. Define $d_2(x_3,x_4):=1+\frac{\epsilon}{4}$, and $d_2(x,y)=d_1(x,y)$ otherwise.

3. The last step deals with \begin{align} d_2(x_1,x_4)=d_2(x_1,x_2)-\frac{\epsilon}{2}+d_2(x_2,x_4) \end{align} Since $\{x_1,x_2\}$ has already appeared in the previous steps, we shall only modify $d_2(x_2,x_4)$. Define $d_3(x_2,x_4)=d_2(x_2,x_4)+\epsilon/6$ and $d_3(x,y)=d_2(x,y)$ otherwise. (Note: We can also start alternatively with \begin{align} d_2(x_1,x_4)=d_2(x_1,x_3)+d_2(x_3,x_4)-\frac{\epsilon}{4}. \end{align} In this case, set $d_3(x_1,x_3)=d_2(x_1,x_3)-\epsilon/6$. )

As a result, with $d_{*}=d_3$, we have \begin{align} d_{*}(x_1,x_2)=d_{*}(x_2,x_3)&=1+\frac{\epsilon}{2} \\ d_{*}(x_3,x_4)&=1+\frac{\epsilon}{4} \\ d_{*}(x_1,x_3)&=2 \\ d_{*}(x_2,x_4)&=2+\frac{\epsilon}{6} \\ d_{*}(x_1,x_4)&=3 \end{align} One can now check manually that $d_{*}$ satisfies strict triangle inequalities on every set of three distinct points.

---

Remark: It may be good to compare this solution to Moishe Kohan's answer.

1. Taking a closer look back at $(*)$, we see that the modification in the 1st case preserves strict triangle inequalities. This reflects the fact that the set $C^{\circ}$ of all metrics on $X$ satisfying strict triangle inequalities (on every set of distinct three points) is open (by suitably endowing the set of all (pseudo)metrics on $X$ a topology). This corresponds to Step 2 in his/her answer. See also the comment under the answer.
2. The 2nd case shows that every metric on $X$ can be approximated by one that satisfies strict triangle inequalities. In other words, every metric is in the closure of the open set $C^{\circ}$. This corresponds partly to Step 3 in his/her answer.

Hence, it seems that the two approaches are based on the same underlying structure of the space of all metrics on $X$.