\section{Introduction}
Let $d\geq 1$. 
We consider $\mu \in {\mathcal P}({\rr^d})$, the set of probability measures on ${\rr^d}$,
and an i.i.d. sequence $(X_k)_{k\geq 1}$
of $\mu$-distributed random variables. For $N\geq 1$, we introduce the empirical measure
\begin{equation}\label{muN}
\mu_N=\frac1N
\sum_{k=1}^N \delta_{X_k}.
\end{equation}

Estimating the rate of convergence of $\mu_N$ to $\mu$ is of course a fundamental problem,
and it seems that measuring this convergence in Wasserstein distance
is nowadays a widely adopted choice. 
Some seminal works on the subject are those by Dudley \cite{d},
Ajtai-Koml\'os-Tusn\'ady \cite{akt} and Dobri\'c-Yukich \cite{dy}. More recently, some results
have been established by Bolley-Guillin-Villani \cite{bgv}, Boissard-Le Gouic \cite{blg},
Dereich-Scheutzow-Schottstedt \cite{dss} and Fournier-Guillin \cite{fg}.
In particular, we can find in \cite{dss,fg} the following result.

\vskip.2cm

Fix some norm $|\cdot|$ on ${\mathbb{R}}^d$ and consider, for $p>0$ and $\mu,\nu \in {\mathcal P}({\rr^d})$, the transport cost
$$
{\mathcal T}_p(\mu,\nu) = \inf\Big\{\int_{{\rr^d}\times{\rr^d}} |x-y|^p \xi({\rm d} x,{\rm d} y) : \xi\in{\mathcal H}(\mu,\nu)\Big\},
$$ 
where
${\mathcal H}(\mu,\nu)$ stands for the set of probability measures on ${\rr^d}\times{\rr^d}$ with marginals
$\mu$ and $\nu$. It holds that ${\mathcal T}_p={\mathcal W}_p^p$, with the usual notation, if $p\geq 1$.
For $q>0$, we also define
$$
{\mathcal M}_q(\mu)= {\int_{\rd}} |x|^q \mu({\rm d} x).
$$
There exists a constant $C_{d,p,q}$ such that for all $\mu \in {\mathcal P}({\mathbb{R}}^d)$, for all $N\geq 1$,
with $\mu_N$ defined in \eqref{muN},
$$
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)] \leq C_{d,p,q} [{\mathcal M}_q(\mu)]^{p/q}\times \left\{ \begin{array}{cl}
N^{-1/2} & \hbox{if $p>d/2$ and $q>2p$},\\[5pt]
N^{-1/2} \log (1+N) & \hbox{if $p=d/2$ and $q>2p$},\\[5pt]
N^{-p/d} & \hbox{if $p\in (0,d/2)$ and $q>dp/(d-p)$}.
\end{array}\right.
$$
These bounds are sharp, but the constants in \cite{dss,fg} are either non explicit or large.
The number of required moments is also sharp. The case with less finite moments is also studied in \cite{fg}.

\vskip.2cm

We have been asked a high number of times, in particular by applied scientists, if one can compute the constant
$C_{d,p,q}$. If following the proofs in \cite{dss,fg}, one finds 
some huge constants.
But revisiting these proofs and optimizing as often as possible the computations,
which is the purpose of the present paper,
we obtain some rather reasonable constants, when using the maximum norm $|\cdot|_\infty$ on ${\rr^d}$. 
In particular, they remain finite
as the dimension tends to infinity (but of course, the rate of convergence in $N^{-p/d}$ is worse and worse).
\vskip.2cm
The reason why the maximum norm $|\cdot|_\infty$ is used in \cite{dss,fg} it that the proofs rely
on a partitioning of the unit ball, and that a cube is very easy to cut into 
smaller cubes. We of course deduce some bounds for the more natural Euclidean norm $|\cdot|_2$,
multiplying the constant by $d^{p/2}$. This leads to a constant (for the Euclidean norm) 
that explodes as $d\to \infty$.
\vskip.2cm
Using similar arguments, together with some ideas found in Weed-Bach \cite{wb}, Lei \cite[Theorem 3.1]{l}
proves that one can also find, in the case of the Euclidean norm, 
some constants (that he does not make explicit) that remain finite as $d\to\infty$.
We also produce, in the present paper, some explicit constants in this context.
\vskip.2cm
We present a unified proof for $|\cdot|_\infty$ and $|\cdot|_2$, 
specifying only at the end the choice of the norm.
Since the situation is more intricate for the Euclidean norm,
the constants we obtain are less good.
As we will see, 
it is actually preferable to use the bound concerning $|\cdot|_\infty$ multiplied
by $d^{p/2}$ for low dimensions, see e.g. Tables 3 and 4 below.
\vskip.2cm
Finally, let us mention that Dudley \cite{d} and more recently 
Weed-Bach \cite{wb} study the very interesting problem
of obtaining some rates of convergence depending on the {\it true} dimension of the problem:
if e.g. $\mu$ is a measure on ${\rr^d}$ but is actually carried by a manifold of lower dimension, what about
the rate of convergence ?
They introduce some notion of dimension of the measure $\mu$ and get some bounds
of $\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]$ in terms of this dimension. 
\vskip.2cm
We refer to the introduction of \cite{wb}, as well as those of 
\cite{l}, \cite{dss} and \cite{fg}, for some much more detailed presentations
of the subject and its numerous applications.


\section{Main results}


\subsection{Basic notation}
We consider the Euclidean and maximum norms: for $x=(x_1,\dots,x_d)\in{\mathbb{R}}^d$,
$$
|x|_2=\Big(\sum_{i=1}^d x_i^2 \Big)^{1/2}\qquad \hbox{and} \qquad |x|_\infty=\max \{|x_1|,\dots,|x_d|\}.
$$
For $p>0$, for $\mu,\nu$ in ${\mathcal P}({\rr^d})$ and for $i \in \{2,\infty\}$, we set
$$
{\mathcal T}_p^{(i)}(\mu,\nu) = \inf \Big\{\int_{{\rr^d}\times{\rr^d}} |x-y|_i^p \xi({\rm d} x,{\rm d} y) : \xi \in {\mathcal H}(\mu,\nu)\Big\},
$$
where we recall that ${\mathcal H}(\mu,\nu)$ is the set of probability measures on ${\rr^d}\times{\rr^d}$ with marginals
$\mu$ and $\nu$.
For $q>0$, for $\mu\in{\mathcal P}({\rr^d})$ and for $i\in\{2,\infty\}$, we define
$$
{\mathcal M}_q^{(i)}(\mu)= {\int_{\rd}} |x|_i^q \mu({\rm d} x).
$$
We of course have, since $|\cdot|_\infty \leq |\cdot|_2 \leq \sqrt d |\cdot|_\infty$, that
\begin{equation}\label{neq}
{\mathcal T}_p^{(\infty)}(\mu,\nu)\leq {\mathcal T}_p^{(2)}(\mu,\nu)\leq d^{p/2} {\mathcal T}_p^{(\infty)}(\mu,\nu)
\quad \hbox{and}\quad {\mathcal M}_q^{(\infty)}(\mu)\leq {\mathcal M}_q^{(2)}(\mu)\leq d^{q/2}{\mathcal M}_q^{(\infty)}(\mu).
\end{equation}

\subsection{Covering number}
Our proofs are based on a suitable partitioning of the unit ball. The case
of the maximum norm is not hard, because it is easy to cut a cube into smaller cubes.
The case of the Euclidean case is more intricate. For $r\in (0,1)$, we define
\begin{equation}\label{Nr}
N_r=\min\Big\{k\in {\mathbb{N}} : \exists\; x_1,\dots,x_k \in B_2(0,1) \hbox{ such that } B_2(0,1)\subset \cup_{i=1}^k 
B_2(x_i,r)\Big\},
\end{equation}
where $B_2(x,r)=\{y\in {\rr^d} : |x-y|_2<r\}$, as well as
\begin{equation}\label{Kd}
K_d=\sup_{r\in (0,1)} r^dN_r, \quad \hbox{so that for all } r\in (0,1), \quad N_r \leq K_d \,r^{-d}.
\end{equation}
An estimate of $K_d$ can be found in the work of Verger-Gaugry \cite{vg}, partly based on the results of
Rogers \cite{r},
see \eqref{KdVG} below.

\subsection{Main result}

For $x>0$ and $q>s>0$, we set
\begin{equation}\label{H}
H(x,s,q)=\Big(x\frac{q-s}{s}+(1+x)\Big(\frac{q}s\Big)^{q/(q-s)}\Big)^{s/q}\frac{q}{q-s}.
\end{equation}
The goal of this paper is to prove the following result.

\begin{thm}\label{mr}
We fix $p>0$ and $\mu \in {\mathcal P}({\rr^d})$, we set 
${\varepsilon}_p=\max\{2^{-1},2^{-p}\}$ and we recall \eqref{muN}. 

\vskip.2cm

(i) If $p>d/2$ and $q>2p$, then  for $i\in \{2,\infty\}$, for all $N \geq 1$,
$$
\mathbb{E}[{\mathcal T}_p^{(i)}(\mu_N,\mu)]\leq 2^p \frac{\kappa_{d,p}^{(i)}}{\sqrt N}[{\mathcal M}_q^{(i)}(\mu)]^{p/q}
\theta_{d,p,q}^{(i)},
\quad \hbox{where} \quad
\theta_{d,p,q}^{(i)}=H\Big(\frac{{\varepsilon}_p}{\kappa_{d,p}^{(i)}},2p,q\Big),
$$
with
$$
\kappa_{d,p}^{(\infty)}=\frac{2^{d/2-1}}{1-2^{d/2-p}},
$$
and with 
$$
\kappa_{d,p}^{(2)}=\min\{\kappa_{d,p,r}^{(2)} : r>2\},\qquad \hbox{where} \qquad
\kappa_{d,p,r}^{(2)}=\frac{\sqrt{K_d}}{2}\frac{r^{d}}{(r-2)^{d/2}(1-r^{d/2-p})}.
$$

(ii) If $p=d/2$ and $q>2p$, then for $i\in \{2,\infty\}$, for all $N \geq 1$,
$$
\mathbb{E}[{\mathcal T}_p^{(i)}(\mu_N,\mu)]\leq 2^p\frac{\kappa_{d,p,N}^{(i)}}{\sqrt N}[{\mathcal M}_q^{(i)}(\mu)]^{p/q}
\theta_{d,p,q,N}^{(i)}, \quad \hbox{where}\quad
\theta_{d,p,q,N}^{(i)}=H\Big(\frac{{\varepsilon}_p}{\kappa_{d,p,N}^{(i)}},2p,q\Big),
$$
with (here $\log_+(x)=\max\{\log x,0\}$)
$$
\kappa_{d,p,N}^{(\infty)}
=\frac{2^{p-1}}{p\log 2} \log_+\Big((2^{1-p}-2^{1-2p})\sqrt N \Big)+ \frac{2^{p-1}}{1-2^{-p}},
$$
and with  
$$\kappa_{d,p,N}^{(2)}=\min\{\kappa_{d,p,N,r}^{(2)} : r>2\},$$ 
where
$$
\kappa_{d,p,N,r}^{(2)}=
\frac{\sqrt{K_d}}2\frac{r^{2p}}{(r-2)^{p}p\log r}\log_+\Big(2(r-2)^{p}(r^{-2p}-r^{-3p})\sqrt{\frac N {K_d}}\Big)
+ \frac{\sqrt{K_d}}2 \frac{r^{3p}}{(r-2)^p(r^p-1)}.
$$

(iii) If $p\in (0,d/2)$ and $q>dp/(d-p)$, then for $i\in \{2,\infty\}$, for all $N \geq 1$,
$$
\mathbb{E}[{\mathcal T}_p^{(i)}(\mu_N,\mu)]\leq 2^p \frac{\kappa_{d,p}^{(i)}}{N^{p/d}} [{\mathcal M}_q^{(i)}(\mu)]^{p/q}\theta_{d,p,q}^{(i)},
\quad \hbox{where}\quad
\theta_{d,p,q}^{(i)}=H\Big(\frac{2^{1-2p/d}{\varepsilon}_p}{\kappa_{d,p}^{(i)}},\frac{dp}{d-p},q \Big),
$$ 
with
$$
\kappa_{d,p}^{(\infty)}=\frac{2^{p-2p/d}(1-2^{-d/2})^{1-2p/d}}{1-2^{p-d/2}},
$$
and with
$$
\kappa_{d,p}^{(2)}=\min\{\kappa_{d,p,r}^{(2)} : r>2\},\qquad\hbox{where}\qquad
\kappa_{d,p,r}^{(2)}=\Big(\frac{K_d}4\Big)^{p/d}\frac{r^{2p}(1-r^{-d/2})^{1-2p/d}}{(r-2)^p(1-r^{p-d/2})}.
$$
\end{thm}


\subsection{Comments}
By invariance by translation, we can replace ${\mathcal M}_q^{(i)}(\mu)$, 
in all the formulas, by
$$
\inf \Big\{{\int_{\rd}} |x-x_0|_i^q \mu({\rm d} x) : x_0 \in {\rr^d} \Big\}.
$$

Let us next observe, and we will see that this is often advantageous, that 
concerning the bound of $\mathbb{E}[{\mathcal T}_p^{(2)}(\mu_N,\mu)]$, by \eqref{neq},
we can replace
\vskip.2cm
$\bullet$ 
$\kappa^{(2)}_{d,p}$ by $d^{p/2}\kappa_{d,p}^{(\infty)}$ and $\theta^{(2)}_{d,p,q}$ by $\theta^{(\infty)}_{d,p,q}$ 
in items (i) and (iii);
\vskip.2cm
$\bullet$
$\kappa^{(2)}_{d,p,N}$ by $d^{p/2}\kappa_{d,p,N}^{(\infty)}$ and $\theta^{(2)}_{d,p,q,N}$ by 
$\theta^{(\infty)}_{d,p,q,N}$
in item (ii).

\vskip.2cm

Set $B_i(x,r)=\{y \in {\rr^d} : |x-y|_i<r\}$. In each case, we present the bound under the form
$$
\hbox{{\tt \Big(diameter of $B_i(0,1)\Big)^p$}$\times${\tt 
\Big(bound in the compact case\Big)}$\times [{\mathcal M}_q^{(i)}(\mu)]^{p/q}\times${\tt
\Big($\theta_{d,p,q}^{(i)}$ or $\theta_{d,p,q,N}^{(i)}$\Big)},}
$$
where {\it diameter of $B_i(0,1)$} equals $2$ and where by {\it compact case} 
we mean the case where $\mu$ is supported by the ball $B_i(0,1/2)$ with diameter $1$.
\vskip.2cm
One can tediously check that in each case, $q\to \theta_{d,p,q}^{(i)}$ (or $q\to \theta_{d,p,q,N}^{(i)}$) is decreasing
and tends to $1$ as $q\to \infty$. Hence if we are in the compact case, i.e. if $\mu$ is supported in 
$B_i(0,1/2)$, then 
${\mathcal M}_q^{(i)}(\mu)\leq 2^{-q}$ for all $q>0$, and we find that 
$$
\lim_{q\to \infty} \hbox{{\tt \Big(diameter of $B_i(0,1)\Big)^p$}$\times[{\mathcal M}_q^{(i)}(\mu)]^{p/q}\times${\tt
\Big($\theta_{d,p,q}^{(i)}$ or $\theta_{d,p,q,N}^{(i)}$\Big)}}=1,
$$
which justifies the denomination {\tt bound in the compact case}.
Let us mention that the explicit constant $\theta'_{d,p,q}$
provided in \cite[Theorem 3]{dss}, that concerns the case $p\in (0,d/2)$ and 
the maximum norm, tends to infinity as $q\to \infty$.
\vskip.2cm

One can tediously check
from (iii) that $p \to (\kappa_{d,p}^{(i)})^{1/p}$ is increasing for $p\in (0,d/2)$, which is natural
by monotony in $p$ of $[{\mathcal T}_p(\mu,\nu)]^{1/p}$. Actually, in the case of the Euclidean norm, it holds that
$p \to (\kappa_{d,p,r}^{(2)})^{1/p}$ is increasing for $p\in (0,d/2)$ for each $r>2$.
Still concerning (iii), an explicit
constant $\kappa'_{d,p}$ is provided in \cite[Proposition 1]{dss} for the maximum norm, but 
$(\kappa'_{d,p})^{1/p}$ tends to infinity as $p$ decreases to $0$.
\vskip.2cm

However, in the non compact case, we did not manage to guarantee such a property: it does not hold true that
in item (iii), $p\to [\kappa_{d,p}^{(i)}\theta_{d,p,q}^{(i)}]^{1/p}$ is increasing 
for $p \in (0,d/2)$, as it should. Hence it may be sometimes be preferable to use the bound:
for $p\in (0,d/2)$ and $q>dp/(d-p)$,
\begin{equation}\label{grosdefaut}
\mathbb{E}[{\mathcal T}_p^{(i)}(\mu_N,\mu)]\leq \inf_{p'\in [p,d/2)}\mathbb{E}[{\mathcal T}_{p'}^{(i)}(\mu_N,\mu)]^{p/p'}\leq
\inf_{p'\in [p,d/2)}2^p \frac{[\kappa_{d,p'}^{(i)}]^{p/p'}}{N^{p/d}} [{\mathcal M}_q^{(i)}(\mu)]^{p/q}[\theta_{d,p',q}^{(i)}]^{p/p'},
\end{equation}
with the convention that $\theta_{d,p',q}^{(i)}=\infty$ if $q\leq d p'/(d-p')$.
This is the major default of this work. We identified some computations that
might be done more carefully, but this led to awful complications, without producing some marked improvements.
\vskip.2cm
Finally, one can easily check from (iii)
that for any $p>0$,
$$
\lim_{d\to\infty} \kappa_{d,p}^{(\infty)} = 2^p \qquad \hbox{ and } \qquad \lim_{d\to\infty} \kappa_{d,p}^{(2)} = 8^p.
$$ 
Concerning the Euclidean case, we use \eqref{KdVG} below which implies that $\lim_{d\to \infty} K_d^{1/d}= 1$,
we find that $\lim_{d\to\infty} \kappa_{d,p,r}^{(2)} = (r-2)^{-p}r^{2p}$ for each $r>2$, and this (optimally)
equals $8^p$ with $r=4$.
The constant $\kappa_{d,p}'$ of \cite[Proposition 1]{dss}, for the maximum norm, increases 
to infinity as $d\to\infty$.

\subsection{Numerical values in the compact case}
We start with the maximum norm. 
\vskip.2cm
\begin{center}
\noindent\fbox{\begin{minipage}{0.97\textwidth}
\small{
\begin{center}
\renewcommand{\arraystretch}{1.9}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$d=1$&$d=2$&$d=3$&$d=4$&$d=5$&$d=6$&$d=7$&$d=8$&$d=9$&$d=100$&$d=500$
\\\hline
\large{$\frac{2.42}{N^{1/2}}$}&\large{$\frac{0.73\log N + 1}{N^{1/2}}$}&\large{$\frac{3.72}{N^{1/3}}$}&
\large{$\frac{2.45}{N^{1/4}}$}&\large{$\frac{2.09}{N^{1/5}}$}&\large{$\frac{1.94}{N^{1/6}}$}&
\large{$\frac{1.87}{N^{1/7}}$}&\large{$\frac{1.84}{N^{1/8}}$}&\large{$\frac{1.82}{N^{1/9}}$}&
\large{$\frac{1.98}{N^{1/100}}$}&\large{$\frac{2.00}{N^{1/500}}$}
\\\hline
\end{tabular}
\end{center}
{\sc Table 1.} Bound of $\mathbb{E}[{\mathcal T}_1^{(\infty)}(\mu_N,\mu)]$ for $N\geq 1$ (actually $N\geq 4$ when $d=2$),
if $\mu\in {\mathcal P}(B_\infty(0,1/2))$.}
\end{minipage}}
\end{center}
\vskip.2cm
\begin{center}
\noindent\fbox{\begin{minipage}{0.97\textwidth}
\small{
\begin{center}
\renewcommand{\arraystretch}{1.9}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$d=1$&$d=2$&$d=3$&$d=4$&$d=5$&$d=6$&$d=7$&$d=8$&$d=9$&$d=100$&$d=500$
\\\hline
\large{$\frac{1.05}{N^{1/4}}$}&\large{$\frac{1.42}{N^{1/4}}$}&\large{$\frac{2.20}{N^{1/4}}$}&
\large{$\frac{\sqrt{0.73\log N+1.26}}{N^{1/4}}$}&\large{$\frac{2.75}{N^{1/5}}$}&\large{$\frac{2.20}{N^{1/6}}$}&
\large{$\frac{2.01}{N^{1/7}}$}&\large{$\frac{1.92}{N^{1/8}}$}&\large{$\frac{1.87}{N^{1/9}}$}&
\large{$\frac{1.98}{N^{1/100}}$}&\large{$\frac{2.00}{N^{1/500}}$}
\\\hline
\end{tabular}
\end{center}
{\sc Table 2.} Bound of $\sqrt{\mathbb{E}[{\mathcal T}_2^{(\infty)}(\mu_N,\mu)]}$ for $N\geq 1$ (actually $N\geq 8$ when $d=4$),
if $\mu\in {\mathcal P}(B_\infty(0,1/2))$.}
\end{minipage}}
\end{center}
\vskip.2cm
We carry on with the Euclidean norm.
By Verger-Gaugry \cite[(1.1)-(1.3)-(1.4)]{vg}, where (1.1) is due to Rogers \cite{r},
we have the following bound of $K_d$ if $d\geq 8$ (we know from the author that there is a typo in
\cite{vg} and $d\geq 8$ is the correct condition, instead of $d \geq 2$):
\begin{gather}\label{KdVG}
K_d \leq \max\{K_{d,1},K_{d,2},K_{d,3}\},
\end{gather}
where (recall \eqref{Nr}-\eqref{Kd};
we have  $N_r=\nu_{T,n}$ with $2T=1/r$ and $n=d$ in the notation of \cite{vg})
\begin{gather*}
K_{d,1}= d^2[\log d + \log \log d +5],\\
K_{d,2}=\frac{7^{4(\log 7)/7}}4\sqrt{\frac\pi 2}d^{3/2}\frac{2(d-1)\log d +\frac12\log d
+ \log(\frac{\pi\sqrt{2d}}{\sqrt{\pi d}-2})}
{(1-2/\log d)(1-2/\sqrt{\pi d})(\log d)^2},\\
K_{d,3}= \sqrt{2 \pi d} \frac{(d-1)\log(2d)+(d-1)\log\log d +\frac12\log d
+ \log(\frac{\pi\sqrt{2d}}{\sqrt{\pi d}-2})}
{(1-2/\log d)(1-2/\sqrt{\pi d})}. 
\end{gather*}
\vskip.2cm
\begin{center}
\noindent\fbox{\begin{minipage}{0.97\textwidth}
\small{
\begin{center}
\renewcommand{\arraystretch}{1.9}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
$d=8$&$d=15$&$d=20$&$d=25$&$d=30$&$d=35$&$d=50$&$d=75$&$d=100$&$d=500$
\\\hline
\large{$\frac{23.44}{N^{1/8}}$}&\large{$\frac{13.40}{N^{1/15}}$}&\large{$\frac{11.98}{N^{1/20}}$}&
\large{$\frac{11.20}{N^{1/25}}$}&\large{$\frac{10.69}{N^{1/30}}$}&\large{\boldmath$\frac{10.34}{N^{1/35}}$}&
\large{\boldmath$\frac{9.70}{N^{1/50}}$}&\large{\boldmath$\frac{9.19}{N^{1/75}}$}&\large{\boldmath$\frac{8.93}{N^{1/100}}$}&
\large{\boldmath$\frac{8.24}{N^{1/500}}$}
\\\hline
\large{\boldmath$\frac{5.18}{N^{1/8}}$}&\large{\boldmath$\frac{7.11}{N^{1/15}}$}&\large{\boldmath$\frac{8.36}{N^{1/20}}$}&
\large{\boldmath$\frac{9.47}{N^{1/25}}$}&\large{\boldmath$\frac{10.47}{N^{1/30}}$}&\large{$\frac{11.38}{N^{1/35}}$}&
\large{$\frac{13.76}{N^{1/50}}$}&\large{$\frac{17.01}{N^{1/75}}$}&\large{$\frac{19.73}{N^{1/100}}$}&
\large{$\frac{44.60}{N^{1/500}}$}
\\\hline
\end{tabular}
\end{center}
{\sc Table 3.} Bound of $\mathbb{E}[{\mathcal T}_1^{(2)}(\mu_N,\mu)]$ for $N\geq 1$
if $\mu\in {\mathcal P}(B_2(0,1/2))$, using the bound proposed for the Euclidean norm in 
Theorem \ref{mr}-(iii) (second line)
and using $\sqrt{d}$ times the bound proposed for the maximum norm (third line). In bold the one to be used.}
\end{minipage}}
\end{center}
\vskip.2cm
\begin{center}
\noindent\fbox{\begin{minipage}{0.97\textwidth}
\small{
\begin{center}
\renewcommand{\arraystretch}{1.9}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
$d=8$&$d=15$&$d=20$&$d=25$&$d=30$&$d=35$&$d=50$&$d=75$&$d=100$&$d=500$
\\\hline
\large{$\frac{23.86}{N^{1/8}}$}&\large{$\frac{13.41}{N^{1/15}}$}&\large{$\frac{11.98}{N^{1/20}}$}&
\large{$\frac{11.20}{N^{1/25}}$}&\large{$\frac{10.69}{N^{1/30}}$}&\large{\boldmath$\frac{10.34}{N^{1/35}}$}&
\large{\boldmath$\frac{9.70}{N^{1/50}}$}&\large{\boldmath$\frac{9.19}{N^{1/75}}$}&\large{\boldmath$\frac{8.93}{N^{1/100}}$}&
\large{\boldmath$\frac{8.24}{N^{1/500}}$}
\\\hline
\large{\boldmath$\frac{5.41}{N^{1/8}}$}&\large{\boldmath$\frac{7.13}{N^{1/15}}$}&\large{\boldmath$\frac{8.36}{N^{1/20}}$}&
\large{\boldmath$\frac{9.47}{N^{1/25}}$}&\large{\boldmath$\frac{10.47}{N^{1/30}}$}&\large{$\frac{11.38}{N^{1/35}}$}&
\large{$\frac{13.76}{N^{1/50}}$}&\large{$\frac{17.01}{N^{1/75}}$}&\large{$\frac{19.73}{N^{1/100}}$}&
\large{$\frac{44.60}{N^{1/500}}$}
\\\hline
\end{tabular}
\end{center}
{\sc Table 4.} Bound of $\sqrt{\mathbb{E}[{\mathcal T}_2^{(2)}(\mu_N,\mu)]}$ for $N\geq 1$
if $\mu\in {\mathcal P}(B_2(0,1/2))$, using the bound proposed for the Euclidean norm in 
Theorem \ref{mr}-(iii) (second line)
and using $\sqrt{d}$ times the bound proposed for the maximum norm (third line). In bold the one to be used.}
\end{minipage}}
\end{center}
\vskip.2cm
As we can see, in large dimension, the bounds concerning $p=1$ and $p=2$ are very similar.
Also, we see that, for $p=1$ and $p=2$, it is better to use $\sqrt{d}$ 
times the bound proposed for the maximum norm
when $d\in \{8,\dots,30\}$. Hence it does not seem crucial to find a formula similar to \eqref{KdVG}
when $d\in \{2,\dots,7\}$.

\subsection{Numerical values in the non-compact case}

Here we study how $\theta^{(i)}_{d,p,q}$ is far from $1$.
When $p=d/2$, we observe that $N \mapsto \theta^{(i)}_{d,p,q,N}$ is decreasing, and we 
e.g. study $\theta^{(i)}_{d,p,q,100}$ (which controls $\theta^{(i)}_{d,p,q,N}$ for all $N\geq 100$).
We start with the maximum norm.
\vskip.2cm

\begin{center}
\noindent\fbox{\begin{minipage}{0.95\textwidth}
\small{
\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$d=1$  &$d=2$  &$d=3$  &$d=4$  &$d=5$  &$d=6$  &$d=7$  &$d=8$  &$d=9$  &$d=100$ &$d=500$
\\\hline
$4.4$  &$4.2$  &$3.3$  &$3.0$  &$2.9$  &$2.8$  &$2.8$  &$2.7$  &$2.7$  &$2.5$   &$2.4$
\\\hline
$9.8$  &$9.4$  &$7.3$  &$6.8$  &$6.5$  &$6.4$  &$6.3$  &$6.2$  &$6.1$  &$5.5$   &$5.5$
\\\hline
$40.4$ &$39.0$ &$29.9$ &$27.7$ &$26.6$ &$25.9$ &$25.3$ &$25.0$ &$24.6$ &$22.3$  &$22.1$
\\\hline
\end{tabular}
\end{center}
{\sc Table 5.} Here $p=1$.
Minimum value of $q$ so that $\theta_{d,1,q}^{(\infty)} \leq c$ if
$d\neq 2$ or $\theta_{d,1,q,100}^{(\infty)} \leq c$ if $d= 2$,
with $c=4$ (second line), $c=2$ (third line), $c=1.25$ (fourth line).}
\end{minipage}}
\end{center}
\vskip.2cm
\begin{center}
\noindent\fbox{\begin{minipage}{0.95\textwidth}
\small{
\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$d=1$  &$d=2$  &$d=3$  &$d=4$  &$d=5$  &$d=6$  &$d=7$  &$d=8$  &$d=9$  &$d=100$ &$d=500$
\\\hline
$5.1$  &$5.0$  &$4.9$  &$4.9$  &$4.1$  &$3.7$  &$3.5$  &$3.3$  &$3.2$  &$2.6$   &$2.5$
\\\hline
$9.5$  &$8.9$  &$8.4$  &$8.4$  &$6.9$  &$6.4$  &$6.0$  &$5.8$  &$5.7$  &$4.6$   &$4.5$
\\\hline
$37.0$ &$34.5$ &$32.4$ &$32.5$ &$26.7$ &$24.6$ &$23.4$ &$22.5$ &$21.9$ &$17.7$  &$17.4$
\\\hline
\end{tabular}
\end{center}
{\sc Table 6.} Here $p=2$.
Minimum value of $q$ so that $\sqrt{\theta_{d,2,q}^{(\infty)}} \leq c$ if
$d\neq 4$ or $\sqrt{\theta_{d,2,q,100}^{(\infty)}} \leq c$ if $d=4$,
with $c=4$ (second line), $c=2$ (third line), $c=1.25$ (fourth line).}
\end{minipage}}
\end{center}
\vskip.2cm
Comparing Tables 5 and 6, it seems clear that, at least for large values
of $d$, it is preferable to use the bound \eqref{grosdefaut}.

\vskip.2cm

We do the same job concerning the Euclidean norm. 
We only deal with $\theta_{d,1,q}^{(2)}$ as defined in Theorem \ref{mr} for simplicity,
even if we recall that it is preferable to use \eqref{neq} and the bound concerning the maximum norm
for low dimensions.
\vskip.2cm
\begin{center}
\noindent\fbox{\begin{minipage}{0.95\textwidth}
\small{
\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$d=8$  &$d=15$  &$d=20$  &$d=25$  &$d=30$  &$d=35$  &$d=50$  &$d=75$  &$d=100$  &$d=500$
\\\hline
$2.4$  &$2.3$   &$2.2$   &$2.2$   &$2.2$  &$2.2$   &$2.2$   &$2.2$   &$2.2$    &$2.2$
\\\hline
$5.2$  &$5.0$   &$4.9$   &$4.9$   &$4.8$   &$4.8$   &$4.8$   &$4.8$   &$4.8$    &$4.8$
\\\hline
$21.5$ &$20.5$  &$20.2$  &$20.1$  &$20.0$  &$19.9$  &$19.8$  &$19.7$  &$19.7$   &$19.6$
\\\hline
\end{tabular}
\end{center}
{\sc Table 7.} Here $p=1$.
Minimum value of $q$ so that $\theta_{d,1,q}^{(2)} \leq c$
with $c=4$ (second line), $c=2$ (third line), $c=1.25$ (fourth line).}
\end{minipage}}
\end{center}
\vskip.2cm
\begin{center}
\noindent\fbox{\begin{minipage}{0.95\textwidth}
\small{
\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$d=8$  &$d=15$  &$d=20$  &$d=25$  &$d=30$  &$d=35$  &$d=50$  &$d=75$  &$d=100$  &$d=500$
\\\hline
$3.2$  &$2.8$   &$2.7$   &$2.6$   &$2.6$   &$2.6$   &$2.5$   &$2.5$   &$2.5$    &$2.4$
\\\hline
$5.4$  &$4.7$   &$4.5$   &$4.4$   &$4.4$   &$4.3$   &$4.2$   &$4.2$   &$4.2$    &$4.1$
\\\hline
$20.5$ &$17.7$  &$17.1$  &$16.7$  &$16.5$  &$16.4$  &$16.1$  &$15.9$  &$15.8$   &$15.5$
\\\hline
\end{tabular}
\end{center}
{\sc Table 8.} Here $p=2$.
Minimum value of $q$ so that $\sqrt{\theta_{d,2,q}^{(2)}} \leq c$
with $c=4$ (second line), $c=2$ (third line), $c=1.25$ (fourth line).}
\end{minipage}}
\end{center}
\vskip.2cm

Comparing Tables 7 and 8, it seems again clear that
it is not vain to use the bound \eqref{grosdefaut}.


\subsection{On a possible lowerbound}
As mentioned to us by Pag\`es, we have the following lowerbound, 
holding for $i\in \{2,\infty\}$ and actually for any other norm.
Consider $X_1,\dots,X_N$ independent and $\mu$-distributed.
It holds that ${\mathcal T}_p^{(i)}(\mu_N,\mu) \geq {\mathcal S}_p^{(i)}(\mu;X_1,\dots,X_N)$, where
$$
{\mathcal S}_p^{(i)}(\mu;x_1,\dots,x_d)=\inf\Big\{{\mathcal T}_p^{(i)}\Big(\mu,\sum_{i=1}^N \alpha_i \delta_{x_i}\Big) 
: (\alpha_i)_{i=1,\dots,N} \in [0,1]^N,\;\sum_{i=1}^N \alpha_i=1\Big\},
$$
and Luschgy-Pag\`es show in \cite{lp} that, under some technical conditions on $\mu$,
$$
\lim_{N\to \infty} N^{-p/d} \mathbb{E}[{\mathcal S}_p^{(i)}(\mu;X_1,\dots,X_n)]=\frac{\Gamma(1+p/d)}{[\lambda_d(B_{(i)}(0,1))]^{p/d}} 
\int_{{\rr^d}} [f(x)]^{1-p/d} {\rm d} x,
$$
where $f$ is the density of $\mu$, where $\lambda_d$ is the Lebesgue measure on ${\rr^d}$
and where $\Gamma$ is the classical $\Gamma$ function.
Choosing for $\mu$ the uniform law on $B_i(0,1/2)$, we find that for $i\in\{2,\infty\}$,
$$
\liminf_{N \to \infty} N^{-p/d}\mathbb{E}[{\mathcal T}_p^{(i)}(\mu_N,\mu)] \geq  \lim_{N\to \infty} N^{-p/d} \mathbb{E}[{\mathcal S}_p^{(i)}(\mu;X_1,\dots,X_n)]
=\frac{\Gamma(1+p/d)}{2^p}=: \gamma_{d,p},
$$
to be compared with $\kappa_{d,p}^{(i)}$ when $p \in (0,d/2)$.
This may be a rough lowerbound, because this is an asymptotic bound as $N\to \infty$, and because
${\mathcal S}_p^{(i)}(\mu;X_1,\dots,X_N)$ is likely to be really smaller 
than ${\mathcal T}_p^{(i)}(\mu_N,\mu)$ (in particular it converges in $N^{-p/d}$ when $p>d/2$ while ${\mathcal T}_p^{(i)}(\mu_N,\mu)$
only converges in $N^{-1/2}$ in general when $p>d/2$).

\vskip.2cm

It holds that $\gamma_{d,1}\in (0.44,0.5)$ for all $d \geq 3$, to be compared with
the numerators in Tables 1 and 3. Hence when $p=1$ and say $d\geq 4$, see Table 1,
$\kappa_{d,1}^{(\infty)}$ is at worst $6$ times too large.
When $p=1$ and $d\geq 8$, see Table 3, $\min\{\kappa_{d,1}^{(2)},\sqrt d \kappa_{d,1}^{(\infty)}\}$
is at worst $24$ times too large.
We hope this is pessimistic.
\vskip.2cm
It holds that $\sqrt{\gamma_{d,2}}\in (0.47,0.5)$ for all $d \geq 5$, 
to be compared with the numerators in Tables 2 and 4. When $p=2$ and $d\geq 5$, see Table 2,
$(\kappa_{d,2}^{(\infty)})^{1/2}$ is at worst $6$ times too large. 
When $p=2$ and $d\geq 8$, see Table 4, $\min\{(\kappa_{d,2}^{(2)})^{1/2},\sqrt d (\kappa_{d,2}^{(\infty)})^{1/2}\}$
is at worst $23$ times too large.
Again, we hope this is pessimistic.

\vskip.2cm

We do not discuss the non compact case, but the numerical results do not seem
quite favorable.

\subsection{The case with a low order finite moment}
Since this last result is likely to be much
less useful for applications, we only treat the case of the maximum norm.

\begin{thm}\label{mrn}
Let $q>p>0$ such that $q<\min\{2p,dp/(d-p)\}$, i.e. $q\in(p,2p)$ if 
$p\geq d/2$ and $q\in(p,dp/(d-p))$ if $p\in (0,d/2]$. 
Fix $\mu \in {\mathcal P}({\rr^d})$.
For all $N\geq 1$,
$$
\mathbb{E}[{\mathcal T}_p^{(\infty)}(\mu_N,\mu)]\leq 2^p [{\mathcal M}_q^{(\infty)}(\mu)]^{p/q} \frac{\zeta_{d,p,q}^{(\infty)}}{N^{(q-p)/q}},
$$
where, setting ${\varepsilon}_p=\max\{2^{-1},2^{-p}\}$,
$$
\zeta_{d,p,q}^{(\infty)}=\Big[{\varepsilon}_p 2^{2p/q-1} +\Big(\frac{2^{d-1}}{2^{d/2}-1}\Big)^{2(q-p)/q}\frac{1-2^{-p}}{1-2^{d-p-dp/q}}\Big]
\min_{a\in(1,\infty)} \Big(\frac{a^p}{a^{p-q/2}-1}+ \frac{a^p}{1-a^{p-q}}\Big).
$$
\end{thm}

\subsection{Plan of the paper}
In Section \ref{gu}, we provide a general estimate of the transport cost between two measures.
In Section \ref{gume}, we apply this general estimate to derive a bound of
$\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]$, for a general norm, for all the values of $p>0$ and in any dimension.
In Section \ref{series}, we precisely study some elementary series.
We obtain a bound of
$\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]$, for a general norm, separating the cases $p>d/2$, $p=d/2$ and $p\in (0,d/2)$
in Section \ref{titrenaze}.
We conclude the proof of Theorem \ref{mr} for the maximum norm in Section \ref{concmax}
and for the Euclidean norm in Section \ref{conceuc}.
Finally, we check Theorem \ref{mrn} in Section \ref{lom}.


\section{Upperbound of the transport cost between two measures}\label{gu}

The result we prove in this section, Proposition \ref{depart}, 
is more or less classical, see  Boissard-Le Gouic \cite[Proposition 1.1]{blg},
Dereich-Scheutzow-Schottstedt \cite[Lemma 2 and Theorem 3]{dss},
Fournier-Guillin \cite[Lemma 5]{fg} and Weed-Bach \cite[Proposition 1]{wb}.
As noted in \cite{wb}, similar ideas can already be found in Ajtai-Koml\'os-Tusn\'ady \cite{akt}.
However, we provide a slightly more
precise version, that allows us to get some smaller constants.
We consider fixed the following objects.

\begin{set}\label{sss}
(a) We fix a norm $|\cdot|$ on ${\mathbb{R}}^d$. We denote by $B(x,r)=\{y\in{\rr^d} : |x-y|<r\}$ the corresponding balls,
by ${\mathcal T}_p(\mu,\nu)=\inf_{\xi \in {\mathcal H}(\mu,\nu)} \int_{{\rr^d}\times{\rr^d}}|x-y|^p \xi({\rm d} x,{\rm d} y)$
the corresponding transport cost, and by ${\mathcal M}_q(\mu)=\int_{{\rr^d}}|x|^q \mu({\rm d} x)$ the corresponding moments.
\vskip.2cm
(b) Let $G_0=B(0,1)$. For $a>1$, we set $G_0^a=G_0$ and, for all $n\geq 1$, 
$G_n^a=B(0,a^n)\setminus B(0,a^{n-1})$.
\vskip.2cm
(c) We consider a family $({\mathcal Q}_\ell)_{\ell=0,\dots,k}$ of nested partitions of $G_0$ such that ${\mathcal Q}_0=\{G_0\}$.
For each $\ell=1,\dots,k$, each $C \in {\mathcal Q}_{\ell}$,
there exists a unique $F \in {\mathcal Q}_{\ell-1}$ such that $C \subset F$; we then say that $C$ is a child of $F$. 
For $\ell=0,\dots,k$, we denote by $|{\mathcal Q}_\ell|$ the cardinal of 
${\mathcal Q}_\ell$ and we set
$$
\delta_\ell = \max_{C \in {\mathcal Q}_\ell} \sup_{x,y \in C} |x-y|.
$$
\end{set}

For $C\subset {\mathbb{R}}^d$ and $r>0$, we put $rC=\{rx : x \in C\}$. Recall that ${\varepsilon}_p=2^{-1}\lor 2^{-p}$.

\begin{prop}\label{depart}
We adopt Setting \ref{sss} and consider
$\mu,\nu \in {\mathcal P}({\mathbb{R}}^d)$. 
For all $a>1$,
there are some nonnegative numbers 
$(r_{a,n,\ell}(\mu,\nu))_{n\geq 0,\ell= 0,\dots,k-1}$ satisfying 
\begin{gather}
\sum_{\ell=0}^{k-1} r_{a,n,\ell}(\mu,\nu)\leq 1\label{rnl1}
\end{gather}
for all $n\geq 0$ and, with the convention that $0/0=0$,
\begin{gather}
r_{a,n,\ell}(\mu,\nu)\!\leq\! \frac12\sum_{F\in{\mathcal Q}_\ell} 
\Big(\frac{\mu(a^nF \cap G_n^a)}{\mu(G_n^a)}\land\frac{\nu(a^nF \cap G_n^a)}{\nu(G_n^a)}\Big)\hskip-5pt
\sum_{C \!\hbox{\tiny{ child of }}\! F}
\Big|\frac{\mu(a^nC \cap G_n^a)}{\mu(a^nF \cap G_n^a)}-\frac{\nu(a^nC \cap G_n^a)}{\nu(a^nF \cap G_n^a)} \Big|
\label{rnl2}
\end{gather}
for all $n\geq 0$, all $\ell=0,\dots,k-1$, 
and such that for all $p>0$,
\begin{align*}
{\mathcal T}_p(\mu,\nu) \leq& \sum_{n\geq 0} a^{pn}\Big( 2^p{\varepsilon}_p |\mu(G_n^a)-\nu(G_n^a)| + 
(\mu(G_n^a)\land\nu(G_n^a)) \Big[\delta_k^p+\sum_{\ell= 0}^{k-1} \delta_\ell^p r_{a,n,\ell}(\mu,\nu)\Big] \Big).
\end{align*}
\end{prop}

The coefficients $r_{a,n,\ell}(\mu,\nu)$ are  actually explicit, but it seems difficult
to use more than the properties \eqref{rnl1}-\eqref{rnl2}.
We start with the compact case.

\begin{lem}\label{cc}
Let $\mu,\nu \in {\mathcal P}(B(0,1))$. There is
$(u_{\ell}(\mu,\nu))_{\ell=0,\dots,k-1} \in {\mathbb{R}}_+^{k}$ satisfying
\begin{gather}
\sum_{\ell=0}^{k-1} u_\ell(\mu,\nu)\leq 1 \label{sul}
\end{gather}
and
\begin{gather}
u_{\ell}(\mu,\nu)\leq \frac12\sum_{F\in{\mathcal Q}_\ell} (\mu(F)\land \nu(F)) \hskip-5pt\sum_{C \!\hbox{\tiny{ child of }}\! F}
\Big|\frac{\mu(C)}{\mu(F)}-\frac{\nu(C)}{\nu(F)} \Big|, \qquad \ell=0,\dots,k-1, \label{ul}
\end{gather}
and such that for all $p>0$,
\begin{align*}
{\mathcal T}_p(\mu,\nu) \leq& \delta_k^p+ \sum_{\ell=0}^{k-1} \delta_\ell^{p} u_{\ell}(\mu,\nu).
\end{align*}
\end{lem}


\begin{proof}
For all $0\leq i\leq\ell\leq k$ and $C\in {\mathcal Q}_\ell$, let
$f_i(C)$ be the unique element of ${\mathcal Q}_i$ containing $C$.

\vskip.2cm

{\it Step 1: construction of the coupling.} For all $F \in {\mathcal Q}_k$, we set
\begin{equation}\label{ttc}
\xi_{F}({\rm d} x,{\rm d} y)=\frac{\mu|_{F}({\rm d} x)}{\mu(F)}\frac{\nu|_{F}({\rm d} y)}{\nu(F)}.
\end{equation}
Then by reverse induction, for $\ell\in\{0,\dots,k-1\}$ and $F\in {\mathcal Q}_\ell$, we build
\begin{align}\label{dfck}
\xi_{F}({\rm d} x,{\rm d} y)=\sum_{C \!\hbox{\tiny{ child of }}\! F}
\rho_C \xi_C({\rm d} x,{\rm d} y) + q_F \alpha_F({\rm d} x) \beta_F({\rm d} y),
\end{align}
where
$$
\rho_C= \frac{\mu(C)}{\mu(F)}\land \frac{\nu(C)}{\nu(F)},
$$
which depends only on $C \in {\mathcal Q}_{\ell+1}$ since $F=f_{\ell}(C)$, where
\begin{equation}\label{ano0}
q_F=\frac12\sum_{C \!\hbox{\tiny{ child of }}\! F}
\Big|\frac{\mu(C)}{\mu(F)}-\frac{\nu(C)}{\nu(F)} \Big|,
\end{equation}
and where
\begin{align*}
\alpha_F({\rm d} x)=& \frac1{q_F} \sum_{C \!\hbox{\tiny{ child of }}\! F} 
\Big(\frac{\mu(C)}{\mu(F)}-\frac{\nu(C)}{\nu(F)} \Big)_+\frac{\mu|_{C}({\rm d} x)}{\mu(C)},\\
\beta_F({\rm d} x)=& \frac1{q_F} \sum_{C \!\hbox{\tiny{ child of }}\! F} 
\Big(\frac{\nu(C)}{\nu(F)}-\frac{\mu(C)}{\mu(F)} \Big)_+\frac{\nu|_{C}({\rm d} x)}{\nu(C)}.
\end{align*}
It holds that $\alpha_F$ and $\beta_F$ are two probability measures on $F$, because
\begin{equation}\label{ano}
q_F=\sum_{C \!\hbox{\tiny{ child of }}\! F}
\Big(\frac{\mu(C)}{\mu(F)}-\frac{\nu(C)}{\nu(F)} \Big)_+
=\sum_{C \!\hbox{\tiny{ child of }}\! F}
\Big(\frac{\nu(C)}{\nu(F)}-\frac{\mu(C)}{\mu(F)} \Big)_+.
\end{equation}

{\it Step 2.} Here we show that $\xi_{G_0} \in {\mathcal H}(\mu,\nu)$,
so that ${\mathcal T}_p(\mu,\nu)\leq \int_{{\rr^d}\times{\rr^d}}|x-y|^p\xi_{G_0}({\rm d} x,{\rm d} y)$.
We recall that $G_0=B(0,1)$ is the unique element of ${\mathcal Q}_0$.

\vskip.2cm
We actually prove by 
reverse induction that for all $\ell\in\{0,\dots,k\}$, all $F \in {\mathcal Q}_\ell$, it holds that 
$\xi_F \in {\mathcal H}(\frac{\mu|_{F}}{\mu(F)}, \frac{\nu|_{F}}{\nu(F)})$.
The result will then follow by choosing $\ell=0$ and $F=G_0$.
\vskip.2cm
This is obvious if $\ell=k$, see \eqref{ttc}. 
Next, we assume that this holds true for some $\ell+1 \in \{1,\dots,k\}$,
and we consider $F\in {\mathcal Q}_\ell$.
For $A\in{\mathcal B}({\mathbb{R}}^d)$, we use \eqref{dfck} to write
$$
\xi_F(A\times {\mathbb{R}}^d)=\sum_{C \!\hbox{\tiny{ child of }}\! F}\rho_C \xi_{C}(A\times {\mathbb{R}}^d) + q_F\alpha_F(A)
=\sum_{C \!\hbox{\tiny{ child of }}\! F}\rho_C \frac{\mu(A\cap C)}{\mu(C)} + q_F\alpha_F(A)
$$
by induction assumption. Thus
$$
\xi_F(A\times {\mathbb{R}}^d)=\hskip-5pt\sum_{C \!\hbox{\tiny{ child of }}\! F} \Big[\frac{\mu(C)}{\mu(F)}\land \frac{\nu(C)}{\nu(F)}
+\Big(\frac{\mu(C)}{\mu(F)}-\frac{\nu(C)}{\nu(F)} \Big)_+ \Big]\frac{\mu(A\cap C)}{\mu(C)}
=\hskip-5pt\sum_{C \!\hbox{\tiny{ child of }}\! F} \frac{\mu(C)}{\mu(F)}\frac{\mu(A\cap C)}{\mu(C)},
$$
whence $\xi_F(A\times {\mathbb{R}}^d)=\mu(A\cap F)/\mu(F)$. One shows 
similarly that $\xi_F({\mathbb{R}}^d\times A)=\nu(A\cap F)/\nu(F)$.

\vskip.2cm

{\it Step 3.} For $i\in\{0,\dots,k\}$ and $F\in {\mathcal Q}_i$, we put $m_F=\int_{{\rr^d}\times{\rr^d}}|x-y|^p\xi_F({\rm d} x,{\rm d} y)$.
In this step, we show by induction that for all $i\in\{0,\dots,k-1\}$,
\begin{equation}\label{rectd}
m_{G_0}\leq \delta_0^pq_{G_0}+\sum_{\ell=1}^i \delta_{\ell}^p\sum_{C_\ell\in {\mathcal Q}_\ell} \Big(\prod_{j=1}^\ell\rho_{f_j(C_\ell)}\Big)
q_{C_\ell}+ \sum_{C_{i+1}\in{\mathcal Q}_{i+1}} \Big(\prod_{j=1}^{i+1}\rho_{f_j(C_{i+1})}\Big)m_{C_{i+1}}.
\end{equation}

Recalling \eqref{dfck}, since the set of all the children of $G_0$ is ${\mathcal Q}_1$, and since
$|x-y|\leq \delta_0$ for all $x,y\in G_0$, so that $\int_{{\rr^d}\times{\rr^d}}|x-y|^p\alpha_{G_0}({\rm d} x)\beta_{G_0}({\rm d} y)
\leq \delta_0^p$, we see that
$$
m_{G_0} \leq \delta_0^p q_{G_0} + \sum_{C_1 \in {\mathcal Q}_1} \rho_{C_1} m_{C_1}
= \delta_0^p q_{G_0} + \sum_{C_1 \in {\mathcal Q}_1} \rho_{f_1(C_1)} m_{C_1},
$$
which is \eqref{rectd} with $i=0$. Assume now that \eqref{rectd} holds true for some 
$i \in \{0,\dots,k-2\}$. For all $C_{i+1}\in{\mathcal Q}_{i+1}$, we use \eqref{dfck} and 
that $\int_{{\rr^d}\times{\rr^d}}|x-y|^p\alpha_{C_{i+1}}({\rm d} x)\beta_{C_{i+1}}({\rm d} y) \leq \delta_{i+1}^p$
to write
$$
m_{C_{i+1}} \leq \delta_{i+1}^p q_{C_{i+1}} + \sum_{C_{i+2} \!\hbox{\tiny{ child of }}\! C_{i+1}} 
\rho_{C_{i+2}}m_{C_{i+2}}.
$$
Hence, since $f_j(C_{i+2})=f_j(C_{i+1})$
for all $j=1,\dots,i+1$ if $C_{i+2}$ is a child of $C_{i+1}$,
\begin{align*}
\sum_{C_{i+1}\in{\mathcal Q}_{i+1}} \hskip-5pt \Big(\prod_{j=1}^{i+1}\rho_{f_j(C_{i+1})}\Big)m_{C_{i+1}} \leq &
 \delta_{i+1}^p \hskip-5pt
\sum_{C_{i+1}\in{\mathcal Q}_{i+1}} \hskip-5pt\Big(\prod_{j=1}^{i+1}\rho_{f_j(C_{i+1})}\Big)q_{C_{i+1}}
+ \hskip-5pt\sum_{C_{i+2}\in{\mathcal Q}_{i+2}} \hskip-5pt\Big(\prod_{j=1}^{i+2}\rho_{f_j(C_{i+2})}\Big)m_{C_{i+2}}.
\end{align*}
This last formula, inserted in \eqref{rectd}, gives \eqref{rectd} with $i+1$ instead of $i$.

\vskip.2cm

{\it Step 4.} For all $C_{k} \in {\mathcal Q}_k$, we have $m_{C_k} \leq \delta_k^p$ by \eqref{ttc} and since 
$x,y\in C_k$ implies
that $|x-y| \leq \delta_k$. Hence, by definition of $\rho_F$,
$$
\sum_{C_{k}\in{\mathcal Q}_{k}} \Big(\prod_{j=1}^{k}\rho_{f_j(C_{k})}\Big)m_{C_{k}}
\leq \delta_k^p \sum_{C_{k}\in{\mathcal Q}_{k}} \prod_{j=1}^{k}\frac{\mu(f_j(C_{k}))}{\mu(f_{j-1}(C_{k}))}
=\delta_k^p \sum_{C_{k}\in{\mathcal Q}_{k}}\mu(C_{k})=\delta_k^p.
$$
This, inserted in \eqref{rectd} with $i=k-1$, tells us that
$$
m_{G_0}\leq \delta_0^p q_{G_0} +\sum_{\ell=1}^{k-1} \delta_\ell^{p}\sum_{C_\ell\in {\mathcal Q}_\ell} \Big(\prod_{j=1}^\ell\rho_{f_j(C_\ell)}
\Big)q_{C_\ell}+ \delta_k^p.
$$
Since ${\mathcal T}_p(\mu,\nu)\leq m_{G_0}$ by Step 2, we conclude that
$$
{\mathcal T}_p(\mu,\nu) \leq  \sum_{\ell=0}^{k-1} \delta_\ell^{p}u_\ell(\mu,\nu) + \delta_k^p,
$$
where 
$$
u_0(\mu,\nu)=q_{G_0} \qquad \hbox{and} \qquad 
u_\ell(\mu,\nu)=\sum_{C_\ell\in {\mathcal Q}_\ell} (\prod_{j=1}^\ell\rho_{f_j(C_\ell)})q_{C_\ell} 
\quad\hbox{for}\quad \ell\in \{1,\dots,k-1\}.
$$

{\it Step 5.} We now check by induction that for all $n=1,\dots,k$,  
\begin{align}\label{find}
\sum_{\ell=0}^{n-1} u_\ell(\mu,\nu)=1- \sum_{C_n \in {\mathcal Q}_n} \prod_{j=1}^n\rho_{f_j(C_n)},
\end{align}
and this will imply \eqref{sul}. If first $n=1$, by \eqref{ano},
$$
u_0(\mu,\nu)=q_{G_0}=\sum_{C_1\in{\mathcal Q}_1}(\mu(C_1)-\nu(C_1))_+=1-\sum_{C_1\in{\mathcal Q}_1}[\mu(C_1)\land\nu(C_1)]
=1-\sum_{C_1\in{\mathcal Q}_1} \rho_{C_1}
$$
as desired. If next \eqref{find} holds with some $n\in \{1,k-1\}$, we write
$$
\sum_{\ell=0}^{n} u_\ell(\mu,\nu)=1- \sum_{C_n \in {\mathcal Q}_n} \prod_{j=1}^n\rho_{f_j(C_n)}+
\sum_{C_n\in {\mathcal Q}_n} \Big(\prod_{j=1}^n\rho_{f_j(C_n)}\Big)q_{C_n}
=1- \sum_{C_{n+1} \in {\mathcal Q}_{n+1}} \prod_{j=1}^{n+1}\rho_{f_j(C_{n+1})},
$$
because, recalling \eqref{ano} and 
that  $\rho_{C_{n+1}}=\frac{\mu(C_{n+1})}{\mu(C_n)}\land\frac{\nu(C_{n+1})}{\nu(C_n)}$
(if $C_{n+1}$ is a child of $C_n$),
\begin{align*}
q_{C_n}=&\sum_{C_{n+1} \!\hbox{\tiny{ child of }}\! C_n}
\Big(\frac{\mu(C_{n+1})}{\mu(C_n)}-\frac{\nu(C_{n+1})}{\nu(C_n)} \Big)_+
=1 - \sum_{C_{n+1} \!\hbox{\tiny{ child of }}\! C_n} \rho_{C_{n+1}}.
\end{align*}

\vskip.2cm

{\it Step 6.} It only remains to verify \eqref{ul}. But for $\ell=1,\dots,k-1$, by definition \eqref{ano0}
of $q_{C_\ell}$ and 
since
$\prod_{j=1}^\ell\rho_{f_j(C_\ell)} \leq\mu(C_\ell)\land\nu(C_\ell)$,
$$
u_{\ell}(\mu,\nu)=\sum_{C_\ell\in {\mathcal Q}_\ell} \Big(\prod_{j=1}^\ell\rho_{f_j(C_\ell)}\Big)q_{C_\ell}\leq 
\frac12 \sum_{C_\ell\in {\mathcal Q}_\ell} (\mu(C_\ell)\land\nu(C_\ell)) \sum_{C_{\ell+1} \!\hbox{\tiny{ child of }}\! C_\ell}
\Big|\frac{\mu(C_{\ell+1})}{\mu(C_\ell)}-\frac{\nu(C_{\ell+1})}{\nu(C_\ell)} \Big|.
$$
Hence we have \eqref{ul} for any $\ell=1,\dots,k-1$. Next, since ${\mathcal Q}_0=\{G_0\}$
and $\mu,\nu$ are carried by $G_0$,
$$
u_0(\mu,\nu)=q_{C_0}=\frac12 \sum_{C_1\in {\mathcal Q}_1}|\mu(C_1)-\nu(C_1)|=\frac12\sum_{C_0\in{\mathcal Q}_0} (\mu(C_0)\land\nu(C_0))
\sum_{C_1\in {\mathcal Q}_1}\Big|\frac{\mu(C_1)}{\mu(C_0)}-\frac{\nu(C_1)}{\nu(C_0)}\Big|,
$$
whence \eqref{ul} with $\ell=0$.
\end{proof}


We next consider the non compact case.

\begin{lem}\label{l2}
For any $\mu,\nu \in {\mathcal P}({\mathbb{R}}^d)$, any $a>1$, any $p>0$,
\begin{align}\label{ccc}
{\mathcal T}_p(\mu,\nu)\leq \sum_{n\geq 0}a^{pn}\Big(2^p {\varepsilon}_p|\mu(G_n^a)-\nu(G_n^a)|
+(\mu(G_n^a)\land \nu(G_n^a)){\mathcal T}_p({\mathcal R}_n^a\mu,{\mathcal R}_n^a\nu)\Big),
\end{align}
where ${\mathcal R}_n^a\mu$ is the image measure of $\frac{\mu|_{G_n^a}}{\mu(G_n^a)}$ by the map
$x \mapsto a^{-n}x$.
\end{lem}



\begin{proof}
We fix $a>1$ and $p>0$ and consider, for each $n\geq 0$, the optimal coupling $\pi_n$
between ${\mathcal R}_{n}^a\mu$ and ${\mathcal R}_{n}^a\nu$ for ${\mathcal T}_p$. We define $\xi_n$
as the image of $\pi_n$ by the map $(x,y)\mapsto (a^nx,a^ny)$. It holds that $\xi_n$ belongs
to ${\mathcal H}(\mu\vert_{G_n^a}/\mu(G_n^a),\nu\vert_{G_n^a}/\nu(G_n^a))$
and satisfies 
\begin{align}\label{jab2}
\int_{{\mathbb{R}}^d\times{\mathbb{R}}^d} |x-y|^p \xi_n({\rm d} x,{\rm d} y) = a^{pn} \int_{{\mathbb{R}}^d\times{\mathbb{R}}^d} |x-y|^p \pi_n({\rm d} x,{\rm d} y)
=a^{pn} {\mathcal T}_p({\mathcal R}_{n}^a\mu,{\mathcal R}_{n}^a\nu).
\end{align}
Next, we introduce $q=\frac12 \sum_{n\geq 0} |\mu(G_n^a)-\nu(G_n^a)|$
and we define
\begin{align}\label{jab1}
\xi({\rm d} x,{\rm d} y)=\sum_{n\geq 0} (\mu(G_n^a)\land\nu(G_n^a))\xi_n({\rm d} x,{\rm d} y) + q\alpha({\rm d} x)\beta({\rm d} y),
\end{align}
where
$$
\alpha({\rm d} x)= \frac1q\sum_{n\geq 0}(\mu(G_n^a)-\nu(G_n^a))_+ \frac{\mu\vert_{G_n^a}({\rm d} x)}{\mu(G_n^a)} \quad \hbox{and} \quad
\beta({\rm d} y)= \frac1q\sum_{n\geq 0}(\nu(G_n^a)-\mu(G_n^a))_+ \frac{\nu\vert_{G_n^a}({\rm d} y)}{\nu(G_n^a)}.
$$
Using that $(G_n^a)_{n\geq 0}$ is a partition of ${\rr^d}$, that
$\xi_n\in{\mathcal H}(\mu\vert_{G_n^a}/\mu(G_n^a),\nu\vert_{G_n^a}/\nu(G_n^a))$ and that
$$
q=\sum_{n\geq 0}(\nu(G_n^a)-\mu(G_n^a))_+=\sum_{n\geq 0}(\mu(G_n^a)-\nu(G_n^a))_+
=1-\sum_{n\geq 0} (\nu(G_n^a)\land\mu(G_n^a)),
$$
it is easily checked that $\alpha$ and $\beta$ are probability measures and that $\xi \in {\mathcal H}(\mu,\nu)$.
Furthermore, setting $c_p=1\lor 2^{p-1}$,
\begin{align*}
\int_{{\mathbb{R}}^d\times{\mathbb{R}}^d} \!|x-y|^p \alpha({\rm d} x)\beta({\rm d} y)
\!\leq& c_p\int_{{\mathbb{R}}^d\times{\mathbb{R}}^d} \!(|x|^p +|y|^p)
\alpha({\rm d} x)\beta({\rm d} y)\!=c_p\!\int_{{\mathbb{R}}^d}\! |x|^p \alpha({\rm d} x) +  c_p \!\int_{{\mathbb{R}}^d}\! |y|^p \beta({\rm d} y).
\end{align*}
We have $|x|< a^n$ for all $x \in G_n^a$, whence
\begin{align}\label{jab3}
q\int_{{\mathbb{R}}^d\times{\mathbb{R}}^d}|x-y|^p \alpha({\rm d} x)\beta({\rm d} y)\leq & c_p
\sum_{n\geq 0} a^{pn} [(\mu(G_n^a)-\nu(G_n^a))_+ +(\nu(G_n^a)-\mu(G_n^a))_+ ] \notag\\
=& 2^p {\varepsilon}_p  \sum_{n\geq 0} a^{pn} |\mu(G_n^a)-\nu(G_n^a)|.
\end{align}
Using that ${\mathcal T}_p(\mu,\nu)\leq \int_{{\rr^d}\times{\rr^d}} |x-y|^p \xi({\rm d} x,{\rm d} y)$ 
and \eqref{jab1}-\eqref{jab2}-\eqref{jab3} 
completes the proof.
\end{proof}


We can now give the

\begin{proof}[Proof of Proposition \ref{depart}]
Fix $\mu$ and $\nu$ in ${\mathcal P}({\rr^d})$ and $a>1$.
For each $n\geq 0$, the probability measures ${\mathcal R}_n^a\mu$ and ${\mathcal R}_n^a\nu$, defined in Lemma \ref{l2}, 
are supported in $B(0,1)$,
and ${\mathcal R}_n^a\mu(C)=\frac{\mu(a^nC \cap G_n^a)}{\mu(G_n^a)}$ for all $C \in {\mathcal B}({\mathbb{R}}^d)$.
Hence we know from Lemma \ref{cc} that there exists some numbers $r_{a,n,\ell}(\mu,\nu)=u_\ell({\mathcal R}_n^a\mu,{\mathcal R}_n^a\nu)$
satisfying $\sum_{\ell=0}^{k-1} r_{a,n,\ell}(\mu,\nu)\leq 1$ and 
$$
r_{a,n,\ell}(\mu,\nu) \leq \frac12 \sum_{F\in {\mathcal Q}_\ell}
\Big(\frac{\mu(a^nF \cap G_n^a)}{\mu(G_n^a)} \land \frac{\nu(a^nF \cap G_n^a)}{\nu(G_n^a)} \Big)
\sum_{C\!\hbox{\tiny{ child of }}\! F} \Big|\frac{\mu(a^nC \cap G_n^a)}{\mu(a^nF\cap G_n^a)} 
- \frac{\nu(a^nC \cap G_n^a)}{\nu(a^nF\cap G_n^a)}\Big|
$$
and such that
$$
{\mathcal T}_p({\mathcal R}_n^a\mu,{\mathcal R}_n^a\nu) \leq  \delta_k^p+\sum_{\ell=0}^{k-1} \delta_\ell^p r_{a,n,\ell}(\mu,\nu).
$$
Inserting this into \eqref{ccc} completes the proof.
\end{proof}

\section{A general estimate concerning the empirical measure}\label{gume}

To go further, we need a more precise setting.

\begin{set}\label{ssm}
Same points (a) and (b) as in Setting \ref{sss}.
\vskip.2cm
(c) There are some constants $A,D>0$ and $r>1$ such that for each $k\geq 1$,
there is a family $({\mathcal Q}_{k,\ell})_{\ell=0,\dots,k}$ of nested partitions of $G_0$ such that ${\mathcal Q}_{k,0}=\{G_0\}$
and such that 
\begin{gather}\label{card}
\forall\; \ell=1,\dots,k,\qquad |{\mathcal Q}_{k,\ell}|\leq A \,r^{d\ell}
\end{gather}
and
\begin{gather}\label{card2}
\forall\; \ell=0,\dots,k,\qquad \delta_{k,\ell} = \max_{C \in {\mathcal Q}_{k,\ell}} \sup_{x,y \in C} |x-y| \leq D r^{-\ell}.
\end{gather}
\end{set}
Recall that ${\varepsilon}_p=2^{-1}\lor 2^{-p}$.
The goal of this section is to prove the following result.

\begin{prop}\label{ccco}
We adopt Setting \ref{ssm}, consider $\mu \in {\mathcal P}({\rr^d})$ and
the associated empirical measure $\mu_N$, see \eqref{muN}. 
Fix $p>0$ and assume that ${\mathcal M}_q(\mu)<\infty$ for some $q>p$.
For all $a>1$, all $N\geq 1$,
$$
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq K_{N}+\min\{L_{N},M_{N}\},
$$
where
\begin{align*}
K_{N}=&2^p{\varepsilon}_p \Big[\Big(2[1-\mu(G_0^a)]\Big)\land\sqrt{\frac{1-\mu(G_0^a)}{N}}\Big]
+ 2^p{\varepsilon}_p\sum_{n\geq 1} a^{pn} \Big[\Big(2\mu(G_n^a)\Big)\land \sqrt{\frac{\mu(G_n^a)}{N}}\Big],\\
L_{N}=& \frac{D^p\sqrt{Ar^d}}{2\sqrt N} \sum_{\ell\geq 0} r^{(d/2-p)\ell}
\sum_{n\geq 0} a^{pn}\sqrt{\mu(G_n^a)},\\
M_{N}=&D^p(1-r^{-p}) \sum_{n\geq 0} a^{pn}\sum_{\ell\geq 0} r^{-p\ell} \Big(\mu(G_n^a) 
\land \Big[\frac{\sqrt A r^{d\ell/2+d}}{2(r^{d/2} -1)}
\sqrt{\frac{\mu(G_n^a)}{N}}\Big] \Big).
\end{align*}
\end{prop}

We simply write $K_N,L_N,M_N$ for readability, but these quantities also depend on $p$, $a$ and $\mu$.

\begin{proof} 
We fix $\mu\in{\mathcal P}({\mathbb{R}}^d)$, $a>1$ and $p>0$.
We also fix $k\geq 1$; we will let $k\to \infty$ at the end of the proof.
Applying Proposition \ref{depart}, with the family $({\mathcal Q}_{k,\ell})_{\ell=0,\dots,k}$, 
with $\mu$ and $\nu=\mu_N$ and taking expectations, we find
\begin{align}\label{rr1}
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq U_{N,k}+V_{N,k}+W_{N,k}, 
\end{align}
where, setting 
$\rho_{k,a,n,\ell}=\mathbb{E}[(\mu(G_n^a)\land\mu_N(G_n^a))r_{k,a,n,\ell}(\mu,\mu_N)]$
(with $r_{k,a,n,\ell}(\mu,\mu_N)$ as defined in Proposition \ref{depart} with 
the family  $({\mathcal Q}_{k,\ell})_{\ell=0,\dots,k}$),
\begin{align}
U_{N,k}=&2^p{\varepsilon}_p \sum_{n\geq 0} a^{pn}\mathbb{E}[|\mu(G_n^a)-\mu_N(G_n^a)|],\notag\\
V_{N,k}=&\sum_{n\geq 0}a^{pn}\sum_{\ell= 0}^{k-1} \delta_{k,\ell}^p\rho_{k,a,n,\ell}\leq D^p
\sum_{n\geq 0}a^{pn}\sum_{\ell=0}^{k-1} r^{-p\ell}\rho_{k,a,n,\ell},\notag\\
W_{N,k}=& \delta_{k,k}^p\sum_{n\geq 0} a^{pn} \mu(G_n^a)\leq D^p r^{-pk} \sum_{n\geq 0} a^{pn}\mu(G_n^a). \label{rr2}
\end{align}
We used that $\delta_{k,\ell}\leq D r^{-\ell}$ for all $\ell\in\{0,\dots,k\}$, see \eqref{card2}.

\vskip.2cm

Since $N\mu_N(G_n^a)$ is Binomial$(N,\mu(G_n^a))$-distributed, it holds that $\mathbb{E}[\mu_N(G_n^a)]=\mu(G_n^a)$ and 
$\mathbb{V}{\rm ar}\, [\mu_N(G_n^a)]=N^{-1}\mu(G_n^a)(1-\mu(G_n^a))$, from which we  deduce that
$$
\mathbb{E}[|\mu(G_n^a)-\mu_N(G_n^a)|]\leq \Big(2[1-\mu(G_n^a)]\Big)\land \Big(2\mu(G_n^a)\Big)
\land \sqrt{\frac{\mu(G_n^a)(1-\mu(G_n^a))}{N}}.
$$
We used that $|x-y|=|(1-x)-(1-y)|\leq 1-x+1-y$ for all $x,y \in [0,1]$ for the first bound,
that $|x-y|\leq x+y$ for the second one, and the Bienaym\'e-Tchebychev inequality for the third one.
All this implies that for all $k\geq 1$,
\begin{align}\label{rr3}
U_{N,k}\leq K_{N}.
\end{align}

Next, we observe that $\sum_{\ell=0}^{k-1}\rho_{k,a,n,\ell} \leq \mu(G_n^a)$ by \eqref{rnl1} and we claim that
for $\ell=0,\dots,k-1$,
\begin{align}\label{tp}
\rho_{k,a,n,\ell} \leq \frac12\sqrt{\frac{|{\mathcal Q}_{k,\ell+1}|\mu(G_n^a)}{N}}.
\end{align}
Recalling \eqref{rnl2} and using that $(\mu(G_n^a)\land\mu_N(G_n^a))(\frac{\mu(a^nF\cap G_n^a)}{\mu(G_n^a)}\land
\frac{\mu_N(a^nF\cap G_n^a)}{\mu_N(G_n^a)}) \leq \mu_N(a^nF\cap G_n^a)$,
\begin{align}\label{tbi}
\rho_{k,a,n,\ell}\leq \frac12\sum_{F\in {\mathcal Q}_{k,\ell}} \hskip3pt\sum_{C \!\hbox{\tiny{ child of }}\! F}
\mathbb{E}\Big[\Big|\mu_N(a^nC \cap G_n^a)\!-\frac{\mu_N(a^nF \cap G_n^a)\mu(a^nC \cap G_n^a)}{\mu(a^nF \cap G_n^a)}\Big|\Big].
\end{align}
But for $C$ a child of $F$, the 
conditional law
of $N\mu_N(a^nC \cap G_n^a)$ knowing that $N\mu_N(a^nF \cap G_n^a)=i$ is Binomial$(i,\frac{\mu(a^nC \cap G_n^a)}
{\mu(a^nF \cap G_n^a)})$, whence
$$
\mathbb{E}\Big[\Big|\mu_N(a^nC \cap G_n^a)-\frac{\mu_N(a^nF \cap G_n^a)\mu(a^nC \cap G_n^a)}{\mu(a^nF \cap G_n^a)}\Big|
\hskip3pt\Big| N\mu_N(a^nF \cap G_n^a)=i\Big] \leq \sqrt{\frac i {N^2} 
\frac{\mu(a^nC \cap G_n^a)}{\mu(a^nF \cap G_n^a)}.}
$$
Hence, since $\mathbb{E}[\sqrt{N\mu_N(A)}]\leq \sqrt{N\mu(A)}$ because $\mathbb{E}[\mu_N(A)]=\mathbb{E}[\mu(A)]$,
\begin{align*}
\mathbb{E}\Big[\Big|\mu_N(a^nC \cap G_n^a)\!-\frac{\mu_N(a^nF \cap G_n^a)\mu(a^nC \cap G_n^a)}{\mu(a^nF \cap G_n^a)}\Big|
\Big] \!\leq& \sqrt{\frac{\mu(a^nC \cap G_n^a)}{N^2\mu(a^nF \cap G_n^a)}} \mathbb{E}\Big[ \sqrt{N\mu_N(a^nF \cap G_n^a)}\Big]\\
\leq &\sqrt{\frac{\mu(a^nC \cap G_n^a)}{N}}.
\end{align*}
This, inserted in \eqref{tbi}, proves the claim \eqref{tp}, since by the Cauchy-Schwarz inequality,
$$
\sum_{F\in {\mathcal Q}_{k,\ell}} \hskip3pt\sum_{C \!\hbox{\tiny{ child of }}\! F} \sqrt{\frac{\mu(a^nC \cap G_n^a)}{N}}
=\sum_{C \in {\mathcal Q}_{k,\ell+1}} \sqrt{\frac{\mu(a^nC \cap G_n^a)}{N}} \leq \sqrt{\frac{|{\mathcal Q}_{k,\ell+1}|\mu(G_n^a)}{N}}.
$$

We deduce from \eqref{tp} and \eqref{card} that
$$
\sum_{\ell=0}^{k-1} r^{-p\ell} \rho_{k,a,n,\ell}
\leq \frac12\sum_{\ell=0}^{k-1} r^{-p\ell}\sqrt{\frac{|{\mathcal Q}_{k,\ell+1}|\mu(G_n^a)}{N}}
\leq\! \frac{\sqrt {A\mu(G_n^a)}}{2\sqrt{N}} \sum_{\ell=0}^{k-1}r^{-p\ell}r^{d(\ell+1)/2}.
$$
Since $V_{N,k}\leq D^p\sum_{n\geq 0}a^{pn}\sum_{\ell=0}^{k-1}r^{-p\ell} \rho_{k,a,n,\ell}$, we conclude that 
for all $k\geq 1$,
\begin{align}\label{rr4}
V_{N,k} \leq 
D^p\sum_{n\geq 0}a^{pn} \frac{\sqrt {A\mu(G_n^a)}}{2\sqrt{N}} \sum_{\ell\geq0}r^{-p\ell}r^{d(\ell+1)/2}
=L_{N}
\end{align}

Next, we set $S_{k,a,n,\ell}=\sum_{i=0}^\ell \rho_{k,a,n,i}$ for $\ell=0,\dots,k-1$ and $S_{k,a,n,-1}=0$ to write
$$
\sum_{\ell=0}^{k-1} r^{-p\ell}\rho_{k,a,n,\ell}=
\sum_{\ell=0}^{k-1} r^{-p\ell}(S_{k,a,n,\ell}-S_{k,a,n,\ell-1})
=(1-r^{-p})\sum_{\ell=0}^{k-1}r^{-p\ell}S_{k,a,n,\ell}+r^{-pk}S_{k,a,n,k-1}.
$$
But for each $\ell=0,\dots,k-1$, we both have $S_{k,a,n,\ell} \leq \mu(G_n^a)$ 
(since $\sum_{\ell=0}^{k-1}\rho_{k,a,n,\ell} \leq \mu(G_n^a)$, as already seen) and, by \eqref{tp} and \eqref{card},
$$
S_{k,a,n,\ell} \leq \frac 12 \sum_{i=0}^\ell \sqrt{\frac{|{\mathcal Q}_{k,i+1}|\mu(G_n^a)}{N}}
\leq \frac{\sqrt{A \mu(G_n^a)}}{2\sqrt{N}} \sum_{i=0}^\ell r^{d(i+1)/2}\leq
\frac{\sqrt A r^{d\ell/2+d}}{2(r^{d/2} -1)}
\sqrt{\frac{\mu(G_n^a)}{N}}.
$$
Hence  
$$
\sum_{\ell=0}^{k-1} r^{-p\ell}\rho_{k,a,n,\ell}
\leq (1-r^{-p}) \sum_{\ell=0}^{k-1} r^{-p\ell} \Big(\mu(G_n^a) 
\land \Big[\frac{\sqrt A r^{d\ell/2+d}}{2(r^{d/2} -1)}
\sqrt{\frac{\mu(G_n^a)}{N}}\Big] \Big)+r^{-pk}\mu(G_n^a).
$$
Recalling that  $V_{N,k}\leq D^p\sum_{n\geq 0}a^{pn}\sum_{\ell=0}^{k-1}r^{-p\ell} \rho_{k,a,n,\ell}$, we
conclude that for all $k\geq 1$, it holds that
\begin{align}
V_{N,k} \leq & D^p\sum_{n\geq 0}a^{pn}(1-r^{-p}) \sum_{\ell \geq 0} r^{-p\ell} \Big(\mu(G_n^a) 
\land \Big[\frac{\sqrt A r^{d\ell/2+d}}{2(r^{d/2} -1)}
\sqrt{\frac{\mu(G_n^a)}{N}}\Big] \Big) + D^pr^{-pk}\sum_{n\geq 0} a^{pn}\mu(G_n^a)   \notag\\
=&M_{N} + D^pr^{-pk}\sum_{n\geq 0} a^{pn}\mu(G_n^a).\label{rr5}
\end{align}

Gathering \eqref{rr1}-\eqref{rr2}-\eqref{rr3}-\eqref{rr4}-\eqref{rr5}, we have proved that for all $k\geq 1$,
\begin{equation}\label{tti}
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq K_N+\min\Big\{L_N,M_N+ D^pr^{-pk}\sum_{n\geq 0} a^{pn}\mu(G_n^a)\Big\}
+ D^pr^{-pk}\sum_{n\geq 0} a^{pn}\mu(G_n^a).
\end{equation}
Since $\mu(G_n^a)\leq {\mathcal M}_q(\mu) a^{(1-n)q}$ for all $n\geq 1$
because $G_n^a \subset B(0,a^{n-1})^c$, and since $q>p$, we deduce that 
$\sum_{n\geq 0} a^{pn}\mu(G_n^a)<\infty$.
Letting $k\to \infty$ in \eqref{tti} thus completes the proof.
\end{proof}

Let us mention that the penultimate paragraph of this proof, where we handle a discrete integration
by parts, is crucial to obtain reasonable constants when $p\in(0,d/2)$.

\section{Precise study of some series}\label{series}

\begin{lem}\label{phi}
Fix $r>1$, $\beta\geq \alpha>0$ and $x \geq 0$ and put
$$
\Psi_{r,\alpha,\beta}(x)= \sum_{\ell \geq 0} r^{-\alpha \ell} [1 \land (x \;r^{\beta \ell})].
$$ 
With the notation $\log_+ x= (\log x)\lor 0$, it holds that
\begin{align}
\Psi_{r,\alpha,\beta}(x) \leq& \Big(\frac{\log_+ (1/x)}{\beta\log r} + \frac{1}{1-r^{-\alpha}}\Big)x
&\hbox{if $\beta=\alpha$,}\label{tt2}\\
\Psi_{r,\alpha,\beta}(x) \leq & 
\Big(\frac 1 {r^{\beta-\alpha}-1} + \frac 1{1-r^{-\alpha}} \Big) x^{\alpha/\beta}
 &\hbox{if $\beta>\alpha$.}\label{tt3}
\end{align}
\end{lem}

\begin{proof}
We fix $\alpha=\beta>0$ and prove \eqref{tt2}. 
If $x>1$, we write 
$$
\Psi_{r,\alpha,\beta}(x)\leq \sum_{\ell \geq 0} r^{-\alpha \ell}= \frac 1{1-r^{-\alpha}}\leq \frac x{1-r^{-\alpha}}.
$$
If $x\in [0,1]$, we set $t_x= \log (1/x) / (\beta \log r) \geq 0$, $\ell_x=\lfloor t_x \rfloor\in{\mathbb{N}}$ and 
$s_x=t_x-\ell_x\in [0,1)$ and write
$$
\Psi_{r,\alpha,\beta}(x)\leq \sum_{\ell=0}^{\ell_x} x + \sum_{\ell=\ell_x+1}^{\infty} r^{-\alpha\ell}
=x(\ell_x+1)+\frac{r^{-\alpha(\ell_x+1)}}{1-r^{-\alpha}}
= u+v,
$$
where $u=x t_x +x/(1-r^{-\alpha})$ is the  desired bound and where, since $x=r^{-\alpha t_x}$,
$$
v=x(\ell_x+1-t_x)+ \frac{r^{-\alpha(\ell_x+1)}-x}{1-r^{-\alpha}}=x
\Big[1-s_x + \frac{r^{-\alpha(1-s_x)}-1}{1-r^{-\alpha}}\Big].
$$
To show that $v\leq 0$, which will complete the proof of \eqref{tt2}, 
it suffices to prove that $g(u)=u+ \frac{r^{-\alpha u}-1}{1-r^{-\alpha}}$
is nonpositive for all $u\in[0,1]$. But
$g''(u)=\frac{(\alpha \log r)^2}{1-r^{-\alpha}}r^{-\alpha u}\geq 0$, so that
$g$ is convex, and $g(0)=g(1)=0$. The conclusion follows.

\vskip.2cm

We fix $\beta>\alpha>0$ and prove \eqref{tt3}.
If $x>1$, we write 
$$
\Psi_{r,\alpha,\beta}(x)\leq \sum_{\ell \geq 0} r^{-\alpha \ell}= \frac 1{1-r^{-\alpha}}\leq \frac {x^{\alpha/\beta}}{1-r^{-\alpha}}.
$$
If $x\in [0,1]$, we set $t_x= \log (1/x) / (\beta \log r)\geq 0$, $\ell_x=\lfloor t_x \rfloor\in{\mathbb{N}}$ and 
$s_x=t_x-\ell_x\in [0,1)$ and write
$$
\Psi_{r,\alpha,\beta}(x)\leq \sum_{\ell=0}^{\ell_x} x r^{(\beta-\alpha)\ell} + \sum_{\ell=\ell_x+1}^{\infty} r^{-\alpha\ell}
\leq x \frac{r^{(\beta-\alpha)(\ell_x+1)}}{r^{\beta-\alpha}-1}+\frac{r^{-\alpha(\ell_x+1)}}{1-r^{-\alpha}}
= u+v,
$$
where $u=x^{\alpha/\beta}/(r^{\beta-\alpha}-1)+x^{\alpha/\beta}/(1-r^{-\alpha})$ is the desired bound and where,
since $x=r^{-\beta t_x}$,
$$
v=\frac{x r^{(\beta-\alpha)(\ell_x+1)}-x^{\alpha/\beta}}{r^{\beta-\alpha}-1}+\frac{r^{-\alpha(\ell_x+1)}-x^{\alpha/\beta}}{1-r^{-\alpha}}
=x^{\alpha/\beta}\Big[\frac{r^{(\beta-\alpha)(1-s_x)}-1}{r^{\beta-\alpha}-1}+\frac{r^{-\alpha(1-s_x)}-1}{1-r^{-\alpha}} \Big].
$$
To show that $v\leq 0$, which will complete the proof of \eqref{tt3}, 
it suffices to show that $g(u)=\frac{r^{(\beta-\alpha)u}-1}{r^{\beta-\alpha}-1}+\frac{r^{-\alpha u}-1}{1-r^{-\alpha}}$
is nonpositive for all $u\in[0,1]$. But $g''(u)=\frac{((\beta-\alpha) \log r)^2}{r^{\beta-\alpha}-1}r^{(\beta-\alpha)u}
+\frac{(\alpha \log r)^2}{1-r^{-\alpha}}r^{-\alpha u} \geq 0$, so that
$g$ is convex, and it holds that $g(0)=g(1)=0$.
\end{proof}

\section{Theoretical result for a general norm}\label{titrenaze}

Recall that ${\varepsilon}_p=2^{-1}\lor 2^{-p}$ and that $H$ was defined in \eqref{H}. 
Here we prove the following general result,
to be applied to some specific norms later.

\begin{prop}\label{genen}
We adopt Setting \ref{ssm}, we fix $\mu \in {\mathcal P}({\rr^d})$ and consider the associated empirical 
measure $\mu_N$, see \eqref{muN}. We fix $q>p>0$ and assume that ${\mathcal M}_q(\mu)<\infty$.
\vskip.2cm
(i) If $p>d/2$ and $q>2p$, then for all $N\geq 1$,
$$
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq 2^p\frac{\kappa_{d,p}}{\sqrt N}[{\mathcal M}_q(\mu)]^{p/q}H\Big(\frac{{\varepsilon}_p}{\kappa_{d,p}},2p,q\Big),
$$
where
$$
\kappa_{d,p}=\frac{D^p\sqrt{A r^d}}{2^{p+1}(1-r^{d/2-p})}.
$$

(ii) If $p=d/2$ and $q>2p$, then for all $N\geq 1$,
$$
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq 2^p\frac{\kappa_{d,p,N}}{\sqrt N}[{\mathcal M}_q(\mu)]^{p/q}H\Big(\frac{{\varepsilon}_p}{\kappa_{d,p,N}},2p,q\Big),
$$
where
$$
\kappa_{d,p,N}=\frac{D^p\sqrt{A} r^{p}}{2^{p+1}p\log r}\log_+\Big(2(r^{-p}-r^{-2p})\sqrt{\frac N A}\Big) 
+\frac{D^p\sqrt{A} r^{2p}}{2^{p+1}(r^p-1)}.
$$

(iii) If $p\in (0,d/2)$ and $q>dp/(d-p)$, then for all $N\geq 1$,
$$
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq 2^p\frac{\kappa_{d,p}}{N^{p/d}}[{\mathcal M}_q(\mu)]^{p/q}
H\Big(\frac{2^{1-2p/d}{\varepsilon}_p}{\kappa_{d,p}},\frac{dp}{d-p},q\Big),
$$
where
$$
\kappa_{d,p}=\frac{D^pA^{p/d}r^{p}(r^{d/2}-1)^{1-2p/d}}{2^{p+2p/d}(r^{d/2-p}-1)}.
$$
\end{prop}

\begin{proof}
We fix $q>p>0$. We have $(G_0^a)^c \subset \{x \in {\rr^d} : |x|\geq 1\}$ and
$G_n^a \subset  \{x \in {\rr^d} : |x|\geq a^{n-1}\}$ for each $n\geq 1$, whence
\begin{equation}\label{mom}
1-\mu(G_0^a) \leq {\mathcal M}_q(\mu) \qquad \hbox{and}\qquad \mu(G_n^a) \leq {\mathcal M}_q(\mu)a^{-q(n-1)}\quad\hbox{if $n\geq 1$}.
\end{equation}
We know from Proposition \ref{ccco} that 
$\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)] \leq K_{N}+\min\{L_{N},M_{N}\}$.
\vskip.2cm
{\it Case (i): $p>d/2$ and $q>2p$.} First, by \eqref{mom}, we have
$$
K_{N}\leq 2^p{\varepsilon}_p\sqrt{\frac{{\mathcal M}_q(\mu)}{N}}+ 2^p{\varepsilon}_p\sum_{n\geq 1} a^{pn}\sqrt{\frac{{\mathcal M}_q(\mu)}{Na^{q(n-1)}}}
= 2^p{\varepsilon}_p \sqrt{\frac{{\mathcal M}_q(\mu)}N}\Big[1+\frac {a^p}{1-a^{p-q/2}}\Big].
$$
Next,
\begin{align*}
L_{N}\leq& \frac{D^p\sqrt{Ar^d}}{2\sqrt N} \sum_{\ell\geq 0}r^{(d/2-p)\ell}\Big( 1 + \sum_{n\geq 1}a^{pn}
\sqrt{\frac{{\mathcal M}_q(\mu)}{a^{q(n-1)}}}\Big)=2^p\frac{\kappa_{d,p}}{\sqrt N}
\Big(1+\sqrt{{\mathcal M}_q(\mu)} \frac {a^p}{1-a^{p-q/2}}\Big)
\end{align*}
recall that $\kappa_{d,p}=(D/2)^p\sqrt{Ar^d}/[2(1-r^{d/2-p})]$.
All in all, we have proved that
\begin{equation}\label{fri}
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq \frac{2^p}{\sqrt N} \Big(\kappa_{d,p}+\sqrt{{\mathcal M}_q(\mu)}\Big[{\varepsilon}_p+({\varepsilon}_p+\kappa_{d,p})
 \frac {a^p}{1-a^{p-q/2}}\Big] \Big).
\end{equation}
This holds true for any value of $a>1$ and we optimally choose
$a=[q/(2p)]^{2/(q-2p)}$ and set
$$
v_{p,q}=\frac{a^p}{1-a^{p-q/2}}=
\frac{q}{q-2p}\Big(\frac{q}{2p}\Big)^{2p/(q-2p)}.
$$
We thus have
$$
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq \frac{2^p}{\sqrt N} \Big(\kappa_{d,p}+\sqrt{{\mathcal M}_q(\mu)}
[{\varepsilon}_p+({\varepsilon}_p+\kappa_{d,p})v_{p,q}] \Big)
= \frac{2^p \kappa_{d,p}}{\sqrt N} \Big(1+\sqrt{{\mathcal M}_q(\mu)}\rho_{d,p,q}\Big),
$$
where $\rho_{d,p,q}={\varepsilon}_p/\kappa_{d,p}+({\varepsilon}_p+\kappa_{d,p})v_{p,q}/\kappa_{d,p}$. 
\vskip.2cm
For any $\alpha>0$, we may apply this formula to $\mu^\alpha$, the image measure of $\mu$
by the map $x \mapsto \alpha x$, which satisfies $\mathbb{E}[{\mathcal T}_p(\mu_N^\alpha,\mu^\alpha)]=\alpha^p\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]$
and ${\mathcal M}_q(\mu^\alpha)=\alpha^q {\mathcal M}_q(\mu)$. We thus get
$$
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq \frac{2^p \kappa_{d,p}}{\sqrt N} \frac{1}{\alpha^p}
\Big(1+\sqrt{\alpha^q{\mathcal M}_q(\mu)}\rho_{d,p,q}\Big).
$$
We optimally choose $\alpha=[(q-2p)\rho_{d,p,q}\sqrt{{\mathcal M}_q(\mu)}/(2p)]^{-2/q}$ and find
\begin{align*}
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq& \frac{2^p \kappa_{d,p}}{\sqrt N}
[{\mathcal M}_q(\mu)]^{p/q} \Big(\rho_{d,p,q} \frac{q-2p}{2p}\Big)^{2p/q} \frac{q}{q-2p}\\
=&\frac{2^p \kappa_{d,p}}{\sqrt N}[{\mathcal M}_q(\mu)]^{p/q} \Big(\frac{{\varepsilon}_p}{\kappa_{d,p}}\frac{q-2p}{2p}
+\frac{{\varepsilon}_p+\kappa_{d,p}}{\kappa_{d,p}}v_{p,q}\frac{q-2p}{2p}\Big)^{2p/q} \frac{q}{q-2p}\\
=&\frac{2^p \kappa_{d,p}}{\sqrt N}[{\mathcal M}_q(\mu)]^{p/q} \Big(\frac{{\varepsilon}_p}{\kappa_{d,p}}\frac{q-2p}{2p}
+\frac{{\varepsilon}_p+\kappa_{d,p}}{\kappa_{d,p}}\Big(\frac{q}{2p}\Big)^{q/(q-2p)}\Big)^{2p/q} \frac{q}{q-2p}\\
=&\frac{2^p \kappa_{d,p}}{\sqrt N}[{\mathcal M}_q(\mu)]^{p/q} H\Big(\frac{{\varepsilon}_p}{\kappa_{d,p}},2p,q\Big).
\end{align*}

{\it Case (ii): $p=d/2$ and $q>2p$.} Exactly as in Case (i),
$$
K_{N}\leq 2^p{\varepsilon}_p \sqrt{\frac{{\mathcal M}_q(\mu)}N}\Big[1+\frac {a^p}{1-a^{p-q/2}}\Big].
$$
We next write
\begin{align*}
M_{N}\leq&D^p(1-r^{-p})\sum_{n\geq 0}a^{pn} \mu(G^a_n)
\sum_{\ell\geq 0} r^{-p\ell} \Big(1\land\Big[\frac{\sqrt A r^{d\ell/2+d}}{2(r^{d/2}-1)}
\frac1{\sqrt{N\mu(G_n^a)}}\Big]\Big)\\
= &D^p(1-r^{-p})\sum_{n\geq 0}a^{pn} \mu(G^a_n)
\Psi_{r,p,d/2}\Big(\frac{\sqrt A r^{d}}{2(r^{d/2}-1)\sqrt{N\mu(G_n^a)}}\Big).
\end{align*}
By \eqref{tt2} with $\alpha=\beta=p=d/2$, we can
bound $M_N$ by
\begin{align*}
&D^p(1-r^{-p})\sum_{n\geq 0}a^{pn} \mu(G^a_n)\Big[
\frac{\log_+(2(r^{-d/2}-r^{-d})\sqrt{N\mu(G_n^a)/A})}{p\log r}+\frac1{1-r^{-p}}\Big]
\frac{\sqrt A r^{d}}{2(r^{d/2}-1)\sqrt{N\mu(G_n^a)}}\\
\leq & \frac{D^p\sqrt A r^{2p}}{2(r^{p}-1)\sqrt N}\Big[\frac{(1-r^{-p})\log_+(2(r^{-p}-r^{-2p})\sqrt{N/A})}{p\log r}
+1\Big]\sum_{n\geq 0}a^{pn} \sqrt{\mu(G^a_n)}
\end{align*}
since $\mu(G_n^a)\leq 1$. Observing that, by \eqref{mom},
$$
\sum_{n\geq 0}a^{pn} \sqrt{\mu(G^a_n)}\leq 1+\sum_{n\geq 1}a^{pn}\sqrt{\frac{{\mathcal M}_q(\mu)}{a^{q(n-1)}}}
= 1+\sqrt{{\mathcal M}_q(\mu)}
\frac{a^p}{1-a^{p-q/2}}, 
$$
and recalling that
$$
\kappa_{d,p,N}=\frac{(D/2)^p\sqrt A r^{p}\log_+(2(r^{-p}-r^{-2p})\sqrt{N/A})}{2p\log r}
+\frac{(D/2)^p\sqrt A r^{2p}}{2(r^p-1)},
$$
we conclude that
$$
M_N \leq 2^p \frac{\kappa_{d,p,N}}{\sqrt N}\Big(1+\sqrt{{\mathcal M}_q(\mu)}\frac{a^p}{1-a^{p-q/2}}\Big).
$$
All in all, we have proved that
$$
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq \frac{2^p}{\sqrt N}\Big(\kappa_{d,p,N}+\sqrt{{\mathcal M}_q(\mu)}\Big[{\varepsilon}_p+({\varepsilon}_p+\kappa_{d,p,N})
\frac{a^p}{1-a^{p-q/2}}\Big] \Big).
$$
From there we conclude exactly as in Case (i) (compare the above formula to \eqref{fri}) that
$$
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq 2^p\frac{\kappa_{d,p,N}}{\sqrt N}[{\mathcal M}_q(\mu)]^{p/q}H\Big(\frac{{\varepsilon}_p}{\kappa_{d,p,N}},2p,q\Big).
$$

{\it Case (iii): $p\in (0,d/2)$ and $q>dp/(d-p)$.} We write, using that $2p/d\in (0,1)$ and then \eqref{mom},
\begin{align*}
K_N \leq &2^p{\varepsilon}_p \Big[2(1-\mu(G_0^a))\Big]^{1-2p/d}\Big[\sqrt{\frac{1-\mu(G_0^a)}{N}}\Big]^{2p/d}+
2^p{\varepsilon}_p\sum_{n\geq 1}a^{pn} \Big[2\mu(G_n^a)\Big]^{1-2p/d}
\Big[\sqrt{\frac{\mu(G_n^a)}{N}}\Big]^{2p/d}\\
\leq& 2^p{\varepsilon}_p    \Big[2{\mathcal M}_q(\mu)\Big]^{1-2p/d}\Big[\sqrt{\frac{{\mathcal M}_q(\mu)}{N}}\Big]^{2p/d}
+2^p{\varepsilon}_p\sum_{n\geq 1}a^{pn} \Big[\frac{2{\mathcal M}_q(\mu)}{a^{q(n-1)}}\Big]^{1-2p/d}
\Big[\sqrt{\frac{{\mathcal M}_q(\mu)}{Na^{q(n-1)}}}\Big]^{2p/d}\\
= &2^p{\varepsilon}_p \frac{2^{1-2p/d}[{\mathcal M}_q(\mu)]^{1-p/d}}{N^{p/d}}
+2^p{\varepsilon}_p \frac{2^{1-2p/d}[{\mathcal M}_q(\mu)]^{1-p/d}}{N^{p/d}}
\sum_{n\geq 1}a^{pn-q(1-p/d)(n-1)}\\
= & 2^p{\varepsilon}_p \frac{2^{1-2p/d}[{\mathcal M}_q(\mu)]^{1-p/d}}{N^{p/d}} \Big(1+\frac{a^p}{1-a^{p-q+pq/d}}\Big).
\end{align*}
We used that $p-q+pq/d<0$ because $q>dp/(d-p)$. Next,
\begin{align*}
M_{N}\leq D^p(1-r^{-p})\sum_{n\geq 0}a^{pn} \mu(G^a_n)
\Psi_{r,p,d/2}\Big(\frac{\sqrt A r^{d}}{2(r^{d/2}-1)\sqrt{N\mu(G_n^a)}}\Big)
\end{align*}
as in Case (ii). Thus, using \eqref{tt3} with $\alpha=p$ and $\beta=d/2$,
\begin{align*}
M_N\leq & D^p(1-r^{-p})\Big[\frac1{r^{d/2-p}-1}+\frac1{1-r^{-p}}\Big]
\sum_{n\geq 0}a^{pn} \mu(G^a_n) \Big(\frac{\sqrt A r^{d}}{2(r^{d/2}-1)\sqrt{N\mu(G_n^a)}}\Big)^{2p/d}\\
=& 2^p \frac{\kappa_{d,p}}{N^{p/d}}\sum_{n\geq 0}a^{pn} [\mu(G^a_n)]^{1-p/d},
\end{align*}
because
\begin{align*}
\Big(\frac D2\Big)^p(1-r^{-p})\Big[\frac1{r^{d/2-p}-1}+\frac1{1-r^{-p}}\Big]
\Big(\frac{\sqrt A r^{d}}{2(r^{d/2}-1)}\Big)^{2p/d}=\frac{D^pA^{p/d}r^p(r^{d/2}-1)^{1-2p/d}}
{2^{p+2p/d}(r^{d/2-p}-1)}
=\kappa_{d,p}.
\end{align*}
But, using \eqref{mom},
$$
\sum_{n\geq 0}a^{pn} [\mu(G^a_n)]^{1-p/d} 
\leq  1+\sum_{n\geq 1} a^{pn}\Big[\frac{{\mathcal M}_q(\mu)}{a^{q(n-1)}}\Big]^{1-p/d}
= 1+ [{\mathcal M}_q(\mu)]^{1-p/d}\frac{a^p}{1-a^{p-q+pq/d}},
$$
whence
$$
M_N\leq 2^p \frac{\kappa_{d,p}}{N^{p/d}}\Big(1+ [{\mathcal M}_q(\mu)]^{1-p/d}\frac{a^p}{1-a^{p-q+pq/d}}\Big).
$$
All in all, we have
\begin{align*}
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq&
\frac{2^p}{N^{p/d}}\Big(\kappa_{d,p}+[{\mathcal M}_q(\mu)]^{1-p/d}\Big[2^{1-2p/d}{\varepsilon}_p+
(2^{1-2p/d}{\varepsilon}_p+\kappa_{d,p})\frac{a^p}{1-a^{p-q+pq/d}}\Big]\Big)\\
=&\frac{2^p}{N^{p/d}}\Big(\kappa_{d,p} + [{\mathcal M}_q(\mu)]^{p/\tau}\Big[2^{1-2p/d}{\varepsilon}_p+
(2^{1-2p/d}{\varepsilon}_p+\kappa_{d,p}) \frac{a^p}{1-a^{p-pq/\tau}} \Big]\Big),
\end{align*}
where we have set $\tau=dp/(d-p)$.
We choose $a=[q/\tau]^{\tau/(p(q-\tau))}>1$, for which
$$
v_{d,p,q}=\frac{a^p}{1-a^{p-pq/\tau}}=\frac{q}{q-\tau}\Big(\frac{q}\tau\Big)^{\tau/(q-\tau)}.
$$
Thus
\begin{align*}
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq &
\frac{2^p \kappa_{d,p}}{N^{p/d}}\Big(1
+[{\mathcal M}_q(\mu)]^{p/\tau}\Big[\frac{2^{1-2p/d}{\varepsilon}_p}{\kappa_{d,p}}
+ (2^{1-2p/d}{\varepsilon}_p+\kappa_{d,p})\frac{v_{d,p,q}}{\kappa_{d,p}}\Big]\Big)\\
=&\frac{2^p \kappa_{d,p}}{N^{p/d}}\Big(1
+[{\mathcal M}_q(\mu)]^{p/\tau}\rho_{d,p,q}\Big),
\end{align*} 
where $\rho_{d,p,q}\!=\!2^{1-2p/d}{\varepsilon}_p/\kappa_{d,p}+(2^{1-2p/d}{\varepsilon}_p+\kappa_{d,p})v_{d,p,q}/\kappa_{d,p}$.
As in Case (i), we deduce that
$$
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq \frac{2^p\kappa_{d,p}}{N^{p/d}}\frac1{\alpha^p}\Big(1
+ [\alpha^q {\mathcal M}_q(\mu)]^{p/\tau}\rho_{d,p,q}\Big)
$$
for all $\alpha>0$. 
With $\alpha=[\rho_{d,p,q}{\mathcal M}_q^{p/\tau}(q-\tau)/\tau]^{-\tau/(pq)} $, which is optimal,
we find
\begin{align*}
\mathbb{E}[{\mathcal T}_p(\mu_N,\mu)]\leq &\frac{2^p\kappa_{d,p}}{N^{p/d}}[{\mathcal M}_q(\mu)]^{p/q}
\Big(\rho_{d,p,q}\frac{q-\tau}{\tau}\Big)^{\tau/q}\frac{q}{q-\tau}\\
=&\frac{2^p\kappa_{d,p}}{N^{p/d}}[{\mathcal M}_q(\mu)]^{p/q}
\Big(\frac{2^{1-2p/d}{\varepsilon}_p}{\kappa_{d,p}}\frac{q-\tau}{\tau}
+\frac{2^{1-2p/d}{\varepsilon}_p+\kappa_{d,p}}{\kappa_{d,p}}v_{d,p,q}\frac{q-\tau}{\tau}\Big)^{\tau/q}\frac{q}{q-\tau}\\
=&\frac{2^p\kappa_{d,p}}{N^{p/d}}[{\mathcal M}_q(\mu)]^{p/q}
\Big(\frac{2^{1-2p/d}{\varepsilon}_p}{\kappa_{d,p}}\frac{q-\tau}{\tau}
+ \frac{2^{1-2p/d}{\varepsilon}_p
+\kappa_{d,p}}{\kappa_{d,p}}\Big(\frac q\tau\Big)^{q/(q-\tau)}\Big)^{\tau/q}\frac{q}{q-\tau}\\
=&\frac{2^p\kappa_{d,p}}{N^{p/d}}[{\mathcal M}_q(\mu)]^{p/q}H\Big(\frac{2^{1-2p/d}{\varepsilon}_p}{\kappa_{d,p}},\tau,q\Big)
\end{align*}
as desired.
\end{proof}

\section{Conclusion for the maximum norm}\label{concmax}

Here we consider the maximum norm $|\cdot|_\infty$. We claim that Setting \ref{ssm}-(c) holds
true with $A=1$, $D=2$ and $r=2$.
Indeed, consider, for each $\ell\geq 0$, the natural partition ${\mathcal Q}_\ell$ of $G_0=[-1,1]^d$ into 
$2^{d\ell}$ translations of $[-2^{-\ell},2^{-\ell}]^d$ (we actually have to remove some
of the common faces, but this is of course not an issue).
Then for any $k\geq 1$, $({\mathcal Q}_\ell)_{\ell=0,\dots,k}$ is a family of nested partitions of $G_0$,
we have $|{\mathcal Q}_\ell|=2^{d\ell} =Ar^{d\ell}$ for all $\ell=1,\dots,k$ and
$\delta_\ell=\max_{C \in {\mathcal Q}_\ell} \sup_{x,y\in C}|x-y|= 2\times 2^{-\ell}=Dr^{-\ell}$
for all $\ell =0,\dots, k$.

\vskip.2cm

We thus may apply Proposition \ref{genen} with these values $A=1$, $D=2$ and $r=2$. This gives Theorem
\ref{mr} (with the norm  $|\cdot|_\infty$) with the announced formulas, which we now check.

\vskip.2cm
If first $p>d/2$, we have
$$
\kappa_{d,p}^{(\infty)}=\frac{D^p\sqrt{A r^d}}{2^{p+1}(1-r^{d/2-p})}=\frac{2^{d/2-1}}{1-2^{d/2-p}}.
$$

If next $p=d/2$, we have
\begin{align*}
\kappa_{d,p,N}^{(\infty)}=&\frac{D^p\sqrt{A} r^p}{2^{p+1}p \log r}
\log_+\Big(2(r^{-p}-r^{-2p})\sqrt{\frac N A}\Big) 
+\frac{D^p\sqrt{A} r^{2p}}{2^{p+1}(r^p-1)}\\
=&\frac{2^{p-1}}{p\log 2} \log_+\Big((2^{1-p}-2^{1-2p})\sqrt N \Big)+ \frac{2^{p-1}}{1-2^{-p}}.
\end{align*}

If finally $p\in (0,d/2)$, we have
$$
\kappa_{d,p}^{(\infty)}=
\frac{D^pA^{p/d}r^p(r^{d/2}-1)^{1-2p/d}}{2^{p+2p/d}(r^{d/2-p}-1)}
=\frac{2^{p-2p/d}(1-2^{-d/2})^{1-2p/d}}{1-2^{p-d/2}}.
$$

\section{Conclusion for the Euclidean norm}\label{conceuc}

We now work with the Euclidean norm $|\cdot|_2$.
The following lemma is slight modification of Boissard-Le Gouic \cite[Lemma 2.1]{blg}
and Weed-Bach \cite[Proposition 3]{wb}.
Recall that $K_d$ was defined in \eqref{Kd} and 
that $B_2(x,r)=\{y\in{\rr^d} : |y-x|_2<r\}$.

\begin{lem}
For any $k\geq 1$, any $r>2$, there exists a family $({\mathcal Q}_{k,\ell})_{\ell=0,\dots,k}$
of nested partitions of $B_2(0,1)$ such that ${\mathcal Q}_{k,0}=\{B_2(0,1)\}$,
with $|{\mathcal Q}_{k,\ell}|\leq K_d (r-2)^{-d}r^d r^{d\ell}$ for all $\ell=1,\dots,k$ and
$\delta_{k,\ell}=\max_{C \in {\mathcal Q}_{k,\ell}} \sup_{x,y \in C} |x-y|_2 \leq 2 r^{-\ell}$ for all $\ell=0,\dots,k$.
\end{lem}

\begin{proof}
We fix $k\geq 1$ and $r>2$ and consider $\gamma\in (0,r)$ to be chosen later. 
By definition \eqref{Nr} of $N_r$, for each $\ell=1,\dots,k$,
there is a covering $(C_{k,\ell,i})_{i=1,\dots,N_{\gamma r^{-\ell}}}$ of $B_2(0,1)$ by balls
with radius $\gamma r^{-\ell}$ (observe that for each $\ell=1,\dots,k$, it holds that $\gamma r^{-\ell}<1$).

\vskip.2cm

We now define, by reverse induction on $\ell$, a family $({\mathcal Q}_{k,\ell})_{\ell=1,\dots,k}$ of nested partitions
of $B_2(0,1)$,
such that for all $\ell=1,\dots,k$, it holds that $|{\mathcal Q}_{k,\ell}|=N_{\gamma r^{-\ell}}$ and 
$$
\delta_{k,\ell}:=\max_{C \in {\mathcal Q}_{k,\ell}} \sup_{x,y \in C} |x-y|_2 \leq 2\gamma r^{-\ell}\sum_{i=0}^{k-\ell} (2/r)^i.
$$

We first define $F_{k,k,1}=C_{k,k,1}\cap B_2(0,1)$ and by induction, for every $i=2,\dots,N_{\gamma r^{-k}}$,
$F_{k,k,i}=(C_{k,k,i}\cap B_2(0,1))\setminus (\cup_{j=1}^{i-1}C_{k,k,j})$. Then
${\mathcal Q}_{k,k}=(F_{k,k,i})_{i=1,\dots,N_{\gamma r^{-k}}}$ is a partition of $B_2(0,1)$,
of which all the elements have a $|\cdot|_2$-diameter smaller 
than $2\gamma r^{-k}= 2\gamma r^{-k}\sum_{i=0}^{k-k}(2/r)^i$.

\vskip.2cm

We next assume that ${\mathcal Q}_{k,\ell+1}$ has been built, for some $\ell\in \{2,\cdots,k-1\}$, and we build ${\mathcal Q}_{k,\ell}$.
We first set, for $i=1,\dots,N_{\gamma r^{-\ell}}$ ,
$$
G_{k,\ell,i}=\bigcup_{j \in {\mathcal A}_{k,\ell,i}} F_{k,\ell+1,j},\quad \hbox{where}\quad
{\mathcal A}_{k,\ell,i}=\Big\{j\in \{1,\dots,N_{\gamma r^{-\ell-1}}\} : F_{k,\ell+1,j} \cap C_{k,\ell,i} \neq \emptyset\Big\}.
$$
Since the $|\cdot|_2$-diameter of $C_{k,\ell,i}$ equals $2\gamma r^{-\ell}$ and the $|\cdot|_2$-diameter of $F_{k,\ell+1,j}$
is smaller, for each $j$,  than $2\gamma r^{-\ell-1}\sum_{i=0}^{k-\ell-1} (2/r)^i$, we deduce 
that the $|\cdot|_2$-diameter of $G_{k,\ell,i}$ is smaller than
$$
2\gamma r^{-\ell}+4\gamma r^{-\ell-1}\sum_{i=0}^{k-\ell-1} (2/r)^i
=2 \gamma r^{-\ell}\Big( 1+ (2/r) \sum_{i=0}^{k-\ell-1} (2/r)^i\Big)
=2 \gamma r^{-\ell} \sum_{i=0}^{k-\ell} (2/r)^i.
$$
We then set $F_{k,\ell,1}=G_{k,\ell,1}$ and, by induction, for $i=2,\dots,N_{\gamma r^{-\ell}}$,
$F_{k,\ell,i}=G_{k,\ell,i}\setminus (\cup_{j=1}^{i-1}G_{k,\ell,j})$. Then ${\mathcal Q}_{k,\ell}=(F_{k,\ell,i})_{i=1,\dots,N_{\gamma r^{-\ell}}}$
is a partition of $B_2(0,1)$, composed of elements of which the $|\cdot|_2$-diameter is smaller
than $2\gamma r^{-\ell}\sum_{i=0}^{k-\ell} (2/r)^i$. Finally, each element
of ${\mathcal Q}_{k,\ell}$ is a union of elements of ${\mathcal Q}_{k,\ell+1}$, so that ${\mathcal Q}_{k,\ell+1}$ is a refinement
of ${\mathcal Q}_{k,\ell}$.

\vskip.2cm

We finally set ${\mathcal Q}_{k,0}=\{B_2(0,1)\}$. With the choice $\gamma=(r-2)/r$,
the family $({\mathcal Q}_{k,\ell})_{\ell=0,\dots,k}$ meets all the requirements of the statement.
Indeed, for each $\ell=1,\dots,k$, we have $|{\mathcal Q}_{k,\ell}|=
N_{\gamma r^{-\ell}} \leq K_d (\gamma r^{-\ell})^{-d}=K_d(r-2)^{-d}r^d r^{d\ell}$
by \eqref{Kd} and 
$\max_{C \in {\mathcal Q}_{k,\ell}} \sup_{x,y \in C} |x-y|_2 \leq 2\gamma r^{-\ell}\sum_{i=0}^{k-\ell} (2/r)^i
\leq 2 r^{-\ell}$. This also holds true with $\ell=0$ since
$\sup_{x,y \in B_2(0,1)} |x-y|_2=2$.
\end{proof}

Thus Setting \ref{ssm}-(c) holds with any $r>2$, with $A=K_d(r-2)^{-d}r^d$ and $B=2$, 
so that we may apply Proposition \ref{genen} with these values. Optimizing in $r>2$,
this gives Theorem
\ref{mr} (with the norm  $|\cdot|_2$) with the announced formulas, which we now check.

\vskip.2cm
If first $p>d/2$, we find $\kappa_{d,p}^{(2)}=\min\{\kappa_{d,p,r}^{(2)} : r>2\}$, where
$$
\kappa_{d,p,r}^{(2)}=\frac{D^p\sqrt{A r^d}}{2^{p+1}(1-r^{d/2-p})}=\frac{\sqrt{K_d}}{2}
\frac{r^{d}}{(r-2)^{d/2}(1-r^{d/2-p})}.
$$

If next $p=d/2$, we have $\kappa_{d,p,N}^{(2)}=\min\{\kappa_{d,p,N,r}^{(2)} : r>2\}$, where
\begin{align*}
\kappa_{d,p,N,r}^{(2)}=&\frac{D^p\sqrt{A} r^{p}}{2^{p+1}p\log r}
\log_+\Big(2(r^{-p}-r^{-2p})\sqrt{\frac N A}\Big) 
+\frac{D^p\sqrt{A} r^{2p}}{2^{p+1}(r^p-1)}\\
=&\frac{\sqrt{K_d}}2\frac{r^{2p}}{(r-2)^{p}p\log r}\log_+\Big(2(r-2)^{p}(r^{-2p}-r^{-3p})\sqrt{\frac N {K_d}}\Big)
+ \frac{\sqrt{K_d}}2 \frac{r^{3p}}{(r-2)^p(r^p-1)}.
\end{align*}

If finally $p\in (0,d/2)$, we have $\kappa_{d,p}^{(2)}=\min\{\kappa_{d,p,r}^{(2)} : r>2\}$, where
$$
\kappa_{d,p,r}^{(2)}=
\frac{D^pA^{p/d}r^p(r^{d/2}-1)^{1-2p/d}}{2^{p+2p/d}(r^{d/2-p}-1)}
=\Big(\frac{K_d}4\Big)^{p/d}\frac{r^{2p}(1-r^{-d/2})^{1-2p/d}}{(r-2)^p(1-r^{p-d/2})}.
$$



\section{The case of a low order finite moment}\label{lom}
We finally handle the case where $\mu$ has a low order moment.
We only treat the case of the maximum norm for simplicity.
We thus may apply Proposition \ref{ccco} with
$A=1$, $D=2$ and $r=2$, see the beginning of Section \ref{concmax}.
\vskip.2cm

\begin{proof}[Proof of Theorem \ref{mrn}]
We consider $p>0$, $q\in (p,\min\{2p,dp/(d-p)\})$, $\mu\in {\mathcal P}({\rr^d})$ and the associated empirical
measure $\mu_N$.
We know that $\mathbb{E}[{\mathcal T}_p^{(\infty)}(\mu_N,\mu)] \leq K_N+\min\{L_{N},M_N\}$
by Proposition \ref{ccco}, and we have 
\begin{equation}\label{mom2}
\mu(G_n^a) \leq {\mathcal M}_q^{(\infty)}(\mu)a^{-q(n-1)}\quad\hbox{if $n\geq 1$}.
\end{equation}
as usual. First,
\begin{align*}
K_N\leq & \frac{2^p{\varepsilon}_p}{\sqrt N} + 2^p{\varepsilon}_p\sum_{n\geq 1} a^{pn}\Big[\frac{2{\mathcal M}_q^{(\infty)}(\mu)}{a^{q(n-1)}}
\land \sqrt{\frac{{\mathcal M}_q^{(\infty)}(\mu)}{N a^{q(n-1)}}} \Big]\\
=& \frac{2^p{\varepsilon}_p}{\sqrt N}+ 2^p{\varepsilon}_pa^p  \sum_{n\geq 0} a^{(p-q)n}\Big[\Big(2{\mathcal M}_q^{(\infty)}(\mu)\Big)
\land \Big(\sqrt{\frac{{\mathcal M}_q^{(\infty)}(\mu)}{N}} a^{qn/2}\Big) \Big]\\
=& \frac{2^p{\varepsilon}_p}{\sqrt N}+2^{p+1}{\varepsilon}_p{\mathcal M}_q^{(\infty)}(\mu) a^p   
\Psi_{a,q-p,q/2}\Big(\frac 1{2\sqrt{N{\mathcal M}_q^{(\infty)}(\mu)}}\Big).
\end{align*}
Since $q/2>q-p$ because $q<2p$, we may apply \eqref{tt3} with $r=a$, with $\alpha=q-p$ and $\beta=q/2$:
\begin{align*}
K_N\leq & \frac{2^p{\varepsilon}_p}{\sqrt N}+ 2^{p+1}{\varepsilon}_p{\mathcal M}_q^{(\infty)}(\mu) a^p\Big[\frac1{a^{p-q/2}-1}+\frac1{1-a^{p-q}}\Big]
\Big(\frac 1{2\sqrt{N{\mathcal M}_q^{(\infty)}(\mu)}}\Big)^{2(q-p)/q}\\
=&\frac{2^p{\varepsilon}_p}{\sqrt N} + 2^p{\varepsilon}_p \rho_a [{\mathcal M}_q^{(\infty)}(\mu)]^{p/q}\frac{2^{2p/q-1}}{N^{(q-p)/q}},
\end{align*}
where $\rho_a=a^p[1/(a^{p-q/2}-1)+1/(1-a^{p-q})]$. Next, recalling that $A=1$, $D=2$ and $r=2$,
\begin{align*}
M_N\leq& 2^p(1-2^{-p})\sum_{n\geq 0}a^{pn}\sum_{\ell\geq 0}2^{-p\ell}  \Big[\mu(G_n^a)\land 
\Big(\frac{2^{d-1}2^{d\ell/2}}{2^{d/2}-1}\sqrt{\frac{\mu(G_n^a)}{N}} \Big)\Big]\leq M_{N,1}+M_{N,2},
\end{align*}
where we separate the cases $n=0$ and $n\geq 1$, i.e.
$$
M_{N,1}=2^p(1-2^{-p})\sum_{\ell\geq 0}2^{-p\ell}  \Big[1\land
\Big(\frac{2^{d-1}2^{d\ell/2}}{2^{d/2}-1}\sqrt{\frac{1}{N}} \Big)\Big]
\leq 2^p(1-2^{-p})\sum_{\ell\geq 0}2^{-p\ell} = 2^p,
$$
and
\begin{align*}
M_{N,2}=& 2^p(1-2^{-p})\sum_{n\geq 1}a^{pn}\sum_{\ell\geq 0}2^{-p\ell}  \Big[\frac{{\mathcal M}_q^{(\infty)}(\mu)}{a^{q(n-1)}}\land 
\Big(\frac{2^{d-1}2^{d\ell/2}}{2^{d/2}-1}\sqrt{\frac{{\mathcal M}_q^{(\infty)}(\mu)}{Na^{q(n-1)}}} \Big)\Big]\\
=&2^p(1-2^{-p})a^p\sum_{\ell\geq 0}  2^{-p\ell} \sum_{n\geq 0}a^{pn} \Big[\frac{{\mathcal M}_q^{(\infty)}(\mu)}{a^{qn}}\land 
\Big(\frac{2^{d-1}2^{d \ell/2}}{2^{d/2}-1}\sqrt{\frac{{\mathcal M}_q^{(\infty)}(\mu)}{Na^{qn}}}  \Big)\Big]\\
=&2^p(1-2^{-p})a^p\sum_{\ell\geq 0}  2^{-p\ell} \sum_{n\geq 0}a^{(p-q)n} \Big[{\mathcal M}_q^{(\infty)}(\mu)\land 
\Big(\frac{2^{d-1}2^{d \ell/2}}{2^{d/2}-1}\sqrt{\frac{{\mathcal M}_q^{(\infty)}(\mu)}{N}}a^{qn/2}  \Big)\Big]\\
=&2^p(1-2^{-p})a^p{\mathcal M}_q^{(\infty)}(\mu)\sum_{\ell\geq 0}  2^{-p\ell}\Psi_{a,q-p,q/2}
\Big(\frac{2^{d-1}2^{d\ell/2}}{(2^{d/2}-1)\sqrt{N{\mathcal M}_q^{(\infty)}(\mu)}}\Big).
\end{align*}
By \eqref{tt3} with $r=a$, $\alpha=q-p$ and $\beta=q/2$, recalling that
$\rho_a=a^p[1/(a^{p-q/2}-1)+1/(1-a^{p-q})]$,
\begin{align*}
M_{N,2}\leq & 2^p(1-2^{-p}){\mathcal M}_q^{(\infty)}(\mu)\rho_a \sum_{\ell\geq 0} 2^{-p\ell} 
\Big(\frac{2^{d-1}2^{d\ell/2}}{(2^{d/2}-1)\sqrt{N{\mathcal M}_q^{(\infty)}(\mu)}} \Big)^{2(q-p)/q}\\
=& 2^p\rho_a\frac{[{\mathcal M}_q^{(\infty)}(\mu)]^{p/q}}{N^{(q-p)/q}} 
\Big(\frac{2^{d-1}}{2^{d/2}-1}\Big)^{2(q-p)/q}\frac{1-2^{-p}}{1-2^{d-p-dp/q}},
\end{align*}
observe that $d-p-dp/q<0$ because $q<dp/(d-p)$. All in all, we conclude that
$$
\mathbb{E}[{\mathcal T}_p^{(\infty)}(\mu_N,\mu)] \leq 2^p\Big(\frac{{\varepsilon}_p}{{\sqrt N}}+1+
\rho_a\frac{[{\mathcal M}_q^{(\infty)}(\mu)]^{p/q}}{N^{(q-p)/q}}
\Big[{\varepsilon}_p 2^{2p/q-1} +\Big(\frac{2^{d-1}}{2^{d/2}-1}\Big)^{2(q-p)/q}\frac{1-2^{-p}}{1-2^{d-p-dp/q}}\Big] \Big).
$$
For any $\alpha>0$, we may apply this above formula to $\mu^\alpha$, the image measure of $\mu$
by the map $x \mapsto \alpha x$, for which
$\mathbb{E}[{\mathcal T}_p^{(\infty)}(\mu_N^\alpha,\mu^\alpha)]=\alpha^p\mathbb{E}[{\mathcal T}_p^{(\infty)}(\mu_N,\mu)]$
and ${\mathcal M}_q^{(\infty)}(\mu^\alpha)=\alpha^q {\mathcal M}_q^{(\infty)}(\mu)$. We get
$$
\mathbb{E}[{\mathcal T}_p^{(\infty)}(\mu_N,\mu)]\! \leq \frac{2^p}{\alpha^p}\Big(\frac{{\varepsilon}_p}{{\sqrt N}}+1+
\rho_a\frac{[\alpha^q {\mathcal M}_q^{(\infty)}(\mu)]^{p/q}}{N^{(q-p)/q}}
\Big[{\varepsilon}_p 2^{2p/q-1} \!+\Big(\frac{2^{d-1}}{2^{d/2}-1}\Big)^{2(q-p)/q}\hskip-4pt\frac{1-2^{-p}}{1-2^{d-p-dp/q}}\Big] \Big).
$$
Letting $\alpha \to \infty$, we find
$$
\mathbb{E}[{\mathcal T}_p^{(\infty)}(\mu_N,\mu)]\leq 2^p \frac{[{\mathcal M}_q^{(\infty)}(\mu)]^{p/q}}{N^{(q-p)/q}}
\rho_a
\Big[{\varepsilon}_p 2^{2p/q-1} +\Big(\frac{2^{d-1}}{2^{d/2}-1}\Big)^{2(q-p)/q}\frac{1-2^{-p}}{1-2^{d-p-dp/q}}\Big] \Big).
$$
Since $\rho_a=a^p/(a^{p-q/2}-1)+a^p/(1-a^{p-q})$ 
and since this result holds for any $a \in (1,\infty)$, the proof is complete.
\end{proof}



