Existence of a Riemannian metric inducing a given distance.

Let $M$ be a smooth, finite-dimensional manifold. Suppose $M$ is also a metric space, with a given distance function $d: M \times M \rightarrow \mathbb{R}_{+}$, which is compatible with the original (manifold) topology on $M$.

Question: is there a Riemannian metric $g$ on $M$ such that the distance $$d_g(p, q) = \inf_{\gamma \in \Omega(p, q)} L_g(\gamma)$$ coincides with $d$?

I believe that this setting is very standard, but for the sake of completeness: $L_g$ denotes the Riemannian length of the curve $\gamma$, and $\Omega(p, q)$ the set of all piecewise smooth curves $\gamma : [a, b] \rightarrow M$ s.t. $\gamma(a) = p$ and $\gamma(b) = q$. Thanks in advance.

I believe the answer is no in general.

Consider the taxicab metric on $\mathbb{R}^2$. That is $d((x_1,y_1),(x_2,y_2)) = |x_1 - x_2| + |y_1+y_2|$. This metric induces the same topology on $\mathbb{R}^2$ as the standard metric.

The 2 points $(0,0)$ and $(a,a)$ with $a>0$ are a distance $2a$ from each other in this metric. The key point is that there are infinitely many shortest "geodesics" between these 2 points - any monotonic staircase picture is an example of one.

On the other hand, there is a well known consequence of the Gauss Lemma that, given a Riemannian metric, for a small enough neighborhood around any point there are unique shortest geodesics between any 2 points in the neighborhood.

But any neighborhood of $(0,0)$ contains at least one point of the form $(a,a)$, so the taxicab metric cannot be induced from a Riemannian metric.

This is an old post and Jason already gave a satisfactory (negative) answer to it, but some stubborn people do not take no for an answer! One of such people was A.D.Alexandov who asked (in 1940s or 1950s, I think) about synthetic geometric conditions on metric spaces $(M,d)$ which ensure that the distance function $d$ comes from a Riemannian metric (no a priori assumption that $M$ is homeomorphic to a manifold!). The first obvious necessary condition is that $M$ is locally compact (every topological manifold, of course, satisfies this property) and $d$ is a path-metric, i.e, $$ d(x,y)=\inf_{p} L(p) $$ where the infimum is taken over the length of all paths $p$ connecting $x$ to $y$. (The $l_1$-metric in Jason's answer does pass this test.) Every Riemannian metric has Riemannian metric tensor (which makes no sense for general path-metric spaces, of course) as well as the (sectional) curvature. The latter still has no meaning in the setting of arbitrary path-metric spaces. However, Alexandrov realized that for arbitrary path-metric spaces one can define the notions of upper and lower curvature bounds. Every Riemannian manifold, of course, does have curvature locally bounded above and below (the metric in Jason's answer fails this test). One needs to impose one more geometric condition on $(M,d)$: Every finite geodesic in $(M,d)$ has to extend in both directions (at least a little bit) to a longer geodesic. This eliminates, for instance, manifolds with boundary.

Alexandrov then asked if the curvature conditions plus extendibility of geodesics, plus some obvious topological restrictions (see below) is sufficient for the path-metric to be Riemannian. (In the 1930s A. Wald found a metric characterization of two-dimensional Riemannian manifolds.)

Remarkably, the answer to Alexandrov's question turned out to be positive:

[1] Suppose that $(M,d)$ is a locally compact finite dimensional path-metric space with curvature locally bounded above and below and extendible geodesics. Then $M$ is homeomorphic to a smooth manifold $M'$ and, under this homeomorphism, the distance function $d$ is isometric to the distance function coming from a Riemannian metric $g$ on $M'$, the regularity of the metric tensor $g$ is $C^{1,\alpha}$.

[2] Under further synthetic geometric "curvature-type" restrictions on $d$, the metric $g$ is $C^\infty$-smooth.

See:

[1] I. Nikolaev, Smoothness of the metric of spaces with bilaterally bounded curvature in the sense of A. D. Aleksandrov. Sibirsk. Mat. Zh. 24 (1983), no. 2, 114–132.

[2] I. Nikolaev, A metric characterization of Riemannian spaces. Siberian Adv. Math. 9 (1999), no. 4, 1–58.

Every compact metric space of covering dimension $n$ can be embedded isometrically in $\mathbb{R}^{2n+1}$, as far as I can tell. This is discussed in this MO post. In particular, a compact, metric manifold can be embedded in this way and then inherits a Riemannian metric from the ambient Euclidean space.