# Graphical embedding

This post continues the theme of operating with functions using their graphs. Given an integrable function ${f}$ on the interval ${[0,1]}$, consider the region ${R_f}$ bounded by the graph ${y=f(x)}$, the axis ${y=0}$, and the vertical lines ${x=0}$, ${x=1}$.

The area of ${R_f}$ is exactly ${\int_0^1 |f(x)|\,dx}$, the ${L^1}$ norm of ${f}$. On the other hand, the area of a set is the integral of its characteristic function,

$\displaystyle \chi_f = \begin{cases}1, \quad x\in R_f, \\ 0,\quad x\notin R_f \end{cases}$

So, the correspondence ${f\mapsto \chi_f }$ is a map from the space of integrable functions on ${[0,1]}$, denoted ${L^1([0,1])}$, to the space of integrable functions on the plane, denoted ${L^1(\mathbb R^2)}$. The above shows that this correspondence is norm-preserving. It also preserves the metric, because integration of ${|\chi_f-\chi_g|}$ gives the area of the symmetric difference ${R_f\triangle R_g}$, which in turn is equal to ${\int_0^1 |f-g| }$. In symbols:

$\displaystyle \|\chi_f-\chi_g\|_{L^1} = \int |\chi_f-\chi_g| = \int |f-g| = \|f-g\|_{L^1}$

The map ${f\mapsto \chi_f}$ is nonlinear: for example ${2f}$ is not mapped to ${2 \chi_f}$ (the function that is equal to 2 on the same region) but rather to a function that is equal to 1 on a larger region.

So far, this nonlinear embedding did not really offer anything new: from one ${L^1}$ space we got into another. It is more interesting (and more difficult) to embed things into a Hilbert space such as ${L^2(\mathbb R^2)}$. But for the functions that take only the values ${0,1,-1}$, the ${L^2}$ norm is exactly the square root of the ${L^1}$ norm. Therefore,

$\displaystyle \|\chi_f-\chi_g\|_{L^2} = \sqrt{\int |\chi_f-\chi_g|^2} = \sqrt{\int |\chi_f-\chi_g|} = \sqrt{\|f-g\|_{L^1}}$

In other words, raising the ${L^1}$ metric to power ${1/2}$ creates a metric space that is isometric to a subset of a Hilbert space. The exponent ${1/2}$ is sharp: there is no such embedding for the metric ${d(f,g)=\|f-g\|_{L^1}^{\alpha} }$ with ${\alpha>1/2}$. The reason is that ${L^1}$, having the Manhattan metric, contains geodesic squares: 4-cycles where the distances between adjacent vertices are 1 and the diagonal distances are equal to 2. Having such long diagonals is inconsistent with the parallelogram law in Hilbert spaces. Taking the square root reduces the diagonals to ${\sqrt{2}}$, which is the length they would have in a Hilbert space.

This embedding, and much more, can be found in the ICM 2010 talk by Assaf Naor.