MacManus' Easy Bi-Lipschitz Extension Theorem

2021-01-24
7 min read

In Week 5 of my Geometric Measure Theory course, we’ll be studying Lipschitz functions and various useful techniques for working with them. In this note I’m going to discuss one of my favorite results from this week and show how I illustrated it using Numpy and Matplotlib. Neither the theorem nor the code are difficult, but I’ve always wanted to visualize this theorem, and coding it is a nice exercise.

Recall a function $ f:A\subseteq X\rightarrow Y$ (where $ X$ and $ Y$ are two metric spaces) is $ L$-Lipschitz if $ { |f(x)-f(y)|\leq L|x-y|}$ for all $ x,y\in A$ and is $ L$-bi-Lipschitz if its inverse $ f^{-1}:f(A)\rightarrow X$ is also $ L$-Lipschitz.

One should think of these functions as weaker versions of differentiable functions. For example, $ f(x)=|x|$ is Lipschitz but not differentiable. They can be thought of as differentiable in a measure theoretic sense, since a theorem of Rademacher says that the set of points where such a function is not differentiable is of measure zero.

One useful set of tools we discuss is how to extend Lipschitz functions, meaning to find a function $ F:X\rightarrow Y$ that is also Lipschitz (ideally with not too much larger Lipschitz constant) so that $ F=f$ on the set $ A$. There are many results dealing with when you can extend such functions and at what sacrifice to the Lipschitz constant (since large Lipschitz constant corresponds to possibly more erratic behavior in your function). In this post, I won’t go too deep in the theory, but there’s one bi-Lipschitz extension I like because it is dead simple, though nontrivial in the sense that its proof is a paragraph, but if aliens abducted me and said I had to come up with this result on my own or the world would explode and they would give me as long as I wanted, I’d probably just push the detonate button myself.

It comes from a paper by MacManus Bi-Lipschitz Extensions in the Plane where he generalizes a result of Tukia (The Planar Schönflies Theorem for Lipschitz maps) by showing that any $ L$-bi-Lipschitz map $ f:A\subseteq \mathbb{S}\rightarrow \mathbb{R}^{2}$ can be extended to a bi-Lipschitz homeomorphism $ F:\mathbb{R}^{2}\rightarrow \mathbb{R}^{2}$.

This is a cool result and quite technical, but along the way he shows that when $ A$ is a subset of the real line (instead of a circle) mapping to another subset of the line, then the result is easy, and in fact generalizes to higher dimensions.

Theorem: Let $ f:A\subseteq \mathbb{R}^{n}\rightarrow \mathbb{R}^{n}$ be $ L$-bi-Lipschitz. Then there is a $ CL^{2}$-bi-Lipschitz extension $ F:\mathbb{R}^{2n}\rightarrow \mathbb{R}^{2n}$.

The proof is rather quick: Kirzbraun’s Extension Theorem says $ f:A\rightarrow \mathbb{R}^{n}$ has $ L$-Lipschitz extension $ f_{1}:\mathbb{R}^{n}\rightarrow \mathbb{R}^{n}$, and $ f^{-1}:f(A)\rightarrow \mathbb{R}^{n}$ has an $ L$-Lipschitz extension $ f_{2}:\mathbb{R}^{n}\rightarrow \mathbb{R}^{n}$. Let $ F_{1}(x,y)= (y+f_{1}(x),x)$ and $ F_{2}(x,y)=(x,y+f_{2}(x))$. Then it’s not hard to check $ F_{2}^{-1}\circ F_{1}$ is our desired extension.

Why do we need to go up in dimension? Consider the simple bi-Lipschitz map that takes the numbers 1,2, and 3 to 1, 3 and 2 respectively. This is a 2-bi-Lipschitz map from a subset of $ \mathbb{R}$ into $ \mathbb{R}$, but it cannot extend even to an injective continuous map from $ \mathbb{R}$ into itself, let alone a bi-Lipschitz map, simply because if you take a pen and connect the dots according to the above instructions (moving the pen from 1 to 3 and then to 2), you will cross 2 twice.

Now there are results that are better than this. A theorem of David and Semmes from their monograph Singular Integrals and Rectifiable sets in $ \mathbb{R}^{n}$ says that a bi-Lipschitz map from a compact subset of $ \mathbb{R}^{d}$ into $ \mathbb{R}^n$ extends to a bi-Lipschitz map from $ \mathbb{R}^{d}$ into $ \mathbb{R}^m$ where $ m = \max{n,2d+1}$. In other words, if the dimension of your target space is large enough (at least $ 2d+1$), there is enough room for you to find a bi-Lipschitz extension. However, MacManus' lemma gives better results in the case that $ n=d=1$, and is quick and reliable if, say, you are teaching a class and want to give a tangible example of such a theorem.

What I always wanted to see was how this extension actually looks like. In the earlier example of the 3 points, the extension is from $ \mathbb{R}^{2}$ to $ \mathbb{R}^2$, and so you should be able to visualize it. Moreover, for more complicated arrangements of points, the resulting map should send the real line to a curve in $ \mathbb{R}^{d}$ that passes between the points in order but, because it is bi-Lipschitz, it should wrap around itself in a small amount of space. I’ve tried drawing this in lecture before, but I thought this time I’d write a program to simulate this.

#The following class takes a 
#function defined on a finite
#set of points and gives a call function
#that will equal the piecewise linear
#interpolation of f. 

class interpolate:
        #We initiate the class with two
        #vectors x and f, where 
        #f is our function evaluated 
        #along the points x.
	def __init__(self,x,f):
    
            self.x=x
    
            self.f=f
    
	def __call__(self,y):
    
            j=0
    
            y = np.array(y)
    
            f=self.f
    
            x=self.x
    
    #This is where we will stash the values
    #of our interpolation evaluated at the 
    #points y.
    F = np.zeros(len(y))
    
    for i in range(len(self.x)-1):
        #For each consecutive pair of points
        #x_1 and x_2 in x, we compuite the slope of the
        #line passing from (x_1,f(x_1)) to (x_2,f(x_2))
        #and then define a function for that secant line.
        
        m = (f[i+1]-f[i])/(x[i+1]-x[i])
        
        line = lambda t: m*(t-x[i]) + f[i]
        
        #We then define F on the points in y
        #that lie between these two points to
        #equal to this line.
        
        indices = ((y>=x[i]) & (y<=x[i+1]))
        F[indices] = line(y[indices])
        
    #For the values of y that came before 
    #the first element in x or afte the
    #last, we just set F equal to the 
    #first and last values of f
    #respectively.
    
    F[y<=x[0]] = f[0]
    
    F[y>=x[-1]] = f[-1]
    
    return F


#This defines the MacManus extension
#operator.

class Macmanus:
        def __init__(self,x,f):
                #The initial arguments are numbers x
                #and their values f under the function
                #we want to extend. We first convert
             #them to numpy arrays
    
             x = np.array(x)
    
                f=np.array(f)
    
                self.m=len(x)
    
                assert (self.m,)==x.shape, "x must be 1 dimensional"

                #Next, we define the extension classes
                #for f and its inverse,, which we call
                #f_1 and f_2 respectively. 
    
                self.f_1 = interpolate(x,f)
    
            #Note that the interpolation
             #class assumes that the x variable
                #is ordered from smallest to largest,
            #so we can't just pass the pair
            #(f,x) as the initial input, we
                #need to reorder the numbers so that
                #f is now increasing.
    
                i = np.argsort(f)
    
                self.f_2 = interpolate(f[i],x[i])

        def __call__(self,x):
    
            #This will evaluate the MacManus
            #extension at an array of points x.
            #If x is a list, we convert it to
            #a numpy array.
    
                x = np.array(x)
    
                #If m is the number of values 
                #in x, the following is a 
                #mx2 array where we will store
                #the m values of the MacManus 
                #extension (now 2-d vectors),
                #the columns being the x and 
                #y coordinates respectively.
    
                ext = np.zeros((len(x),2))
    
            #We now define these coordinates
         #as per the definition of the
         #MacManus extension
    
                f_1 = self.f_1(x)
    
                ext[:,0] = f_1
    
            ext[:,1] = x-self.f_2(f_1)


        
             return ext
            
    
#Now let's try an example.
#Below are some numbers x
#and the values of a Lipschitz
#function f evaluated at these 
#points. We'll plot what the 
#image of the real line looks
#like under the extension


x= np.array([0,1,2,3,4,5])

f = [5,1,3,2,4,0]

F = Macmanus(x,f)

y=np.linspace(-1,5,200)

Z=F(y)

fig, ax = plt.subplots(1,2)

for a in ax:
        a.set_xlim([-1,6])
        a.set_ylim([-4,4])
        a.set_aspect("equal")
        a.axis("off")


ax[0].scatter(np.arange(0,6), np.zeros(6), color="red")
ax[0].plot([-1,6],[0,0], color=u'#1f77b4')
[ax[0].text(i-.15,.3,i) for i in range(0,6)]
ax[0].axis("off")



ax[1].plot(Z[:,0], Z[:,1])
ax[1].scatter(f,np.zeros(len(f)), color="red")

for i in x:
        _=ax[1].text(f[i]-.1,.3,i)

The test case we apply it to is a function defined on the integers 0 to 5 s.t. $ f(0)=5, f(1)=1, f(2) = 4, f(3) = 2, f(4) = 4, f(5)=0$, clearly not extendable in the real line. But then we apply the function above and voilà, its extension into $ \mathbb{R}^{2}$!