Let M be a smooth connected compact Riemannian manifold with no boundary,
of dimension at least 2. Pick a point x. For each direction and speed v at
x there is a geodesic t -> exp_x(t v) leaving x in that direction. For
small t the geodesic is the shortest path from x to exp_x(t v). For larger
t it need not be: it can stop being the shortest path, or it can hit a
conjugate point, where nearby geodesics fan back and focus.

A tangent vector v is called a minimizing velocity from x if the geodesic
t -> exp_x(t v), 0 <= t <= 1, is genuinely the shortest path from x to
exp_x(v). G_x denotes the set of all minimizing velocities at x.

The injectivity domain I(x) is the interior of G_x: the minimizing
velocities that survive a small backward stretch of the geodesic, so that
the geodesic is minimizing on [0, 1+eps] for some eps > 0. Equivalently,

  I(x) = {v in T_x M : there is a > 1 with d(x, exp_x(a v)) = a |v|_x}.

This is the precise definition used everywhere below. It is open, and G_x
is its closure. Both are subsets of the tangent space T_x M, which is just
ordinary Euclidean space of dimension n after choosing a basis, and that
is the point: the question concerns subsets of R^n.


A subset of R^n is convex if together with any two of its points it
contains the whole line segment between them. The question, raised by
Villani, is whether I(x) is always convex, for every x, under a curvature
condition.


The Hessian of the cost c(x,y) = d(x,y)^2/2, with respect to both
variables, measures how geodesics wiggle. The Ma-Trudinger-Wang tensor S
is one particular fourth derivative of c. The weak form of the condition,
called weak MTW or A3w, is

  S_(x,v)(xi, eta) >= 0  whenever  xi is perpendicular to eta.

pdf/trudinger-wang-2009.pdf

In optimal transport one moves a pile of
mass from one shape to another so that a cost (here, half the squared
distance) is minimized. Regularity theory of the transport map asks: is
the map smooth? The answer turned out to depend on this tensor S, in
directions perpendicular to the direction of transport. Weak MTW is the
borderline nonnegative case, and it is exactly the case where the smooth
theory is hardest.


  THEOREM (convexity of injectivity domains).
  If (M,g) is a compact connected Riemannian manifold without boundary,
  of dimension n >= 2, satisfying weak MTW, then for every x the sets
  I(x) and G_x are convex.

  THEOREM (global support).
  Under the same hypothesis, for every "potential" u (defined below in the potentials section)
  and every subgradient p of u at x, the vector p is a minimizing
  velocity, and the squared distance provides a global supporting
  inequality

    u(y) >= u(x) + c(x, exp_x p) - c(y, exp_x p)   for every y in M.

  Also, for every 0 < t < 1, the map sending (x,p) in the subgradient
  graph of u to exp_x(t p) is a homeomorphism of M onto M.

The global support theorem implies the convexity theorem almost
immediately. The whole difficulty is in the global support theorem, and
the whole difficulty there is controlling what happens when a geodesic
reaches the cut locus,
where the cost stops being smooth.


A minimizing geodesic can stop being minimizing for exactly two reasons,
and only these two:

  (i) an ordinary cut point: a second, different shortest geodesic
      arrives at the same endpoint;
  (ii) a conjugate point: the exponential map becomes singular, so the
      endpoint is a focus of the geodesic family.

Prior work (Loeper-Villani; Figalli-Rifford-Villani) treated the case
where minimizing geodesics reach the cut locus strictly before their
first conjugate point, i.e. where only obstruction (i) occurs. The point
of the present argument is to remove that restriction and let obstruction
(ii) happen too. That is what the conjugacy section does.

pdf/figalli-rifford-villani-2011.pdf


Weak MTW controls the Hessian of the cost in directions perpendicular to
the velocity. That is exactly enough to make the Hessian behave concavely
as the velocity slides along a straight line, and it is enough to kill
conjugacy in a segment whose endpoints are known to be nonconjugate. Everything then proceeds by continuation: start from very small
times where everything is obviously fine, push forward through the
subgradient graph of a potential, and show the projection cannot fail
before time 1. Failure would require either a conjugate point or a second
geodesic, and the conjugacy section rules out the first while a compactness-plus-covering
argument rules out the second.



A geodesic is a critical point of the length (equivalently, the energy)
functional. Whether it is a minimum is decided by the second derivative,
and the second derivative has a name: the index form. Every step is a statement about the index form. Build it once, carefully, and never re-derive it.


For a smooth curve alpha: [0,T] -> M define

  E(alpha) = (1/2) integral_0^T |alpha'(t)|^2 dt.

Cauchy-Schwarz says length(alpha)^2 <= 2 T E(alpha), with equality iff
|alpha'| is constant. Consequently, if gamma: [0,T] -> M has constant
speed and minimizes length among curves with the same endpoints, then it
also minimizes E among those curves. Indeed, for any competitor alpha,

  E(alpha) >= length(alpha)^2 / (2T)
            >= d(alpha(0),alpha(T))^2 / (2T)
            = E(gamma).



Let alpha(s,t) be a smooth two-parameter family of curves, and let
gamma(t) = alpha(0,t). Let Z(t) = d/ds alpha(0,t) be the variational
field. Suppose Z vanishes at both ends, Z(0) = Z(T) = 0 (varying only
in the interior, keeping endpoints fixed). Then

  d^2/ds^2 |_{s=0} E(alpha(s, .))
    = Q_gamma(Z,Z)

where

  Q_gamma(Z,Z) = integral_0^T ( |D_t Z|^2 - <R(Z, gamma')gamma', Z> ) dt,

and R is the Riemann curvature tensor. Convention: the Jacobi equation
will be D_t^2 J + R(J, gamma')gamma' = 0. If your convention for R is
opposite, flip the sign everywhere; the theorems are independent of the
convention as long as one uses it consistently.

Also needed is the polarized version of Q: for two fields X, Y on the same
geodesic, define

  Q_gamma(X,Y) = integral_0^T ( <D_t X, D_t Y>
                                 - <R(X, gamma')gamma', Y> ) dt,

so that Q_gamma(Z,Z) = Q_gamma(Z,Z). This is a symmetric bilinear form on
the space of piecewise smooth fields along gamma.


LEMMA (minimality, energy form). Let gamma: [0,T] -> M be a geodesic of
constant speed that minimizes length among curves with endpoints
gamma(0) and gamma(T). Then for every continuous piecewise smooth field
Z along gamma with Z(0) = Z(T) = 0,

  Q_gamma(Z,Z) >= 0.

PROOF. By the Cauchy-Schwarz bound just above, gamma minimizes the energy too. Pick a variation whose
variational field is Z; for instance, in a coordinate chart take
alpha(s,t) = exp^c_{gamma(t)} (s Z(t)) or any smooth interpolation. The
energy has a local minimum at s = 0, so its second derivative at s = 0 is
nonnegative, which is exactly Q_gamma(Z,Z) >= 0. For fields that are
only piecewise smooth, approximate by smooth fields and take a limit. []

Also needed is the converse-flavored statement, that equality in the
above forces Z to be a Jacobi field, and the exact statement of what a
Jacobi field is.


A field J along gamma satisfying

  D_t^2 J + R(J, gamma') gamma' = 0

is a Jacobi field. These are exactly the fields that arise as
variational vector fields of geodesic families: if the endpoints are
perturbed geodesically, the resulting Z is Jacobi.

The equation is a second-order linear ODE for the components of J. For
each choice of initial value J(0) and initial covariant derivative
D_t J(0), there is a unique Jacobi field on [0,T]; its components
depend smoothly on the initial data. That is the whole linear theory.


LEMMA (equality case). In the setting of the preceding minimality lemma, if Q_gamma(Z,Z) = 0, then
Z is a Jacobi field on [0,T].

PROOF. Take any other test field W along gamma with W(0) = W(T) = 0, and
consider the function f(s) = Q_gamma(Z + sW, Z + sW). Minimality of
gamma gives f(s) >= 0 for all s, and f(0) = Q_gamma(Z,Z) = 0. So s = 0
is a minimum of f, hence f'(0) = 0, i.e. Q_gamma(Z,W) = 0 for every W.

Integrate Q_gamma(Z,W) by parts along gamma. The boundary terms vanish
because W vanishes at both ends. What remains is

  0 = - integral_0^T <D_t^2 Z + R(Z, gamma')gamma', W> dt

for every W vanishing at the ends. Since W is arbitrary on the interior,
the bracket vanishes pointwise: D_t^2 Z + R(Z, gamma')gamma' = 0. That is
the Jacobi equation. If Z is only piecewise smooth, the integration by
parts produces extra boundary terms at the break points; these are also
arbitrary, and their vanishing forces D_t Z to be continuous at the break
points. So Z is Jacobi on the full interval. []


Recall exp_x: T_x M -> M sends a velocity w to the point a unit time
later of a geodesic starting at x with that velocity.

A velocity w is called conjugate at x if the differential of exp_x at w
is singular, i.e. d_w exp_x: T_x M -> T_{exp_x(w)} M is not invertible.
This definition is basis-free: pick any parallel orthonormal frame to
identify tangent spaces and check the determinant.

LEMMA (conjugacy equals a null Jacobi field). A velocity w is conjugate
at x if and only if the geodesic gamma(t) = exp_x(t w), 0 <= t <= 1,
carries a nonzero Jacobi field J with J(0) = J(1) = 0.

PROOF. Fix xi in T_x M. There is a unique Jacobi field J along gamma with
J(0) = 0 and D_t J(0) = xi: start from the geodesic variation
s -> gamma_xi(s) = exp_{exp_x(s xi')}(w') where xi' = xi and w' is the
parallel transport of w; after the fact, this shows

  d_w exp_x (xi) = J(1).

So d_w exp_x is singular iff there exists nonzero xi with J(1) = 0;
equivalently, a nonzero Jacobi field with J(0) = 0 and J(1) = 0. []

That equivalence reduces "conjugate" (a statement
about a derivative being non-invertible) to "some Jacobi field vanishes
at both ends" (a statement about ODEs).


Putting 2.3 and 2.6 together: if gamma: [0,1] -> M is a minimizing
geodesic, and some nonzero Jacobi field J along gamma has J(0) = J(1) =
0, then Q_gamma(J,J) = 0 by the Jacobi equation (integrate by parts),
so gamma is at the boundary of being a strict minimum: some direction of
variation has zero second variation. When this happens, the geodesic
fails to be uniquely minimizing under any perturbation that pushes one
endpoint out of phase.

This is the sense in which conjugate points hurt the argument. They are
a genuine obstruction and cannot be reasoned past by continuity alone;
that is what the conjugacy section will have to resolve.



The cost c(z,y) = d(z,y)^2/2 is smooth as long as the path stays inside the
injectivity domain (which is open). Once the geodesic hits a cut point, the cost stops
being smooth. The whole trick of the argument is to have a substitute
that is still smooth: around any nonconjugate velocity there is a
smooth "branch" of the exponential map's inverse, and Hessian of the
cost with respect to the source variable, taken inside that branch, is
called A_x(w). Proving the main theorem means tracking A_x(w)
as w slides from 0 out to the cut boundary. Three identities make it
tractable: the radial identity, the index-form formula, and the strict
radial comparison.


Consider the map

  Psi: TM -> M x M,  Psi(z,u) = (z, exp_z(u)).

Its differential at (x,w) has a simple shape: the second component is
d_w exp_z, so Psi is a local diffeomorphism at (x,w) exactly when w is
nonconjugate at x. So condition: assume w is nonconjugate at x. Then
there is an open neighborhood of (x,w) in TM on which Psi is a
diffeomorphism onto an open set in M x M, and write

  u = U(z, y)  when  y = exp_z(u) with (z,u) in that neighborhood.

Define the branch cost

  c_hat(z,y) = |U(z,y)|_z^2 / 2.

This is smooth on that neighborhood. Its value at (x, exp_x(w)) is
c_hat(x, exp_x w) = |w|_x^2 / 2. If w is in I(x), then on a smaller
neighborhood this branch agrees with the true cost c(z,y) = d(z,y)^2/2,
because the minimizing geodesic through (x,w) is unique in I(x).

DEFINITION (branch Hessian). For w nonconjugate at x, define

  A_x(w) = Hess_{zz} c_hat(z, y)|_{z=x, y=exp_x(w)},

a symmetric bilinear form on T_x M, obtained by differentiating c_hat
twice in z with y held fixed. Because Psi's inverse branches agree
wherever they overlap, A_x(w) depends smoothly on (x,w) throughout the
nonconjugate set.

The point of the definition: A_x(w) is defined and smooth even when w is
a cut point, provided w is merely nonconjugate. That is what lets us
continue the argument past ordinary cut points.

Convention A_x(0) = g_x, the metric at x. Justified in Lemma 3.3.


First-variation formula for c_hat. Let s -> z(s) be a smooth curve with
z(0) = x and z'(0) = xi, so that y = exp_x(w) is fixed. Let u(s) = U(z(s), y)
be the branch velocity, u(0) = w. Differentiating c_hat(z(s), y) at s = 0
gives

  d/ds c_hat(z(s), y)|_{s=0} = -<xi, w>_x.

So grad_z c_hat(x, y) = -w.

Now the radial identity. Consider sliding the source point along the
geodesic itself: z(tau) = exp_x(tau w), y fixed = exp_x(w). The branch
velocity from z(tau) to y is exactly (1-tau) times the derivative
gdot(tau) of the geodesic (because the short geodesic segment from
z(tau) in that direction reaches gamma(1) = y at time 1 with speed
|gdot|*(1-tau)). So u(tau) = (1-tau) gdot(tau), and

  -u(tau) = -(1-tau) gdot(tau).

Its covariant derivative in tau at tau = 0 is -gdot(0) = -w. Negating:

  A_x(w)(w, xi) = <w, xi>_x   for every xi.        (RADIAL IDENTITY)

Equivalently A_x(w)(w, .) = <w, .>_x. In particular, taking w itself,

  A_x(w)(w, w) = |w|_x^2.

This is used to pin the source Hessian's behavior in the radial
direction at every nonconjugate velocity.


LEMMA 3.3. Suppose w is nonconjugate at x. Let gamma(tau) = exp_x(tau w),
0 <= tau <= 1. Then for every xi in T_x M,

  A_x(w)(xi, xi) = min_{X: X(0) = xi, X(1) = 0} Q_gamma(X, X),

where Q_gamma is the index form, and the minimum is taken over
continuous piecewise smooth fields X along gamma. The minimum is attained
uniquely, by the Jacobi field with those endpoints. In particular
A_x(0) = g_x.

PROOF. Fix xi. Follow the geodesic starting at x with velocity xi; the
points exp_x(s xi) vary the base point along a geodesic, and the branch
velocity u(s) = U(exp_x(s xi), exp_x w) varies smoothly. The
corresponding variational field Y(tau) = d/ds at s = 0 of exp_{exp_x(s xi)}(tau * U(exp_x(s xi), y))
satisfies Y(0) = xi and Y(1) = 0: at tau = 0 the curve in s is the
geodesic through x with velocity xi, so Y(0) = xi; at tau = 1 the
endpoints y are the same for all s, so Y(1) = 0. Because the curves
exp_{exp_x(s xi)}(tau u(s)) are all geodesics in tau, Y is a Jacobi
field (Jacobi equation is exactly the linearized geodesic equation).

Differentiating the first-variation formula twice with respect to s:
first variation gives d/ds c_hat(exp_x(s xi), y) = -<xi(s), u(s)>, where
xi(s) = d/ds base point. Differentiating again in s at s = 0, the
tangential term drops because x is moving along a geodesic, so

  A_x(w)(xi, xi) = -<xi, D_tau Y(0)>_x.

Integration by parts along gamma turns the right side into Q_gamma(Y,Y),
since Y is a Jacobi field and Y(1)=0 removes the boundary contribution
at the far end (Y(0)=xi is the far-side boundary term). So
A_x(w)(xi,xi) = Q_gamma(Y,Y).

Now take any admissible field X. Put Z = X - Y. Then Z(0)=Z(1)=0.
Bilinearity and the Jacobi equation for Y give Q_gamma(Y, Z) = 0. And
gamma is a minimizing geodesic (since w is nonconjugate implies w is in
the closure of I(x) via Lemma 5.4 below; alternatively, first
restrict to w nonconjugate with w in I(x), then extend by continuity).
By Lemma 2.3, Q_gamma(Z,Z) >= 0. Hence

  Q_gamma(X,X) = Q_gamma(Y,Y) + Q_gamma(Z,Z) >= Q_gamma(Y,Y).

So Y minimizes. If equality holds, then Q_gamma(Z,Z) = 0, so by Lemma
2.5, Z is a Jacobi field vanishing at both ends, and nonconjugacy of w
forces Z = 0. So the minimum is unique. Finally at w = 0, gamma is the
constant geodesic, Y(tau) = (1 - tau) xi is the minimizing field, and
Q_gamma(Y,Y) = |xi|_x^2. So A_x(0)(xi,xi) = |xi|_x^2 for every xi,
i.e. A_x(0) = g_x. []

The index-form formula is the workhorse: it turns "the Hessian of a
smooth function at a point" into "a variational minimum", which lets us
minimize over test fields to obtain upper bounds.


LEMMA 3.4. Fix x, fix a in G_x (a minimizing velocity). For any
0 < s < s' < 1, the inequality

  A_x(s a) > (s/s') A_x(s' a)

holds as quadratic forms: A_x(s a) - (s/s') A_x(s' a) is positive
definite on T_x M.

PROOF. Time rescaling in Lemma 3.3. Along gamma(tau) = exp_x(tau a),
let Y_s and Y_{s'} be the minimizing Jacobi fields on [0,s] and [0,s']
respectively, for arbitrary xi at 0 and value 0 at s or s'. Scaling tau
back to a common interval gives

  (1/s) A_x(s a)(xi,xi) = min_{X(0)=xi, X(s)=0} Q_{[0,s]}(X,X),
  (1/s') A_x(s' a)(xi,xi) = min_{X(0)=xi, X(s')=0} Q_{[0,s']}(X,X).

Extend the s-side minimizer Y_s by zero to [0,s']. Its index-form value
is unchanged, so the right side of the second line is at most the score
of the first line. Suppose equality. Then the extension is itself a
minimizer for the second minimum, so by Lemma 2.5 (applied on [0,s']) it
is a Jacobi field. But it vanishes on (s, s'), so it is a Jacobi field
that is zero on an open interval; a Jacobi field with a single interior
zero interval must be identically zero, contradicting xi != 0. Therefore
the inequality is strict: (1/s) A_x(s a)(xi,xi) > (1/s') A_x(s' a)(xi,xi)
for every nonzero xi, which is the claim. []

For a = 0 the same argument gives the difference explicitly as
(1 - s/s') g_x, again positive definite.


Because each branch of U (and hence c_hat and A_x(w)) is smooth on an
open set in TM x M, and because these branches agree where they overlap,
A_x(w) depends smoothly on (x,w) throughout the nonconjugate set. In
particular, if nonconjugate velocities w_j -> w with w nonconjugate,
then A_x(w_j) -> A_x(w) as symmetric forms. This lets us take limits at
the edge of I(x) without losing control of A.

Also, on any compact subset of the nonconjugate set with |w| bounded
(say |w| <= diam(M)), the symmetric forms A_x(w) and their derivatives
in (x,w) are uniformly bounded. This is used repeatedly for compactness.




Weak MTW is a curvature inequality in a fourth derivative of c. Its
only consequence used is this: fix a test
direction xi and slide the velocity w along a straight line in T_x M
pointing in a direction eta perpendicular to xi, then the branch
Hessian A_x(w)(xi,xi) is concave in the sliding parameter. That is
exactly the statement that turns a local curvature condition into a
usable inequality.


For x in M, v in I(x), and xi, eta in T_x M define

  S_(x,v)(xi,eta)
    = -(3/2) * d^4/(ds^2 dt^2) [ c(exp_x(t xi), exp_x(v + s eta)) ] |_{0}.

This is standard MTW curvature. It is symmetric in xi, and symmetric
bilinear in xi alone and eta alone; the pairing between the xi-slot and
the eta-slot is the structural content of the tensor.

WEAK MTW (also called A3w). For every x, every v in I(x), and every
pair xi, eta of tangent vectors at x with <xi, eta>_x = 0:

  S_(x,v)(xi, eta) >= 0.

Nothing else is assumed: not strict positivity, not nonconjugacy, not
convexity of I(x). This is the entire hypothesis.


LEMMA 4.2. Fix x in M, b_0 in I(x), and eta in T_xM. Let
b_t = b_0 + t eta and suppose b_t is in I(x) for t in an open interval
around some t_0. Let xi be perpendicular to eta. Then

  d^2/dt^2 [ A_x(b_t)(xi, xi) ] |_{t = t_0}
    = -(2/3) S_(x, b_{t_0})(xi, eta).

In particular t -> A_x(b_t)(xi,xi) is concave on that interval.

PROOF. For b_t in I(x), the branch cost c_hat coincides with
the true cost c in a neighborhood of (x, exp_x(b_t)). So

  A_x(b_t)(xi, xi) = d^2/ds^2 c(exp_x(s xi), exp_x(b_t)) |_{s = 0}.

Differentiate twice in t. Because exp_x(b_0 + t eta) is a geodesic
starting at x in direction eta, and exp_x(s xi) is a geodesic starting
at x in direction xi, the mixed fourth derivative at s = t = 0 is
exactly S_(x,b_0)(xi,eta) (with the roles of s and t swapped in the
definition). So

  d^2/dt^2 A_x(b_t)(xi,xi) = -(2/3) S_(x,b_0)(xi,eta).

Weak MTW says S_(x,b_0)(xi,eta) >= 0, so the second derivative is
nonpositive: concavity. By smooth dependence of A on (x,w) (3.5), the
same identity holds at every t_0 in the interval, not just t_0 = 0. []


LEMMA 4.3 (transverse concavity, finite Jensen form). Let
b_1, ..., b_m be in T_xM and theta_i >= 0 with sum_i theta_i = 1. Set
b = sum_i theta_i b_i. Suppose the whole convex hull of {b_1,...,b_m}
is contained in I(x). Let xi be perpendicular (at x) to the linear span
E = span of {b_i - b_j : i,j}. Then

  A_x(b)(xi,xi) >= sum_i theta_i A_x(b_i)(xi,xi).

PROOF. Two-term case first. Let b_t = (1-t) b_1 + t b_2 and note
b_t in I(x) for 0 <= t <= 1 (hypothesis). Concavity of A_x(b_t)(xi,xi)
in t (Lemma 4.2, with eta = b_2 - b_1 and xi perpendicular to eta by
hypothesis) gives, at t = theta_2 and using theta_1 = 1 - theta_2,

  A_x(b)(xi,xi) >= theta_1 A_x(b_1)(xi,xi) + theta_2 A_x(b_2)(xi,xi).

General case by induction on the number of positive weights. Let
theta_k > 0 and put b' = sum_{i<k} (theta_i/(1-theta_k)) b_i, which is
in the convex hull of b_1,...,b_{k-1} and hence of I(x). By induction,

  A_x(b')(xi,xi) >= sum_{i<k} (theta_i/(1-theta_k)) A_x(b_i)(xi,xi).

Now apply the two-term case to the pair (b', b_k), whose convex
combination with weights (1-theta_k, theta_k) is exactly b. That gives

  A_x(b)(xi,xi) >= (1-theta_k) A_x(b')(xi,xi) + theta_k A_x(b_k)(xi,xi),

and combining the two inequalities proves the claim. []

Note that the hypothesis "xi perpendicular to E" is automatically
satisfied whenever xi is perpendicular to some single p and b_i - p in
E for every i, because xi then annihilates E.


Sometimes only the scaled hull r b_i (0 < r < t) is known to lie in
I(x), and each b_i is a nonconjugate minimizing velocity at x. Passing
to a limit r -> t in Lemma 4.3 goes through because each A_x(r b_i)
converges as r approaches t (smoothness of A_x, validity of A_x(b_i) via
branch extension at nonconjugate cut points). So the Jensen inequality
still holds at the limit:

  A_x(t p)(xi,xi) >= sum_i theta_i A_x(t b_i)(xi,xi)

whenever the limiting forms exist. This version is used (with the
same hypotheses on E and xi).



Existence of minimizing geodesics on a compact manifold gives: for
every (x, y) there is at least one w with exp_x(w) = y and |w|_x = d(x,y).
Define

  L_x(y) = {w in T_x M : exp_x(w) = y, |w|_x = d(x,y)}   (nonempty)
  G_x    = {w in T_x M : w in L_x(exp_x w)}
         = {w in T_x M : d(x, exp_x w) = |w|_x}
  C      = {(x,w) in TM : w in G_x}
  I      = {(x,w) in TM : w in I(x)}    (the total injectivity set)

PROPOSITION 5.1. (a) G_x is closed in T_x M and bounded by D = diam(M);
so G_x is compact. (b) C = union over x of {(x,w) : w in G_x} is closed
and bounded; so C is compact. (c) I is open in TM. (d) The zero section
{(x,0) : x in M} is contained in I and is compact; consequently there
is rho > 0 such that |w|_x < rho for every x implies w in I(x).

PROOF. (a) d is continuous, exp is continuous, w -> |w|_x is continuous;
so {w : d(x, exp_x w) = |w|_x} is closed. Bound: for w in G_x,
|w|_x = d(x, exp_x w) <= D. Ball of radius D is compact. (b) Same
argument varying x; T_x M varies continuously with x, so C is closed
in TM; |w|_x <= D makes C bounded; being closed and bounded in the
compact manifold TM's unit disk bundle, C is compact. (c) shown in
Lemma 5.4 below. (d) Trivial: 0 in I(x) by the definition I(x) = {v :
there is a > 1 with d(x, exp_x(a v)) = a |v|_x}. The zero section is
compact and I is open, so there is a uniform rho. []


LEMMA 5.2. For every x in M:

  I(x) is contained in G_x,  and  r G_x is contained in I(x) for every
  0 <= r < 1.

PROOF. First inclusion: if w is in I(x), there is a > 1 with
d(x, exp_x(a w)) = a |w|_x. The geodesic from x with velocity w reaches
exp_x w at time 1, at distance |w|_x by the same equality (the geodesic
is a straight-line shortcut: |w|_x = d(x, exp_x w) because if not, the
path from x to exp_x(a w) would be longer than a |w|_x). So
w in G_x.

Second inclusion: fix w in G_x, r in [0,1). The curve
gamma_r(t) = exp_x(t r w), 0 <= t <= 1/r, is the geodesic starting at x
with velocity r w. It is the same as the geodesic exp_x(t w) rescaled
by r. Because the original geodesic exp_x(t w) is minimizing on [0,1],
its scaled version exp_x(t r w) is minimizing on [0, 1/r] (lengths and
distances scale by r: d(x, exp_x(r w)) = r d(x, exp_x w) = r |w|_x, and
similarly at each scaled time). Since 1/r > 1, this is exactly the
condition for r w to be in I(x). For r = 0, w = 0, and the constant
geodesic works for any a > 1. []


LEMMA 5.3 (interior characterization). For any x in M and w in T_x M:

  w in I(x)  iff  w is the unique velocity in L_x(exp_x w) and w is
                  nonconjugate at x.

PROOF.

(=>) Suppose w in I(x). Fix T > 1 with gamma|[0,T] minimizing, gamma(t)
= exp_x(t w). Write y = gamma(1) = exp_x w and z = gamma(T).

Uniqueness. Suppose w' in L_x(y) with w' != w. Then the concatenation of
gamma_{w'} on [0,1] with gamma_gamma'(1) on [1,T] is a curve from x to z
of length |w'| + (T-1)|w| = d(x,y) + d(y,z) = d(x,z). So the
concatenation is also minimizing, and therefore has no corner at y,
which forces w' = w. Contradiction.

Nonconjugacy. Suppose w is conjugate at x. By Lemma 2.6, there is a
nonzero Jacobi field J along gamma|[0,1] with J(0) = J(1) = 0. Extend J
by zero to [0,T]. The extended field is admissible for the index form
Q_gamma on [0,T]. Its index-form value is zero (the zero extension
contributes nothing). Since gamma|[0,T] minimizes, Lemma 2.3 says
Q_gamma(J_ext, J_ext) >= 0; but Q_gamma(J, J) = 0 by Lemma 2.5 (J is
Jacobi) so the value is 0. So equality holds for the extended field, and
Lemma 2.5 forces J_ext to be a Jacobi field on [0,T]. But J_ext vanishes
on (1, T), and a Jacobi field vanishing on an open interval is
identically zero on [0,T]. Then J = 0 on [0,1], contradicting J != 0.

(<=) Suppose w is the unique velocity in L_x(exp_x w) and is
nonconjugate at x. This places w in I(x).

Step 1: the set D of unique-minimizing velocities is open in TM.
  Define D = {(z,u) in TM : u in L_z(exp_z u) and L_z(exp_z u) = {u}}.
  Fix (z_0, u_0) in D and suppose D does not contain a neighborhood of
  (z_0, u_0). Then there are (z_j, u_j) -> (z_0, u_0) with
  (z_j, u_j) not in D. For each j, pick a minimizing velocity u_j' in
  L_{z_j}(exp_{z_j}(u_j)); this exists by Proposition 5.1. The total minimizing set
  C is compact (5.1(b)), so along a subsequence u_j' -> u'. Then u' is a
  minimizing velocity from z_0 to exp_{z_0}(u_0) = exp_z_0(u_0): the
  constraint d(z_j, exp_{z_j}(u_j')) = |u_j'|_{z_j} passes to the limit.
  Uniqueness forces u' = u_0. Hence both u_j and u_j' approach u_0, and
  both are minimizing velocities from z_j to y_j = exp_{z_j}(u_j). But
  w = u_0 is nonconjugate at z_0, so by the exponential pair
  map Psi is a local diffeomorphism at (z_0, u_0); for large j, Psi is
  invertible near (z_j, u_j) and (z_j, u_j'), and both approximate the
  inverse branch value at (z_j, y_j). So u_j = u_j'. Hence (z_j, u_j)
  is in D, contradiction. So D is open.

Step 2: a small forward radial change remains in D. Since w in D and D
  is open, and w in T_x M is a point of TM, the point a w in TM is in D
  for all a > 1 sufficiently close to 1. Also w is nonconjugate and
  nonconjugacy is an open condition (d_w exp_x invertible persists in a
  neighborhood). So a w is uniquely minimizing and nonconjugate for such
  a.

Step 3: a w in D corresponds to d(x, exp_x(a w)) = a |w|_x. Combination
  with Step 2 gives w in I(x) by the definition of I(x). []


COROLLARY 5.4. (a) G_x = closure of I(x). (b) I(x) is its own interior:
  I(x) is open in T_x M. (c) For w in I(x), the true cost c agrees with
  the branch cost c_hat on a neighborhood of (x, exp_x(w)); in
  particular c is smooth near (x, exp_x(w)) and I(x) is an open set on
  which the equivalence of A_x(w) and Hess c holds.

PROOF. (a) I(x) subset G_x by Lemma 5.2. Conversely, r G_x subset I(x)
for every 0 <= r < 1, so closure(I(x)) contains G_x. Since G_x is
closed (Prop 5.1(a)) and contains I(x), closure(I(x)) is contained in
G_x. Together: equality. (b) I(x) is open in the total set I (Prop
5.1(c)), and the total set I is open in TM; a slice at fixed base point
is open. (c) Apply Lemma 5.3: w in I(x) implies w is the unique
minimizing velocity near (x, exp_x(w)), so on a small neighborhood the
branch velocity U(z,y) is the true minimizing velocity. The true cost
equals |U(z,y)|_z^2/2 there. The branch cost is exactly that; smooth by
3.1. []


For any x, G_x is compact and convex (convexity proved later, at
Corollary 8.6). I(x) is its open interior. The total minimizing set C is
compact in TM. The characterization 5.3 is: w in I(x) iff w is unique
minimizing to exp_x(w) and nonconjugate. In practice the
contrapositive is used: to keep velocities in I(x), simultaneously control
"no competitor geodesic" and "no conjugate time".
The continuation below will produce, at every step, a finite set of
velocities a_1, ..., a_m that are known to be minimizing; and it will
ask whether some velocity in the convex hull co{a_1,...,a_m} is
conjugate, which would obstruct the argument. This part proves a clean
fact: if the two ends of a segment in T_x M are nonconjugate minimizing
velocities, then every velocity on that segment is nonconjugate. By
induction on the number of vertices (Corollary 6.7), every velocity in
the hull is nonconjugate. Conjugate points never occur inside these
hulls.


PROPOSITION 6.1. Let b_0, b_1 in T_x M be nonconjugate velocities with
[b_0, b_1] = {(1-t) b_0 + t b_1 : 0 <= t <= 1} contained in G_x. Then
every velocity in [b_0, b_1] is nonconjugate.

PROOF. If b_0 = b_1 there is nothing to prove. Otherwise, suppose there
is a conjugate velocity z in the open segment (b_0, b_1). Write

  b_t = z + t e,  t in [-l_0, l_1],  |e|_x = 1,  l_0, l_1 > 0,

so b_0 = z - l_0 e and b_1 = z + l_1 e. Because z is strictly inside
the segment, both l_0, l_1 are positive. The velocity z is nonzero,
since z = 0 would have d_0 exp_x = Id invertible, contradicting
conjugacy.

For every 0 < r < 1 the contracted segment S_r = {r b_t :
-l_0 <= t <= l_1} is contained in I(x). This is Lemma 5.2:
each r b_t = r * (a point of G_x) is in r G_x, and r G_x is contained
in I(x). So all r b_t, 0 < r < 1, are in I(x), hence smooth.


Since z is conjugate at x, Lemma 2.6 provides a nonzero Jacobi field
J_z along gamma_{x,z}(tau) = exp_x(tau z), 0 <= tau <= 1, with
J_z(0) = 0 and J_z(1) = 0. Write k = D_tau J_z(0) in T_x M; by
uniqueness of the Jacobi field for given initial data, k != 0 (J_z is
nonzero and vanishes at 0, so its derivative at 0 is nonzero).

LEMMA 6.2. <k, z>_x = 0.

PROOF. For a Jacobi field J along a geodesic gamma, the function
tau -> <J(tau), gamma'(tau)>_x is affine in tau. Indeed,
  d^2/dtau^2 <J, gamma'> = <D_tau^2 J, gamma'> + 2 <D_tau J, D_tau gamma'>
                            + <J, D_tau^2 gamma'>,
and D_tau^2 gamma' = 0 (geodesic), D_tau^2 J = -R(J, gamma')gamma' (Jacobi),
so the first term is -<R(J, gamma')gamma', gamma'> = 0 by antisymmetry of
R in the (J, gamma') slots. So <J, gamma'> is affine.

Applying this to J_z: <J_z(0), gamma'(0)> = 0 and <J_z(1), gamma'(1)> = 0.
Affine with two roots implies identically zero. Differentiating at 0:
<D_tau J_z(0), gamma'(0)> = <k, z>_x = 0. []


Let xi in T_x M be any vector with <xi, k>_x != 0. Such an xi exists
since k != 0. (Later the construction is applied with xi = e once k
has been shown parallel to e; for now xi is general.)

For a velocity a in T_x M near z, both fixed and chosen so that a
remains nonconjugate, define

  T_a(tau)  parallel transport from x to gamma_{x,a}(tau) along gamma_{x,a}
  j(tau)    = T_z(tau)^{-1} J_z(tau)     (fixed vector field along x)
  J_a(tau)  = T_a(tau) j(tau)
  E_a(tau)  = (1 - tau) T_a(tau) xi.

Here j is a fixed curve in T_x M; only T_a varies with a. Both J_a and
E_a are continuous piecewise smooth along gamma_{x,a}. Directly:

  J_a(0) = T_a(0) j(0) = j(0) = J_z(0) = 0,
  J_a(1) = T_a(1) j(1) = T_a(1) T_z(1)^{-1} J_z(1) = 0,
  E_a(0) = xi,   E_a(1) = 0,
  J_a is nonzero (j is nonzero, parallel transport is invertible).

Write Q_a = Q_{gamma_{x,a}} for the index form on [0,1], and
define

  P(a) = Q_a(J_a, J_a).

This is a smooth function of a in a full neighborhood of z, and:

  (i)  P(z) = 0. Indeed, Q_z(J_z, J_z) = 0 for any Jacobi field J_z with
       J_z(0) = J_z(1) = 0: the boundary terms in the integration by
       parts both vanish.
  (ii) P(a) >= 0 for every a in G_x. By Lemma 2.3, minimizing geodesics
       have nonnegative index form.
  (iii) P(a) > 0 for every a in I(x). If P(a) = 0, Lemma 2.5 says J_a
       is Jacobi; but J_a is a nonzero Jacobi field vanishing at both
       ends, so a is conjugate, contradicting (a in I(x)) => (a is
       nonconjugate, Lemma 5.3).

One more identity, at a = z. Because J_z is Jacobi and E_z(1) = 0,
E_z(0) = xi, integration by parts gives

  Q_z(E_z, J_z) = [<E_z, D_tau J_z>_x]_0^1 = -<xi, k>_x.

By the choice of xi this is nonzero. Call this constant c_1 = |<xi,k>| > 0.

Now use the index-form minimum for A_x(a). For a in I(x), Lemma 3.3 says

  A_x(a)(xi, xi) = min over X with X(0) = xi, X(1) = 0 of Q_a(X, X).

The particular field X = E_a + lambda J_a is admissible: X(0) = E_a(0) +
lambda J_a(0) = xi, X(1) = E_a(1) + lambda J_a(1) = 0. So Q_a(X, X) bounds
A_x(a)(xi,xi) from above. Compute

  Q_a(E_a + lambda J_a, E_a + lambda J_a) = Q_a(E_a,E_a)
                                            + 2 lambda Q_a(E_a, J_a)
                                            + lambda^2 P(a).

Minimize over lambda in R (P(a) > 0). The minimum is at lambda = -Q_a(E_a, J_a)/P(a),
with value

  Q_a(E_a, E_a) - Q_a(E_a, J_a)^2 / P(a).

So for a in I(x) close enough to z that smooth dependence applies:

  A_x(a)(xi, xi) <= Q_a(E_a, E_a) - Q_a(E_a, J_a)^2 / P(a).   (6.a)

On a small compact neighborhood U of z, the quantities Q_a(E_a, E_a) and
|Q_a(E_a, J_a)| are uniformly bounded, and |Q_a(E_a, J_a)| is uniformly
bounded below by, say, c_1/2 > 0 (by smoothness, since it is c_1 at a=z).
So there are constants C_0 >= 0 and c_0 > 0 such that for all a in U
intersected with I(x),

  A_x(a)(xi, xi) <= C_0 - c_0 / P(a).      (TRIAL UPPER BOUND)


For each xi perpendicular to e, transverse concavity (Lemma 4.3) on
the contracted segment {r b_t : -l_0 <= t <= l_1} subset I(x), with
the axis direction e perpendicular to xi, gives

  A_x(r z)(xi, xi)
    >= (l_1/(l_0+l_1)) A_x(r b_0)(xi, xi)
     + (l_0/(l_0+l_1)) A_x(r b_1)(xi, xi).

Indeed, r z = (l_1/(l_0+l_1)) r b_0 + (l_0/(l_0+l_1)) r b_1 is a convex
combination with positive weights, and every segment direction r b_t -
r b_s is a multiple of e, which is perpendicular to xi.

Both b_0 and b_1 are nonconjugate, so the maps r -> A_x(r b_0) and
r -> A_x(r b_1) extend smoothly to r = 1 (by branch extension).
Hence the right-hand side is bounded below by a constant independent of
r (as long as r ranges over, say, [1/2, 1)).

The left-hand side, however, is bounded above by the trial upper bound
the trial upper bound, which reads A_x(r z)(xi, xi) <= C_0 - c_0/P(r z). As
r -> 1, P(r z) -> P(z) = 0 by smoothness of P (a is smooth, and rz -> z
from inside I(x)). So the right side of that inequality tends to
-infinity. A lower bound and an upper bound tending to -infinity
cannot both hold unless the constant c_0 = 0. But c_0 > 0 was chosen
from |<xi, k>| > 0. So <xi, k> = 0 for every xi perpendicular to e.

Hence every vector k in ker d_z exp_x is orthogonal to e^perp. In a
Hilbert space, (e^perp)^perp = span{e}, so ker d_z exp_x is contained
in span{e}. Since z is conjugate, the kernel is nontrivial, so it must
equal span{e}. In particular e belongs to the kernel: there is a
nonzero Jacobi field J_e along gamma_{x,z} with J_e(0) = J_e(1) = 0 and
D_tau J_e(0) = e. Then Lemma 6.2 applied to J_e gives <e, z>_x = 0.


From now on fix xi = e. This is allowed because <e, k> != 0 (in fact
= |e|^2 = 1). Re-run the trial-field construction with this
choice; the bound reads

  A_x(a)(e, e) <= C_0 - c_0/P(a),    P(a) = Q_a(J_a, J_a),

with J_a constructed from the Jacobi field J_e (which has
D_tau J_e(0) = e). Same constants as before; possibly adjusted.

Now take the specific path a(t) = z + t e for small |t|. Because the
whole segment b_t = z + t e, t in [-l_0, l_1], is contained in G_x,
P(z + t e) >= 0 for every such t (the index form is nonnegative
on minimizing geodesics). Also P(z) = 0. Thus the smooth function
t -> P(z + t e) has a local minimum of value 0 at t = 0. Its first
derivative vanishes at 0, and by Taylor's theorem there are delta > 0
and a constant C_3 > 0 with

  0 <= P(z + t e) <= C_3 t^2,    |t| < delta.

Shrink delta further so that z + t e and all r(z + t e), r in
[1 - delta, 1), lie in the compact neighborhood U from the trial-field construction. Also let L
be a Lipschitz constant for P on a slightly larger ball, and K an
upper bound for |z + t e|_x, |t| < delta. Then

  P(r(z + t e)) <= P(z + t e) + L |r(z + t e) - (z + t e)|
                 <= C_3 t^2 + L K (1 - r)
                 <= C_4 (t^2 + 1 - r)

for constants C_4 > 0 and all |t| < delta and r in [1 - delta, 1).
Indeed |r(z+te) - (z+te)| = (1-r)|z+te|.

Substituting into the trial upper bound at a = r(z + t e):

  A_x(r(z + t e))(e, e)
    <= C_0 - c_0 / P(r(z + t e))
    <= C_0 - c_0 / (C_4 (t^2 + 1 - r))
    = C_1 - c_1 / (t^2 + 1 - r),                 (SINGULAR UPPER)

with new constants C_1 >= 0, c_1 > 0. The bounds hold simultaneously for
all t with |t| < delta and r in [1 - delta, 1), no matter how the pair
(t, r) tends to (0, 1). That "no matter how" is exactly what is needed
for the final contradiction.


Define B_x(a) = g_x - A_x(a), a symmetric bilinear form on T_x M, an
auxiliary object designed so that the RADIAL IDENTITY becomes
a null condition. Indeed, A_x(a)(a, .) = <a, .>_x implies

  B_x(a)(a, v) = <a, v>_x - <a, v>_x = 0  for every v,

so in particular B_x(a)(a, a) = 0. This is used twice below.

For 0 < r < 1 define

  f_r(t) = B_x(r (z + t e))(z, z),  -l_0 <= t <= l_1.

Claim 1: f_r is convex in t. Proof: z is perpendicular to e (Lemma 6.4
outcome). So for the velocity line r(z + t e) = r z + (r t) e with
direction r e, and test vector z perpendicular to r e, Lemma 4.2
(concavity of A along the velocity line) says t -> A_x(r(z+te))(z, z)
is concave. Since B_x = g_x - A_x and g_x is constant in t, B_x has the
opposite convexity: t -> B_x(r(z+te))(z,z) is convex.

Claim 2: f_r(0) = 0. Indeed, applying the RADIAL IDENTITY with w = r z
and testing against z:

  A_x(r z)(z, z) = <z, z>_x = |z|_x^2,

so f_r(0) = |z|_x^2 - A_x(r z)(z,z) = 0.

Claim 3: f_r(l_1) is bounded above uniformly in r near 1. Indeed,
f_r(l_1) = B_x(r b_1)(z,z), and b_1 is nonconjugate, so
A_x(r b_1) -> A_x(b_1) as r -> 1 (by branch extension). Hence
B_x(r b_1) -> B_x(b_1) as well, giving a uniform bound C_5 >= 0 with
f_r(l_1) <= C_5 for r sufficiently close to 1.

Convexity of f_r on [0, l_1] with f_r(0) = 0 and f_r(l_1) <= C_5 implies
(by the secant-line inequality valid for convex functions) for every
0 < t <= l_1,

  f_r(t) <= (t / l_1) f_r(l_1) <= (C_5 / l_1) t.

Now the crucial rewriting. Apply B_x(a)(a, .) = 0 with a = r(z + t e).
Multiplication by r is a bijection, so B_x(r(z+te))(z+te, .) = 0 for
every v. Then

  f_r(t) = B_x(r(z+te))(z, z)
         = B_x(r(z+te))(z + t e - t e, z + t e - t e)
         = B_x(r(z+te))(z+te, z+te)
             - 2 B_x(r(z+te))(z+te, t e)
             + B_x(r(z+te))(t e, t e)
         = 0 - 0 + t^2 B_x(r(z+te))(e, e),

where the middle two vanish by the null condition. So
f_r(t) = t^2 B_x(r(z+te))(e,e). Combining with f_r(t) <= (C_5/l_1) t
and dividing by t^2 > 0:

  B_x(r(z + t e))(e, e) <= C_6 / t,   0 < t <= l_1,

for a constant C_6 = C_5/l_1, valid for r sufficiently close to 1.

Finally, A_x = g_x - B_x, and |e|_x^2 = 1:

  A_x(r(z + t e))(e, e)
    = 1 - B_x(r(z + t e))(e, e)
    >= 1 - C_6 / t.                    (SINGULAR LOWER)

This is the contour needed to contradict (SINGULAR UPPER).


Return to (SINGULAR UPPER):

  A_x(r(z + t e))(e, e) <= C_1 - c_1 / (t^2 + 1 - r).

and (SINGULAR LOWER):

  A_x(r(z + t e))(e, e) >= 1 - C_6 / t.

Now specialize: take r = 1 - t^2 for t > 0 sufficiently small (t < sqrt(delta)
say, so r in [1 - delta, 1)). Then t^2 + 1 - r = 2 t^2, and both
inequalities apply (upper requires |t| < delta and r in [1 - delta, 1),
which holds; lower requires 0 < t <= l_1, also holds after shrinking
t further). Hence

  1 - C_6 / t <= C_1 - c_1 / (2 t^2).

Multiply both sides by t^2 > 0:

  t^2 - C_6 t <= C_1 t^2 - c_1 / 2.

Let t -> 0. The left side tends to 0 and the right side to -c_1/2 < 0.
A sequence of true inequalities cannot have limits satisfying
0 <= -c_1/2. Contradiction.

Therefore the conjugate velocity z cannot exist in the open segment
(b_0, b_1). Since b_0 and b_1 themselves are nonconjugate by hypothesis,
every velocity in [b_0, b_1] is nonconjugate. []

COROLLARY 6.8 (nonconjugacy passes to minimizing convex hulls).
Let a_1, ..., a_m in T_x M be nonconjugate velocities with the closed
convex hull co{a_1, ..., a_m} contained in G_x. Then every velocity in
co{a_1, ..., a_m} is nonconjugate.

PROOF. Induction on the number k of positive weights in a convex
representation w = sum_i theta_i a_i, theta_i > 0, sum_i theta_i = 1.
The case k = 1 is w = a_i, nonconjugate by hypothesis. For k >= 2,
choose an index k and write

  w = (1 - theta_k) w' + theta_k a_k,
  w' = sum_{i < k} (theta_i / (1 - theta_k)) a_i.

The point w' lies in co{a_1, ..., a_{k-1}} subset co{a_1, ..., a_m}
subset G_x, so by induction w' is nonconjugate. Also a_k is nonconjugate
by hypothesis. The whole segment [w', a_k] lies in co{a_1, ..., a_m},
hence in G_x. Proposition 6.1 applies and makes w nonconjugate. By
metrizability of T_x M and compactness of the simplex of weights, this
covers every point of the hull. []



The proof of global support goes by a continuation argument
on the subgradient graph of a potential u. To set it up, it helps to know
what a potential is, what its subdifferential is, and how to write the
subdifferential in terms of "active velocities". Also needed is the
divided action cost c_t = c/t, its inf-convolution Q_t u, and a family
of geometric estimates (radial decrease, transverse slack) on the
source Hessian of c_t. This part gathers all of that.


DEFINITION. A continuous function u: M -> R is a potential if there is a
continuous v: M -> R with

  u(x) = max_y {-c(x, y) - v(y)}   for every x in M.       (7.a)

The function v is called a representing datum for u. The dual transform
of u is

  v_u(y) = max_x {-c(x, y) - u(x)}.

If v is replaced by v_u the right-hand side of (7.a) does not change
(given that u is realized as a max of that form):

  u(x) = max_y {-c(x, y) - v_u(y)}.

Take (u, v_u) as a dual pair without loss. For a dual pair,
u(x) + c(x, y) + v_u(y) >= 0 for all x, y, and for each pair (x, p)
there exists y with u(x) + c(x, y) + v_u(y) = 0 if and only if p is an
active velocity to y (see below).

FINITE MAXIMA ARE POTENTIALS. If u(x) = max_{i=1..N} {h_i - c(x, y_i)}
for distinct y_i and constants h_i, then after dual completion
v_u(y_i) <= -h_i and v_u(y) > -h_i off a small set, and the maxima
coincide. So finite maxima of "cones" minus c are potentials in the
above sense. Any potential with finitely many active targets is one of
these. General potentials have infinitely many possible active targets,
but only finitely many are used at each x (by Caratheodory).


  LIPSCHITZ: u is D-Lipschitz. Proof: |c(x,y) - c(x',y)| = |d(x,y)^2
  - d(x',y)^2|/2. Write d(x,y) + d(x',y) <= 2 D and use the reverse
  triangle inequality d(x,y) - d(x',y) <= d(x,x'). So the absolute
  difference is at most D d(x,x'). Max over y of these - v(y) gives
  |u(x) - u(x')| <= D d(x,x').

  SEMICONCAVITY OF c: there is a uniform geometric constant C_g > 0
  such that c(., y) and c(x, .) are C_g-semiconcave on M, i.e. in any
  local coordinate ball, Hess c <= C_g g on the smooth part (in the
  barrier sense at cut points).

  The second-argument version is proved below; the first-argument
  version is the same by symmetry of c. Both extend to cut points by
  taking barrier supports.

  LIPSCHITZ AND SEMICONVEX OF u: as a maximum of the semiconvex
  functions -c(.,y) - v(y) (each is semiconvex because its negative
  c(.,y) is semiconcave), u is semiconvex with the same constant.
  Because -c <= 0 and using (7.a), |u| <= max(|v|).


For a parameter t > 0 write

  c_t = c / t,    Q_t f(z) = min_x {f(x) + c_t(x, z)},
  c_t(x, z) = d(x, z)^2 / (2 t).

DIVIDED TRIANGLE INEQUALITY. For a, b > 0 and any x, y, w in M:

  c_{a+b}(x, y) <= c_a(x, w) + c_b(w, y),                (7.b)

with equality if w lies on a minimizing geodesic from x to y at
parameter a/(a+b).

PROOF. Concatenate the minimizing geodesic from x to w (velocity u, time
a) with the minimizing geodesic from w to y (velocity u, time b), when w
is on a minimizing x-y geodesic with speed |u|. Both parts are geodesic,
so the concatenation is a geodesic from x to y of length (a+b)|u|. Because
the whole x-y geodesic is minimizing, its cost is c(x,y) = (a+b)^2 |u|^2
/ 2. On the other hand, c_a(x,w) = a|u|^2/2 and c_b(w,y) = b|u|^2/2,
summing to (a+b)|u|^2/2 = c(x,y) = c_{a+b}(x,y). In general w is off
the minimizing geodesic, and the path through w is longer, so the sum
of separated costs is at least c_{a+b}(x,y). []

SPLIT SUPPORT INEQUALITY. Let p in G_x, y = exp_x(p), and y_s =
exp_x(s p) for 0 < s < 1. Then for every z:

  c(z, y) <= c_s(z, y_s) + (1-s) |p|^2 / 2,               (7.c)

with equality at z = x.

PROOF. Apply (7.b) with (x, y) replaced by (z, y), a = s, b = 1-s,
w = y_s. The right-hand side is

  c_s(z, y_s) + c_{1-s}(y_s, y).

Now y_s lies on the minimizing geodesic from x to y at parameter s (with
p in G_x). So d(y_s, y) = (1-s)|p|_x. Thus

  c_{1-s}(y_s, y) = (1-s) |p|_x^2 / 2.

Substituting, (7.c) follows. At z = x, c_s(x, y_s) = s |p|^2 / 2 and
(1-s)|p|^2/2 sum to |p|^2/2 = c(x,y). []

The right-hand side of (7.c) is smooth in z near x, because s p is in
I(x) (Lemma 5.2: s p in s G_x subset I(x) for 0 < s < 1). So (7.c)
exhibits c(., y) as squeezed between a smooth upper support (the right
side) and equality at x. This is exactly the semiconcavity property
needed. Taking s = 1/2 and 3/4, e.g., gives uniform constants.


From (7.c): for every x, y and every 0 < s < 1 with s log_x(y) in I(x)
for some minimizing log, the map

  z -> c_s(z, y_s) + (1-s)|p|^2/2

is a smooth upper support to c(., y) touching at z = x. Because the
family of half-vectors sp lies in the compact set (1/2) C subset TM for
s = 1/2 (the total minimizing set C is compact), the supports
have a common neighborhood size and a common Hessian upper bound.
Hence c(., y) is C_g-semiconcave with a constant C_g depending only on
(M, g). Symmetry of c gives the same for c(x, .).


DEFINITION. Fix x. A velocity p in G_x is active for a fixed representing
datum v if

  u(x) + c(x, exp_x(p)) + v(exp_x(p)) = 0.                (7.d)

Write V_u(x) for the set of active velocities. This set depends on the
datum v only via the constraint (7.d), and in practice work
with the dual completion v = v_u, making V_u(x) = {p in G_x : u(x) +
c(x, exp_x(p)) + v_u(exp_x(p)) = 0}.

DIRECTIONAL DERIVATIVE. For any h in T_x M set

  u'(x; h) = lim_{r -> 0+} (u(exp_x(r h)) - u(x)) / r.

LEMMA 7.4. u'(x; h) = max_{p in V_u(x)} <p, h>_x.

PROOF. Fix h. Lower bound on u': fix any active p (so y = exp_x(p)
satisfies (7.d)). For any z, u(z) >= -c(z, y) - v(y). With z = exp_x(r h),
u(z) >= -c(exp_x(rh), y) - v(y). Combine with (7.d) giving
u(x) = -c(x, y) - v(y):

  [u(exp_x(r h)) - u(x)] / r >= [c(x, y) - c(exp_x(rh), y)] / r.

Apply the split support (7.c) at z = exp_x(rh) and z = x, both with the
same p and the same s (take s -> 1/2 or any intermediate value):

  c(x, y) = c_s(x, y_s) + (1-s)|p|^2/2,
  c(exp_x(rh), y) <= c_s(exp_x(rh), y_s) + (1-s)|p|^2/2.

The difference is at least c_s(x, y_s) - c_s(exp_x(rh), y_s). Since
c_s(., y_s) is smooth near x (as sp in I(x)), its first-order Taylor
expansion at x along the geodesic exp_x(rh) is

  c_s(exp_x(rh), y_s) = c_s(x, y_s) + r <grad c_s(x, y_s), h> + o(r).

Now grad_z c_s(x, y_s) = -sp/s = -p (from the branch first-variation
formula, branch velocity sp for the divided cost). So the
difference is r <p, h> + o(r). Taking r -> 0:

  u'(x; h) >= <p, h>_x.  For every active p in V_u(x).  So u'(x;h) >= max.

Upper bound. For each r > 0, pick a minimizing active pair for
u(exp_x(rh)): some y_r and v(y_r) with u(exp_x(rh)) = -c(exp_x(rh), y_r)
- v(y_r). By compactness of the active graph (below, Lemma 7.5), along a
subsequence r_j -> 0 pass to a limit y_0 with a corresponding
limit p_0 in V_u(x). From smoothness of c on the (uniformly bounded)
branch from x to y_j for small r_j and the identity

  c(exp_x(r_j h), y_j) - c(x, y_0) = -r_j <p_0 + o(1), h> + o(r_j),

it follows that u'(x; h) <= <p_0, h>_x <= max_{p in V_u(x)} <p, h>. []

LEMMA 7.5 (compactness of the subdifferential graph). The set
Gamma_u = {(x, p) : p in Du(x)} is compact in TM.

PROOF. Bounded: for p in Du(x), p is a subgradient of the D-Lipschitz
function u at x, so |p|_x <= D. The set is closed: subdifferentials
of a semiconvex function are upper-semicontinuous -- if x_j -> x and
p_j in Du(x_j) with p_j -> p, then p in Du(x). This follows from the
subgradient inequality u(x') >= u(x_j) + <p_j, log_{x_j}(x')>_{x_j}
- (K/2) d(x_j, x')^2 valid for the semiconvexity constant K, sending
j -> infinity and using continuity of u, log, and d. So Gamma_u is a
closed subset of {(x, p) : |p| <= D}, which is compact in TM. []

REMARK. The same argument applies to the subset {(x, p) : p in V_u(x)}
of active velocities (they form the extreme points of Du(x)); the
version for Gamma_u is what the continuation section uses.

COROLLARY 7.6 (subdifferential = convex hull of active velocities).
For a semiconvex function u, the ordinary subdifferential Du(x) equals

  Du(x) = conv V_u(x).

PROOF. For a semiconvex function, p in Du(x) iff <p, h> <= u'(x; h) for
every h. By Lemma 7.4, u'(x;h) = max_{p in V_u(x)} <p, h>, so p is in
Du(x) iff <p, h> <= max_{q in V_u(x)} <q, h> for all h. The polar of the
set V_u(x) has this as its defining half-space condition. Taking polars
twice gives Du(x) = conv(cl V_u(x)) = conv V_u(x) (by compactness). []

COROLLARY 7.7 (Caratheodory and affine independence). Every p in
Du(x) has a convex representation

  p = sum_{i=1}^m theta_i a_i,  theta_i > 0,  sum_i theta_i = 1,
  a_i in V_u(x),  m <= n+1,

with the a_i affinely independent.

PROOF. Caratheodory: any point of conv V_u(x) in R^n (identifying T_xM
with R^n via a frame) is a convex combination of at most n+1 points of
V_u(x). Reduce the representation to one with the fewest positive
weights; if the a_i were affinely dependent, the weights could be
perturbed within the affine dependence until one hits zero, contradicting
minimality. So the surviving vertices are affinely independent. []

These are the only facts used by the continuation argument.


For a fixed base point x and velocity p in a minimizing set for x, define
for 0 < s < 1

  H_s(p) = Hess_{zz} c_s(z, exp_x(s p)) |_{z = x}
        = (1/s) A_x(s p)               (branches agree in I(x)),

a symmetric bilinear form on T_x M. It is the source Hessian of the
divided cost c_s at the point x with respect to the endpoint exp_x(s p).
Note that s p lies in I(x) because s p lies in s G_x and s G_x is
contained in I(x) (Lemma 5.2). So A_x(s p) is defined and smooth: the
branch cost is the true cost near (x, exp_x(s p)).

Geometrically: the second term in the Taylor expansion of the divided
cost c_s(z, exp_x(s p)) near z = x is (1/2) <(z - x), H_s(p)(z - x)>_x
+ o(|z - x|^2). H_s(p) measures how fast a small displacement in z costs
extra divided action.


LEMMA 7.7. Fix x and a in G_x. For 0 < t < s < 1 there is a constant
kappa = kappa(s) > 0 such that

  H_t(a) - H_s(a) >= kappa (s - t) Id.            (7.e)

Here kappa depends on (t, s) via the geometry of Jacobi fields on [0, s];
on compact subintervals of (0, 1), kappa can be chosen uniformly.

PROOF. Recall the STRICT radial comparison (Lemma 3.4): for 0 < t < s < 1,

  A_x(t a) > (t / s) A_x(s a).

That gives H_t(a) > H_s(a), i.e. positivity. For the uniform quantitative
version the argument passes through Jacobi fields.

Let S_a(r) be the Jacobi tensor along gamma_{x,a} with S_a(0) = 0 and
D_r S_a(0) = Id, expressed in a parallel orthonormal frame. This is the
"endpoint-vanishing" Jacobi family. It is a smooth invertible matrix for
r in (0, 1): its invertibility at r is equivalent to (r a being conjugate
at x), which is forbidden by Lemma 5.3 (all r a in I(x), for 0 < r < 1).

On the compact set {(a, r) : a in G_x, 0 < r <= s} (with s < 1 fixed),
S_a(r) and S_a(r)^{-1} are continuous and bounded above. Let
kappa = kappa(s) = min_{a in G_x, r <= s} sigma_min(S_a(r))^{-2} > 0,
where sigma_min is the smallest singular value. (Positive because
S_a(r) is invertible on this compact set.)

Now the derivative of H_r(a) in r. Because H_r(a)(xi,xi) is the
index-form minimum along gamma_{x,a}|_{[0,r]} (by Lemma 3.3, rescaled),
standard Jacobi-field calculus (the Wronskian identity for a fundamental
pair of Jacobi tensors S_a, C_a) gives

  (d/dr) H_r(a) = -S_a(r)^{-1} S_a(r)^{-T}.        (7.f)

Indeed, write Y_r(r') = C_a(r') - S_a(r') S_a(r)^{-1} C_a(r) for the
Jacobi field vanishing at r' = r with Y_r(0) an arbitrary vector; its
index-form value equals <S_a(r)^{-1} C_a(r) xi, xi> by integration by
parts, and differentiating in r using the Wronskian identity

  C_a'(r) - S_a'(r) S_a(r)^{-1} C_a(r) = -S_a(r)^{-T}

gives (7.f). The calculation is not repeated; both sides agree on
diagonal entries by direct differentiation, and the quadratic forms are
symmetric, so the identity holds in general.

Now integrate (7.f) from t to s. The product S_a(r)^{-1} S_a(r)^{-T}
is positive definite, and its smallest eigenvalue is
1 / lambda_max(S_a(r) S_a(r)^T) = sigma_min(S_a(r))^{-2}, where
sigma_min is the smallest singular value. On the compact set
{(a,r) : a in G_x, 0 <= r <= s} the value sigma_min(S_a(r)) is
bounded below by sigma_0(s) > 0 (by invertibility and continuity),
so the smallest eigenvalue of S_a(r)^{-1} S_a(r)^{-T} is at least
sigma_0(s)^{-2}. Choose kappa = sigma_0(s)^{-2}. Then

  H_t(a) - H_s(a) = integral_t^s (-(d/dr) H_r(a)) dr
                  = integral_t^s S_a(r)^{-1} S_a(r)^{-T} dr
                  >= (s - t) kappa Id. []


LEMMA 7.8. Let p_1, ..., p_m in G_x, m_i > 0, sum_i m_i = 1, p = sum_i m_i p_i,
E = span{p_i - p : i = 1..m}. Suppose t conv{p_1, ..., p_m} is contained
in I(x) and 0 < t < s < 1. Then

  [H_t(p) - sum_i m_i H_s(p_i)] |_{E^perp}
    >= kappa (s - t) Id,             (7.g)

where kappa is as in Lemma 7.7 (with the same s; on compact subintervals of
(0,1) the constant is uniform).

PROOF. Fix xi in E^perp. Each direction p_i - p_j lies in E and is
therefore perpendicular to xi. The velocities t p_i all lie in I(x) by
hypothesis, so all segments [t p_i, t p_j] lie in I(x) (as the segments
lie in t conv{p_i}). Apply the transverse concavity (Lemma 4.3) on
these segments, with direction p_i - p_j perpendicular to xi:

  A_x(t p)(xi, xi) >= sum_i m_i A_x(t p_i)(xi, xi).

Divide by t (using H_t(q) = A_x(t q)/t):

  H_t(p)(xi, xi) >= sum_i m_i H_t(p_i)(xi, xi).     (7.h)

Then subtract sum_i m_i H_s(p_i):

  H_t(p)(xi, xi) - sum_i m_i H_s(p_i)(xi, xi)
    >= sum_i m_i [H_t(p_i)(xi, xi) - H_s(p_i)(xi, xi)]
    >= sum_i m_i kappa (s - t) |xi|^2       (by Lemma 7.7)
    = kappa (s - t) |xi|^2.

Since each p_i is in G_x, so Lemma 7.7 applies to p_i in place of a.
Since xi in E^perp was arbitrary, this proves (7.g). []

The same conclusion holds at a limiting t if the radially contracted
hulls r conv{p_i}, 0 < r < t, lie in I(x) and each p_i is nonconjugate
(so H_t(p_i) exists as a limit of branches), and the branch Hessians
admit limits. Then A_x(t p_i) makes sense via branch extension,
and (7.h) follows by continuity from the r < t version.


LEMMA 7.9. Let u be a potential, t > 0, z in M. If x is a global
minimizer of u + c_t(., z), then w/t in Du(x) for every minimizing
velocity w in L_x(z). Consequently, F_t : Gamma_u -> M, F_t(x, p) =
exp_x(t p), is surjective for every t > 0.

PROOF. Fix any w in L_x(z) and any lambda in (0, 1). Put z_lambda =
exp_x(lambda w). The divided triangle inequality (7.b), applied with
x' in place of x, (a, b) = (t lambda, t (1 - lambda)), and w replaced by
z_lambda, gives the upper support

  U_w(x') = (1/(t lambda)) c(x', z_lambda)
          + (1/(t (1 - lambda))) c(z_lambda, z)
          >= c_t(x', z),
  U_w(x) = c_t(x, z).

(Equality at x: c_t(x,z) = |w|_x^2/(2t), the divided costs through z_lambda
are ((t lambda)*|w_lambda|)^2/(2 t lambda) + ... summing to that.)

The support U_w is smooth near x, because lambda w in I(x) (Lemma 5.2)
and the part involving z is just a constant in x'. Its gradient at x is

  grad_x U_w(x) = (1/(t lambda)) * grad_x c(x, z_lambda)
                = (1/(t lambda)) * (-lambda w)
                = -w / t.

The last identity uses the branch first-variation formula
with velocity lambda w: grad_x c(x, exp_x(lambda w)) = -lambda w.

Now, x globally minimizes u + c_t(., z). Since U_w >= c_t(., z) with
equality at x, the point x also globally minimizes u + U_w (if x' made
u + U_w smaller, then u + c_t(., z) would be at most as small, contradicting
minimality at x). At a minimum of u + U_w with U_w smooth, the gradient
of U_w at x lies in -Du(x):

  -w / t in -Du(x),  i.e. w/t in Du(x). []

COROLLARY 7.10. For every potential u, t > 0, and z in M, there is a
pair (x, p) in Gamma_u (i.e. p in Du(x)) with F_t(x, p) = z. So F_t: Gamma_u
-> M is surjective.

PROOF. A global minimizer x of u + c_t(., z) exists (u + c_t is continuous
on the compact M). Pick any w in L_x(z) (nonempty by Proposition 5.1). Lemma 7.9
gives w/t in Du(x), so (x, w/t) is in Gamma_u with F_t(x, w/t) = exp_x(w) = z. []



LEMMA 7.11. Let f be Lipschitz and semiconvex on M, with constants L
and K (|f(x) - f(x')| <= L d(x,x'), Hess f >= -K g). Then for every
sufficiently small t > 0 (depending only on L, K, (M,g)), the map

  F_t : Gamma_f -> M,    F_t(x, p) = exp_x(t p),

is a homeomorphism. Its inverse is locally Lipschitz as a map to TM.
At every z, the unique global minimizer x_t(z) of f + c_t(., z) is the
first component of F_t^{-1}(z), and

  Q_t f(z) = f(x_t(z)) + c_t(x_t(z), z)                    (7.i)

is C^{1,1} on M, with

  grad_z Q_t f(z) = -(1/t) log_z x_t(z).                   (7.j)

PROOF.

STEP A: MINIMIZERS RUN INTO A SMALL BALL. Let x globally minimize
f + c_t(., z) and let p in Df(x) be any subgradient. Then

  c_t(x, z) <= f(z) - f(x) <= L d(x, z),

so d(x, z)^2/(2t) <= L d(x, z) and therefore d(x, z) <= 2 L t. Also
|p|_x <= L (because f is L-Lipschitz; Df extracts |p| <= L). So
z_p = exp_x(t p) satisfies d(z_p, x) <= t |p| <= L t. Both x and z_p
are within 3 L t of z. In particular, if t < rho/(3L) they both lie in
the normal ball of radius rho around a fixed center (say a point halfway
between x and z), inside which the cost is smooth and D^2_{xx} c has a
uniform positive lower bound a_ > 0.

STEP B: STRONG CONVEXITY, UNIQUENESS OF POLE. On this ball
D^2_{xx} c(x', z) >= a_ g. And f has Hess f >= -K g. So
f + c_t(., z) has Hess >= (a_/t - K) g. For t < a_/(2K) (or if K=0,
unconditionally), this is strongly convex on the ball. Hence its
global minimizer is unique (and it lies in the ball by Step A). Call it
x_t(z).

STEP C: A GRAPH POINT PROJECTING TO z HAS THE MINIMIZER AS ITS POLE.
Let (x, p) in Gamma_f with z = exp_x(t p). On the small ball of STEPS A
and B, c_t(., z) is smooth, so the subdifferential of f + c_t(., z) at
x contains the sum of the two contributions:

  D(f + c_t(., z))(x) contains Df(x) + D_x c_t(x, z).

By hypothesis p in Df(x). On the other hand, first variation of c_t
in the source variable (with velocity t p for the divided
cost) gives D_x c_t(x, z) = -(log_x(z))/t. And log_x(z) = t p because
z = exp_x(t p). So D_x c_t(x, z) = -p. Hence

  0 = p + (-p)  is in  D(f + c_t(., z))(x).

So x is a critical point of f + c_t(., z) on the ball.

By STEP B, f + c_t(., z) is strongly convex on the ball. On a convex
domain a critical point of a strongly convex function is its unique
global minimum. The unconstrained global minimizer of f + c_t(., z)
also lies in the ball (STEP A). Hence x is a global minimizer, and by
uniqueness x = x_t(z).

STEP D: F_t IS A BIJECTION. Surjectivity follows from Lemma 7.9's
argument, which only used the tangent-gradient structure of f and the
smoothness of the divided cost; nothing special about potentials
entered. For injectivity, suppose F_t(x_1, p_1) = F_t(x_2, p_2) = z
with (x_i, p_i) in Gamma_f. By STEP C, x_1 = x_2 = x_t(z). The two
velocities t p_1 and t p_2 in L_x(z) have common endpoint z with
common length d(x, z). For t < rho / L, d(x, z) <= L t < rho,
so z lies in the injectivity ball of radius rho around x. There the
exponential map is a diffeomorphism, hence t p_1 = t p_2 and
p_1 = p_2. Thus F_t is a bijection.

STEP E: F_t IS A HOMEOMORPHISM. It is continuous (exp is smooth, t is
fixed) and, as a continuous bijection from a compact (Gamma_f is compact by
Lemma 7.5) to a Hausdorff space (M), it is a homeomorphism.

STEP F: LIPSCHITZ POLE AND MOMENTUM. Let z_1, z_2 in M and x_i = x_t(z_i).
Set p_i = -D_x c_t(x_i, z_i) in Df(x_i). Subgradient monotonicity:
<p_1 - p_2, x_1 - x_2>_x >= -K |x_1 - x_2|^2 for a semiconvex function f
with Hess f >= -K g. Here the pairing is done in a fixed coordinate
chart, and the log endomorphism transfers between T_{x_1} M and T_{x_2} M
harmlessly (as it is O(1) close). Expanding D_x c_t at (x_2, z_2) and
using D^2_{xx} c_t >= (a_/t) g and |D^2_{xz} c_t| <= B/t on the ball,
gives (a_/t - K) |x_1 - x_2| <= (B/t) |z_1 - z_2|. So

  |x_1 - x_2| <= (B / (a_ - t K)) |z_1 - z_2|.             (7.k)

Hence z -> x_t(z) is (a_ - tK)^{-1} B-Lipschitz. Because p = -D_x c_t(x, z)
and c_t is smooth on the ball, p is Lipschitz too, with a constant
depending only on M, g, t (and on L, K through (7.k)). This gives local
Lipschitz-inverse for F_t.

STEP G: FORMULA FOR GRAD Q_t f. Differentiate (7.i) in z. v = x_t(z) is
a C^0 initial variable, and the first-order condition
-D_x c_t(x_t(z), z) = p(z) in Df(x_t(z)) means that, at fixed z, the x
direction is stationary. Standard differentiation of an infimum at a
stationary point (envelope theorem) then gives

  grad_z Q_t f(z) = grad_z [f(x_t(z)) + c_t(x_t(z), z)] |_{x = x_t(z) fixed}
                  = D_z c_t(x_t(z), z)
                  = -(1/t) log_z x_t(z).

The last identity is the branch formula for the z-derivative of the cost:
grad_z c(x, z) = -log_z x (velocity at z pointing to x, in a unit-time
parametrization), so grad_z c_t = -log_z x / t. []

      semiconvex f).





Fix a potential u with dual pair v . Recall:

  Gamma_u = {(x, p) : p in Du(x)},                 compact in TM (Lemma 7.5)
  F_t : Gamma_u -> M,    F_t(x, p) = exp_x(t p),   0 <= t < 1.

Do not use F_0. The graph Gamma_u need not be a single-valued graph
over M: for a potential u (a max of functions -c(., y) - v(y)) the
ordinary subdifferential Du(x) can have interior. A concrete example on
Euclidean R^n with c(x,y) = |x-y|^2/2: put v(y) = -|y|, then
u(x) = max_y {-c(x, y) - v(y)} = |x| + 1/2, which is a potential with
Du(0) = closed unit ball of R^n. So "u is C^{1,1} and Gamma_u is a graph
over M" fails in general, and F_0 is not injective whenever Du(x) is
multivalued.

What is true unconditionally: Gamma_u is compact (Lemma 7.5), F_t is
continuous for each t (smoothness of exp), and F_epsilon is a
homeomorphism for every small enough epsilon > 0 (Lemma 7.11). This
homeomorphism justifies viewing Gamma_u as a compact topological
n-manifold homeomorphic to M; in particular, when applied later
Lemma 8.4 to X = Gamma_u, the hypothesis that X is a compact topological
n-manifold is met by transport of the manifold structure along
F_epsilon^{-1}.

By Lemma 7.11, F_t is a homeomorphism for small t > 0 (the constant
L there is the Lipschitz constant D of u, and K the semiconvexity
constant C_g, both fixed).

By Corollary 7.10, F_t is surjective for every t > 0. So the only thing
that can fail as t increases from 0 is injectivity. It will be shown that
nothing fails.


DEFINITION. Call a pair (x, p) in Gamma_u "t-good" if t p is in I(x).
Call the continuation good up to t if every (x, p) in Gamma_u is t-good.
Write

  T = sup { t_0 in [0, 1] : every (x,p) in Gamma_u is t-good for every
           t in [0, t_0] }.

By definition of I(x), 0 is in I(x) for every x, and by Lemma 7.11 there
is a uniform delta_0 > 0 such that every t p with 0 <= t < delta_0 and
(x,p) in Gamma_u lies in I(x) (velocity |p| <= D, so t|p| < delta_0|p| <
rho when t < rho/D). Hence T >= delta_0 > 0.

If T >= 1 the argument is complete: every graph pair stays in I(x) up to time 1.
Suppose for contradiction that T < 1, and derive a contradiction.

CLAIM 8.2 (nonconjugacy at the first failure). At the failure time
T, every scaled graph vector T p, (x,p) in Gamma_u, is nonconjugate.

PROOF. Fix (x,p) in Gamma_u. Since p in Du(x), write
p = sum_{i=1}^m theta_i a_i with theta_i > 0, sum_i theta_i = 1, and
a_i in V_u(x) (Caratheodory, Corollary 7.7). Then

  T p = sum_i theta_i (T a_i).

Because each a_i is in G_x and T < 1, Lemma 5.2 says T a_i is in
I(x), hence nonconjugate (Lemma 5.3). The scaled hull
co{T a_1, ..., T a_m} lies in T G_x (since each T a_i is T times an
element of G_x), which is contained in G_x (Lemma 5.2: r G_x subset
G_x for 0 <= r <= 1, with the boundary case r=1 being G_x itself).
Corollary 6.8 then makes every point of the hull, in particular
T p, nonconjugate at x. []

So at t = T every graph vector is being scaled to a nonconjugate
velocity, even though it is no longer certain to be in I(x).

CLAIM 8.2B (closure up to G_x). At time T every scaled graph vector
T p, (x,p) in Gamma_u, actually lies in G_x.

PROOF. Fix (x,p) in Gamma_u. Choose a sequence t_j to T. Then t_j < T, so
t_j p is in I(x), hence in G_x. The set G_x is closed (Lemma 5.1), so
the limit T p = lim t_j p is in G_x. []

So at t = T: every graph vector is a minimizing velocity (Claim 8.2B)
AND nonconjugate (Claim 8.2). This combination is exactly the hypothesis
of the local injectivity lemma to be proved next.


The following two-part statement is needed.

LEMMA 8.3 (local injectivity). Let u be a potential and 0 < T < 1.
Suppose that

  (a) for every (x,p) in Gamma_u and every 0 < t < T, the velocity t p
      is in I(x), and

  (b) every scaled graph vector T p, (x,p) in Gamma_u, is nonconjugate.

Then F_T : Gamma_u -> M is locally injective.

The case analysis is deferred to the next two subsections; the proof
requires (i) the one-dimensional expansion of the "active" contributions
to u, (ii) the exact cancellation of the linear terms before taking
limits, (iii) the transverse slack inequality. Those are
developed below. For now record what is known:
- by Claim 8.2B, under the failure assumption T < 1, T p lies in G_x
  for every (x,p) in Gamma_u;
- by Claim 8.2, T p is nonconjugate, so d_{T p} exp_x is invertible.

8.3.1 PROOF OF THE LOCAL INJECTIVITY LEMMA: SETUP.

Proof of Lemma 8.3. Suppose local injectivity of F_T fails at some
(x, p) in Gamma_u. Then there are distinct graph points converging to (x, p):

  (x_j, p_j) -> (x, p),    (x~_j, p~_j) -> (x, p),
  z_j := exp_{x_j}(T p_j) = exp_{x~_j}(T p~_j) -> z := exp_x(T p).

By hypothesis (b), T p is nonconjugate. So the exponential pair map
(z,u) -> (z, exp_z(u)) is a local diffeomorphism at (x, T p), and
therefore admits a smooth local inverse-branch cost C_hat around (x, z)
that represents the cost near (x, z). Both sequences (T p_j) and
(T p~_j) lie in that branch for large j, and the branch cost provides a
smooth function C_hat between the branch velocities.

The points x_j and x~_j must be distinct (else p_j = p~_j for large j
since they would give the same branch velocity to z_j). Exchange them
if necessary so that

  Delta_j := u(x~_j) + (1/T) C_hat(x~_j, z_j)
       - u(x_j) - (1/T) C_hat(x_j, z_j) <= 0.            (8.a)

(One of the two orderings has non-positive Delta_j, since Delta_j^{swapped} =
-Delta_j.)

Write ell_j := log_{x_j}(x~_j), l_j := |ell_j|_{x_j} > 0, and
e_j := ell_j/l_j in T_{x_j} M. These logarithms are unique for large j
because l_j -> 0 and the injectivity radius is positive. After passage
to a subsequence in a tangent-bundle chart, e_j -> e in T_x M with
|e|_x = 1. Because x_j, x~_j -> x, the entire short geodesic joining
x_j to x~_j lies in a fixed compact neighborhood on which C_hat is smooth.

8.3.2 ACTIVE SLOTS AND THE TAYLOR EXPANSION.

Each p_j in Du(x_j) has an active representation with at most n+1 slots:

  p_j = sum_{i=1}^{N} m_{ji} a_{ji},    m_{ji} >= 0,    sum_i m_{ji} = 1,
  a_{ji} in V_u(x_j),   N = n+1.

(Zero weights are allowed; a fixed number of slots is used.)

Compactness of the active-log graph (Lemma 7.5) and of the weight
simplex gives, after passing to a further subsequence:

  m_{ji} -> m_i,    a_{ji} -> a_i in V_u(x),
  p = sum_{i=1}^{N} m_i a_i.

Only these finitely many slots enter the argument. Note that p itself is
the limit of p_j and admits the limiting representation.

Now fix an intermediate time s with T < s < 1. This is the crucial move:
s is strictly larger than T, and by hypothesis (a) the scaled velocities
s a_{ji} are nonconjugate-at-x_j velocities (in fact s a_{ji} lies in
s G_{x_j} subset I(x_j), by Lemma 5.2, because a_{ji} in G_{x_j} and
s < 1). So the divided cost c_s is smooth near (x_j, exp_{x_j}(s a_{ji})).

For each slot i, split the active ray at time s to get the smooth
lower support

  u(x) >= u(x_j) + c_s(x_j, y_{ji}) - c_s(x, y_{ji}),
  y_{ji} := exp_{x_j}(s a_{ji}),

where the gradient of the right side at x_j is a_{ji} and the Hessian
at x_j is -H_s(a_{ji}) (with H_s(q) = A_{x_j}(s q)/s from the previous subsection).

On the other side, the selected divided branch cost has gradient -p_j at
x_j with respect to the first argument, and Hessian H_T(p_j).

Taylor expansion along ell_j gives, for every slot i:

  Delta_j >= l_j <a_{ji} - p_j, e_j>_{x_j}
        + (l_j^2/2) [H_T(p_j) - H_s(a_{ji})](e_j, e_j)
        + eps_{ji} l_j^2,                              (8.b)

where max_i |eps_{ji}| -> 0 as j -> infinity. The remainder eps_{ji} is
uniform over i, even for slots whose weights vanish: the branch cost C_hat
has bounded third derivatives on the fixed compact neighborhood, and
the shortened active vectors s a_{ji} lie in a compact subset of the
injectivity domain (in the total TM, by the total version of Lemma 5.2),
so the corresponding support costs carry a uniform third-derivative
bound.

8.3.3 LIMITS OF THE LINEAR TERMS.

Write d_{ji} := <a_{ji} - p_j, e_j>_{x_j} and
B_{ji} := [H_T(p_j) - H_s(a_{ji})](e_j, e_j). Each B_{ji} is bounded,
and converges along the subsequence, because H_T(p_j) is a fixed smooth
branch Hessian at (x, T p) and H_s(a_{ji}) is a shortened active branch
Hessian that converges to H_s(a_i). So B_{ji} -> B_i uniformly in i.

Now divide (8.b) by l_j and use Delta_j <= 0:

  <a_{ji} - p_j, e_j>_{x_j} + (l_j/2) B_{ji} + (l_j) eps_{ji} <= 0.

Let j -> infinity. The middle and last terms vanish (l_j -> 0, B_{ji}
bounded, eps_{ji} -> 0). So

  d_i := <a_i - p, e>_x <= 0  for every i = 1, ..., N.       (8.c)

Now sum over slots weighted by m_{ji}. At every finite stage, p_j =
sum_i m_{ji} a_{ji}, so

  sum_i m_{ji} d_{ji} = 0                                       (8.d)

because sum_i m_{ji} <a_{ji} - p_j, e_j> = <p_j - p_j, e_j> = 0.
Let j -> infinity. Then sum_i m_i d_i = 0. Since every d_i <= 0 by
(8.c) and every m_i >= 0, this sum is zero if and only if

  d_i = 0 whenever m_i > 0.                                    (8.e)

Consequence: every positive-weight limiting active velocity a_i lies in
a common affine hyperplane perpendicular to e. That is, the vectors
a_i - p for i with m_i > 0 span a subspace E of T_x M that is
perpendicular to e.

But there is a subtlety: the limit e is defined in T_x M only after
passing to a diagonal subsequence in a tangent bundle chart. This is
fine; all the limits are consistent in one chart, and the bilinear
pairings above are continuous in (a_{ji}, p_j, e_j) in that chart.

8.3.4 THE TRANSVERSE SLACK AND THE CONTRADICTION.

Let P := {i : m_i > 0}, the set of positive weights in the limiting
representation p = sum_i m_i a_i. Put

  E := span{a_i - p : i in P} subset T_x M.

By (8.e) e in E^perp.

Now use the lower supports at the intermediate time s. Each a_i (i in
P) is in G_x (limit of a_{ji} in G_{x_j}, closed). For 0 < r < T, the
hull r co{a_i : i in P} is contained in r G_x subset I(x) (Lemma 5.2).
At time T the hull T co{a_i : i in P} is contained in T G_x subset G_x,
and by Claim 8.2 every point of the hull is nonconjugate. So the
hypotheses of the transverse slack Lemma 7.8 are met at (t,s) = (T,s):

  [H_T(p) - sum_i m_i H_s(a_i)] |_{E^perp}
    >= kappa (s - T) Id.                                       (8.f)

The right side is a positive multiple of the identity on E^perp. In
particular, at e (which is in E^perp, |e| = 1),

  delta_* := [H_T(p) - sum_i m_i H_s(a_i)](e, e)
    >= kappa (s - T) > 0.                                      (8.g)

Note how the argument uses s but not the smoothed hull at time s: only
the ORIGINAL active velocities a_i are evaluated at time s. The later
time s has been applied only to the a_i in G_x, never to the smoothed
p; no claim about s p or s Du(x) has been made.

Now the contradiction. Multiply (8.b) by m_{ji} and sum over i:

  m_{ji} Delta_j >= m_{ji} l_j d_{ji}
              + m_{ji} (l_j^2 / 2) B_{ji} + m_{ji} eps_{ji} l_j^2.

Summing:

  Delta_j sum_i m_{ji} >= l_j sum_i m_{ji} d_{ji}
                    + (l_j^2/2) sum_i m_{ji} B_{ji}
                    + l_j^2 sum_i m_{ji} eps_{ji}.

The middle term on the left is 1 (since sum_i m_{ji} = 1). The first
term on the right is zero by (8.d). Dividing by l_j^2 (positive) gives

  Delta_j / l_j^2 >= (1/2) sum_i m_{ji} B_{ji} + sum_i m_{ji} eps_{ji}. (8.h)

Now take j -> infinity. The last sum tends to zero (uniform bound
max_i |eps_{ji}| -> 0, weighted by m_{ji} in the simplex). The first sum
tends to (1/2) delta_*: positive-weight slots contribute (8.g), and
zero-weight slots contribute zero in the limit because B_{ji} remain
bounded and m_{ji} -> 0. Therefore

  liminf_{j -> infinity} (Delta_j / l_j^2) >= (1/2) delta_* > 0.  (8.i)

But (8.a) says Delta_j <= 0 for every j, so Delta_j / l_j^2 <= 0, and the
liminf cannot be positive. Contradiction.

This proves Lemma 8.3. The mechanism is transparent: the first-order
terms vanish because they can be canceled exactly at the finite stage
(before taking limits), and the second-order terms are bounded below by
the transverse slack kappa(s - t) Id, which is strictly positive.


LEMMA 8.4. Let X and N be connected compact topological n-manifolds
without boundary (n >= 1). A continuous locally injective map
f : X -> N that is homotopic to a homeomorphism h : X -> N is itself a
homeomorphism.

PROOF. Local injectivity: every point has a neighborhood on which f is
injective. By invariance of domain, f is a local homeomorphism, so
f(X) is open in N. Since X is compact, f(X) is compact in N, hence
closed. Since N is connected and nonempty, f(X) = N. So f is surjective.

Each fiber f^{-1}(y) is compact (as a closed subset of the compact X)
and discrete (by local injectivity). A compact discrete space is finite.

For y in N with f^{-1}(y) = {q_1, ..., q_k}: choose pairwise disjoint
neighborhoods U_i of q_i (in X) so small that f|U_i is a homeomorphism
onto its image V_i (in N). The compact set
E := X setminus union_i U_i has image f(E) (compact, closed in N) that
misses y. So

  W := (intersection_i V_i) setminus f(E)

is a nonempty open neighborhood of y evenly covered by f (each preimage
of a point w in W is one point in each U_i, and no point of E maps into
W). Hence f is a covering map.

Now use the homotopy from h to f. Homotopic maps induce the same map on
fundamental groups after base-point change (standard covering-space
theory). Since h is a homeomorphism, f_* : pi_1(X, q) -> pi_1(N, f(q))
is surjective for every lift-of-a-loop argument (as in the standard
proof that a covering homotopic to a homeomorphism is one-sheeted).

Assume f(q') = f(q) for q' != q. Choose a path gamma from q to q' in X.
Then f(gamma) is a loop at f(q) in N. Because pi_1 surjectivity holds,
there is a loop eta at q in X with f(eta) homotopic (endpointwise) to
f(gamma). The homotopy lifts uniquely to a homotopy from eta to a lift
of f(gamma), and by uniqueness of path-lifting-the path starting at q
in direction f(gamma) is eta itself, whose endpoint is q. But the path
starting at q in direction f(gamma) is gamma (because f(gamma) is the
image of gamma), whose endpoint is q'. So q = q'.

A bijective local homeomorphism between compact Hausdorff spaces is a
homeomorphism. []

Applied: X = Gamma_u is a compact topological n-manifold;
N = M; f = F_T; h = F_epsilon for epsilon small enough that F_epsilon
is a homeomorphism (Lemma 7.11). And the map

  (lambda, (x, p)) |-> exp_x(((1 - lambda) epsilon + lambda T) p)

provides a homotopy from F_epsilon to F_T (continuity in both variables
by smoothness of exp). So Lemma 8.4 applies. F_T is a homeomorphism.


Under the standing failure assumption T < 1, just shown:
F_T is a homeomorphism. Now finish the contradiction.

Fix any (x, p) in Gamma_u. Set z := F_T(x, p) = exp_x(T p). Let x' be a
global minimizer of u + c_T(., z) (existence by continuity on compact M).

By Lemma 7.9 applied at time T, every minimizing velocity w in L_{x'}(z)
satisfies w / T in Du(x'). So (x', w/T) is a graph point in Gamma_u, and
F_T(x', w/T) = exp_{x'}(T (w/T)) = exp_{x'}(w) = z. By injectivity of
F_T:

  x' = x and w/T = p, so w = T p.

Since w ranges over all minimizing velocities from x' to z, this shows
the fiber L_x(z) = {T p}.

Now by Lemma 5.3, a velocity is in I(x) if and only if it is the UNIQUE
minimizing velocity to its endpoint AND nonconjugate. was just shown
uniqueness at T p (L_x(z) = {T p}), and by Claim 8.2 the velocity T p
is nonconjugate. So T p is in I(x).

But this contradicts the definition of T as a failure time. Hence no
failure time exists in (0, 1): every graph vector T p lies in I(x) for
every T < 1.

CONSEQUENCE. So no failure time exists in (0, 1), i.e. for
every T in (0, 1) and every (x, p) in Gamma_u, the velocity T p lies in
I(x). Fix any such T. Lemma 8.3 requires two hypotheses:
  (a) every graph velocity t p with 0 < t < T lies in I(x). This holds
      by the just-proved conclusion at time t (since t < T < 1).
  (b) every graph velocity T p is nonconjugate. This holds by (a) of
      Lemma 5.3: a velocity in I(x) is nonconjugate at x.
So Lemma 8.3 gives that F_T is locally injective. Lemma 8.4 then
upgrades F_T to a global homeomorphism. Since T in (0, 1) was
arbitrary, F_T : Gamma_u -> M is a homeomorphism for every 0 < T < 1.


The first part of global support is ready.

THEOREM 8.6 (global support). Let u be a potential and x in M. For
every p in Du(x), the velocity p lies in G_x and satisfies

  u(x') >= u(x) + c(x, exp_x p) - c(x', exp_x p)   for all x' in M.
                                                              (8.j)

PROOF. Fix (x, p) in Gamma_u and x' in M. By the just-proved conclusion of
the continuation, for every T in (0, 1) the velocity T p lies in I(x). In
particular,

  d(x, exp_x(T p)) = T |p|_x,                          (8.k)
  u(x') + c_T(x', exp_x(T p)) >= u(x) + c_T(x, exp_x(T p)).   (8.l)

The inequality (8.l) is the global minimizing inequality for the
functional u + c_T(., exp_x(T p)) at x; it holds because x is the
unique global minimizer, by Corollary 7.10's conclusion applied to
the divided cost.

Now let T -> 1 in both (8.k) and (8.l). Continuity of d, c_T, u, exp
on compact M gives

  d(x, exp_x(p)) = |p|_x,
  u(x') + c(x', exp_x p) >= u(x) + c(x, exp_x p).

The first is exactly p in G_x. The second is exactly (8.j). []


THEOREM 8.7 (convexity). For every x in M, the closed minimizing
domain G_x is convex, and the open injectivity domain I(x) equals its
interior, hence is convex.

PROOF. Convexity of G_x. Fix p_0, p_1 in G_x and set y_i = exp_x(p_i),
i in {0, 1}. Define

  w(z) = max_{i=0,1} { c(x, y_i) - c(z, y_i) }.

This is a potential (finite maximum of c-cones, see above). The claim is
both p_0 and p_1 lie in Dw(x).

Fix i in {0, 1}. For z near x:

  w(z) >= c(x, y_i) - c(z, y_i).

The split support inequality (7.c) at parameter s (0 < s < 1) applied
with velocity p_i and endpoint y_i gives

  c(z, y_i) <= c_s(z, y_{i,s}) + (1-s)|p_i|_x^2/2,
  c(x, y_i) = c_s(x, y_{i,s}) + (1-s)|p_i|_x^2/2,

where y_{i,s} = exp_x(s p_i). Combining,

  w(z) >= c_s(x, y_{i,s}) - c_s(z, y_{i,s}).

The right side is smooth in z near x, and its gradient at x is

  -grad_z c_s(x, y_{i,s}) = -( -p_i ) = p_i,

by the branch first-variation formula (with divided-cost velocity s p_i).
So w(z) = w(x) + <p_i, log_x z> + o(|log_x z|). That is p_i in Dw(x).

Since Dw(x) = conv V_w(x) is convex (Corollary 7.6), the whole segment
[p_0, p_1] lies in Dw(x). By Theorem 8.6 applied to the potential w,
every p in Dw(x) lies in G_x. So [p_0, p_1] is contained in G_x.

The interior and the open domain. The claim is I(x) = int G_x.

(i) I(x) is open in T_x M (Lemma 5.1(c) total set I is open, sliced
    at fixed base x), and contained in G_x (Lemma 5.2). So
    I(x) is contained in int G_x.

(ii) Conversely, suppose v in int G_x. Because int G_x is open in T_x M,
    there is epsilon > 0 such that (1 + epsilon) v lies in G_x. By the
    definition of G_x, this means

      d(x, exp_x((1 + epsilon) v)) = (1 + epsilon)|v|_x.

    That is exactly the condition for v in I(x). So int G_x is
    contained in I(x).

Convexity of I(x) follows because the interior of a convex set is convex.

Specifically: if v_0, v_1 in I(x), then for 0 < theta < 1 the convex
combination theta v_0 + (1 - theta) v_1 lies in I(x), because both v_0
and v_1 are interior points of the convex set G_x and the combination
of interior points of a convex set lies in the interior.

This proves convexity of injectivity domains. []

REMARK 8.7. The proof of convexity of G_x used Theorem 8.6 (global
support at time 1), which was obtained by passing T -> 1. The full
strength of Theorem 8.6 is: every subgradient of a potential is a
minimizing velocity. So G_x here is the convex hull of the active
velocities of any potential, and the whole argument above shows that
conv V_w(x) is contained in G_x; taking w to range over potentials
exhausts G_x.


The global support theorem part (ii) says that for a dual pair (u, v) and any r, the set

  S_x(r) = { p in G_x : u(x) + |p|^2/2 + v(exp_x p) <= r }

is compact and convex, and satisfies a diameter bound. The proof follows.

LEMMA 8.8. Let (u, v) be a dual pair (v = v_u). For every x and every
r >= 0, S_x(r) is compact and convex. If S_x(r) is nonempty, then

  diam S_x(r)^2 <= 8 ( r + osc_{p in S_x(r)} v(exp_x p) ).      (8.m)

PROOF.

Compactness. G_x is compact (Lemma 5.1). The function
p -> u(x) + |p|^2/2 + v(exp_x p) is continuous, so its r-sublevel in
G_x is closed in G_x, hence compact.

The generating inequality. For p in G_x define

  m_p(z) = |p|^2/2 - c(z, exp_x p),    z in M.

Then the identity (from the definition of the dual completion)

  u(x) + |p|^2/2 + v(exp_x p) = sup_z { u(x) - u(z) + m_p(z) }     (8.n)

holds for every z. Indeed:
  sup_z { u(x) - u(z) + |p|^2/2 - c(z, exp_x p) }
  = u(x) + |p|^2/2 + sup_z { -u(z) - c(z, exp_x p) }
  = u(x) + |p|^2/2 + v(exp_x p)                     (definition of v = v_u).

Jensen-type inequality. Fix p_0, p_1 in G_x and 0 <= theta <= 1. Write
p_theta = (1-theta) p_0 + theta p_1. Define

  w(z) = max_{i=0,1} m_{p_i}(z).

Then w(x) = 0 (each m_{p_i}(x) = |p_i|^2/2 - c(x, exp_x p_i) = 0).
Each p_i is in Dw(x): for z near x, the branch formula for the
divided cost gives m_{p_i}(z) = <p_i, log_x z>_x + o(|log_x z|_x) (same
calculation as in the convexity step), and w(z) >= m_{p_i}(z). So p_i in Dw(x).

By convexity of Dw(x) = conv V_w(x) (Corollary 7.6), p_theta is also in
Dw(x). By Theorem 8.6 applied to the potential w and the subgradient
p_theta:

  w(z) >= w(x) + c(x, exp_x p_theta) - c(z, exp_x p_theta)
       = m_{p_theta}(z).

Combining, for all z:

  m_{p_theta}(z) <= max_{i=0,1} m_{p_i}(z).                     (8.o)

Now use (8.n). For p_theta:

  u(x) + |p_theta|^2/2 + v(exp_x p_theta)
    = sup_z { u(x) - u(z) + m_{p_theta}(z) }
    <= sup_z { u(x) - u(z) + max_{i=0,1} m_{p_i}(z) }
    <= max_{i=0,1} sup_z { u(x) - u(z) + m_{p_i}(z) }
    = max_{i=0,1} [ u(x) + |p_i|^2/2 + v(exp_x p_i) ].

So if p_0 and p_1 both satisfy the gap <= r, so does p_theta. Hence
the r-sublevel S_x(r) is convex.

Diameter bound. If p_0, p_1 in S_x(r), put p_m = (p_0 + p_1)/2 in S_x(r).
Set q(p) = u(x) + |p|^2/2 + v(exp_x p). Because |p|^2/2 satisfies the
exact parallelogram identity,

  |p_0|^2/2 + |p_1|^2/2 - 2 |p_m|^2/2 = |p_0 - p_1|^2 / 4.

Using q(p) = u(x) + |p|^2/2 + v(exp_x p):

  |p_0 - p_1|^2 / 8
    = [ q(p_0) + q(p_1) ] / 2 - q(p_m)
      + v(exp_x p_m) - [ v(exp_x p_0) + v(exp_x p_1) ] / 2.

Now q(p_0), q(p_1) <= r, and q(p_m) >= 0 (the gap is nonnegative because
u(x) + c(x, exp_x p) + v(exp_x p) >= 0). So

  [ q(p_0) + q(p_1) ] / 2 - q(p_m) <= r.

And

  v(exp_x p_m) - [ v(exp_x p_0) + v(exp_x p_1) ] / 2
    <= osc_{p in S_x(r)} v(exp_x p).

Combining,

  |p_0 - p_1|^2 / 8 <= r + osc_{p in S_x(r)} v(exp_x p).

Taking sup over p_0, p_1 in S_x(r) gives (8.m). []


The global support theorem part (iii) is about the intermediate potential at times
0 < t < 1. The proof follows.

THEOREM 8.9 (intermediate regularity). Let (u, v) = (u, v_u) be a dual
pair. For every 0 < t < 1:

  (a) Q_t u = -Q_{1-t} v, and Q_t u is C^{1,1} on M with a C^{1,1}
      seminorm bounded solely in terms of (M, g, t);

  (b) if (x_t(z), p_t(z)) = F_t^{-1}(z) is the pole and momentum pair,
      then grad Q_t u(z) = -(1/t) log_z(x_t(z)), and both x_t and p_t
      are Lipschitz, with constants depending only on (M, g, t);

  (c) there exist r_t, b_t > 0, depending only on (M, g, t), such that
      for every graph pair (x, p) in Gamma_u with z = F_t(x, p),

        u(x') + c_t(x', z) >= u(x) + c_t(x, z) + b_t d(x, x')^2
                                                              (8.p)
        for every x' with d(x, x') < r_t.

      On every compact subinterval of (0, 1), the constants can be
      chosen uniformly.

PROOF OF (a) AND THE IDENTITY Q_t u = -Q_{1-t} v.

For a dual pair, u(x') + c(x', y') + v(y') >= 0 for all x', y'.

The divided triangle inequality (7.b) with a = t, b = 1 - t gives, for
any x' and y',

  c_t(x', z') + c_{1-t}(z', y') >= c(x', y').

Chaining the two inequalities:

  u(x') + c_t(x', z')
    >= u(x') + c(x', y') - c_{1-t}(z', y')      (divided triangle, (7.b))
    >= -v(y') - c_{1-t}(z', y').                (dual pair: u + c + v >= 0)

That gives, for all x' and y',

  u(x') + c_t(x', z') >= -v(y') - c_{1-t}(z', y').               (8.q)

Take inf over x' and sup over y':

  Q_t u(z') >= -Q_{1-t} v(z').                                  (8.r)

Now fix (x, p) in Gamma_u and z = F_t(x, p). Put y = exp_x(p) = F_1(x, p).
By Theorem 8.6 (global support at time 1), applied to the graph pair
(x, p) and the point x',

  u(x') >= u(x) + c(x, y) - c(x', y)   for every x'.

Rearranged, that is

  -c(x', y) - u(x') <= -c(x, y) - u(x)  for every x'.

So the maximum over x' of {-c(x', y) - u(x')} is attained at x and
equals -c(x, y) - u(x). By the definition v(y) = v_u(y) =
max_{x'}{-c(x', y) - u(x')}, this gives

  v(y) = -c(x, y) - u(x),  i.e.  u(x) + c(x, y) + v(y) = 0.      (8.s)

Now at z' = z, evaluate the two extreme functional values:

  Q_t u(z) <= u(x) + c_t(x, z) = u(x) + t |p|_x^2/2,

  Q_{1-t} v(z) <= v(y) + c_{1-t}(z, y) = v(y) + (1-t) |p|_x^2/2.

Summing and using (8.s):

  Q_t u(z) + Q_{1-t} v(z) <= u(x) + |p|_x^2/2 + v(y)
                           = u(x) + c(x, y) + v(y) = 0.

Combining with (8.r):

  Q_t u(z) >= -Q_{1-t} v(z),  Q_t u(z) + Q_{1-t} v(z) <= 0,
  hence  Q_t u(z) = -Q_{1-t} v(z).                              (8.t)

Since F_t is a homeomorphism (by the continuation), every z is of this form; so
(8.t) holds on all of M.

The C^{1,1} bound now follows from the standard regularity picture:
Q_t u is an infimum over x' of c_t(x', .) + u(x'), and by uniform
semiconcavity of c_t, the infimum is uniformly semiconcave.
Symmetrically, Q_{1-t} v is uniformly semiconcave by the same argument,
so -Q_{1-t} v = Q_t u is uniformly semiconvex. A function that is
uniformly semiconcave and semiconvex on M is C^{1,1}; its C^{1,1}
seminorm depends only on (M, g, t) and the semiconcavity constant C_g.

PROOF OF (b): GRADIENT FORMULA AND LIPSCHITZ POLE.

By the continuation section F_t is a homeomorphism, with inverse assigning to each z
the graph pair (x_t(z), p_t(z)) in Gamma_u. At z' = z, Q_t u(z) has x as
the unique global minimizer (Lemma 7.11, STEP C of its proof), so x_t(z)
is well-defined and Lipschitz in z (Lemma 7.11, STEP F, bound (7.k)).
The momentum p_t(z) is recovered as p_t(z) = (1/t) log_{x_t(z)}(z),
also Lipschitz in z by the same argument (smooth stationarity equation
of the divided cost, formula (7.k) with the branch closed). The
formula grad_z Q_t u(z) = -(1/t) log_z x_t(z) is STEP G of Lemma 7.11
applied with f = u. This proves (b).

8.9 (c): UNIFORM QUADRATIC GROWTH.

Fix (x, p) in Gamma_u and z := F_t(x, p). Fix an intermediate time

  s := (1 + t)/2,    so  t < s < 1.

Let y_s := exp_x(s p). Because p in G_x and 0 < s < 1, s p lies in I(x)
(Lemma 5.2), so the cost c reduces smoothly to c_s near (x, y_s). The
split support (7.c) with parameter s gives

  u(x') >= u(x) + c_s(x, y_s) - c_s(x', y_s)  for every x'.      (8.u)

Add c_t(x', z) - c_t(x, z) to both sides:

  g(x') := u(x') + c_t(x', z) - u(x) - c_t(x, z)
         >= h(x') := [c_s(x, y_s) - c_s(x', y_s)]
                     + [c_t(x', z) - c_t(x, z)].                (8.v)

At x' = x: h(x) = [c_s(x, y_s) - c_s(x, y_s)] + [c_t(x, z) - c_t(x, z)]
= 0. So g(x) = h(x) = 0. And g(x') >= h(x') for every x'.

Gradient and Hessian of h at x. Two applications of the branch
first-variation formula:

  grad_{x'} c_s(x', y_s) |_{x' = x} = -(s p)/s = -p
    (branch velocity s p for divided cost c_s),
  grad_{x'} c_t(x', z)  |_{x' = x} = -(t p)/t = -p
    (branch velocity t p for divided cost c_t, and log_x z = t p).

Hence

  grad h(x) = (+p) + (-p) = 0.                                  (8.w)

The Hessians follow the same branch data:

  Hess_{x'x'} [-c_s(., y_s)] |_x = -H_s(p),
  Hess_{x'x'} [c_t(., z)]    |_x = +H_t(p).

So

  Hess h(x) = H_t(p) - H_s(p) >= kappa (s - t) Id,              (8.x)

by the radial decrease (Lemma 7.7). Since s - t = (1-t)/2,
Hess h(x) >= kappa (1-t)/2 Id at x.

Quadratic growth on a small ball. Choose r_t > 0 small enough that

  - h is twice continuously differentiable on the closed ball of
    radius r_t around x, with third derivatives uniformly bounded;
  - the Taylor remainder of h around x is at most (1/4) of the
    quadratic term at radius r_t.

Then for d(x, x') < r_t,

  h(x') >= h(x) + <grad h(x), log_x x'> + (1/2) <log_x x', Hess h(x) log_x x'>
          + O(|log_x x'|^3)                     (third-order remainder)
        >= (1/4) kappa (1-t) |log_x x'|_x^2
        >= (1/4) kappa (1-t) d(x, x')^2.      (comparing |log_x x'| and d)

Set b_t := (1/4) kappa (1-t) > 0. Then g(x') >= b_t d(x, x')^2 for
d(x, x') < r_t, which is exactly (8.p).

UNIFORMITY IN (x, p) AND IN t. The constant b_t only depends on kappa
and t, both fixed. The radius r_t depends on third derivatives of the
branch costs c_s and c_t, which are uniformly bounded on the compact
graph Gamma_u: both the branch at (x, sp) (shortened active velocity, in
(1/2) C subset I) and the branch at (x, tp) (graph velocity, in
[0, t] G_x subset I) are uniformly smooth, so the Taylor remainders and
radii are uniform in (x, p). On a compact subinterval [eps, 1-eps] of
(0, 1), the smoothed branch velocities stay in a fixed compact subset of
I, so kappa and r_t are uniform.

This proves (c) and completes Theorem 8.9. []


Collecting the results.

THEOREM (convexity of injectivity domains). Under weak MTW, for every
x in M, the closed minimizing domain G_x is convex and the open
injectivity domain I(x) = int G_x is convex. This is Theorem 8.7.

THEOREM (global support and intermediate geometry). Under weak MTW,
for every potential u with dual v:

  (i)  Every subgradient p in Du(x) is a minimizing velocity (p in G_x),
       and gives a global supporting inequality
         u(x') >= u(x) + c(x, exp_x p) - c(x', exp_x p) for every x'.
       For every 0 < t < 1, F_t: Gamma_u -> M is a homeomorphism with
       vectors t p in I(x) and pole the unique global minimizer of
       Q_t u. (Parts 8.5, 8.6.)

  (ii) For every dual pair (u, v) and every x, r, the lifted section
       S_x(r) = {p in G_x : u(x) + |p|^2/2 + v(exp_x p) <= r} is
       compact and convex, and satisfies
         diam S_x(r)^2 <= 8 (r + osc v). (Lemma 8.8.)

  (iii) For every 0 < t < 1, Q_t u = -Q_{1-t} v is C^{1,1}, with
        grad Q_t u(z) = -(1/t) log_z x_t(z); the pole and momentum are
        Lipschitz in z with constants depending only on M, g, t; and
        the uniform quadratic growth (8.p) holds. (Theorem 8.9.)

No density hypothesis is used. Time one retains the support and
minimizing-velocity conclusions; intermediate-time regularity and
one-to-one behavior are used only for 0 < t < 1.

This establishes both theorems.



The main proof rules out the first failure time T by showing F_T is a
homeomorphism, which sits on a topological input (Lemma 8.4: covering
plus homotopy to a homeomorphism). This appendix records a different
route to the same conclusion: instead of a covering argument, use a
degree computation.

It is stated as a conditional theorem. It reuses the earlier parts without
modification; only the local-injectivity, covering, and continuation steps are replaced.

A.1 THE CONDITIONAL STATEMENT.

THEOREM (alternative globalization). Let u be a potential and
0 < T < 1. Assume:
  (i) for every (x,p) in Gamma_u and every 0 < r < T, the velocity
      r p lies in I(x);
  (ii) every scaled graph vector T p, (x,p) in Gamma_u, is
      nonconjugate;
  (iii) for every (x,p) in Gamma_u, x is a local minimum of
      x' -> u(x') + c_T(x', exp_x(T p));
  (iv) F_T : Gamma_u -> M is open.
Then F_T is a homeomorphism. Its pole at every endpoint is the unique
global minimizer of Q_T u, and every T p lies in I(x).

A.2 LOCAL QUADRATIC GROWTH AT A TERMINAL TIME.

LEMMA A.2. Under hypotheses (i) and (ii), for every (x,p) in Gamma_u
with z = exp_x(T p), there are b, rho > 0 such that every x' with
d(x,x') < rho satisfies

  u(x') + c_T(x', z) >= u(x) + c_T(x, z) + b d(x,x')^2.        (A.a)

PROOF. This is exactly the argument of the intermediate-regime lemma (c), run at time T
instead of t. Split the active velocities a_i at a time s with T < s < 1
(which lies further out but still inside (0,1)); use hypothesis (i) to
make s a_i lie in I(x); the transverse-slack Lemma 7.8 supplies
H_T(p) - sum_i m_i H_s(a_i) >= kappa (s - T) on the perpendicular of
the active span, and H_T(p_i) - H_s(p_i) >= kappa (s - T) on each
original active ray. Adding the finite-active lower supports (7.c) and
the closed selected divided branch (as in the intermediate-regime argument (c)) yields a smooth
lower support h to x' -> u(x') + c_T(x', z) - u(x) - c_T(x, z) near
x, tangent to 0 at x = x, with Hess h(x) >= kappa (s - T) Id on a full
neighborhood. Taylor on a small ball gives (A.a). []

A.3 OPENNESS.

LEMMA A.3. Under hypotheses (i), (ii) and (A.a), the projection
F_T : Gamma_u -> M is open.

PROOF. Fix (x,p) in Gamma_u and z = F_T(x,p). Choose a small closed
ball B about x inside the neighborhood of (A.a). For z' near z,
minimize G_{z'}(x') := u(x') + c_T(x', z') over x' in B. Because (A.a)
gives a positive boundary gap at z' = z, for z' close enough to z the
minimizer stays in the interior of B. As z' -> z, any minimizer of
G_{z'} on B tends to x, since x is the unique minimizer of G_z on B
(again by (A.a)). Stationarity at the minimizer gives

  p' := -D_x c_T(x', z')  in  Du(x'),

and first variation on the divided branch gives exp_{x'}(T p') = z'.
So every (x', p') is a graph point F_T^{-1}(z') near (x,p). Since z'
ranges over a neighborhood of z, F_T is open at (x,p). []

A.4 JACOBIAN SIGN AND DEGREE ONE.

The argument proceeds in three steps: local Minty coordinates, a sign calculation,
and an area-formula argument.

Minty coordinates. Take local coordinates on a chart of M, write p as a
covector, and choose a > 0 small enough that h(x) := |x|^2/2 + a u(x)
is strongly convex on the chart ball. Then

  q := x + a p

parametrizes the graph locally (a proximal parametrization): for each q
near the reference value, maximize q . x - h(x) on a small closed ball;
strong convexity makes the maximizer unique and Lipschitz in q, hence
interior for q near the reference, and x(q) is its gradient. Set
p(q) = (q - x(q)) / a. This gives a bi-Lipschitz chart on the graph.

Jacobian sign. Rademacher's theorem applies to such a chart; at almost
every point define

  X = D_q x >= 0,     P = D_q p = (Id - X) / a,

both symmetric, both nonnegative, commuting. Let Z = D_q F_T and let
Ascr = D^2_{xx} c_T(x, F_T(q)) be the source Hessian of the divided
cost at the graph point. Differentiating the identity -D_x c_T(x,
F_T) = T p in q gives

  Z = (-D^2_{xz} c_T)^{-1} (T P + Ascr X).                 (A.b)

Local minimality (iii) implies

  X (T P + Ascr X) >= 0.                                 (A.c)

Here is the sign form's derivation without second derivatives of x(q):
along a straight line q + lambda xi in the chart,

  d/dlambda u(x_lambda) = <p_lambda, x'_lambda>

holds almost everywhere; expanding x_lambda = x + lambda X xi + o(lambda),
p_lambda = p + lambda P xi + o(lambda), and integrating the quadratic
contribution of the polar p_lambda against x'_lambda produces

  u(x_lambda) - u(x) - <p, x_lambda - x> = (lambda^2/2) <P xi, X xi> + o(lambda^2).

Adding T times the expansion of c_T(x_lambda, z), linear term
-T <p, x_lambda - x> and quadratic term (lambda^2/2) <Ascr X xi, X xi>,
the linear terms cancel and (iii) forces (A.c).

Split into ker X and its orthogonal complement. In those blocks,
T P + Ascr X is triangular with kernel block (T/a) Id, and (A.c) makes
the complementary block positive semidefinite after multiplication by
the positive definite X. So

  det(T P + Ascr X) >= 0,      with strict sign on nonsingular blocks.

The other factor (-D^2_{xz} c_T)^{-1} in (A.b) also has positive
determinant for compatible orientations: it is (inverse exponential
differential) times the metric identification, whose sign starts at
positive 1 at time 0 and cannot change along a minimizing ray before a
conjugate time (hypothesis (ii)).

Degree and area formula. For 0 < eps < T, F_eps : Gamma_u -> M is a
homeomorphism (short-time lemma). Transfer to M via H_r : = F_r o F_eps^{-1},
eps <= r <= T; these are Lipschitz and form a homotopy from the identity
to H_T. The same computation at the small time eps gives positive
signed Jacobian J_{H_T} >= 0 almost everywhere. (At eps, semiconvexity
and the positive cost Hessian make each stationary branch a local
minimum without needing (iii).)

The signed degree identity, valid for Lipschitz maps by approximating
in W^{1,n} and applying Stokes' theorem to smooth approximations
uniformly close to H_T, gives

  integral_M h^* omega = integral_M omega

for every smooth top form omega. Applying the Lipschitz area formula
in manifold charts gives

  integral_M J_{H_T} dvol = vol(M),
  integral_M N(y, H_T) dvol(y) = vol(M),

where N counts preimages, allowed infinite. Surjectivity of F_T
(hypothesis + degree identity + compactness of M, as in the continuation section's
first paragraph) gives N >= 1 everywhere, and the integral identity
forces N = 1 almost everywhere. Openness (Lemma A.3) applied to two
distinct preimages of a common y would force N >= 2 on a nonempty open
set, contradiction. So H_T is injective.

Nonorientability. Lift to the orientation double cover and apply the
same argument: uniqueness of homotopy lifting makes every lift commute
with the deck transformation, and deck equivariance passes injectivity
downstairs. So F_T is injective in either case.

A.5 PUTTING IT TOGETHER.

If F_T is a homeomorphism (by A.4), then for each z = F_T(x,p):

  - any global minimizer x' of u + c_T(.,z) has, by Lemma 7.9, every
    minimizing log w in L_{x'}(z) in T Du(x'), so (x', w/T) is a graph
    point mapping to z;
  - injectivity forces (x', w/T) = (x, p), so x' = x and
    L_x(z) = {T p};
  - by (ii) and Lemma 5.3, T p lies in I(x).

So under hypotheses (i)-(iv) at time T, the same conclusions as the covering and time-one sections hold: F_T is a homeomorphism, T p in I(x). Combined with the
first-failure analysis, no failure time exists in (0,1),
and the convexity theorem follows.

A.6 WHAT THE APPENDIX DOES NOT DO.

It does not remove the conjugacy section: the nonconjugacy of scaled active hulls
(Claim 8.2) is still needed to make the branch at T p smooth in the
degree computation. It simply replaces the (compactness + covering)
argument of the local-injectivity and covering steps with the (Minty coordinates + degree) argument
above. The two arguments have the same hypothesis set and give the same
conclusion.

END OF DOCUMENT