ALEXANDROV’S THEOREM ON THE SECOND DERIVATIVES OF CONVEX FUNCTIONS VIA RADEMACHER’S THEOREM ON THE FIRST DERIVATIVES OF LIPSCHITZ FUNCTIONS

RALPH HOWARD DEPARTMENT OF MATHEMATICS UNIVERSITY OF SOUTH CAROLINA COLUMBIA, S.C. 29208, USA

                           HOWARD@MATH.SC.EDU

These are notes from lectures given the the functional analysis seminar at the University of South Carolina.

Contents

1. Introduction 1 2. Rademacher’s Theorem 2 3. A General Sard Type Theorem for Maps Between Spaces of the

Same Dimension 6 3.1. A more general result. 11 4. An Inverse Function Theorem for Continuous Functions Differentiable

at a Single Point 14 5. Derivatives of Set-Valued Functions and Inverses of Lipschitz

Functions 16 6. Alexandrov’s Theorem 18 7. Symmetry of the Second Derivatives 21 References 22

1. Introduction

A basic result in the regularity theory of convex sets and functions is the theorem of Alexandrov that a convex function has second derivatives almost everywhere. The notes here are a proof of this following the ideas in the appendix of the article [4] of Crandall, Ishii, and Lions and they attribute the main idea of the proof to F. Mignot [5]. To make the notes more self contained I have included a proof of Rademacher’s theorem on the differentiable almost everywhere of Lipschitz functions following the presentation in the book [8] of Ziemer (which I warmly recommend to anyone wanting to learn about the pointwise behavior of functions in Sobolev spaces or of bounded variation). Actually a slight generalization of Alexandrov’s theorem is given in Theorem 5.3 which shows that set-valued functions that are inverses to Lipschitz functions are differentiable almost everywhere.

Date: May 1998.

To simplify notation I have assumed that functions have domains all of R^{n}. It is straightforward to adapt these proofs to locally Lipschitz functions or convex function defined on convex open subsets of R^{n}.

As to notation. If x, y ∈ R^{n} then the inner product is denoted as usual by either x · y or ⟨x, y⟩. Explicitly if x = (x_{1}, …, x_{n}) and y = (y_{1}, …, y_{n})

x · y = ⟨x, y⟩ = x_{1}y_{1} + ⋯ + x_{n}y_{n}.

The norm of x is ∥x∥ = \sqrt{x · x}. Lebesgue measure in R^{n} will be denoted by L^{n} and integrals with respect to this measure will be written as ∫_{R^{n}} f(x) dx. If x_{0} ∈ R^{n} and r > 0 then the open and closed balls about x_{0} will be denoted by

B(x_{0}, r) := \{x ∈ R^{n} : ∥x − x_{0}∥ < r\} \overline{B}(x_{0}, r)\{x ∈ R^{n} : ∥x − x_{0}∥ ≤ r\}.

2. Rademacher’s Theorem

We first review a little about Lipschitz functions in one variable. The following is a special case of a theorem of Lebesgue.

2.1. Theorem. Let f: R → R satisfy |f(x_{1}) − f(x_{0})| ≤ M|x_{1} − x_{0}|. Then the derivative f′(t) exists for almost all t and

|f′(t)| ≤ M

holds at all points where it does exist. Also for a < b

∫_{a}^{b} f′(t) dt = f(b) − f(a).

Note if f: R → R is Lipschitz and φ ∈ C_{0}^{∞}(R) then the product φ(t)f(t) is also Lipschitz and so the last result implies

∫_{R} f′(t)φ(t) dt = − ∫_{R} f(t)φ′(t) dt.

Now if f: R^{n} → R then denote by D_{i}f the partial derivative

D_{i}f(x) = \frac{∂f}{∂x_{i}} (x)

at points where this partial derivative exists. Let Df(x) denote

Df(x) = (D_{1}f(x), …, D_{n}f(x)).

2.2. Proposition. If f: R^{n} → R is Lipschitz, say ∥f(x_{1}) − f(x_{0})∥ ≤ M∥x_{1} − x_{0}∥, then Df(x) exists for almost all x ∈ R^{n}. Moreover all the partial derivative D_{i}f satisfy

|D_{i}f(x)| ≤ M

at points where they exist. Thus

∥Df(x)∥ ≤ \sqrt{n}M. (2.1)

Finally if φ ∈ C_{0}^{∞}(R^{n}) then

∫_{R^{n}} D_{i}f(x)φ(x) dx = − ∫_{R^{n}} f(x)D_{i}φ(x) dx. (2.2)

Proof. We show that D_{1}f(x) exists almost everywhere, the argument for D_{i}f being identical. Write x = (x_{1}, x_{2}, …, x_{n}) as x = (x_{1}, x′) where x′ = (x_{2}, …, x_{n}). Then for any x′ ∈ R^{n−1} let

N_{x′} := {x_{1} ∈ R : D_{1}f(x_{1}, x′) does not exist.}.

Then by the one variable result N_{x′} is a set of measure zero in R for all x′ ∈ R^{n−1}. Therefore by Fubini’s the set

N = ⋃_{x′∈R^{n−1}} N_{x′} = {x ∈ R^{n} : D_{1}f(x) does not exist}

is a set of measure zero. That |D_{i}f(x)| ≤ M at points where it exists is clear (or follows from the one dimensional result). At points where Df(x) exists

∥Df(x)∥ = \sqrt{D_{1}f(x)^{2} + ⋯ + D_{n}f(x)^{2}} ≤ \sqrt{M^{2} + ⋯ + M^{2}} = \sqrt{n}M.

Finally we show (2.2) in the case of i = 1. Using the notation above, Fubini’s theorem, and the one variable integration by parts formula.

∫_{R^{n}} D_{1}f(x)φ(x) dx = ∫_{R^{n−1}} ∫_{R} D_{1}f(x_{1}, x′)φ(x_{1}, x′) dx_{1} dx′
= − ∫_{R^{n−1}} ∫_{R} f(x_{1}, x′)D_{1}φ(x_{1}, x′) dx_{1} dx′
= − ∫_{R^{n}} f(x)D_{1}φ(x) dx

This completes the proof.

2.3. Definition. Let f: R^{n} → R, then for a fixed vector v ∈ R^{n} define

df(x, v) := lim_{t→0} \frac{f(x + tv) − f(x)}{t}.

When this limit exists it is directional derivative of f in the direction of v at the point x.

2.4. Proposition. Let f: R^{n} → R be Lipschitz and let v ∈ R^{n} be a fixed vector. Then df(x, v) exists for almost all x ∈ R^{n} and is given by the formula

df(x, v) = Df(x) · v (2.3)

for almost all x.

Proof. Note if v = e_{1} where e_{1}, …, e_{n} is the standard coordinate basis of R^{n} then df(x, v) = df(x, e_{1}) = D_{1}f(x) and the fact that df(x, v) exists almost everywhere follows from Proposition 2.2. In the general case if v ≠ 0 (and the case v = 0 is trivial) there is a linear coordinate system ξ_{1}, …, ξ_{n} on R^{n} so that df(x, v) = \frac{∂f}{∂ξ_{1}} . But again Proposition 2.2 can be used to see that df(x, v) exits for almost all x ∈ R^{n}.

To see that the formula (2.3) holds let φ ∈ C_{0}^{∞}(R^{n}). Then as φ is smooth the usual form of the chain rule implies dφ(x, v) = Dφ(x) · v. Let M be the Lipschitz constant of f. Then

|\frac{f(x + tv) − f(x)}{t}φ(x)| ≤ \frac{M∥tv∥}{|t|}|φ(x)| ≤ M∥v∥∥φ∥_{L^{∞}}.

Therefore for 0 < |t| ≤ 1 the function x ↦ |\frac{f(x+tv)−f(x)}{t}φ(x)| is uniformly bounded and has compact support. Thus by the dominated convergence theorem and the version of integration by parts given in Proposition 2.2

∫_{R^{n}} df(x, v)φ(x) dx = lim_{t→0} ∫_{R^{n}} \frac{f(x + tv) − f(x)}{t}φ(x) dx

= lim_{t→0} \frac{1}{t} (∫_{R^{n}} f(x + tv)φ(x) dx − ∫_{R^{n}} f(x)φ(x) dx)

= lim_{t→0} \frac{1}{t} (∫_{R^{n}} f(x)φ(x − tv) dx − ∫_{R^{n}} f(x)φ(x) dx)

= lim_{t→0} ∫_{R^{n}} f(x)\frac{φ(x − tv) − φ(x)}{t} dx

= ∫_{R^{n}} f(x)dφ(x, −v) dx

= − ∫_{R^{n}} f(x)Dφ(x) · v dx

= − ∑_{i=1}^{n} v_{i} ∫_{R^{n}} f(x)D_{i}φ(x) dx

= ∑_{i=1}^{n} v_{i} ∫_{R^{n}} D_{i}f(x)φ(x) dx

= ∫_{R^{n}} Df(x) · vφ(x) dx.

Thus ∫_{R^{n}} df(x, v)φ(x) dx = ∫_{R^{n}} Df(x) · vφ(x) dx for all φ ∈ C^{∞}(R^{n}). Therefore d(x, v) = Df(x) · v for almost all x ∈ R^{n}.

2.5. Definition. Let f: R^{n} → R^{m}. Then f is differentiable at x_{0} ∈ R^{n} iff there is a linear map L: R^{n} → R^{m} so that

f(x) − f(x_{0}) = L(x − x_{0}) + o(∥x − x_{0}∥).

In this case the linear map L is easily seen to be unique and will be denoted by f′(x_{0}).

By o(∥x − x_{0}∥) we mean a function of the form ∥x − x_{0}∥g(x, x_{0}) where lim_{x→x_{0}} g(x, x_{0}) = 0. This definition could be given a little more formally by letting S^{n−1} = {u ∈ R^{n} : ∥u∥} be the unit sphere in R^{n}. Then f: R^{n} → R^{m} is differentiable at x with f′(x) = L iff for all ε > 0 there is a δ > 0 so that for all u ∈ S^{n−1}

0 < |t| ≤ δ implies ∥\frac{f(x_{0} + tu) − f(x_{0})}{t} − Lu∥ < ε. (2.4)

2.6. Theorem (Rademacher [6] 1919). If f: R^{n} → R^{m} is Lipschitz, say ∥f(x_{1}) − f(x_{0})∥ ≤ M∥x_{1} − x_{0}∥, then the derivative f′(x) exists for almost all x ∈ R^{n}. In the case m = 1, so that f: R^{n} → R, then f′(x) is given by

f′(x)v = Df(x) · v

for almost all x ∈ R^{n}.

Proof. We first consider the case when m = 1 so that f is scalar valued. Let E_{0} be the set of points x ∈ R^{n} so that Df(x) exists. By Proposition 2.2 the set E_{0} has full measure (that is L^{n}(R^{n} \ E_{0}) = 0). Let R^{#} = R \ {0} and define Q: E_{0} × S^{n−1} × R^{#} → [0, ∞) to be

Q(x, u, t) := |\frac{f(x + tu) − f(x)}{t} − Df(x) · u| .

Then, in light of the form of the definition of differentiable given by 2.4, we wish to show that Q(x, u, t) can be made small by making t small.

First note if u, u′ ∈ S^{n−1} then, using the Lipschitz condition of f and the bound (2.1) on ∥Df(x)∥ we have

|Q(x, u, t) − Q(x, u′, t)| ≤ |\frac{f(x + tu) − f(x + tu′)}{t}| + |Df(x) · (u − u′)|

≤ \frac{M|t|∥u − u′∥}{|t|} + ∥Df(x)∥∥u − u′∥

≤ M(1 + \sqrt{n})∥u − u′∥. (2.5)

Now choose a sequence {u_{k}}_{k=1}^{∞} that is dense in S^{n−1}. For each k = 1, 2, … set

E_{k} = {x ∈ E_{0} : df(x, u_{k}) exists and df(x, u_{k}) = Df(x) · u_{k}}.

Then by Proposition 2.4 each set E_{k} has full measure and thus the same is true of

E := ⋂_{k=1}^{∞} E_{k}.

Fix a point x ∈ E. Let ε > 0. Then there is a K so that {u_{k}}_{k=1}^{K} is ε/(2M(1 + \sqrt{n}) dense in S^{n−1}. That is for all u ∈ S^{n−1} there is a k ≤ K so that

M(1 + \sqrt{n})∥u − u_{k}∥ < \frac{ε}{2}. (2.6)

As each directional derivative df(x, u_{k}) exists there is a δ > 0 so that if 1 ≤ k ≤ K then

0 < |t| ≤ δ implies Q(x, u_{k}, t) < \frac{ε}{2}.

Then for any u ∈ S^{n−1} there is a u_{k} with k ≤ K so that (2.6) holds. Therefore 0 < |t| ≤ δ implies

Q(x, u, t) ≤ Q(x, u_{k}, t) + |Q(x, u, t) − Q(x, u_{k}, t)|

< \frac{ε}{2} + M(1 + \sqrt{n})∥u − u_{k}∥

< \frac{ε}{2} + \frac{ε}{2} = ε.

This shows that f is differentiable at x with f′(x)v = Df(x) · v. As x was any point of E and E has full measure this completes the proof in the case m = 1.

For m ≥ 2 write f as

f(x_{1}, …, x_{n}) = f(x) = [ f_{1}(x) ; f_{2}(x) ; ⋮ ; f_{m}(x)]

Let F_{i} = {x : f′_{i}(x) exists and f′_{i}(x)v = Df_{i}(x)·v}. Then we have just shown that F_{i} has full measure and thus the same is true of F := E_{1} ∩ ⋯ ∩ F_{m}. For x ∈ F let L_{x}: R^{n} → R^{m} be the linear map given by the matrix

L_{x} := [\begin{matrix}D_{1}f_{1}(x) & D_{2}f_{1}(x) & ⋯ & D_{n}f_{1}(x) \\ D_{1}f_{2}(x) & D_{2}f_{2}(x) & ⋯ & D_{n}f_{2}(x) \\ ⋮ & ⋮ & ... & ⋮ \\ D_{1}f_{m}(x) & D_{2}f_{m}(x) & ⋯ & D_{n}f_{m}(x) \end{matrix}] .

Then using that the derivatives f′_{i}(x) for all x ∈ F it is not hard to show that f′(x) exists for all x ∈ F and that for these x the derivative is given by f′(x) = L_{x}. This competes the proof.

3. A General Sard Type Theorem for Maps Between Spaces of the Same Dimension

Let G: R^{n} → R^{n}. Then define the set of critical points of G as

Crit(G) := {x : G′(x) does not exist or G′(x) exists but det G′(x) = 0}.

The set of regular points of G is R^{n} \Crit(G). Thus x is a regular value iff G′(x) exists and is a linear automorphism of R^{n}. The set of critical values of G is G[Crit(G)] and the set of regular values is R^{n} \ G[Crit(G)]. Thus y is a regular value iff when ever there is an x ∈ R^{n} with G′(x) = y then G′(x) exists and is nonsingular. (Note that if y is not in the image of G then will be regular value of G. Thus non-values of G are regular values.)

3.1. Theorem. Let G: R^{n} → R^{n} be Lipschitz. Then the set G[Crit(G)] of critical values of G has measure zero (that is L^{n}G[Crit(G)] = 0). (Or what is the same thing almost very point y ∈ R^{n} is a regular value of G.)

This will be based on some more general results. We will denote the Lebesgue outer measure on R^{n} by L^{n}. (That is we use the same notation for the outer measure and the measure. As these agree on the set of measurable functions this should not lead to any confusion.)

3.2. Proposition. Let f: R^{n} → R^{n} be an arbitrary map (it need not be continuous or even measurable) and assume that there is a set A (which need not be measurable) so that at every point a ∈ A the derivative f′(a) exists and satisfies | det f′(a)| ≤ M for some constant M. Then the outer measure of f[A] satisfies L^{n}(f[A]) ≤ ML^{n}(A). In particular if A has measure zero then so does f[A].

The proof will be based on a weaker version of the result (which is really all that is needed to prove Theorem 3.1).

3.3. Lemma. There is a constant C(n) only depending on the dimension so the if f: R^{n} → R^{n} is an arbitrary map (it need not be continuous or even measurable) and A is a set (which need not be measurable) so that at every point a ∈ A the derivative f′(a) exists and satisfies | det f′(a)| ≤ M for some constant M. Then the outer measure of f[A] satisfies L^{n}(f[A]) ≤ C(n)ML^{n}(A).

Proof. Let a ∈ A and let α(x) := f(a) + f′(a)(x − a) be the affine approximation to f at a. Then if B(a, r) is the ball of radius r centered at a then from the change of variable formula from calculus we have L^{n}(α[B]) = | det f′(a)|L^{n}(B(a, r)).

3.4. Claim. If a ∈ A and ε > 0 then there is an an r_{0} = r_{0}(x_{0}, ε) so that if r ≤ r_{0}(x_{0}, ε) then

L^{n}(f[B(a, r)]) ≤ (M + ε)L^{n}(B(a, r)) (3.1)

(The proof will show this also holds for closed balls \overline{B}(a, r) with r ≤ r_{0}.)

Proof of the claim. As f is differentiable at a there is a monotone decreasing function ω: [0, ∞) → [0, ∞) with lim_{t↘0} ω(t) = 0 so that

∥f(x) − f(a) − f′(a)(x − a)∥ ≤ ω(∥x − a∥)∥x − a∥.

(To be explicit we can take ω(t) = sup{∥f(x) − f(a) − a′(a)(x − a)∥/∥x − a∥ : 0 < ∥x − a∥ ≤ t}.) Let α(x): R^{n} → R^{n} be the affine map α(x) = f(a) + f′(a)(x − a). Then ∥f(x) − α(x)∥ ≤ ω(∥x − a∥)∥x − a∥. As above L^{n}(α[B(a, r)]) = | det f′(a)|L^{n}(B(x, r)). But if ∥x − a∥ ≤ r then

∥x − a∥ ≤ r implies ∥f(x) − α(x)∥ ≤ ω(r)r. (3.2)

Let \overline{B}^{n} be the unit ball in R^{n}. Then for ρ > 0 the set ρ\overline{B}^{n} = \{ρx : x ∈ \overline{B}^{n}\} is the closed ball of radius ρ and for any set C ⊂ R^{n} the set C + ρ\overline{B}^{n} = \{c + ρx : c ∈ C, x ∈ \overline{B}^{n}\} is the tube of radius ρ about C (that is the set of points at a distance ≤ ρ from C). But then (3.2) implies

f[B(a, r)] ⊆ α[B(a, r)] + ω(r)r\overline{B}^{n}.

Thus

L^{n}(f[B(a, r)]) ≤ L^{n}(α[B(a, r)] + ω(r)r\overline{B}^{n})
= L^{n}(α[B(a, 1)] + ω(r)\overline{B}^{n})r^{n}

But lim_{t↘0} ω(t) = 0 implies

lim_{r↘0} L^{n}(α[B(a, 1)] + ω(r)\overline{B}^{n}) = L^{n}(α[B(a, 1)]
= | det f′(a)|L^{n}(B(a, 1))
≤ ML^{n}(B(a, 1))

Thus there is an r_{0} so that L^{n}(α[B(a, 1)] + ω(r_{0})\overline{B}^{n}) ≤ (M + ε)L^{n}(B(a, 1)). Then for r ≤ r_{0} our bounds imply

L^{n}(f[B(a, r)]) ≤ L^{n}(α[B(a, 1)] + ω(r)\overline{B}^{n})r^{n}
≤ (M + ε)L^{n}(B(a, 1))r^{n} = (M + ε)L^{n}(B(a, r))

which shows (3.1) holds and completes the proof of the claim.

Before returning to the proof of Theorem 3.6 we need a covering theorem from analysis. This is the Besicovitch covering theorem which in many ways is more useful than the Vitali covering theorem. There are many equivalent statements of the theorem and at first glance the following many not look like the form given in some texts. For a proof see [8, Thm 1.3.5 p. 9].

3.5. Theorem (Besicovitch [2, 1945]). There is a number N = N(n) so that if A ⊆ R^{n} and r: A → (0, ∞) with sup_{a∈A} r(a) < ∞ then there is a subset {a_{k}}_{k=1}^{∞} ⊆ A so that

A ⊂ ⋃_{k=1}^{∞} \overline{B}(a_{k}, r(a_{k}))

and for all x ∈ R^{n}

#\{k : x ∈ \overline{B}(a_{k}, r(a_{k}))\} ≤ N(n).

(That is any point of R^{n} is in at most N(n) of the balls \overline{B}(a_{k}, r(a_{k})).)

We now return to the proof of Lemma 3.3. If L^{n}(A) = ∞ there is nothing to prove. Thus assume L^{n}(A) < ∞. Then there is an open set U so that A ⊂ U and L^{n}(U) ≤ 2L^{n}(A). Fix ε > 0. For each x ∈ A we can use the claim to find an r(x) > 0 so that the closed ball \overline{B}(x, r(x)) ⊂ U and

L^{n}f[\overline{B}(x, r(x))] ≤ (M + ε)L^{n}B(x, r(x)).

As \overline{B}(x, r(x)) ⊂ U and L^{n}(U) ≤ 2L^{n}(A) < ∞ we have sup_{x∈A} r(x) < ∞. Therefore by the Besicovitch theorem there is a subset {x_{k}}_{k=1}^{∞} ⊂ A so that if r_{k} := r(x_{k}) then

A ⊆ ⋃_{k=1}^{∞} \overline{B}(x_{k}, r_{k})

and each x ∈ R^{n} is in at most N(n) of the balls B(x_{k}, r_{k}). This last fact, along with the fact that each \overline{B}(x_{k}, r_{k}) ⊂ U, implies ∑_{k=1}^{∞} χ_{\overline{B}(x_{k},r_{k})}(x) ≤ N(n)χ_{U}(x) (where χ_{S} is the characteristic function of the set S). Therefore

∑_{k=1}^{∞} L^{n}(\overline{B}(x_{k}, r_{k})) = ∫_{R^{n}} ∑_{k=1}^{∞} χ_{\overline{B}(x_{k},r_{k})}(x) dx

≤ ∫_{R^{n}} N(n)χ_{U}(x) dx
= N(n)L^{n}(U)
≤ 2N(n)L^{n}(A).

We now estimate L^{n}(f[A]).

L^{n}(f[A]) ≤ L^{n}(f[ ⋃_{k=1}^{∞} B(x_{k}, r_{k})])

≤ ∑_{k=1}^{∞} L^{n}(f[B(x_{k}, r_{k})])

≤ (M + ε) ∑_{k=1}^{∞} L^{n}(B(x_{k}, r_{k}))

≤ 2N(n)(M + ε)L^{n}(A)

As ε was arbitrary this implies L^{n}(f[A]) ≤ C(n)L^{n}(A) where C(n) = 2N(n). This completes the proof.

3.6. Proposition. Let f: R^{n} → R^{n} be a map (which is not assumed to be continuous or even measurable) and let

C := {x ∈ R^{n} : f′(x) exists, but det f′(x) = 0}

be the set of points where f′(x) exists but has rank less than n. Then the set f[C] has measure zero.

Proof. If L^{n}(C) < ∞ then the result follows from Lemma 3.3 by letting M = 0. In the general case we can let decompose C as C = ⋃_{k=1}^{∞} A_{k} where for each k L^{n}(A_{k}) < ∞ (for example let A_{k} = B(0, k) ∩ A). Then Lemma 3.3 implies f[A_{k}] has measure zero and thus the same is true of f[C] = ⋃_{k=1}^{∞} f[A_{k}].

Proof of Theorem 3.1. Split Crit(G) into two sets, the first being

N := {x ∈ R^{n} : G′(x) does not exist}

the points where the derivative does not exist and the second being

C := {x ∈ R^{n} : det G′(x) = 0}

being the points where G′(x) exists but has rank less than n.

From Rademacher’s Theorem 2.6 the set N has measure zero. But as G is Lipschitz this implies L^{n}(G[N]) = 0. But Theorem 3.6 implies L^{n}(G[C]) = 0. Thus

L^{n}(G[Crit(G)]) ≤ L^{n}(G[N]) + L^{n}(G[C]) = 0 + 0 = 0.

This completes the proof.

Proof of Proposition 3.2. If L^{n}(A) = ∞ there is nothing to prove so assume L^{n}(A) < ∞. Let ε > 0. Then there is an open set U so that A ⊂ U and L^{n}(U) ≤ L^{n}(A) + ε.

For each a ∈ A the claim 3.4 gives an r_{0} = r_{0}(a, ε) so that for all r ≤ r_{0} the ball B(a, r) satisfies L^{n}(f[B(a, r)]) ≤ (M + ε)L^{n}(B(a, r)). Let

V(a) := {B(a, r) : r ≤ r_{0}(a, ε) and B(a, r) ⊂ U}

and set

V : ⋃_{a∈A} V(a).

Then V is a fine cover of A (that is every point of A is contained in balls of arbitrarily small balls contained in V. Then by the Vitali covering theorem (cf. [8, Thm 1.3.6 P. 12] where this is deduced from the Besicovitch covering theorem) there is a countable set {B(x_{k}, r_{k})}_{k=1}^{∞} ⊂ V so that

L^{n} (A \ ⋃_{k=1}^{∞} B(x_{k}, r_{k})) = 0

and B(x_{i}, r_{i}) ∩ B(x_{j}, r_{j}) = ∅ if i ≠ j. Let A_{0} = A \ ⋃_{k=1}^{∞} B(x_{k}, r_{k}) and A_{1} = A ∩ (⋃_{k=1}^{∞} B(x_{k}, r_{k})). Then L^{n}(A_{0}) = 0 and therefore L^{n}(f[A_{0}]) = 0 by Lemma 3.3. As to A_{1} we have

L^{n}(f[A_{1}]) ≤ L^{n} (f [ ⋃_{k=1}^{∞} B(x_{k}, r_{k})])

≤ ∑_{k=1}^{∞} L^{n}(f[B(x_{k}, r_{k})])

≤ (M + ε) ∑_{k=1}^{∞} L^{n}(B(x_{k}, r_{k}))

= (M + ε)L^{n} ( ⋃_{k=1}^{∞} B(x_{k}, r_{k}))

≤ (M + ε)L^{n}(U)

≤ (M + ε)(L^{n}(A) + ε).

But ε was arbitrary so L^{n}(f[A_{1}]) ≤ ML^{n}(A_{1}). Thus L^{n}(f[A]) ≤ L^{n}(f[A_{0}])+ L^{n}(f[A_{1}]) ≤ 0 + ML^{n}(A_{1}) = L^{n}(A) as L^{n}(A_{0}) = 0. This completes the proof.

3.1. A more general result.

3.7. Theorem. Let f: R^{n} → R^{n} be any map and let A ⊂ R^{n} be a set so that f′(x) exists for all x ∈ A. Then

∫_{R^{n}} #(A ∩ f^{−1}[y]) dy ≤ ∫_{A} | det f′(x)| dx.

Note that χ_{f[A]}(y) ≤ #(A ∩ f^{−1}[y]) for all y so there is the inequality L^{n}(f[A]) ≤ ∫_{R^{n}} #(A∩f^{−1}[y]) dy therefore the theorem as a corollary (which will actually be proven first as for use as a lemma):

3.8. Corollary. Let f: R^{n} → R^{n} be any map and let A ⊆ R^{n} be a set so that f′(x) exists for all x ∈ A. Then

L^{n}(f[A]) ≤ ∫_{A} | det f′(x)| dx.

Proof. We can assume that L^{n}(A) < ∞ for if we prove the result in that case we can split a set A with L^{n}(A) = ∞ into a countable disjoint collection of subsets with finite measure and apply what we have shown to those subsets and then sum over the collection to get the bound in the general case. So assume L^{n}(A) < ∞ and define

A_{0} := {x ∈ A : det f′(x) = 0}
A_{k,j} := \{x ∈ A : \frac{j − 1}{2^{k}} < | det f′(x)| ≤ \frac{j}{2^{k}} \}

A_{k} := ⋃_{j=1}^{2^{2k}} A_{k,j}

f_{k} := ∑_{j=1}^{2^{2k}} \frac{j − 1}{2^{k}}χ_{A_{k,j}}

where χ_{A_{k,j}} is the characteristic function of A_{k,j}. Then 0 ≤ f_{k} ≤ f_{k+1}, lim_{k→∞} f_{k}(x) = | det f′(x)| on A, and the support of f_{k} is A_{k}. By the monotone convergence theorem

lim_{k→∞} ∫_{A} f_{k}(x) dx = ∫_{A} | det f′(x)| dx.

By Proposition 3.2

L^{n}(f[A_{k,j}]) ≤ \frac{j}{2^{k}} L^{n}(A_{k,j}).

12 RALPH HOWARD

Thus

L^{n}(f[A_{k}]) ≤ ∑_{j=1}^{2^{2k}} L^{n}(f[A_{k,j}])

≤ ∑_{j=1}^{2^{2k}} \frac{j}{2^{k}} L^{n}(A_{k,j})

= \frac{1}{2^{k}} ∑_{j=1}^{2^{2k}} L^{n}(A_{k,j}) + ∑_{j=1}^{2^{2k}} \frac{j − 1}{2^{k}}L^{n}[A_{k,j}]

= \frac{1}{2^{k}} L^{n}(A_{k}) + ∑_{j=1}^{2^{2k}} \frac{j − 1}{2^{k}}L^{n}[A_{k,j}]

= \frac{1}{2^{k}} L^{n}(A_{k}) + ∫_{A} f_{k}(x) dx

≤ \frac{1}{2^{k}} L^{n}(A) + ∫_{A} f_{k}(x) dx

Also f[A_{k}] ⊆ f[A_{k+1}] and ⋃_{k=1}^{∞} f[A_{k}] = f[A] so

L^{n}(f[A]) = lim_{k→∞} L^{n}(f[A_{k}])

≤ lim_{k→∞}(\frac{1}{2^{k}} L^{n}(A_{k}) + ∫_{A} f_{k}(x) dx)

= ∫_{A} | det f′(x)| dx.

This completes the proof. proof of Theorem 3.7. We can assume that det f′(x) ≠ 0 for all y ∈ A. This is because if N := {x ∈ A : det f′(x) = 0} then ∫_{A} | det f′(x)| dx = ∫_{A\N} | det f′(x)| dx and by Proposition 3.6 the image f[N] has measure zero and thus ∫_{R^{n}} #(A ∩ f^{−1}[y]) dy = ∫_{R^{n}\f[N]} #(A ∩ f^{−1}[y]) dy.

As we are assuming that f′(a) is nonsingular for all a ∈ A the inverse f′(a) exists. Define

C_{k} = {a ∈ A :∥f′(a)∥_{Op}, ∥f′(a)∥_{Op} ≤ k, and ∥f(x) − f(a) − f′(a)(x − a)∥

≤ \frac{1}{∥f′(a)^{−1}∥_{Op}∥x − a∥} for ∥x − a∥ ≤ \frac{1}{k} \}

Then A = ⋃_{k=1}^{∞} C_{k}. 3.9. Claim. If a ∈ A_{k} and if a ∈ R^{n} with ∥x − a∥ ≤ \frac{1}{k} then

\frac{1}{2k} ∥x − a∥ ≤ ∥f(x) − f(a)∥ ≤ \frac{3}{2}k∥x − a∥.

THEOREMS OF RADEMACHER AND ALEXANDROV 13

Proof of claim. Note that ∥f′(a)∥_{Op} ≤ k implies 1 = ∥I∥_{Op} = ∥f′(a)f′(a)^{−1}∥_{Op}∥ ≤ ∥f′(a)∥_{Op}∥f′(a)^{−1}∥_{Op} ≤ k∥f′(a)∥_{Op}∥f′(a)^{−1}∥_{Op} so that \frac{1}{∥f′(a)^{−1}∥_{Op}} ≤ k. Thus

∥f(x) − f(a)∥ ≤ ∥f(x) − f(a) − f′(a)(x − a)∥ + ∥f′(a)(x − a)∥

≤ \frac{1}{2∥f′(a)^{−1}∥_{Op}} ∥x − a∥ + ∥f′(a)∥_{Op}∥x − a∥

≤ \frac{k}{2} ∥x − a∥ + k∥x − a∥

= \frac{3}{2}k∥x − a∥

which is the required upper bound on ∥f(x) − f(a)∥. For the lower bound estimate

∥x − a∥ ≤ ∥f′(a)^{−1}∥_{Op}∥f′(a)(x − a)∥

≤ ∥f′(a)^{−1}∥(∥f(x) − f(a) − f′(a)(x − a)∥ + ∥f(x) − f(a)∥)

≤ ∥f′(a)^{−1}∥_{Op} \frac{1}{2∥f′(a)^{−1}∥_{Op}} ∥x − a∥ + ∥f′(a)^{−1}∥_{Op}∥f(x) − f(a)∥

≤ \frac{1}{2}∥x − a∥ + k∥f(x) − f(a)∥.

This can be solved for ∥f(x) − f(a)∥ to get

\frac{1}{2k} ∥x − a∥ ≤ ∥f(x) − f(a)∥.

This completes the proof of the claim.

Returning to the proof of Theorem 3.7 we let A_{1} := C_{1} and A_{k} := C_{k} \ C_{k−1} for k ≥ 2. Then we can decompose each A_{k} into a disjoint union

A_{k} = • ⋃_{j=1}^{∞} A_{k,j} with diameter(A_{k,j}) ≤ \frac{1}{k} .

Then by the claim we have that if a, b ∈ A_{k,j} then

\frac{1}{2k} ∥b − a∥ ≤ ∥f(b) − f(a)∥ ≤ \frac{3}{2}k∥b − a∥.

Therefore the restriction f|_{A_{k,j}}: A_{k,j} → R^{n} is injective. Also A is a disjoint union A = • ⋃_{k,j} A_{k,j}. Now from Corollary 3.8

L^{n}(f[A_{k,j}]) ≤ ∫_{A_{k,j}} | det f′(x)| dx.

But as f|_{A_{k,j}} is injective we have

∫_{R^{n}} #(A ∩ f^{−1}[y]) dy = ∑_{j,k} L^{n}(f[A_{k,j}])

≤ ∑_{j,k} ∫_{A_{k,j}} | det f′(x)| dx

= ∫_{A} | det f′(x)| dx.

This completes the proof.

4. An Inverse Function Theorem for Continuous Functions Differentiable at a Single Point

Let A: R^{n} → R^{m} be a linear map. Then the operator norm of A is defined by

∥A∥_{Op} := inf_{0≠v∈R^{n}} \frac{∥Av∥}{∥v∥}.

Therefore the inequality

∥Av∥ ≤ ∥A∥_{Op}∥v∥.

holds.

We now give a form of the inverse function theorem that only requires the function G: R^{n} → R^{n} to be continuous and differentiable at one point x_{0}. In this generality the function need not have a local inverse, but we will be able to solve the equation G(x) = y for y close to G(x_{0}). However the proof is just an easy variant on the usual proof of the inverse function theorem where the Brouwer fixed point theorem is used instead of Banach’s fixed point theorem for contractions.

4.1. Theorem. Let G: R^{n} → R^{n} be continuous and differentiable at x_{0} with G′(x_{0}) nonsingular. Set y_{0} = G(x_{0}). Then there is an r_{0} > 0 so that if

β := \frac{1}{2∥G′(x_{0})^{−1}∥_{Op}} , r_{1} = βr_{0},

then

1. for all y ∈ \overline{B}(y_{0}, r_{1}) there is an x ∈ \overline{B}(x_{0}, r_{0}) with G(x) = y.

2. If y ∈ \overline{B}(y_{0}, r_{1}) and x ∈ \overline{B}(x_{0}, r_{0}) with G(x) = y the inequalities

β∥x − x_{0}∥ ≤ ∥y − y_{0}∥ ≤ (β + ∥G′(x_{0})∥_{Op})∥x − x_{0}∥.

hold.

THEOREMS OF RADEMACHER AND ALEXANDROV 15

Proof. From the definition of the derivative there is an r_{0} > 0 so that ∥x − x_{0}∥ ≤ r_{0} implies

∥G(x) − y_{0} − G′(x_{0})(x − x_{0})∥ ≤ \frac{1}{2∥G′(x_{0})^{−1}∥_{Op}} ∥x − x_{0}∥

= β∥x − x_{0}∥. (4.1)

For y ∈ R^{n} define Φ_{y}: R^{n} → R^{n} by

Φ_{y}(x) := x − G′(x_{0})^{−1}(G(x) − y).

Then (4.2) Φ_{y}(x) = x if and only if G(x) = y and

x_{0} − Φ_{y}(x) = x_{0} − x + G′(x_{0})^{−1}(G(x) − y)
= x_{0} − x + G′(x_{0})^{−1}(G(x) − y_{0}) + G′(x_{0})^{−1}(y_{0} − y)
= G′(x_{0})^{−1}(G(x) − y_{0} − G′(x_{0})(x − x_{0})) + G′(x_{0})^{−1}(y_{0} − y)

Using the definition of r_{0} we have that if ∥x − x_{0}∥ ≤ r_{0} then

∥x_{0} − Φ_{y}(x)∥ ≤ ∥G′(x_{0})^{−1}∥_{Op}∥G(x) − y_{0} − G′(x_{0})(x − x_{0})∥
+ ∥G′(x_{0})^{−1}∥_{Op}∥y − y_{0}∥

≤ ∥G′(x_{0})^{−1}∥_{Op} \frac{1}{2∥G′(x_{0})^{−1}∥_{Op}} ∥x − x_{0}∥

+ ∥G′(x_{0})^{−1}∥_{Op}∥y − y_{0}∥

= \frac{1}{2}∥x − x_{0}∥ + ∥G′(x_{0})^{−1}∥_{Op}∥y − y_{0}∥ (4.3)

Therefore using the definition of β and r_{1}

∥x − x_{0}∥ ≤ r_{0}, ∥y − y_{0}∥ ≤ r_{1} implies ∥Φ_{y}(x) − x_{0}∥ ≤ r_{0}. So if y ∈ \overline{B}(y_{0}, r_{1}) we have that Φ_{y}: \overline{B}(x_{0}, r_{0}) → \overline{B}(x_{0}, r_{0}). Thus by the Brouwer fixed point theorem the map Φ_{y} will have a fixed point in \overline{B}(x_{0}, r_{0}). But Φ_{y}(x) = x implies that G(x) = y by (4.2). Thus proves the first of the two conclusions of the theorem.

If x ∈ \overline{B}(x_{0}, r_{0}) and y ∈ \overline{B}(y_{0}, r_{1}). Then by (4.2) Φ_{y}(x) = x and so by the estimate (4.3)

∥x − x_{0}∥ = ∥Φ_{y}(x) − x_{0}∥ ≤ \frac{1}{2}∥x − x_{0}∥ + ∥G′(x_{0})^{−1}∥_{Op}∥y − y_{0}∥

which along with the definition of β implies

β∥x − x_{0}∥ = \frac{1}{2∥G′(x_{0})^{−1}∥_{Op}} ∥x − x_{0}∥ ≤ ∥y − y_{0}∥

which proves the lower bound of second conclusion of the theorem. To prove the upper we use the implication (4.1)

∥y − y_{0}∥ ≤ ∥G(x) − y_{0}∥
≤ ∥G(x) − y_{0} − G′(x_{0})(x − x_{0})∥ + ∥G′(x_{0})(x − x_{0})∥
≤ β∥x − x_{0}∥ + ∥G′(x_{0})∥_{Op}∥x − x_{0}∥
(β + ∥G′(x_{0})∥_{Op})∥x − x_{0}∥.

This completes the proof.

5. Derivatives of Set-Valued Functions and Inverses of Lipschitz Functions

A set-valued function F: R^{n} → R^{m} is a function so that for each x ∈ R^{n} the value F (x) is a subset of R^{n}. We will also refer to such functions as multiple valued. If F (x) = ∅ then F is said to be undefined at x and if F (x) ≠ ∅ then F is defined at x. If f: R^{n} → R^{m} is an ordinary function it determines a set-valued function by F (x) = {f(x)}. In this case we will just identify F and f and say that F is single valued and just write F (x) = f(x). More generally if F (x) = {y} is single valued at a point x then we will write F (x) = y and conversely if we write F (x) = y this means that F is single valued at x and that F (x) = {y}.

5.1. Definition. The set-valued function F: R^{n} → R^{m} is differentiable at x_{0} iff there is a linear map L: R^{n} → R^{m} so that for all ε > 0 there is a δ > 0 such that

\{ \begin{matrix}∥x − x_{0}∥ ≤ δ, y_{0} ∈ F (x_{0}), y ∈ F (x) implies \\ ∥y − y_{0} − L(x − x_{0})∥ ≤ ε∥x − x_{0}∥. \end{matrix} (5.1)

With what I hope is obvious notation if F is single valued at x_{0} (and this will always be the case if F is differentiable at x_{0}) and y_{0} = F (x_{0}) then F is differentiable at x_{0} iff

y ∈ F (x) implies y − y_{0} = L(x − x_{0}) + o(∥x − x_{0}∥).

5.2. Proposition. If F: R^{n} → R^{m} is set-valued then

1. If F is single valued then F is differentiable at x_{0} is the sense of Definition 5.1 if and only if it is differentiable at x_{0} in the usual sense (that is is in Definition 2.5.)

2. If F is differentiable at x_{0} then F is single valued at x_{0} and the linear map L in (5.1) is uniquely determined. We will call this linear map the derivative of F at x_{0} and write G′(x_{0}) = L.

3. If F is differentiable at x_{0} and f: R^{n} → R^{m} is single valued and differentiable at x_{0} then the set-valued function H(x) := f(x) + F (x) is differentiable at x_{0} and H′(x_{0}) = f′(x_{0}) + F′(x_{0}).

Proof. The first and last of these are straightforward and left to the reader. For the second let y_{0}, y_{1} ∈ F (x_{0}). Then letting x = x_{0} and y = y_{1} in (5.1) we get ∥y_{1} − y_{0}∥ ≤ 0. Thus y_{1} = y_{0} which shows F is single valued at x_{0}. If L and L_{1} are linear maps which work in (5.1) then for any ε > 0 let δ > 0 so that (5.1) holds. Then for y_{0} = F (x_{0}) and y ∈ F (x) where ∥x − x_{0}∥ ≤ δ

∥(L − L_{1})(x − x_{0})∥ = ∥L(x − x_{0}) − L_{1}(x − x_{0})∥
≤ ∥y − y_{0} − L(x − x_{0})∥ + ∥y − y_{0} − L_{1}(x − x_{0})∥
≤ 2ε∥x − x_{0}∥

Thus can be rescaled to show for all v ∈ R^{n} that ∥(L − L_{1})v∥ ≤ 2ε∥v∥. As ε was arbitrary this implies L = L_{1} and completes the proof.

5.3. Theorem. Let G: R^{n} → R^{n} be a surjective Lipschitz function and assume that for each y ∈ R^{n} the preimage G^{−1}[y] is connected. Then define a set-valued function F: R^{n} → R^{n} to be the inverse of G, that is

F (y) := G^{−1}[y] = {x : F (x) = y}.

Then F is differentiable almost everywhere with F′(G(x)) = G′(x)^{−1}.

Proof. Let x_{0} ∈ R^{n} be a point where G′(x_{0}) exists and is nonsingular. Let y_{0} = G(x_{0}). We first show that F is differentiable at y_{0} with F′(y_{0}) = G′(x_{0})^{−1}. Toward this end we use the version of the inverse function given by 4.1 to get positive numbers r_{0} and β so that if r_{1} = βr_{0} and C_{0} = (β + ∥G′(x_{0})∥_{Op}) then

For all y ∈ \overline{B}(y_{0}, r_{1}) there is x ∈ \overline{B}(x_{0}, r_{0}) with G(x) = y.

and

x ∈ \overline{B}(x_{0}, r_{0}) and y ∈ \overline{B}(y_{0}, r_{1}) with G(x) = y implies

β∥x − x_{0}∥ ≤ ∥y − y_{0}∥ ≤ C_{0}∥x − x_{0}∥. (5.2)

If y ∈ B(y_{0}, r_{1}), so that ∥y − y_{0}∥ < r_{1} = βr_{0}, then for x ∈ \overline{B}(x_{0}, r_{0}) we have β∥x − x_{0}∥ ≤ ∥y − y_{0}∥ < βr_{0} and so x ∈ B(x_{0}, r_{0}). Thus implies that if y ∈ B(y_{0}, r_{1}) then G^{−1}[y] ∩ {x : ∥x − x_{0}∥ = r_{0}} = ∅. But as G^{−1}[y] ∩ \overline{B}(x_{0}, r_{0}) ≠ ∅ and F (y) = G^{−1}[y] is connected this yields that G^{−1}[y] ⊂ B(x_{0}, r_{0}) for all y ∈ B(y_{0}, r_{1}). Therefore (5.2) can be improved to

x ∈ R^{n} and y ∈ B(y_{0}, r_{1}) with x ∈ F (y) implies

β∥x − x_{0}∥ ≤ ∥y − y_{0}∥ ≤ C_{0}∥x − x_{0}∥. (5.3)

As G is differentiable at x_{0}

G(x) − y_{0} = G′(x_{0})(x − x_{0}) + o(∥x − x_{0}∥)

which, as G′(x_{0}) is invertible, is equivalent to

x − x_{0} = G′(x_{0})^{−1}(G(x) − y_{0}) + o(∥x − x_{0}∥)

Let y ∈ B(y_{0}, r_{1}) then this last equation implies

x ∈ F (y) implies x − x_{0} = G′(x_{0})^{−1}(G(x) − y_{0}) + o(∥x − x_{0}∥).

But by the inequalities in (5.3) for y ∈ B(y_{0}, r_{1}) we have o(∥x − x_{0}∥) = o(∥y − y_{0}∥) and thus for y ∈ B(y_{0}, r_{1})

x ∈ F (y) implies x − x_{0} = G′(x_{0})^{−1}(y − y_{0}) + o(∥y − y_{0}∥).

This shows that F is differentiable at y_{0} with derivative G′(x_{0})^{−1} as claimed. Let

E := {y ∈ R^{n} : y_{0} = G(x) where G′(x) exsits and is nonsingular}.

We have just shown that F is differentiable at each point of E and that at these points F′(G(x)) = G′(x)^{−1}. Theorem 3.1 implies L^{n}(R^{n} \ E) = 0. This completes the proof.

6. Alexandrov’s Theorem

Let f: R^{n} → R a function. A vector b ∈ R^{n} is a lower support vector for f at x_{0} iff

f(x) − f(x_{0}) ≥ b · (x − x_{0}) for all x ∈ R^{n}.

For each x_{0} ∈ R^{n} set

∇f(x_{0}) := {b : b is a lower suport vector for f at x_{0}}.

Of course for some functions this maybe empty for many (and possibly all) points x_{0}. The function f is convex iff ∇f(x) is nonempty for all x ∈ R^{n} (this is equivalent to the more usual definition of f((1−t)x_{0}+tx_{1}) ≤ f((1 − t)x_{0}) + tf(x_{1}) for 0 ≤ t ≤ 1 cf. [7, Thm 1.5.9 p. 29]). If f is convex then it is easy to see that ∇f(x) is a convex set for all x. Our goal is to give a proof of:

6.1. Theorem (Busemann-Feller [3, 1936] and Alexandrov [1, 1939]). Let f: R^{n} → R be convex. Then the set-valued function ∇f is differentiable almost everywhere.

6.2. Remark. When n = 1 this follows from the differentiability almost everywhere of monotone functions of one variable. The case n = 2 was proven by H. Busemann and W. Feller [3] in 1936. The general case was settled in 1939 by A. D. Alexandrov [1].

We start with the following basic property of convex functions.

6.3. Proposition. Let f: R^{n} → R be convex. Then the set valved function ∇f is monotone in the sense that

b_{0} ∈ ∇f(x_{0}), b_{1} ∈ ∇f(x_{1}) implies (b_{1} − b_{0}) · (x_{1} − x_{0}) ≥ 0.

We will sometime miss use notation and write this in the more easily read form

(∇f(x_{1}) − ∇f(x_{0})) · (x_{1} − x_{0}) ≥ 0.

Proof. From the definitions of b_{0} ∈ ∇f(x_{0}) and b_{1} ∈ ∇f(x_{1}) we have

f(x_{1}) − f(x_{0}) ≥ b_{0} · (x_{1} − x_{0})
f(x_{0}) − f(x_{1}) ≥ b_{1} · (x_{0} − x_{1}).

The result follows by adding these.

Also of use is the following which I have seen used in other parts of geometry (for example in the theory of minimal surfaces).

6.4. Proposition. Let f: R^{n} → R be convex. Then the set-valued map

F (x) = x + ∇f(x)

is surjective (i.e. for all y ∈ R^{n} then is an x ∈ R^{n} so that y ∈ F (x)) and is non-contractive ∥F (x_{1}) − F (x_{0})∥ ≥ ∥x_{1} − x_{0}∥. More precisely

(6.1) y_{1} ∈ F (x_{1}) and y_{0} ∈ F (x_{0}) implies ∥y_{1} − y_{0}∥ ≥ ∥x_{1} − x_{0}∥.

The inverse G of F defined by G(y) = x iff y ∈ F (x) is single valued and Lipschitz. In fact

∥G(x_{1}) − G(x_{0})∥ ≤ ∥x_{1} − x_{0}∥. (6.2)

Proof. To see that F is surjective let y ∈ R^{n} and let φ: R^{n} → R be the function

φ(x) := \frac{1}{2}∥x∥^{2} + f(x) − x · y.

As h_{y}(x) := \frac{1}{2}∥x∥^{2}−x·y is convex the function φ is a sum of convex functions and thus is convex. Also, as h_{y}(x) = \frac{1}{2}∥x∥^{2} −x·y is smooth so that its lower support vectors are given by the classical gradient ∇h_{y}(x) = {Dh_{y}} = x−y, we have (Proposition 5.2) that

∇φ(x_{0}) = ∇h_{y}(x_{0}) + ∇f(x_{0}) = x_{0} − y + ∇f(x_{0}) = F (x_{0}) − y.

(Here F (x_{0}) − y = {η − y : η ∈ F (x_{0})}.)

Likewise the function

ψ(x) := \frac{1}{4}∥x∥^{2} + f(x) − x · y = φ(x) − \frac{1}{4}∥x∥^{2}

is convex. Let b a lower support vector to ψ at 0. Then the inequality ψ(x) − ψ(0) ≥ b · (x − 0) can be rewritten as

φ(x) ≥ φ(0) + \frac{1}{4}∥x∥^{2}.

As φ is continuous this implies there is an x_{0} so that φ will have a global minimum at x_{0}. Then 0 will be a lower support vector for φ at x_{0}. But 0 ∈ ∇φ(x_{0}) = F (x_{0}) − y implies that y ∈ F (x_{0}). As y was arbitrary this implies F is surjective as claimed.

Let y_{1} ∈ F (x_{1}) and y_{0} ∈ F (x_{0}). Then there are b_{1} ∈ ∇f(x_{1}) and b_{0} ∈ ∇f(x_{0}) so that y_{1} = x_{1} + b_{1} and y_{0} = x_{0} + b_{0}. Then by proposition 6.3

(y_{1} − y_{0}) · (x_{1} − x_{0}) = (x_{1} + b_{1} − x_{0} − b_{0}) · (x_{1} − x_{0})
= ∥x_{1} − x_{0}∥^{2} + (b_{1} − b_{0}) · (x_{1} − x_{0})
≥ ∥x_{1} − x_{0}∥^{2}.

Therefore by the Cauchy Schwartz inequality

∥y_{1} − y_{0}∥∥x_{1} − x_{0}∥ ≥ (y_{1} − y_{0}) · (x_{1} − x_{0}) ≥ ∥x_{1} − x_{0}∥^{2}

which implies (6.1). In particular this implies that if y ∈ F (x_{1}) and y ∈ F (x_{0}) then ∥x_{1} − x_{0}∥ ≤ ∥y − y∥ = 0 and so x_{1} = x_{0}. Thus the inverse G of F (defined by G(y) = {x : y ∈ F (x)}) is single valued. The inequality (6.2) is then equivalent to (6.1). This completes the proof.

Proof of Theorem 6.1. Let f: R^{n} → R be convex and let F (x) = x+∇f(x). Then by the last proposition F is the inverse a Lipschitz function G. Moreover as each set ∇f(x) is convex the same is true of F (x) = x + ∇f(x) and thus F (x) is connected. Therefore Theorem 5.3 implies that F is differentiable almost everywhere. But ∇f(x) = F (x) − x is differentiable at the same points where F is differentiable and so it is also differentiable almost everywhere.

6.5. Corollary. If G is the function used in the proof of Proposition 6.4 then there is a convex function g: R^{n} → R so that G(y) = ∇g(y).

Proof. Let h: R^{n} → R be the function

h(x) := \frac{1}{2}∥x∥^{2} + f(x).

Then define g by

g(y) = max_{x∈R^{n}}(x · y − h(x)).

Note x · y − h(x) = −(\frac{1}{2}∥x∥^{2} + f(x) − x · y) = −φ(x) with φ as in the proof of Proposition 6.4. In the proof of Proposition 6.4 it has shown that φ always obtains its minimum and therefore g will always obtain its maximum. Moreover given y_{0} a point x_{0} is where the maximum occurs in the definition of g if and only if

0 ∈ ∇(x·y_{0} −h(x))|_{x=x_{0}} = ∇(x·y_{0} − \frac{1}{2}∥x∥^{2} −f(x))|_{x=x_{0}} = y_{0} −x_{0} −∇f(x_{0}).

That is if and only if y_{0} ∈ x_{0} + ∇f(x_{0}) = F (x_{0}) (with F as in Proposition 6.4). This is the same as G(y_{0}) = x_{0}. Thus the definition of g implies

(6.3) h(x) + g(y) ≥ x · y with equality iff x = G(y).

But this is symmetric in x and y so we also have

h(x) = max_{y∈R^{n}}(x · y − g(y)) (6.4)

and for a given x the maximum occurs for those y with G(y) = x. We now want to show that g is convex. Let y_{0} ∈ R^{n} and let x_{0} = G(y_{0}). Then the formula giving h as a maximum implies

x_{0} · y_{0} − g(y_{0}) ≥ x_{0} · y − g(y)

which can be rewritten as

g(y) − g(y_{0}) ≥ x_{0} · (y − y_{0})

and thus x_{0} is a lower support vector for g at y_{0} and so ∇g(y_{0}) ≠ ∅. As y_{0} was any point of R^{n} this implies g is convex.

Finally if y_{0} ∈ R^{n} and x_{0} is the point where the maximum occurs in 6.4 then equality holds in (6.3) and so G(y_{0}) = x_{0}. But also we have 0 ∈ ∇(x_{0} · y − g(y))|_{y=y_{0}} = x_{0} − ∇g(y_{0}). Thus x_{0} ∈ ∇g(y_{0}) if and only if G(y_{0}) = x_{0}. Therefore G(y_{0}) = ∇g(y_{0}). This completes the proof.

7. Symmetry of the Second Derivatives

If f: R^{n} → R is convex then at the points x_{0} where the derivative of the set-valued map ∇f exists then it is a linear map (∇f)′(x_{0}): R^{n} → R^{n}. Then we wish to show that at least for almost all x_{0} that ⟨(∇f)′(x_{0})u, v⟩ = ⟨(∇f)′(x_{0})v, u⟩. Formally the matrix of (∇f)′ is [D_{i}D_{j}f] and at least on the level of distributions D_{i}D_{j}f = D_{j}D_{i}f. The complication is that the distributional second derivatives of f do not have to be functions and so information about them does not seem to directly imply information about (∇f)′(x_{0}) at points where it exists. (For an example in one dimension where the second derivative is not a function consider f(x) = |x|. Then f′′(x) = 2δ where δ is the point mass (i.e. Dirac delta function) at the origin.)

7.1. Theorem. Let f: R^{n} → R be convex. Then for almost all x ∈ R^{n} the derivative of the set-valued function ∇f is single valued and (∇f)′(x) is a symmetric positive definite matrix. (Explicitly ⟨(∇f)′(x)u, v⟩ = ⟨(∇f)′(x)v, u⟩ and (∇f)′(x)v, v⟩ ≥ 0 for almost all x.)

Proof. That (∇f)′(x) exists almost everywhere has already been shown. In the proof of Alexandrov’s theorem we showed that if F (x) = x+∇f(x) then the inverse G of F is single valued, Lipschitz, and that almost every point x ∈ R^{n} is of the form x = G(y) at a point where G′(y) is nonsingular and at these points F′(G(y)) = G′(y)^{−1}. In Corollary 6.5 we showed that there is a convex function g so that ∇g(y) = G(y). But G is Lipschitz and therefore its classical derivatives exist almost everywhere and are bounded. Moreover the distributional derivatives of G will equal the classical derivatives. But as G = ∇g this implies that the classical second derivatives D_{i}D_{j}g of g exist almost everywhere and that they are equal to the distributional second derivatives of g. But the (as distributional derivatives commute) we have that the classical derivatives satisfy D_{i}D_{j}g(y) = D_{j}D_{i}g(y) for almost all y. That is the matrix of G′(y) = (∇g)′(y) is symmetric. But then as F′(G(y)) = G′(y)^{−1} the matrix of F′(G(y))^{−1} is symmetric. (Note that the set A := {y : G′(y) is not symmetric} has measure zero and G is Lipschitz so G[A] will also be of measure zero and so we can ignore the x = G(y) where G′(y) is not symmetric.) This shows F′(x) is symmetric for almost all x. But F (x) = x + ∇f(x) implies F′(x) = I + (∇f)′(x) so that (∇f)′(x) is symmetric at exactly the same set of points where F′(x) is symmetric. This shows that (∇f)′(x) is symmetric for almost all x.

That (∇f)(x) is positive semi-definite follows from a calculation and the fact that f is convex (and thus has a lower supporting linear hyperplane at each point). Details are left to the reader.

References

1. A. D. Alexandrov, Almost everywhere existence of the second differential of a convex function and some properties of convex surfaces connected with it, Leningrad State Univ. Annals [Uchenye Zapiski] Math. Ser. 6 (1939), 3–35.

2. A. S. Besicovitch, A general form of the covering principle and relative differentiation of additive functions, Proc. Cambridge Philos. Soc. 41 (1945), 103–110.

3. H. Busemann and W. Feller, Krümmungsindikatritizen konvexer Flc̈hen, Acta Math. 66 (1936), 1–47.

4. M. G. Crandall, H. Ishii, and P.-L. Lions, Users guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc. 27 (1992), no. 1, 1–67.

5. F. Mignot, Contrôle dans les inéquations variationelles elliptiques, J. Functional Analysis 22 (1976), no. 2, 130–185.

6. H. Rademacher, Über partielle und totale Differenzierbarkeit I., Math. Ann. 79 (1919), 340–359.

7. R. Schneider, Convex bodies: The Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, 1993.

8. W. P. Ziemer, Weakly differentiable functions, Graduate Texts in Mathematics, vol. 120, Springer-Verlag, New York, 1989.