7
$\begingroup$

I've been struggling to prove the following fact for some time now, and I didn't manage to do so.

Suppose $W : \Bbb{R}^n \to \Bbb{R}_+$ is a continuous, positive function, with exactly $n$ zeros $\alpha_1,...,\alpha_n$. Define the following 'distance':

$ d(\xi_i,\xi_j)=\inf\left\{\int_0^1 \sqrt{W(\gamma(t))}| \gamma'(t)|dt : \gamma \in C^1([0,1];\Bbb{R}^n), \gamma(0)=\xi_i,\ \gamma(1)=\xi_j\right\}$

Suppose I have a set of real, positive numbers $\sigma_{ij}>0,\ i \neq j$ with the property that $\sigma_{ij}=\sigma_{ji}$ and $\sigma_{ij} \leq \sigma_{ik}+\sigma_{kj},i,j,k=1,...,n$.

My question is:

Can we find $\alpha_i, i=1..n$ and $W$ with the desired properties, such that $d(\alpha_i,\alpha_j)=\sigma_{ij}$?

I have asked the question on MathOverflow also, and got an answer which is not complete and I couldn't finish it myself. It is possible to prove the existence of such a function if there is a finite metric space with distances $\sigma_{ij}$ that can be embedded in $\Bbb{R}^n$, but I would like to prove the general case also.

I think I might have proved a weaker form, that there exists a sequence of continuous functions $W_n$ such that the corresponding distances $d^n(\alpha_i,\alpha_j)$ converge to $\sigma_{ij}$. I did this by embedding in $\Bbb{R}^n$ a set of $n$ points with pairwise distance $1$. Then define a function $f$ on the union $K$ of segments with these endpoints such that the path-integral on each segment $[\alpha_i,\alpha_j]$ is $\sigma_{ij}$. Then extend $f$ to the whole $\Bbb{R}^N$ continuously and positively and consider $\sqrt{W_\varepsilon(x)}=f(x)+\frac{1}{\varepsilon}d(x,K)$. Then I used a $\Gamma$-convergence trick to obtain that the limits of minimizers $d^\varepsilon(\alpha_i,\alpha_j)$ for $W_\varepsilon$ as $\varepsilon \to 0$ are in fact $\sigma_{ij}$.

I have a few questions:

  1. It seems that I've used the existence of geodesics, i.e. distance minimizing paths between $\alpha_i,\alpha_j$. I have heard of Hopf-Rinow theorem, but I've never used this theorem. Is it applicable here?

  2. Does the existence of the sequence of functions $W_\varepsilon$ such that the respective geodesics with lengths $d^\varepsilon(\alpha_i,\alpha_j) \to \sigma_{ij}$ implies somehow the existence of my desired function?

  3. Is there another way to approach the problem? I tried to consider functions of the form $ W(x)=\prod_{i=1}^n |x-\alpha_i|^2 \cdot \sum_{1\leq i so that the function has as many parameters as the desired distances $\sigma_{ij}$. The problem is that when $a_{ij}$ change, the minimizing path, if exists also change, and this is not a linear problem.

I have a feeling that the answer to this question can't be unknown, but I haven't found a proof or reference for it until now.

  • 0
    @GenericHuman: I am familiar with the difference between English and the 'rest of the world' formulation. :) I just slipped positive instead of non-negative, because that was the word I was accustomed to.2012-05-14

1 Answers 1

1

Here's a brute force construction that I think works. If not, then, well, it's at least a start. I'll try to be as precise as possible. Here is the statement I would like to prove.

Let $n\geq 2$ be an integer, and let $\sigma_{ij}$ for $i,j\in \{1,\ldots, n\}$ be real numbers as given in the problem. Let $\alpha_1,\ldots, \alpha_n$ be any distinct points in $\mathbb{R}^3$. Then there is a continuous $W\colon \mathbb{R}^3\to \mathbb{R}_{\geq 0}$ which vanishes precisely at the $\alpha_i$ such that $d_W(\alpha_i,\alpha_j) = \sigma_{ij}$, where $d_W$ is the distance induced by $W$ as described in the problem.

It is easy to see that if you could prove this, then it holds in $\mathbb{R}^m$ for all $m\geq 3$, just by embedding $\mathbb{R}^3\subseteq\mathbb{R}^m$. The case of $\mathbb{R}^2$ seems a little trickier, and I will talk about it later.

Lemma 1. Suppose that $\alpha_1,\ldots, \alpha_n\in \mathbb{R}^3$ are distinct points such that there is an $W$ solving the problem for the $\alpha_i$. Let $\beta_1,\ldots, \beta_n\in \mathbb{R}^3$ be any other distinct points. Then there is a $W'$ solving the problem for the $\beta_i$.

Proof: Let $h\colon \mathbb{R}^3\to \mathbb{R}^3$ be a homeomorphism mapping $\beta_i$ to $\alpha_i$. To get $W'$ you need only pull back the metric induced by $W$ via $h$.

Thanks to this lemma, it suffices to prove the existence of $W$ for any (convenient) set of points $\alpha_1,\ldots, \alpha_n\in \mathbb{R}^3$. I will choose $\alpha_1,\ldots,\alpha_n$ as follows.

Assumption. Let $L_{ij}$ denote the straight line segment connecting $\alpha_i$ and $\alpha_j$. We assume $\alpha_1,\ldots,\alpha_n$ are such that two distinct $L_{ij}$ can only intersect at their endpoints. Moreover, we assume that $\|\alpha_i - \alpha_j\|\ll\sigma_{ij}$.

This assumption very much uses the fact that we are in $\mathbb{R}^3$; it would not work in $\mathbb{R}^2$.

I will use the following notation.

  • $B_i$ will denote the open Euclidean ball around $\alpha_i$ of radius $\delta>0$, where $\delta$ is small compared to the Euclidean distances between the $\alpha_i$, say $\delta = 10^{-8}\min_{i\neq j}\|\alpha_i - \alpha_j\|$.
  • $T_{ij}$ will denote the open set $\{x\in \mathbb{R}^3 : d(x,L_{ij})<\varepsilon\}$, where $\varepsilon\ll\delta$ will be determined later.
  • $M$ will denote a very large positive constant, to be determined later.

The function $W$ will be defined piecewise.

Step 1: For $x\in \mathbb{R}^3$ such that $x\notin \bigcup_i B_i\cup \bigcup_{ij} T_{ij}$, we define $W(x) = M$.

Step 2: Choose $\varepsilon$ to be small enough so that any two distinct $T_{ij}$ have intersection contained within one of the $B_i$. You can always do this by our assumption on the $\alpha_i$. We will next define $W$ on the set $\bigcup_{ij}T_{ij}\smallsetminus\bigcup_i B_i$. This set is a disjoint union of "cylinders" $T_{ij}\smallsetminus (B_i\cup B_j).$ For $x\in T_{ij}\smallsetminus (B_i\cup B_j)$, let $\pi_{ij}(x)$ denote the closest point on $L_{ij}$ to $x$. We begin by choosing a continuous "bump" function $f_{ij}\colon L_{ij}\to \mathbb{R}$ which $\geq 1$ everywhere, is $\equiv 1$ except in a small neighborhood of the midpoint of $L_{ij}$, and is $\equiv \Lambda_{ij}>1$ in a small neighborhood of the midpoint. Here $\Lambda_{ij}$ is a constant to be determined later, but we will always assume that $M\gg \Lambda_{ij}$ by adjusting $M$ if necessary. Define $W$ on $T_{ij}\smallsetminus B_i\cup B_j$ by $W(x) = M\frac{d(x,L_{ij})}{\varepsilon} + f_{ij}(\pi(x))\left(1 - \frac{d(x,L_{ij})}{\varepsilon}\right).$ Note that $W$ is radially symmetric in $T_{ij}\smallsetminus (B_i\cup B_j)$ around $L_{ij}$ and increasing with radius. It follows, in particular, that the line $L_{ij}$ is minimal geodesic for this $W$.

Step 3: It only remains to define $W$ in the balls $B_i$. Currently $W$ is defined and continuous on $\partial B_i$ for each $i$. We define $W$ in the $B_i$ by $B(x) = \frac{\|x - \alpha_i\|}{\delta}W\left(\alpha_{i} + \delta \frac{x - \alpha_i}{\|x - \alpha_i\|}\right).$ Note that the minimum value of $W$ in $\partial B_i$ is $1$, and this value is obtained exactly at the points $L_{ij}\cap \partial B_i$. It follows that the segments $L_{ij}\cap B_i$ are minimal geodesic segments for $W$ in $B_i$.

So now we have constructed $W$. It is continuous, it vanishes precisely at the $\alpha_i$, and we have show that the $L_{ij}$ are geodesics for $W$. Here's what this gives us:

Step 4: By adjusting the $\Lambda_{ij}$, we can make the length of $L_{ij}$ equal to $\sigma_{ij}$. We therefore get geodesic segments $L_{ij}$ from $\alpha_i$ to $\alpha_j$ of exactly the right length. Moreover, by making $M$ large enough, we can ensure that these geodesics are minimal: if $M$ is large enough, no minimal geodesic from $\alpha_i$ to $\alpha_j$ will pass through the region $\mathbb{R}^3\smallsetminus (\bigcup_k B_k\cup\bigcup_{k,l}T_{kl})$.

I think this construction, though a pain to write out, works for $\mathbb{R}^3$. In $\mathbb{R}^2$ it doesn't work since you cannot choose the $\alpha_i$ as in our assumption. In order to adapt this method to $\mathbb{R}^2$, something you can do would be to choose your $\alpha_i$, and consider the graph $\bigcup_{ij}L_{ij}$. Assign to each edge a weight such that $\alpha_i$ and $\alpha_j$ are at a distance $\sigma_{ij}$ apart with respect to these weights. You can then do the above procedure to construct a $W$ which makes each of the edges in the graph minimal geodesic with length equal to that weight.

I hope this all works. I'm curious to hear what people think.

  • 0
    Also, transforming the metric by homeomorphism does not result in existence of a $W'$ because angles will usually not be preserved: to prove you can indeed work with any $\alpha_i$, it's possible to pick an embedding of the complete graph on $n$ vertices with straight line segments in the middle and at either end and construct $W$ from there.2012-05-14