GENERIC CUT LOCI ARE DENSE

RALPH HOWARD

Abstract. Let K be the complete metric space of compact subsets of R^{n} with the Hausdorff distance. For K ∈ K let Cut(K) be the cut locus of K in R^{n}. We show that D := {K ∈ K : Cut(K) is dense in R^{n} ∖ K} is a dense G_{δ} in K.

The following are notes from a lecture give in the geometry/anaylsis seminar on Friday, 13 April 2001.

Contents

1. Introduction 1 2. The Hausdorff distance 2 3. Minimizing segments and generators 5 4. The Baire Category Theorem 7 5. Proof of Theorem 1 8 6. The cut locus and regularity properties of ρ_{A} 9 References 14

1. Introduction

Let A ⊂ R^{n} be a compact set and let

ρ_{A}(x) := min{∥x − a∥ : a ∈ A}

be the distance from A. We are interested in studying the regularity properties (such as where is is differentiable) in terms of geometric properties of A. Much of the regularity of ρ_{A} can be understood in terms of two geometric concepts: generators and cut points. For an interval I a unit speed curve c: I → R^{n} is A-minimizing iff ρ_{A}(c(t)) = t for all t ∈ I. An A-minimizing segment with maximal domain is called an A-generator. When A is clear from context we will just refer to generators. We will show that every Aminimizing segment is contained in an A-generator and that the domain of an A-generator is either of the form [0, L] (when the generator has finite length) or [0, ∞) (when the generator has infinite length). If c: [0, L] → R^{n} is a finite length A-generator, then its endpoint c(L) is the cut point of c. The set

Cut(A) = {c(L) : c: [0, L] → R^{n} is a finite length A-genator.}

is the cut locus of A. The elements of Cut(A) are called cut point of A. The relation of these concepts to regularity properties of ρ_{A} is that for x ∈ R^{n} ∖ A the derivative dρ_{A}(x) exists at x if and only if x is on exactly one generator of A (Theorem 6.8) and the set of non-differentiable points of ρ_{A} is dense in Cut(A) (Proposition 6.12).

If A is an embedded C^{2} submanifold of R^{n} then it is well known that Cut(A) is a closed subset of R^{n}. However for more general sets it is known that Cut(A) need not be closed and that it can be dense in an open set (cf. [7, 5]). We will show that this later behavior is generic. To make this precise, let K be the collection of nonempty compact subsets of R^{n} and d_{H}(A, B) be the Hausdorff distance between A and B (see Definition 2.1 for the precise definition). Then (K, d_{H}) is a complete metric space (Proposition 2.2).

Let

D := {A ∈ K : Cut(A) is a dense subset of R^{n} ∖ A}.

Our main result is that almost all, is the sense of Baire category, elements of K are in D. Recall that a set in a metric space is a G_{δ} iff it is a countable intersection of open sets.

Theorem 1. The set D is a dense G_{δ} in K.

It will be shown (Theorem 6.13) that D is also the set of A so that ρ_{A} is not differentiable on any open subset of R^{n} ∖ A. Theorems 1 and 6.13 are closely related to [5, Thm. 3 p. 5141] where they prove a related result with K replaced by the compact convex sets. These results show that for generic A ∈ K the function ρ_{A} is nowhere C^{1}. The proof here is an adaption of Banach’s [3] well known proof that almost every, in the sense of Baire category, function in C[0, 1] is nowhere differentiable. (For a very nice presentation of Banach’s proof and other ideas related to the Baire category theorem see the readable and informative little book [11] of Oxtoby.)

While the results here are stated and proven for compact subsets of Euclidean space R^{n}, it is not hard to see that they hold with only slightly rewritten proofs for compact subsets of a complete Riemannian manifold (and with some extra work and appropriate definitions in incomplete Riemannian manifolds or even smooth Finsler manifolds).

2. The Hausdorff distance

We start by making the collection of compact subsets of a complete metric space into another metric space.

2.1. Definition (Hausdorff 1914 [10]). Let (X, d) be a complete metric space and K the collection of all nonempty compact subsets of X. Define a distance d_{H} on K by

d_{H}(A, B) := max{sup_{a∈A} inf_{b∈B} d(a, b), sup_{b∈B} inf_{a∈A} d(a, b)}
= inf {r : Every point of A is within r of a point of B and every point of B is within r of a point of A. }

Then d_{H} is the Hausdorff distance on K. □

2.2. Proposition (Hausdorff 1914 [10]). If (X, d) is a compete metric space, then (K, d_{H}) is also a complete metric space.

Proof. To start:

Exercise 1. The function d_{H} satisfies the triangle inequality on K and if d_{H}(A, B) = 0, then A = B. □

This shows that (X, d_{H}) is a metric space. To show completeness let {A_{ℓ}}_{ℓ=1}^{∞} is a Cauchy sequence in (K, d_{H}) and let A be the set of all points a that are limits of convergent sequences {a_{ℓ}}_{ℓ=1}^{∞} with a_{ℓ} ∈ A_{ℓ}. From its definition A is easily seen to be closed and bounded. If (X, d) is a space where closed bounded sets are compact (such as R^{n}) then we have that A is compact without any more work.

But if (X, d) has closed bounded sets that are not compact (Hilbert space is such an example) more work is needed to show A is compact. This will be based on:

Exercise 2. Let (Y, d) be a metric space. Show (Y, d) is compact if and only if (Y, d) is complete and for every ε there is a finite number of open ε balls {B(y_{i}, ε)}_{i=1}^{N} that cover Y. (A metric space that can be covered by a finite number of ε balls for any ε is called totally bounded. Therefore a metric space is compact if and only if it is complete and totally bounded.) □

We next show that the Hausdorff distance between A and the terms in {A_{ℓ}}_{ℓ=1}^{∞} goes to zero.

Exercise 3. Let ε > 0 and choose that ℓ so that if m, n ≥ ℓ, then d_{H}(A_{m}, A_{n}) < ε. Then show that if n ≥ ℓ then for any point a of A_{n} there is a point b of A with d(a, b) ≤ ε and for every point b of A there is a point a of A_{n} with d(a, b) ≤ ε. □

Returning to our set A ⊂ X, it is a closed subset of compete metric space (X, d) and therefore A is complete as a metric space. So we only need show that it is totally bounded to show that it is compact. Let ε > 0. Then choose ℓ so that if m, n ≥ ℓ, then d_{H}(A_{m}, A_{n}) < ε/3. As A_{ℓ} is compact there is a finite subset {b_{1}, …, b_{N}} ⊂ A_{ℓ} so that every point of A_{ℓ} is at a distance < ε/3 from one of the b_{i}’s. By Exercise 3 for each b_{i} there is an a_{i} ∈ A with d(a_{i}, b_{i}) ≤ ε/3. Now let a ∈ A. There there is a point b ∈ A_{ℓ} with d(a, b) ≤ ε/3 and a b_{i} with d(b, b_{i}) < ε/3. Therefore

d(a, a_{i}) ≤ d(a, b) + d(b, b_{i}) + d(b_{i}, a_{i}) < ε/3 + ε/3 + ε/3 = ε.

Thus A ⊂ ⋃_{i=1}^{N} B(a_{i}, ε) and so A is totally bounded. Therefore A is compact as claimed.

Finally d_{H}(A, A_{ℓ}) → 0 follows from Exercise 3. So every Cauchy sequence in (K, d_{H}) converges and therefore it is complete. □

For a nonempty subset A of the a metric space (X, d) let

(2.1)  ρ_{A}(x) := inf{d(x, a) : a ∈ A}.

If A is compact then the infimum can be replaced by a minimum

ρ_{A}(x) := min{d(x, a) : a ∈ A} when A is compact.

The triangle inequality implies

(2.2)  ρ_{A}(y) ≤ ρ_{A}(x) + d(x, y).

Interchanging the rôles of x and y gives ρ_{A}(x) ≤ ρ_{A}(y) + d(y, x) and so

|ρ_{A}(x) − ρ_{A}(y)| ≤ d(x, y).

If f: X → R is continuous then the sup norm of f is

∥f∥_{L^{∞}} = sup_{x∈X} |f(x)|.

2.3. Proposition. If (X, d) is a compete metric space the Hausdorff distance on (K, d_{H}) is given by

d_{H}(A, B) = ∥ρ_{A} − ρ_{B}∥_{L^{∞}}

where ρ_{A} is defined by (2.1).

Proof. Let a ∈ A and let b ∈ B be so that d(a, b) = ρ_{B}(a). Then, using ρ_{A}(a) = 0, we have

d(a, b) = ρ_{B}(a) − ρ_{A}(a) = |ρ_{B}(a) − ρ_{A}(a)| ≤ ∥ρ_{A} − ρ_{B}∥_{L^{∞}}.

Thus we have shown that for any a ∈ A there is a b ∈ B with d(a, b) ≤ ∥ρ_{A} − ρ_{B}∥_{L^{∞}}. By symmetry there for each b ∈ A there is an a ∈ A with d(a, b) ≤ ∥ρ_{A} − ρ_{B}∥_{L^{∞}}. Therefore d_{H}(A, B) ≤ ∥ρ_{A} − ρ_{B}∥_{L^{∞}}.

To finish the proof it is enough to show ∥ρ_{A} − ρ_{B}∥_{L^{∞}} ≤ d_{H}(A, B). If x ∈ X let a ∈ A be so that d(x, a) = ρ_{A}(x). Then there is a b ∈ B with d(a, b) ≤ d_{H}(A, B). Therefore

ρ_{B}(x) ≤ d(x, b) ≤ d(x, a) + d(a, b) = ρ_{A}(x) + d(a, b) ≤ ρ_{A}(x) + d_{H}(A, B).

That is ρ_{B}(x)−ρ_{A}(x) ≤ d_{H}(A, B). Interchanging the rôles of A and B gives ρ_{A}(x) − ρ_{B}(x) ≤ d_{H}(A, B). Therefore |ρ_{B}(x) − ρ_{A}(x)| ≤ d_{H}(A, B). Whence

∥ρ_{B} − ρ_{A}∥ = sup_{x∈X} |ρ_{B}(x) − ρ_{A}(x)| ≤ d_{H}(A, B),

which completes the proof. □

2.4. Corollary. If A_{ℓ}, A ∈ K and d(A, A_{ℓ}) → 0, then ρ_{A_{ℓ}} → 0 uniformly. If also c_{ℓ}, c: [a, b] → X are continuous maps and c_{ℓ} → c uniformly then ρ_{A_{ℓ}}(c_{ℓ}(t)) → ρ_{A}(c(t)) uniformly.

Proof. This follows at once from the last proposition and general results about uniform convergence. □

3. Minimizing segments and generators

We first show that minimizing segments really are parts of line segments.

3.1. Proposition. Let A ∈ K and let c: [a, b] → R^{n} be an A-minimizing segment. Then c is a unit speed parameterization of the line segment between c(a) and c(b). Explicitly:

c(t) = \frac{1}{∥c(b) − c(a)∥}((b − t)c(a) + (t − a)c(b))

Proof. The triangle inequality implies that |ρ_{A}(x) − ρ_{A}(y)| ≤ ∥x − y∥ for all x, y ∈ R^{n}. As an A-minimizing segment c: [a, b] → R^{n} is unit speed we then have the length of c is b − a is ≥ the distance ∥c(b) − c(a)∥ between the endpoints of c. Therefore

∥c(b) − c(a)∥ ≤ Length(c) = (b − a) = ρ_{A}(c(b)) − ρ_{A}(c(a)) ≤ ∥c(b) − c(a)∥.

Thus c minimizes the distance between its endpoints and whence is a parameterization of a line segment. □

3.2. Proposition. Let A ∈ K. Then every x ∈ R^{n} ∖A is on a A-generator. The domain of an A-generator c is either [0, L] for some L > 0 or of the from [0, ∞) and in either case c(0) ∈ A.

Proof. If x ∉ A, then, as A is compact, there is a point z ∈ A so that ∥x − z∥ = ρ_{A}(x). Then c(t) = ∥x − z∥^{−1}((1 − t)z + tx) with t ∈ [0, ρ_{A}(x)] is an A-minimizing segment. Thus every point is on at least one such segment. For the segment c: [0, ρ_{A}(x)] → R^{n} just defined let \overline{c}: [0, ∞) → R^{n} be the natural extension of c to [0, ∞) (that is \overline{c}(t) = ∥x − z∥^{−1}((1 − t)z + tx) for all t ≥ 0). Let

L := sup\{b : \overline{c}|_{[0,b]} is an A-minimizing segment.\}

If L < ∞ then \overline{c}|_{[0,L]} : [0, L] → R^{n} is an A-generator. If L = ∞ then \overline{c}: [0, ∞) → R^{n} is an A-generator. From the construction of \overline{c} as an extension of c we have that L ≥ ρ_{A}(x) and therefore x is on the generator just constructed.

If c: [a, b] → R^{n} is an A-minimizing segment with a > 0, then let z ∈ A be a point with ∥c(a)−z∥ = a (note a = ρ_{A}(c(a)) by definition of A-minimizing) and define c_{0} : [0, b] → R^{n} by

c_{0}(t) := \begin{cases}a^{−1}((1 − t)z + tx), & t ∈ [0, a]; \\ c(t), & t ∈ [a, b]. \end{cases}

This is an A-minimizing segment. Thus every A-minimizing segment defined on an interval [a, b] can be extended to an A-minimizing segment on an interval [0, b]. It then follows that A-minimizing segments with maximal domain are either of the for c: [0, L] → R^{n}, or of the form c: [0, ∞) → R^{n}. Finally if c(0) will have distance zero from A and therefore c(0) ∈ A as A is closed. □

3.3. Proposition. If A ∈ K and z ∈ R^{n} ∖ A is on two A-generators, then z is a cut point of both generators.

Proof. Let z be on both c_{1} and c_{2}, which we assume are distinct. Let a = ρ_{A}(z). Then z = c_{1}(a) = c_{2}(a). If z is not a cut point of one of the two segments, say c_{2}, then we have for some b > a that c_{2}|_{[0,b]} is an A-minimizing segment. Let c: [0, b] → R^{n} be defined by

c(t) = \begin{cases}c_{1}(t), & t ∈ [0, a]; \\ c_{2}(t), & t ∈ [a, b]. \end{cases}

Then c will be A-minimizing and therefore by Proposition 3.1 a line segment. But this implies that c_{1} = c_{2} contrary to the assumption that c_{1} and c_{2} are distinct. □

3.4. Proposition. Let U ⊂ R^{n} be a non-empty open set. Then

K_{U} := {A ∈ K : U ∩ (A ∪ Cut(A)) = ∅}

is a closed nowhere dense subset of K.

Proof. Let A_{ℓ} ∈ K_{U} with lim_{ℓ→∞} A_{ℓ} = A in K. Then to show that K_{U} is closed we need that A ∈ K_{U}. As A_{ℓ} ∩ U = ∅ for all ℓ we have A ∩ U = ∅. Let z ∈ U and 2r = dist(z, ∂U). For each ℓ let a_{ℓ} = ρ_{A_{ℓ}}(z). Then there is an A_{ℓ}-generator c_{ℓ} with c_{ℓ}(a_{ℓ}) = z and, as c_{ℓ} has no endpoint in U, the domain of c_{ℓ} is at least [0, a_{ℓ} + 2r]. Let a = ρ_{A}(z). Then lim_{ℓ→∞} a_{ℓ} = a and by going to a subsequence we can assume that {c_{ℓ}}_{ℓ=1}^{∞} converges uniformly to some segment c on [0, a + r]. But then for t ∈ [0, a + r] we have

ρ_{A}(c(t)) = lim_{ℓ→∞} ρ_{A_{ℓ}}(c_{ℓ}(t)) = lim_{ℓ→∞} t = t

and therefore c: [0, a + r] → R^{n} is an A-minimizing segment. By Proposition 3.3 z = c(a) can not be on any other A-minimizing segment (otherwise it would be a cut point of c, contradicting that c(a) is in the interior of c: [0, a + r] → R). Therefore z = c(a) is not a cut point of any Aminimizing segment and so z ∉ Cut(A). As z was any point of U this shows that U ∩ (A ∪ Cut(A)) = ∅ and completes the proof that K_{U} is closed.

To show that K_{U} is nowhere dense let ε > 0 and A ∈ K_{U}. Let z ∈ U. Then by definition of K_{U}, z is not a cut point of A. Let a = ρ_{A}(z) and let c: [0, b] → R^{n} be a minimizing segment from A to z. Then c(a) = z. The closed ball \overline{B}(z, a) meets A in just the one point c(0) ∈ A, for otherwise there would be two minimizing segments from z to A, which would imply z is a cut point of A (by Proposition 3.3). Therefore we can choose a point x on the sphere S(z, a) := ∂B(z, a) with x ≠ c(0) and ∥x − c(0)∥ < ε. Let A_{1} = A ∪ {x}. Then

d_{H}(A, A_{1}) = dist(x, A) ≤ ∥x − c(0)∥ < ε.

Also dist(a, A_{1}) = a and \overline{B}(z, a) ∩ A = \{c(0), z\} so that there will be two minimizing segments from A_{1} to z. Therefore z is a cut point of A. This shows that for all ε > 0 and any A ∈ K_{U} there is an A_{1} ∉ K_{U} with d(A, A_{1}) < ε. Thus K_{U} is nowhere dense. □

4. The Baire Category Theorem

The statement of Baire’s theorem which is easiest to prove is:

4.1. Theorem (Baire Category Theorem, Baire 1899 [2]). Let (X, d) be a complete metric space. Then the intersection of a countable collection of dense open sets is dense.

Exercise 4. Prove this. Hint: Let the collection of dense open sets be {U_{ℓ}}_{ℓ=1}^{∞}. By replacing U_{ℓ} with the intersection U_{1} ∩ U_{2} ∩ ⋯ ∩ U_{ℓ} we can assume that U_{ℓ+1} ⊆ U_{ℓ} for all ℓ. Let B(a, r) be the open ball of radius r about a. Then to show that ⋂_{ℓ=1}^{∞} U_{ℓ} is dense, it is enough to show that it meets each B(a, r). As U_{1} is open and dense the set B(a, r) ∩ U_{1} is open and non-empty. So there is closed ball \overline{B}(a_{1}, r_{1}) ⊂ U_{1} ∩ B(a, r) and we can arrange that r_{1} ≤ 1. Likewise U_{2} ∩ B(a_{1}, r_{1}) is non-empty and open so there is a closed ball \overline{B}(a_{2}, r_{2}) ⊂ U_{2} ∩ B(a_{1}, r_{1}) and we can choose this so that r_{2} ≤ 1/2. Continuing in this manner we get a sequence \{\overline{B}(a_{ℓ}, r_{ℓ})\} with \overline{B}(a_{ℓ}, r_{ℓ}) ⊂ U_{ℓ} ∩ B(a_{ℓ−1}, r_{ℓ−1}) and r_{ℓ} ≤ 1/ℓ. Now show that \{a_{ℓ}\}_{ℓ=1}^{∞} is Cauchy and use completeness to show B(a, r) ∩ ⋂_{ℓ=1}^{∞} U_{ℓ} ⊇ ⋂_{ℓ=1}^{∞} \overline{B}(a_{ℓ}, r_{ℓ}) ≠ ∅. □

As the compliment of dense open set is a closed nowhere dense set and the compliment of an intersection is a union we can dualize the form of Baire’s theorem above.

4.2. Theorem (Baire Category Theorem Second Form). Let (X, d) be a complete metric space. Then the union of a countable collection of nowhere dense subsets of X has dense compliment in X. In particular X is not the a countable union of nowhere dense subsets.

Proof. Let {F_{ℓ}}_{ℓ=1}^{∞} be a countable collection of nowhere dense subsets of X. Then U_{ℓ} := X ∖ \overline{F}_{ℓ} is open and dense. Therefore X ∖ ⋃_{ℓ=1}^{∞} F_{ℓ} ⊇ X ∖ ⋃_{ℓ=1}^{∞} \overline{F}_{ℓ} = ⋂_{ℓ=1}^{∞} U_{ℓ} is dense. □

4.3. Definition. Let (X, d) be a metric space and A ⊆ X. Then A is meager iff A is contained in a countable union of closed nowhere dense sets. A set is comeager iff it is the compliment of a meager set. (Equivalently A is comeager iff it contains a countable intersection of dense open sets.) □

These definitions imply

4.4. Proposition. A countable union of meager sets is meager. A countable intersection of comeager sets is comeager. □

Note that if (X, d) is a complete metric space, no set can be both meager and comeager. For if A was such a set, then X ∖ A would also be meager and therefore X = A ∪ (X ∖ A) would be meager. But this contradicts Theorem 4.2 which implies that X is not a countable union of nowhere dense sets.

The next proposition is not important in applications of the Baire Theorem, but it does formalize, at least a bit, the idea that meager subsets of X are “small” and the comeager sets are “large”.

4.5. Proposition. Let (X, d) be a complete metric space. Let C be the set of all subsets of X that are either meager or comeager. Then C is a σ-algebra and if μ: C → R is defined by

μ(A) = \begin{cases}0, & if A is meager; \\ 1, & if A is comeager. \end{cases}

then μ is a measure on C.

Exercise 5. Prove this. Hint: To show countably additivity of μ note that any two comeager sets intersect non-trivially, so if {A_{ℓ}}_{ℓ=1}^{∞} is a pairwise disjoint sequence from C then at most one of the A_{ℓ}’s is comeager. Therefore ∑_{ℓ=1}^{∞} μ(A_{ℓ}) is 0 if all the A_{ℓ}’s are meager, and is 1 if one of the A_{ℓ}’s is comeager. □

Motivated by Proposition 4.5 if P (x) is a property of points of X so that {x ∈ X : P (x)} is comeager, then is often said that “P (x) holds for almost all x ∈ X in the sense of category”. A more common terminology is that “the generic point x ∈ X has property P (x)”. In this setting “generic” means “holds on a comeager set”. For example the generic real number is irrational.

5. Proof of Theorem 1

We will prove the dual of theorem. Let K_{U} be as in the statement of Proposition 3.4. That is K_{U} is the collection of A ∈ K so that U ∩ (A ∪ Cut(A)) = ∅. Set

R := ⋃{K_{U} : U is a non-empty open subset of R^{n}}.

Then R is exactly the set of all A so that both A and Cut(A) are disjoint from some nonempty open set. That is R = K ∖ D. Therefore Theorem 1 can be restated as

5.1. Theorem. The set R is a countable union of closed nowhere dense subsets of K. (Thus by Theorem 4.2 R is meager in K and therefore D is comeager.)

Proof. Let B the collection of open balls B(a, r) in R^{n} where all the components of a and the number r are rational. This is a countable set and every open subset of R^{n} is a countable union of elements of B. By Proposition 3.4 the set K_{B} is a closed nowhere dense subset of K and thus ⋃{K_{B} : B ∈ B} is a countable union of closed nowhere subsets of K.

To finish it is enough to show ⋃{K_{B} : B ∈ B} = R. Clearly ⋃{K_{B} : B ∈ B} ⊆ R. If A ∈ R, then there is a nonempty open subset U of R^{n} so that A ∈ K_{U}. There will be a nonempty open ball B ∈ B with B ⊂ U. But then A ∈ K_{B} and thus A ∈ ⋃{K_{B} : B ∈ B}. Therefore R ⊆ ⋃{K_{B} : B ∈ B}. □

6. The cut locus and regularity properties of ρ_{A}

6.1. Definition. Let U be an open subset of R^{n} and f: U → R^{n}. Then f is semi-concave iff every point of U has an open convex neighborhood V so that f|_{V} = h + φ where h is concave and φ is C^{∞}. □

6.2. Definition. Let U be an open subset of R^{n} and f: U → R^{n}. Then a function φ defined in an neighborhood of x_{0} ∈ U is an upper support function for f at x_{0} iff φ(x_{0}) = f(x_{0}) and f ≤ φ in a neighborhood of x_{0}. A lower support function for f at x_{0} is defined similarly. □

If φ is a C^{2} function with Hessian D^{2}φ (which we view as a symmetric bilinear form) then we say hat D^{2}φ(x_{0}) ≥ C iff D^{2}φ(x_{0})(v, v) ≥ C∥v∥^{2} for all vectors v. Likewise D^{2}φ(x_{0}) ≤ C iff D^{2}φ(x_{0})(v, v) ≤ C∥v∥^{2} for all vectors v.

6.3. Proposition. Let U ⊆ R^{n} be open and convex and let f: U → R be continuous and such that for each x_{0} ∈ U there is a C^{2} upper support function φ to f at x_{0} with D^{2}φ(x_{0}) ≤ C. Then the function f(x)− \frac{1}{2}C∥x∥^{2} is concave on U. (A function f satisfying the the hypothesis of this proposition is said to satisfy D^{2}f ≤ C in the sense of support functions.

Proof. (Taken form [1].) We first give the proof in the one dimensional case. Then U ⊆ R is an interval. Let φ be an upper support function to f at x_{0} that satisfies D^{2}φ = φ′′ ≤ C near x_{0} and let a = φ′(x_{0}). We claim f(x) ≤ f(x_{0}) + a(x − x_{0}) − (C/2)(x − x_{0})^{2}. Let g(x) := f(x_{0}) + a(x − x_{0}) − (C/2)(x − x_{0})^{2}. As φ(x_{0}) = g(x_{0}), φ′(x_{0}) = g′(x_{0}) and φ′′(x) ≤ C = g′′(x) we have an interval about x_{0} so that f(x) ≤ φ(x) ≤ g(x). Assume, toward a contradiction, there is an x_{1} so that f(x_{1}) − g(x_{1}) > 0. Then the function g_{1} := f − g will satisfy g′′_{1} ≤ 0 in the sense of support functions and g_{1}(x_{0}) = 0, g_{1}(x_{1}) > 0 and the function g_{1}(x) ≤ 0 for x near x_{0} so the function g_{1} will have an minimum at a point x_{∗} between x_{0} and x_{1}. Let g_{0} be the constant function g_{0}(x) = v_{1}(x_{∗}). Then g_{1} ≥ g_{0}, g_{1}(x_{∗}) − g_{0}(x_{∗}) = 0, and v′′_{1} ≤ 0 (in the sense of support functions) and g′′_{0} = 0 (in the strong sense) so the one variable case of of the linear maximum principle (which is easy to verify) implies g_{0}(x) = g_{1}(x) for x between x_{0} and x_{1}. As g_{1}(x_{0}) = 0 and g_{0} is constant this implies g_{1}(x) = g(x) − f(x) for all x between x_{0} and x_{1}. This in particular implies 0 = f(x_{1}) = g(x_{1}) which contradicts the assumption f(x_{1}) − g(x_{1}) > 0. Therefore f − g ≥ 0 on all of U. This implies f(x)−(C/2)∥x∥^{2} has a linear upper support function on U at x_{0}. As x_{0} was any point of U we have that f(x) − (C/2)∥x∥^{2} is concave. This completes the proof in the one dimensional case.

We return to the general case. Let φ be a upper support function for f at x_{0} that satisfies D^{2}φ ≤ C near x_{0} and let a := Dφ(x_{0}). For any unit vector b ∈ R^{n} let f_{b}(t) = f(x_{0} + tb) − t⟨b, a⟩. Then a lower support ψ function to v at x_{0} + t_{0}b that satisfies D^{2}ψ ≤ C yields the lower support function ψ_{b}(t) := ψ(x_{0} + tb) to v_{b} at t_{0} that satisfies ψ′′_{b}(t) ≤ C near t_{0}. Thus f_{b} satisfies the one variable version of the result and so f_{b}(t) = f(x_{0} + tb) ≤ v(x_{0}) − t⟨b, a⟩ + (C/2)t^{2}. But as Ω is convex every point of Ω can be written as x = x_{0} + tb for some t and some unit vector and so the multidimensional case reduces to the one dimensional case and completes the proof. □

If f: R^{n} → R and df exists at x, then let ∇f(x) be the vector so that

df(x)(V) = ⟨∇f(x), V ⟩ for all vectors V .

That is ∇f is the usual gradient of f at x.

For the last proposition to be useful we need a good supply of support functions. In geometric problems this can often be done by using distance functions from points.

Exercise 6. Let a ∈ R^{n} and set

ρ_{a}(x) = ∥x − a∥.

Then the gradient and Hessian of ρ_{a} are given by

∇ρ_{a}(x) = \frac{x − a}{∥x − a∥}, D^{2}ρ_{a}(x)(v, v) = \frac{1}{∥x − a∥} (∥v∥^{2} − \frac{⟨x − a, v⟩^{2}}{∥x − a∥^{2}} )

and thus ρ_{a} satisfies the inequalities

(6.1)  0 ≤ D^{2}ρ_{a}(x) ≤ \frac{1}{∥x − a∥}.

This shows that D^{2}ρ_{a} is informally bounded above on any set that has positive distance from a. □

6.4. Theorem. For any compact set A ⊂ R^{n} the function ρ_{A} is semiconcave on U := R^{n} ∖ A.

Proof. Let B be an open ball with ρ_{A}|_{B} bounded below. Then for any x_{0} ∈ B there is an a_{0} ∈ A with ∥x_{0} − a_{0}∥ = ρ_{A}(x_{0}). Let φ(x) := ρ_{a_{0}} = ∥x − a_{0}∥. Then φ(x_{0}) = φ_{A}(x_{0}) and for x ∈ B we have

ρ_{A}(x) = inf{∥x − a∥ : a ∈ A} ≤ ∥x − a_{0}∥ = φ(x).

Therefore φ is an upper support function for ρ_{A} at x_{0}. Also φ is C^{∞} on B and as the distance of B from A is positive there are uniform bounds on the Hessian D^{2}φ(x) for x ∈ B (which only depend on the distance of B form A by the inequalities (6.1)). By Proposition 6.3 this implies that ρ_{A}(x) + \frac{1}{2}C∥x∥^{2} is concave on B. As every point of R^{n} ∖ A is in a ball of positive distance from A this shows that ρ_{A} is semi-concave. □

Differentiability of concave functions can be understood in terms of the super-differential at a point: The differentiable points are the points where the super-differential is just one point. We start with the definition.

6.5. Definition. Let f: U → R be a semi-concave function. Then the super-differential ∂f(x_{0}) of f at x_{0} is

∂f(x_{0}) := {dφ(x_{0}) : φ is a C^{2} upper support function to f at x_{0}}

where dφ(x_{0}) is the linear functional dφ(x_{0})v := \frac{d}{dt}φ(x_{0} + tv)|_{t=0}. □

Exercise 7. If f is concave the usual definition of ∂f(x_{0}) form convex analysis is

∂f(x_{0}) = {Λ : Λ is a linear funcional and f − Λ has a maximum at x_{0}}.

Show that for concave f this agrees with Definition 6.5. □

The following is a standard result from convex analysis.

6.6. Proposition. A semi-concave function f is differentiable at x_{0} if and only if the super-differential ∂f(x_{0}) is a singleton. If ∂f(x_{0}) = {Λ}, then the differential is df(x_{0}) = Λ. □

The following is due to Joe Fu.

6.7. Proposition (Fu [9, Lemma 4.2 pp. 1037–1038]). Let A ⊂ R^{n} be compact and let x_{0} ∈ R^{n} ∖ A and set

U_{A}(x_{0}) := \{\frac{1}{∥x_{0} − a∥}(x_{0} − a) : a ∈ A, ∥x_{0} − a∥ = ρ_{A}(x_{0})\} .

(That is U_{A}(x_{0}) is the set of unit tangent vectors to A-generators from A to x_{0}.) Then

∂ρ_{A}(x_{0}) = convex hull of {⟨·, u⟩ : u ∈ U_{A}(x_{0})}. □

For x ∈ R^{n} ∖ A set

N_{A}(x) = number of points in U_{A}(x).

N_{A}(x), which is a positive integer or ∞, is the multiplicity of A at x. It is just the number of A-generators connecting A to x.

Our result now combine our results to give a Euclidean version of a Lorentzian result of Beem and Królak.

6.8. Theorem (Beem and Królak [4]). The function ρ_{A} is differentiable at x ∈ R^{n} ∖ A if and only if N_{A}(x) = 1.

Proof. By Proposition 6.6, φ_{A} is differentiable at x if and only if ∂ρ_{A}(x) is a single point. By Proposition 6.7 ∂ρ_{A}(x) is the convex hull of U_{A}(x) and therefore ∂ρ_{A}(x) is a singleton if and only if N_{A}(x) = 1. □

6.9. Proposition (Beem and Królak [4]). Assume that ρ_{A} is differentiable on the open set U which is disjoint form A. Then the map x ↦ ∇ρ_{A}(x) is continuous.

Proof. It is a general fact about concave, and thus also semi-concave, functions that if they are differentiable on an open set, then they are C^{1} on the set. However we can give a direct proof in this case. Let x, x_{ℓ} ∈ U with lim_{ℓ→∞} x_{ℓ} = x. As ρ_{A} is differentiable on U we have N_{A}(x) = N_{A}(x_{ℓ}) = 1 by Theorem 6.8. Therefore there are unique a, a_{ℓ} ∈ A with ∥x − a∥ = ρ_{A}(x) and ∥x_{ℓ} − a_{ℓ}∥ = ρ_{A}(x_{ℓ}). As A is compact {a_{ℓ}}_{ℓ=1}^{∞} will have at least one cluster point. If b ∈ A is a cluster point of {a_{ℓ}}_{ℓ=1}^{∞}, then by going to a subsequence we have may assume a_{ℓ} → b. But then

∥x − b∥ = lim_{ℓ→∞} ∥x_{ℓ} − a_{ℓ}∥ = lim_{ℓ→∞} ρ_{A}(x_{ℓ}) = ρ_{A}(x).

As a ∈ A is the only point with ∥x − a∥ = ρ_{A}(x) this implies that b = a and therefore a is the only cluster point of {a_{ℓ}}_{ℓ=1}^{∞}. Thus lim_{ℓ→∞} a_{ℓ} = a. Now using Propositions 6.6 and 6.7 we have

lim_{ℓ→∞} ∇ρ_{A}(x_{ℓ}) = lim_{ℓ→∞} \frac{1}{∥x_{ℓ} − a_{ℓ}∥}(x_{ℓ} − a_{ℓ}) = \frac{1}{∥x − a∥}(x − a) = ∇ρ_{A}(x)

and therefore ∇ρ_{A} is continuous at x as claimed. □

6.10. Proposition. If ρ_{A} is differentiable on an open set U which is disjoint from A, then Cut(A) ∩ U = ∅. That is every point of U is an interior point of the unique generator that it is on.

Proof. Let x_{0} ∈ U and let t_{0} = ρ_{A}(x_{0}). As the vector field x ↦ ∇ρ_{A}(x) is continuous it follows form the Peano existence for ordinary differential equations [8, Thm 1.3 p. 7 and Sec. 1.5 pp. 15–19] that

ċ(t) = ∇ρ_{A}(c(t)), c(t_{0}) = x_{0}

will have a solution on some interval (t_{0} − ε, t_{0} + ε). As we only know that x ↦ ∇ρ_{A}(x) is continuous, we do not know, yet, that this solution is unique, only that at least one solution exists. However when ∇ρ_{A}(x) exists it is given by ∇ρ_{A}(x) = ∥x − a∥^{−1}(x − a) for the unique a ∈ A with ∥x − a∥ = ρ_{A}(x) and so it is a unit vector. Therefore c is unit speed curve.

However

\frac{d}{dt}ρ_{A}(c(t)) = ⟨∇ρ_{A}(c(t)), ċ(t)⟩ = ⟨∇ρ_{A}(c(t)), ∇ρ_{A}(c(t))⟩ = 1

as ∇ρ_{A} is a unit vector when it exists. This implies that on (t_{0} − ε, t_{0} + ε)

ρ_{A}(c(t)) = ρ_{A}(c(t_{0})) + (t − t_{0}) = ρ_{A}(x_{0}) + (t − t_{0}) = t.

This implies that c is an A-minimizing segment. As x_{0} is in the interior of this segment, when the segment is extended to an A-minimizing x_{0} is not an end point of the generator. Therefore x_{0} is not a cut point of A. As x_{0} as any point of U this shows that Cut(A) ∩ U = ∅. That any x ∈ U is only one one A-generator now follows from Proposition 3.3. □

The “irregularity” of a point of Cut(A) can be measured by the number of generators it is on. Set

Cut^{[k]}(A) = {x ∈ Cut(A) : dim convex hull(U_{A}(x)) ≥ k}.

It will be seen that dim convex hull(U_{A}(x)) is a better measure of the size if the set of generators throw x than just N_{A}(x).

6.11. Proposition. For k ≥ 1 we have

{x ∈ Cut(A) : N_{A}(x) ≥ k} ⊆ Cut^{[k]}(A).

For small values of k this can be improved:

{x ∈ Cut(A) : N_{A}(x) ≥ k} = Cut^{[k]}(A)  for  1 ≤ k ≤ 3.

Exercise 8. Prove this. □

The set Cut^{[2]}(A) of points that are on two or more A-generators is often called the strict cut locus. Note that the result of Beem-Królak Theorem 6.8 implies that the Cut^{[2]}(A) is exactly the set of points x ∈ R^{n} ∖ A where ρ_{A} is not differentiable.

6.12. Proposition. The strict cut locus Cut^{[2]}(A) of A is dense in the cut locus Cut(A). Therefore for any open set U we have that Cut(A) ∩ U ≠ ∅ if and only if U ∩ {x : dρ_{A}(x) does not exist} ≠ ∅.

Proof. If Cut^{[2]}(A) is not dense in Cut(A) then there is an open set U, disjoint from A so that U ∩ Cut(A) ≠ ∅, but U ∩ Cut^{[2]}(A) = ∅. But then for all x ∈ U we have N_{(}x) = 1 and therefore ρ_{A} is differentiable on U by Theorem 6.8. But by Proposition 6.10 this implies U is disjoint from the cut locus, contradicting U ∩ Cut(A) ≠ ∅. □

This can be combined with Theorem 1 to give the following:

6.13. Theorem. Let

N := {A ∈ K : {x : dρ_{A}(x) does not exist} is dense in R^{n} ∖ A}.

Then, with the notation of Theorem 1, N = D and therefore N is a dense G_{δ} in K.

Exercise 9. Prove this as a corollary to Proposition 6.12. □

We can now refine Proposition 6.9 by increasing the regularity to C_{Loc}^{1,1}.

6.14. Theorem. Let A ∈ K and let U be an open set disjoint from A so that ρ_{A} is differentiable on U (which, by Proposition 6.12 is equivalent to Cut(A) ∩ U = ∅). Then ρ_{A} is locally a C^{1,1} function in U. (That is locally the gradient is a Lipschitz function).

Proof. Let a_{1} ∈ A and define φ_{1}(x) = ∥x − a_{1}∥. Then as in the proof of Theorem 6.4 we have

ρ_{A}(x) ≤ ∥x − a_{1}∥ = ρ_{1}(x)

for all x ∈ R^{n}. Let x_{0} ∈ R^{n} and let ρ_{0}(x) = ρ_{A}(x_{0}) − ∥x − x_{0}∥. The the inequality (2.2) implies ρ_{A}(x_{0}) ≤ ρ_{A}(x) + ∥x − x_{0}∥ and therefore

φ_{0}(x) = ρ_{A}(x_{0}) − ∥x − x_{0}∥ ≤ ρ_{A}(x).

We now make special chooses of a_{1} and x_{0}. Let c: [0, b] → R^{n} be an Aminimizing segment. Let a_{1} = c(0) ∈ A and x_{0} = c(b). Then for t ∈ (0, b) we have

ρ_{A}(c(t)) = t = ∥c(t) − c(0)∥ = ∥c(t) − a_{1}∥ = φ_{1}(c(t)),

and

ρ_{a}(c(t)) = t = b − (b − t) = ρ_{A}(c(b)) − ∥c(b) − c(t)∥
= ρ_{A}(x_{0}) − ∥c(t) − x_{0}∥ = φ_{0}(c(t)).

Thus for this choice of a_{1} and x_{0} the function φ_{0} is a lower support function and φ_{1} is an upper support function to ρ_{A} at c(t) whenever 0 < t < b. Let B be an open ball in U with dist(B, ∂U) = r > 0. Then for any x ∈ B there will be an A-minimizing segment c: [0, b] → R^{n} so that x = c(t) for some t and 0 < t, b − t < r (for the A-generator through x has no end point in U and therefore dist(B, ∂U) implies we can extend to at least a distance r past any point x = c(t) ∈ B). Let a_{1} = c(0) and x_{0} = c(b) and let φ_{0} be the support functions ρ_{A} at x = c(t) as above. By (6.1) there are bounds on the Hessian D^{2}φ_{0} and D^{2}φ_{1} hold on all of B (and in fact only depend on r). By [6, Prop 1.1 p. 7] this implies that ρ_{A}|_{B} is C^{1,1}. As U is the union of open balls that have positive distance from the boundary this shows that the restriction of ρ_{A} to U is C^{1,1}. □

References

1. L. Andersson, G. J. Galloway, and R. Howard, A strong maximum principle for weak solutions of quasi-linear elliptic equations with applications to Lorentzian and Riemannian geometry, Comm. Pure Appl. Math. 51 (1998), no. 6, 581–624.

2. R. Baire, Sur les fonctions de variables réelles, Annali Mat. pura e appl. 3 (1899), no. 3, 1–122.

3. S. Banach, über die Baire’sche Kategorie gewisser Funktionmengen, Studia Mathematica 3 (1931), 174–179.

4. J. K. Beem and A. Królak, Cauchy horizon end points and differentiability, J. Math. Phys. 39 (1998), no. 11, 6001–6010. MR 99h:83032

5. R. J. Budzyński, W. Kondracki, and A. Królak, On the differentiability of Cauchy horizons, J. Math. Phys. 40 (1999), no. 10, 5138–5142. MR 2000m:83083

6. L. A. Caffarelli and Cabrè, Fully nonlinear elliptic equations, American Mathematical Society Colloquium Publications, vol. 43, American Mathematical Society, Providence, Rhode Island, 1995.

7. P. T. Chruściel and G. J. Galloway, Horizons non-differentiable on a dense set, Comm. Math. Phys. 193 (1998), no. 2, 449–470.

8. E. A. Coddington and N. Levinson, Theory of ordinary differential equations, McGraw-Hill Book Company, Inc., New York-Toronto-London, 1955. MR 16,1022b

9. J. H. G. Fu, Tubular neighborhoods in Euclidean spaces, Duke Math. J. 52 (1985), no. 4, 1025–1046. MR 87f:57019

10. F. Hausdorff, Grundzüge der mengenlehre, Verlan von Veit, 1914.

11. J. C. Oxtoby, Measure and category. A survey of the analogies between topological and measure spaces, Springer-Verlag, New York, 1971, Graduate Texts in Mathematics, Vol. 2. MR 52 #14213

Department of Mathematics, University of South Carolina, Columbia, S.C. 29208, USA

E-mail address: howard@math.sc.edu