Proof of The Support of an Optimal Coupling is Cyclically Monotone

Each result cited below is universally quantified over the data in its own statement. Finite sums of real numbers are those of Finite Sum Notation in a Field, and for $N\in\mathbb{N}$ we write $\Sigma_{N}$ for the finite sum $\sum_{i=1}^{N}1$ of $N$ copies of $1$, a positive real number by claim 6 of Properties of Finite Sums and claim 6 of Elementary Order Arithmetic in an Ordered Field. We use twice that a finite nonempty set of real numbers has a least and a greatest member, which follows from claim 9 of Elementary Order Arithmetic in an Ordered Field together with the trichotomy of the order and induction on the number of members, the inductive set being the set of those $p\in\mathbb{N}$ for which every family of $p$ real numbers has a least and a greatest member. Write $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$ for every $\sigma\in\mathcal{P}(\mathbb{R}^{d+d})$ by Couplings of Two Probability Measures on Euclidean Space and Their Quadratic Cost §cost.

Suppose, for contradiction, that $\operatorname{supp}\pi$ is not cyclically monotone. By Cyclically Monotone Subset of a Doubled Euclidean Space §monotone there are $N\in\mathbb{N}$ and $z_{1},\dots,z_{N}\in\operatorname{supp}\pi$ such that, writing $x_{i}=\mathrm{pr}_{1}(z_{i})$ and $y_{i}=\mathrm{pr}_{2}(z_{i})$ for $i\in[N]$ and $x_{N+1}=x_{1}$,

Let $\beta$ be a positive real with $4\beta=2\sum_{i=1}^{N}y_{i}\cdot(x_{i+1}-x_{i})$. For $i\in[N]$ write $i^{-}=i-1$ if $2\le i$ and $1^{-}=N$; the map $i\mapsto i^{-}$ is a permutation of $[N]$, its inverse being $i\mapsto i+1$ for $i<N$ and $N\mapsto1$.

1. The algebraic identity. Expanding $\lVert a-b\rVert^{2}=\lVert a\rVert^{2}-2\,a\cdot b+\lVert b\rVert^{2}$, which follows from claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$, and using additivity of finite sums (claim 2 of Properties of Finite Sums) together with the invariance of a finite sum under the reindexing $i\mapsto i^{-}$ (Invariance of Finite Sums and Products under Reindexing by a Permutation), which gives both $\sum_{i=1}^{N}\lVert y_{i^{-}}\rVert^{2}=\sum_{i=1}^{N}\lVert y_{i}\rVert^{2}$ and $\sum_{i=1}^{N}x_{i}\cdot y_{i^{-}}=\sum_{i=1}^{N}x_{i+1}\cdot y_{i}$, one obtains

2. Choice of the radius. Let $L$ be the greatest of the $2N$ real numbers $\lVert x_{i}-y_{i}\rVert$ and $\lVert x_{i}-y_{i^{-}}\rVert$, $i\in[N]$, and let $\varepsilon$ be a positive real with $\varepsilon\le1$ and $\Sigma_{N}\,\varepsilon\,(8L+8)<4\beta$; such an $\varepsilon$ exists by claim 3 of The Archimedean Property of the Real Numbers, applied to the positive number $4\beta\,(\Sigma_{N}(8L+8))^{-1}$, together with claim 9 of Elementary Order Arithmetic in an Ordered Field to secure $\varepsilon\le1$ as well. For $i\in[N]$ put $A_{i}=B(z_{i},\varepsilon)\in\mathcal{B}(\mathbb{R}^{d+d})$ and $m_{i}=\pi(A_{i})$, a real number with $0<m_{i}\le1$ by Support of a Borel Measure on a Metric Space §support and claim 2 of Basic Properties of a Measure. Let $m$ be the least of $m_{1},\dots,m_{N}$ and put $\theta=m\,\Sigma_{N}^{-1}$, a positive real.

3. The normalised pieces and their marginals. For $i\in[N]$ let $h_{i}=m_{i}^{-1}\mathbf{1}_{A_{i}}$, a measurable function from $\mathbb{R}^{d+d}$ to $[0,\infty)$, and let $\pi_{i}$ be the measure with density $h_{i}$ with respect to $\pi$, as in claim 3 of that lemma. For $B\in\mathcal{B}(\mathbb{R}^{d+d})$ the product $\mathbf{1}_{B}h_{i}$ is $m_{i}^{-1}\mathbf{1}_{A_{i}\cap B}$, so claim 1 of Linearity and Monotonicity of the Lebesgue Integral and The Integral of an Indicator Function is the Measure of the Set give

In particular $\pi_{i}\in\mathcal{P}(\mathbb{R}^{d+d})$ and $\pi_{i}(\mathbb{R}^{d+d}\setminus A_{i})=0$. Put $\alpha_{i}=(\mathrm{pr}_{1})_{\#}\pi_{i}$ and $\beta_{i}=(\mathrm{pr}_{2})_{\#}\pi_{i}$, probability measures on $\mathbb{R}^{d}$ by claim 1 of Image Measures, Measures with Densities, and Change of Variables.

If $z\in A_{i}$ then $\mathrm{pr}_{1}(z)-x_{i}=\mathrm{pr}_{1}(z-z_{i})$, because the coordinate projections are compatible with differences by Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §projections and Concatenation Identifies a Product of Euclidean Spaces with a Euclidean Space, so $\lVert\mathrm{pr}_{1}(z)-x_{i}\rVert\le\lVert z-z_{i}\rVert\le\varepsilon$ 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 and claim 2 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$; likewise $\lVert\mathrm{pr}_{2}(z)-y_{i}\rVert\le\varepsilon$. Hence $\alpha_{i}(\mathbb{R}^{d}\setminus\bar{B}(x_{i},\varepsilon))=0$ and $\beta_{i}(\mathbb{R}^{d}\setminus\bar{B}(y_{i},\varepsilon))=0$.

4. The competitor. Let $g=1-\theta\sum_{i=1}^{N}h_{i}$. For every $z$ one has $m_{i}^{-1}\le m^{-1}$, since $0<m\le m_{i}$ and inversion reverses the order on the positive reals by claims 7 and 10 of Elementary Order Arithmetic in an Ordered Field, so $h_{i}(z)\le m^{-1}$ by claim 5 of Elementary Arithmetic in an Ordered Field; summing the resulting nonnegative differences $m^{-1}-h_{i}(z)$ with claims 2, 3 and 5 of Properties of Finite Sums gives $\theta\sum_{i=1}^{N}h_{i}(z)\le\theta\,\Sigma_{N}\,m^{-1}=1$; thus $g$ is a measurable function from $\mathbb{R}^{d+d}$ to $[0,\infty)$, and the measure $\nu_{g}$ with density $g$ with respect to $\pi$ satisfies, by the computation of step 3,

For $i\in[N]$ let $\sigma_{i}$ be the measure with constant density $\theta$ with respect to the product measure $\alpha_{i}\boxtimes\beta_{i^{-}}$ of Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §product, so that $\sigma_{i}(B)=\theta\,(\alpha_{i}\boxtimes\beta_{i^{-}})(B)$ by the same computation, and put $\sigma_{N+1}=\nu_{g}$.

For $i\in[N+1]$ let $(X_{i},\mathcal{F}_{i},\mu_{i})$ be the transport of $(\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\}$, as in claim 2 of Assembly of Measure Spaces: Restriction, Transport, One-Point Spaces, and Countable Disjoint Unions. The sets $X_{i}$ are pairwise disjoint, so claim 4 of that lemma provides their countable disjoint union $(X_{\sqcup},\mathcal{F}_{\sqcup},\mu_{\sqcup})$, and the map $W:X_{\sqcup}\to\mathbb{R}^{d+d}$ with $W((z,i))=z$ is measurable by claim 4(b) there. Let $\tilde\pi=W_{\#}\mu_{\sqcup}$ be its image measure; since $W^{-1}(B)$ meets $X_{i}$ in the transport of $B$, whose $\mu_{i}$-measure is $\sigma_{i}(B)$ by claim 2 of Assembly of Measure Spaces: Restriction, Transport, One-Point Spaces, and Countable Disjoint Unions, claim 4(a) there gives

5. The competitor is a coupling. Taking $B=\mathbb{R}^{d+d}$ gives $\tilde\pi(\mathbb{R}^{d+d})=1-\theta\,\Sigma_{N}+\theta\,\Sigma_{N}=1$. For $A\in\mathcal{B}(\mathbb{R}^{d})$, using $\pi_{i}(\mathrm{pr}_{1}^{-1}(A))=\alpha_{i}(A)$ and $(\alpha_{i}\boxtimes\beta_{i^{-}})(\mathrm{pr}_{1}^{-1}(A))=\alpha_{i}(A)$ from Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §product,

and for $B\in\mathcal{B}(\mathbb{R}^{d})$, using $\sum_{i=1}^{N}\beta_{i^{-}}(B)=\sum_{i=1}^{N}\beta_{i}(B)$ by Invariance of Finite Sums and Products under Reindexing by a Permutation,

Hence $\tilde\pi\in\Pi(\mu,\nu)$ by Couplings of Two Probability Measures on Euclidean Space and Their Quadratic Cost §coupling.

6. The cost of the competitor. All the costs below are finite by Couplings on Euclidean Space: Product Coupling, Swap, Finiteness of the Cost, Push-Forward Couplings, Modifying One Marginal, Quantisation, Gluing over a Finitely Supported Measure, and the Lipschitz Bound §cost-finite. By claim 2 of Image Measures, Measures with Densities, and Change of Variables applied to $W$, claims 4(c) and 2 of Assembly of Measure Spaces: Restriction, Transport, One-Point Spaces, and Countable Disjoint Unions (the latter transporting each $\int_{X_{i}}$ back to an integral against $\sigma_{i}$) and claim 3 of Image Measures, Measures with Densities, and Change of Variables,

We estimate the two families of integrals. Let $p,q\in\mathbb{R}^{d}$ and let $z\in\mathbb{R}^{d+d}$ satisfy $\lVert\mathrm{pr}_{1}(z)-p\rVert\le\varepsilon$ and $\lVert\mathrm{pr}_{2}(z)-q\rVert\le\varepsilon$. Writing $a=\mathrm{pr}_{1}(z)-\mathrm{pr}_{2}(z)$ and $b=p-q$, claims 5 and 6 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ give $\lVert a-b\rVert\le2\varepsilon$, and the same two claims give both $\lVert a\rVert-\lVert b\rVert\le\lVert a-b\rVert$ and $\lVert b\rVert-\lVert a\rVert\le\lVert a-b\rVert$, hence $\bigl|\lVert a\rVert-\lVert b\rVert\bigr|\le2\varepsilon$ by claim 6 of Properties of the Absolute Value in an Ordered Field. Since $\lVert b\rVert\le L$ and therefore $\lVert a\rVert\le L+2\varepsilon$, claim 4 of Properties of the Absolute Value in an Ordered Field gives

the first equality by the factorisation of a difference of squares (claim 4 of Zero Products and Elementary Identities in a Field) and claim 4 of Properties of the Absolute Value in an Ordered Field, and the last step using $\varepsilon\le1$. By step 3 this applies $\pi_{i}$-almost everywhere with $(p,q)=(x_{i},y_{i})$ and $(\alpha_{i}\boxtimes\beta_{i^{-}})$-almost everywhere with $(p,q)=(x_{i},y_{i^{-}})$, the second because the marginals of the product measure are $\alpha_{i}$ and $\beta_{i^{-}}$ by Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §product. Integrating these bounds with claims 1 and 2 of Linearity and Monotonicity of the Lebesgue Integral and The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison, and summing,

the second term accounting for the $2N$ integrals, each of which deviates from the corresponding squared distance by at most $\varepsilon(4L+4)$.

7. The contradiction. By step 1 the bracket equals $-4\beta$, and by the choice of $\varepsilon$ in step 2 we have $\Sigma_{N}\,\varepsilon\,(8L+8)<4\beta$; multiplying that inequality by the positive number $\theta$ (claim 10 of Elementary Order Arithmetic in an Ordered Field) and adding $-4\theta\beta$ to both sides (claim 1 there) gives

Thus $I(\tilde\pi)<I(\pi)$, and $I(\pi)=W_{2}(\mu,\nu)^{2}$ because $\pi$ is optimal. This contradicts $W_{2}(\mu,\nu)^{2}\le I(\tilde\pi)$, which holds for every member of $\Pi(\mu,\nu)$ by The Quadratic Wasserstein Distance on Euclidean Space §distance and applies to $\tilde\pi$ by step 5.

Therefore $\operatorname{supp}\pi$ is cyclically monotone, which is claim 1 of the statement.