Proof of Brenier's Theorem: Optimal Couplings out of an Absolutely Continuous Measure are Induced by a Unique Map

Each result cited below is universally quantified over the data in its own statement. Write $j:\mathbb{N}\to\mathbb{R}$ for the canonical map of $\mathbb{R}$ (the letter $\iota$ being reserved for the concatenation map of Probability Measures on Euclidean Space and Random Vectors: Standing Notation §pairs), and $c$ for the Borel function on $\mathbb{R}^{d+d}$ with $c(z)=\lVert\mathrm{pr}_{1}(z)-\mathrm{pr}_{2}(z)\rVert^{2}$ of Probability Measures on Euclidean Space and Random Vectors: Standing Notation §pairs, so that $I(\sigma)=\int_{\mathbb{R}^{d+d}}c\,d\sigma$ by Couplings of Two Probability Measures on Euclidean Space and Their Quadratic Cost §cost.

0. The projections are continuous. For $z,z'\in\mathbb{R}^{d+d}$ one has $\mathrm{pr}_{1}(z)-\mathrm{pr}_{1}(z')=\mathrm{pr}_{1}(z-z')$, because by Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space the concatenation map reads off components and differences of points of a Euclidean space are taken componentwise (Difference, Dot Product, and Orthogonality in $\mathbb{R}^n$). Hence $\lVert\mathrm{pr}_{1}(z)-\mathrm{pr}_{1}(z')\rVert\le\lVert z-z'\rVert$ by the norm bound of Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §projections, so by claim 2 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ the map $\mathrm{pr}_{1}$ is continuous, the choice $\delta=\varepsilon$ serving at every point.

1. A closed cyclically monotone set of full measure. Let $\pi\in\Pi(\mu,\nu)$ be optimal. By Probability Measures on Euclidean Space and Random Vectors: Standing Notation §measures it is a Borel measure on $(\mathbb{R}^{d+d},d_{E})$; let $\Gamma=\operatorname{supp}\pi$ be its support. By The Support of an Optimal Coupling is Cyclically Monotone §monotone the set $\Gamma$ is cyclically monotone, and by The Support of a Borel Measure is Closed, and Carries Full Measure on a Separable Space §closed it is closed and Borel. The metric space $(\mathbb{R}^{d+d},d_{E})$ is separable by Euclidean Space is a Separable Metric Space §separable, so The Support of a Borel Measure is Closed, and Carries Full Measure on a Separable Space §full gives $\pi(\mathbb{R}^{d+d}\setminus\Gamma)=0$, whence $\pi(\Gamma)=1$ by claim 3 of Basic Properties of a Measure. In particular $\Gamma\ne\emptyset$.

2. The potential. By Rockafellar's Theorem: a Cyclically Monotone Set Lies in the Subdifferential of a Convex Function there are a nonempty convex set $C\subseteq\mathbb{R}^{d}$ and a function $\psi:C\to\mathbb{R}$, convex on $C$, with $\mathrm{pr}_{1}(z)\in C$ by Rockafellar's Theorem: a Cyclically Monotone Set Lies in the Subdifferential of a Convex Function §domain and $\mathrm{pr}_{2}(z)\in\partial_{C}\psi(\mathrm{pr}_{1}(z))$ by Rockafellar's Theorem: a Cyclically Monotone Set Lies in the Subdifferential of a Convex Function §subgradient, for every $z\in\Gamma$.

3. The interior of the domain has full measure. Put $G=\operatorname{int}C$, open by The Interior is the Largest Open Subset and convex by The Interior of a Convex Set is Convex and Carries Each of Its Borel Subsets up to a Null Set §convex-interior. For $k\in\mathbb{N}$ let $\Gamma_{k}=\Gamma\cap\bar{B}(0,j(k))$ if $0<j(k)$, and $\Gamma_{k}=\emptyset$ otherwise. Each nonempty $\Gamma_{k}$ is closed and bounded, hence compact by Heine-Borel Theorem in $\mathbb{R}^n$, so $\mathrm{pr}_{1}(\Gamma_{k})$ is compact by step 0 and Continuous Image of a Compact Space is Compact, and therefore belongs to $\mathcal{B}(\mathbb{R}^{d})$ by Compact Subsets of a Metric Space are Closed and Borel. By claim 1 of The Archimedean Property of the Real Numbers every $z\in\mathbb{R}^{d+d}$ satisfies $\lVert z\rVert<j(k)$ for some $k\in\mathbb{N}$, so $\Gamma=\bigcup_{k\in\mathbb{N}}\Gamma_{k}$ and

is the image $\mathrm{pr}_{1}(\Gamma)$ and belongs to $\mathcal{B}(\mathbb{R}^{d})$. By step 2, $E\subseteq C$; and $\Gamma\subseteq\mathrm{pr}_{1}^{-1}(E)$, so

using $(\mathrm{pr}_{1})_{\#}\pi=\mu$ and claim 2 of Basic Properties of a Measure; hence $\mu(E)=1$. By The Interior of a Convex Set is Convex and Carries Each of Its Borel Subsets up to a Null Set §null, $\lambda_{d}(E\setminus G)=0$, and $E\setminus G$ is Borel, so $\mu(E\setminus G)=0$ because $\mu$ is absolutely continuous. Claim 3 of Basic Properties of a Measure now gives $\mu(E\cap G)=1$, and claim 2 there gives $\mu(G)=1$.

4. Differentiability off a Borel null set. Let $\phi:G\to\mathbb{R}$ be the restriction of $\psi$ to $G$; it is convex on $G$, the defining inequality of Convex Real-Valued Function on a Convex Subset of $\mathbb{R}^n$ holding for points of $G\subseteq C$. Since $G$ is open, $G$ is itself an open subset of $G$ containing each of its points, so every $x\in G$ is an interior point of $G$; hence A Convex Function is Lipschitz on a Ball around an Interior Point, applied to the convex set $G$ and the convex function $\phi$, gives positive reals $\rho,L$ with $\bar{B}(x,\rho)\subseteq G$ and $|\phi(y)-\phi(y')|\le L\lVert y-y'\rVert$ for $y,y'\in\bar{B}(x,\rho)$. Thus $\phi$ is locally Lipschitz on $G$, and Rademacher's Theorem in $\mathbb{R}^n$ §locally-lipschitz, read with $m=1$, shows that the set of points of $G$ at which $\phi$ is not differentiable is null; let $N_{0}\in\mathcal{B}(\mathbb{R}^{d})$ with $\lambda_{d}(N_{0})=0$ contain it, as that notion of nullity provides. Put $D=G\setminus N_{0}\in\mathcal{B}(\mathbb{R}^{d})$. Then $\phi$ is differentiable at every point of $D$, and $\mu(N_{0})=0$ by absolute continuity, so claim 3 of Basic Properties of a Measure gives $\mu(D)=\mu(G)=1$.

5. The map. Let $x\in D$. Since $G$ is open and convex and $\phi$ is convex on $G$ and differentiable at $x$, claim 4 of Elementary Calculus of the Subdifferential of a Convex Function gives a point $T_{0}(x)\in\mathbb{R}^{d}$, read off from the derivative matrix of $\phi$ at $x$ as described there, with $\partial_{G}\phi(x)=\{T_{0}(x)\}$. This defines $T_{0}:D\to\mathbb{R}^{d}$.

$T_{0}$ is continuous on $D$: given $x\in D$ and a positive real $\varepsilon$, claim 5 of Elementary Calculus of the Subdifferential of a Convex Function supplies a positive $\delta$ such that every $x'\in G$ with $\lVert x'-x\rVert<\delta$ and every $q\in\partial_{G}\phi(x')$ satisfy $\lVert q-T_{0}(x)\rVert<\varepsilon$; taking $x'\in D$ and $q=T_{0}(x')$ gives the requirement of Continuous Map Between Metric Spaces. By The Metric Subspace: Continuity, the Borel Sigma-Algebra, and the Restriction of a Borel Measure §continuity-map the map $T_{0}$ is then continuous from the metric space $(D,d_{E})$ to $(\mathbb{R}^{d},d_{E})$, hence measurable with respect to $\mathcal{B}(D)$ and $\mathcal{B}(\mathbb{R}^{d})$ by claim 3 of Borel Measurability and Bounded Integration on a Metric Space; and $\mathcal{B}(D)=\{B\in\mathcal{B}(\mathbb{R}^{d}):B\subseteq D\}$ by The Metric Subspace: Continuity, the Borel Sigma-Algebra, and the Restriction of a Borel Measure §borel-subset, $D$ being Borel.

Let $T:\mathbb{R}^{d}\to\mathbb{R}^{d}$ agree with $T_{0}$ on $D$ and take the value $0_{\mathbb{R}^{d}}$ on $\mathbb{R}^{d}\setminus D$. For $B\in\mathcal{B}(\mathbb{R}^{d})$ the preimage $T^{-1}(B)$ is $T_{0}^{-1}(B)$ if $0_{\mathbb{R}^{d}}\notin B$ and $T_{0}^{-1}(B)\cup(\mathbb{R}^{d}\setminus D)$ otherwise; in both cases it belongs to $\mathcal{B}(\mathbb{R}^{d})$. So $T$ is Borel.

6. The coupling is concentrated on the graph of $T$. Let $\Gamma_{T}$ be the graph of $T$ in the sense of A Coupling Concentrated on the Graph of a Borel Map is the Push-Forward by That Map. Put $\Gamma'=\Gamma\cap\mathrm{pr}_{1}^{-1}(D)$. Since $\pi(\Gamma)=1$ and $\pi(\mathrm{pr}_{1}^{-1}(D))=\mu(D)=1$, claims 3 and 4 of Basic Properties of a Measure give $\pi(\Gamma')=1$. Let $z\in\Gamma'$ and $x=\mathrm{pr}_{1}(z)\in D\subseteq G\subseteq C$. By step 2, $\mathrm{pr}_{2}(z)\in\partial_{C}\psi(x)$, that is $\psi(u)\ge\psi(x)+\mathrm{pr}_{2}(z)\cdot(u-x)$ for every $u\in C$; restricting $u$ to $G$ gives $\mathrm{pr}_{2}(z)\in\partial_{G}\phi(x)=\{T(x)\}$ by Subdifferential of a Real-Valued Function on a Convex Subset of $\mathbb{R}^n$ §subdifferential and step 5. Hence $\mathrm{pr}_{2}(z)=T(\mathrm{pr}_{1}(z))$, so $\Gamma'\subseteq\Gamma_{T}$ and $\pi(\Gamma_{T})=1$. By A Coupling Concentrated on the Graph of a Borel Map is the Push-Forward by That Map §graph,

7. Claim 1. Existence of $T$ is step 6. Let now $T$ be any Borel map with $\pi=(\mathrm{id},T)_{\#}\mu$. By Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §projections and Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §pairing one has $\mathrm{pr}_{2}\circ(\mathrm{id},T)=T$, so for $B\in\mathcal{B}(\mathbb{R}^{d})$

that is $T_{\#}\mu=\nu$. The change-of-variables formula of Probability Measures on Euclidean Space and Random Vectors: Standing Notation §pushforward, applied to the nonnegative Borel function $y\mapsto\lVert y\rVert^{2}$, then gives

which is finite because $\nu\in\mathcal{P}_{2}(\mathbb{R}^{d})$ (The Second Moment of a Probability Measure on Euclidean Space and the Probability Measures with Finite Second Moment §space).

8. Claim 2. The data $G$, $\phi$, $D$ and $T$ of steps 3 to 6 have exactly the listed properties: $G$ is open and convex with $\mu(G)=1$, $\phi$ is convex on $G$, $D$ is Borel with $D\subseteq G$ and $\mu(D)=1$, $\phi$ is differentiable at every point of $D$, $\partial_{G}\phi(x)=\{T(x)\}$ there, and $\pi=(\mathrm{id},T)_{\#}\mu$.

9. Claim 3. Let $\pi$ and $\pi'$ be optimal couplings of $\mu$ and $\nu$. Let $\sigma_{1}$ and $\sigma_{2}$ be the measures with constant density $\tfrac12$ with respect to $\pi$ and to $\pi'$, in the sense of claim 3 of Image Measures, Measures with Densities, and Change of Variables; by The Integral of an Indicator Function is the Measure of the Set and claim 1 of Linearity and Monotonicity of the Lebesgue Integral they satisfy $\sigma_{1}(B)=\tfrac12\pi(B)$ and $\sigma_{2}(B)=\tfrac12\pi'(B)$. For $i\in\{1,2\}$ transport $(\mathbb{R}^{d+d},\mathcal{B}(\mathbb{R}^{d+d}),\sigma_{i})$ along the bijection $z\mapsto(z,i)$ onto $X_{i}=\mathbb{R}^{d+d}\times\{i\}$ (claim 2 of Assembly of Measure Spaces: Restriction, Transport, One-Point Spaces, and Countable Disjoint Unions), form the countable disjoint union of the two resulting measure spaces (claim 4 there), and let $\hat\pi$ be the image measure of that union under the map $(z,i)\mapsto z$, which is measurable by claim 4(b). Then, by claims 2 and 4(a) of Assembly of Measure Spaces: Restriction, Transport, One-Point Spaces, and Countable Disjoint Unions,

so $\hat\pi$ is a probability measure with $(\mathrm{pr}_{1})_{\#}\hat\pi=\mu$ and $(\mathrm{pr}_{2})_{\#}\hat\pi=\nu$, that is $\hat\pi\in\Pi(\mu,\nu)$. By claim 2 of Image Measures, Measures with Densities, and Change of Variables, claim 4(c) of Assembly of Measure Spaces: Restriction, Transport, One-Point Spaces, and Countable Disjoint Unions and claim 3 of Image Measures, Measures with Densities, and Change of Variables,

so $\hat\pi$ is optimal. By claim 1 there is a Borel $S$ with $\hat\pi=(\mathrm{id},S)_{\#}\mu$; since $(\mathrm{id},S)(x)$ lies in the graph $\Gamma_{S}$ for every $x$, $\hat\pi(\Gamma_{S})=\mu(\mathbb{R}^{d})=1$. From $\tfrac12\pi(B)\le\hat\pi(B)$ we get $\pi(\mathbb{R}^{d+d}\setminus\Gamma_{S})\le2\hat\pi(\mathbb{R}^{d+d}\setminus\Gamma_{S})=0$, so $\pi(\Gamma_{S})=1$ and A Coupling Concentrated on the Graph of a Borel Map is the Push-Forward by That Map §graph gives $\pi=(\mathrm{id},S)_{\#}\mu$. The same argument gives $\pi'=(\mathrm{id},S)_{\#}\mu$, so $\pi=\pi'$.

10. Claim 4. Let $T,T'$ be Borel maps such that $(\mathrm{id},T)_{\#}\mu$ and $(\mathrm{id},T')_{\#}\mu$ are optimal couplings of $\mu$ and $\nu$. By claim 3 they are equal. Let $\Gamma_{T'}$ be the graph of $T'$. As in step 9, $(\mathrm{id},T')_{\#}\mu(\Gamma_{T'})=1$, while

because $(\mathrm{id},T)(x)=\iota(x,T(x))$ lies in $\Gamma_{T'}$ exactly when $T(x)=T'(x)$. Hence that set has $\mu$-measure $1$, and claim 3 of Basic Properties of a Measure gives $\mu(\{x\in\mathbb{R}^{d}:T(x)\ne T'(x)\})=0$.