Proof of Bounds, Monotonicity and Borwein-Preiss Perturbed Maximisers of the Wasserstein-Doubled Difference for a Wasserstein-Closed Penalty Pair

Each result cited is universally quantified over the data in its own statement. We write $W$ for $W_{2}$, which is a metric on $\mathcal{P}_{2}(\mathbb{R}^{d})$ by The Quadratic Wasserstein Distance is a Metric on the Wasserstein Space §metric; so $W$ is nonnegative, symmetric, vanishes on the diagonal and satisfies the triangle inequality (Metric Space). For $c\in\mathbb{R}$ we write $\mathcal{D}_{c}=\{\sigma\in\mathcal{D}:\mathcal{E}(\sigma)\le c\}$, as in Basic Properties of a Wasserstein-Closed Penalty Pair: Lower Bound, Lower Semicontinuity, Complete Sublevel Sets, Bounded Distances, and Coercive Pairs. Elementary real arithmetic and order, including squares of nonnegative reals and suprema, are used through The Real Numbers: Standing Notation and Background §background and The Real Numbers: Standing Notation and Background §bounds.

Step 0 (Envelope facts). As recorded in the statement, $u$ has penalty-subordinate growth from above and $v$ from below, by The Delta-Envelopes of Bounded Functions and Their Monotonicity in the Weight, for a Wasserstein-Closed Penalty Pair §growth. Let $\delta\in\mathbb{R}$ be positive. By Basic Properties of the Delta-Envelopes on the Wasserstein Space §semicontinuity, $u^{-}_{\delta}$ is upper semicontinuous and $v^{+}_{\delta}$ lower semicontinuous on $\mathcal{D}$ relative to $\mathcal{D}$ in $(\mathcal{P}_{2}(\mathbb{R}^{d}),W)$, and

$$u(\sigma)-\delta\,\mathcal{E}(\sigma)\le u^{-}_{\delta}(\sigma),\qquad v^{+}_{\delta}(\sigma)\le v(\sigma)+\delta\,\mathcal{E}(\sigma)\qquad(\sigma\in\mathcal{D}).\qquad(0.1)$$

By The Delta-Envelopes of Bounded Functions and Their Monotonicity in the Weight, for a Wasserstein-Closed Penalty Pair §bounded, applied to $u$ with the bound $b$ and to $v$ with the bound $b'$,

$$u^{-}_{\delta}(\sigma)\le b-\delta\,\mathcal{E}(\sigma),\qquad b'+\delta\,\mathcal{E}(\sigma)\le v^{+}_{\delta}(\sigma)\qquad(\sigma\in\mathcal{D}).\qquad(0.2)$$

Finally $\delta e_{0}\le\delta\,\mathcal{E}(\sigma)$ for every $\sigma\in\mathcal{D}$, by the choice of $e_{0}$ and the positivity of $\delta$.

Step 1 (Clause bounds). Let $\delta,\alpha$ be positive and $(\mu,\nu)\in\mathcal{D}\times\mathcal{D}$. Since $\tfrac{\alpha}{2}W(\mu,\nu)^{2}\ge0$, (0.2) gives $\Psi_{\delta,\alpha}(\mu,\nu)\le b-\delta\,\mathcal{E}(\mu)-b'-\delta\,\mathcal{E}(\nu)$, and Step 0 gives $-\delta(\mathcal{E}(\mu)+\mathcal{E}(\nu))\le-2\delta e_{0}$; this is the displayed chain of clause bounds. The set of values of $\Psi_{\delta,\alpha}$ is nonempty because $\mathcal{D}\times\mathcal{D}$ is (as noted in the statement), and it is bounded above by $b-b'-2\delta e_{0}$, so its supremum $M(\delta,\alpha)$ is a real number by The Real Numbers: Standing Notation and Background §bounds. As $M(\delta,\alpha)$ is an upper bound of these values,

$$\Psi_{\delta,\alpha}(\mu,\nu)\le M(\delta,\alpha)\qquad\text{for all }(\mu,\nu)\in\mathcal{D}\times\mathcal{D}.\qquad(1.1)$$

Step 2 (Clause diagonal). Let $\delta,\alpha$ be positive and $\mu\in\mathcal{D}$. Since $W(\mu,\mu)=0$, (0.1) gives $\Psi_{\delta,\alpha}(\mu,\mu)=u^{-}_{\delta}(\mu)-v^{+}_{\delta}(\mu)\ge u(\mu)-\delta\,\mathcal{E}(\mu)-v(\mu)-\delta\,\mathcal{E}(\mu)$, and (1.1) gives $\Psi_{\delta,\alpha}(\mu,\mu)\le M(\delta,\alpha)$. Hence $u(\mu)-v(\mu)-2\delta\,\mathcal{E}(\mu)\le M(\delta,\alpha)$.

Step 3 (Clause weight). Let $0<\delta'<\delta$, $0<\alpha$, $0\le\tau$ and let $(\mu,\nu)\in\mathcal{D}\times\mathcal{D}$ satisfy $M(\delta,\alpha)-\tau\le\Psi_{\delta,\alpha}(\mu,\nu)$. By The Delta-Envelopes of Bounded Functions and Their Monotonicity in the Weight, for a Wasserstein-Closed Penalty Pair §monotone, read with $\delta'$ and $\delta$ in the roles of its smaller and larger weight (its hypotheses hold by Step 0),

$$u^{-}_{\delta}(\mu)+(\delta-\delta')\,\mathcal{E}(\mu)\le u^{-}_{\delta'}(\mu),\qquad v^{+}_{\delta'}(\nu)\le v^{+}_{\delta}(\nu)-(\delta-\delta')\,\mathcal{E}(\nu).$$

Subtracting the second from the first and then subtracting $\tfrac{\alpha}{2}W(\mu,\nu)^{2}$, and using (1.1) for $\delta'$,

$$M(\delta',\alpha)\ge\Psi_{\delta',\alpha}(\mu,\nu)\ge\Psi_{\delta,\alpha}(\mu,\nu)+(\delta-\delta')\bigl(\mathcal{E}(\mu)+\mathcal{E}(\nu)\bigr)\ge M(\delta,\alpha)-\tau+(\delta-\delta')\bigl(\mathcal{E}(\mu)+\mathcal{E}(\nu)\bigr).$$

Step 4 (Clause strength). Let $0<\delta$, $0<\alpha'<\alpha$, $0\le\tau$ and let $(\mu,\nu)\in\mathcal{D}\times\mathcal{D}$ satisfy $M(\delta,\alpha)-\tau\le\Psi_{\delta,\alpha}(\mu,\nu)$. Since $\tfrac{\alpha'}{2}=\tfrac{\alpha}{2}-\tfrac{\alpha-\alpha'}{2}$, directly from the definition $\Psi_{\delta,\alpha'}(\mu,\nu)=\Psi_{\delta,\alpha}(\mu,\nu)+\tfrac{\alpha-\alpha'}{2}W(\mu,\nu)^{2}$. Adding $\tfrac{\alpha-\alpha'}{2}W(\mu,\nu)^{2}$ to both sides of the hypothesis and using (1.1) for $\alpha'$,

$$M(\delta,\alpha)-\tau+\tfrac{\alpha-\alpha'}{2}W(\mu,\nu)^{2}\le\Psi_{\delta,\alpha'}(\mu,\nu)\le M(\delta,\alpha').$$

Step 5 (Clause perturbed: the constants $K$ and $B$). Fix a positive $\delta$. The constants are chosen in the order $\mu_{0}$, $a_{0}$, $K$, $B$, all before $\alpha$ and $\tau$. Fix $\mu_{0}\in\mathcal{D}$, possible since $\mathcal{D}\ne\varnothing$, and put $a_{0}=u^{-}_{\delta}(\mu_{0})-v^{+}_{\delta}(\mu_{0})$. For every positive $\alpha$, $W(\mu_{0},\mu_{0})=0$ gives $a_{0}=\Psi_{\delta,\alpha}(\mu_{0},\mu_{0})$, so by (1.1)

$$a_{0}\le M(\delta,\alpha)\qquad\text{for every positive }\alpha.\qquad(5.1)$$

Put $K=\delta^{-1}(b-b'-a_{0}+1)-e_{0}$, so that $\delta K+\delta e_{0}=b-b'-a_{0}+1$, and let $B\in\mathbb{R}$ satisfy $M_{2}(\sigma)\le B$ for every $\sigma\in\mathcal{D}_{K}$, as provided by Wasserstein-Closed Penalty Pairs §bounded with $c=K$ (the pair being Wasserstein-closed, Wasserstein-Closed Penalty Pairs §w2-closed). These depend only on $\delta$, $u$, $v$, $b$, $b'$, $e_{0}$ (and the fixed choice of $\mu_{0}$ in the pair's domain), not on $\alpha$ or $\tau$, and $M_{2}(\sigma)\le B$ whenever $\sigma\in\mathcal{D}$ and $\mathcal{E}(\sigma)\le K$, as clause perturbed requires.

Off the localising set. Let $\alpha$ be positive and let $(\mu,\nu)\in\mathcal{D}\times\mathcal{D}$ with $\mu\notin\mathcal{D}_{K}$ or $\nu\notin\mathcal{D}_{K}$. Then

$$\Psi_{\delta,\alpha}(\mu,\nu)<M(\delta,\alpha)-1.\qquad(5.2)$$

Indeed, if $\mu\notin\mathcal{D}_{K}$, then $K<\mathcal{E}(\mu)$, and Step 1 together with $\delta e_{0}\le\delta\,\mathcal{E}(\nu)$ (Step 0) and the positivity of $\delta$ gives

$$\Psi_{\delta,\alpha}(\mu,\nu)\le b-b'-\delta\,\mathcal{E}(\mu)-\delta e_{0}<b-b'-\delta K-\delta e_{0}=a_{0}-1\le M(\delta,\alpha)-1,$$

the last step by (5.1); if $\nu\notin\mathcal{D}_{K}$ the same holds with the roles of $\mu$ and $\nu$ exchanged.

Step 6 (The complete metric space $X$). Let $d_{\times}$ be the product metric on $\mathcal{P}_{2}(\mathbb{R}^{d})\times\mathcal{P}_{2}(\mathbb{R}^{d})$ built from two copies of $(\mathcal{P}_{2}(\mathbb{R}^{d}),W)$, a metric by claim 1 of The Product Metric is a Metric. By claim 2 of that theorem, for $x=(\mu,\nu)$ and $x'=(\mu',\nu')$ we have $W(\mu,\mu')\le d_{\times}(x,x')$ and $W(\nu,\nu')\le d_{\times}(x,x')$. Put $X=\mathcal{D}_{K}\times\mathcal{D}_{K}\subseteq\mathcal{D}\times\mathcal{D}$ and let $d_{X}$ be the restriction of $d_{\times}$ to $X\times X$, a metric on $X$ by claim 1 of The Restriction of a Metric to a Subset Induces the Subspace Topology.

$(X,d_{X})$ is complete. Let $(x_{m})_{m\in\mathbb{N}}$ be a Cauchy sequence in $(X,d_{X})$, $x_{m}=(\sigma_{m},\rho_{m})$. Given a positive $\varepsilon$ and $N$ as in that definition, the domination above gives $W(\sigma_{m},\sigma_{l})\le d_{X}(x_{m},x_{l})<\varepsilon$ and $W(\rho_{m},\rho_{l})<\varepsilon$ for all $m,l\ge N$; so $(\sigma_{m})$ and $(\rho_{m})$ are Cauchy sequences in $(\mathcal{D}_{K},W)$, and by Basic Properties of a Wasserstein-Closed Penalty Pair: Lower Bound, Lower Semicontinuity, Complete Sublevel Sets, Bounded Distances, and Coercive Pairs §complete they converge in $(\mathcal{D}_{K},W)$ to points $\sigma,\rho\in\mathcal{D}_{K}$. Since that convergence is expressed by the same distances $W(\sigma_{m},\sigma)$ and $W(\rho_{m},\rho)$, both sequences also converge in $(\mathcal{P}_{2}(\mathbb{R}^{d}),W)$, and by claim 1 of Coordinatewise Convergence, Sequential Compactness and Density in a Product Metric Space $(x_{m})$ converges to $(\sigma,\rho)$ in $(\mathcal{P}_{2}(\mathbb{R}^{d})\times\mathcal{P}_{2}(\mathbb{R}^{d}),d_{\times})$. As $(\sigma,\rho)\in X$ and $d_{X}$ is the restriction of $d_{\times}$, $(x_{m})$ converges to $(\sigma,\rho)$ in $(X,d_{X})$.

Step 7 (Two elementary facts). (a) If $s,s',t$ are nonnegative reals with $s\le s'+t$, then $s^{2}\le s'^{2}+2st$: if $s\le s'$ then $s^{2}\le s'^{2}$; otherwise $0<s-s'\le t$ and $s+s'\le2s$, so $s^{2}-s'^{2}=(s-s')(s+s')\le2st$. (b) Let $(Y,d_{Y})$ be a metric space, $A\subseteq Y$, $\varphi:A\to\mathbb{R}$, $y\in A$, and suppose there is a nonnegative $a$ with $\varphi(y)\le\varphi(y')+a\,d_{Y}(y,y')$ for every $y'\in A$. Then $\varphi$ is lower semicontinuous at $y$ relative to $A$: given a positive $\varepsilon$, the number $r=\varepsilon(a+1)^{-1}$ is positive, and for $y'\in A$ with $d_{Y}(y,y')<r$ we get $a\,d_{Y}(y,y')\le ar<\varepsilon$, hence $\varphi(y)-\varepsilon<\varphi(y')$.

Step 8 (The function $f$). Let $\alpha$ be positive and write $\Psi=\Psi_{\delta,\alpha}$, $M=M(\delta,\alpha)$. (a) By claim 4 of Negation, Restriction, and Separated Differences of Semicontinuous Functions, with both metric spaces $(\mathcal{P}_{2}(\mathbb{R}^{d}),W)$, $A=B=\mathcal{D}$, the upper semicontinuous $u^{-}_{\delta}$ and the lower semicontinuous $v^{+}_{\delta}$ (Step 0), the function $h(\mu,\nu)=u^{-}_{\delta}(\mu)-v^{+}_{\delta}(\nu)$ is upper semicontinuous on $\mathcal{D}\times\mathcal{D}$ with respect to $d_{\times}$. (b) Let $q(\mu,\nu)=\tfrac{\alpha}{2}W(\mu,\nu)^{2}$ on $\mathcal{D}\times\mathcal{D}$. For $x=(\mu,\nu)$, $x'=(\mu',\nu')$ in $\mathcal{D}\times\mathcal{D}$ and $\rho=d_{\times}(x,x')$, the triangle inequality, symmetry and Step 6 give $W(\mu,\nu)\le W(\mu,\mu')+W(\mu',\nu')+W(\nu',\nu)\le W(\mu',\nu')+2\rho$, so Step 7(a) gives $W(\mu,\nu)^{2}\le W(\mu',\nu')^{2}+4\rho\,W(\mu,\nu)$ and $q(x)\le q(x')+2\alpha W(\mu,\nu)\,\rho$. By Step 7(b), $q$ is lower semicontinuous at every point of $\mathcal{D}\times\mathcal{D}$ relative to $\mathcal{D}\times\mathcal{D}$ in $(\mathcal{P}_{2}(\mathbb{R}^{d})\times\mathcal{P}_{2}(\mathbb{R}^{d}),d_{\times})$. (c) Hence $\Psi=h-q$ is upper semicontinuous at every point of $\mathcal{D}\times\mathcal{D}$ by claim 3 of Negation, Restriction, and Separated Differences of Semicontinuous Functions, and its restriction $f:X\to\mathbb{R}$, $f(x)=\Psi(x)$, is upper semicontinuous at every point of $X$ relative to $X$ by claim 2 of that lemma. Since $d_{X}$ agrees with $d_{\times}$ on $X\times X$, the condition of Upper Semicontinuous Function on a Subset of a Metric Space reads the same in $(X,d_{X})$, so $f$ is upper semicontinuous on $X$ in $(X,d_{X})$. By Step 1, $f$ is bounded above by $b-b'-2\delta e_{0}$.

Step 9 (Weights and the starting point). Let $\alpha,\tau\in\mathbb{R}$ with $0<\alpha$ and $0<\tau<1$, with $\Psi$, $M$, $f$ as in Step 8. (a) Put $c_{k}=\tau\bigl(\tfrac12\bigr)^{k}$ for $k\in\mathbb{N}$, a positive real. By Series of Nonnegative Real Numbers, Comparison, and the Geometric Series §geometric, $\sum_{k=1}^{\infty}(\tfrac12)^{k}$ converges with sum $1$, so by Elementary Properties of Series of Real Numbers §linearity (both of its series taken to be this one, and $\lambda=\tau$) the series $\sum_{k=1}^{\infty}c_{k}$ converges with sum $\tau$; in particular $\sum_{k=1}^{\infty}c_{k}\le\tau$. (b) By Approximation Property of the Supremum and the Infimum in $\mathbb{R}$ §epsilon-above, applied to the nonempty set of values of $\Psi$, bounded above with supremum $M$ (Step 1), and to $\varepsilon=\tau$, there is $x_{1}=(\mu_{1},\nu_{1})\in\mathcal{D}\times\mathcal{D}$ with $M-\tau<\Psi(x_{1})$. As $\tau<1$, $M-1<M-\tau$, so by (5.2) neither $\mu_{1}\notin\mathcal{D}_{K}$ nor $\nu_{1}\notin\mathcal{D}_{K}$ can hold; thus $x_{1}\in X$ and $X\ne\varnothing$. The values of $f$ are values of $\Psi$, so $f$ is bounded above by $M$ and $\sup_{x\in X}f(x)\le M$; hence $f(x_{1})>M-\tau\ge\sup_{x\in X}f(x)-\tau$.

Step 10 (The gauge). For $x=(\mu,\nu)$ and $y=(\mu',\nu')$ in $X$ put $g(x,y)=W(\mu,\mu')^{2}+W(\nu,\nu')^{2}$, and $G=8B$. (i) $g(x,x)=0$ and $0\le g(x,y)$. Since $\mathcal{D}_{K}$ consists of the $\sigma\in\mathcal{D}$ with $\mathcal{E}(\sigma)\le K$, on which $M_{2}\le B$ (Step 5), Basic Properties of a Wasserstein-Closed Penalty Pair: Lower Bound, Lower Semicontinuity, Complete Sublevel Sets, Bounded Distances, and Coercive Pairs §diameter with $c=K$ gives $W(\mu,\mu')^{2}\le4B$ and $W(\nu,\nu')^{2}\le4B$, so $g(x,y)\le G$. In particular, by the bound just proved applied with $x=y=x_{1}\in X$, $G\ge g(x_{1},x_{1})\ge0$, so $G$ is nonnegative. (ii) Fix $y=(\mu'',\nu'')\in X$. For $x=(\mu,\nu)$, $x'=(\mu',\nu')$ in $X$ and $\rho=d_{X}(x,x')$, the triangle inequality and Step 6 give $W(\mu,\mu'')\le W(\mu',\mu'')+\rho$ and $W(\nu,\nu'')\le W(\nu',\nu'')+\rho$, so Step 7(a) gives $g(x,y)\le g(x',y)+a\rho$ with $a=2\bigl(W(\mu,\mu'')+W(\nu,\nu'')\bigr)\ge0$; by Step 7(b), applied in $(X,d_{X})$ with $A=X$, $g(\cdot,y)$ is lower semicontinuous on $X$. (iii) Let $\eta$ be positive and $\beta=(\tfrac{\eta}{2})^{2}$, which is positive. If $x=(\mu,\nu)$ and $y=(\mu',\nu')$ in $X$ satisfy $g(x,y)\le\beta$, then $W(\mu,\mu')^{2}\le\beta$, so $W(\mu,\mu')\le\tfrac{\eta}{2}<\eta$ (if $\tfrac{\eta}{2}<W(\mu,\mu')$ then $\beta<W(\mu,\mu')^{2}$, squares being strictly monotone on nonnegative reals); likewise $W(\nu,\nu')<\eta$, and $d_{X}(x,y)<\eta$ by claim 3 of The Product Metric is a Metric.

Step 11 (The variational principle; conclusion of clause perturbed). With $\alpha,\tau$ as in Step 9, apply A Smooth Variational Principle of Borwein-Preiss Type with a Gauge on a Complete Metric Space to the nonempty complete metric space $(X,d_{X})$ (Steps 6 and 9(b)), the upper semicontinuous function $f$, bounded above (Step 8), the bound $G$ and the gauge $g$ (Step 10), the weights $c_{k}$ (Step 9(a)), its $\varepsilon$ taken to be $\tau$, and the point $x_{1}$ (Step 9(b)). It yields $(\hat{\mu},\hat{\nu})\in X$ and a sequence $(x_{k})_{k\in\mathbb{N}}$ in $X$ with first term $x_{1}$; write $x_{k}=(\mu_{k},\nu_{k})$, so that $(\mu_{k})$ and $(\nu_{k})$ are sequences in $\mathcal{D}_{K}\subseteq\mathcal{D}$.

Localisation. Since $(\hat{\mu},\hat{\nu})$ and every $x_{k}$ lie in $X=\mathcal{D}_{K}\times\mathcal{D}_{K}$, we have $\mathcal{E}(\hat{\mu})\le K$, $\mathcal{E}(\hat{\nu})\le K$, $\mathcal{E}(\mu_{k})\le K$ and $\mathcal{E}(\nu_{k})\le K$ for every $k$.

Convergence of the series. Let $(\mu,\nu)\in\mathcal{P}_{2}(\mathbb{R}^{d})\times\mathcal{P}_{2}(\mathbb{R}^{d})$ and $w_{k}=W(\mu,\mu_{k})^{2}+W(\nu,\nu_{k})^{2}$. For each $k$, $W(\mu,\mu_{k})\le W(\mu,\mu_{1})+W(\mu_{1},\mu_{k})$, and $W(\mu_{1},\mu_{k})^{2}\le4B$ by Basic Properties of a Wasserstein-Closed Penalty Pair: Lower Bound, Lower Semicontinuity, Complete Sublevel Sets, Bounded Distances, and Coercive Pairs §diameter ($\mu_{1},\mu_{k}\in\mathcal{D}_{K}$); since $(s+t)^{2}\le2s^{2}+2t^{2}$ for reals $s,t$, this gives $W(\mu,\mu_{k})^{2}\le2W(\mu,\mu_{1})^{2}+8B$, and likewise $W(\nu,\nu_{k})^{2}\le2W(\nu,\nu_{1})^{2}+8B$. So $0\le w_{k}\le L$ with $L=2W(\mu,\mu_{1})^{2}+2W(\nu,\nu_{1})^{2}+16B$, independent of $k$, and $L\ge w_{1}\ge0$. By Series of Nonnegative Real Numbers, Comparison, and the Geometric Series §tail-bound, with its nonnegative convergent series $\sum_{k=1}^{\infty}c_{k}$ and its bound $L$, the series $\sum_{k=1}^{\infty}c_{k}w_{k}$ converges. Its terms are nonnegative, so its sum is at least its first partial sum, which is nonnegative, by Series of Nonnegative Real Numbers, Comparison, and the Geometric Series §dominates. Hence, for $\Phi$ as in clause perturbed,

$$\Phi(\mu,\nu)\le\Psi(\mu,\nu)\qquad\text{for every }(\mu,\nu)\in\mathcal{D}\times\mathcal{D}.\qquad(11.1)$$

For $x\in X$ the sum of this series is $\sum_{k=1}^{\infty}c_{k}\,g(x,x_{k})$, so the function $f-\sum_{k}c_{k}\,g(\cdot,x_{k})$ of A Smooth Variational Principle of Borwein-Preiss Type with a Gauge on a Complete Metric Space is the restriction of $\Phi$ to $X$.

Near-maximiser. By A Smooth Variational Principle of Borwein-Preiss Type with a Gauge on a Complete Metric Space §value and Step 9(b), $\Phi(\hat{\mu},\hat{\nu})\ge f(x_{1})>M-\tau$, so by (11.1) $\Psi_{\delta,\alpha}(\hat{\mu},\hat{\nu})\ge\Phi(\hat{\mu},\hat{\nu})>M(\delta,\alpha)-\tau$.

Strict maximum. Let $(\mu,\nu)\in\mathcal{D}\times\mathcal{D}$ with $(\mu,\nu)\ne(\hat{\mu},\hat{\nu})$. If $(\mu,\nu)\in X$, then $\Phi(\mu,\nu)<\Phi(\hat{\mu},\hat{\nu})$ by A Smooth Variational Principle of Borwein-Preiss Type with a Gauge on a Complete Metric Space §maximum. Otherwise $\mu\notin\mathcal{D}_{K}$ or $\nu\notin\mathcal{D}_{K}$, and (11.1), (5.2), $\tau<1$ and the inequality $\Phi(\hat{\mu},\hat{\nu})>M-\tau$ established above give

$$\Phi(\mu,\nu)\le\Psi(\mu,\nu)<M-1<M-\tau<\Phi(\hat{\mu},\hat{\nu}).$$

Since $K$ and $B$ were fixed in Step 5 before $\alpha$ and $\tau$, clause perturbed holds. $\blacksquare$