# Sharp PDE estimates for random two-dimensional bipartite matching with power
cost function

L. Ambrosio  Scuola Normale Superiore, Pisa<EMAIL_ADDRESS>,  F.
Vitillaro  Scuola Normale Superiore, Pisa<EMAIL_ADDRESS>and  D.
Trevisan  Università di Pisa<EMAIL_ADDRESS>
###### Abstract.

We investigate the random bipartite optimal matching problem on a flat torus
in two-dimensions, considering general strictly convex power costs of the
distance. We extend the successful ansatz first introduced by Caracciolo et
al. for the quadratic case, involving a linear Poisson equation, to a non-
linear equation of $q$-Poisson type, allowing for a more comprehensive
analysis of the optimal transport cost. Our results establish new asymptotic
connections between the energy of the solution to the PDE and the optimal
transport cost, providing insights on their asymptotic behavior.

##  1\. Introduction and main result

Let $(X_{1},\ldots,X_{n})$, $(Y_{1},\ldots,Y_{n})$ be two sets of $n$ random
points independent and uniformly distributed on the flat torus
${\mathbb{T}^{2}}=\mathbb{R}^{2}/\mathbb{Z}^{2}$, i.e., with common law given
by the Lebesgue measure $\mathfrak{m}$ on ${\mathbb{T}^{2}}$. The random
bipartite optimal matching problem concerns the study of the optimal coupling
(with respect to a certain cost function) of these points, that is, the
optimal transport from the empirical measure
$\mu^{n}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}}$ to
$\nu_{n}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{Y_{i}}$, in particular in the limit
$n\gg 1$.

For the quadratic cost $c(x,y):=\mathbf{d}(x,y)^{2}$, where $\mathbf{d}$ is
the quotient (flat) distance in ${\mathbb{T}^{2}}$, the seminal paper [CLPS14]
gave a very appealing PDE ansatz on the asymptotic of the expectation of the
optimal transport cost, based on a linearization of the Monge-Ampère equation.
While it was already known in the literature that, for the cost
$c=\mathbf{d}^{p}$ in dimension $d=2$, the expectation of the optimal
transport cost behaves like $(n^{-1}\ln n)^{p/2}$ (for $p=1$ since [AKT84]),
in [CLPS14] they managed to predict the limit coefficient as $1/(2\pi)$ in the
case $p=2$, exploiting Fourier analysis and some renormalization procedure.
This prediction was then rigorously proven in [AST19], together with a new PDE
proof of the classical bounds in [AKT84].

Since then, several works have been using such PDE ansatz to estimate with
different degrees of sharpness the asymptotics of random optimal matching
costs and their solutions, in several settings. Focusing only on the two-
dimensional case, but possibly including more general manifolds than
${\mathbb{T}^{2}}$, we mention here the rigorous results [BL21, AG19, AGT19,
GHO21, AGT22, GH22, HMO23a, GHO23, CM24] as well as further intriguing
predictions from the physical literature [BC20, BCCDSS21] and refer e.g. to
the contribution [Led22] for a more general overview on the subject.

The aim of the present work is to establish new asymptotic connections between
the solution of a “linearized PDE” and the expectation of the optimal
transport cost, on ${\mathbb{T}^{2}}$, for general $p>1$, extending the main
results in [AST19, AG19]. Let us mention here that recently other works
focused on two-dimensional random optimal matching problems, beyond the
quadratic cost, in particular [Koc24], where the quantitative harmonic
approximation techniques – originally in [GHO21], see also the exposition
[KO23] – are extended to any $p>1$, and the preprint [HMO23], where existence
of a $p$-cyclically monotone stationary matching from a Poisson point process
to the Lebesgue measure is ruled out for any $p>1$ – the quadratic case is
covered in [HMO23a].

In order to describe here informally our results, we may treat the empirical
measures $\mu^{n}=\rho_{0}\mathfrak{m}$, $\nu^{n}=\rho_{1}\mathfrak{m}$ as
absolutely continuous with respect to $\mathfrak{m}$. This will be made
rigorous by a regularization with the heat kernel $P_{t}$ on
${\mathbb{T}^{2}}$, as performed in [AST19]. We first recall (see e.g.,
[ABS21, Remark 5.3]) that the Kantorovich potential $\phi$ is related to the
optimal transport map $T$ by the identity

$T(x)=x-|\nabla\phi(x)|^{q-2}\nabla\phi(x),$

where, throughout the paper, $q=p/(p-1)$ denotes the dual exponent of $p$.
Then, the Monge-Ampère equation takes the form

$\rho_{1}(x-|\nabla\phi(x)|^{q-2}\nabla\phi(x))\det(\nabla(x-|\nabla\phi(x)|^{q-2}\nabla\phi(x)))=\rho_{0}(x).$

This PDE contains three non-linearities: the determinant, the dependence of
$\rho_{1}$ on $\nabla\phi$ and finally, when $p\neq 2$, the nonlinear term
$|\nabla\phi|^{q-2}\nabla\phi$. Our main result shows that in order to obtain
a good first-order approximation of the expected value of the transport cost
it is sufficient to remove only the first two non-linearities, keeping the
third one. This invokes the “linearized” (but still nonlinear!) PDE of
$q$-Poisson type

$-{\rm
div}\bigl{(}|\nabla\phi|^{q-2}\nabla\phi)=\rho_{1}-\rho_{0},\qquad\phi\in
H^{1,q}({\mathbb{T}^{2}})$ (1.1)

in the sense of distributions, namely

$\int_{\mathbb{T}^{2}}|\nabla\phi|^{q-2}\langle\nabla\phi,\nabla\eta\rangle\mbox{
}d\mathfrak{m}=\int(\rho_{1}-\rho_{0})\eta\mbox{
}d\mathfrak{m}\qquad\forall\eta\in H^{1,q}({\mathbb{T}^{2}}),$ (1.2)

where we always assume, to ensure uniqueness, that
$\int_{\mathbb{T}^{2}}\phi\,\mathrm{d}\mathfrak{m}=0$, yielding the
approximation

$|T(x)-x|^{p}\approx||\nabla\phi(x)|^{q-2}\nabla\phi(x)|^{p}=|\nabla\phi(x)|^{q}.$
(1.3)

Our main result makes precise such approximation (see Section 2 for more
details on the notation).

######  Theorem 1.1 (Main result).

If $(X_{i})_{i=1}^{\infty}$ and $(Y_{i})_{i=1}^{\infty}$ are independent and
identically distributed random variables with law $\mathfrak{m}$ on
${\mathbb{T}^{2}}$, then

$\lim_{n\to\infty}\biggl{(}\frac{n}{\ln
n}\biggr{)}^{p/2}\biggl{|}\operatorname{\mathbb{E}}\left[W_{p}^{p}(\mu^{n},\nu^{n})\right]-\operatorname{\mathbb{E}}\left[\int_{\mathbb{T}^{2}}|\nabla\phi_{n}|^{q}\,\mathrm{d}\mathfrak{m}\right]\biggr{|}=0$

where

$\mu^{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}},\qquad\nu^{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{Y_{i}},$
(1.4)

and $\phi_{n}$ is the solution to (1.2) with random right hand side
$\rho_{1}-\rho_{0}=\rho_{1,n}-\rho_{0,n}$ and

$\rho_{0,n}\mathfrak{m}=P_{t_{n}}\mu^{n},\qquad\rho_{1,n}\mathfrak{m}=P_{t_{n}}\nu^{n}$
(1.5)

provided $t_{n}\gg n^{-1}\ln n$ and $\ln(nt_{n})\ll\ln n$.

For instance, a good choice of the intermediate regularization scale $t_{n}$
in the main result would be $t_{n}=n^{-1}(\ln n)^{\beta}$ with $\beta>1$.
Thanks to this result, the existence of the limit

$\lim_{n\to\infty}\frac{\operatorname{\mathbb{E}}\left[W_{p}^{p}(\mu^{n},\nu^{n})\right]}{\bigl{(}(\ln
n)/n\bigr{)}^{p/2}}$

is equivalent to the existence of the limit when, in the numerator,
$\operatorname{\mathbb{E}}\left[W_{p}^{p}(\mu^{n},\nu^{n})\right]$ is replaced
by
$\operatorname{\mathbb{E}}\left[\int_{\mathbb{T}^{2}}|\nabla\phi_{n}|^{q}\,\mathrm{d}\mathfrak{m}\right]$,
with $\phi_{n}$ solutions to the PDE (1.2) with a random right hand side
(1.5). It would be interesting to prove or disprove the existence of the limit
thanks to this reduction to a stochastic PDE.

In order to prove Theorem 1.1, the only probabilistic ingredients (see Section
2.4) will consist in checking that as $n\rightarrow\infty$, with high
probability the densities $\rho_{i,n}$ in (1.5), for $i=0,1$ are both
sufficiently close to the constant density (Proposition 2.6), as well as not
too far from $\mu^{n}$ and $\nu^{n}$ in the Wasserstein sense (Proposition
2.5), collecting and slightly extending some results from [AG19] and [AST19].
Then, in Section 4.1 and Section 4.2 we will focus our efforts on showing the
following deterministic result.

######  Theorem 1.2.

Let $p>1$, let $\phi$ be a solution of (1.2), and let
$c:=2\max\limits_{i=0,1}\|\rho_{i}-1\|_{L^{\infty}({\mathbb{T}^{2}})}$. Then
there exist $\underline{\delta}=\underline{\delta}(c,p)$ and
$\overline{\delta}=\overline{\delta}(c,p)$ such that
$\underline{\delta}+\overline{\delta}\rightarrow 0$ as $c\rightarrow 0$ and

$(1-\underline{\delta})\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}\leq
W_{p}^{p}(\rho_{0}\mathfrak{m},\rho_{1}\mathfrak{m})\leq(1+\overline{\delta})\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}.$

This result actually holds, with the same proof, on any $d$-dimensional torus.
The extension to the setting of compact Riemannian manifolds (along the lines
of [AST19]) possibly with boundary is beyond the scope of this note, and
requires in particular the understanding in that more general setting of the
stability of the estimates from above for the Riemannian analogous of the
operator ${\rm div}(|\nabla\phi|^{q-1}\nabla\phi)$ under the action of the
Hopf-Lax semigroup, even after shocks.

Acknowledgements. The authors thank N. Gigli for having pointed out to them
[Oht14, Section 4.3] where, on Riemannian manifolds, via the theory of
characteristics, the preservation of upper bounds on the $q$-Laplacian under
the action of the $p$-Hopf-Lax semigroup is shown, even in the nonlinear case
$p\neq 2$, before shocks. Eventually, in the case of the flat space
${\mathbb{T}^{2}}$, the proof we gave in Proposition 3.2 does not use this
computation and works even beyond shocks, using solutions in the viscosity
sense.

L.A. and F.V. acknowledge the PRIN Italian grant 202244A7YL “Gradient Flows
and Non-Smooth Geometric Structures with Applications to Optimization and
Machine Learning”. D.T. acknowledges the MUR Excellence Department Project
awarded to the Department of Mathematics, University of Pisa, CUP
I57G22000700001, the HPC Italian National Centre for HPC, Big Data and Quantum
Computing - Proposal code CN1 CN00000013, CUP I53C22000690001, the PRIN
Italian grant 2022WHZ5XH - “understanding the LEarning process of QUantum
Neural networks (LeQun)”, CUP J53D23003890006, the INdAM-GNAMPA project 2023
“Teoremi Limite per Dinamiche di Discesa Gradiente Stocastica: Convergenza e
Generalizzazione”, INdAM-GNAMPA project 2024 “Tecniche analitiche e
probabilistiche in informazione quantistica” and the project G24-202
“Variational methods for geometric and optimal matching problems” funded by
Università Italo Francese. Research also partly funded by PNRR - M4C2 -
Investimento 1.3, Partenariato Esteso PE00000013 - ”FAIR - Future Artificial
Intelligence Research” - Spoke 1 ”Human-centered AI”, funded by the European
Commission under the NextGeneration EU programme.

##  2\. Preliminaries

###  2.1. The Wasserstein distance

Given probability measures $\mu$, $\nu$ on ${\mathbb{T}^{2}}$ and $p\geq 1$ we
define the $p-$Wasserstein distance between $\mu$ and $\nu$ as

$W_{p}(\mu,\nu):=\left.\min\left\\{\left(\int_{{\mathbb{T}^{2}}\times{\mathbb{T}^{2}}}\mathbf{d}(x,y)^{p}d\pi(x,y)\right)^{1/p}\right|\pi_{1}=\mu,\pi_{2}=\nu\right\\}.$

We refer to [ABS21] for an introduction to the subject. In particular, we will
use throughout that $W_{p}$ enjoys the triangle inequality. Moreover, we
recall here for later use the following consequence of the Benamou-Brenier
formula, see e.g. [Pey18], [Led17, Theorem 2] or [GT21, Lemma 3.4].

######  Proposition 2.1.

Let $\mu=\rho_{0}\mathfrak{m}$, $\nu=\rho_{1}\mathfrak{m}$ be absolutely
continuous with respect to $\mathfrak{m}$ and let $\phi$ be a solution to
(1.2) with $q=2$. Then, for every $p\geq 1$ there exists a constant
$C=C({\mathbb{T}^{2}},p)<\infty$ such that

$W_{p}^{p}(\mu,\nu)\leq C(\operatorname{ess-
inf}\rho_{1})^{1-p}\int_{{\mathbb{T}^{2}}}|\nabla\phi|^{p}d\mathfrak{m}.$
(2.1)

We notice that the bound above is asymmetric in the roles of $\mu$ and $\nu$,
since only $\rho_{1}$ is required to be (essentially) bounded from below. In
some sense, our work aims to sharpen (2.1) by replacing the linear Poisson
equation with the non-linear $q$-Poisson one, and indeed Proposition 4.1 below
is proved using a similar argument. However, (2.1) is useful as one can
combine it with harmonic analysis tools, as done e.g. in [AST19, Led17]. For
example, for any $p>1$, by the classical boundedness of the Riesz transform
operator $\nabla(-\Delta)^{-1/2}$ on ${\mathbb{T}^{2}}$, where
$(-\Delta)^{-1/2}$ is defined as a Fourier multiplier, one can further bound
from above

$\int_{{\mathbb{T}^{2}}}|\nabla\phi|^{p}d\mathfrak{m}\leq
C\int_{{\mathbb{T}^{2}}}|(-\Delta)^{-1/2}(\rho_{1}-\rho_{0})|^{p}d\mathfrak{m},$

where $C=C({\mathbb{T}^{2}},p)<\infty$. Hence, from (2.1) we further deduce
the upper bound

$W_{p}^{p}(\mu,\nu)\leq C(\operatorname{ess-
inf}\rho_{1})^{1-p}\int_{{\mathbb{T}^{2}}}|(-\Delta)^{-1/2}(\rho_{1}-\rho_{0})|^{p}d\mathfrak{m},$
(2.2)

where again $C=C({\mathbb{T}^{2}},p)<\infty$.

###  2.2. Viscosity solutions

Viscosity solutions are designed to give a suitable notion of solution (with
good properties such us uniqueness, stability and comparison principles) for
general non-linear equations for which the distributional point of view does
not make sense, as fully nonlinear PDE’s. However, this notion reveals to be
useful also for PDE’s having a distributional formulation. This is the case of
the $q$-Laplace (also called $q$-Poisson) equation considered in this paper,
associated to the differential operator

$-\Delta_{q}u:=-{\rm div}\bigl{(}|\nabla u|^{q-2}\nabla u).$

Actually, we will just deal with supersolutions.

######  Definition 2.2.

Let $g:{\mathbb{T}^{2}}\to\mathbb{R}$. We say that a function
$f:{\mathbb{T}^{2}}\rightarrow(-\infty,+\infty]$ is a viscosity supersolution
for the equation $-\Delta_{q}u+g=0$, and we write

$-\Delta_{q}u+g\geq 0\quad\text{in the viscosity sense}$ (2.3)

if the following conditions hold:

  1. (i)

$f$ is lower semicontinuous, $f\not\equiv+\infty$, and

  2. (ii)

whenever $x_{0}\in{\mathbb{T}^{2}}$ and $\varphi\in C^{2}({\mathbb{T}^{2}})$
are such that $f-\varphi$ has a local minimum at $x_{0}$ and
$\nabla\varphi(x_{0})\neq 0$, we have

$-\Delta_{q}\varphi(x_{0})+g(x_{0})\geq 0.$

Definition 2.2 is adapted to the special form of the $q$-Laplace PDE. Indeed,
the additional requirement $\nabla\varphi(x_{0})\neq 0$ (not present in the
general theory of viscosity solutions, see for instance [CIL92]) is due to the
fact that the expression

$\Delta_{q}\varphi=|\nabla\varphi|^{q-4}\left[|\nabla\varphi|^{2}\Delta\varphi+(q-2)\sum_{i,\,j=1}^{n}\frac{\partial\varphi}{\partial
x_{i}}\frac{\partial\varphi}{\partial
x_{j}}\frac{\partial^{2}\varphi}{\partial x_{i}\partial x_{j}}\right]$ (2.4)

is singular at the critical points of $\varphi$, when $1<q<2$.

######  Remark 2.3.

With this convention, any $f\in C^{2}({\mathbb{T}^{2}})$ satisfying
$-\Delta_{q}f+g\geq 0$ in the pointwise sense is also a viscosity
supersolution. This follows from the fact that if we call

$F_{q}(v,S):(\mathbb{R}^{2}\setminus\\{0\\})\times\mbox{Sym}^{2\times
2}(\mathbb{R})\to\mathbb{R}$

the differential operator such that $F_{q}(\nabla
u,\nabla^{2}u)=-\Delta_{q}u$, then $F$ is non-increasing with respect to $S$
(just look at (2.4)). It follows that if $f-\varphi$ has a local minimum at
$x_{0}$ with $\nabla\varphi(x_{0})\neq 0$, then $\nabla
f(x_{0})=\nabla\varphi(x_{0})\neq 0$ and

$F_{q}(\nabla\varphi(x_{0}),\nabla^{2}\varphi(x_{0}))+g(x_{0})\geq
F_{q}(\nabla f(x_{0}),\nabla^{2}f(x_{0}))+g(x_{0})\geq 0$

as $\nabla^{2}f(x_{0})\geq\nabla^{2}\varphi(x_{0})$.

###  2.3. Hopf-Lax semigroup

Given $f:{\mathbb{T}^{2}}\to\mathbb{R}$ lower semicontinuous, let $u=Q_{t}f$
be the Hopf-Lax semigroup associated to the Hamilton-Jacobi equation

$\partial_{t}u+\frac{|\nabla u|^{q}}{q}=0,$ (2.5)

that is

$(Q_{t}f)(x)=\min_{y\in{\mathbb{T}^{2}}}\left\\{f(y)+\frac{{\mathbf{d}}^{p}(x,y)}{pt^{p-1}}\right\\}.$
(2.6)

The following properties of the semigroup $Q_{t}f$, with $Q_{0}f=f$, are well-
known, see for instance Proposition 3.3 in [AGS13] for a detailed proof.

######  Proposition 2.4.

Let $f:{\mathbb{T}^{2}}\to\mathbb{R}$ be Lipschitz. Then the functions
$Q_{t}f$ are Lipschitz, uniformly with respect to $t\in[0,1]$, $t\mapsto
Q_{t}f$ is Lipschitz from $[0,1]$ to $C({\mathbb{T}^{2}})$ and the PDE (2.5)
is satisfied almost everywhere in $(0,1)\times{\mathbb{T}^{2}}$.

###  2.4. Heat kernel on ${\mathbb{T}^{2}}$

We recall that the heat kernel on the torus
${\mathbb{T}^{2}}=\mathbb{R}^{2}/\mathbb{Z}^{2}$ is given by

$p_{t}(x):=\sum_{\mathbf{n}\in\mathbb{Z}^{2}}\overline{p}_{t}(x+\mathbf{n}),$
(2.7)

where $\overline{p}_{t}(x)=\frac{1}{4\pi t}e^{-\frac{|x|^{2}}{4t}}$,
$x\in\mathbb{R}^{2}$, is the Euclidean heat kernel. Given a probability
measure $\mu$ in ${\mathbb{T}^{2}}$, we denote by $P_{t}\mu\ll\mathfrak{m}$
the probability measure having density

$\rho(x)=\int_{\mathbb{T}^{2}}p_{t}(x-y)\,\mathrm{d}\mu(y).$

Let us recall that $(P_{t})_{t\geq 0}$ defines a symmetric Markov
(convolution) semigroup, $P_{s+t}=P_{s}\circ P_{t}$ with (unique) invariant
measures $\mathfrak{m}$ and generator given by the (distributional) Laplacian.
Let us recall the following deterministic dispersion bound, directly coming
from the coupling

$\Sigma=\int_{\mathbb{T}^{2}}p_{t}(z)\Sigma_{z}\,\mathrm{d}\mathfrak{m}(z)\qquad\text{with}\qquad\Sigma_{z}=(Id\times\tau_{z})_{\\#}\mu$

between $\mu$ and $P_{t}\mu$ (where $\tau_{z}$ is the shift map):

$W_{p}(\mu,P_{t}\mu)\leq C_{0}\sqrt{t}\qquad\forall t>0,$ (2.8)

with
$C_{0}=C_{0}({\mathbb{T}^{2}})=\bigl{(}\int_{{\mathbb{T}^{2}}}|z|^{p}p_{1}(z)\,\mathrm{d}\mathfrak{m}(z)\bigr{)}^{1/p}$
for any probability measure $\mu$ in ${\mathbb{T}^{2}}$.

A remarkable fact, first noticed in [AG19, Theorem 5.2], is that the
dispersion bound above can be significantly improved (in average) when applied
to empirical measures $\mu^{n}$ as in (1.4).

######  Proposition 2.5.

For every $p\geq 1$ there exists positive constant
$C_{1}({\mathbb{T}^{2}},p),\,C_{2}({\mathbb{T}^{2}},p)$ such that the
following holds. If $t=\alpha/n\leq\frac{1}{2}$ with $\alpha\geq
C_{1}({\mathbb{T}^{2}},p)\ln n$, then

$\operatorname{\mathbb{E}}\left[W_{p}^{p}(\mu^{n},P_{t}\mu^{n})\right]\leq
C_{2}({\mathbb{T}^{2}},p)\left(\frac{\ln\alpha}{n}\right)^{p/2}.$

###### Proof.

The case $p=2$ is established in [AG19, Theorem 5.2], and by the Hölder
inequality, it entails the thesis for every $1\leq p<2$:

$\operatorname{\mathbb{E}}\left[W_{p}^{p}(\mu^{n},P_{t}\mu^{n})\right]\leq(C_{2})^{p/2}\frac{(\ln\alpha)^{p/2}}{n^{p/2}},\quad
t=\frac{\alpha}{n},\,\,\alpha\geq C_{1}\ln n.$ (2.9)

Therefore, it is sufficient to consider the case $p\geq 2$. To this aim, we
combine the argument from [AG19] with the application of Rosenthal’s
inequality, from [Led17], where upper bounds for the random bipartite matching
cost are proved for any $p\geq 2$. By the triangle inequality and the
elementary bound

$|x+y|^{p}\leq 2^{p-1}(|x|^{p}+|y|^{p})$ (2.10)

for some $C=C(p)<\infty$, we find

$\begin{split}\operatorname{\mathbb{E}}\left[W_{p}^{p}(\mu^{n},P_{t}\mu^{n})\right]&\leq
2^{p-1}\left(\operatorname{\mathbb{E}}\left[W_{p}^{p}(\mu^{n},P_{1/n}\mu^{n})\right]+\operatorname{\mathbb{E}}\left[W_{p}^{p}(P_{1/n}\mu^{n},P_{t}\mu^{n})\right]\right)\\\
&\leq
2^{p-1}\left(C_{0}n^{-p/2}+\operatorname{\mathbb{E}}\left[W_{p}^{p}(P_{1/n}\mu^{n},P_{t}\mu^{n})\right]\right),\end{split}$
(2.11)

having used (2.8) in the second inequality. Thus, we are reduced to bound from
above the expectation of $W_{p}^{p}(P_{1/n}\mu^{n},P_{t}\mu^{n})$. Since this
random variable is always bounded from above by
$\operatorname{diam}({\mathbb{T}^{2}})^{p}$, by choosing e.g. $d=1/2$ in
(2.15) of Proposition 2.6 below, we see that, if we pick $C_{1}=(\ln a)^{-1}K$
sufficiently large – precisely such that $5-Kd^{2}<p/2$, we can safely reduce
ourselves to argue on the event $\|\rho_{t,n}-1\|\leq 1/2$, so that
$P_{t}\mu^{n}=\rho_{t,n}\mathfrak{m}$ has a density uniformly bounded from
below by $1/2$. On such event, we use (2.2) (with $\mu=P_{1/n}\mu^{n}$ and
$\nu=P_{t}\mu^{n}$), and we find

$W_{p}^{p}(P_{1/n}\mu^{n},P_{t}\mu^{n})\leq
C\int_{{\mathbb{T}^{2}}}\left|(-\Delta)^{-1/2}(\rho_{1/n,n}-\rho_{t,n})\right|^{p}\,\mathrm{d}\mathfrak{m}.$
(2.12)

where $C=C({\mathbb{T}^{2}},p)<\infty$. By the linearity of the operator
$(-\Delta)^{-1/2}$, we collect the identity

$(-\Delta)^{-1/2}(\rho_{1/n,n}-\rho_{t,n})(x)=\frac{1}{n}\sum_{i=1}^{n}[(-\Delta)^{-1/2}(p_{1/n}-p_{t})](X_{i}-x),$

and notice that, for each $x\in{\mathbb{T}^{2}}$, the random variables
$\varphi_{i}(x):=[(-\Delta)^{-1/2}(p_{1/n}-p_{t})](X_{i}-x)$, for
$i=1,\ldots,n$ are independent and centered. After taking expectation in
(2.12), we see that the thesis amounts to bound from above the quantity

$\int_{{\mathbb{T}^{2}}}\operatorname{\mathbb{E}}\left[\left|\frac{1}{n}\sum_{i=1}^{n}\varphi_{i}(x)\right|^{p}\right]\,\mathrm{d}\mathfrak{m}(x),$

where we recognize, for every $x$, the $p$-th moment of a sum of independent
centered random variables. By Rosenthal’s inequality, [Ros70], we have for
some constant $C=C(p)<\infty$,

$\operatorname{\mathbb{E}}\left[\left|\frac{1}{n}\sum_{i=1}^{n}\varphi_{i}(x)\right|^{p}\right]\leq
C\left[\frac{1}{n^{p-1}}\operatorname{\mathbb{E}}\left[\left|\varphi(x)\right|^{p}\right]+\frac{1}{n^{p/2}}\operatorname{\mathbb{E}}\left[\left|\varphi(x)\right|^{2}\right]^{p/2}\right],$
(2.13)

where we write $\varphi:=[(-\Delta)^{-1/2}(p_{1/n}-p_{t})](X_{1}-x)$. To
conclude, we follow very closely the argument in [Led17] from eq. (34) onwards
(in the case $d=2$), so we omit some details. We collect first the uniform
bound, valid for $0<s\leq 1/2$:

$\sup_{z\in{\mathbb{T}^{2}}}\left|(-\Delta)^{-1/2}(p_{s}-1)(z)\right|\leq\frac{C}{s^{1/2}},$

which we apply in particular to $s\in\\{1/n,t\\}$, yielding

$\sup_{z\in{\mathbb{T}^{2}}}\left|\varphi(z)\right|\leq\sup_{z\in{\mathbb{T}^{2}}}\left|(-\Delta)^{-1/2}(p_{1/n}-1)(z)\right|+\sup_{z\in{\mathbb{T}^{2}}}\left|(-\Delta)^{-1/2}(p_{t}-1)(z)\right|\leq
Cn^{1/2}.$

Then, by the representation $(-\Delta)^{-1}=\int_{0}^{\infty}P_{s}ds$, we find
for any $f\in L^{2}({\mathbb{T}^{2}})$ with
$\int_{{\mathbb{T}^{2}}}f\,\mathrm{d}\mathfrak{m}=0$ that

$\begin{split}\int_{{\mathbb{T}^{2}}}[(-\Delta)^{-1/2}f]^{2}\,\mathrm{d}\mathfrak{m}&=\int_{{\mathbb{T}^{2}}}f(-\Delta)^{-1}f\,\mathrm{d}\mathfrak{m}\\\
&=\int_{0}^{\infty}\int_{\mathbb{T}^{2}}fP_{s}f\,\mathrm{d}\mathfrak{m}\,\mathrm{d}s=\int_{0}^{\infty}\int_{\mathbb{T}^{2}}(P_{s/2}f)^{2}\,\mathrm{d}\mathfrak{m}\,\mathrm{d}s.\end{split}$

We use this identity in our case, i.e., with $f=p_{1/n}-p_{t}$, yielding

$\begin{split}\operatorname{\mathbb{E}}\left[\left|\varphi(x)\right|^{2}\right]&=\int_{{\mathbb{T}^{2}}}[(-\Delta)^{-1/2}(p_{1/n}-p_{t})]^{2}(y-x)\,\mathrm{d}\mathfrak{m}(y)\\\
&=\int_{0}^{\infty}\int_{{\mathbb{T}^{2}}}(p_{s/2+1/n}(y-x)-p_{s/2+t}(y-x))^{2}\,\mathrm{d}\mathfrak{m}(y)\,\mathrm{d}s\\\
&=\int_{0}^{\infty}[p_{s+2/n}(0)+p_{s+2t}(0)-2p_{s+t+1/n}(0)]\,\mathrm{d}s\\\
&=O\left(-\log(2/n)-\log(2t)+2\log(t+1/n)+1\right)=O(\ln\alpha),\end{split}$

where in developing the square we invoked the semigroup property (so that, for
any $t_{1},t_{2}>0$,
$\int_{\mathbb{T}^{2}}p_{t_{1}}(y-x)p_{t_{2}}(y-x)\,\mathrm{d}\mathfrak{m}(y)=P_{t_{1}+t_{2}}\delta_{x}(x)=p_{t_{1}+t_{2}}(0)$),
and the final asymptotics can be computed directly from (2.7).

Combining these bounds, we find

$\operatorname{\mathbb{E}}\left[\left|\varphi(x)\right|^{p}\right]\leq\sup_{z\in{\mathbb{T}^{2}}}\left|\varphi(z)\right|^{p-2}\operatorname{\mathbb{E}}\left[\left|\varphi(x)\right|^{2}\right]\\\
\leq Cn^{(p-2)/2}\ln\alpha,$

and therefore we bound from above the right hand side in (2.13) with

$\left[\frac{1}{n^{p-1}}\operatorname{\mathbb{E}}\left[\left|\varphi(x)\right|^{p}\right]+\frac{1}{n^{p/2}}\operatorname{\mathbb{E}}\left[\left|\varphi(x)\right|^{2}\right]^{p/2}\right]\leq
C\frac{\ln\alpha}{n^{p/2}}+C\left(\frac{\ln\alpha}{n}\right)^{p/2}$ (2.14)

and the thesis follows. ∎

In the proof above we used a regularizing property of the heat semigroup, when
acting on empirical measures, as established in [AG19] (see Theorem 3.3 and
Remark 3.17 therein), that we report here.

######  Proposition 2.6.

If $\mu^{n}$ are as in (1.4) and $P_{t}\mu^{n}=\rho_{t,n}\mathfrak{m}$, then

$\operatorname{\mathbb{P}}\left(\\{\|\rho_{t,n}-1\|_{\infty}>d\\}\right)\leq\frac{C_{3}({\mathbb{T}^{2}})}{d^{2}t^{3}}a^{-ntd^{2}}$

for some $C_{3}({\mathbb{T}^{2}})>0$ and $a=a({\mathbb{T}^{2}})>1$. In
particular, if $d\geq n^{-1}$ and $t=(\ln a)^{-1}Kn^{-1}\ln n$ with $K\geq 1$,
then

$\operatorname{\mathbb{P}}\left(\\{\|\rho_{t,n}-1\|_{\infty}>d\\}\right)\leq
C_{3}({\mathbb{T}^{2}})(\ln a)^{3}n^{5-Kd^{2}}.$ (2.15)

Our strategy for proving Theorem 1.1 will be to adjust the parameters
$K=K_{n}\to\infty$ and $d=d_{n}\to 0$ in such a way that $Kd$ is sufficiently
large, so that the probability of the deviation from the constant density $1$
will have the power like decay we need with respect to $n$.

We will also need $L^{p}$ estimates on $\rho_{t,n}$, provided by the following
proposition.

######  Proposition 2.7.

Let $t_{n}$ as in Theorem 1.1, and $K=K_{n}$ related to $t_{n}$ as in
Proposition 2.6. Fixed $k>0$, take $c_{n}\rightarrow 0^{+}$ such that

$\liminf_{n}K_{n}c_{n}^{2}>k+5.$ (2.16)

Then

$\sup\left\\{n^{k}\operatorname{\mathbb{E}}\left[\mathbf{1}_{\\{\|\rho_{t_{n},n}-1\|_{\infty}>c_{n}\\}}\int_{{\mathbb{T}^{2}}}|\rho_{t_{n},n}-1|^{p}\,\mathrm{d}\mathfrak{m}\right]:\,\,n\geq
2\right\\}<\infty.$

###### Proof.

In this proof $C$ denotes a positive constant, depending only on
${\mathbb{T}^{2}}$. Arguing as in the proof of Theorem 3.3 in [AG19], the
bounds

$\operatorname{\mathbb{E}}\left[Y^{2}\right]\leq\frac{C}{t},\qquad|Y|\leq\frac{C}{t}\qquad
t\in(0,1)$

for the random variables $Y=Y_{i}=p_{t}(X_{i},y)-1$, together with Bernstein’s
inequality yield

$\operatorname{\mathbb{P}}\left(\\{|\rho_{t,n}(y)-1|>\xi\\}\right)\leq
C\exp(-nct\xi)\qquad\forall t\in(0,1),\,\,\xi>1$

for all $y\in{\mathbb{T}^{2}}$. For our choice of $t=t_{n}$, Fubini’s theorem
and Cavalieri’s formula yield

$n^{k}\operatorname{\mathbb{E}}\left[\int_{\\{|\rho_{t_{n},n}-1|>1\\}}|\rho_{t_{n},n}-1|^{p}\,\mathrm{d}\mathfrak{m}\right]\leq
C\int_{1}^{\infty}n^{k-c(\ln a)^{-1}K_{n}\xi}\cdot\xi^{p-1}\,\mathrm{d}\xi.$

Thus, for $n\gg 1$

$\displaystyle
n^{k}\operatorname{\mathbb{E}}\left[\int_{\\{|\rho_{t_{n},n}-1|>1\\}}|\rho_{t_{n},n}-1|^{p}\,\mathrm{d}\mathfrak{m}\right]\leq
C\int_{1}^{\infty}n^{\xi(k-c(\ln a)^{-1}K_{n})}\xi^{p-1}d\xi$
$\displaystyle\leq C\int_{1}^{\infty}2^{-\xi}\xi^{p-1}\,\mathrm{d}\xi<\infty.$

On the other hand, exploiting Proposition 2.6 along with (2.16) we get

$\displaystyle
n^{k}\operatorname{\mathbb{E}}\left[\mathbf{1}_{\\{\|\rho_{t_{n},n}-1\|_{\infty}>c_{n}\\}}\int_{\\{|\rho_{t_{n},n}-1|\leq
1\\}}|\rho_{t_{n},n}-1|^{p}\,\mathrm{d}\mathfrak{m}\right]\leq
n^{k}\operatorname{\mathbb{P}}\left(\\{\|\rho_{t_{n},n}-1\|_{\infty}>c_{n}\\}\right)$
$\displaystyle\leq C_{3}({\mathbb{T}^{2}})(\ln
a)^{3}n^{k+5-K_{n}c_{n}^{2}}\rightarrow 0.\qed$

##  3\. Propagation of $q$-laplacian estimates and differentiation of
$\int|\nabla Q_{t}\phi|^{q}\mbox{ }\,\mathrm{d}\mathfrak{m}$

Recalling the definition of $c\geq 0$ in Theorem 1.2, $\phi\in
H^{1,q}({\mathbb{T}^{2}})$ satisfies in a distributional sense the inequality

$-{\rm div}\bigl{(}|\nabla\phi|^{q-2}\nabla\phi)+c\geq 0.$ (3.1)

Namely, for every nonnegative $\eta\in C^{\infty}({\mathbb{T}^{2}})$ we have

$\int_{\mathbb{T}^{2}}|\nabla\phi|^{q-2}\langle\nabla\phi,\nabla\eta\rangle\mbox{
}\,\mathrm{d}\mathfrak{m}+c\int_{\mathbb{T}^{2}}\eta\mbox{
}\,\mathrm{d}\mathfrak{m}\geq 0.$ (3.2)

In order to control the time derivative of $\int_{\mathbb{T}^{2}}|\nabla
Q_{t}\phi|^{q}\,\mathrm{d}\mathfrak{m}$, we would like to show that (3.2)
propagates with the Hopf-Lax semigroup, that is, it is satisfied also by
$Q_{t}\phi$ for any $t\in(0,1)$. The proof of this stability property becomes
much easier if we understand (3.1) in the viscosity sense; this is possible
thanks to the following result (see [JJ12], [JLM01] for the homogeneous case
$g=0$ and Remark 3.3 below):

######  Theorem 3.1.

Let $f\in H^{1,q}({\mathbb{T}^{2}})$ and $g:{\mathbb{T}^{2}}\to\mathbb{R}$ be
continuous. Then $-\Delta_{q}f+g\geq 0$ in the viscosity sense, according to
Definition 2.2, if and only if $-\Delta_{q}f+g\geq 0$ in the sense of
distributions.

We are going to use Theorem 3.1 both ways: first we pass from the
distributional sense for $\phi$, granted by (1.1), to the viscosity sense,
then we pass from the viscosity sense to the distributional sense for
$Q_{s}\phi$ in the proof of Lemma 3.4.

Then, let us show propagation of the estimate $-\Delta_{q}\phi+c\geq 0$ to
$Q_{t}\phi$ in the viscosity sense. Actually it will be usefult to prove this
property for the Hopf-Lax semigroup associated to any power $r>1$. We provide
a direct proof, even though the statement could directly follow by the general
fact that viscosity supersolutions to $-\Delta_{q}+c\geq 0$ are stable under
translations in the dependent and independent variables, and infimum.

######  Proposition 3.2.

Let $f:{\mathbb{T}^{2}}\to\mathbb{R}$ be lower semicontinuous and satisfying
$-\Delta_{q}f+c\geq 0$ in the viscosity sense and $r\in(1,\infty)$. Then for
all $t>0$ the function

$f_{t}(x):=\min_{y\in{\mathbb{T}^{2}}}\left\\{f(y)+\frac{{\mathbf{d}}^{r}(x,y)}{rt^{r-1}}\right\\}.$

still satisfies $-\Delta_{q}f_{t}+c\geq 0$ in the viscosity sense.

###### Proof.

Given $t>0$ and $x_{0}\in{\mathbb{T}^{2}}$, let $y_{0}\in{\mathbb{T}^{2}}$ be
a point where the minimum in the definition of $f_{t}$ is attained, so that

$f_{t}(x_{0})=f(y_{0})+\frac{{\mathbf{d}}^{r}(x_{0},y_{0})}{rt^{r-1}}.$

Consider $\varphi\in C^{2}({\mathbb{T}^{2}})$ such that $f_{t}-\varphi$ has a
local minimum in $x_{0}$ and, with no loss of generality, assume that the
minimum is global and $f_{t}(x_{0})=\varphi(x_{0})$.
If we set $\psi(x):=\varphi(x-y_{0}+x_{0})$, we claim that $\phi-\psi$ has a
minimum in $y_{0}$, equal to $-{\mathbf{d}}^{r}(x_{0},y_{0})/(rt^{r-1})$. From
this we would obtain

$F_{q}(\nabla\psi(y_{0}),\nabla^{2}\psi(y_{0}))\leq c$

thus

$F_{q}(\nabla\varphi(x_{0}),\nabla^{2}\varphi(x_{0}))\leq c.$

To prove the claim, we notice that

$\phi(y_{0})-\psi(y_{0})=\phi(y_{0})-\varphi(x_{0})=\phi(y_{0})-f_{t}(x_{0})=-\frac{1}{rt^{r-1}}{\mathbf{d}}^{r}(x_{0},y_{0}),$

while in the other hand $f_{t}(x)\geq\varphi(x)$ implies

$\phi(y)+\frac{1}{rt^{r-1}}{\mathbf{d}}^{r}(x,y)\geq\varphi(x)\quad\forall
x,\,y.$

Choosing $y=x-x_{0}+y_{0}$ (understanding the sum modulo $\mathbb{Z}^{2}$) we
obtain

$\phi(y)-\psi(y)\geq-\frac{1}{rt^{r-1}}{\mathbf{d}}^{r}(x_{0},y_{0})\quad\forall
y,$

as desired. ∎

######  Remark 3.3.

We can use Proposition 3.2 to provide a sketchy proof of the implication from
viscous to distributional granted, also in the converse direction, by Theorem
3.1. Indeed, we can use the Hopf-Lax semigroup with power $r=2$ to obtain that
$f_{s}=Q_{s}f$ still satisfy $-\Delta_{q}f_{s}+c\geq 0$ in the viscosity sense
and $C^{1,1}$ regularity of $f_{s}$. Since $f_{s}\to f$ in
$H^{1,q}({\mathbb{T}^{2}})$ as $s\to 0^{+}$, it is then sufficient to show
that $-\Delta_{q}f_{s}+c\geq 0$ in the sense of distributions. Here we can use
the $C^{1,1}$ regularity of $f_{s}$ to build appropriate test functions
$\phi$, of the form

$\phi(x)=f_{s}(x_{0})+\langle\nabla
f_{s}(x_{0}),x-x_{0}\rangle+\frac{1}{2}\langle\nabla^{2}f_{s}(x_{0})(x-x_{0}),(x-x_{0})\rangle-\epsilon|x-x_{0}|^{2}$

at any point $x_{0}\in{\mathbb{T}^{2}}$ where $\nabla f_{s}(x_{0})\neq 0$ and
$\nabla^{2}f_{s}(x_{0})$ exists. This leads to the validity of
$-\Delta_{q}f_{s}+c\geq 0$ almost everywhere in the open set
$\Omega_{s}=\\{|\nabla f_{s}|\neq 0\\}$. Then, one obtains the validity of the
inequality in the sense of distributions first in $\Omega_{s}$ and then on the
whole of ${\mathbb{T}^{2}}$, using the fact that the flux of the continuous
vector field $|\nabla f_{s}|^{q-2}\nabla f_{s}$ is null on the boundary
(because $q>1$). If $\Omega_{s}$ is not smooth one can perform a further
approximation, since

$\frac{1}{\epsilon}\int_{0}^{\epsilon}\int_{\\{|\nabla f_{s}|=\tau\\}}|\nabla
f_{s}|^{q-1}\,\mathrm{d}\mathscr{H}^{1}\,\mathrm{d}\tau=\int_{\\{0<|\nabla
f_{s}|<\epsilon\\}}|\nabla f_{s}|^{q}\,\mathrm{d}\mathfrak{m}$

tends to $0$ as $\epsilon\to 0$.

Now, we apply Proposition 3.2 with $f=\phi$ and $r=p$ in order to estimate the
variation in time of $\int_{\mathbb{T}^{2}}|\nabla
Q_{t}\phi|^{q}\,\mathrm{d}\mathfrak{m}$.

######  Lemma 3.4.

Let $\Lambda(t):=\int_{\mathbb{T}^{2}}|\nabla
Q_{t}\phi|^{q}\,\mathrm{d}\mathfrak{m}$ with $\phi$ as in (1.2) and
$c=\|\rho_{1}-\rho_{0}\|_{\infty}$. Then $\Lambda$ is Lipschitz in $[0,1]$ and
$\frac{\,\mathrm{d}}{\,\mathrm{d}t}\Lambda(t)\leq c\Lambda(t)$ for almost
every $t\in(0,1)$. In particular

$\int_{\mathbb{T}^{2}}|\nabla Q_{t}\phi|^{q}\,\mathrm{d}\mathfrak{m}\leq
e^{ct}\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}\qquad\forall
t\in[0,1].$ (3.3)

###### Proof.

Thanks to Proposition 3.2, $f_{t}=Q_{t}\phi$ satisfy $-\Delta_{q}f_{t}+c\geq
0$ in the viscosity sense. Therefore Theorem 3.1 grants this property also in
the sense of distributions, namely (notice that the improvement from
$C^{\infty}({\mathbb{T}^{2}})$ to $H^{1,q}({\mathbb{T}^{2}})$ follows by
density and $L^{p}$ integrability of $|\nabla f_{t}|^{q-2}\nabla f_{t}$)

$\int_{\mathbb{T}^{2}}|\nabla f_{t}|^{q-2}\langle\nabla
f_{t},\nabla\eta\rangle\mbox{
}\,\mathrm{d}\mathfrak{m}+c\int_{\mathbb{T}^{2}}\eta\mbox{
}\,\mathrm{d}\mathfrak{m}\geq 0\qquad\forall\eta\in
H^{1,q}({\mathbb{T}^{2}}),\eta\geq 0.$ (3.4)

First, we note that, by 3.4, the distribution $T:=-\operatorname{div}(|\nabla
f_{t}|^{q-2}\nabla f_{t})+c$ is non-negative. Thus, if $\eta\in
C^{\infty}({\mathbb{T}^{2}})$

$\langle T,\eta\rangle\leq\langle
T,\|\eta\|_{\infty}1\rangle={\|\eta\|}_{\infty}c$

and then $T$ is represented by a nonnegative finite measure with mass less or
equal than $c$ (here we used that $\langle\operatorname{div}(|\nabla
f_{t}|^{q-2}\nabla f_{t}),1\rangle=0$ and therefore $\langle T,1\rangle=c$).
It follows that $\mu_{t}:=\operatorname{div}(|\nabla f_{t}|^{q-2}\nabla
f_{t})$ is a signed measure with $\|\mu_{t}\|\leq 2c$.
By the convexity of $y\mapsto|y|^{q}$ we then infer

$\Lambda(t)-\Lambda(s)\geq q\int_{\mathbb{T}^{2}}|\nabla
f_{s}|^{q-2}\langle\nabla
f_{s},\nabla(f_{t}-f_{s})\rangle\,\mathrm{d}\mathfrak{m}=q\int_{\mathbb{T}^{2}}(f_{s}-f_{t})\,\mathrm{d}\mu_{s}\geq-2cq\|f_{t}-f_{s}\|_{\infty}$
(3.5)

for every $s,\,t\in[0,1]$. From the Lipschitz regularity of the initial datum
$\phi$ (which follows by [Tei14, Theorem 2.1]) and Proposition 2.4 we deduce
that the map $t\mapsto f_{t}$ is Lipschitz with respect to the sup norm, let
us say with constant $L$. Hence, exchanging the roles of $t$ and $s$ we
conclude that

$|\Lambda(t)-\Lambda(s)|\leq 2cqL|t-s|,$

as we desired.

Now, we can refine (3.5) as follows. Let $t\in(0,1)$ be a differentiability
point for $\Lambda$ such that
$-q\frac{\,\mathrm{d}}{\,\mathrm{d}t}f_{t}=|\nabla f_{t}|^{q}$ a.e. in
${\mathbb{T}^{2}}$. Thanks to Rademacher’s theorem and Proposition 2.4, both
properties are satisfied for a.e. $t\in(0,1)$. For $s\geq t$, using the
inequality $f_{t}\geq f_{s}$ granted directly from the definition (2.6), as
well as the inequality $-\operatorname{div}(|\nabla f_{s}|^{q-2}\nabla
f_{s})+c\geq 0$ in the sense of distributions, we get

$\displaystyle\Lambda(s)-\Lambda(t)$ $\displaystyle\leq$
$\displaystyle-q\int_{\mathbb{T}^{2}}|\nabla f_{s}|^{q-2}\langle\nabla
f_{s},\nabla(f_{t}-f_{s})\rangle\,\mathrm{d}\mathfrak{m}$ $\displaystyle=$
$\displaystyle q\int_{\mathbb{T}^{2}}\operatorname{div}(|\nabla
f_{s}|^{q-2}\nabla f_{s})(f_{t}-f_{s})\,\mathrm{d}\mathfrak{m}$
$\displaystyle\leq$ $\displaystyle
cq\int_{\mathbb{T}^{2}}(f_{t}-f_{s})\,\mathrm{d}\mathfrak{m},$

so that

$\frac{\,\mathrm{d}}{\,\mathrm{d}t}\Lambda(t)=\lim_{s\rightarrow
t^{+}}\frac{\Lambda(s)-\Lambda(t)}{s-t}\leq\lim_{s\rightarrow
t^{+}}cq\int_{\mathbb{T}^{2}}\frac{f_{t}-f_{s}}{s-t}\,\mathrm{d}\mathfrak{m}=-cq\int_{\mathbb{T}^{2}}\frac{\,\mathrm{d}}{\,\mathrm{d}t}f_{t}\,\mathrm{d}\mathfrak{m}=c\int_{\mathbb{T}^{2}}|\nabla
f_{t}|^{q}\,\mathrm{d}\mathfrak{m},$

which proves that $\Lambda^{\prime}(t)\leq c\Lambda(t)$. Finally, the validity
of (3.3) follows by Gronwall’s Lemma. ∎

##  4\. Proof of Theorem 1.2

In this section $\phi$, $c$ are as in Theorem 1.2.

###  4.1. Upper bound

The upper bound in Theorem 1.2 can be obtained immediately by repeating the
argument in Proposition 2.3 of [AST19], involving duality and the Hopf-Lax
formula. We still give the proof here for the sake of completeness.

Since ${\mathbb{T}^{2}}$ is compact, the duality formula for $W_{p}^{p}$ can
be written in the form

$\frac{1}{p}W_{p}^{p}(\rho_{0}\mathfrak{m},\rho_{1}\mathfrak{m})=\sup\left\\{-\int_{\mathbb{T}^{2}}f\rho_{0}\,\mathrm{d}\mathfrak{m}+\int_{\mathbb{T}^{2}}(Q_{1}f)\rho_{1}\,\mathrm{d}\mathfrak{m}:\text{$f:{\mathbb{T}^{2}}\to\mathbb{R}$
Lipschitz}\right\\}.$ (4.1)

######  Proposition 4.1 (Upper bound).

There exists $\overline{\delta}(c,p)$ such that
$\overline{\delta}(c,p)\rightarrow 0$ as $c\to 0$ and

$W_{p}^{p}(\rho_{0}\mathfrak{m},\rho_{1}\mathfrak{m})\leq(1+\overline{\delta}(c,p))\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}.$

###### Proof.

Let us bound uniformly the argument of the supremum in (4.1), for
$f:{\mathbb{T}^{2}}\to\mathbb{R}$ Lipschitz, exploiting the PDE (1.2)
satisfied by $\phi$, the fact that $Q_{t}f$ solves (2.5) almost everywhere in
$(0,1)\times{\mathbb{T}^{2}}$ and dominated convergence to put
$\frac{\,\mathrm{d}}{\,\mathrm{d}s}$ under the integral sign. If we set
$\rho_{t}:=t\rho_{1}+(1-t)\rho_{0}$ per $t\in(0,1)$, then:

$\displaystyle\int_{\mathbb{T}^{2}}(\rho_{1}Q_{1}f-\rho_{0}f)\,\mathrm{d}\mathfrak{m}=\int_{0}^{1}\frac{\,\mathrm{d}}{\,\mathrm{d}s}\int_{\mathbb{T}^{2}}\rho_{s}Q_{s}f\,\mathrm{d}\mathfrak{m}\,\mathrm{d}s$
$\displaystyle=\int_{0}^{1}\int_{\mathbb{T}^{2}}\left(\rho_{s}\frac{\,\mathrm{d}}{\,\mathrm{d}s}Q_{s}f+(\rho_{1}-\rho_{0})Q_{s}f\right)\,\mathrm{d}\mathfrak{m}\,\mathrm{d}s$
$\displaystyle=\int_{0}^{1}\int_{\mathbb{T}^{2}}\left(-\frac{1}{q}|\nabla
Q_{s}f|^{q}\rho_{s}+|\nabla\phi|^{q-2}\langle\nabla\phi,\nabla
Q_{s}f\rangle\right)\,\mathrm{d}\mathfrak{m}\,\mathrm{d}s$
$\displaystyle\leq\int_{0}^{1}\int_{\mathbb{T}^{2}}\left(-\frac{1}{q}|\nabla\phi|^{q}\rho_{s}^{-\frac{q}{q-1}}\rho_{s}+|\nabla\phi|^{q}\rho_{s}^{-\frac{1}{q-1}}\right)\,\mathrm{d}\mathfrak{m}\,\mathrm{d}s$
$\displaystyle=\frac{1}{p}\int_{\mathbb{T}^{2}}\left(\int_{0}^{1}\rho_{s}^{-\frac{1}{q-1}}\,\mathrm{d}s\right)|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m},$
(4.2)

where for the inequality we used that $v=\rho_{s}^{-\frac{1}{q-1}}\nabla\phi$
minimizes
$v\mapsto\frac{1}{q}|v|^{q}\rho_{s}-|\nabla\phi|^{q-2}\langle\nabla\phi,v\rangle$.
In conclusion

$W_{p}^{p}(\rho_{0}\mathfrak{m},\rho_{1}\mathfrak{m})\leq\int_{\mathbb{T}^{2}}M_{q}(\rho_{0},\rho_{1})|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m},$

where
$M_{q}(\rho_{0},\rho_{1})(x)=\int_{0}^{1}\rho_{s}(x)^{-\frac{1}{q-1}}\,\mathrm{d}s\lesssim
1$ as $c\to 0$. More precisely, since $\|\rho_{i}-1\|_{\infty}\leq c/2$, for
$c<2$ one has

$M_{q}(\rho_{0},\rho_{1})(x)\leq 1+\overline{\delta}(c,p)$

with $\overline{\delta}(c,p)=(1-c/2)^{-\frac{1}{q-1}}-1$.∎

###  4.2. Lower bound

######  Proposition 4.2 (Lower bound).

There exists $\underline{\delta}(c,p)$ such that
$\underline{\delta}(c,p)\rightarrow 0$ as $c\to 0$ and

$W_{p}^{p}(\rho_{0}\mathfrak{m},\rho_{1}\mathfrak{m})\geq(1-\underline{\delta}(c,p))\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}.$

###### Proof.

From the duality formula, with an integration by parts and Fubini’s theorem,
we get

$\displaystyle\frac{1}{p}W_{p}^{p}(\rho_{1}\mathfrak{m},\rho_{0}\mathfrak{m})$
$\displaystyle\geq$
$\displaystyle-\int_{\mathbb{T}^{2}}\phi\rho_{0}\,\mathrm{d}\mathfrak{m}+\int_{\mathbb{T}^{2}}(Q_{1}\phi)\rho_{1}\,\mathrm{d}\mathfrak{m}=\int_{\mathbb{T}^{2}}\phi(\rho_{1}-\rho_{0})\,\mathrm{d}\mathfrak{m}+\int_{\mathbb{T}^{2}}(Q_{1}\phi-\phi)\rho_{1}\,\mathrm{d}\mathfrak{m}$
$\displaystyle=$
$\displaystyle\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}-\frac{1}{q}\int_{0}^{1}\int_{\mathbb{T}^{2}}|\nabla
Q_{s}\phi|^{q}\rho_{1}\,\mathrm{d}\mathfrak{m}\,\mathrm{d}s.$

Now we can use first the inequality $\|\rho_{1}-1\|_{\infty}\leq c/2$ to
replace $\rho_{1}$ with $1$ and then Lemma 3.4 with
$c\geq\|\rho_{1}-\rho_{0}\|_{\infty}$ to estimate

$\frac{1}{p}W_{p}^{p}(\rho_{1}\mathfrak{m},\rho_{0}\mathfrak{m})\geq\frac{1}{p}\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}-\frac{ce^{c}/2+e^{c}-1}{q}\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m},$

so that $\underline{\delta}(c,p)=(p-1)(ce^{c}/2+e^{c}-1)$.∎

##  5\. Proof of Theorem 1.1

In this section we adopt the notation in the statement of Theorem 1.1.

###  5.1. Upper bound

Since $\ln(nt_{n})\ll\ln n$, using Proposition 2.5 and the triangle inequality
for $W_{p}$, arguing as in [AST19], the proof of the upper bound reduces to
the following estimate:

$\limsup_{n\to\infty}\biggl{(}\frac{n}{\ln
n}\biggr{)}^{p/2}\biggl{(}\operatorname{\mathbb{E}}\left[W_{p}^{p}(P_{t_{n}}\mu^{n},P_{t_{n}}\nu^{n})\right]-\operatorname{\mathbb{E}}\left[\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}\right]\biggr{)}\leq
0$ (5.1)

where $\phi$ is the solution to (1.2) with right hand side

$\rho_{0,n}\mathfrak{m}=P_{t_{n}}\mu^{n},\qquad\rho_{1,n}\mathfrak{m}=P_{t_{n}}\nu^{n}.$

Now, since $t_{n}\gg n^{-1}\ln n$ we can use Proposition 2.6 to write $t_{n}$
as $(\ln a)^{-1}K_{n}n^{-1}\ln n$ with $K_{n}\geq 1$ and $c_{n}\to 0$ in such
a way that $K_{n}c_{n}^{2}>2p+10$, so that

$\operatorname{\mathbb{P}}\left(\\{\|\rho_{i,n}-1\|_{\infty}>\frac{c_{n}}{2}\\}\right)\leq
C_{3}({\mathbb{T}^{2}})(\ln a)^{3}n^{5-K_{n}c_{n}^{2}/4}=O(n^{-p/2})\qquad
i=0,1.$

Since $W_{p}(\mu,\nu)\leq{\rm diam}({\mathbb{T}^{2}})$ for any pair of
probability measures $\mu$, $\nu$, it follows that the contribution to (5.1)
of the event $\\{\max_{i}\|\rho_{i,n}-1\|_{\infty}>\frac{c_{n}}{2}\\}$ is null
and in the complementary event we can use Theorem 1.2 to conclude.

###  5.2. Lower bound

Recall that the semigroup $P_{t}$ is contractive in ${\mathbb{T}^{2}}$ with
respect to any $W_{p}$ distance; this can be easily proved taking any coupling
$\Sigma$ between $\mu$ and $\nu$ and considering the average
$\bar{\Sigma}=\int\Sigma_{z}p_{t}(z)\,\mathrm{d}\mathfrak{m}(z)$ of the
shifted couplings

$\Sigma_{z}:=(\tau_{z}\times\tau_{z})_{\\#}\Sigma\qquad\text{with}\qquad\tau_{z}(x)=x+z,$

which provides a coupling between $P_{t}\mu$ and $P_{t}\nu$ with the same
cost. Therefore, the lower bound

$\liminf_{n\to\infty}\biggl{(}\frac{n}{\ln
n}\biggr{)}^{p/2}\biggl{(}\operatorname{\mathbb{E}}\left[W_{p}^{p}(\mu^{n},\nu^{n})\right]-\operatorname{\mathbb{E}}\left[\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}\right]\biggr{)}\geq
0$ (5.2)

can be deduced from

$\liminf_{n\to\infty}\biggl{(}\frac{n}{\ln
n}\biggr{)}^{p/2}\biggl{(}\operatorname{\mathbb{E}}\left[W_{p}^{p}(\rho_{0,n}\mathfrak{m},\rho_{1,n})\mathfrak{m}\right]-\operatorname{\mathbb{E}}\left[\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}\right]\biggr{)}\geq
0.$ (5.3)

Now, recall that the solution $\phi$ to (1.1) is the unique minimizer of the
functional

$\Lambda_{q}(f):=\int_{\mathbb{T}^{2}}\frac{1}{q}|\nabla
f|^{q}-f(\rho_{1}-\rho_{0})\,\mathrm{d}\mathfrak{m}=\int_{\mathbb{T}^{2}}\frac{1}{q}|\nabla
f|^{q}-(f-\bar{f})(\rho_{1}-\rho_{0})\,\mathrm{d}\mathfrak{m}$

whose minimum value is nonpositive. Hence, from the Sobolev embedding we
obtain

$\frac{1}{q}\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}\leq\|\rho_{1}-\rho_{0}\|_{p}\|\phi\|_{q}\leq
c_{S}\|\rho_{1}-\rho_{0}\|_{p}\biggl{(}\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}\biggr{)}^{1/q}$

and then the deterministic upper bound

$\int_{\mathbb{T}^{2}}|\nabla\phi|^{q}\,\mathrm{d}\mathfrak{m}\leq(\|\rho_{1}-\rho_{0}\|_{p}c_{S}q)^{p}.$
(5.4)

As in the proof of the upper bound, since $nt_{n}\gg\ln n$, we can use this
time Proposition 2.7 that provides an estimate in expectation on
$\|\rho_{i,n}-1\|_{p}^{p}$ to show that the contribution to (5.3) of the event
$\\{\max_{i}\|\rho_{i,n}-1\|_{\infty}>\frac{c_{n}}{2}\\}$ is null (if we also
require $K_{n}c_{n}^{2}>2p+20$ in order to satisfy (2.16) with
$\frac{c_{n}}{2}$ and $k=\frac{p}{2}$) and in the complementary event we can
use Theorem 1.2 to conclude.

## References

  * [ABS21] L. Ambrosio, E. Brué and D. Semola  “Lectures on optimal transport”, Unitext- La Matematica per il 3+2, 130  Cham: Springer, 2021
  * [AG19] Luigi Ambrosio and Federico Glaudo  “Finer estimates on the 2-dimensional matching problem”  In _J. Éc. polytech. Math._ 6, 2019, pp. 737–765
  * [AGS13] L. Ambrosio, N. Gigli and G. Savaré  “Density of Lipschitz functions and equivalence of weak gradients in metric measure spaces”  In _Rev. Mat. Iberoam._ 29.3, 2013, pp. 969–996
  * [AGT19] L. Ambrosio, F. Glaudo and D. Trevisan  “On the optimal map in the 2-dimensional random matching problem”  In _Discrete Contin. Dyn. Syst._ 39.12, 2019, pp. 7291–7308
  * [AGT22] Luigi Ambrosio, Michael Goldman and Dario Trevisan  “On the quadratic random matching problem in two-dimensional domains”  In _Electron. J. Probab._ 27 Institute of Mathematical StatisticsBernoulli Society, 2022, pp. 1–35
  * [AKT84] M. Ajtai, J. Komlós and G. Tusnády  “On optimal matchings”  In _Combinatorica_ 4.4, 1984, pp. 259–264
  * [AST19] L. Ambrosio, F. Stra and D. Trevisan  “A PDE approach to a 2-dimensional matching problem”  In _Probab. Theory Related Fields_ 173.1-2, 2019, pp. 433–477
  * [BC20] Dario Benedetto and Emanuele Caglioti  “Euclidean random matching in 2d for non-constant densities”  In _Journal of Statistical Physics_ 181.3 Springer, 2020, pp. 854–869
  * [BCCDSS21] Dario Benedetto et al.  “Random Assignment Problems on 2d Manifolds”  In _Journal of Statistical Physics_ 183.2 Springer, 2021, pp. 34
  * [BL21] Sergey G Bobkov and Michel Ledoux  “A simple Fourier analytic proof of the AKT optimal matching theorem”  In _The Annals of Applied Probability_ 31.6 Institute of Mathematical Statistics, 2021, pp. 2567–2584
  * [CIL92] M. Crandall, H. Ishii and P. Lions  “User’s guide to viscosity solutions of second order partial differential equations”  In _Bull. Amer. Math. Soc. (N.S.)_ 27.1, 1992, pp. 1–67
  * [CLPS14] S. Caracciolo, C. Lucibello, G. Parisi and G. Sicuro  “Scaling hypothesis for the Euclidean bipartite matching problem”  In _Phys. Rev. E_ 90.1, 2014, pp. 012118
  * [CM24] Nicolas Clozeau and Francesco Mattesini  “Annealed quantitative estimates for the quadratic 2d-discrete random matching problem”  In _Probability Theory and Related Fields_ Springer, 2024, pp. 1–57
  * [GH22] Michael Goldman and Martin Huesmann  “A fluctuation result for the displacement in the optimal matching problem”  In _Ann. Probab._ 50.4 Institute of Mathematical Statistics, 2022, pp. 1446–1477
  * [GHO21] Michael Goldman, Martin Huesmann and Felix Otto  “Quantitative Linearization Results for the Monge-Ampère Equation”  In _Communications on Pure and Applied Mathematics_ 74.12 Wiley Online Library, 2021, pp. 2483–2560
  * [GHO23] Michael Goldman, Martin Huesmann and Felix Otto  “Almost sharp rates of convergence for the average cost and displacement in the optimal matching problem”  In _arXiv preprint arXiv:2312.07995_ , 2023
  * [GT21] Michael Goldman and Dario Trevisan  “Convergence of asymptotic costs for random Euclidean matching problems”  In _Probability and Mathematical Physics_ 2.2 Mathematical Sciences Publishers, 2021, pp. 341–362
  * [HMO23] Martin Huesmann, Francesco Mattesini and Felix Otto  “There is no stationary $p$-cyclically monotone Poisson matching in 2D”  In _arXiv:2311.17687_ , 2023
  * [HMO23a] Martin Huesmann, Francesco Mattesini and Felix Otto  “There is no stationary cyclically monotone Poisson matching in 2d”  In _Probability Theory and Related Fields_ 187.3 Springer, 2023, pp. 629–656
  * [JJ12] V. Julin and P. Juutinen  “A new proof for the equivalence of weak and viscosity solutions for the $p$-Laplace equation”  In _Comm. Partial Differential Equations_ 37.5, 2012, pp. 934–946
  * [JLM01] P. Juutinen, P. Lindqvist and J. Manfredi  “On the equivalence of viscosity solutions and weak solutions for a quasi-linear equation”  In _SIAM J. Math. Anal._ 33.3, 2001, pp. 699–717
  * [KO23] Lukas Koch and Felix Otto  “Lecture notes on the harmonic approximation to quadratic optimal transport”  In _arXiv:2303.14462_ , 2023
  * [Koc24] Lukas Koch  “Geometric linearisation for optimal transport with strongly p-convex cost”  In _Calculus of Variations and Partial Differential Equations_ 63.4 Springer, 2024, pp. 87
  * [Led17] M. Ledoux  “On optimal matching of Gaussian samples”  In _Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI)_ 457.Veroyatnost’ i Statistika. 25, 2017, pp. 226–264
  * [Led22] Michel Ledoux  “Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures”  In _Mathematics Going Forward: Collected Mathematical Brushstrokes_ Springer, 2022, pp. 615–627
  * [Oht14] Shin-ichi Ohta  “On the curvature and heat flow on Hamiltonian systems”  In _Anal. Geom. Metr. Spaces_ 2.1, 2014, pp. 81–114
  * [Pey18] Rémi Peyre  “Comparison between $W_{2}$ distance and $\dot{H}^{-1}$ norm, and localization of Wasserstein distance”  In _ESAIM, Control Optim. Calc. Var._ 24.4, 2018, pp. 1489–1501  DOI: 10.1051/cocv/2017050
  * [Ros70] Haskell P Rosenthal  “On the subspaces of $L^{p}$ ($p>2$) spanned by sequences of independent random variables”  In _Israel Journal of Mathematics_ 8 Springer, 1970, pp. 273–303
  * [Tei14] E. Teixeira  “Regularity for quasilinear equations on degenerate singular sets”  In _Math. Ann._ 358.1-2, 2014, pp. 241–256