# Constructing a function over a metric space through given points

Suppose there is a compact metric space $(X,\rho)$ and a Euclidean space $\mathbb{R}^n$.

There is a sequence of unequal points $\{x_1,...x_N\}$ in $X$ such that all metrics $\rho(x_i,x_j)$ are known and $f(x_i)=a_i$ for some $a_i$ in $\mathbb{R}^n$ whereas:

$$\forall x_i,x_j \in \{x_1,...x_N\} . ||a_i-a_j|| \leq L \cdot \rho(x_i, x_j)$$

for a fixed $L$.

Suppose also that $\{x_1,...x_N\}$ form a finite cover of $X$ by balls of some suitable (known) radius.

If $X$ were just a compact interval, $\{x_1,...x_N\}$ its partition, and $n$ were $1$, we could certainly construct a piecewise-linear function $f:X \rightarrow \mathbb{R}^n$ such that:

$$f(x_i)=a_i \\ \forall x,y \in X . ||f(x)-f(y)|| \leq L \cdot \rho(x, y)$$

with a slope controlled by $L$.

It should be also possible in certain cases if $X \subset \mathbb{R}^m$.

Is it possible to construct such a function for a general compact metric space? And if $X$ is a subset of a Euclidean space?

Applying rescaling you can assume that $L=1$.

We look for a 1-Lipschitz piecewise linear maps $f\colon\mathbb{R}^m\to\mathbb{R}^n$.

If $m=n$ we get $f$ from Brehm's theorem; it says that there is a piecewise distance preserving map of that type (in particular 1-Lipschitz and piecewise linear). See Brehm, U., Extensions of distance reducing mappings to piecewise congruent mappings on $\mathbb{R}^m$ and also our paper written for kids.

If $m<n$ we can think that $\mathbb{R}^m$ is a subspace of $\mathbb{R}^n$; in this case apply Brehm's theorem and restrict the obtained map to $\mathbb{R}^m$.

If $m>n$ we can think that $\mathbb{R}^n$ is a subspace of $\mathbb{R}^m$; in this case apply Brehm's theorem and compose the obtained map with the projection to $\mathbb{R}^n$. Since projection linear and 1-Lipschitz, so it the composition.

• @ValerySaharov Rescale $X$ or $\mathbb R^n$:) – Anton Petrunin Oct 25 '15 at 18:19
• @ValerySaharov, After first line $L=1$ :) – Anton Petrunin Oct 25 '15 at 18:52
• @ValerySaharov We look for a 1-Lipschitz PL-maps $\mathbb{R}^m\to\mathbb{R}^n$. If $m=n$ we get it from Brehm's theorem. If $m<n$ we can think that $\mathbb{R}^m$ is a subspace of $\mathbb{R}^n$; in this case apply Brehm's theorem and restrict the obtained map to $\mathbb{R}^m$. If $m>n$ we can think that $\mathbb{R}^n$ is a subspace of $\mathbb{R}^m$; in this case apply Brehm's theorem and compose the obtained map with the projection to $\mathbb{R}^m$. – Anton Petrunin Oct 27 '15 at 11:06

Anton's answer is for the case where $X$ is a subset of a Hilbert space. For $X$ a general metric space (compactness does not help, BTW), $L$ must be increased by a factor of order $\log^{1/2}N$; see  Johnson, William B.; Lindenstrauss, Joram Extensions of Lipschitz mappings into a Hilbert space. Conference in modern analysis and probability (New Haven, Conn., 1982), 189–206, Contemp. Math., 26, Amer. Math. Soc., Providence, RI, 1984.

• You do not except PL map from general metric space, dont' you? – Anton Petrunin Oct 25 '15 at 21:20