Proof of A Periodic Potential for a Torus-Cyclically Monotone Set: Lipschitz Periodic Part, Convex Lift and Subgradients

Each result cited below is universally quantified over the data in its own statement. Throughout, $L=\sqrt{d}/2$, a nonnegative real number, and for $x,y\in\mathbb{R}^{d}$ we write

$$\kappa(x,y)=\tfrac12\,d_{\mathbb{T}}(x,y)^{2}.$$

Finite sums $\sum_{i=1}^{m}$ are those of Finite Sum Notation in a Field in the field of real numbers; from Properties of Finite Sums we use the recursion and the independence of the extending family (claim 1), additivity (claim 2) and homogeneity (claim 3, with the factors $\tfrac12$ and $-1$, so that a finite sum of differences is the difference of the finite sums). Points of $\mathbb{R}^{d}$ are added, subtracted and scaled coordinatewise, as in Sum of Points of $\mathbb{R}^n$, Scalar Multiple of a Point of $\mathbb{R}^n$ and Difference, Dot Product, and Orthogonality in $\mathbb{R}^n$, and $\mathbb{R}^{d}$ is a real vector space by Euclidean Space $\mathbb{R}^n$ is a Real Vector Space. Since $0\in\mathbb{Z}$ and $\mathbb{Z}$ is closed under negation and addition (claim 2 of Arithmetic, Order, Discreteness and Intervals of the Integers), the lattice $\mathbb{Z}^{d}$ of Lattice-Periodic Functions and the Periodic Function Classes §lattice contains the origin $0_{\mathbb{R}^{d}}$ and is closed under negation and addition. The set $\mathbb{R}^{d}$ is convex, since every point $t\,x+(1-t)\,y$ with $x,y\in\mathbb{R}^{d}$ lies in $\mathbb{R}^{d}$.

Step 0. Three elementary facts.

(a) Expansion. For all $a,b\in\mathbb{R}^{d}$,

$$\tfrac12\lVert a\rVert^{2}-\tfrac12\lVert a-b\rVert^{2}=a\cdot b-\tfrac12\lVert b\rVert^{2}.$$

Indeed, by claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ one has $\lVert a-b\rVert^{2}=(a-b)\cdot(a-b)$; by claims 3 and 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ this equals $a\cdot a-b\cdot a-a\cdot b+b\cdot b$, and by claim 1 there (symmetry) together with claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ it equals $\lVert a\rVert^{2}-2\,a\cdot b+\lVert b\rVert^{2}$. Multiplying by $\tfrac12$ and subtracting from $\tfrac12\lVert a\rVert^{2}$ gives the identity.

(b) Nearest lifts. Let $x,y\in\mathbb{R}^{d}$. For every $\tilde y\in y+\mathbb{Z}^{d}$,

$$d_{\mathbb{T}}(x,y)\le\lVert x-\tilde y\rVert=\lVert\tilde y-x\rVert\qquad\text{and hence}\qquad\kappa(x,y)\le\tfrac12\lVert x-\tilde y\rVert^{2};$$

and the point $\tilde y_{x}=x+\varpi(y-x)$ belongs to $y+\mathbb{Z}^{d}$ and satisfies $\lVert x-\tilde y_{x}\rVert=d_{\mathbb{T}}(x,y)$, hence $\kappa(x,y)=\tfrac12\lVert x-\tilde y_{x}\rVert^{2}$. To see this, write $\tilde y=y+m$ with $m\in\mathbb{Z}^{d}$. Then $x-\tilde y=(-1)\bigl(y-x-(-m)\bigr)$ and $\tilde y-x=y-x-(-m)$, so claim 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ (with $|-1|=1$) gives $\lVert x-\tilde y\rVert=\lVert\tilde y-x\rVert=\lVert y-x-(-m)\rVert$; as $-m\in\mathbb{Z}^{d}$, The Flat Torus Distance: Minimality of the Wrapped Displacement, Periodicity, the Metric on the Unit Cell and the Lipschitz Bound §minimal gives $d_{\mathbb{T}}(x,y)\le\lVert y-x-(-m)\rVert$. Both $d_{\mathbb{T}}(x,y)$ (The Wrapped Displacement and the Flat Torus Distance §distance) and $\lVert x-\tilde y\rVert$ (claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$) are nonnegative, and for real numbers $0\le s\le t$ one has $s\cdot s\le s\cdot t\le t\cdot t$, multiplication by a nonnegative element preserving the order of the ordered field $\mathbb{R}$; so $d_{\mathbb{T}}(x,y)^{2}\le\lVert x-\tilde y\rVert^{2}$, and multiplying by $\tfrac12$ gives the second inequality. For $\tilde y_{x}$: the point $k_{0}=y-x-\varpi(y-x)$ lies in $\mathbb{Z}^{d}$ by The Flat Torus Distance: Minimality of the Wrapped Displacement, Periodicity, the Metric on the Unit Cell and the Lipschitz Bound §range, and $\tilde y_{x}=y+(-k_{0})$ with $-k_{0}\in\mathbb{Z}^{d}$; moreover $x-\tilde y_{x}=(-1)\varpi(y-x)$, so $\lVert x-\tilde y_{x}\rVert=\lVert\varpi(y-x)\rVert=d_{\mathbb{T}}(x,y)$ by claim 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and The Wrapped Displacement and the Flat Torus Distance §distance.

(c) Periodicity and Lipschitz bound of $\kappa$ in the first variable. For all $x,x',y\in\mathbb{R}^{d}$ and $k\in\mathbb{Z}^{d}$ one has $\kappa(x+k,y)=\kappa(x,y)$, by The Flat Torus Distance: Minimality of the Wrapped Displacement, Periodicity, the Metric on the Unit Cell and the Lipschitz Bound §symmetry applied with the lattice points $k$ and $0_{\mathbb{R}^{d}}$; and $|\kappa(x,y)-\kappa(x',y)|\le L\lVert x-x'\rVert$, which is the second inequality of The Flat Torus Distance: Minimality of the Wrapped Displacement, Periodicity, the Metric on the Unit Cell and the Lipschitz Bound §lipschitz multiplied by $\tfrac12$.

Step 1. Chains and their values. Since $\Gamma$ is nonempty, fix once and for all a point $\hat w\in\Gamma$ and put $\hat x=\mathrm{pr}_{1}(\hat w)$. A chain $C$ consists of a natural number $N$ with $2\le N$ and a map $[N]\to\Gamma$, $i\mapsto w_{i}$, with $w_{1}=\hat w$; we write $x_{i}=\mathrm{pr}_{1}(w_{i})$ and $y_{i}=\mathrm{pr}_{2}(w_{i})$ for $i\in[N]$, so that $x_{1}=\hat x$. Let $\mathcal{C}$ be the set of all chains; it is nonempty, containing the chain with $N=2$ and $w_{1}=w_{2}=\hat w$. For a chain $C$ (with $N-1\in\mathbb{N}$ because $2\le N$) put

$$K_{C}=\sum_{i=1}^{N-1}\bigl(\kappa(x_{i+1},y_{i})-\kappa(x_{i},y_{i})\bigr)-\kappa(x_{N},y_{N}),\qquad g_{C}(x)=K_{C}+\kappa(x,y_{N})\quad(x\in\mathbb{R}^{d}).$$

These functions have the following four properties.

(i) $0\le g_{C}(\hat x)$. Put $x_{N+1}=x_{1}$ and $b_{i}=\kappa(x_{i+1},y_{i})-\kappa(x_{i},y_{i})$ for $i\in[N]$. By the recursion of claim 1 of Properties of Finite Sums, applied with $S(N-1)=N$, and the independence of the extending family stated there,

$$\sum_{i=1}^{N}b_{i}=\sum_{i=1}^{N-1}\bigl(\kappa(x_{i+1},y_{i})-\kappa(x_{i},y_{i})\bigr)+\kappa(x_{1},y_{N})-\kappa(x_{N},y_{N})=g_{C}(x_{1})=g_{C}(\hat x).$$

By claims 2 and 3 of Properties of Finite Sums,

$$\sum_{i=1}^{N}b_{i}=\tfrac12\Bigl(\sum_{i=1}^{N}d_{\mathbb{T}}(x_{i+1},y_{i})^{2}-\sum_{i=1}^{N}d_{\mathbb{T}}(x_{i},y_{i})^{2}\Bigr),$$

which is nonnegative because $\Gamma$ is torus-cyclically monotone: that definition, applied to $N$ and the points $w_{1},\dots,w_{N}\in\Gamma$, with $x_{N+1}=x_{1}$ exactly as there, gives $\sum_{i=1}^{N}d_{\mathbb{T}}(x_{i},y_{i})^{2}\le\sum_{i=1}^{N}d_{\mathbb{T}}(x_{i+1},y_{i})^{2}$.

(ii) Periodicity. $g_{C}(x+k)=g_{C}(x)$ for all $x\in\mathbb{R}^{d}$ and $k\in\mathbb{Z}^{d}$, by Step 0(c).

(iii) Lipschitz bound. $|g_{C}(x)-g_{C}(x')|=|\kappa(x,y_{N})-\kappa(x',y_{N})|\le L\lVert x-x'\rVert$ for all $x,x'\in\mathbb{R}^{d}$, by Step 0(c).

(iv) Extension. Let $w\in\Gamma$, $x=\mathrm{pr}_{1}(w)$ and $y=\mathrm{pr}_{2}(w)$, and let $C^{+}$ be the chain with $N+1$ points $w_{1},\dots,w_{N},w_{N+1}$, where $w_{N+1}=w$, so that $x_{N+1}=x$ and $y_{N+1}=y$ for $C^{+}$. The first $N-1$ summands defining $K_{C^{+}}$ are those defining $K_{C}$, since they involve only $w_{1},\dots,w_{N}$, and the recursion of claim 1 of Properties of Finite Sums, applied with $S(N-1)=N$, gives

$$K_{C^{+}}=\sum_{i=1}^{N-1}\bigl(\kappa(x_{i+1},y_{i})-\kappa(x_{i},y_{i})\bigr)+\kappa(x,y_{N})-\kappa(x_{N},y_{N})-\kappa(x,y)=g_{C}(x)-\kappa(x,y).$$

Hence $g_{C^{+}}(x')=g_{C}(x)+\kappa(x',y)-\kappa(x,y)$ for every $x'\in\mathbb{R}^{d}$.

Step 2. Definition of $\varphi$. For $x\in\mathbb{R}^{d}$ let $S(x)=\{g_{C}(x):C\in\mathcal{C}\}$, a nonempty subset of $\mathbb{R}$ because $\mathcal{C}$ is nonempty. For every chain $C$, (iii) and (i) give

$$g_{C}(x)\ge g_{C}(\hat x)-L\lVert x-\hat x\rVert\ge-L\lVert x-\hat x\rVert ,$$

so $S(x)$ is bounded below by $-L\lVert x-\hat x\rVert$, and by Existence of the Infimum of a Nonempty Subset of $\mathbb{R}$ Bounded Below it has a greatest lower bound in $\mathbb{R}$. Define $\varphi(x)=\inf S(x)$, and $\psi(x)=\tfrac12\lVert x\rVert^{2}-\varphi(x)$ as in the statement. By the definition of a greatest lower bound we shall use two facts: $\varphi(x)\le g_{C}(x)$ for every chain $C$; and every real lower bound of $S(x)$ is at most $\varphi(x)$.

Step 3. Claim 1. Let $x\in\mathbb{R}^{d}$ and $k\in\mathbb{Z}^{d}$. By (ii), $S(x+k)=S(x)$, so $\varphi(x+k)=\varphi(x)$ and $\varphi$ is $\mathbb{Z}^{d}$-periodic. Let $x,x'\in\mathbb{R}^{d}$. For every chain $C$, Step 2 and (iii) give $\varphi(x)\le g_{C}(x)\le g_{C}(x')+L\lVert x-x'\rVert$, so $\varphi(x)-L\lVert x-x'\rVert$ is a lower bound of $S(x')$ and therefore $\varphi(x)-L\lVert x-x'\rVert\le\varphi(x')$. Exchanging $x$ and $x'$, and using $\lVert x'-x\rVert=\lVert x-x'\rVert$ (claim 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$), we get $|\varphi(x)-\varphi(x')|\le L\lVert x-x'\rVert$. As $\lVert x-x'\rVert=d_{E}(x,x')$ by claim 2 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and $|\varphi(x)-\varphi(x')|$ is the distance of the absolute-value metric, $\varphi$ is Lipschitz with constant $L=\sqrt{d}/2$.

Step 4. Claim 3. Let $w\in\Gamma$, $x=\mathrm{pr}_{1}(w)$, $y=\mathrm{pr}_{2}(w)$ and $x'\in\mathbb{R}^{d}$. For every chain $C$, Step 2 applied at $x'$ to the chain $C^{+}$ of (iv) gives

$$\varphi(x')\le g_{C^{+}}(x')=g_{C}(x)+\kappa(x',y)-\kappa(x,y).$$

Hence $\varphi(x')-\kappa(x',y)+\kappa(x,y)$ is a lower bound of $S(x)$, so it is at most $\varphi(x)$; rearranging,

$$\varphi(x')\le\varphi(x)+\tfrac12d_{\mathbb{T}}(x',y)^{2}-\tfrac12d_{\mathbb{T}}(x,y)^{2}.$$

Step 5. Claim 2. For a chain $C$, whose last point has second coordinate $y_{N}$, and for $\tilde y\in y_{N}+\mathbb{Z}^{d}$, let $f_{C,\tilde y}:\mathbb{R}^{d}\to\mathbb{R}$ be given by

$$f_{C,\tilde y}(x)=\tilde y\cdot x+\Bigl(-\tfrac12\lVert\tilde y\rVert^{2}-K_{C}\Bigr).$$

By claim 1 of Affine Functions, Sums, Nonnegative Multiples and Pointwise Suprema of Convex Functions, applied to the convex set $\mathbb{R}^{d}$, the point $p=\tilde y$ and the constant $-\tfrac12\lVert\tilde y\rVert^{2}-K_{C}$, each $f_{C,\tilde y}$ is convex on $\mathbb{R}^{d}$. Let $\mathcal{F}$ be the set of all these functions; it is nonempty, since $\mathcal{C}$ is nonempty and $y_{N}=y_{N}+0_{\mathbb{R}^{d}}\in y_{N}+\mathbb{Z}^{d}$. Fix $x\in\mathbb{R}^{d}$; we show that $\psi(x)$ is the least upper bound of $\{f(x):f\in\mathcal{F}\}$.

Upper bound. Let $C$ be a chain and $\tilde y\in y_{N}+\mathbb{Z}^{d}$. By Step 0(b), $\kappa(x,y_{N})\le\tfrac12\lVert x-\tilde y\rVert^{2}$, so $g_{C}(x)\le K_{C}+\tfrac12\lVert x-\tilde y\rVert^{2}$. By Step 0(a) and the symmetry of the dot product (claim 1 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$), and then Step 2,

$$f_{C,\tilde y}(x)=\tfrac12\lVert x\rVert^{2}-\tfrac12\lVert x-\tilde y\rVert^{2}-K_{C}\le\tfrac12\lVert x\rVert^{2}-g_{C}(x)\le\tfrac12\lVert x\rVert^{2}-\varphi(x)=\psi(x).$$

Least. Let $b\in\mathbb{R}$ be an upper bound of $\{f(x):f\in\mathcal{F}\}$, and let $C$ be a chain. The point $\tilde y_{x}=x+\varpi(y_{N}-x)$ of Step 0(b) lies in $y_{N}+\mathbb{Z}^{d}$ and satisfies $\kappa(x,y_{N})=\tfrac12\lVert x-\tilde y_{x}\rVert^{2}$, so $g_{C}(x)=K_{C}+\tfrac12\lVert x-\tilde y_{x}\rVert^{2}$ and, by the same identity as above, $f_{C,\tilde y_{x}}(x)=\tfrac12\lVert x\rVert^{2}-g_{C}(x)$. Hence $\tfrac12\lVert x\rVert^{2}-g_{C}(x)\le b$, that is $\tfrac12\lVert x\rVert^{2}-b\le g_{C}(x)$. As $C$ was arbitrary, $\tfrac12\lVert x\rVert^{2}-b$ is a lower bound of $S(x)$, so $\tfrac12\lVert x\rVert^{2}-b\le\varphi(x)$, that is $\psi(x)\le b$.

Thus for every $x$ the set $\{f(x):f\in\mathcal{F}\}$ has an upper bound, and its least upper bound is $\psi(x)$. Claim 4 of Affine Functions, Sums, Nonnegative Multiples and Pointwise Suprema of Convex Functions, applied to the convex set $\mathbb{R}^{d}$ and the nonempty family $\mathcal{F}$ of convex functions, shows that the function whose value at $x$ is that least upper bound, namely $\psi$, is convex on $\mathbb{R}^{d}$.

Step 6. Claim 4. Let $w\in\Gamma$, $x=\mathrm{pr}_{1}(w)$, $y=\mathrm{pr}_{2}(w)$, and let $\tilde y\in y+\mathbb{Z}^{d}$ satisfy $\lVert\tilde y-x\rVert=d_{\mathbb{T}}(x,y)$. By claim 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, $\lVert x-\tilde y\rVert=\lVert\tilde y-x\rVert$, so $\kappa(x,y)=\tfrac12\lVert x-\tilde y\rVert^{2}$. Let $x'\in\mathbb{R}^{d}$. By Step 0(b), $\kappa(x',y)\le\tfrac12\lVert x'-\tilde y\rVert^{2}$, so claim 3 (Step 4) gives

$$\varphi(x')\le\varphi(x)+\tfrac12\lVert x'-\tilde y\rVert^{2}-\tfrac12\lVert x-\tilde y\rVert^{2},$$

and therefore

$$\psi(x')=\tfrac12\lVert x'\rVert^{2}-\varphi(x')\ge\Bigl(\tfrac12\lVert x'\rVert^{2}-\tfrac12\lVert x'-\tilde y\rVert^{2}\Bigr)-\varphi(x)+\tfrac12\lVert x-\tilde y\rVert^{2}.$$

By Step 0(a) with $a=x'$ and $b=\tilde y$, the bracket equals $x'\cdot\tilde y-\tfrac12\lVert\tilde y\rVert^{2}$; by Step 0(a) with $a=x$ and $b=\tilde y$, $\tfrac12\lVert x-\tilde y\rVert^{2}=\tfrac12\lVert x\rVert^{2}-x\cdot\tilde y+\tfrac12\lVert\tilde y\rVert^{2}$. Adding, and using claims 1 and 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ to write $x'\cdot\tilde y-x\cdot\tilde y=\tilde y\cdot(x'-x)$,

$$\psi(x')\ge\tfrac12\lVert x\rVert^{2}-\varphi(x)+\tilde y\cdot(x'-x)=\psi(x)+\tilde y\cdot(x'-x).$$

Since this holds for every $x'\in\mathbb{R}^{d}$, and $\mathbb{R}^{d}$ is convex, $\tilde y$ belongs to the subdifferential $\partial_{\mathbb{R}^{d}}\psi(x)$.