Proof of Localisation at a Sequentially Strict Maximum of a Quadratically Penalised Difference

Each result cited is universally quantified over the data in its own statement, and is applied here to the data named in the statement of the lemma.

Write $M_{0}=\Phi(\bar{x},\bar{y})$ and $R=|\bar{x}-\bar{y}|$, so that $0\le R$ by Real Inner Product Spaces (ii). By clause 1 of Sequentially Strict Maxima and Minima on a Subset of a Metric Space (i),

$$\Phi(x,y)\le M_{0}\qquad\text{for every }(x,y)\in A\times A .$$

Fix, once and for all, a sequence $(\varepsilon_{k})_{k\in\mathbb{N}}$ of positive real numbers converging to $0$ in $(\mathbb{R},d_{\mathbb{R}})$; such a sequence exists by Existence of a Sequence of Positive Real Numbers with Limit Zero. For $x,y\in E$ one has $d(x,y)=|x-y|$ by Real Inner Product Spaces (iii), so that convergence of a sequence $(x_{k})$ to $x$ in $(E,d)$ means: for every positive $\sigma\in\mathbb{R}$ there is $k_{0}\in\mathbb{N}$ with $|x_{k}-x|<\sigma$ for every $k$ with $k_{0}\le k$.

Claim 1 (near-maximising pairs converge). Let $(x_{k},y_{k})_{k\in\mathbb{N}}$ be a sequence in $A\times A$ with $M_{0}-\varepsilon_{k}<\Phi(x_{k},y_{k})$ for every $k\in\mathbb{N}$. Then $(x_{k})_{k\in\mathbb{N}}$ converges to $\bar{x}$ and $(y_{k})_{k\in\mathbb{N}}$ converges to $\bar{y}$ in $(E,d)$.

Proof. For each $k$ we have $M_{0}-\varepsilon_{k}<\Phi(x_{k},y_{k})\le M_{0}$, hence $0\le M_{0}-\Phi(x_{k},y_{k})<\varepsilon_{k}$ by claim 3 of Elementary Arithmetic in an Ordered Field, and therefore $|\Phi(x_{k},y_{k})-M_{0}|\le\varepsilon_{k}$ by claims 1 and 2 of Properties of the Absolute Value in an Ordered Field. Since $(\varepsilon_{k})$ converges to $0$, claim 3 of Order Properties of Limits of Real Sequences shows that the sequence of real numbers $(\Phi(x_{k},y_{k}))_{k\in\mathbb{N}}$ converges to $M_{0}=\Phi(\bar{x},\bar{y})$. The function $\Phi$ attains a sequentially strict maximum on $A\times A$ at $(\bar{x},\bar{y})$, so clause 1 of Sequentially Strict Maxima and Minima on a Subset of a Metric Space (i) gives that the sequence $((x_{k},y_{k}))_{k\in\mathbb{N}}$ converges to $(\bar{x},\bar{y})$ in $(E\times E,d_{\times})$. The coordinate maps of Real Hilbert Spaces: Series, Products, Orthonormal Bases and Differential Calculus (ii) send $(x_{k},y_{k})$ to $x_{k}$ and to $y_{k}$ and $(\bar{x},\bar{y})$ to $\bar{x}$ and to $\bar{y}$, so claim 4 of Properties of the Product of Two Real Inner Product Spaces gives the assertion. This proves Claim 1.

Claim 2 (localisation of the points). For every positive $\varepsilon\in\mathbb{R}$ there is a positive $\eta\in\mathbb{R}$ such that every $(x,y)\in A\times A$ with $M_{0}-\eta<\Phi(x,y)$ satisfies $|x-\bar{x}|<\varepsilon$ and $|y-\bar{y}|<\varepsilon$.

Proof. Suppose the assertion fails for some positive $\varepsilon$. Then for each $k\in\mathbb{N}$, failure for the positive number $\varepsilon_{k}$ provides $(x_{k},y_{k})\in A\times A$ with $M_{0}-\varepsilon_{k}<\Phi(x_{k},y_{k})$ for which at least one of $|x_{k}-\bar{x}|<\varepsilon$ and $|y_{k}-\bar{y}|<\varepsilon$ fails, that is, for which $\varepsilon\le|x_{k}-\bar{x}|$ or $\varepsilon\le|y_{k}-\bar{y}|$. By Claim 1 the sequences $(x_{k})$ and $(y_{k})$ converge to $\bar{x}$ and to $\bar{y}$ in $(E,d)$, so there is $k_{0}\in\mathbb{N}$ such that $|x_{k}-\bar{x}|<\varepsilon$ and $|y_{k}-\bar{y}|<\varepsilon$ both hold for every $k$ with $k_{0}\le k$ (take the larger of the two thresholds obtained for $\sigma=\varepsilon$, using claim 9 of Elementary Order Arithmetic in an Ordered Field on the corresponding indices). For $k=k_{0}$ this contradicts the previous sentence. This proves Claim 2.

Claim 3 (one-sided value bounds). For every positive $\varepsilon\in\mathbb{R}$ there is a positive $\eta\in\mathbb{R}$ such that every $(x,y)\in A\times A$ with $M_{0}-\eta<\Phi(x,y)$ satisfies

$$u(x)<u(\bar{x})+\varepsilon\qquad\text{and}\qquad v(\bar{y})-\varepsilon<v(y).$$

Proof. Suppose the first inequality fails to hold for all such pairs, for every positive $\eta$. Then for each $k\in\mathbb{N}$ there is $(x_{k},y_{k})\in A\times A$ with $M_{0}-\varepsilon_{k}<\Phi(x_{k},y_{k})$ and $u(\bar{x})+\varepsilon\le u(x_{k})$. By Claim 1 the sequence $(x_{k})$ lies in $A$ and converges to $\bar{x}$ in $(E,d)$. The real number $t=u(\bar{x})+\varepsilon$ satisfies $t\le u(x_{k})$ for every $k$, and $u$ has closed superlevel sets in $E$, so claim 1 of Functions with Closed Superlevel Sets: Sequential Characterisation, Semicontinuity, Perturbation and Limits gives $t\le u(\bar{x})$, that is $\varepsilon\le0$ by claim 3 of Elementary Arithmetic in an Ordered Field, contradicting $0<\varepsilon$. Hence some positive $\eta'$ makes the first inequality hold for all pairs as described.

The second inequality is the first one applied to $-v$ and $\bar{y}$: if for every positive $\eta$ some pair $(x,y)\in A\times A$ with $M_{0}-\eta<\Phi(x,y)$ had $v(y)\le v(\bar{y})-\varepsilon$, that is $-v(\bar{y})+\varepsilon\le-v(y)$, then choosing such a pair $(x_{k},y_{k})$ for $\eta=\varepsilon_{k}$ and using that $(y_{k})$ converges to $\bar{y}$ by Claim 1, that $-v$ has closed superlevel sets in $E$, and claim 1 of Functions with Closed Superlevel Sets: Sequential Characterisation, Semicontinuity, Perturbation and Limits would give $-v(\bar{y})+\varepsilon\le-v(\bar{y})$, again contradicting $0<\varepsilon$. Hence some positive $\eta''$ makes the second inequality hold. Taking for $\eta$ the lesser of $\eta'$ and $\eta''$, positive because it is one of them (claim 9 of Elementary Order Arithmetic in an Ordered Field), proves Claim 3.

Claim 4 (stability of the penalty). Let $\sigma\in\mathbb{R}$ satisfy $0<\sigma\le1$ and let $x,y\in E$ satisfy $|x-\bar{x}|<\sigma$ and $|y-\bar{y}|<\sigma$. Then

$$\Bigl|\tfrac{\alpha}{2}|x-y|^{2}-\tfrac{\alpha}{2}R^{2}\Bigr|\ \le\ 2\,|\alpha|\,\sigma\,(R+1),$$

where $R^{2}=R\,R$.

Proof. By the triangle inequality for the norm (claim 1 of The Norm Metric of a Real Inner Product Space: Triangle Inequalities, Limits and Continuity), applied twice in each line,

$$|x-y|\le|x-\bar{x}|+|\bar{x}-\bar{y}|+|\bar{y}-y|<R+2\sigma, \qquad R\le|\bar{x}-x|+|x-y|+|y-\bar{y}|<|x-y|+2\sigma,$$

so $-2\sigma<|x-y|-R<2\sigma$ and hence $\bigl||x-y|-R\bigr|\le2\sigma$ by claim 6 of Properties of the Absolute Value in an Ordered Field. Since $\sigma\le1$ we also have $0\le|x-y|+R<R+2\sigma+R\le2R+2$. Now $|x-y|^{2}-R^{2}=\bigl(|x-y|-R\bigr)\bigl(|x-y|+R\bigr)$, so by claim 4 of Properties of the Absolute Value in an Ordered Field and claim 5 of Elementary Arithmetic in an Ordered Field,

$$\bigl||x-y|^{2}-R^{2}\bigr|=\bigl||x-y|-R\bigr|\,\bigl(|x-y|+R\bigr)\le 2\sigma\,(2R+2)=4\sigma\,(R+1).$$

Multiplying by the nonnegative number $\tfrac{|\alpha|}{2}$ and using claim 4 of Properties of the Absolute Value in an Ordered Field again gives the claim. This proves Claim 4.

Claim 5 (the remaining value bounds). For every positive $\varepsilon\in\mathbb{R}$ there is a positive $\eta\in\mathbb{R}$ such that every $(x,y)\in A\times A$ with $M_{0}-\eta<\Phi(x,y)$ satisfies

$$u(\bar{x})-\varepsilon<u(x)\qquad\text{and}\qquad v(y)<v(\bar{y})+\varepsilon .$$

Proof. Let $\varepsilon$ be positive. Choose a positive $\sigma\le1$ with $2|\alpha|\sigma(R+1)<\tfrac{\varepsilon}{4}$, as follows: if $\alpha=0$ take $\sigma=1$, so that the left-hand side is $0$; otherwise $|\alpha|$ is positive by claim 1 of Properties of the Absolute Value in an Ordered Field and $R+1$ is positive, so the quotient $\tfrac{\varepsilon}{16|\alpha|(R+1)}$ exists and is positive by claim 7 of Elementary Order Arithmetic in an Ordered Field, and taking for $\sigma$ the lesser of it and $1$ gives $2|\alpha|\sigma(R+1)\le\tfrac{\varepsilon}{8}<\tfrac{\varepsilon}{4}$.

Let $\eta_{1}$ be a number provided by Claim 2 for $\sigma$, let $\eta_{2}$ be one provided by Claim 3 for $\tfrac{\varepsilon}{2}$, and let $\eta$ be the least of $\eta_{1}$, $\eta_{2}$ and $\tfrac{\varepsilon}{4}$, positive because it is one of them.

Let $(x,y)\in A\times A$ satisfy $M_{0}-\eta<\Phi(x,y)$. Then $|x-\bar{x}|<\sigma$ and $|y-\bar{y}|<\sigma$ by Claim 2, so Claim 4 and claim 6 of Properties of the Absolute Value in an Ordered Field give

$$\tfrac{\alpha}{2}R^{2}-\tfrac{\varepsilon}{4}<\tfrac{\alpha}{2}|x-y|^{2};$$

and Claim 3 gives $u(x)<u(\bar{x})+\tfrac{\varepsilon}{2}$ and $v(\bar{y})-\tfrac{\varepsilon}{2}<v(y)$. From the definition of $\Phi$,

$$u(x)=\Phi(x,y)+v(y)+\tfrac{\alpha}{2}|x-y|^{2} >\Bigl(M_{0}-\tfrac{\varepsilon}{4}\Bigr)+\Bigl(v(\bar{y})-\tfrac{\varepsilon}{2}\Bigr)+\Bigl(\tfrac{\alpha}{2}R^{2}-\tfrac{\varepsilon}{4}\Bigr) =u(\bar{x})-\varepsilon,$$

the last equality because $M_{0}=u(\bar{x})-v(\bar{y})-\tfrac{\alpha}{2}R^{2}$. Likewise

$$-v(y)=\Phi(x,y)-u(x)+\tfrac{\alpha}{2}|x-y|^{2} >\Bigl(M_{0}-\tfrac{\varepsilon}{4}\Bigr)-\Bigl(u(\bar{x})+\tfrac{\varepsilon}{2}\Bigr)+\Bigl(\tfrac{\alpha}{2}R^{2}-\tfrac{\varepsilon}{4}\Bigr) =-v(\bar{y})-\varepsilon,$$

that is $v(y)<v(\bar{y})+\varepsilon$ by claim 4 of Elementary Order Arithmetic in an Ordered Field. This proves Claim 5.

Conclusion. Let $\varepsilon\in\mathbb{R}$ be positive. Let $\eta_{1}$, $\eta_{2}$ and $\eta_{3}$ be numbers provided for $\varepsilon$ by Claims 2, 3 and 5 respectively, and let $\eta$ be the least of the three, positive because it is one of them. Let $(x,y)\in A\times A$ satisfy $\Phi(\bar{x},\bar{y})-\eta<\Phi(x,y)$. Claim 2 gives $|x-\bar{x}|<\varepsilon$ and $|y-\bar{y}|<\varepsilon$. Claims 3 and 5 give

$$u(\bar{x})-\varepsilon<u(x)<u(\bar{x})+\varepsilon, \qquad v(\bar{y})-\varepsilon<v(y)<v(\bar{y})+\varepsilon,$$

that is $-\varepsilon<u(x)-u(\bar{x})<\varepsilon$ and $-\varepsilon<v(y)-v(\bar{y})<\varepsilon$ by claim 3 of Elementary Arithmetic in an Ordered Field, whence $|u(x)-u(\bar{x})|<\varepsilon$ and $|v(y)-v(\bar{y})|<\varepsilon$ by claim 9 of Properties of the Absolute Value in an Ordered Field. This is the assertion of the lemma.