$U_{1}\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\mathtt{b}}}}N_{1}$ or (ii)
$U_{2}\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\mathtt{b}}}}N_{2}$.
Consider (i). Necessarily,
$U_{1}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}N_{1}$ (because
$U_{1}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}N_{1}$
would imply $U_{1}U_{2}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}N_{1}N_{2}$
by Def. 4.1) and therefore by _i.h._ $N_{1}$ is not $\mathtt{b}$-normal, and
neither is $N=N_{1}N_{2}$. Similarly for (ii).

    * –

The other cases are similar (and simpler).

See 4.3

######  Proof B.8.

  1. 1.

This is Lemma B.2.

  2. 2.

Since ${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}\subseteq\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\mathtt{b}}}}$,
every $\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\mathtt{b}}}}$-normal form
is ${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}$-normal.
Conversely, if $M$ is ${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}$-normal,
then $M$ is ${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\,$}\vss}}}}}$-normal and a
straightforward induction on $M$ shows that $M$ is
$\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\mathtt{b}}}}$-normal.

  3. 3.

Proof 1: By Thm. B.4,
$M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}U{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N$. Since $N$ is
$\mathtt{b}$-normal, by Lemma B.6 $P=N$.

Proof 2: By induction on the shape of $N$, using $\mathsf{s}$-factorization.

The fact that
$\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}}}}$ is a
normalizing strategy (Thm. 4.4) follows from Prop. 4.3, because
$\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}}}}$ is complete
w.r.t. normal forms, and it is RD-diamond (and hence uniformly normalizing).

###  B.1 A parallel variant of unbiased reduction.

Given $(\Lambda,\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\mathtt{b}}}})$
and ${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\,$}\vss}}}}}$ as in Def. 4.1,
a parallel version ${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}$ is easily defined. The idea here
is that once a term is
${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\,$}\vss}}}}}$-normal,
iteration of the reduction process can be performed in any arbitrary order, or
in _parallel_. Recall that here
$(\mathtt{b},\mathsf{s})\in\\{(\beta,\mathsf{h}),(\beta_{v},\mathsf{w})\\}$.

  1. 1.

If $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\,$}\vss}}}}}{}M^{\prime}$
then $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}M^{\prime}$ ($M$ is not
$\mathsf{s}$-normal);

  2. 2.

If $M\not\rightarrow$ then
$M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}M$ ($M$ is $\xrightarrow{}$-normal);

  3. 3.

Otherwise:
$M\coloneqq\lambda x.P{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}\lambda
x.P^{\prime}P{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}P^{\prime}\qquad M\coloneqq
P_{1}P_{2}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}P_{1}^{\prime}P_{2}^{\prime}\lx@proof@logical@and
P_{1}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}P_{1}^{\prime}P_{2}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}P_{2}^{\prime}\qquad
M\coloneqq\mathbf{o}(P_{1},\dots,P_{k}){\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}\mathbf{o}(P_{1}^{\prime},\dots,P_{k}^{\prime})(P_{i}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}P_{i}^{\prime})_{1\leq i\leq k}$

Rule 2. makes the relation reflexive on normal forms and _only_ on normal
forms—this is a harmless shortcut in order to give a compact and neat
formulation.

The (multistep) reduction
${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}$ is guaranteed to reach the
$\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\mathtt{b}}}}$-_nf_ , if any
exists.

######  Lemma B.9.

Let $\mathtt{b}\in\\{\beta,\beta_{v}\\}$

  1. 1.

If $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}\ N$ then
$M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N$.
Therefore, $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}\ N$ implies
$M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N$.

  2. 2.

If $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N$
then there exists $N^{\prime}$ such that
$M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N^{\prime}$ and
$N{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N^{\prime}$.

######  Proof B.10.

  1. 1.

Easy induction on $M$.

  2. 2.

By induction on $N$, using $\mathsf{s}$-factorization and the fact that non-
surface steps preserve the shape of terms. By the former
$M\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}}^{*}U\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}}^{*}N$.
By the latter, $U$ has the same shape as $N$; we then examine the possible
cases, and conclude by _i.h._.

     * •

$N=\lambda x.N_{0}$ and $U=\lambda x.U_{0}$. By definition of
$\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}}}}$,
$U_{0}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{0}$,
and we conclude by _i.h._.

     * •

$N=N_{1}N_{2}$ and $U=U_{1}U_{2}$. It holds
$U_{1}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{1}$
and $U_{2}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{2}$.
By _i.h._ , for $i\in\\{1,2\\}$
$U_{i}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{i}^{\prime}$ and
$N_{i}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{i}^{\prime}$.
We now extend the two ${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}$-sequences so that they have the
same length (recall that
${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}$ is reflexive on
$\mathtt{b}$-_nf_), obtaining
$U_{i}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{i}^{\prime}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{i}^{\prime\prime}$ . We then
can conclude that
$U_{1}U_{2}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{1}^{\prime}N_{2}^{\prime}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{1}^{\prime\prime}N_{2}^{\prime\prime}$.

By using point 1., we also have
$N_{i}^{\prime}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{i}^{\prime\prime}$,
and so $U_{1}U_{2}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N_{i}^{\prime\prime}N_{2}^{\prime\prime}$.
Hence the claim.

######  Corollary 6 ($\mathcal{N}$-completeness).

Let $\mathtt{b}\in\\{\beta,\beta_{v}\\}$ and $N$ be
$\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\mathtt{b}}}}$-normal.
$M\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\mathtt{b}}}}^{*}N$ if and only
if $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}^{*}N$.

##  Appendix C Proofs of Sect. 5.1: Asymptotic Normalization for
$\Lambda_{\oplus}^{\mathtt{cbv}}$

Notice also that the definition of the reductions
$\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}},\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}$ can be given in the same way also in CbN, by replacing $\beta_{v}$
with $\beta$ (surface steps are here head steps).

#### Properties.

We freely use the following fact.

######  Fact 7.

$[M]\Rightarrow_{\beta_{v}}[M^{\prime}]\quad\text{ iff }\quad
M\mathrel{\rightarrow{}_{\mkern-6.0mu\beta_{v}}}^{=}{M^{\prime}}$ , where

  * •

on the l.h.s. we have $(\mathcal{M}(\Lambda_{\oplus}),\Rightarrow)$, and

  * •

on the r.h.s. the CbV $\lambda$-calculus
$(\Lambda_{\oplus},\mathrel{\rightarrow_{\beta_{v}}})$, as defined in Sect.
4.1.

#### Factorization and Neutrality.

Recall that $\mathcal{S}$ denotes the set of the surface normal forms of
$\rightarrow\,=\,(\mathrel{\rightarrow_{\beta_{v}}}\cup\rightarrow_{\oplus})$.
$M\in\Lambda_{\oplus}$ is $\mathsf{s}$-normal if
$M\not\\!{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\,$}\vss}}}}}$. That is
$M\not\rightarrow_{\oplus}$ and
$M\not\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}}$.

######  Lemma C.1 (snf propagation).

If $M$ is $\mathsf{s}$-normal and $M\rightarrow M^{\prime}$, then $M^{\prime}$
is $\mathsf{s}$-normal.

######  Proof C.2.

If $M$ is $\mathsf{s}$-normal and $M\rightarrow M^{\prime}$, then
$M\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}}M^{\prime}$.
By Lemma A.1, $M^{\prime}$ is $\mathsf{s}$-normal.

######  Proposition 8 (e-Factorization of $\Rightarrow$.).

In $\Lambda_{\oplus}^{\mathtt{cbv}}$: $\mathtt{m}\Rightarrow^{*}\mathtt{n}$
implies $\mathtt{m}\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}^{*}\cdot\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{e}\leavevmode\nobreak\
$}\vss}}}^{*}\mathtt{n}$

######  Proof C.3.

In the proof, we use freely 7. By surface factorization of $\Rightarrow$
(proved in [16]), $\mathtt{m}\Rightarrow^{*}\mathtt{n}\mbox{ implies
}\mathtt{m}\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\leavevmode\nobreak\
$}\vss}}}^{*}\mathtt{t}\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\leavevmode\nobreak\
$}\vss}}}^{*}\mathtt{n}$ for some $\mathtt{t}$. From this we have:

  * •

$\mathtt{m}\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}^{*}\mathtt{t}$. Because if
$M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\,$}\vss}}}}}\ \mathtt{r}$
then also $M\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}\ \mathtt{r}$.

  * •

$\mathtt{t}\mathrel{{\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}$}\vss}}}}{}_{\mkern-5.0mu\
\beta_{v}}}^{*}\mathtt{n}$. Because if
$M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\,$}\vss}}}}}\ \mathtt{r}$
then necessarily $M{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}}\mathtt{r}$.
Moreover, $\mathtt{r}=[M^{\prime}]$.

Let $\mathtt{t}=[\dots p_{i}T_{i}\dots]_{{i\in I}}$. Then necessarily,
$\mathtt{n}=[\dots p_{i}N_{i}\dots]_{{i\in I}}$ and
$[T_{i}]\mathrel{\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\leavevmode\nobreak\
$}\vss}}}{}_{\mkern-6.0mu\beta_{v}}}^{*}[N_{i}]$ and so also
${T_{i}}\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}}^{*}{N_{i}}$.
For each $T_{i}$, we examine if $T_{i}$ is $\mathsf{s}$-normal or not
($\mathcal{S}$ being the set of snf’s).

  1. 1.

$T_{i}\in\mathcal{S}$. By
${T_{i}}\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}}^{*}{N_{i}}$
and u-factorization of $\mathrel{\rightarrow_{\beta_{v}}}$ (Thm. B.4),
${T_{i}}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}^{*}U_{i}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}^{*}{N_{i}}$. By Lemma C.1, each term
in the sequence
${T_{i}}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}^{*}U_{i}{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}^{*}{N_{i}}$ is $\mathsf{s}$-normal.
Hence, by Def. 5.1 (since only the second rule can apply), we conclude that
$[T_{i}]\mathrel{\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}^{*}[U_{i}]\mathrel{\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{e}\leavevmode\nobreak\
$}\vss}}}{}_{\mkern-6.0mu\beta_{v}}}^{*}[N_{i}]$.

  2. 2.

$T_{i}\not\in\mathcal{S}$. By Lemma A.1, each term in the sequence
${T_{i}}\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}}^{*}{N_{i}}$
is not $\mathsf{s}$-normal. By definition of
$\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}$ (since only the first rule can apply) we conclude that
$[T_{i}]\mathrel{\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{e}\leavevmode\nobreak\
$}\vss}}}{}_{\mkern-6.0mu\beta_{v}}}^{*}[N_{i}]$.

Let us partition $\mathtt{t}$ into two multi-distributions, collecting in
$\mathtt{t}_{1}$ the terms of case 1. and in $\mathtt{t}_{2}$ the terms of
case 2. We partition $\mathtt{n}$ so that
$\mathtt{t}_{1}\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\leavevmode\nobreak\
$}\vss}}}^{*}\mathtt{n}_{1}$ and
$\mathtt{t}_{2}\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\leavevmode\nobreak\
$}\vss}}}^{*}\mathtt{n}_{2}$. We have
$\mathtt{t}_{1}\mathrel{\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}^{*}\mathtt{u}\mathrel{\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{e}\leavevmode\nobreak\
$}\vss}}}{}_{\mkern-6.0mu\beta_{v}}}^{*}\mathtt{n}_{1}$ and
$\mathtt{t}_{2}\mathrel{\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{e}\leavevmode\nobreak\
$}\vss}}}{}_{\mkern-6.0mu\beta_{v}}}^{*}\mathtt{n}_{2}$. Therefore
$\mathtt{m}\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}^{*}(\mathtt{t}_{1}+\mathtt{t}_{2})\mathrel{\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}}^{*}(\mathtt{u}+\mathtt{t}_{2})\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{e}\leavevmode\nobreak\
$}\vss}}}^{*}(\mathtt{n}_{1}+\mathtt{n}_{2})=\mathtt{n}.$ which proves the
claim.

######  Proposition 9 (neutrality).

If $\mathtt{m}\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{e}\leavevmode\nobreak\
$}\vss}}}\mathtt{n}$ then
$\mathtt{obs}_{\mathcal{N}}(\mathtt{m})=\mathtt{obs}_{\mathcal{N}}(\mathtt{n})$.

######  Proof C.4.

Consequence of the fact that if
$U{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}N$, then $N$ is not
$\beta_{v}$-normal Lemma B.6. Indeed
$\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{e}\leavevmode\nobreak\
\leavevmode\nobreak\
$}\vss}}}\subseteq{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\mathsf{s}\,$}\vss}}}}}$ and so
$M\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{e}\leavevmode\nobreak\
\leavevmode\nobreak\ $}\vss}}}\mathtt{r}$ _iff_ (
$M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}M^{\prime}$ with
$\mathtt{r}=[M^{\prime}]$).

#### Diamonds.

Prop. 5 (the relation $\mathrel{\mathop{\rightrightarrows}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
\leavevmode\nobreak\ $}\vss}}}$ is $\mathtt{obs}_{\mathcal{N}}$-diamond)
follows from the following key lemma. Notice that Point (2.) implies that
$\mathtt{obs}_{\mathcal{N}}(\mathtt{m}_{1})=\mathtt{obs}_{\mathcal{N}}(\mathtt{m}_{2})$.

######  Lemma C.5 (Pointed Diamond).

Let $\alpha,\gamma\in\\{\beta_{v},\oplus\\}$. Assume $M$ has two distinct
redexes, such that $M\mathrel{\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}{}_{\mkern-6.0mu\alpha}}\mathtt{m}_{1}$ and
$M\mathrel{\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}{}_{\mkern-6.0mu\gamma}}\mathtt{m}_{2}$. Then

  1. 1.

exists $\mathtt{t}$ such that
$\mathtt{m}_{1}\mathrel{\mathop{\rightrightarrows}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
\leavevmode\nobreak\ $}\vss}}}{}_{\gamma}\ \mathtt{t}$ and
$\mathtt{m}_{2}\mathrel{\mathop{\rightrightarrows}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
\leavevmode\nobreak\ $}\vss}}}{}_{\alpha}\ \mathtt{t}$.

  2. 2.

Moreover, no $M_{i}$ in $\mathtt{m}_{1}=[p_{i}M_{i}]_{i}$ and no $M_{j}$ in
$\mathtt{m}_{2}=[q_{j}M_{j}]_{j}$ is $\rightarrow$normal.

######  Proof C.6.

  * •

If $M$ is $\mathsf{s}$-normal, then by definition of
$\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}$, $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}\mathtt{m}_{1}$
and $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}\mathtt{m}_{2}$,
and we conclude by using 7 and Prop. 4.3, point 1.

  * •

If $M$ is $\mathsf{s}$-reducible, then by definition of
$\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}$, $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}\mathtt{m}_{1}$
and $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\mathsf{s}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}\mathtt{m}_{2}$.
We easily conclude by case analysis.

######  Remark C.7 ($\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}\ \not=\ {\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\mathtt{b}}}}}\cup\rightarrow_{\oplus}$).

It is useful to notice that $\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}\ \not=\ {\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}\cup\rightarrow_{\oplus}$.
Such a relation is neither diamond nor confluent.

  * •

The lifting of ${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}\cup\rightarrow_{\oplus}$
is neither diamond nor confluent. Consider $(\Delta\oplus\Delta\Delta)(\lambda
z.Iz)$. Then $\mathtt{m}_{1}=[\frac{1}{2}\Delta(\lambda
z.Iz),\frac{1}{2}(\Delta\Delta){(\lambda
z.\underline{Iz})}]\mathrel{{\mathrel{\mathop{\leftarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle$}\vss}}}}{}_{\mkern-3.0mu\oplus}}(\Delta\oplus\Delta\Delta)(\lambda
z.Iz){\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}[(\Delta\oplus\Delta\Delta)(\lambda
z.z)]=\mathtt{m}_{2}$. The elements $\mathtt{m}_{1}$ and $\mathtt{m}_{2}$
cannot join, because no
${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta_{v}}}}}$-step
can fire the underlined $(Iz)$.

  * •

Similarly in CbN, for the lifting of
${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta}}}}\cup\rightarrow_{\oplus}$.
Consider $(\Delta\oplus\Delta\Delta)(x(Iz))$.

######  Remark C.8.

Notice that the problem in Remark C.7 does not happen. Indeed
$M=(\Delta\oplus\Delta\Delta)(\lambda
z.Iz)\not\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}[(\Delta\oplus\Delta\Delta)(\lambda z.z)]$ because $M$ is not
$\mathsf{s}$-normal.

##  Appendix D Details for Sect. 6: more case studies

###  D.1 Asymptotic Normalization for a calculus with outputs

##### Proof of Lemma 6.1.

The $\mathsf{w}$-factorization of $\rightarrow$ is proved in [18], where it is
called surface factorization, and proved in general for all CbV monadic
calculi, including the payoff calculus which we discuss here.
$\mathtt{obs}$-neutrality is straightforward to verify, by case analysis.

###  D.2 Asymptotic Normalization and Böhm Trees

We show that the Böhm Tree of a term $M$ is the (unique) limit of an
asymptotically normalizing strategy, _i.e._ the limit of a _single_ reduction
sequence.

#### Böhm Trees and Partial Normal Forms

Following [3], the Böhm Tree of a term $M$ is (the downward closure of) the
set of the partial normal forms of all reducts of $M$.

######  Definition D.1 (Partial Normal Forms and Böhm Trees ).

The set $\mathcal{N}_{\omega}$ of partial normal forms is defined as follows;

$\Omega\in\mathcal{N}_{\omega}\qquad\lambda x_{1}\dots x_{n}.xA_{1}\dots
A_{n}\in\mathcal{N}_{\omega}A_{1}\in\mathcal{N}_{\omega}\ \dots\
A_{n}\in\mathcal{N}_{\omega}$

$\mathcal{N}_{\omega}$ is a subset of the set of partial $\lambda$-terms,
defined by $P:=\Omega\mid x\mid PP\mid\lambda x.P$, and inherits its order
$\leq$, which is generated by the following rules:

$\Omega\leq P\qquad P_{1}P_{2}\leq
P^{\prime}_{1}P^{\prime}_{2}\lx@proof@logical@and P_{1}\leq
P^{\prime}_{1}P_{2}\leq P^{\prime}_{2}\qquad\lambda x.P\leq\lambda
x.P^{\prime}P\leq P^{\prime}$

The elements of the ideal completion $\mathcal{N}_{\omega}^{\infty}$ of
$\mathcal{N}_{\omega}$ are called Böhm Trees. Precisely:

  1. 1.

The function $\omega:\Lambda\rightarrow\mathcal{N}_{\omega}$ associates to
each term $M\in\Lambda$ its _partial normal form_ $\omega(M)$:

$\omega(M)=\left\\{\begin{array}[]{ll}\Omega&\mbox{ if }M\not\in\mathcal{H}\\\
\lambda\vec{x}.x\omega(M_{1})\dots\omega(M_{p})&\mbox{ if
}M=\lambda\vec{x}.xM_{1}...M_{p}\end{array}\right.$

  2. 2.

The Böhm Tree of $M$ is defined as below For a set $\mathcal{S}$,
$\downarrow\mathcal{S}=\\{Q\in\mathcal{N}_{\omega}\mid Q\leq
S\in\mathcal{S}\\}$.

$\mathtt{BT(M)}:=\bigcup\limits_{M\rightarrow^{*}N}\downarrow\\{\omega(N)\\}=\downarrow\\{\omega(N)\mid
M\rightarrow^{*}N\\}$

The following property is standard and easy-to-check (see [3, Lemma 2.3.2].)

######  Lemma D.2.

Let $M,M^{\prime}\in\Lambda$. If
$M\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\beta}}}M^{\prime}$ then
$\omega(M)\leq\omega(M^{\prime})$.

Lemma D.2 guarantees that
$((\Lambda,\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\beta}}}),\mathtt{obs})$
is a QARS where
$\mathtt{obs}\colon\Lambda\xrightarrow{}\mathcal{N}_{\omega}^{\infty}$ is
defined as $\mathtt{obs}(M)=\downarrow\\{\omega(M)\\}$.

#### Asymptotic Normalization.

Let us define
$\mathtt{obs}:\Lambda\xrightarrow{}\mathcal{N}_{\omega}^{\infty}$ as
$\mathtt{obs}(M)=\downarrow\\{\omega(M)\\}$. It is easily checked that
$\big{(}(\Lambda,\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\beta}}}),\mathtt{obs}\big{)}$
is a QARS. We show that the Böhm Tree of a term $M$ can be obtained by
asymptotic normalization, as the limit a
${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\beta}}}}$ reduction sequence, which is an
$\mathtt{obs}$-normalizing strategy for
$\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\beta}}}$ (LABEL:thm:mainBT).

The $\mathtt{obs}$-limit of a reduction sequence $\langle M_{n}\rangle_{n}$ is
then
$\sup_{i}\\{\mathtt{obs}(M_{i})\\}=\bigcup_{i}\downarrow\\{\omega(M_{i})\\}$.
$\mathtt{BT(M)}$ is clearly the sup of the set
$\mathtt{Lim}_{\mathtt{obs}}{(M,\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\beta}}})}$.
We show that $\mathtt{BT(M)}$ _belongs_ to that set, by proving that
$\mathtt{Lim}_{\mathtt{obs}}{(M,\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\beta}}})}$
has a greatest element $\llbracket{M}\rrbracket$; this necessarily is
$\mathtt{BT(M)}$.

We first show that ${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta}}}}$
is $\mathtt{obs}$-complete for
$\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\beta}}}$ (Point 1 in
LABEL:prop:Oasymptotic_BT below). Reduction
${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}{}_{\mkern-6.0mu{\beta}}}}$
is not $\mathtt{obs}$-normalizing for
$\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\beta}}}$ (for example, it
admits the sequence
$x(\Delta\Delta)(Iz)\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}}}}x(\Delta\Delta)(Iz)\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}}}}\dots$) but its
parallel version ${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}}}$ (Sect. B.1) is.

We proceed similarly to Sect. 5.1 (think
$\mathrel{\mathop{\Rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
$}\vss}}}$ vs $\mathrel{\mathop{\rightrightarrows}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{e}\leavevmode\nobreak\
\leavevmode\nobreak\ $}\vss}}}$). We consider the reduction
${\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{//u}\leavevmode\nobreak\
\,$}\vss}}}}}$ (the explicit definition is in Sect. B.1) which has
$\mathtt{obs}$-Random Descent (trivially) and is asymptotically complete for
$\mathrel{{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\textsc{u}\,$}\vss}}}}}}$ (Point 2 in
LABEL:prop:Oasymptotic_BT below), and so for
$\mathrel{\mathrel{\rightarrow{}_{\mkern-6.0mu\beta}}}$.

######  Lemma D.3.

If $M{\mathrel{\,\mathrel{\mathop{\rightarrow}\limits_{\vbox
to0.0pt{\kern-6.0pt\hbox{$\scriptstyle\neg\textsc{u}\leavevmode\nobreak\
\,$}\vss}}}{}_{\mkern-6.0mu{\beta}}}}M^{\prime}$ then
$\omega(M)=\omega(M^{\prime})$.


# Quantitative estimate of the overdamped limit for the Vlasov–Fokker–Planck
systems

Hui Huang  Department of Mathematics and Statistics, University of Calgary,
Calgary, Canada<EMAIL_ADDRESS>
###### Abstract.

This note adapts a probabilistic approach to establish a quantified estimate
of the overdamped limit for the Vlasov–Fokker–Planck equation towards the
aggregation-diffusion equation, which in particular includes cases of the
Newtonian type singular forces. The proofs are based on the investigation of
the weak convergence of the corresponding stochastic differential equations
(SDEs) of Mckean type in the continuous path space. We show that one can
obtain the same convergence rate as in [choi2020quantified] under the same
assumptions.

H. H. is partially supported by the Pacific Institute for the Mathematical
Sciences (PIMS) postdoc fellowship.

Keywords: Overdamped, large friction, zero inertia, tightness.

##  1\. Introduction

The present note is concerning with the following kinetic Vlasov-Fokker-Planck
(VFP) equation

$\partial_{t}f^{\gamma}_{t}+\gamma
v\cdot\nabla_{x}f^{\gamma}_{t}+\gamma\nabla_{v}\cdot(F(x,\rho^{\gamma}_{t})f^{\gamma}_{t})=\gamma^{2}\nabla_{v}\cdot(\nabla_{v}f^{\gamma}_{t}+vf^{\gamma}_{t}),\quad
f^{\gamma}|_{t=0}=f_{0}\,,$ (1.1)

in dimension $d\geq 1$, where $(f^{\gamma}_{t})_{t\geq
0}\subset\mathcal{P}(\mathbb{R}^{d}\times\mathbb{R}^{d})$ is a family of
probability measures on $\mathbb{R}^{d}\times\mathbb{R}^{d}$ and $\gamma>0$ is
the damping coefficient. Here
$\rho^{\gamma}_{t}=\int_{\mathbb{R}^{d}}f^{\gamma}_{t}(\cdot,dv)\in\mathcal{P}(\mathbb{R}^{d})$
represents the spacial distribution, namely the $x$-marginal of
$f^{\gamma}_{t}$. In the sequel we may abuse the notations for a measure and
its Lebesgue density for simplicity. Moreover, we assume the driving force $F$
is arising from an external potential $\Phi:\mathbb{R}^{d}\to\mathbb{R}$
and/or interaction potential $K:\mathbb{R}^{d}\to\mathbb{R}$, which is of the
following from

$F(x,\rho)=-\nabla\Phi(x)-(\nabla K\ast\rho)(x)\quad\mbox{for
}(x,\rho)\in\mathbb{R}^{d}\times\mathcal{P}(\mathbb{R}^{d})\,,$ (1.2)

where

$(\nabla K\ast\rho)(x):=\int_{\mathbb{R}^{d}}\nabla K(x-y)\rho(dy)\,.$ (1.3)

It is well-known that the VFP equation (1.1) can be derived from a system of
large number of particles interacting through the force field $F$, which
satisfies the following system of stochastic differential equations

$\displaystyle\begin{cases}dX_{t}^{i,\gamma}=\gamma V_{t}^{i,\gamma}dt,\\\
dV_{t}^{i,\gamma}=-\gamma\nabla\Phi(X_{t}^{i,\gamma})dt-\frac{\gamma}{N}\sum_{j\neq
i}\nabla
K(X_{t}^{i,\gamma}-X_{t}^{j,\gamma})dt-\gamma^{2}V_{t}^{i,\gamma}+\sqrt{2}\gamma
dB_{t}^{i},\quad i=1,\cdots,N\,,\end{cases}$ (1.4)

where $X_{t}^{i,\gamma},~{}V_{t}^{i,\gamma}\in\mathbb{R}^{d}$ denote the
position and velocity of the $i$-th particle at time $t$, and
$\\{(B_{t}^{i})_{t\geq 0}\\}_{i=1}^{N}$ are $N$ independent $d$-dimensional
Brownian motions. Here we assume the initial data
$\\{(X_{0}^{i,\gamma},V_{0}^{i,\gamma})\\}_{i=1}^{N}$ are i.i.d. with the
common distribution $f_{0}$. Model (1.1) and its microscopic counterpart (1.4)
have been widely used in the investigation of complex systems that model
collective behaviour (or swarming), an area that has attracted a great deal of
attention, see for instance [carrillo2010asymptotic, bellomo2011modeling,
ha2008particle, cucker2007emergent, motsch2014heterophilious] and references
therein. Note that equation (1.1) also includes the classical
Vlasov–Poisson–Fokker–Planck system when $\nabla K=a\frac{x}{|x|^{d}}$, $d\geq
3$. The case $a>0$ corresponds, for example, to the electrostatic (repulsive)
interaction of charged particles in a plasma, while the case $a<0$ describes
the attraction between massive particles subject to gravitation in
astrophysics.

Under suitable assumption on $\Phi$ and $K$, as $N\to\infty$, the mean-field
limit result, see for example [bolley2011stochastic, huang2020mean,
carrillo2019propagation, sznitman1991topics, jabin2017mean,
lazarovici2017mean, fetecau2019propagation, liu2019propagation], shall show
that the particle dynamics (1.4) well approximates the following mean-field
nonlinear Mckean process

$\displaystyle dX_{t}^{\gamma}=\gamma V_{t}^{\gamma}dt,$ (1.5a) $\displaystyle
dV_{t}^{\gamma}=-\gamma^{2}V_{t}^{\gamma}dt+\gamma
F(X_{t}^{\gamma},\rho_{t}^{\gamma})dt+\sqrt{2}\gamma dB_{t}\,,$ (1.5b)

where the initial data $(X_{0},V_{0})$ is the same as in (1.4). Here
$\rho^{\gamma}_{t}=\mbox{Law}(X^{\gamma}_{t})$, the $x$-marginal of
$f^{\gamma}_{t}=\mbox{Law}(X_{t}^{\gamma},V_{t}^{\gamma})$, which makes the
set of equations (1.5) nonlinear. A direct application of Itô’s formula, the
law $f_{t}^{\gamma}:=f^{\gamma}(t,\cdot,\cdot)$ at time $t$ is a weak solution
to the following with the initial data
$f^{\gamma}_{0}(x,v)=\mbox{Law}(X_{0},V_{0})$.

In this note, we are interested in the VFP equation (1.1) in the overdamped
regime, namely in the regime where $\gamma\gg 1$. When $\gamma\to\infty$, it
is expected that the kinetic equation (1.1) will converge to the following so-
called aggregation-diffusion equation

$\partial_{t}\rho_{t}+\nabla_{x}\cdot(\rho_{t}F(x,\rho_{t}))=\Delta_{x}\rho_{t},\quad\rho|_{t=0}=\rho_{0}\,.$
(1.6)

Equation of the type (1.6) appears in various contexts, such as biological
aggregations [topaz2006nonlocal], material science and granular media
[toscani2000one], self-assembly of nanoparticles [holm2005aggregation] and
molecular dynamics simulations of matter [haile1993molecular]. The most noble
example is the case when $\Delta K=\delta_{0}$, which is corresponding to the
Keller–Segel model for chemotaxis [keller1970initiation]. Similar to (1.5), we
have the underlying nonlinear Mckean process satisfying

$\displaystyle X_{t}=X_{0}+\int_{0}^{t}F(X_{s},\rho_{s})ds+\sqrt{2}B_{t}$
(1.7)

with $\rho_{t}=\mbox{Law}(X_{t})$, and it satisfies the aggregation-diffusion
equation (1.6). Since the well-posedness of equations (1.1) and (1.6), and
nonlinear processes (1.5) and (1.7) are not the focus of the present note, we
refer readers to, for instance [bouchut1993existence, sznitman1991topics,
bolley2011stochastic, carrillo2019aggregation, godinho2015propagation], for
more discussions on the topic of solvability.

In the absence of the interaction potential, i.e. $K=0$, the overdamped limit
was first formally discussed in [kramers1940brownian] by Kramers through
introducing a coarse-graining map. Since then, more related results have been
proven by using stochastic and asymptotic techniques [freidlin2004some,
hottovy2012noise], or variational methods [duong2018quantification]. In the
presence of the interaction potential $K$, a variational technique was
proposed in [duong2017variational] without obtaining the convergence rate.
Most recently the authors in [choi2020quantified] obtained a quantified
overdamped limit in 2-Wasserstein distance for the VFP equation with nonlocal
forces. In the absence of diffusion, similar problems were also investigated
in [carrillo2020quantitative, jabin2000macroscopic, fetecau2015first] via
large friction limit. Especially in [carrillo2020quantitative], the authors
obtained a quantitative convergence rate, and it was extended to the case with
diffusion in [carrillo2021large]. In the present note we will use a different
alternative approach to obtain the quantified overdamped limit under the same
assumptions as in [choi2020quantified]. Instead of looking into the PDEs (1.1)
and (1.6) directly, we will investigate their underlying Mckean processes
(1.5) and (1.7) in the continuous path space. This is less technical than the
methods of PDE analysis and is more intuitive in way, and hopefully more
accessible to non-specialists. Such method has been used in [hui2021] to
obtain the consensus based optimization from the particle swarm optimization
with the limit of zero inertia.

Outline of the proof. Let us first solve $V_{t}^{\gamma}$ from (1.5b) and
obtain that

$V_{t}^{\gamma}=e^{-\gamma^{2}t}V_{0}+\gamma\int_{0}^{t}e^{-\gamma^{2}(t-s)}F(X_{s}^{\gamma},\rho_{s}^{\gamma})ds+\sqrt{2}\gamma\int_{0}^{t}e^{-\gamma^{2}(t-s)}dB_{s}\,,$
(1.8)

which implies that

$\displaystyle X_{t}^{\gamma}$
$\displaystyle=X_{0}+\gamma\int_{0}^{t}V_{\tau}^{\gamma}d\tau=X_{0}+\gamma\int_{0}^{t}e^{-\gamma^{2}\tau}V_{0}d\tau+\gamma^{2}\int_{0}^{t}\int_{0}^{\tau}e^{-\gamma^{2}(\tau-s)}F(X_{s}^{\gamma},\rho_{s}^{\gamma})dsd\tau$
$\displaystyle\quad+\sqrt{2}\gamma^{2}\int_{0}^{t}\int_{0}^{\tau}e^{-\gamma^{2}(\tau-s)}dB_{s}d\tau$
$\displaystyle=X_{0}+\frac{1}{\gamma}(1-e^{-\gamma^{2}t})V_{0}+\int_{0}^{t}(1-e^{-\gamma^{2}(t-s)})F(X_{s}^{\gamma},\rho_{s}^{\gamma})ds+\sqrt{2}\int_{0}^{t}(1-e^{-\gamma^{2}(t-s)})dB_{s}\,.$
(1.9)

Then $X^{\gamma}_{t}$ has the law $\rho^{\gamma}_{t}$ for each $t\geq 0$.
Denote by $\mathcal{C}([0,T];\mathbb{R}^{d})$ the space of all
$\mathbb{R}^{d}$-valued continuous functions on $[0,T]$ equipped with the
usual uniform norm. Each continuous stochastic process $X^{\gamma}$ may be
seen as a $\mathcal{C}([0,T];\mathbb{R}^{d})$-valued random function and it
induces a probability measure (or law, denoted by $\rho^{\gamma}$) on
$\mathcal{C}([0,T];\mathbb{R}^{d})$. We shall use the weak convergence in the
space of probability measures on $\mathcal{C}([0,T];\mathbb{R}^{d})$. We first
use Aldous’s tightness criteria to prove the tightness of the process
$\\{X^{\gamma}\\}_{\gamma>0}$. This means that there exist a convergent
subsequence of $\\{X^{\gamma}\\}_{\gamma>0}$, which will be still denoted by
$\\{X^{\gamma}\\}_{\gamma>0}$, such that for some process $\widehat{X}$ it
holds $X^{\gamma}\rightharpoonup\widehat{X}$ in the sense of distribution.
Next we verify that the limit process $\widehat{X}$ indeed satisfies (1.7)
which is the underlying Mckean process of (1.6). Furthermore we can obtain the
quantified convergence rate by comparing (1) and (1.7) directly, which reads

$\displaystyle\sup_{t\in[0,T]}W_{2}^{2}(\rho^{\gamma}_{t},\rho_{t})\leq\sup_{t\in[0,T]}\mathbb{E}[|X^{\gamma}_{t}-X_{t}|^{2}]\leq
C\frac{1}{\gamma^{2}}\,.$ (1.10)

See Theorem 2.3.

For readers’ convenience, we give a brief introduction of the Wasserstein
metric in the following definition, we refer to [ambrosio2008gradient] for
more details. Let $1\leq p<\infty$ and $\mathcal{P}_{p}(\mathbb{R}^{d})$ be
the space of Borel probability measures on $\mathbb{R}^{d}$ with finite
$p$-moment. We equip this space with the Wasserstein distance

$W_{p}^{p}(\mu,\nu):=\inf\left\\{\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}|z-\widehat{z}|^{p}\
d\pi(\mu,\nu)\ \big{|}\ \pi\in\Pi(\mu,\nu)\right\\}$ (1.11)

where $\Pi(\mu,\nu)$ denotes the collection of all Borel probability measures
on $\mathbb{R}^{d}\times\mathbb{R}^{d}$ with marginals $\mu$ and $\nu$ in the
first and second component respectively. The Wasserstein distance can also be
expressed as

$W_{p}^{p}(\mu,\nu)=\inf\left\\{\mathbb{E}[|Z-\overline{Z}|^{p}]\right\\}\,,$
(1.12)

where the infimum is taken over all joint distributions of the random
variables $Z$, $\overline{Z}$ with marginals $\mu$, $\nu$ respectively. Thanks
to the Kantorovich duality, in the space $\mathcal{P}_{1}(\mathbb{R}^{d})$, we
shall also use the following alternative representation

$W_{1}(\mu,\nu)=\sup\left\\{\big{|}\int_{\mathbb{R}^{d}}\phi(x)\mathrm{d}(\mu-\nu)(x)\big{|}:~{}\phi\in\mbox{Lip}(\mathbb{R}^{d}),~{}\|\phi\|_{\text{Lip
}}\leq 1\right\\}\,,$ (1.13)

where $\mbox{Lip}(\mathbb{R}^{d})$ is the space of Lipschitz continuous
functions on $\mathbb{R}^{d}$ and $\|\phi\|_{\text{Lip }}:=\sup_{x\neq
y}\frac{|\phi(x)-\phi(y)|}{|x-y|}$.

Throughout this paper we assume the external potential function $\Phi$
satisfies

######  Assumption 1.

The external potential function $0\leq\Phi\in\mbox{Lip}_{loc}(\mathbb{R}^{d})$

  * 1.

There exists some constant $C_{\Phi}>0$ such that

$|\nabla\Phi(x)|\leq C_{\Phi}(1+|x|)\quad\mbox{ for all
}x\in\mathbb{R}^{d},\quad\mbox{ and
}\left\lVert\nabla\Phi\,\right\rVert_{\mbox{Lip}}\leq C_{\Phi}\,;$ (1.14)

  * 2.

For any $r\in[0,\infty)$:
$C_{\Phi,r}:=\sup_{x\in\mathbb{R}^{d}}|\nabla\Phi(x)|^{r}e^{-\Phi(x)}<\infty$
.

Note that the above assumption allows us to consider both bounded and
unbounded external potentials with at most quadratic growth at infinity, in
particular the case $\Phi(x)=|x|^{2}/2$.

As for the interaction potential $K$, we will consider both regular and
singular cases. We start with assuming $\nabla K\in
L^{\infty}(\mathbb{R}^{d})\cap\mbox{Lip}(\mathbb{R}^{d})$ in Section 2. Then
in Section 3, we assume that the potential $K\in L_{loc}^{q}(\mathbb{R}^{d})$
is singular, which in particular includes the case
$|K(x)|\leq\frac{C}{|x|^{\alpha}}$ with $1\leq\alpha<d-2$, and the Newtonian
potential case $\nabla K(x)=\pm\frac{x}{|x|^{d}}$. In the singular case we
need higher-order regularity of solutions $f^{\gamma}$. Firstly we need
$f^{\gamma}$ to be more than just a measure but a density function. Secondly,
we require some uniform in $\gamma$ estimates of $f^{\gamma}$ in weighted
Sobolev space $W_{x,H}^{k,p}$, which will be collected from
[choi2020quantified].

##  2\. Regular interaction potential

In this section we consider globally Lipschitz continuous and bounded
interaction forces by assuming $\nabla K\in
L^{\infty}(\mathbb{R}^{d})\cap\mbox{Lip}(\mathbb{R}^{d})$. Denote by

$C_{K}:=\left\lVert\nabla K\,\right\rVert_{L^{\infty}}+\left\lVert\nabla
K\,\right\rVert_{\mbox{Lip}}<\infty\,.$

Then one can easily verify that

  1. (1)

For any $\mu\in\mathcal{P}(\mathbb{R}^{d})$, it holds

$\left\lVert\nabla K\ast\mu\,\right\rVert_{L^{\infty}}\leq\left\lVert\nabla
K\,\right\rVert_{L^{\infty}}\leq C_{K}\,;$ (2.1)

  2. (2)

For any $\mu,\nu\in\mathcal{P}(\mathbb{R}^{d})$ and any
$x,y\in\mathbb{R}^{d}$, it holds

$|F(x,\mu)-F(y,\nu)|\leq C_{F}(|x-y|+W_{2}(\mu,\nu))$ (2.2)

with $C_{F}:=\left\lVert\nabla
K\,\right\rVert_{\mbox{Lip}}+\left\lVert\nabla\Phi\,\right\rVert_{\mbox{Lip}}$.

Under the above regular assumptions on $K$, standard result, see for example
[sznitman1991topics], gives the well-posedness of the Mckean processes (1.5)
and (1.7)

######  Theorem 2.1.

Let $\nabla K\in
L^{\infty}(\mathbb{R}^{d})\cap\operatorname{Lip}(\mathbb{R}^{d})$. For each
$T>0$, there hold the following assertions.

(i) If $(X_{0},V_{0})$ is distributed according to
$f_{0}\in\mathcal{P}_{2}(\mathbb{R}^{2d})$, then for each $\gamma>0$, the
nonlinear SDE (1.5) admits a unique solution up to time $T$ with the initial
data $(X_{0},V_{0})$ and it holds further that

$\sup\limits_{t\in[0,T]}\mathbb{E}\left[|X^{\gamma}_{t}|^{2}+|V^{\gamma}_{t}|^{2}\right]\leq
C\mathbb{E}\left[|X_{0}|^{2}+|V_{0}|^{2}\right]\,,$ (2.3)

where $C$ depends only on $C_{K},C_{\Phi},\gamma$ and $T$.

(ii) If $X_{0}$ is distributed according to
$\rho_{0}\in\mathcal{P}_{2}(\mathbb{R}^{d})$, then SDE (1.7) admits a unique
solution up to time $T$ with the initial data $X_{0}$ and it holds further
that

$\sup\limits_{t\in[0,T]}\mathbb{E}\left[|X_{t}|^{2}\right]\leq
C\mathbb{E}\left[|X_{0}|^{2}\right]\,,$ (2.4)

where $C$ depends only on $C_{K},C_{\Phi}$ and $T$.

The proof of the overdamped limit will proceed in two steps:

  * •

We prove a tightness result for the sequence of probability distributions
$\\{\rho^{\gamma}\\}_{\gamma>0}$ of $\\{X^{\gamma}\\}_{\gamma>0}$ by using
Aldous’s tightness criteria.

  * •

We will check that all the limit points of $\\{X^{\gamma}\\}_{\gamma>0}$ as
$\gamma\to\infty$ satisfy the Mckean process (1.7) underlying the aggregation-
diffusion equation (1.6).

For the sake of completeness, let us recall a result from the Aldous criteria
[jacod2002limit, Theorem 4.5].

######  Lemma 2.1.

Let $\\{X^{n}\\}_{n\in\mathbb{N}}$ be a sequence of random variables defined
on a probability space $(\Omega,\mathcal{F},\mathbb{P})$ and valued in
$\mathcal{C}([0,T];\mathbb{R}^{d})$. The sequence of probability distributions
$\\{\mu_{X^{n}}\\}_{n\in\mathbb{N}}$ of $\\{X^{n}\\}_{n\in\mathbb{N}}$ is
tight on $\mathcal{C}([0,T];\mathbb{R}^{d})$ if the following hold.

$(Con1)$ For all $t\geq 0$, $\\{\mu_{X_{t}^{n}}\\}_{n\in\mathbb{N}}$ the set
of distributions of $\\{X_{t}^{n}\\}_{n\in\mathbb{N}}$ is tight in
$\mathbb{R}^{d}$.

$(Con2)$ For all $\varepsilon>0$, $\eta>0$, there exists $\delta_{0}>0$ and
$n_{0}\in\mathbb{N}$ such that for all $n\geq n_{0}$ and for all discrete-
valued $\sigma(X^{n}_{s};s\in[0,T])$-stopping times $\beta$ such that
$0\leq\beta+\delta_{0}\leq T$,

$\sup_{\delta\in[0,\delta_{0}]}\mathbb{P}\left(|X^{n}_{\beta+\delta}-X^{n}_{\beta}|\geq\eta\right)\leq\varepsilon\,.$
(2.5)

######  Theorem 2.2 (Tightness).

For any $\gamma>0$ and $T>0$, let
$(X^{\gamma}_{t},V^{\gamma}_{t})_{t\in[0,T]}$ satisfy the system (1.5) up to
time $T$ with $\nabla K\in
L^{\infty}(\mathbb{R}^{d})\cap\operatorname{Lip}(\mathbb{R}^{d})$, $\Psi$
satisfying Assumption 1, and the initial data
$\operatorname{Law}(X_{0},V_{0})=f_{0}\in\mathcal{P}_{2}(\mathbb{R}^{2d})$.
Then for each countable subsequence $\\{\gamma_{k}\\}_{k\in\mathbb{N}}$ with
$\lim_{k\rightarrow\infty}\gamma_{k}=\infty$, the sequence of probability
distributions $\\{\rho^{\gamma_{k}}\\}_{k\in\mathbb{N}}$ of
$\\{X^{\gamma_{k}}\\}_{k\in\mathbb{N}}$ is tight on
$\mathcal{C}([0,T];\mathbb{R}^{d})$.

###### Proof.

We apply the Aldous criteria in Lemma 2.1 to the system
$\\{X^{\gamma}\\}_{\gamma>0}$ by verifying conditions $(Con1)$ and $(Con2)$.

$\bullet$ Step 1: Checking $(Con1)$.  Let us recall (1) and use Fubini’s
theorem (see [da2014stochastic, Theorem 4.33] for the stochastic version),
then we have

$\displaystyle X_{t}^{\gamma}$
$\displaystyle=X_{0}+\gamma\int_{0}^{t}e^{-\gamma^{2}\tau}V_{0}d\tau+\gamma^{2}\int_{0}^{t}\int_{0}^{\tau}e^{-\gamma^{2}(\tau-s)}F(X_{s}^{\gamma},\rho_{s}^{\gamma})dsd\tau+\sqrt{2}\gamma^{2}\int_{0}^{t}\int_{0}^{\tau}e^{-\gamma^{2}(\tau-s)}dB_{s}d\tau$
$\displaystyle=X_{0}+\gamma\int_{0}^{t}e^{-\gamma^{2}\tau}V_{0}d\tau+\gamma^{2}\int_{0}^{t}\int_{s}^{t}e^{-\gamma^{2}(\tau-s)}d\tau
F(X_{s}^{\gamma},\rho_{s}^{\gamma})ds+\sqrt{2}\gamma^{2}\int_{0}^{t}\int_{s}^{t}e^{-\gamma^{2}(\tau-s)}d\tau
dB_{s}$
$\displaystyle=X_{0}+\frac{1}{\gamma}(1-e^{-\gamma^{2}t})V_{0}+\int_{0}^{t}(1-e^{-\gamma^{2}(t-s)})F(X_{s}^{\gamma},\rho_{s}^{\gamma})ds+\sqrt{2}\int_{0}^{t}(1-e^{-\gamma^{2}(t-s)})dB_{s}\,.$
(2.6)

For $\gamma\geq 1$, it follows from Hölder’s inequality that

$|X_{t}^{\gamma}|^{2}\leq
4|X_{0}|^{2}+4|V_{0}|^{2}+2T\int_{0}^{t}|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}ds+8\left|\int_{0}^{t}(1-e^{-\gamma^{2}(t-s)})dB_{s}\right|^{2}\,.$

Here we have used the fact that for any sequence $\\{a_{i}\\}_{i=1}^{n}\geq
0$, one has

$(\sum_{i=1}^{n}a_{i})^{2}\leq n\sum_{i=1}^{n}a_{i}^{2}\,.$ (2.7)

Using Itô’s isometry yields that

$\displaystyle\mathbb{E}\left[\left|\int_{0}^{t}(1-e^{-\gamma^{2}(t-s)})dB_{s}\right|^{2}\right]=\mathbb{E}\left[\int_{0}^{t}|(1-e^{-\gamma^{2}(t-s)})|^{2}ds\right]\leq
T\,.$

Thus we have

$\displaystyle\mathbb{E}[|X_{t}^{\gamma}|^{2}]\leq
4\mathbb{E}[|X_{0}|^{2}]+4\mathbb{E}[|V_{0}|^{2}]+2T\int_{0}^{t}\mathbb{E}[|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}]ds+8T\,.$
(2.8)

It follows from (1.14) and (2.1) that

$\displaystyle\mathbb{E}[|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}]$
$\displaystyle=\mathbb{E}[|\nabla\Phi(X_{s}^{\gamma})+\nabla
K\ast\rho^{\gamma}_{s}(X_{s}^{\gamma})|^{2}]\leq
2\mathbb{E}[|\nabla\Phi(X_{s}^{\gamma})|^{2}]+2C_{K}^{2}$ $\displaystyle\leq
2\mathbb{E}[|C_{\Phi}(1+|X_{s}^{\gamma}|)|^{2}]+2C_{K}^{2}\leq
4C_{\Phi}^{2}+2C_{K}^{2}+4C_{\Phi}^{2}\mathbb{E}[|X_{s}^{\gamma}|^{2}]\,,$
(2.9)

which leads to

$\displaystyle\mathbb{E}[|X_{t}^{\gamma}|^{2}]\leq
4\mathbb{E}[|X_{0}|^{2}]+4\mathbb{E}[|V_{0}|^{2}]+8C_{\Phi}^{2}T\int_{0}^{t}\mathbb{E}[|X_{s}^{\gamma}|^{2}]ds+2T(4C_{\Phi}^{2}+2C_{K}^{2})+8T\,.$
(2.10)

Using Gronwall’s inequality leads to

$\mathbb{E}[|X_{t}^{\gamma}|^{2}]\leq\left(4\mathbb{E}[|X_{0}|^{2}]+4\mathbb{E}[|V_{0}|^{2}]+2T(4C_{\Phi}^{2}+2C_{K}^{2})+8T\right)\exp\left(8C_{\Phi}^{2}T^{2}\right),\quad
t\in[0,T]\,.$ (2.11)

This implies that

$\sup_{t\in[0,T]}\mathbb{E}[|X_{t}^{\gamma}|^{2}]\leq
C(\mathbb{E}[|X_{0}|^{2}],\mathbb{E}[|V_{0}|^{2}],C_{\Phi},C_{K},T)=:C_{1}$
(2.12)

where $C_{1}>0$ is a constant independent of $\gamma$. So for any
$\varepsilon>0$, there exists a compact subset
$K_{\varepsilon}:=\\{x:~{}|x|^{2}\leq\frac{C_{1}}{\varepsilon}\\}$ such that
by Markov’s inequality

$\rho_{t}^{\gamma}((K_{\varepsilon})^{c})=\mathbb{P}(|X_{t}^{\gamma}|^{2}>\frac{C_{1}}{\varepsilon})\leq\frac{\varepsilon\mathbb{E}[|X_{t}^{\gamma}|^{2}]}{C_{1}}\leq\varepsilon,\quad\forall~{}\gamma\geq
1\,.$ (2.13)

This means that for all $t\in[0,T]$, each countable subset of
$\\{\rho_{t}^{\gamma}\\}_{\gamma\geq 1}$ is tight in $\mathbb{R}^{d}$, which
verifies condition $(Con1)$ in Lemma 2.1.

$\bullet$ Step 2: Checking $(Con2)$.  Let $\beta$ be a
$\sigma(X^{\gamma}_{s};s\in[0,T])$-stopping time with discrete values such
that $\beta+\delta_{0}\leq T$. Let us recall (1) and compute

$\displaystyle
X_{\beta+\delta}^{\gamma}-X_{\beta}^{\gamma}=\int_{\beta}^{\beta+\delta}V_{\tau}d\tau$
$\displaystyle=$
$\displaystyle\gamma\int_{\beta}^{\beta+\delta}e^{-\gamma^{2}\tau}V_{0}d\tau+\gamma^{2}\int_{\beta}^{\beta+\delta}\int_{0}^{\tau}e^{-\gamma^{2}(\tau-s)}F(X_{s}^{\gamma},\rho_{s}^{\gamma})dsd\tau+\sqrt{2}\gamma^{2}\int_{\beta}^{\beta+\delta}\int_{0}^{\tau}e^{-\gamma^{2}(\tau-s)}dB_{s}d\tau$
$\displaystyle=$
$\displaystyle\gamma\int_{\beta}^{\beta+\delta}e^{-\gamma^{2}\tau}V_{0}d\tau+\gamma^{2}\int_{0}^{\beta}\int_{\beta}^{\beta+\delta}e^{-\gamma^{2}(\tau-s)}d\tau
F(X_{s}^{\gamma},\rho_{s}^{\gamma})ds+\gamma^{2}\int_{\beta}^{\beta+\delta}\int_{s}^{\beta+\delta}e^{-\gamma^{2}(\tau-s)}d\tau
F(X_{s}^{\gamma},\rho_{s}^{\gamma})ds$
$\displaystyle\quad+\sqrt{2}\gamma^{2}\int_{0}^{\beta}\int_{\beta}^{\beta+\delta}e^{-\gamma^{2}(\tau-s)}d\tau
dB_{s}+\sqrt{2}\gamma^{2}\int_{\beta}^{\beta+\delta}\int_{s}^{\beta+\delta}e^{-\gamma^{2}(\tau-s)}d\tau
dB_{s}$ $\displaystyle=$
$\displaystyle\frac{1}{\gamma}(e^{-\gamma^{2}\beta}-e^{-\gamma^{2}(\beta+\delta)})V_{0}+\int_{0}^{\beta}(e^{-\gamma^{2}(\beta-s)}-e^{-\gamma^{2}(\beta+\delta-s)})F(X_{s}^{\gamma},\rho_{s}^{\gamma})ds+\int_{\beta}^{\beta+\delta}(1-e^{-\gamma^{2}(\beta+\delta-s)})F(X_{s}^{\gamma},\rho_{s}^{\gamma})ds$
$\displaystyle\quad+\sqrt{2}(e^{-\gamma^{2}\beta}-e^{-\gamma^{2}(\beta+\delta)})\int_{0}^{\beta}e^{\gamma^{2}s}dB_{s}+\sqrt{2}\int_{\beta}^{\beta+\delta}(1-e^{-\gamma^{2}(\beta+\delta-s)})dB_{s}\,.$
(2.14)

Note here that the multiplier
$(e^{-\gamma^{2}\beta}-e^{-\gamma^{2}(\beta+\delta)})$ cannot enter the
stochastic integral due to the non-anticipativity required for Itô integrals
and associated moment estimates.

Notice that it holds $|e^{-x}-e^{-y}|\leq|x-y|\wedge 1$ for all
$x,y\in[0,\infty)$ and $\xi\in[0,1]$. Then it is easy to compute that for each
$q\geq 1$, $\xi\in[0,1]$ and $\tau\in[0,T]$,

$\displaystyle\int_{0}^{\tau}\left|e^{-\gamma^{2}(\tau-s)}-e^{-\gamma^{2}(\tau+\delta-s)}\right|^{q}\,ds\leq\int_{0}^{\tau}\left(e^{-\gamma^{2}(\tau-s)}-e^{-\gamma^{2}(\tau+\delta-s)}\right)\,ds$
$\displaystyle=$
$\displaystyle\frac{1}{\gamma^{2}}\left(1-e^{-\gamma^{2}\delta}\right)-\frac{1}{\gamma^{2}}\left(e^{-\gamma^{2}\tau}-e^{-\gamma^{2}(\tau+\delta)}\right)\leq\frac{1}{\gamma^{2}}\cdot(\gamma^{2}\delta)^{\xi}=(\frac{1}{\gamma^{2}})^{1-\xi}\delta^{\xi},$
(2.15)

and in particular it holds

$\int_{\beta}^{\beta+\delta}\left(1-e^{-\gamma^{2}(\beta+\delta-s)}\right)^{q}ds\leq\int_{\beta}^{\beta+\delta}1\,ds=\delta.$

It is easy to see that

$\displaystyle\mathbb{E}\left[\frac{1}{\gamma^{2}}|(e^{-\gamma^{2}\beta}-e^{-\gamma^{2}(\beta+\delta)})V_{0}|^{2}\right]\leq\frac{1}{\gamma^{2}}\gamma^{2}\delta\mathbb{E}[|e^{-\gamma^{2}\beta}-e^{-\gamma^{2}(\beta+\delta)}||V_{0}|^{2}]\leq\delta\mathbb{E}[|X_{0}|^{2}]\,.$
(2.16)

Moreover, we notice that

$\displaystyle\mathbb{E}\left[|\int_{0}^{\beta}(e^{-\gamma^{2}(\beta-s)}-e^{-\gamma^{2}(\beta+\delta-s)})F(X_{s}^{\gamma},\rho_{s}^{\gamma})ds|^{2}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\int_{0}^{\beta}|e^{-\gamma^{2}(\beta-s)}-e^{-\gamma^{2}(\beta+\delta-s)}|^{2}ds\int_{0}^{\beta}|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}ds\right]\leq\delta\int_{0}^{T}\mathbb{E}[|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}]ds\,,$

and

$\displaystyle\mathbb{E}\left[|\int_{\beta}^{\beta+\delta}(1-e^{-\gamma^{2}(\beta+\delta-s)})F(X_{s}^{\gamma},\rho_{s}^{\gamma})ds|^{2}\right]\leq\delta\mathbb{E}\left[\int_{\beta}^{\beta+\delta}|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}ds\right]\leq\delta\int_{0}^{T}\mathbb{E}\left[|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}\right]ds\,.$

Applying Itô’s isometry one has

$\displaystyle\mathbb{E}\left[|\int_{\beta}^{\beta+\delta}(1-e^{-\gamma^{2}(\beta+\delta-s)})dB_{s}|^{2}\right]=\mathbb{E}\left[\int_{\beta}^{\beta+\delta}|1-e^{-\gamma^{2}(\beta+\delta-s)}|^{2}ds\right]\leq\delta\,.$
(2.17)

Particularly, let us look at

$Z^{\gamma,\delta}_{t}:=(e^{-\gamma^{2}t}-e^{-\gamma^{2}(t+\delta)})\int_{0}^{t}e^{\gamma^{2}s}dB_{s},\quad
t\in[0,T],$

and try to derive an estimate on $Z^{\gamma,\delta}_{\beta}$. Basic
calculations as above yield that

$\displaystyle\mathbb{E}\left[\int_{0}^{T}\Big{|}Z^{\gamma,\delta}_{t}\Big{|}^{2}dt\right]$
$\displaystyle=\mathbb{E}\left[\int_{0}^{T}\Big{|}\int_{0}^{t}(e^{-\gamma^{2}t}-e^{-\gamma^{2}(t+\delta)})e^{\gamma^{2}s}dB_{s}\Big{|}^{2}dt\right]$
$\displaystyle=\int_{0}^{T}\int_{0}^{t}|(e^{-\gamma^{2}t}-e^{-\gamma^{2}(t+\delta)})e^{\gamma^{2}s}|^{2}dsdt\leq
C\delta$ (2.18)

where we have used Itô’s isometry and the estimate (2) with $\zeta=1$ and the
constant $C$ is independent of $\gamma$ and $\delta$. Thus, the process

$M^{\gamma,\delta}_{t}:=\int_{0}^{t}(Z^{\gamma,\delta}_{s})^{\prime}dB_{s},\quad
t\in[0,T],$

is a integrable continuous martingale; indeed, Doob’s martingale inequality
gives

$\displaystyle\mathbb{E}\left[\max_{t\in[0,T]}\left|M^{\gamma,\delta}_{t}\right|\right]\leq
C\mathbb{E}\left[\int_{0}^{T}\left|(Z^{\gamma,\delta}_{s})^{\prime}\right|ds\right]\leq
C\left(\mathbb{E}\left[\int_{0}^{T}\left|Z^{\gamma,\delta}_{s}\right|^{2}ds\right]\right)^{1/2}\leq
C\delta^{1/2},$ (2.19)

with $C$ being independent of $\gamma$ and $\delta$. On the other hand, it is
easy to see that $Z^{\gamma,\delta}$ satisfies the following SDE

$dZ^{\gamma,\delta}_{t}=-\gamma^{2}Z^{\gamma,\delta}_{t}dt+(1-e^{-\gamma^{2}\delta})\,dB_{t},\quad
t>0;\quad Z^{\gamma,\delta}_{0}=0.$

By Itô-Doeblin formula, it holds that for all $t\in[0,T]$,

$\displaystyle|Z^{\gamma,\delta}_{t}|^{2}$
$\displaystyle=\int_{0}^{t}\Big{|}(e^{-\gamma^{2}(t-s)}-e^{-\gamma^{2}(t+\delta-s)})\Big{|}^{2}ds+2\int_{0}^{t}e^{-2\gamma^{2}(t-s)}(1-e^{-\gamma^{2}\delta})dM^{\gamma,\delta}_{s}$
$\displaystyle\leq\delta+2(1-e^{-\gamma^{2}\delta})M^{\gamma,\delta}_{t}-4\int_{0}^{t}\gamma^{2}e^{-2\gamma^{2}(t-s)}(1-e^{-\gamma^{2}\delta})M^{\gamma,\delta}_{s}\,ds$
$\displaystyle\leq\delta+2\left|M^{\gamma,\delta}_{t}\right|+4\gamma^{2}\max_{s\in[0,T]}\left|M^{\gamma,\delta}_{s}\right|\int_{0}^{t}e^{-2\gamma^{2}(t-s)}\,ds\leq\delta+4\max_{s\in[0,T]}\left|M^{\gamma,\delta}_{s}\right|,\quad\text{a.s.,}$
(2.20)

where the integration by parts formula is applied to the stochastic integral
in the first line and in the second inequality, we used estimate (2) with
$\zeta$ equal to $1$. Combined with (2.19), it yields that

$\displaystyle\mathbb{E}\left[\Big{|}Z^{\gamma,\delta}_{\beta}\Big{|}^{2}\right]\leq\mathbb{E}\left[\max_{t\in[0,T]}\Big{|}Z^{\gamma,\delta}_{t}\Big{|}^{2}\right]\leq
C(\delta^{1/2}+\delta),$

where the constant $C$ is independent of $\beta,\gamma,$ and $\delta$.

Thus we have

$\displaystyle\mathbb{E}[|X^{\gamma}_{\beta+\delta}-X^{\gamma}_{\beta}|^{2}]\leq
5\delta\mathbb{E}[|X_{0}|^{2}]+10\delta\int_{0}^{T}\mathbb{E}[|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}]ds+10\delta+10C(\delta^{1/2}+\delta)$
$\displaystyle\leq$ $\displaystyle
5\delta\mathbb{E}[|X_{0}|^{2}]+10\delta\left(4C_{\Phi}^{2}T+2C_{K}^{2}T+4C_{\Phi}^{2}\int_{0}^{T}\mathbb{E}[|X_{s}^{\gamma}|^{2}]ds\right)+10\delta+10C(\delta^{1/2}+\delta)\,,$
(2.21)

where we have used (2) in the last inequality. Recalling the fact that for all
$\gamma\geq 1$

$\sup_{s\in[0,T]}\mathbb{E}[|X_{s}^{\gamma}|^{2}]\leq
C(\mathbb{E}[|X_{0}|^{2}],\mathbb{E}[|V_{0}|^{2}],C_{\Phi},C_{K},T)\,,$

it easy to see that

$\displaystyle\mathbb{E}[|X^{\gamma}_{\beta+\delta}-X^{\gamma}_{\beta}|^{2}]\leq
C(\mathbb{E}[|X_{0}|^{2}],\mathbb{E}[|V_{0}|^{2}],C_{\Phi},C_{K},T)(\delta+\delta^{\frac{1}{2}})\,.$

Hence for any $\varepsilon>0$, $\eta>0$, there exists some $\delta_{0}$ and
$\gamma_{0}=1$, such that for all $\gamma\geq 1$ it holds that

$\sup_{\delta\in[0,\delta_{0}]}\mathbb{P}(|X^{\gamma}_{\beta+\delta}-X^{\gamma}_{\beta}|^{2}\geq\eta)\leq\sup_{\delta\in[0,\delta_{0}]}\frac{\mathbb{E}[|X^{\gamma}_{\beta+\delta}-X^{\gamma}_{\beta}|^{2}]}{\eta}\leq\varepsilon\,.$
(2.22)

This completes the verification of condition $Con2$ in Lemma 2.1. ∎

Next we shall identify the limit process.

######  Theorem 2.3 (Overdamped limit).

For any $\gamma>0$ and $T>0$, let
$(X^{\gamma}_{t},V^{\gamma}_{t})_{t\in[0,T]}$ satisfy the system (1.5) up to
time $T$ with $\nabla K\in
L^{\infty}(\mathbb{R}^{d})\cap\mbox{Lip}(\mathbb{R}^{d})$, $\Psi$ satisfying
Assumption 1, and the initial data
$\operatorname{Law}(X_{0},V_{0})=f_{0}\in\mathcal{P}_{2}(\mathbb{R}^{2d})$.
Then as $\gamma\rightarrow\infty$, the sequence of stochastic processes
$\\{X^{\gamma}\\}_{\gamma>0}$ converge weakly to $X$, which is the unique
solution to the following SDE:

$\displaystyle X_{t}=X_{0}+\int_{0}^{t}F(X_{s},\rho_{s})ds+\sqrt{2}B_{t}\,.$
(2.23)

Moreover it holds that

$\sup_{t\in[0,T]}\mathbb{E}[|X^{\gamma}_{t}-X_{t}|^{2}]\leq\frac{C}{\gamma^{2}}e^{CT}\,,$
(2.24)

where $C$ depends only on
$\mathbb{E}[|X_{0}|^{2}],\mathbb{E}[|V_{0}|^{2}],C_{\Phi},C_{K},C_{F}$ and
$T$.

######  Remark 2.1.

It follows from the definition of Wasserstein distance that

$\sup_{t\in[0,T]}W_{2}^{2}(\rho^{\gamma}_{t},\rho_{t})\leq\sup_{t\in[0,T]}\mathbb{E}[|X^{\gamma}_{t}-X_{t}|^{2}]\leq\frac{C}{\gamma^{2}}e^{CT}\,,$
(2.25)

which is consistent with the result obtained in [choi2020quantified, Theorem
1.3].

###### Proof.

By Theorem 2.2 each subsequence $\\{X^{\gamma_{k}}\\}_{k\in\mathbb{N}}$ with
$\gamma_{0}\geq 1$ and $\gamma_{k}$ converging increasingly to $0$ as
$k\rightarrow\infty$ admits a subsequence (denoted w.l.o.g. by itself) that
converges weakly. This means that there exists some process $\widehat{X}$ as
random variables valued in $\mathcal{C}([0,T];\mathbb{R}^{d})$ such that

$X\rightharpoonup\widehat{X}$ (2.26)

in the sense of distribution.

Recall the SDE satisfied by $X^{\gamma_{k}}$ in (2)

$\displaystyle
X_{t}^{\gamma_{k}}=X_{0}+\frac{1}{\gamma_{k}}(1-e^{-\gamma_{k}^{2}t})V_{0}+\int_{0}^{t}(1-e^{-\gamma_{k}^{2}(t-s)})F(X_{s}^{\gamma_{k}},\rho_{s}^{\gamma_{k}})ds+\sqrt{2}\int_{0}^{t}(1-e^{-\gamma_{k}^{2}(t-s)})dB_{s}\,.$
(2.27)

Notice that the estimate in (2.12) implies that

$\sup_{k\in\mathbb{N}}\sup_{t\in[0,T]}\mathbb{E}[|X_{t}^{\gamma_{k}}|^{2}]\leq
C_{1},\quad\text{ and thus,
}\quad\sup_{t\in[0,T]}\mathbb{E}[|\widehat{X}_{t}|^{2}]\leq C_{1},$ (2.28)

with the constant $C_{1}$ being independent of $\gamma_{k}$. We recall

$\mathbb{E}[|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}]\leq
4C_{\Phi}^{2}+2C_{K}^{2}+4C_{\Phi}^{2}\mathbb{E}[|X_{s}^{\gamma}|^{2}]\,.$

Denoting by $\rho_{t}$ the probability distribution of $X_{t}$ for
$t\in[0,T]$, thus we have

$\sup_{k\in\mathbb{N}}\sup_{t\in[0,T]}|F(X_{s}^{\gamma_{k}},\rho_{s}^{\gamma_{k}})|\leq
C(C_{1},C_{K},C_{\Phi}),\quad\text{ and
}\quad\sup_{t\in[0,T]}|F(X_{s},{\rho}_{s})|\leq C(C_{1},C_{K},C_{\Phi})\,.$
(2.29)

Furthermore, by (2.2) and the definition of Wasserstein distance, one has

$\mathbb{E}[|F(X_{s}^{\gamma_{k}},\rho^{\gamma_{k}}_{s})-F(X_{s},\rho_{s})|^{2}]\leq
C_{F}^{2}\mathbb{E}[||X_{s}^{\gamma_{k}}-X_{s}|+W_{2}(\rho^{\gamma_{k}}_{s},\rho_{s})|^{2}]\leq
2C_{F}^{2}\mathbb{E}[|X_{s}^{\gamma}-X_{s}|^{2}],$ (2.30)

and thus,

$\displaystyle\mathbb{E}\left[\left|\int_{0}^{t}(1-e^{-\gamma_{k}^{2}(t-s)})F(X_{s}^{\gamma_{k}},\rho^{\gamma_{k}}_{s})ds-\int_{0}^{t}F(X_{s},\rho_{s})ds\right|^{2}\right]$
(2.31) $\displaystyle\leq$ $\displaystyle
2\mathbb{E}\left[\left|\int_{0}^{t}(1-e^{-\gamma_{k}^{2}(t-s)})(F(X_{s}^{\gamma_{k}},\rho^{\gamma_{k}}_{s})-F(X_{s},\rho_{s}))ds\right|^{2}\right]+2\mathbb{E}\left[\left|\int_{0}^{t}e^{-\gamma_{k}^{2}(t-s)}F(X_{s},\rho_{s})ds\right|^{2}\right]$
(2.32) $\displaystyle\leq$ $\displaystyle
C\mathbb{E}\left[\int_{0}^{t}\left|X_{s}-X_{s}^{\gamma_{k}}\right|^{2}ds\right]+C\int_{0}^{t}e^{-2\gamma_{k}^{2}(t-s)}ds\mathbb{E}\left[\int_{0}^{T}|F(X_{s},\rho_{s})|^{2}ds\right]$
(2.33) $\displaystyle\leq$ $\displaystyle
C\mathbb{E}\left[\int_{0}^{t}\left|X_{s}-X_{s}^{\gamma_{k}}\right|^{2}ds\right]+C\frac{1}{\gamma_{k}^{2}}\,,$
(2.34)

where the constant $C$ is independent of $k$, and we have used the boundedness
in (2.29). For the stochastic integrals, it holds analogously that

$\displaystyle\mathbb{E}\left[\left|\int_{0}^{t}(1-e^{-\gamma_{k}^{2}(t-s)})dB_{s}-\int_{0}^{t}dB_{s}\right|^{2}\right]=\mathbb{E}\left[\left|\int_{0}^{t}e^{-\gamma_{k}^{2}(t-s)}dB_{s}\right|^{2}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\int_{0}^{t}e^{-2\gamma_{k}^{2}(t-s)}ds\right]\leq
C\frac{1}{\gamma_{k}^{2}}\,.$ (2.35)

Additionally, it is obvious that

$|\frac{1}{\gamma_{k}}(1-e^{-\gamma_{k}^{2}t})V_{0}|^{2}\leq\frac{1}{\gamma_{k}^{2}}|V_{0}|^{2}\,.$
(2.36)

Therefore collecting estimates (2.31)–(2.36) and subtracting both sides of
SDEs (2.27) and (2.23), one has

$\displaystyle\mathbb{E}[|X_{t}^{\gamma_{k}}-X_{t}|^{2}]\leq
C\int_{0}^{t}\mathbb{E}[|X_{s}^{\gamma_{k}}-X_{s}|^{2}]ds+C\frac{1}{\gamma_{k}^{2}}\,,$
(2.37)

where $C$ depends only on
$\mathbb{E}[|X_{0}|^{2}],\mathbb{E}[|V_{0}|^{2}],C_{F},C_{\Phi},C_{K}$ and
$T$. By Gronwall’s inequality implies that

$\sup_{t\in[0,T]}\mathbb{E}[|X_{t}^{\gamma_{k}}-X_{t}|^{2}]\leq
C\frac{1}{\gamma_{k}^{2}}e^{CT}\,.$ (2.38)

In view of both the convergences (2.26) and (2.38), we must have
$\widehat{X}=X$. Finally, due to the arbitrariness of the subsequence
$\\{X^{\gamma_{k}}\\}_{k\in\mathbb{N}}$ and the uniqueness of $X$, we conclude
that as $\gamma\rightarrow\infty$, the sequence of stochastic processes
$\\{X^{\gamma}\\}_{\gamma>0}$ converge weakly to the unique solution $X$ to
SDE (2.23), with the estimate (2.24) following in the same way as (2.38). ∎

##  3\. Singular interaction potential

In this section we assume that $\nabla K\in L_{loc}^{q}(\mathbb{R}^{d})$ for
some $q\in(1,\infty]$. More specifically it satisfies

######  Assumption 2.

There exist some $C_{K}^{\prime}>0$ such that

$C_{K}^{\prime}:=\left\lVert\nabla
K\,\right\rVert_{L^{q}(B_{2R})}+\left\lVert\nabla
K\,\right\rVert_{W^{1,\infty}(\mathbb{R}^{d}\backslash B_{R})}<\infty\mbox{
for some }R>0\mbox{ and }q\in(1,\infty]\,,$ (3.1)

where $B_{R}$ represents a ball of radius $R$ and centered at origin.

As it has been mentioned in Introduction, for singular case we require more
regular solutions $f^{\gamma}$ to the kinetic equation (1.1). For
$p\in[1,\infty)$, we consider the space of weighted measurable functions
$L_{H}^{p}(\mathbb{R}^{2d})$ with the norm

$\left\lVert
f^{\gamma}_{t}\,\right\rVert_{L_{H}^{p}}:=\left(\iint_{\mathbb{R}^{d}\times{\mathbb{R}}^{d}}|f^{\gamma}_{t}|^{p}e^{(p-1)H}dxdy\right)^{\frac{1}{p}}\,,$
(3.2)

where $H(x,v)=\Phi(x)+\frac{|v|^{2}}{2}$. For any integer $k\in\mathbb{N}$,
$W_{x,H}^{k,p}$ represents $L_{H}^{p}$ Sobolev space of $k$-th order in $x$
with the norm

$\left\lVert
f^{\gamma}_{t}\,\right\rVert_{W_{x,H}^{k,p}}:=\left(\sum_{|\alpha|\leq
k}\iint_{\mathbb{R}^{d}\times{\mathbb{R}}^{d}}|\nabla_{x}^{\alpha}f^{\gamma}_{t}|^{p}e^{(p-1)H}dxdy\right)^{\frac{1}{p}}\,.$
(3.3)

First we recall the following implied regularity for $\rho^{\gamma}$:

######  Lemma 3.1.

[choi2020quantified, Lemma 2.9] If $f^{\gamma}_{t}\in
W_{x,H}^{1,p}(\mathbb{R}^{2d})$, then $\rho^{\gamma}_{t}\in
W^{1,p}(\mathbb{R}^{d})$. In particular, if $p>d$, one has
$\rho^{\gamma}_{t}\in L^{\infty}(\mathbb{R}^{d})$ .

Now we state the result of the well-posedness of local-in-time solutions to
the VFP equation (1.1) and $\gamma$ independent estimates:

######  Theorem 3.1.

[choi2020quantified, Theorem 1.4] Let $T>0$ and suppose that the interaction
potential $K$ satisfy Assumption 2. Let the initial data
$f_{0}\in\mathcal{P}_{2}\cap W_{x,H}^{1,p}(\mathbb{R}^{2d})$,
$p>\max\\{d,q/(q-1)\\}$. There exists a positive time $T_{p}\in(0,T]$, and a
unique solution

$f^{\gamma}\in\mathcal{C}\left(\left[0,T_{p}\right];\mathcal{P}_{2}\left(\mathbb{R}^{d}\times\mathbb{R}^{d}\right)\right)\cap
L^{\infty}\left(\left[0,T_{p}\right];W_{x,H}^{1,p}\left(\mathbb{R}^{d}\times\mathbb{R}^{d}\right)\right)$
(3.4)

to (1.1) satisfying

$\sup_{\gamma\geq 1}\sup_{t\in[0,T_{p}]}\left\lVert
f^{\gamma}_{t}\,\right\rVert_{W_{x,H}^{1,p}}<\infty\,.$ (3.5)

Lemma 3.1 implies that

$\sup_{\gamma\geq
1}\sup_{t\in[0,T_{p}]}\left\lVert\rho^{\gamma}_{t}\,\right\rVert_{L^{\infty}}<\infty\,.$
(3.6)

Using above theorem we can proved the uniform bound of $\nabla
K\ast\rho^{\gamma}_{t}$ under additional assumption of $K$:

######  Assumption 3.

The interaction potential $K$ satisfies one of the following conditions:

  * •

$\nabla K\in W^{1,1}(B_{2R})$;

  * •

$K$ is given by the Newtonian potential, i.e. $\pm\Delta K=\delta_{0}$, where
$\delta_{0}$ denotes the Dirac measure on $\mathbb{R}^{d}$ giving unit mass to
the origin.

######  Lemma 3.2.

Assume that $K$ satisfy Assumption 2–3 and let $f^{\gamma},\rho^{\gamma}$ be
the regular solution to (1.1) obtained in Theorem 3.1, It holds that

$\sup_{\gamma\geq 1}\sup_{t\in[0,T_{p}]}\left\lVert\nabla
K\ast\rho^{\gamma}_{t}\,\right\rVert_{W^{1,\infty}}<\infty\,.$ (3.7)

###### Proof.

For $x\in\mathbb{R}^{d}$ we obtain

$\nabla K\ast\rho^{\gamma}_{t}(x)=\int_{\mathbb{R}^{d}}\nabla
K(x-y)\rho^{\gamma}_{t}(y)dy\leq\int_{B_{R}}|\nabla
K|(x-y)\rho^{\gamma}_{t}(y)dy+C_{K}^{\prime}\,.$ (3.8)

Notice that

$\int_{B_{R}}|\nabla K|(x-y)\rho^{\gamma}_{t}(y)dy\leq\left\lVert\nabla
K\,\right\rVert_{L^{q}(B_{R})}\left\lVert\rho^{\gamma}_{t}\,\right\rVert_{L^{q/(q-1)}}<C(C_{K}^{\prime},\left\lVert\rho^{\gamma}_{t}\,\right\rVert_{L^{\infty}})\,.$
(3.9)

By (3.6), this gives

$\sup_{\gamma\geq 1}\sup_{t\in[0,T_{p}]}\left\lVert\nabla
K\ast\rho^{\gamma}_{t}\,\right\rVert_{L^{\infty}}<\infty\,.$ (3.10)

If we additional assume that $\nabla K\in W^{1,1}(B_{2R})$, following the same
arguments as above we can easily obtain

$\sup_{\gamma\geq 1}\sup_{t\in[0,T_{p}]}\left\lVert\nabla
K\ast\rho^{\gamma}_{t}\,\right\rVert_{W^{1,\infty}}<\infty\,.$ (3.11)

On the other hand if we additional assume that $\pm\Delta K=\delta_{0}$, which
means that $\nabla\cdot(\nabla K\ast\rho^{\gamma}_{t})=\pm\rho^{\gamma}_{t}$.
Thus we have $\left\lVert\nabla
K\ast\rho^{\gamma}_{t}\,\right\rVert_{W^{1,\infty}}\leq
C\left\lVert\rho^{\gamma}_{t}\,\right\rVert_{L^{\infty}}$, which implies
(3.7). ∎

Let us give a Lipschitz-type estimate for the interaction force $\nabla K$:

######  Lemma 3.3.

Assume that $K$ satisfy Assumption 2–3. Let $X^{\gamma},X$ be two random
variables with density $\rho^{\gamma},\rho\in\mathcal{P}_{2}\cap
L^{\infty}(\mathbb{R}^{d})$ such that

$C_{\infty}:=\max\\{\|\rho^{\gamma}\|_{L^{\infty}},\|\rho\|_{L^{\infty}}\\}<\infty\,.$
(3.12)

Then it holds that

$\mathbb{E}[|\nabla K\ast\rho^{\gamma}(X^{\gamma})-\nabla
K\ast\rho(X)|^{2}]\leq C\left(\left\lVert\nabla
K\ast\rho^{\gamma}\,\right\rVert_{W^{1,\infty}},C_{\infty},\left\lVert\nabla^{2}K\,\right\rVert_{L^{1}(B_{2R})}^{2},C_{K}^{\prime}\right)\mathbb{E}[|X^{\gamma}-X|^{2}]$
(3.13)

or

$\mathbb{E}[|\nabla K\ast\rho^{\gamma}(X^{\gamma})-\nabla
K\ast\rho(X)|^{2}]\leq C\left(\left\lVert\nabla
K\ast\rho^{\gamma}\,\right\rVert_{W^{1,\infty}},C_{\infty}\right)\mathbb{E}[|X^{\gamma}-X|^{2}]\,.$
(3.14)

###### Proof.

Let us split the error

$\displaystyle|\nabla K\ast\rho^{\gamma}(X^{\gamma})-\nabla
K\ast\rho(X)|^{2}=2|\nabla K\ast\rho^{\gamma}(X^{\gamma})-\nabla
K\ast\rho^{\gamma}(X)|^{2}+2|\nabla K\ast(\rho^{\gamma}-\rho)(X)|^{2}$
$\displaystyle\leq$ $\displaystyle 2\left\lVert\nabla
K\ast\rho^{\gamma}\,\right\rVert_{W^{1,\infty}}|X^{\gamma}-X|^{2}+2|\nabla
K\ast(\rho^{\gamma}-\rho)(X)|^{2}\,.$ (3.15)

The following proof will be divided into two cases:

If $K$ satisfies Assumption 2 and $\nabla K\in W^{1,1}(B_{2R})$, then

$\displaystyle|\nabla K\ast(\rho^{\gamma}-\rho)(X)|$
$\displaystyle\leq\left|\int_{(X-y)\in B_{R}}\nabla
K(X-y)(\rho^{\gamma}-\rho)(y)dy\right|+\left|\int_{(X-y)\in\mathbb{R}^{d}\backslash
B_{R}}\nabla K(X-y)(\rho^{\gamma}-\rho)(y)dy\right|$
$\displaystyle\leq\left|\int_{(X-y)\in B_{R}}\nabla
K(X-y)(\rho^{\gamma}-\rho)(y)dy\right|+\left\lVert\nabla
K\,\right\rVert_{\mbox{Lip}(\mathbb{R}^{d}\backslash
B_{R})}W_{1}(\rho^{\gamma},\rho)\,,$ (3.16)

where we have used the Kantorovich duality (1.13) in the second inequality.
Notice that according to the estimate $(2)$ in [choi2020quantified, Theorem
3.3] that

$\displaystyle\mathbb{E}\left[\left|\int_{(X-y)\in B_{R}}\nabla
K(X-y)(\rho^{\gamma}-\rho)(y)dy\right|^{2}\right]\leq
C_{\infty}\int_{\mathbb{R}^{d}}\left|\int_{(x-y)\in B_{R}}\nabla
K(x-y)(\rho^{\gamma}-\rho)(y)dy\right|^{2}dx$ $\displaystyle\leq$
$\displaystyle
C_{\infty}\left\lVert\nabla^{2}K\,\right\rVert_{L^{1}(B_{2R})}^{2}W_{2}^{2}(\rho^{\gamma},\rho)\,.$
(3.17)

Thus we have

$\displaystyle\mathbb{E}[|\nabla K\ast(\rho^{\gamma}-\rho)(X)|^{2}]$
$\displaystyle\leq
2C_{\infty}\left\lVert\nabla^{2}K\,\right\rVert_{L^{1}(B_{2R})}^{2}W_{2}^{2}(\rho^{\gamma},\rho)+2\left\lVert\nabla
K\,\right\rVert_{\mbox{Lip}(\mathbb{R}^{d}\backslash
B_{R})}^{2}W_{1}^{2}(\rho^{\gamma},\rho)$
$\displaystyle\leq\left(2C_{\infty}\left\lVert\nabla^{2}K\,\right\rVert_{L^{1}(B_{2R})}^{2}+2C_{K}^{\prime
2}\right)W_{2}^{2}(\rho^{\gamma},\rho)$
$\displaystyle\leq\left(2C_{\infty}\left\lVert\nabla^{2}K\,\right\rVert_{L^{1}(B_{2R})}^{2}+2C_{K}^{\prime
2}\right)\mathbb{E}[|X^{\gamma}-X|^{2}]\,.$ (3.18)

Then it follows from (3) that

$\displaystyle\mathbb{E}[|\nabla K\ast\rho^{\gamma}(X^{\gamma})-\nabla
K\ast\rho(X)|^{2}]$ $\displaystyle\leq$ $\displaystyle 2\left\lVert\nabla
K\ast\rho^{\gamma}\,\right\rVert_{W^{1,\infty}}\mathbb{E}[|X^{\gamma}-X|^{2}]+\left(4C_{\infty}\left\lVert\nabla^{2}K\,\right\rVert_{L^{1}(B_{2R})}^{2}+4C_{K}^{\prime
2}\right)\mathbb{E}[|X^{\gamma}-X|^{2}]\,,$ (3.19)

which proves (3.13).

If $K$ satisfies Assumption 2 and it is given by Newtonian potential,
according to $(3)$ in [choi2020quantified, Theorem 3.3] one has

$\left\lVert\nabla K\ast(\rho^{\gamma}-\rho)\,\right\rVert_{L^{2}}^{2}\leq
C_{\infty}W_{2}^{2}(\rho^{\gamma},\rho)\leq
C_{\infty}\mathbb{E}[|X^{\gamma}-X|^{2}]\,.$ (3.20)

Then taking expectation on both sides of (3) leads to

$\displaystyle\mathbb{E}[|\nabla K\ast\rho^{\gamma}(X^{\gamma})-\nabla
K\ast\rho(X)|^{2}]\leq 2\left\lVert\nabla
K\ast\rho^{\gamma}\,\right\rVert_{W^{1,\infty}}\mathbb{E}[|X^{\gamma}-X|^{2}]+2\mathbb{E}[|\nabla
K\ast(\rho^{\gamma}-\rho)(X)|^{2}]$ $\displaystyle\leq$ $\displaystyle
2\left\lVert\nabla
K\ast\rho^{\gamma}\,\right\rVert_{W^{1,\infty}}\mathbb{E}[|X^{\gamma}-X|^{2}]+2C_{\infty}\left\lVert\nabla
K\ast(\rho^{\gamma}-\rho)\,\right\rVert_{L^{2}}^{2}$ $\displaystyle\leq$
$\displaystyle\left(2\left\lVert\nabla
K\ast\rho^{\gamma}\,\right\rVert_{W^{1,\infty}}+2C_{\infty}\right)\mathbb{E}[|X^{\gamma}-X|^{2}]\,.$
(3.21)

This yields (3.14). ∎

Now we can prove the boundness of the second moment uniformly in $\gamma$. In
the following we shall use $C>0$ to denote a generic constant independent of
$\gamma$ even though it is different from line to line.

######  Theorem 3.2.

Assume that $\Phi$ satisfy Assumption 1 and $K$ satisfy Assumption 2–3. Let
$(X^{\gamma}_{t},V^{\gamma}_{t})_{t\in[0,T_{p}]}$ be the unique solution to
(1.5) up to time $T_{p}$ with the initial data
$\mbox{Law}(X_{0},V_{0})=f_{0}\in\mathcal{P}_{2}\cap
W_{x,H}^{1,p}(\mathbb{R}^{2d})$, $p>\max\\{d,q/(q-1)\\}$. It holds that

$\sup_{\gamma\geq
1}\sup_{t\in[0,T_{p}]}\mathbb{E}[|X_{t}^{\gamma}|^{2}]<\infty\,.$ (3.22)

###### Proof.

It follows from the same argument as in the Step 1 of Theorem 2.2 that

$\displaystyle\mathbb{E}[|X_{t}^{\gamma}|^{2}]\leq
C+C\int_{0}^{t}\mathbb{E}[|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}]ds\,,$
(3.23)

where $C$ is independent of $\gamma$. It follows from (1.14) and (3.7) that

$\displaystyle\mathbb{E}[|F(X_{s}^{\gamma},\rho_{s}^{\gamma})|^{2}]$
$\displaystyle=\mathbb{E}[|\nabla\Phi(X_{s}^{\gamma})+\nabla
K\ast\rho^{\gamma}_{s}(X_{s}^{\gamma})|^{2}]\leq
2\mathbb{E}[|\nabla\Phi(X_{s}^{\gamma})|^{2}]+C$ $\displaystyle\leq
2\mathbb{E}[|C_{\Phi}(1+|X_{s}^{\gamma}|)|^{2}]+C\leq
C+C\mathbb{E}[|X_{s}^{\gamma}|^{2}]\,,$ (3.24)

which leads to

$\displaystyle\mathbb{E}[|X_{t}^{\gamma}|^{2}]\leq
C+C\int_{0}^{t}\mathbb{E}[|X_{s}^{\gamma}|^{2}]ds\,.$ (3.25)

Applying Gronwall’s inequality completes the proof. ∎

Using the theorem above we obtain the overdamped limit for the singular case:

######  Theorem 3.3.

Under the same assumptions as in Theorem 3.2. Let
$(X^{\gamma}_{t},V^{\gamma}_{t})_{t\in[0,T_{p}]}$ be the unique solution to
(1.5) up to time $T_{p}$, and $(X_{t})_{t\in[0,T_{p}]}$ be the unique solution
to (1.7). It holds that

$\sup_{t\in[0,T_{p}]}\mathbb{E}[|X^{\gamma}_{t}-X_{t}|^{2}]\leq\frac{C}{\gamma^{2}}e^{CT}\,,$
(3.26)

where $C>0$ is independent of $\gamma\geq 1$.

###### Proof.

It follows from the same argument as in Theorem 2.3 that

$\displaystyle\mathbb{E}[|X^{\gamma}_{t}-X_{t}|^{2}]\leq
C\int_{0}^{t}\mathbb{E}[|F(X^{\gamma}_{s},\rho^{\gamma}_{s})-F(X_{s},\rho_{s})|^{2}]ds+C\frac{1}{\gamma^{2}}\,.$
(3.27)

Applying assumption (1.14) on $\Phi$, Lemma 3.2 and Lemma 3.3 one has

$\displaystyle\mathbb{E}[|F(X^{\gamma}_{s},\rho^{\gamma}_{s})-F(X_{s},\rho_{s})|^{2}]$
$\displaystyle\leq
2\mathbb{E}[|\nabla\Phi(X^{\gamma}_{s})-\nabla\Phi(X_{s})|^{2}]+2\mathbb{E}[|\nabla
K\ast\rho^{\gamma}_{s}(X^{\gamma}_{s})-\nabla K\ast\rho_{s}(X_{s})|^{2}]$
$\displaystyle\leq C\mathbb{E}[|X^{\gamma}_{s}-X_{s}|^{2}]\,,$ (3.28)

where $C$ is independent of $\gamma$. This implies

$\displaystyle\mathbb{E}[|X^{\gamma}_{t}-X_{t}|^{2}]\leq
C\int_{0}^{t}\mathbb{E}[|X^{\gamma}_{s}-X_{s}|^{2}]ds+C\frac{1}{\gamma^{2}}\,.$
(3.29)

Applying Gronwall’s inequality finishes the proof. ∎

## References