Proof of Fibrewise Cyclical Monotonicity of a Noise-Optimal Coupling: Given the Tail, the Heads are Cyclically Monotone

Each result cited is universally quantified over the data in its own statement, and is applied below with the data named at each use.

Conventions. Write $Z=X\times X$; by Borel Sets of a Hilbert Space with an Orthonormal Basis: Coordinates, Determination by Finite-Dimensional Projections, and Pairs §product-sigma, $\mathcal{B}(Z)=\mathcal{B}(X)\otimes\mathcal{B}(X)$ and $\pi_{1},\pi_{2}$ are Borel. For $z\in Z$ we write $x=\pi_{1}(z)$, $y=\pi_{2}(z)$ and $z=(x,y)$. Since $\pi$ is a noise-optimal coupling, Noise-Optimal Couplings §optimal gives $\pi\in\Pi^{a}(\mu,\nu)$ and $I^{a}(\pi)=W_{a}(\mu,\nu)^{2}$; by Couplings of Finite Noise Cost and Their Noise Cost §finite and Couplings of Finite Noise Cost and Their Noise Cost §cost, $\pi(D_{a})=1$ and $I^{a}(\pi)=\int_{Z}c_{a}\,d\pi<\infty$; and by Couplings of Two Borel Probability Measures on a Hilbert Space and Their Quadratic Cost §coupling, $\pi\in\mathcal{P}(Z)$ with $(\pi_{1})_{\#}\pi=\mu$ and $(\pi_{2})_{\#}\pi=\nu$. As $c_{a}$ is Borel and nonnegative (The Noise Space is a Real Hilbert Space: Orthonormal Basis, Continuous Embedding, Partial Sums, Closed Balls and Borel Measurability §pairs) with finite integral, it is integrable with respect to $\pi$ by the criterion of Measure Spaces and the Lebesgue Integral: Standing Notation §integral. The image measure $\mu_{n}=(t_{n})_{\#}\pi$ is a probability measure on $(X,\mathcal{B}(X))$ by claim 1 of Image Measures, Measures with Densities, and Change of Variables. Write $p=p_{n}$ and let $q:X\to\mathbb{R}^{n}$ be $q(y)=(a_{1}^{-1}y_{1},\dots,a_{n}^{-1}y_{n})$. With the concatenation map $\iota=\iota^{n,n}$ and the projections $\mathrm{pr}_{1},\mathrm{pr}_{2}$ of Probability Measures on Euclidean Space and Random Vectors: Standing Notation §pairs, the description of $h_{n}$ in the statement and that of $\iota$ in Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets say that $h_{n}(z)=\iota(p(x),q(y))$, so that $\mathrm{pr}_{1}(h_{n}(z))=p(x)$ and $\mathrm{pr}_{2}(h_{n}(z))=q(y)$ by Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §projections. As recorded in the statement, the functions $x\mapsto x_{k}$ and $x\mapsto a_{k}^{-1}x_{k}$ on $X$ are Borel, and so are their composites with $\pi_{1}$ and $\pi_{2}$; hence $p$ and $q$ are Borel by claim 2 of The Borel Sigma-Algebra of a Euclidean Space as a Product, and Measurability of Projections, Sequentially Continuous Maps, and Open and Closed Sets (with claim 5 there). Real functions built from Borel ones by finitely many sums, constant multiples, products, minima and multiplications by indicators $\mathbf{1}_{A}$ of Borel sets $A$ are Borel by claims 1--4 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions, and a Borel function composed with a Borel map is Borel by claim 4 of Borel Measurability and Bounded Integration on a Metric Space; these two citations cover every such measurability assertion below. For a Borel measure $\lambda$ of finite total mass on a metric space, bounded Borel functions are $\lambda$-integrable and a constant $c$ has integral $c$ times the total mass, by claim 6 of Borel Measurability and Bounded Integration on a Metric Space; for a nonnegative bounded Borel function its integral as a nonnegative function and as an integrable function agree by claim 6(c) there, and for any nonnegative integrable function they agree because its negative part vanishes (Integrable Function and the Lebesgue Integral). Integrals of measurable functions with values in $[0,\infty]$ obey the additivity, homogeneity and monotonicity of claim 1 of Linearity and Monotonicity of the Lebesgue Integral, integrals of integrable functions obey its claim 2, and $\int\mathbf{1}_{A}\,d\lambda=\lambda(A)$ by The Integral of an Indicator Function is the Measure of the Set. When $N\in\mathbb{N}$ is fixed, indices $i\in[N]=\{1,\dots,N\}$ are read cyclically: the index $N+1$ means $1$ and the index $0$ means $N$.

Step 1 (the conditional kernel and a set $W_{0}$ of full measure). The space $Z$ is a real Hilbert space (Borel Probability Measures on a Real Hilbert Space with an Orthonormal Basis: Standing Notation §pairs), so $(Z,d)$ is complete by Real Hilbert Space §hilbert; it is separable by Properties of the Product of Two Real Inner Product Spaces §separable, applied with $E_{1}=E_{2}=X$, since $(X,d)$ is separable (Borel Probability Measures on a Real Hilbert Space with an Orthonormal Basis: Standing Notation §space). The map $t_{n}$ is Borel, as noted in the statement. Hence Conditional Kernels of a Borel Probability Measure on a Polish Space Given a Borel Map: Existence, Uniqueness and Concentration on the Fibres applies with its $(Z,d)$ our $(Z,d)$, its $(Y,d_{Y})$ our $(X,d)$, its $q$ our $t_{n}$, its $\pi$ our $\pi$, its $\nu$ our $\mu_{n}$ and its $\kappa$ our $\kappa$. Moreover the identity of The Conditional Kernel of a Probability Measure Given a Measurable Map §conditional-kernel with $A=X$, for which $t_{n}^{-1}(X)=Z$ and $\mathbf{1}_{X}=1$, gives

$$\pi(E)=\int_{X}\kappa(w,E)\,\mu_{n}(dw)\qquad(E\in\mathcal{B}(Z)).\qquad\text{(1.1)}$$

(a) By Conditional Kernels of a Borel Probability Measure on a Polish Space Given a Borel Map: Existence, Uniqueness and Concentration on the Fibres §fibres, the set $W^{(1)}$ of the $w\in X$ with $\kappa_{w}(t_{n}^{-1}(\{w\}))=1$ belongs to $\mathcal{B}(X)$ and $\mu_{n}(W^{(1)})=1$.

(b) The set $D_{a}$ belongs to $\mathcal{B}(Z)$ by The Noise Space is a Real Hilbert Space: Orthonormal Basis, Continuous Embedding, Partial Sums, Closed Balls and Borel Measurability §pairs, so $f=\mathbf{1}_{Z\setminus D_{a}}$ is a bounded Borel function on $Z$. By Conditional Kernels of a Borel Probability Measure on a Polish Space Given a Borel Map: Existence, Uniqueness and Concentration on the Fibres §bounded applied to this $f$, the function $e(w)=\int_{Z}f\,d\kappa_{w}=\kappa_{w}(Z\setminus D_{a})$ is Borel, bounded and nonnegative on $X$, and $\int_{X}e\,d\mu_{n}=\int_{Z}f\,d\pi=\pi(Z\setminus D_{a})=\pi(Z)-\pi(D_{a})=0$, the last step by Basic Properties of a Measure §differences. By The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §vanishing, the set $\{w:e(w)\neq0\}$ is $\mu_{n}$-null; it belongs to $\mathcal{B}(X)$ since $e$ is Borel, so it has measure $0$ by Null Set of a Measure and Basic Properties of a Measure §monotone. Hence $W^{(2)}=\{w:e(w)=0\}\in\mathcal{B}(X)$ has $\mu_{n}(W^{(2)})=1$ by Basic Properties of a Measure §differences, and $\kappa_{w}(D_{a})=1$ for $w\in W^{(2)}$ by the same clause.

(c) By Conditional Kernels of a Borel Probability Measure on a Polish Space Given a Borel Map: Existence, Uniqueness and Concentration on the Fibres §nonnegative applied to $f=c_{a}$, the set $N_{c}$ of the $w$ for which $c_{a}$ is not $\kappa_{w}$-integrable belongs to $\mathcal{B}(X)$, the function $g_{c}$ equal to $\int_{Z}c_{a}\,d\kappa_{w}$ off $N_{c}$ and to $0$ on $N_{c}$ is Borel, and, $c_{a}$ being $\pi$-integrable, $\mu_{n}(N_{c})=0$, $g_{c}$ is $\mu_{n}$-integrable and

$$I^{a}(\pi)=\int_{Z}c_{a}\,d\pi=\int_{X}g_{c}\,d\mu_{n}.\qquad\text{(1.2)}$$

Let $W_{0}=(W^{(1)}\cap W^{(2)})\setminus N_{c}\in\mathcal{B}(X)$. Its complement is contained in $(X\setminus W^{(1)})\cup(X\setminus W^{(2)})\cup N_{c}$, a union of three sets of $\mu_{n}$-measure $0$ (by Basic Properties of a Measure §differences for the first two), so $\mu_{n}(X\setminus W_{0})=0$ by Basic Properties of a Measure §subadditivity (applied to these three sets followed by empty sets) and Basic Properties of a Measure §monotone, and $\mu_{n}(W_{0})=1$ by Basic Properties of a Measure §differences. For $w\in X$ let $G_{w}=t_{n}^{-1}(\{w\})\cap D_{a}$, which belongs to $\mathcal{B}(Z)$ because $t_{n}^{-1}(\{w\})$ does (preamble of Conditional Kernels of a Borel Probability Measure on a Polish Space Given a Borel Map: Existence, Uniqueness and Concentration on the Fibres). For $w\in W_{0}$ the set $Z\setminus G_{w}$ is the union of $Z\setminus t_{n}^{-1}(\{w\})$ and $Z\setminus D_{a}$, both of $\kappa_{w}$-measure $0$ by (a), (b) and Basic Properties of a Measure §differences; so by Basic Properties of a Measure §subadditivity and Basic Properties of a Measure §differences

$$\kappa_{w}(Z\setminus G_{w})=0\quad\text{and}\quad\kappa_{w}(G_{w})=1\qquad(w\in W_{0}).\qquad\text{(1.3)}$$

For $w\in W_{0}$ the function $c_{a}$ is $\kappa_{w}$-integrable and $g_{c}(w)=\int_{Z}c_{a}\,d\kappa_{w}$, since $w\notin N_{c}$.

Step 2 (the cost on a fibre). Let $x\in X$. By Borel Probability Measures on a Real Hilbert Space with an Orthonormal Basis: Standing Notation §coordinates, $P_{n}x=p_{n}^{*}(p(x))=\sum_{j=1}^{n}x_{j}e_{j}$, so linearity of the inner product and orthonormality of $(e_{k})_{k\in\mathbb{N}}$ (Orthonormal Basis of a Real Hilbert Space §basis) give $\langle P_{n}x,e_{k}\rangle=x_{k}$ for $k\le n$ and $\langle P_{n}x,e_{k}\rangle=0$ for $k>n$. Hence the coordinates of $Q_{n}x=x-P_{n}x$ are $(Q_{n}x)_{k}=0$ for $k\le n$ and $(Q_{n}x)_{k}=x_{k}$ for $k>n$. The map $P_{n}$ is linear, because $\sum_{j\le n}(sx_{j}+tx'_{j})e_{j}=s\sum_{j\le n}x_{j}e_{j}+t\sum_{j\le n}x'_{j}e_{j}$ for $x,x'\in X$ and $s,t\in\mathbb{R}$; hence so is $Q_{n}$. The coordinates of $y-x$ are $y_{k}-x_{k}$.

(2a) Let $h\in X$ and $c_{h}=\sum_{k=1}^{n}a_{k}^{-1}h_{k}^{2}$. With the partial sums $S_{M}$ ($M\in\mathbb{N}$) of The Noise Space is a Real Hilbert Space: Orthonormal Basis, Continuous Embedding, Partial Sums, Closed Balls and Borel Measurability, the coordinates of $Q_{n}h$ just computed give $S_{M}(h)=c_{h}+S_{M}(Q_{n}h)$ for every $M\ge n$. By The Noise Space is a Real Hilbert Space: Orthonormal Basis, Continuous Embedding, Partial Sums, Closed Balls and Borel Measurability §partial-sums the sequences $(S_{M}(h))_{M\in\mathbb{N}}$ and $(S_{M}(Q_{n}h))_{M\in\mathbb{N}}$ are nondecreasing, so each is bounded above if and only if its terms with $M\ge n$ are, and then its least upper bound is that of those terms. Since those terms differ by the constant $c_{h}$, the same clause yields: $h\in X^{a}$ if and only if $Q_{n}h\in X^{a}$, and in that case, with $n_{a}$ as in The Noise Space is a Real Hilbert Space: Orthonormal Basis, Continuous Embedding, Partial Sums, Closed Balls and Borel Measurability §borel,

$$n_{a}(h)=|h|_{a}^{2}=c_{h}+|Q_{n}h|_{a}^{2}=\sum_{k=1}^{n}a_{k}^{-1}h_{k}^{2}+n_{a}(Q_{n}h).$$

(2b) Fix $w\in X$. Let $F_{w}=Q_{n}^{-1}(\{w\})$ and $Y_{w}=\{y\in X:Q_{n}y-w\in X^{a}\}$, and define $\psi,\varphi_{w}:X\to\mathbb{R}$ by

$$\psi(x)=\sum_{k=1}^{n}a_{k}^{-1}x_{k}^{2},\qquad\varphi_{w}(y)=\sum_{k=1}^{n}a_{k}^{-1}y_{k}^{2}+n_{a}(Q_{n}y-w).$$

The map $y\mapsto Q_{n}y-w$ satisfies $|(Q_{n}y-w)-(Q_{n}y'-w)|=|Q_{n}(y-y')|\le|y-y'|$ by Borel Sets of a Hilbert Space with an Orthonormal Basis: Coordinates, Determination by Finite-Dimensional Projections, and Pairs §continuity, so it is continuous, hence Borel by claim 3 of Borel Measurability and Bounded Integration on a Metric Space; $Q_{n}$ is Borel by Borel Sets of a Hilbert Space with an Orthonormal Basis: Coordinates, Determination by Finite-Dimensional Projections, and Pairs §continuity; the singleton $\{w\}$ is Borel (preamble of Conditional Kernels of a Borel Probability Measure on a Polish Space Given a Borel Map: Existence, Uniqueness and Concentration on the Fibres); and $X^{a}\in\mathcal{B}(X)$ and $n_{a}$ is Borel and nonnegative by The Noise Space is a Real Hilbert Space: Orthonormal Basis, Continuous Embedding, Partial Sums, Closed Balls and Borel Measurability §borel. Hence $F_{w},Y_{w}\in\mathcal{B}(X)$, and $\psi,\varphi_{w}$ are nonnegative Borel functions. We claim

$$F_{w}\times Y_{w}=G_{w},\qquad c_{a}(x,y)=\psi(x)+\varphi_{w}(y)-2\,p(x)\cdot q(y)\quad\text{for }(x,y)\in G_{w}.\qquad\text{(2.1)}$$

Indeed $t_{n}(x,y)=Q_{n}x$, so $(x,y)\in t_{n}^{-1}(\{w\})$ if and only if $x\in F_{w}$; and for $x\in F_{w}$ we have $Q_{n}(y-x)=Q_{n}y-w$, so by (2a) $y-x\in X^{a}$, that is $(x,y)\in D_{a}$, if and only if $y\in Y_{w}$. For $(x,y)\in G_{w}$, (2a) with $h=y-x$ gives $c_{a}(x,y)=n_{a}(y-x)=\sum_{k=1}^{n}a_{k}^{-1}(y_{k}-x_{k})^{2}+n_{a}(Q_{n}y-w)$, and $a_{k}^{-1}(y_{k}-x_{k})^{2}=a_{k}^{-1}x_{k}^{2}+a_{k}^{-1}y_{k}^{2}-2x_{k}(a_{k}^{-1}y_{k})$; summing over $k\le n$ and using $p(x)\cdot q(y)=\sum_{k=1}^{n}x_{k}(a_{k}^{-1}y_{k})$ (Difference, Dot Product, and Orthogonality in $\mathbb{R}^n$) gives (2.1).

Step 3 (two integration facts). (3a) Let $(S,\mathcal{S})$ be a measurable space, $r\in\mathbb{N}$, $\lambda_{1},\dots,\lambda_{r}$ finite measures on it and $\gamma_{1},\dots,\gamma_{r}$ real numbers such that $M(E)=\sum_{c=1}^{r}\gamma_{c}\lambda_{c}(E)\ge0$ for every $E\in\mathcal{S}$. Then $M$ is a finite measure; and if every $\gamma_{c}\ge0$, then $\int_{S}f\,dM=\sum_{c=1}^{r}\gamma_{c}\int_{S}f\,d\lambda_{c}$ in $[0,\infty]$ for every measurable $f:S\to[0,\infty]$. Proof: $M(\varnothing)=0$. Let $(E_{m})_{m\in\mathbb{N}}$ be pairwise disjoint members of $\mathcal{S}$ with union $E$. For each $c$, by countable additivity and the definition of the sum of a sequence in Measure, Measure Space, and Probability Measure, the partial sums $\sigma^{c}_{k}=\sum_{m\le k}\lambda_{c}(E_{m})$ are nondecreasing in $k$ with least upper bound $\lambda_{c}(E)\in\mathbb{R}$. Given $\varepsilon>0$ choose $k_{c}$ with $\sigma^{c}_{k_{c}}>\lambda_{c}(E)-\varepsilon$; then for $k\ge\max_{c}k_{c}$ we get $|\sum_{m\le k}M(E_{m})-M(E)|=|\sum_{c}\gamma_{c}(\sigma^{c}_{k}-\lambda_{c}(E))|\le\varepsilon\sum_{c}|\gamma_{c}|$. The partial sums $\sum_{m\le k}M(E_{m})$ are nondecreasing in $k$, as $M(E_{m})\ge0$; by the estimate, no partial sum exceeds $M(E)$ (a partial sum exceeding $M(E)$ by $t>0$ would force all later ones to exceed it by $t$, which the estimate with $\varepsilon\sum_{c}|\gamma_{c}|<t$ forbids), and they come within any $\varepsilon\sum_{c}|\gamma_{c}|$ of $M(E)$. So $M(E)$ is their least upper bound, that is $\sum_{m}M(E_{m})=M(E)$, and $M(S)<\infty$. Now let every $\gamma_{c}\ge0$ and let $f$ be measurable. For a nonnegative simple function $s=\sum_{l}b_{l}\mathbf{1}_{A_{l}}$ in standard representation, Simple Function and Its Integral gives $\int s\,dM=\sum_{l}b_{l}M(A_{l})=\sum_{c}\gamma_{c}\sum_{l}b_{l}\lambda_{c}(A_{l})=\sum_{c}\gamma_{c}\int s\,d\lambda_{c}$, all terms being real. By Approximation of Measurable Functions by Simple Functions §nonnegative choose nonnegative simple functions $s_{m}$ with $s_{m}\le s_{m+1}\le f$ and with $f$ the pointwise least upper bound of the $s_{m}$. By Monotone Convergence Theorem, applied to $M$ and to each $\lambda_{c}$, $\int f\,dM=\sup_{m}\sum_{c}\gamma_{c}J^{c}_{m}$ and $\int f\,d\lambda_{c}=\sup_{m}J^{c}_{m}$, where $J^{c}_{m}=\int s_{m}\,d\lambda_{c}$ is nondecreasing in $m$. Clearly $\sup_{m}\sum_{c}\gamma_{c}J^{c}_{m}\le\sum_{c}\gamma_{c}\sup_{m}J^{c}_{m}$. Conversely, if $\gamma_{c}>0$ and $\sup_{m}J^{c}_{m}=\infty$ for some $c$, the left side is unbounded, hence $\infty$; otherwise, given $\varepsilon>0$, monotonicity in $m$ provides one $m$ with $\gamma_{c}J^{c}_{m}>\gamma_{c}\sup_{m'}J^{c}_{m'}-\varepsilon$ for every $c$, so the left side is at least the right side minus $r\varepsilon$. This proves (3a).

(3b) Let $(S,d_{S})$ be a metric space, $\lambda$ a Borel measure on it with $\lambda(S)=1$, $A\in\mathcal{B}(S)$ with $\lambda(A)=1$, and $f:S\to\mathbb{R}$ a bounded Borel function with $f(s)>0$ for every $s\in A$. Then $\int_{S}f\,d\lambda>0$. Proof: $g=\mathbf{1}_{A}f$ is a bounded nonnegative Borel function equal to $f$ off $S\setminus A$, a set of measure $0$ by Basic Properties of a Measure §differences; so $\int f\,d\lambda=\int g\,d\lambda\ge0$ by The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison. If $\int g\,d\lambda=0$, then by The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §vanishing the set $\{g\neq0\}$, which contains $A$, would be null, so $\lambda(A)=0$ by Null Set of a Measure and Basic Properties of a Measure §monotone, a contradiction.

Step 4 (a countable family of rational cycles). For $s,t\in\mathbb{Q}^{n}$ let $\mathrm{Box}(s,t)=\{u\in\mathbb{R}^{n}:s_{k}<u_{k}<t_{k}\text{ for every }k\in[n]\}$. It is Euclidean open by Euclidean Open Box Criterion in $\mathbb{R}^n$ (for $u$ in it, take the least of the positive numbers $u_{k}-s_{k}$, $t_{k}-u_{k}$), hence belongs to $\mathcal{B}(\mathbb{R}^{n})$ by claims 4 and 5 of The Borel Sigma-Algebra of a Euclidean Space as a Product, and Measurability of Projections, Sequentially Continuous Maps, and Open and Closed Sets. For $N\in\mathbb{N}$ and points $u_{1},v_{1},\dots,u_{N},v_{N}$ of $\mathbb{R}^{n}$ let

$$G_{N}(u_{1},v_{1},\dots,u_{N},v_{N})=\sum_{i=1}^{N}v_{i}\cdot(u_{i+1}-u_{i}),\qquad u_{N+1}=u_{1}.$$

Let $\mathcal{T}$ be the set of pairs $\delta=(N,\omega)$ with $N\in\mathbb{N}$ and $\omega\in\mathbb{Q}^{4nN}$; $\omega$ is read as the list of the points $s_{i},t_{i},s'_{i},t'_{i}\in\mathbb{Q}^{n}$, $i\in[N]$, in consecutive blocks of $n$ entries, and we put $U_{i}^{\delta}=\mathrm{Box}(s_{i},t_{i})$ and $V_{i}^{\delta}=\mathrm{Box}(s'_{i},t'_{i})$. For each $N\in\mathbb{N}$ the set $\{N\}\times\mathbb{Q}^{4nN}$ is countable, because $\mathbb{Q}^{4nN}$ is (claim 3 of The Integers and the Rational Numbers are Countable) and a sequence exhausting $\mathbb{Q}^{4nN}$ yields one exhausting $\{N\}\times\mathbb{Q}^{4nN}$; so $\mathcal{T}$, their union, is countable by A Countable Union of Countable Sets is Countable, and, being nonempty, it is the set of terms of a sequence $(\delta_{m})_{m\in\mathbb{N}}$ by Countable Set. Let $\mathcal{Q}$ be the set of the $\delta=(N,\omega)\in\mathcal{T}$ such that $G_{N}(u_{1},v_{1},\dots,u_{N},v_{N})>0$ whenever $u_{i}\in U^{\delta}_{i}$ and $v_{i}\in V^{\delta}_{i}$ for every $i\in[N]$.

For $\delta\in\mathcal{Q}$ and $i\in[N]$, the set $\iota(U_{i}^{\delta}\times V_{i}^{\delta})$ belongs to $\mathcal{B}(\mathbb{R}^{n+n})$ by Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §product, so $B_{i}^{\delta}=h_{n}^{-1}(\iota(U_{i}^{\delta}\times V_{i}^{\delta}))$ belongs to $\mathcal{B}(Z)$, $h_{n}$ being Borel (statement); since $\iota$ is a bijection and $h_{n}(z)=\iota(p(x),q(y))$, a point $z$ lies in $B_{i}^{\delta}$ if and only if $p(x)\in U_{i}^{\delta}$ and $q(y)\in V_{i}^{\delta}$. Let $m_{i}^{\delta}(w)=\kappa(w,B_{i}^{\delta})$, a Borel function of $w\in X$ with values in $[0,1]$ by Probability Kernels Between Measurable Spaces §kernel; let $\eta_{\delta}=\min_{i\in[N]}m_{i}^{\delta}$, Borel with values in $[0,1]$; and let $K_{\delta}=W_{0}\cap\{w:\eta_{\delta}(w)>0\}\in\mathcal{B}(X)$. For $\delta\in\mathcal{T}\setminus\mathcal{Q}$ put $K_{\delta}=\varnothing$.

Main claim: $\mu_{n}(K_{\delta})=0$ for every $\delta\in\mathcal{Q}$. Steps 5--8 prove it by contradiction: we fix $\delta=(N,\omega)\in\mathcal{Q}$ with $\mu_{n}(K_{\delta})>0$ and drop the index $\delta$ from $U_{i},V_{i},B_{i},m_{i},\eta,K$.

Step 5 (the kernels). Since $\mu_{n}(K)>0=\mu_{n}(\varnothing)$, there is $w_{0}\in K$; then $m_{i}(w_{0})\ge\eta(w_{0})>0$, so $B_{i}\neq\varnothing$ and hence $U_{i}$ and $V_{i}$ are nonempty for every $i\in[N]$. Choosing $u_{i}\in U_{i}$ and $v_{i}\in V_{i}$ gives $G_{N}(u_{1},v_{1},\dots,u_{N},v_{N})>0$; this excludes $N=1$, as $G_{1}(u_{1},v_{1})=v_{1}\cdot(u_{1}-u_{1})=0$. So $N\ge2$. Let $L$ be $1$ plus the largest absolute value of an entry of $\omega$; then $|u_{k}|<L$ and $|v_{k}|<L$ for all $u\in U_{i}$, $v\in V_{i}$, $i\in[N]$ and $k\in[n]$.

For $i\in[N]$ let $r_{i}(w)=1/m_{i}(w)$ if $m_{i}(w)>0$ and $r_{i}(w)=0$ otherwise. It is Borel by the criterion of Measure Spaces and the Lebesgue Integral: Standing Notation §measurable: $\{r_{i}>c\}$ is $X$ for $c<0$, $\{m_{i}>0\}$ for $c=0$, and $\{m_{i}>0\}\cap\{m_{i}<1/c\}$ for $c>0$. For $w\in X$ and $E\in\mathcal{B}(Z)$ define

$$\alpha_{i}(w,E)=r_{i}(w)\,\kappa(w,E\cap B_{i})+\bigl(1-r_{i}(w)m_{i}(w)\bigr)\,\kappa(w,E).$$

For fixed $E$ this is Borel in $w$, as $\kappa(\cdot,E\cap B_{i})$ and $\kappa(\cdot,E)$ are (Probability Kernels Between Measurable Spaces §kernel). For fixed $w$: if $m_{i}(w)=0$ then $\alpha_{i}(w,\cdot)=\kappa_{w}$; if $m_{i}(w)>0$ then $1-r_{i}(w)m_{i}(w)=0$ and $\alpha_{i}(w,E)=r_{i}(w)\kappa_{w}(E\cap B_{i})=\int_{Z}\mathbf{1}_{E}\,r_{i}(w)\mathbf{1}_{B_{i}}\,d\kappa_{w}$, so $\alpha_{i}(w,\cdot)$ is the measure with density $r_{i}(w)\mathbf{1}_{B_{i}}$ with respect to $\kappa_{w}$ (claim 3 of that lemma), with total mass $r_{i}(w)m_{i}(w)=1$, and by the same claim, for every measurable $f:Z\to[0,\infty]$, and for every Borel $f:Z\to\mathbb{R}$ such that $f\mathbf{1}_{B_{i}}$ is $\kappa_{w}$-integrable (the integrability being then equivalent),

$$\int_{Z}f\,d\alpha_{i}(w,\cdot)=r_{i}(w)\int_{Z}f\,\mathbf{1}_{B_{i}}\,d\kappa_{w}\qquad(m_{i}(w)>0).\qquad\text{(5.1)}$$

So $\alpha_{i}$ is a probability kernel from $(X,\mathcal{B}(X))$ to $(Z,\mathcal{B}(Z))$; write $\alpha_{i}^{w}=\alpha_{i}(w,\cdot)$. For $A\in\mathcal{B}(X)$ let $\lambda_{i}(w,A)=\alpha_{i}(w,\pi_{1}^{-1}(A))$ and $\lambda'_{i}(w,A)=\alpha_{i}(w,\pi_{2}^{-1}(A))$; for each $w$ these are the image measures of $\alpha_{i}^{w}$ under the Borel maps $\pi_{1},\pi_{2}$, probability measures by claim 1 of Image Measures, Measures with Densities, and Change of Variables, and they are Borel in $w$ because $\pi_{1}^{-1}(A),\pi_{2}^{-1}(A)\in\mathcal{B}(Z)$. So $\lambda_{i},\lambda'_{i}$ are probability kernels from $(X,\mathcal{B}(X))$ to $(X,\mathcal{B}(X))$; write $\lambda_{i}^{w},\lambda_{i}'^{w}$. By The Product of Two Probability Kernels is a Probability Kernel §kernel, applied with its $(W,\mathcal{W}),(Y,\mathcal{Y}),(Z,\mathcal{Z})$ all equal to $(X,\mathcal{B}(X))$, its $\alpha$ our $\lambda_{i+1}$ and its $\beta$ our $\lambda'_{i}$, and by $\mathcal{B}(X)\otimes\mathcal{B}(X)=\mathcal{B}(Z)$, the function $\beta_{i}(w,E)=(\lambda_{i+1}^{w}\otimes\lambda_{i}'^{w})(E)$ is a probability kernel from $(X,\mathcal{B}(X))$ to $(Z,\mathcal{B}(Z))$; write $\beta_{i}^{w}=\lambda_{i+1}^{w}\otimes\lambda_{i}'^{w}$, the product measure. By Borel Sets of a Hilbert Space with an Orthonormal Basis: Coordinates, Determination by Finite-Dimensional Projections, and Pairs §product-measure, $(\pi_{1})_{\#}\beta_{i}^{w}=\lambda_{i+1}^{w}$ and $(\pi_{2})_{\#}\beta_{i}^{w}=\lambda_{i}'^{w}$. Finally let $\vartheta(w)=N^{-1}\mathbf{1}_{K}(w)\eta(w)$, a Borel function with values in $[0,1]$.

Step 6 (computations on one fibre). Fix $w\in K$. Then $w\in W_{0}$, $m_{i}(w)\ge\eta(w)>0$ for every $i$, so (5.1) applies to every $\alpha_{i}^{w}$, and $\vartheta(w)=\eta(w)/N>0$. In this step $w$ is suppressed from $\alpha_{i}^{w},\lambda_{i}^{w},\lambda_{i}'^{w},\beta_{i}^{w}$. For $j\in[N]$ let $F_{j}=\{x\in F_{w}:p(x)\in U_{j}\}$ and $Y_{j}=\{y\in Y_{w}:q(y)\in V_{j}\}$, Borel sets as $p,q$ are Borel and $U_{j},V_{j}$ are Borel. By Step 4 and (2.1), $B_{j}\cap G_{w}=F_{j}\times Y_{j}$.

(6a) Concentration. By (5.1) with $f=\mathbf{1}_{Z\setminus(F_{j}\times Y_{j})}$ and by (1.3), $\alpha_{j}(Z\setminus(F_{j}\times Y_{j}))=r_{j}(w)\kappa_{w}(B_{j}\setminus G_{w})\le r_{j}(w)\kappa_{w}(Z\setminus G_{w})=0$ (Basic Properties of a Measure §monotone). As $\pi_{1}^{-1}(X\setminus F_{j})$ and $\pi_{2}^{-1}(X\setminus Y_{j})$ are contained in $Z\setminus(F_{j}\times Y_{j})$, also $\lambda_{j}(X\setminus F_{j})=0$ and $\lambda'_{j}(X\setminus Y_{j})=0$. Since $Z\setminus(F_{i+1}\times Y_{i})=((X\setminus F_{i+1})\times X)\cup(X\times(X\setminus Y_{i}))$, the defining property of the product measure and Basic Properties of a Measure §subadditivity give $\beta_{i}(Z\setminus(F_{i+1}\times Y_{i}))\le\lambda_{i+1}(X\setminus F_{i+1})\cdot1+1\cdot\lambda'_{i}(X\setminus Y_{i})=0$. By Basic Properties of a Measure §differences, $\alpha_{j}(F_{j}\times Y_{j})=1$ and $\beta_{i}(F_{i+1}\times Y_{i})=1$. For all $j,j'\in[N]$, $F_{j'}\times Y_{j}\subseteq F_{w}\times Y_{w}=G_{w}\subseteq D_{a}$ by (2.1); hence $\alpha_{j}(D_{a})=\beta_{i}(D_{a})=1$ for all $i,j\in[N]$ (Basic Properties of a Measure §monotone).

(6b) Fibre functions. For $j\in[N]$ and $k\in[n]$ define Borel functions on $X$:

$$\Psi_{j}=\mathbf{1}_{F_{j}}\psi,\qquad P_{j,k}(x)=\mathbf{1}_{F_{j}}(x)\,x_{k},\qquad\Phi_{j}=\mathbf{1}_{Y_{j}}\varphi_{w},\qquad R_{j,k}(y)=\mathbf{1}_{Y_{j}}(y)\,a_{k}^{-1}y_{k}.$$

By the choice of $L$, $|P_{j,k}|\le L$, $|R_{j,k}|\le L$ and $0\le\Psi_{j}\le L^{2}\sum_{k=1}^{n}a_{k}^{-1}$, while $\Phi_{j}\ge0$. For $j,j'\in[N]$ and $(x,y)\in F_{j'}\times Y_{j}\subseteq G_{w}$, (2.1) reads

$$c_{a}(x,y)=\Psi_{j'}(x)+\Phi_{j}(y)-2\sum_{k=1}^{n}P_{j',k}(x)\,R_{j,k}(y).\qquad\text{(6.1)}$$

Let $\bar{u}_{j},\bar{v}_{j}\in\mathbb{R}^{n}$ have components $\bar{u}_{j,k}=\int_{X}P_{j,k}\,d\lambda_{j}$ and $\bar{v}_{j,k}=\int_{X}R_{j,k}\,d\lambda'_{j}$, and let $T_{j}=\int_{Z}\sum_{k=1}^{n}(P_{j,k}\circ\pi_{1})(R_{j,k}\circ\pi_{2})\,d\alpha_{j}$; all integrands are bounded Borel functions. By claim 2 of Image Measures, Measures with Densities, and Change of Variables, $\int_{Z}P_{j,k}\circ\pi_{1}\,d\alpha_{j}=\bar{u}_{j,k}$ and $\int_{Z}R_{j,k}\circ\pi_{2}\,d\alpha_{j}=\bar{v}_{j,k}$.

(6c) Integrability. By (5.1) and monotonicity, $\int_{Z}c_{a}\,d\alpha_{j}=r_{j}(w)\int_{Z}c_{a}\mathbf{1}_{B_{j}}\,d\kappa_{w}\le r_{j}(w)g_{c}(w)<\infty$, so $c_{a}$ is $\alpha_{j}$-integrable. On $F_{j}\times Y_{j}$, (6.1) with $j'=j$ gives $\Phi_{j}\circ\pi_{2}=c_{a}-\Psi_{j}\circ\pi_{1}+2\sum_{k}(P_{j,k}\circ\pi_{1})(R_{j,k}\circ\pi_{2})\le c_{a}+2nL^{2}$; as $\alpha_{j}(Z\setminus(F_{j}\times Y_{j}))=0$, The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison gives $\int_{Z}\Phi_{j}\circ\pi_{2}\,d\alpha_{j}\le\int_{Z}c_{a}\,d\alpha_{j}+2nL^{2}<\infty$. By claim 2 of Image Measures, Measures with Densities, and Change of Variables, $\Phi_{j}$ is $\lambda'_{j}$-integrable with $\int_{X}\Phi_{j}\,d\lambda'_{j}=\int_{Z}\Phi_{j}\circ\pi_{2}\,d\alpha_{j}$; likewise $\int_{X}\Psi_{j}\,d\lambda_{j}=\int_{Z}\Psi_{j}\circ\pi_{1}\,d\alpha_{j}$.

(6d) Cost under $\alpha_{j}$. By (6.1) with $j'=j$, the functions $c_{a}$ and $\Psi_{j}\circ\pi_{1}+\Phi_{j}\circ\pi_{2}-2\sum_{k}(P_{j,k}\circ\pi_{1})(R_{j,k}\circ\pi_{2})$ agree on $F_{j}\times Y_{j}$, hence $\alpha_{j}$-almost everywhere; the latter is integrable by (6c), so The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison and linearity give

$$\int_{Z}c_{a}\,d\alpha_{j}=\int_{X}\Psi_{j}\,d\lambda_{j}+\int_{X}\Phi_{j}\,d\lambda'_{j}-2T_{j}.\qquad\text{(6.2)}$$

(6e) Cost under $\beta_{i}$. By claim 2 of Image Measures, Measures with Densities, and Change of Variables and $(\pi_{1})_{\#}\beta_{i}=\lambda_{i+1}$, $(\pi_{2})_{\#}\beta_{i}=\lambda'_{i}$, the functions $\Psi_{i+1}\circ\pi_{1}$ and $\Phi_{i}\circ\pi_{2}$ are $\beta_{i}$-integrable with integrals $\int_{X}\Psi_{i+1}\,d\lambda_{i+1}$ and $\int_{X}\Phi_{i}\,d\lambda'_{i}$. For $k\in[n]$ the function $(x,y)\mapsto P_{i+1,k}(x)R_{i,k}(y)$ is bounded and Borel on $Z$, hence $\beta_{i}$-integrable; by Tonelli and Fubini Theorems (Fubini), applied with its $(X,\mathcal{F},\mu)$ our $(X,\mathcal{B}(X),\lambda_{i+1})$ and its $(Y,\mathcal{G},\nu)$ our $(X,\mathcal{B}(X),\lambda'_{i})$, both finite hence $\sigma$-finite, its integral equals the iterated integral, whose inner integral at $x$ is $\int_{X}P_{i+1,k}(x)R_{i,k}\,d\lambda'_{i}=P_{i+1,k}(x)\bar{v}_{i,k}$ for every $x$ (the outer integrand of that theorem agrees with $x\mapsto P_{i+1,k}(x)\bar{v}_{i,k}$ off a $\lambda_{i+1}$-null set, so The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison applies); thus $\int_{Z}(P_{i+1,k}\circ\pi_{1})(R_{i,k}\circ\pi_{2})\,d\beta_{i}=\bar{u}_{i+1,k}\bar{v}_{i,k}$. By (6.1) with $j'=i+1$, $j=i$, and $\beta_{i}(F_{i+1}\times Y_{i})=1$, the function $c_{a}$ agrees $\beta_{i}$-almost everywhere with the integrable function $\Psi_{i+1}\circ\pi_{1}+\Phi_{i}\circ\pi_{2}-2\sum_{k}(P_{i+1,k}\circ\pi_{1})(R_{i,k}\circ\pi_{2})$, so by The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison and linearity $c_{a}$ is $\beta_{i}$-integrable and, with the dot product of Difference, Dot Product, and Orthogonality in $\mathbb{R}^n$,

$$\int_{Z}c_{a}\,d\beta_{i}=\int_{X}\Psi_{i+1}\,d\lambda_{i+1}+\int_{X}\Phi_{i}\,d\lambda'_{i}-2\,\bar{v}_{i}\cdot\bar{u}_{i+1}.\qquad\text{(6.3)}$$

(6f) Summation. Since $i\mapsto i+1$ (read cyclically) is a bijection of $[N]$, $\sum_{i}\int\Psi_{i+1}\,d\lambda_{i+1}=\sum_{i}\int\Psi_{i}\,d\lambda_{i}$. Subtracting (6.2) with $j=i$ from (6.3) and summing over $i\in[N]$ therefore gives

$$\sum_{i=1}^{N}\Bigl(\int_{Z}c_{a}\,d\beta_{i}^{w}-\int_{Z}c_{a}\,d\alpha_{i}^{w}\Bigr)=-2\,\Gamma(w),\qquad\Gamma(w)=\sum_{i=1}^{N}\bar{v}_{i}\cdot\bar{u}_{i+1}-\sum_{i=1}^{N}T_{i}.\qquad\text{(6.4)}$$

Step 7 (positivity of $\Gamma(w)$). Keep $w\in K$ and the notation of Step 6. For $j\in\{0,1,\dots,N\}$ and points $u_{i},v_{i}\in\mathbb{R}^{n}$ given for the indices $i\in[N]$ with $i>j$, put, for $i\in[N]$, $\hat{u}_{i}=\bar{u}_{i}$, $\hat{v}_{i}=\bar{v}_{i}$, $\hat{T}_{i}=T_{i}$ if $i\le j$, and $\hat{u}_{i}=u_{i}$, $\hat{v}_{i}=v_{i}$, $\hat{T}_{i}=u_{i}\cdot v_{i}$ if $i>j$, and let

$$\Gamma_{j}=\sum_{i=1}^{N}\hat{v}_{i}\cdot\hat{u}_{i+1}-\sum_{i=1}^{N}\hat{T}_{i}$$

(indices read cyclically). Let $\mathrm{P}(j)$ be the assertion that $\Gamma_{j}>0$ whenever $u_{i}\in U_{i}$ and $v_{i}\in V_{i}$ for every $i>j$. Note $\Gamma_{N}=\Gamma(w)$, there being no free points.

$\mathrm{P}(0)$ holds: by symmetry and the rules for differences in the second argument (claims 1 and 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$), $\Gamma_{0}=\sum_{i}v_{i}\cdot u_{i+1}-\sum_{i}v_{i}\cdot u_{i}=G_{N}(u_{1},v_{1},\dots,u_{N},v_{N})$, which is positive for $u_{i}\in U_{i}$, $v_{i}\in V_{i}$ because $\delta\in\mathcal{Q}$.

Let $j\in[N]$ and assume $\mathrm{P}(j-1)$. Fix $u_{i}\in U_{i}$, $v_{i}\in V_{i}$ for $i>j$, and for $(u,v)\in\mathbb{R}^{n}\times\mathbb{R}^{n}$ let $\Gamma_{j-1}(u,v)$ be $\Gamma_{j-1}$ formed with $(u_{j},v_{j})=(u,v)$ and these points. Since $N\ge2$, the cyclic indices $j-1$ and $j+1$ differ from $j$, so $(u,v)$ enters $\Gamma_{j-1}(u,v)$ only through the summand with $i=j-1$, which is $\hat{v}_{j-1}\cdot u$, the summand with $i=j$, which is $v\cdot\hat{u}_{j+1}$, and $\hat{T}_{j}=u\cdot v$. Thus $\Gamma_{j-1}(u,v)=C+\xi\cdot u+v\cdot\chi-u\cdot v$, where $\xi=\hat{v}_{j-1}$, $\chi=\hat{u}_{j+1}$ and $C$ (the sum of the remaining terms) do not depend on $(u,v)$. These involve only indices $l\neq j$, for which $l\le j-1$ holds exactly when $l\le j$; so forming the hatted quantities with $j$ in place of $j-1$ leaves $\xi,\chi,C$ unchanged, and

$$\Gamma_{j}=C+\xi\cdot\bar{u}_{j}+\bar{v}_{j}\cdot\chi-T_{j}.$$

For $z\in Z$ let $\mathbf{p}(z),\mathbf{r}(z)\in\mathbb{R}^{n}$ have components $P_{j,k}(x)$ and $R_{j,k}(y)$, and let $f(z)=C+\xi\cdot\mathbf{p}(z)+\mathbf{r}(z)\cdot\chi-\sum_{k=1}^{n}P_{j,k}(x)R_{j,k}(y)$, a bounded Borel function on $Z$. By linearity, the constant rule and (6b), $\int_{Z}f\,d\alpha_{j}=C+\sum_{k}\xi_{k}\bar{u}_{j,k}+\sum_{k}\bar{v}_{j,k}\chi_{k}-T_{j}=\Gamma_{j}$. For $z\in F_{j}\times Y_{j}$ we have $\mathbf{p}(z)=p(x)\in U_{j}$ and $\mathbf{r}(z)=q(y)\in V_{j}$, and $\sum_{k}P_{j,k}(x)R_{j,k}(y)=\mathbf{p}(z)\cdot\mathbf{r}(z)$, so $f(z)=\Gamma_{j-1}(\mathbf{p}(z),\mathbf{r}(z))>0$ by $\mathrm{P}(j-1)$. Since $\alpha_{j}(F_{j}\times Y_{j})=1$ by (6a), Step (3b), applied with its $(S,d_{S})$ our $(Z,d)$, its $\lambda$ our $\alpha_{j}$, its $A$ our $F_{j}\times Y_{j}$ and its $f$ our $f$, gives $\Gamma_{j}>0$. This proves $\mathrm{P}(j)$. By induction $\mathrm{P}(N)$ holds, that is,

$$\Gamma(w)>0\qquad(w\in K).\qquad\text{(7.1)}$$

Step 8 (a cheaper coupling). For $w\in X$ and $E\in\mathcal{B}(Z)$ let

$$\kappa'(w,E)=\kappa(w,E)+\vartheta(w)\sum_{i=1}^{N}\bigl(\beta_{i}(w,E)-\alpha_{i}(w,E)\bigr).$$

(8a) $\kappa'$ is a probability kernel from $(X,\mathcal{B}(X))$ to $(Z,\mathcal{B}(Z))$. For fixed $E$ it is Borel in $w$, as $\kappa,\alpha_{i},\beta_{i}$ are kernels and $\vartheta$ is Borel. For $w\notin K$, $\vartheta(w)=0$ and $\kappa'(w,\cdot)=\kappa_{w}$. For $w\in K$ and $E\in\mathcal{B}(Z)$, (5.1) gives $\vartheta(w)\sum_{i}\alpha_{i}(w,E)=N^{-1}\sum_{i}\eta(w)r_{i}(w)\kappa_{w}(E\cap B_{i})\le N^{-1}\sum_{i}\kappa_{w}(E)=\kappa_{w}(E)$, because $\eta(w)r_{i}(w)=\eta(w)/m_{i}(w)\le1$ and $\kappa_{w}(E\cap B_{i})\le\kappa_{w}(E)$ (Basic Properties of a Measure §monotone); hence $\kappa'(w,E)\ge\vartheta(w)\sum_{i}\beta_{i}(w,E)\ge0$. By Step (3a), applied with the finite measures $\kappa_{w},\beta_{i}^{w},\alpha_{i}^{w}$ and the coefficients $1,\vartheta(w),-\vartheta(w)$, $\kappa'(w,\cdot)$ is a finite measure, and $\kappa'(w,Z)=1+\vartheta(w)\sum_{i}(1-1)=1$. Write $\kappa'_{w}=\kappa'(w,\cdot)$.

(8b) The coupling. By Integration Against a Probability Kernel: Measurable Sections, the Composite Measure on the Product and the Iterated Integral §composite, applied with its $(Y,\mathcal{Y})$ our $(X,\mathcal{B}(X))$, its $(Z,\mathcal{Z})$ our $(Z,\mathcal{B}(Z))$, its $\kappa$ our $\kappa'$ and its $\mu$ our $\mu_{n}$, the composite $\mu_{n}\otimes\kappa'$ is a probability measure on $(X\times Z,\mathcal{B}(X)\otimes\mathcal{B}(Z))$. The projection $\mathrm{pr}:X\times Z\to Z$, $(w,z)\mapsto z$, is measurable with respect to $\mathcal{B}(X)\otimes\mathcal{B}(Z)$ and $\mathcal{B}(Z)$, since $\mathrm{pr}^{-1}(E)=X\times E$ is a measurable rectangle (Product Sigma-Algebra). Let $\pi'$ be the image measure of $\mu_{n}\otimes\kappa'$ under $\mathrm{pr}$, a probability measure on $(Z,\mathcal{B}(Z))$ by claim 1 of Image Measures, Measures with Densities, and Change of Variables, so $\pi'\in\mathcal{P}(X\times X)$; by the rectangle formula of Integration Against a Probability Kernel: Measurable Sections, the Composite Measure on the Product and the Iterated Integral §composite with $A=X$,

$$\pi'(E)=(\mu_{n}\otimes\kappa')(X\times E)=\int_{X}\kappa'(w,E)\,\mu_{n}(dw)\qquad(E\in\mathcal{B}(Z)).\qquad\text{(8.1)}$$

(8c) Marginals. Let $A\in\mathcal{B}(X)$ and $w\in X$. Then $\pi_{1}^{-1}(A)=A\times X$ and $\pi_{2}^{-1}(A)=X\times A$, and the defining property of the product measure gives $\beta_{i}(w,A\times X)=\lambda_{i+1}(w,A)\lambda'_{i}(w,X)=\lambda_{i+1}(w,A)$ and $\beta_{i}(w,X\times A)=\lambda_{i+1}(w,X)\lambda'_{i}(w,A)=\lambda'_{i}(w,A)$. Reindexing cyclically, $\sum_{i}\beta_{i}(w,A\times X)=\sum_{i}\lambda_{i}(w,A)=\sum_{i}\alpha_{i}(w,A\times X)$ and $\sum_{i}\beta_{i}(w,X\times A)=\sum_{i}\lambda'_{i}(w,A)=\sum_{i}\alpha_{i}(w,X\times A)$. Hence $\kappa'(w,\pi_{l}^{-1}(A))=\kappa(w,\pi_{l}^{-1}(A))$ for $l=1,2$ and every $w$, and (8.1) and (1.1) give $\pi'(\pi_{l}^{-1}(A))=\pi(\pi_{l}^{-1}(A))$. Therefore $(\pi_{1})_{\#}\pi'=(\pi_{1})_{\#}\pi=\mu$ and $(\pi_{2})_{\#}\pi'=(\pi_{2})_{\#}\pi=\nu$, and $\pi'\in\Pi(\mu,\nu)$ by Couplings of Two Borel Probability Measures on a Hilbert Space and Their Quadratic Cost §coupling.

(8d) $\pi'(D_{a})=1$. Let $w\in W_{0}$; then $\kappa_{w}(D_{a})=1$ by Step 1(b). If $w\notin K$, $\kappa'(w,D_{a})=\kappa_{w}(D_{a})=1$; if $w\in K$, (6a) gives $\kappa'(w,D_{a})=1+\vartheta(w)\sum_{i}(1-1)=1$. So the Borel function $w\mapsto\kappa'(w,D_{a})$ equals the constant $1$ on $W_{0}$, hence $\mu_{n}$-almost everywhere, and by (8.1) and The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison, $\pi'(D_{a})=\int_{X}1\,d\mu_{n}=1$.

(8e) Cost under $\kappa'_{w}$. Let $w\in W_{0}$. If $w\notin K$, then $\kappa'_{w}=\kappa_{w}$, so $c_{a}$ is $\kappa'_{w}$-integrable with $\int_{Z}c_{a}\,d\kappa'_{w}=g_{c}(w)$. If $w\in K$, the set functions $\kappa'_{w}+\vartheta(w)\sum_{i}\alpha_{i}^{w}$ and $\kappa_{w}+\vartheta(w)\sum_{i}\beta_{i}^{w}$ on $\mathcal{B}(Z)$ coincide by the definition of $\kappa'$; applying Step (3a) to each (finite measures, nonnegative coefficients) gives, in $[0,\infty]$,

$$\int_{Z}c_{a}\,d\kappa'_{w}+\vartheta(w)\sum_{i=1}^{N}\int_{Z}c_{a}\,d\alpha_{i}^{w}=\int_{Z}c_{a}\,d\kappa_{w}+\vartheta(w)\sum_{i=1}^{N}\int_{Z}c_{a}\,d\beta_{i}^{w}.$$

The right side is finite by Step 1(c) and (6e); hence $\int_{Z}c_{a}\,d\kappa'_{w}<\infty$, $c_{a}$ is $\kappa'_{w}$-integrable, and, the integrals against $\alpha_{i}^{w}$ being finite by (6c), (6.4) and (7.1) give

$$\int_{Z}c_{a}\,d\kappa'_{w}=g_{c}(w)+\vartheta(w)\sum_{i=1}^{N}\Bigl(\int_{Z}c_{a}\,d\beta_{i}^{w}-\int_{Z}c_{a}\,d\alpha_{i}^{w}\Bigr)=g_{c}(w)-2\vartheta(w)\Gamma(w)<g_{c}(w).\qquad\text{(8.2)}$$

(8f) Cost under $\pi'$. Apply Integration Against a Probability Kernel: Measurable Sections, the Composite Measure on the Product and the Iterated Integral §nonnegative, with the data of (8b), to the nonnegative function $c_{a}\circ\mathrm{pr}$, measurable with respect to $\mathcal{B}(X)\otimes\mathcal{B}(Z)$, whose section at every $w$ is $c_{a}$. Its exceptional set $N'\in\mathcal{B}(X)$, of the $w$ for which $c_{a}$ is not $\kappa'_{w}$-integrable, is disjoint from $W_{0}$ by (8e), so $\mu_{n}(N')\le\mu_{n}(X\setminus W_{0})=0$; its function $g'$, equal to $\int_{Z}c_{a}\,d\kappa'_{w}$ off $N'$ and to $0$ on $N'$, is Borel and nonnegative, and $g'\le g_{c}$ on $W_{0}$ by (8e), hence $\mu_{n}$-almost everywhere. By The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison, $\int_{X}g'\,d\mu_{n}\le\int_{X}g_{c}\,d\mu_{n}<\infty$, so $g'$ is $\mu_{n}$-integrable. By that clause, $c_{a}\circ\mathrm{pr}$ is $(\mu_{n}\otimes\kappa')$-integrable with integral $\int_{X}g'\,d\mu_{n}$, and by claim 2 of Image Measures, Measures with Densities, and Change of Variables

$$\int_{Z}c_{a}\,d\pi'=\int_{X}g'\,d\mu_{n}<\infty.\qquad\text{(8.3)}$$

With (8c) and (8d), $\pi'$ has finite noise cost, so $\pi'\in\Pi^{a}(\mu,\nu)$ and $I^{a}(\pi')=\int_{Z}c_{a}\,d\pi'$ by Couplings of Finite Noise Cost and Their Noise Cost §finite, Couplings of Finite Noise Cost and Their Noise Cost §couplings and Couplings of Finite Noise Cost and Their Noise Cost §cost.

(8g) Strict decrease. The function $\Delta=g_{c}-g'$ is $\mu_{n}$-integrable. Let $\tilde{\Delta}=\mathbf{1}_{W_{0}}\Delta$; it is Borel, nonnegative by (8e), and equal to $\Delta$ off the set $X\setminus W_{0}$ of measure $0$, so by The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison and linearity $\tilde{\Delta}$ is integrable with $\int_{X}\tilde{\Delta}\,d\mu_{n}=\int_{X}g_{c}\,d\mu_{n}-\int_{X}g'\,d\mu_{n}$. By (8.2) and (7.1), $\tilde{\Delta}(w)=2\vartheta(w)\Gamma(w)>0$ for $w\in K$. If $\int_{X}\tilde{\Delta}\,d\mu_{n}$ were $0$, then by The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §vanishing the set $\{\tilde{\Delta}\neq0\}\supseteq K$ would be null and $\mu_{n}(K)=0$ (Null Set of a Measure, Basic Properties of a Measure §monotone), contrary to the hypothesis of Step 5; so $\int_{X}\tilde{\Delta}\,d\mu_{n}>0$. By (8.3) and (1.2),

$$I^{a}(\pi')=\int_{X}g'\,d\mu_{n}<\int_{X}g_{c}\,d\mu_{n}=I^{a}(\pi)=W_{a}(\mu,\nu)^{2}.$$

But The Noise Wasserstein Distance §distance gives $W_{a}(\mu,\nu)^{2}\le I^{a}(\pi')$ since $\pi'\in\Pi^{a}(\mu,\nu)$. This contradiction proves the main claim: $\mu_{n}(K_{\delta})=0$ for every $\delta\in\mathcal{Q}$.

Step 9 (conclusion). Let $W_{1}=W_{0}\setminus\bigcup_{m\in\mathbb{N}}K_{\delta_{m}}$. Every $K_{\delta_{m}}$ belongs to $\mathcal{B}(X)$ and has $\mu_{n}$-measure $0$ (by the main claim if $\delta_{m}\in\mathcal{Q}$, being empty otherwise), so their union belongs to $\mathcal{B}(X)$, is contained in $W_{0}$, and has measure $0$ by Basic Properties of a Measure §subadditivity; hence $W_{1}\in\mathcal{B}(X)$ and $\mu_{n}(W_{1})=\mu_{n}(W_{0})-0=1$ by Basic Properties of a Measure §differences. Since $(\delta_{m})$ exhausts $\mathcal{T}\supseteq\mathcal{Q}$, a point of $W_{1}$ lies in $W_{0}$ and in no $K_{\delta}$ with $\delta\in\mathcal{Q}$.

Let $w\in W_{1}$ and suppose that $\operatorname{supp}\theta_{w}$ is not cyclically monotone. By Cyclically Monotone Subset of a Doubled Euclidean Space §monotone there are $N\in\mathbb{N}$ and $\zeta_{1},\dots,\zeta_{N}\in\operatorname{supp}\theta_{w}$ such that, with $u_{i}=\mathrm{pr}_{1}(\zeta_{i})$ and $v_{i}=\mathrm{pr}_{2}(\zeta_{i})$ (the points called $x_{i}$ and $y_{i}$ there), $g=G_{N}(u_{1},v_{1},\dots,u_{N},v_{N})>0$. The order of choices is: first $N$ and the $\zeta_{i}$; then $L'$ and $r$; then the rationals; then the radii $r'_{i}$.

Let $L'$ be $1$ plus the largest absolute value of a component of the points $u_{i},v_{i}$ ($i\in[N]$), and $r=\min(1,g/(8nNL'))>0$. If $u'_{i},v'_{i}\in\mathbb{R}^{n}$ satisfy $|u'_{i,k}-u_{i,k}|<r$ and $|v'_{i,k}-v_{i,k}|<r$ for all $i\in[N]$ and $k\in[n]$, then all these components have absolute value less than $L'$, and for each $i,k$

$$\bigl|v'_{i,k}(u'_{i+1,k}-u'_{i,k})-v_{i,k}(u_{i+1,k}-u_{i,k})\bigr|\le|v'_{i,k}-v_{i,k}|\,|u'_{i+1,k}-u'_{i,k}|+|v_{i,k}|\,\bigl|(u'_{i+1,k}-u_{i+1,k})-(u'_{i,k}-u_{i,k})\bigr|\le2L'r+2L'r ;$$

summing over $i\in[N]$ and $k\in[n]$ (Difference, Dot Product, and Orthogonality in $\mathbb{R}^n$) gives $|G_{N}(u'_{1},v'_{1},\dots,u'_{N},v'_{N})-g|\le4nNL'r\le g/2$, so $G_{N}(u'_{1},v'_{1},\dots,u'_{N},v'_{N})\ge g/2>0$.

For each $i\in[N]$ and $k\in[n]$, claim 1 of The Rational Numbers are Dense in the Real Numbers, used twice, gives rationals $s_{i,k},t_{i,k}$ with $u_{i,k}-r<s_{i,k}<u_{i,k}<t_{i,k}<u_{i,k}+r$, and likewise rationals $s'_{i,k},t'_{i,k}$ with $v_{i,k}-r<s'_{i,k}<v_{i,k}<t'_{i,k}<v_{i,k}+r$. Let $\omega\in\mathbb{Q}^{4nN}$ list the points $s_{i},t_{i},s'_{i},t'_{i}$ so formed, and $\delta=(N,\omega)\in\mathcal{T}$. Then $u_{i}\in U_{i}^{\delta}$, $v_{i}\in V_{i}^{\delta}$, and every $u'\in U_{i}^{\delta}$, $v'\in V_{i}^{\delta}$ has $|u'_{k}-u_{i,k}|<r$, $|v'_{k}-v_{i,k}|<r$ for all $k$; by the previous paragraph $\delta\in\mathcal{Q}$.

For $i\in[N]$ let $r'_{i}>0$ be the least of the $4n$ positive numbers $u_{i,k}-s_{i,k}$, $t_{i,k}-u_{i,k}$, $v_{i,k}-s'_{i,k}$, $t'_{i,k}-v_{i,k}$ ($k\in[n]$). If $\zeta'\in\mathbb{R}^{n+n}$ and $d_{E}(\zeta',\zeta_{i})<r'_{i}$, then every component of $\zeta'-\zeta_{i}$ has absolute value less than $r'_{i}$ by Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ §distance and Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ §coordinate; the components of $\mathrm{pr}_{1}(\zeta')$ and $\mathrm{pr}_{2}(\zeta')$ are the first and the last $n$ components of $\zeta'=\iota(\mathrm{pr}_{1}(\zeta'),\mathrm{pr}_{2}(\zeta'))$ (Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §projections and the description of $\iota$ there), and likewise for $\zeta_{i}$, so $\mathrm{pr}_{1}(\zeta')\in U_{i}^{\delta}$, $\mathrm{pr}_{2}(\zeta')\in V_{i}^{\delta}$ and $\zeta'\in\iota(U_{i}^{\delta}\times V_{i}^{\delta})$. Thus the open ball $B_{d_{E}}(\zeta_{i},r'_{i})$ is contained in $\iota(U_{i}^{\delta}\times V_{i}^{\delta})$, and since $\zeta_{i}\in\operatorname{supp}\theta_{w}$, Support of a Borel Measure on a Metric Space §support and Basic Properties of a Measure §monotone give

$$0<\theta_{w}\bigl(B_{d_{E}}(\zeta_{i},r'_{i})\bigr)\le\theta_{w}\bigl(\iota(U_{i}^{\delta}\times V_{i}^{\delta})\bigr)=\kappa_{w}\bigl(h_{n}^{-1}(\iota(U_{i}^{\delta}\times V_{i}^{\delta}))\bigr)=\kappa_{w}(B_{i}^{\delta})=m_{i}^{\delta}(w),$$

$\theta_{w}$ being the image measure of $\kappa_{w}$ under $h_{n}$. Hence $\eta_{\delta}(w)>0$, and as $w\in W_{0}$, $w\in K_{\delta}$ with $\delta\in\mathcal{Q}$, which contradicts $w\in W_{1}$. Therefore $\operatorname{supp}\theta_{w}$ is cyclically monotone for every $w\in W_{1}$, where $W_{1}\in\mathcal{B}(X)$ and $\mu_{n}(W_{1})=1$. This proves claim 1.