Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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<j \leq n} a_{ij}x_i^2x_i^2 $$ 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.

share|cite|improve this question
If $W$ is a positive function, then it doesn't have any zeroes. – Andy Barfoot May 8 '12 at 12:01
What's the significance of the number of $\alpha_n$ being equal to the dimension of the manifold, $\mathbb{R}^n$? – Andy Barfoot May 8 '12 at 12:05
@AndyBarfoot: The meaning of 'positive' is non-negative. It is no correlation between the number of zeros and the dimension of the space. In fact, in my problem they are independent. – Beni Bogosel May 10 '12 at 0:02
What Andy meant is that while in French, 'positive' almost always means $\ge 0$, in English 'positive' always means $>0$. You should fix the question. – Generic Human May 14 '12 at 10:50
@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. – Beni Bogosel May 14 '12 at 14:30
up vote 1 down vote accepted

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.

share|cite|improve this answer
I'm not entirely convinced by your construction, but I will give you the bounty, since you are the only one who answered. – Beni Bogosel May 12 '12 at 20:30
Judging by the lack of commentary/votes, it seems you aren't the only one who isn't convinced. Thanks! – froggie May 12 '12 at 20:34
The general idea is correct, but only if the triangle inequalities are strict; otherwise it's possible to take a shortcut in $B_j$ when moving from $L_{ij}\setminus B_j$ to $L_{jk}\setminus B_j$, and that path will become shorter than $L_{ik}$. You need to look at all paths before you can draw a conclusion. If triangle inequalities are strict then, for small enough $\delta$, only direct paths are optimal. – Generic Human May 14 '12 at 10:55
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. – Generic Human May 14 '12 at 10:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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