Sharp One-Third Stability of Brenier Maps

Proof. The first-index choice is Borel because its level sets are given by finitely many strict and non-strict affine inequalities. Merge repeated slopes, retaining the largest intercept for each slope, and write the resulting intercept as c(y). Ties between distinct slopes lie in a finite union of hyperplanes. Outside this null set, the maximizing affine function remains strictly maximal in a neighborhood, so its slope is the gradient of u.

For every transport plan \pi from \rho to \lambda, the inequality x\cdot y+c(y)\le u(x) gives

The graph plan of T attains equality. Since the two marginals fix the integrals of |x|^2 and |y|^2, maximizing the displayed scalar product is equivalent to minimizing quadratic cost. Equality for any optimal plan requires it to be concentrated on pairs (x,y) with x\cdot y+c(y)=u(x). The maximizing slope is unique for \rho-almost every x, so the plan is concentrated on the graph of T. This proves uniqueness of the plan.□

Proof. For 0<a<1/2, put b=a/2 and define

Let \mu_a=(\nabla u_a)_\#\rho and \nu_a=(\nabla\widetilde u_a)_\#\rho, with any fixed first-index selection on the null tie sets. Their slopes are, respectively, -e_1,e_1,0 and -e_1,e_1,be_2, all in the fixed set Y. By Lemma 2.1, these gradients are the unique optimal maps to their laws.

Since a/2\le a+bx_2\le3a/2<1, the central cells are, up to null boundaries,

Tilting the central strip preserves its mass but changes which points receive a central or an outer slope. Figure 1 shows the symmetric difference where this reassignment occurs.

On A_a, the first map is zero; on its complement it is \operatorname{sign}(x_1)e_1. The second map equals be_2 on B_a and \operatorname{sign}(x_1)e_1 on its complement. Under \rho, the coordinates are independent and uniform on [-1,1]. On the slice x_2=t, the second central interval has probability a+bt, and each outer interval has probability (1-a-bt)/2. Averaging over t gives

Both targets have three distinct atoms of positive mass.

The coupling that fixes the outer atoms and moves the central atom from 0 to be_2 has squared cost ab^2. Conversely, every point in the support of \mu_a has second coordinate zero. Every coupling \pi of the two targets therefore satisfies

Consequently,

The same matching coupling costs ab for W_1, while every coupling has cost at least \int|y_2-z_2|\,d\pi=ab. Thus

The two central intervals on the slice x_2=t are nested, and their symmetric difference has conditional probability b|t|. Thus

The first coordinate of the map difference contributes the indicator of that symmetric difference, and its second coordinate contributes b^2 on B_a. Orthogonality gives the pointwise identity

Since \rho(B_a)=a, this proves

The remaining d-2 coordinates integrate out, so all computations hold in every fixed dimension d\ge2.

Substituting b=a/2 into (2.3) and (2.5) gives

For every \alpha>1/3, their ratio is

The source, target container, and number of atoms stay fixed, proving the proposition.□

Proof. We first record the geometric facts that permit differentiation for an arbitrary convex body. The boundary of a full-dimensional compact convex set has zero volume: contractions toward an interior point lie in the interior and their volumes tend to the full volume. The same argument applies within an affine subspace. Moreover, if a hyperplane H meets \operatorname{int}K, then

Indeed, choose p\in\operatorname{int}K\cap H. A relative interior point z\ne p of the section lies strictly between p and a point of the section beyond z. A strict convex combination with the ambient interior point p lies in \operatorname{int}K. The reverse inclusion is immediate. It follows that \partial K\cap H has zero (d-1)-dimensional measure.

Since M_i>0, cell i contains an interior point of K at which its affine function is strictly maximal: remove the boundary of K and the finite union of tie planes from the positive-volume cell. Strictly active points for i and j give opposite signs of their affine difference, so H_{ij} meets \operatorname{int}K. Also, H_{ij} and H_{ik} cannot coincide for three distinct indices. Coincidence would make their affine differences proportional. The three affine functions would then lie on one affine line, with one a strict convex combination of the other two; that function could never be strictly maximal. Hence the intersections H_{ij}\cap H_{ik} are empty or have dimension at most d-2.

We next prove the differential formulas. For a continuous function f:\R^d\to\R, write

Only f=1 and f(x)=x_k will be needed. Perturb (c,y) by h(r,v), with h\downarrow0, and telescope the difference of the products of indicators one factor at a time. On bounded K, the term in which the j-th factor changes is supported in |\ell_{ij}(x)|\le Ch, with C fixed for the configuration and direction. Put n_{ij}=(y_i-y_j)/|y_i-y_j| and use coordinates

Both z and t can be restricted to fixed bounded sets. The factor h in the volume element cancels the difference quotient. Outside

a surface-null set by the preceding geometric observations, all remaining indicators converge to their values at z. The changed factor converges for almost every (z,t) to

Its integral in t is (r_i-r_j+z\cdot(v_i-v_j))/|y_i-y_j|. Dominated convergence therefore gives

Applying the same argument in the opposite direction supplies the two-sided derivative. Taking f=1,x_1,\ldots,x_d gives (3.2) and (3.3).

For completeness, these derivatives are continuous under joint changes of sites and intercepts. Identify a nearby equality plane with the fixed H_{ij} as an affine graph in the normal direction n_{ij}. The graph maps and their surface Jacobians converge uniformly on a common bounded integration region. The face-defining indicators converge outside the same surface-null sets used above. The remaining integrands and the positive denominators |y_i-y_j| converge as well. Dominated convergence proves continuity of each coefficient of the differential, including those containing z_kz_l. Thus all coordinate partial derivatives exist and are continuous, which yields joint C^1 regularity. The admissible parameter set is open: the masses themselves are continuous by dominated convergence away from the original tie hyperplanes.

To prove connectivity, fix strictly active interior points in any two cells. They may be chosen so that the first point p avoids all equality planes and the second point q avoids all equality planes and the affine spans of p with every triple equality set. These are finitely many proper affine subsets, so they cannot cover a strictly active open region. The segment [p,q] lies in \operatorname{int}K and meets no triple equality set. At any change of active index along it, precisely two affine functions are maximal. The other inequalities are strict, so a small relatively open disk in their equality plane belongs to the common face. That face has positive area and gives an edge of the graph. The successive active indices therefore give a graph path between the chosen cells.

Finally, symmetry of the face coefficients gives

Connectivity identifies the kernel as the constant vectors. Symmetry then identifies the range as their orthogonal complement, as claimed.□

Proof. The case N=1 has c_1=0, so assume N\ge2. On the normalization space H_m=\{c\in\R^N:\sum_i m_i c_i=0\}, minimize the convex function

Choose R with |x|\le R on K, and set S=\max_i|y_i|. On H_m,

Positivity of all the weights implies that \max_i c_i tends to infinity as |c|\to\infty within H_m: an upper bound on all coordinates and the weighted mean-zero identity also bound every coordinate below. Hence \mathcal F_y is coercive on H_m and attains its minimum.

Distinct sites give an almost-everywhere unique maximizing index for every c. Differentiation of the maximum under the integral, justified by bounded difference quotients, shows

At a minimum on H_m, this gradient lies in \operatorname{span}\{m\}. Its coordinate sum is zero because the masses and weights each sum to one. Since \sum_i m_i=1, the gradient must vanish. Thus a normalized solution of (3.6) exists. Conversely, every such solution is a minimizer by convexity.

At any solution all cells have positive mass, so Proposition 3.1 applies. The intercept derivative of the mass residual is the restriction

It is an isomorphism: both spaces have dimension N-1, and the only constant vector in H_m is zero. The finite-dimensional implicit function theorem therefore gives a locally unique C^1 solution as the sites vary. In particular, each solution is locally isolated for its fixed sites. If two normalized solutions existed, their segment would consist of minimizers of the convex objective, contradicting this local isolation. Global uniqueness follows, and the local C^1 solution branches agree wherever they overlap. This proves the claimed C^1 dependence on the sites. Only the invertibility of the restricted Laplacian is used here; no quantitative bound on its inverse is needed.□

Proof. We parameterize the two uniform laws by successive one-dimensional quantiles on the same cube. Their diagonal derivatives have constant products. Averaging the two maps and substituting coordinates successively will give the density bound.

We need the boundary observation from the proof of Proposition 3.1 for arbitrary positive-dimensional affine slices, not only hyperplanes. The same segment-extension argument shows that a relative interior point of a slice of U meeting \operatorname{int}U is an ambient interior point: unless it equals a chosen ambient interior point in the slice, it lies strictly between that point and a farther point of the section. The contraction argument for convex boundaries, applied within the slice, then shows that its intersection with \partial U has zero slice volume.

For 0\le k<d, let

Thus p_0=|U|. Write D_k for the projection of \operatorname{int}U onto its first k coordinates. Each p_k is positive and continuous on D_k. For k<d, continuity follows by dominated convergence: at a prefix in D_k, the preceding boundary property makes the indicators of the fibers converge almost everywhere as the prefix varies, and boundedness of U provides a common integrable bound. For k=d the assertion is immediate. The fiber integrals are Borel functions on their full domains.

Given s=(s_1,\ldots,s_d)\in(0,1)^d, construct X(s) recursively. For a previously constructed prefix \xi=(X_1,\ldots,X_{k-1})\in D_{k-1}, let X_k be the quantile at level s_k of the density

Fubini’s theorem shows that this density integrates to one. It is positive and continuous on the bounded open interval \{t:(\xi,t)\in D_k\}, and vanishes outside that interval. Its cumulative distribution function is therefore strictly increasing from zero to one there. This defines the quantile uniquely, keeps the new prefix in D_k, and gives

For each fixed earlier parameter prefix, X_k is C^1 in s_k. The conditional cumulative distribution functions are Borel in their arguments, so comparison at rational points shows that their quantiles are Borel. Thus the whole construction is measurable. With s uniform on the cube, successive conditioning gives the uniform law on U. The diagonal derivatives telescope to

Construct Z(s) in the same way for V, using the same parameters. For H=(X+Z)/2, the arithmetic–geometric mean inequality yields

We justify substitution using only the stated regularity in each coordinate. For a nonnegative Borel function g on \R^d, fix a=(s_1,\ldots,s_{d-1}). One-dimensional substitution in the strictly increasing C^1 function s_d\mapsto H_d(a,s_d), followed by enlargement of its image interval to \R, gives

Here each H_k(a) uses only the first k entries of a. The integral of g in its last variable is again a nonnegative Borel function. The earlier derivative factors depend only on earlier parameters. Tonelli’s theorem therefore permits multiplication by their product and integration in a. Repeating this argument backwards gives

All derivative factors are Borel, as also follows from their explicit formulas above. No differentiability in earlier parameters or boundedness of the derivatives near the boundary of the cube is required. Combining the last two inequalities proves

which is the asserted measure domination.□

Proof of Lemma 4.1. Fix the intercept direction q and hold the sites fixed. For sufficiently small s>0, let P_i^- and P_i^+ be the cells at c-sq and c+sq, respectively, and write

These masses are positive by continuity from Proposition 3.1. The perturbed cells are compact convex sets of positive volume. Couple their uniform probability measures by Lemma 4.2, writing X_i\in P_i^-, Z_i\in P_i^+, and D_i=\E|X_i-Z_i|^2. For each competing index j, the defining inequalities give

Averaging shows that (X_i+Z_i)/2 satisfies the i-cell inequalities at c; convexity also places it in K. Its law is supported on P_i. Since |P_i^-|=|K|\alpha_i and |P_i^+|=|K|\beta_i, the midpoint bound has exactly the normalization

Use the nonnegative function \Phi(x)=R^2-|x|^2 on K, and set A_i^-=\E\Phi(X_i) and A_i^+=\E\Phi(Z_i). The identity

and the cellwise measure domination imply

The last equality uses the partitions at the two perturbed intercepts; all three partitions have null overlaps because the sites are distinct.

Put \delta_i=\alpha_i-\beta_i and

Subtracting the averaged endpoint terms in the preceding inequality gives

Here 0\le A_i^\pm\le R^2, and

Moreover, since |X_i|,|Z_i|\le R,

Cauchy–Schwarz therefore yields

Using \frac R2\sqrt{\mathcal A\mathcal B} \le\mathcal A/8+R^2\mathcal B/2 and rearranging, we obtain

This argument includes the cases where either quantity vanishes.

The cell-moment difference is

where the notation suppresses the fixed sites. Consequently,

For this fixed finite configuration and fixed direction q, continuity allows s to be chosen small enough that every \alpha_i,\beta_i,\gamma_i lies between M_i/2 and 2M_i. Set \mathcal E=\sum_i\delta_i^2/M_i. These comparisons give \alpha_i^2/M_i\le8\gamma_i and \mathcal B\le2\mathcal E. It follows that

Divide by (2s)^2 and let s decrease to zero. By Proposition 3.1, \Delta B_i/(2s)\to-D B_i[q,0] and \delta_i/(2s)\to-D M_i[q,0], which proves the claim.

The permitted threshold for s may depend on the direction and the finite configuration, including its smallest mass. Only the uniform constant 162 remains after taking the derivative limit. Thus the estimate has no dependence on the number of cells, their masses, or the separation of the sites.□

Proof. Choose an optimal finite coupling of the targets. After deleting zero weights and combining identical pairs, write it as

Finite-dimensional compactness gives existence of such a coupling. Set

Then

Optimality implies

Indeed, a negative scalar product would permit swapping equal positive portions of the masses at these two coupling pairs, decreasing their quadratic cost. For a=y_i^0-y_j^0 and b=y_i^1-y_j^1,

The last inequality holds because the endpoint pairs are distinct. Thus the sites are distinct at every interior time, even if some endpoint sites coincide.

By Proposition 3.2, for 0<t<1 there are unique intercepts c_i(t), normalized by

whose cells have masses M_i(t)=m_i. These intercepts are C^1 in t. Let r_i=c_i'(t). In particular,

All derivatives in the next calculation are taken at this fixed interior configuration.

Differentiate the fixed-mass constraints using Proposition 3.1. For every intercept direction q, symmetry of the mass and moment face coefficients gives

To see the symmetry directly, the mass part of \sum_iq_iDM_i[r,v] is \sum_{i<j}g_{ij}(q_i-q_j)(r_i-r_j). Its site part is \sum_{i<j}(q_i-q_j)b_{ij}\cdot(v_i-v_j), which equals \sum_iv_i\cdot DB_i[q,0].

The range statement in Proposition 3.1, together with (5.4), permits a choice of q satisfying

No bound on this q is needed. Put E_r=\sum_i m_ir_i^2. Using (5.5), weighted Cauchy–Schwarz, (5.2), and Lemma 4.1, we obtain

Consequently

This includes E_r=0. If N=1, the normalization gives r_1=0, and the same conclusion is immediate.

Define

On compact time intervals inside (0,1), this function is uniformly Lipschitz in time for x\in K. At a strict maximum its time derivative is x\cdot v_i+r_i. For each fixed time, the exceptional tie set has zero source measure. Fubini therefore identifies this derivative for almost every (t,x). Since its active cells have masses m_i,

The fundamental theorem of calculus and Minkowski’s inequality imply

It remains to justify the endpoint maps without imposing separation of their sites. For each fixed i, (5.6) gives

Hence c_i(t) has finite limits at 0 and 1. This individual estimate is used only for endpoint existence; its mass dependence does not enter (5.7). The finite maxima converge uniformly on K to their endpoint maxima u_0,u_1, so that inequality extends to the endpoints.

At either endpoint, merge repeated slopes by retaining their largest intercept. Outside a finite union of hyperplanes there is a unique maximizing slope. For any such x, all maximizing slopes at approaching interior times converge to this endpoint slope. Otherwise a subsequence with a fixed maximizing index would contradict the strict gap at the endpoint. The interior slope law is \sum_i m_i\delta_{y_i(t)}, and all slopes are bounded by L. Bounded convergence against continuous tests shows that the endpoint slope laws are \mu and \nu. By Lemma 2.1, these slopes are the unique optimal maps to their laws. Taking t=0,t'=1 in (5.7) proves the proposition.□

Proof. Fix j and write

Almost every nonempty coordinate slice of K is an interval [\alpha,\beta] on which the restriction of each u_i is convex and L-Lipschitz. Its derivative exists almost everywhere, is monotone, and has absolute value at most L. Fubini therefore gives all coordinate derivatives almost everywhere in K. For either function u, convexity gives, at points where both derivatives exist,

If \beta-\alpha\ge h, cancellation of translated integrals gives

The coordinates transverse to the slice have been suppressed here. If the slice length is less than h, its allowed portion is empty. Thus, in all cases, integrating \delta_u^2\le 2L\delta_u over slices and then over the orthogonal projection yields

The excluded portion of any slice has length at most h, so

There we use |\partial_j f|\le 2L.

On the allowed set, both x and x+he_j belong to K. Translation invariance of Lebesgue measure and (a-b)^2\le 2a^2+2b^2 give

Since \partial_jf=D_{j,h}f-\delta_{u_0}+\delta_{u_1}, the inequality (a+b+c)^2\le 3(a^2+b^2+c^2) and (6.2) imply

Summing over j proves (6.1). All projection measures are finite because K is compact. The slice argument applies to every h>0, including values larger than some or all slice lengths.

The coordinate derivatives form the full gradient almost everywhere. Indeed, at an interior point x where all partials of a convex function u exist, set p_j=\partial_j u(x) and q=\|v\|_1 for a small nonzero vector v. The point x+v is the convex combination of x+\operatorname{sign}(v_j)q e_j with weights |v_j|/q, omitting zero weights. The finitely many coordinate derivative limits and convexity give u(x+v)-u(x)\le p\cdot v+o(q). Apply this bound to -v and use midpoint convexity to obtain the reverse bound. Since q\le\sqrt d\,|v|, the function is differentiable at x with gradient p. The boundary of K has zero volume, as proved in Proposition 3.1, so this applies almost everywhere to both u_i.□

Proof. Write w=W_2(\mu,\nu). By Proposition 5.1, the maps have convex, L-Lipschitz maximum potentials u_0,u_1 satisfying

If w>0, apply Lemma 6.1 with h=w^{2/3}. The resulting bound on the squared map norm is C_*^2w^{2/3}. Taking its square root proves the claim. If w=0, the potential difference has zero L^2(\rho) norm, and sending h to zero in (6.1) gives the same conclusion.□

Proof. Compactness of Y gives the finite nets. Enumerating each net and choosing the first closest point gives a Borel selection with |Q_n(y)-y|\le\epsilon_n. Put \lambda_n=(Q_n)_\#\lambda, discard any zero-mass sites, and let T_n=T_{\lambda_n}. These finite maps exist by Proposition 3.2 and Lemma 2.1. The coupling induced by y\mapsto(Q_n(y),Q_m(y)) gives

By Corollary 6.2, (T_n) is Cauchy in L^2(\rho). Let S be its limit and choose a subsequence converging almost everywhere. Its limit lies in Y almost everywhere because Y is closed. Modifying S on a null set gives a Borel map with values in Y. For any continuous \phi:Y\to\R, bounded convergence and uniform continuity give

Here and below a limit along the chosen subsequence is understood where needed. It follows that S_\#\rho=\lambda.

To prove optimality directly, choose finite maximum potentials u_n for T_n and subtract a constant so that u_n(x_*)=0 at a fixed x_*\in K. Their slopes lie in Y, so they are L-Lipschitz and |u_n|\le L\diam(K) on K. Arzelà–Ascoli gives a further subsequence converging uniformly on K to a convex, L-Lipschitz function u. Intersect the full-measure sets on which each of the countably many finite-map supporting inequalities holds with the set on which the selected subsequence of T_n converges. On this common set,

Passing to the limit gives, simultaneously for every z\in K,

Define the restricted convex conjugate

It is finite and continuous, and hence bounded on Y. The defining inequality and (6.4) give

For any competing map V with V_\#\rho=\lambda, the integral of u(x)+u^*(V(x)) is fixed by the marginals. Thus (6.5) shows that S maximizes \int_Kx\cdot V(x)\,d\rho(x). The identity

proves quadratic optimality.

If V has the same optimal cost, its nonnegative Fenchel gap u(x)+u^*(V(x))-x\cdot V(x) has integral zero. Equality and the definition of u^* imply u(z)\ge u(x)+V(x)\cdot(z-x) for every z\in K at almost every x. On almost every interior point of K, all coordinate partials of u exist: on each coordinate interval the one-sided derivatives of a convex function are monotone, and Fubini applies. At such a point x, a supporting slope p must satisfy

Both limits equal \partial_j u(x), so the supporting slope is unique. The differentiability argument in the proof of Lemma 6.1 identifies it with \nabla u(x). The boundary of K has zero volume by Proposition 3.1; hence V=S almost everywhere. The same integrated inequality also proves optimality among arbitrary transport plans. Equality forces their target coordinate to be this unique supporting slope over almost every source point, so the optimal plan is the one induced by S.

We have identified the L^2 limit as the unique map T_\lambda. The original sequence was Cauchy, so the asserted convergence holds for the full sequence.□

Proof of Theorem 1.1. Use the same finite nets and selections for \mu and \nu, and set \mu_n=(Q_n)_\#\mu, \nu_n=(Q_n)_\#\nu. For any coupling \pi of \mu,\nu, its image under (Q_n,Q_n) is a coupling of \mu_n,\nu_n. The triangle inequality in L^2(\pi) gives

Taking the infimum over \pi yields W_2(\mu_n,\nu_n)\le W_2(\mu,\nu)+2\epsilon_n. Apply Corollary 6.2 and then use the strong L^2(\rho) convergence from Proposition 6.3 to conclude

The constant in (6.3) depends only on K and an enclosing radius for Y. In particular it is independent of atom counts, masses, site separations, or target densities. No convexity of Y is required: the site interpolation used earlier stays in the ball of radius L, and the discretizations take their values in Y. The argument includes a singleton Y, for which all target maps coincide. The sharpness assertion was proved in Proposition 2.2.□