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 (v), 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 (ii).

Suppose, for contradiction, that $\operatorname{supp}\pi$ is not cyclically monotone. By Cyclically Monotone Subset of a Doubled Euclidean Space (i) 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}$,

$$0<\sum_{i=1}^{N}y_{i}\cdot(x_{i+1}-x_{i}).$$

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 Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square and The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite, 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

$$\sum_{i=1}^{N}\lVert x_{i}-y_{i^{-}}\rVert^{2}-\sum_{i=1}^{N}\lVert x_{i}-y_{i}\rVert^{2} =2\sum_{i=1}^{N}y_{i}\cdot(x_{i}-x_{i+1})=-4\beta .$$

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 (i) 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 Integrability Criterion and The Integral of an Indicator Function is the Measure of the Set give

$$\pi_{i}(B)=m_{i}^{-1}\,\pi(A_{i}\cap B).$$

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 and Measures with a Density: Measures, Integrals 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 (i) 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 (i) and claim 2 of Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square; 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,

$$\nu_{g}(B)=\pi(B)-\theta\sum_{i=1}^{N}\pi_{i}(B)\qquad(B\in\mathcal{B}(\mathbb{R}^{d+d})).$$

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 (iii), 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

$$\tilde\pi(B)=\sum_{i=1}^{N+1}\sigma_{i}(B)=\pi(B)-\theta\sum_{i=1}^{N}\pi_{i}(B)+\theta\sum_{i=1}^{N}(\alpha_{i}\boxtimes\beta_{i^{-}})(B).$$

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 (iii),

$$\tilde\pi\bigl(\mathrm{pr}_{1}^{-1}(A)\bigr)=\pi\bigl(\mathrm{pr}_{1}^{-1}(A)\bigr)=\mu(A),$$

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,

$$\tilde\pi\bigl(\mathrm{pr}_{2}^{-1}(B)\bigr)=\pi\bigl(\mathrm{pr}_{2}^{-1}(B)\bigr)=\nu(B).$$

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

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 (iii). By claim 2 of Image Measures and Measures with a Density: Measures, Integrals 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 and Measures with a Density: Measures, Integrals and Change of Variables,

$$I(\tilde\pi)=I(\pi)-\theta\sum_{i=1}^{N}\int c\,d\pi_{i}+\theta\sum_{i=1}^{N}\int c\,d(\alpha_{i}\boxtimes\beta_{i^{-}}).$$

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 Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square 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

$$\bigl|c(z)-\lVert b\rVert^{2}\bigr|=\bigl|\lVert a\rVert-\lVert b\rVert\bigr|\cdot\bigl(\lVert a\rVert+\lVert b\rVert\bigr)\le2\varepsilon\,(2L+2\varepsilon)\le\varepsilon\,(4L+4),$$

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 (iii). Integrating these bounds with claims 1 and 2 of Linearity and Monotonicity of the Lebesgue Integral, and the Integrability Criterion and The Lebesgue Integral and Null Sets (iii), and summing,

$$I(\tilde\pi)-I(\pi)\le\theta\Bigl(\sum_{i=1}^{N}\lVert x_{i}-y_{i^{-}}\rVert^{2}-\sum_{i=1}^{N}\lVert x_{i}-y_{i}\rVert^{2}\Bigr)+\theta\,\Sigma_{N}\,\varepsilon\,(8L+8),$$

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

$$I(\tilde\pi)-I(\pi)<-4\theta\beta+4\theta\beta=0 .$$

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 (i) and applies to $\tilde\pi$ by step 5.

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