# Legendre transform and Lipschitz approximation

Let $(X,d)$ be a compact metric space and $f:X \to \mathbb{R}$ a real valued continuous function. Let us agree that a modulus of continuity means concave, nondecreasing, uniformly continuous function $\omega$ such that $\omega(0)=0$ and $|f(x)-f(y)| \leq \omega(d(x,y))$ for $x,y \in X$. Let $\delta(s)$ be a distance of $f$ from the set of all functions satisfying Lipschitz condition with a constant $s$. According to wikipedia, it can be shown, using Legendre transform, that if $\omega$ is a minimal concave modulus of continuity for $f$ then the following formulas holds: $$2\delta(s)=\sup_{t \geq 0}\{\omega(t)-st\},$$ and $$\omega(t)=\inf_{s \geq 0}\{2\delta(s)+st\}.$$ I would be grateful if anybody could give me reference, where I can find the proof of that fact.
PS. I need this result in order to justify some construction in the world of $C^*$-algebras-otherwise this construction would be somehow artificial.

These are somehow folk results. Here's a proof.

Let $(X,d)$ be a metric space, $f$ a function on $X$ which admits a concave modulus of continuity, and $g$ any $s$-Lipschitz function on $X$ with $\|f-g\|_\infty<\infty$. Then, for all $x$ and $y$ in $X$ $$|f(x)-f(y)|\le|f(x)-g(x)|+|g(x)-g(y)|+|g(y)-f(y)|\le$$ $$\le2\|f-g\|_\infty+sd(x,y)\,. \qquad(1)$$

The minimum concave modulus of continuity of $f$ is the inferior envelope of all increasing affine functions whose graphs are above the set of points $$\{(d(x,y),|f(x)-f(y)|)\in [0,\infty]\times[0,\infty] \;:\; x\in X,y\in X\}$$ that is, for any $t\ge0$
$$\omega(t)=\inf\{at+b\; :\;a\ge0,\,b\ge0,\forall x\;\forall y\; |f(x)-f(y)|\le a|x-y|+b \}\, .$$ So by (1) also $\omega(t)\le 2\|f-g\|_\infty +st$, and since this is true for all $s$ and $g$ $s$-Lipschitz, $$\omega(t)\le\inf_{s\ge0} \{ 2\delta(s) +st\}\,.\qquad(2)$$

Keeping $f,g,s$ as above, it is straightforward to check that the inferior envelope $$f^*_s(x):=\inf_{y\in X}\{f(y)+sd(x,y)\}$$ is the largest $s$-Lipschitz function below $f$ (note that the infimum is finite because it is larger than $g-\|f-g\|_\infty$, which is itself an $s$-Lipschitz function below $f$). This implies that the minimal distance $\delta(s)$ is realized by the $s$-Lipschitz function $f^*_s+\delta(s)$ and that $$2\delta(s)=\|f-f^*_s\|_\infty= \sup_{x,y\in X}\{f(x)-f(y)-sd(x,y)\}\,.$$ Since $f(x)-f(y)\le\omega(d(x,y))$, we also have $$2\delta(s)\le\sup_{t\ge0}\{\omega(t)-st\}\,.\qquad(3)$$

One may analogously prove that (2) and (3) are indeed equalities, by similar arguments, but note that, introducing the convex function $\alpha(t):=-\omega(-t)$ for $t\le0$ and $+\infty$ for $t>0$, and also putting $\delta(t)=+\infty$ for $t<0$, the stated inequalities (2) and (3) reads, in terms of Legendre transforms $$\alpha\ge (2\delta)^*,\qquad 2\delta\le \alpha^*.$$ Since the Legendre transform reverses the inequalities and is involutory we conclude that these inequalities are indeed equalities, that is, $\alpha$ and $2\delta$ are a pair of convex conjugate functions.

• Many thanks for your proof: however I'm also interested in knowing the reference for the fact that Legendre transform is involutory. I would be very grateful for giving me such reference Feb 4 '15 at 16:19
• It's Fenchel–Moreau theorem, which you can find in any textbook on convex analysis. Feb 4 '15 at 18:00
• (here it's the just the one variable case) Feb 4 '15 at 18:04