<figure><img src="image_1.png" /></figure>

HAL
open science

# The random walk penalised by its range in dimensions

$d \ge 3$

Nathanael Berestycki, Raphaël Cerf

► To cite this version:

Nathanael Berestycki, Raphaël Cerf. The random walk penalised by its range in dimensions $d \ge 3$. Annales Henri Lebesgue, 2021, 4, pp.1-79. 10.5802/ahl.66. hal-03998535

HAL Id: hal-03998535

https://hal.science/hal-03998535

Submitted on 15 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_1.png" /></figure>

ANNALES
HENRI LEBESGUE

NATHANAËL BERESTYCKI

RAPHAËL CERF

THE RANDOM WALK PENALISED
BY ITS RANGE IN
DIMENSIONS $d \ge 3$

LA MARCHE ALÉATOIRE PÉNALISÉE PAR
SON IMAGE EN DIMENSION $d \ge 3$

ABSTRACT. — We study a self-attractive random walk such that each trajectory of length $N$ is penalised by a factor proportional to $\exp(-|R_N|)$, where $R_N$ is the set of sites visited by the walk. We show that the range of such a walk is close to a solid Euclidean ball of radius approximately $\rho_d N^{1/(d+2)}$, for some explicit constant $\rho_d > 0$. This proves a conjecture of Bolthausen [Bol94] who obtained this result in the case $d=2$.

RÉSUMÉ. — Nous étudions une marche aléatoire auto-attractive, chaque trajectoire de longueur $N$ est pénalisée par un facteur proportionnel à $\exp(-|R_N|)$, où $R_N$ est l'ensemble des sites visités par la marche. Nous montrons que l'image d'une telle marche aléatoire est proche d'une boule Euclidienne dont le rayon est approximativement $\rho_d N^{1/(d+2)}$, avec une valeur explicite de la constante $\rho_d > 0$. Nous prouvons ainsi une conjecture de Bolthausen [Bol94], qui a obtenu ce résultat dans le cas $d=2$.

Keywords: Random walk, Faber-Krahn, large deviations.

2020 Mathematics Subject Classification: 60F05, 60G50, 82B41.

DOI: https://doi.org/10.5802/ahl.66

<footnote>(*) This project started in 2013, while RC was visiting Cambridge, thanks to the support of the IUF. NB's research was partly supported by EPSRC grants EP/L018896/1 and EP/I03372X/1.</footnote>
<figure><img src="image_3.png" /></figure>

ANNALES
HENRI LEBESGUE

NATHANAËL BERESTYCKI

RAPHAËL CERF

THE RANDOM WALK PENALISED
BY ITS RANGE IN
DIMENSIONS $d \ge 3$

LA MARCHE ALÉATOIRE PÉNALISÉE PAR
SON IMAGE EN DIMENSION $d \ge 3$

ABSTRACT. — We study a self-attractive random walk such that each trajectory of length $N$ is penalised by a factor proportional to $\exp(-|R_N|)$, where $R_N$ is the set of sites visited by the walk. We show that the range of such a walk is close to a solid Euclidean ball of radius approximately $\rho_d N^{1/(d+2)}$, for some explicit constant $\rho_d > 0$. This proves a conjecture of Bolthausen [Bol94] who obtained this result in the case $d=2$.

RÉSUMÉ. — Nous étudions une marche aléatoire auto-attractive, chaque trajectoire de longueur $N$ est pénalisée par un facteur proportionnel à $\exp(-|R_N|)$, où $R_N$ est l'ensemble des sites visités par la marche. Nous montrons que l'image d'une telle marche aléatoire est proche d'une boule Euclidienne dont le rayon est approximativement $\rho_d N^{1/(d+2)}$, avec une valeur explicite de la constante $\rho_d > 0$. Nous prouvons ainsi une conjecture de Bolthausen [Bol94], qui a obtenu ce résultat dans le cas $d=2$.

Keywords: Random walk, Faber-Krahn, large deviations.

2020 Mathematics Subject Classification: 60F05, 60G50, 82B41.

DOI: https://doi.org/10.5802/ahl.66

<footnote>(*) This project started in 2013, while RC was visiting Cambridge, thanks to the support of the IUF. NB's research was partly supported by EPSRC grants EP/L018896/1 and EP/I03372X/1.</footnote>
CONTENTS

<table><tr><td>1. Introduction</td><td>3</td></tr><tr><td>1.1. Main results</td><td>3</td></tr><tr><td>1.2. Heuristics</td><td>5</td></tr><tr><td>Warning</td><td>6</td></tr><tr><td>1.3. Relation with other works</td><td>6</td></tr><tr><td>Acknowledgements</td><td>8</td></tr><tr><td>2. Further results and organisation of the paper</td><td>8</td></tr><tr><td>2.1. Preliminary lower bound on the partition function</td><td>8</td></tr><tr><td>2.2. Upper bound on the numerator</td><td>9</td></tr><tr><td>2.3. Organisation of paper</td><td>9</td></tr><tr><td>2.3.1. Main steps in the proof of Theorem 1.2.</td><td>11</td></tr><tr><td>3. Martingale estimates</td><td>13</td></tr><tr><td>3.1. The classical martingale</td><td>13</td></tr><tr><td>3.2. The fundamental inequality</td><td>13</td></tr><tr><td>3.3. Estimate for a fixed profile</td><td>14</td></tr><tr><td>3.4. Donsker-Varadhan estimate for the random walk in the full space</td><td>15</td></tr><tr><td>3.5. Correction for the origin</td><td>21</td></tr><tr><td>4. A priori estimates</td><td>24</td></tr><tr><td>4.1. Control of the range</td><td>24</td></tr><tr><td>4.2. Control of the Dirichlet energy</td><td>25</td></tr><tr><td>4.3. High density blocks</td><td>26</td></tr><tr><td>4.4. Local averaging</td><td>27</td></tr><tr><td>5. Upper bound: proof of Theorem 2.2</td><td>28</td></tr><tr><td>5.1. The coarse grained profile</td><td>29</td></tr><tr><td>5.2. Continuation of proof of Theorem 2.2</td><td>31</td></tr><tr><td>5.3. Truncation</td><td>35</td></tr><tr><td>5.4. End of proof of Theorem 2.2</td><td>36</td></tr><tr><td>6. Continuous version of Theorem 2.2</td><td>42</td></tr><tr><td>6.1. Linear interpolation</td><td>42</td></tr><tr><td>6.2. Rescaling</td><td>45</td></tr><tr><td>7. Application of the quantitative Faber-Krahn inequality</td><td>51</td></tr><tr><td>7.1. Statement</td><td>51</td></tr><tr><td>7.2. Application of Faber-Krahn: proof of Theorem 1.1</td><td>57</td></tr><tr><td>8. Filling the ball and proof of Theorem 1.2</td><td>59</td></tr><tr><td>8.1. Time spent in mesoscopic balls</td><td>60</td></tr><tr><td>8.2. Bridges in mesoscopic balls</td><td>61</td></tr><tr><td>8.3. Conditioning and summation</td><td>67</td></tr><tr><td>8.4. Transition probabilities for bridges</td><td>68</td></tr><tr><td>8.5. End of proof of Theorem 8.1</td><td>73</td></tr><tr><td>Appendix A. Functional inequalities on the rescaled lattice</td><td>75</td></tr><tr><td>Appendix B. Inequalities on the original lattice</td><td>77</td></tr><tr><td>References</td><td>78</td></tr></table>
CONTENTS

<table><tr><td>1. Introduction</td><td>3</td></tr><tr><td>1.1. Main results</td><td>3</td></tr><tr><td>1.2. Heuristics</td><td>5</td></tr><tr><td>Warning</td><td>6</td></tr><tr><td>1.3. Relation with other works</td><td>6</td></tr><tr><td>Acknowledgements</td><td>8</td></tr><tr><td>2. Further results and organisation of the paper</td><td>8</td></tr><tr><td>2.1. Preliminary lower bound on the partition function</td><td>8</td></tr><tr><td>2.2. Upper bound on the numerator</td><td>9</td></tr><tr><td>2.3. Organisation of paper</td><td>9</td></tr><tr><td>2.3.1. Main steps in the proof of Theorem 1.2.</td><td>11</td></tr><tr><td>3. Martingale estimates</td><td>13</td></tr><tr><td>3.1. The classical martingale</td><td>13</td></tr><tr><td>3.2. The fundamental inequality</td><td>13</td></tr><tr><td>3.3. Estimate for a fixed profile</td><td>14</td></tr><tr><td>3.4. Donsker-Varadhan estimate for the random walk in the full space</td><td>15</td></tr><tr><td>3.5. Correction for the origin</td><td>21</td></tr><tr><td>4. A priori estimates</td><td>24</td></tr><tr><td>4.1. Control of the range</td><td>24</td></tr><tr><td>4.2. Control of the Dirichlet energy</td><td>25</td></tr><tr><td>4.3. High density blocks</td><td>26</td></tr><tr><td>4.4. Local averaging</td><td>27</td></tr><tr><td>5. Upper bound: proof of Theorem 2.2</td><td>28</td></tr><tr><td>5.1. The coarse grained profile</td><td>29</td></tr><tr><td>5.2. Continuation of proof of Theorem 2.2</td><td>31</td></tr><tr><td>5.3. Truncation</td><td>35</td></tr><tr><td>5.4. End of proof of Theorem 2.2</td><td>36</td></tr><tr><td>6. Continuous version of Theorem 2.2</td><td>42</td></tr><tr><td>6.1. Linear interpolation</td><td>42</td></tr><tr><td>6.2. Rescaling</td><td>45</td></tr><tr><td>7. Application of the quantitative Faber-Krahn inequality</td><td>51</td></tr><tr><td>7.1. Statement</td><td>51</td></tr><tr><td>7.2. Application of Faber-Krahn: proof of Theorem 1.1</td><td>57</td></tr><tr><td>8. Filling the ball and proof of Theorem 1.2</td><td>59</td></tr><tr><td>8.1. Time spent in mesoscopic balls</td><td>60</td></tr><tr><td>8.2. Bridges in mesoscopic balls</td><td>61</td></tr><tr><td>8.3. Conditioning and summation</td><td>67</td></tr><tr><td>8.4. Transition probabilities for bridges</td><td>68</td></tr><tr><td>8.5. End of proof of Theorem 8.1</td><td>73</td></tr><tr><td>Appendix A. Functional inequalities on the rescaled lattice</td><td>75</td></tr><tr><td>Appendix B. Inequalities on the original lattice</td><td>77</td></tr><tr><td>References</td><td>78</td></tr></table>
# 1. Introduction

## 1.1. Main results

Let $P$ be the law of the discrete-time simple random walk $(S_n)_{n \in \mathbb{N}}$ on $\mathbb{Z}^d$, $d \ge 1$, starting from the origin. Let $N$ be a positive integer. In [Bol94], Bolthausen proposed the following model for a self-attractive random walk: let us denote by $R_N$ the set of the points visited by the random walk until time $N$ and by $|R_N|$ its cardinality. We define a new probability on the set of the $N$-steps trajectories by setting

$$ (1.1) \qquad \frac{d\tilde{P}_N}{dP} = \frac{1}{Z_N} \exp(-|R_N|), $$

where the normalization factor (or partition function) $Z_N$ is given by

$$ (1.2) \qquad Z_N = E\left(\exp\left(-|R_N|\right)\right). $$

Clearly, $\tilde{P}_N$ favours configurations where the trajectory is localised on a small number of points. Bolthausen asked what can be said about a typical realisation of $\tilde{P}_N$. The question is particularly natural from the point of view of large deviations theory. Indeed one of the early successes of the theory, due to Donsker and Varadhan [DV75], was a determination of the first order asymptotics of the partition function $Z_N$:

$$ (1.3) \qquad Z_N = \exp\left(-\left(1 + o(1)\right)\chi_d N^{d/d+2}\right), $$

for some $\chi_d > 0$ depending only on the dimension. Bolthausen was able to show that in dimension $d=2$, under $\tilde{P}_N$ a typical trajectory localises on a Euclidean ball of radius approximately $\rho_2 N^{1/4}$ for some constant $\rho_2 > 0$. His analysis strongly suggests that in general dimensions $d \ge 3$, a similar result holds except that the walk now localises on a ball of radius approximately $\rho_d N^{1/(d+2)}$, where $\rho_d > 0$ is a specific constant depending only on the ambient dimension $d$.

The main goal of this paper is to verify Bolthausen's conjecture. Bolthausen actually provided support for his conjecture by showing that two (admittedly crucial) estimates implied the conjecture in general dimension $d \ge 2$; these two estimates were in turn proved for $d=2$. The two Theorems 1.1 and 1.2 below provide a proof of these two estimates in the general case $d \ge 3$, thereby proving as a corollary of Bolthausen's paper [Bol94] that his conjecture is true and hence completing his programme. We now state below these two results from which Bolthausen's conjecture follows.

We suppose without loss of generality that

$$ n = N^{1/(d+2)} $$

is an integer. We define the local time $L_N$ as

$$ \forall x \in \mathbb{Z}^d \quad L_N(x) = \sum_{k=0}^{N-1} 1_{\{S_k=x\}}. $$

We define the continuous rescaled version $\ell_N$ of $L_N$ by

$$ (1.4) \qquad \forall x \in \mathbb{R}^d \quad \ell_N(x) = \frac{n^d}{N} L_N(\lfloor nx \rfloor). $$
# 1. Introduction

## 1.1. Main results

Let $P$ be the law of the discrete-time simple random walk $(S_n)_{n \in \mathbb{N}}$ on $\mathbb{Z}^d$, $d \ge 1$, starting from the origin. Let $N$ be a positive integer. In [Bol94], Bolthausen proposed the following model for a self-attractive random walk: let us denote by $R_N$ the set of the points visited by the random walk until time $N$ and by $|R_N|$ its cardinality. We define a new probability on the set of the $N$-steps trajectories by setting

$$ (1.1) \qquad \frac{d\tilde{P}_N}{dP} = \frac{1}{Z_N} \exp(-|R_N|), $$

where the normalization factor (or partition function) $Z_N$ is given by

$$ (1.2) \qquad Z_N = E\left(\exp\left(-|R_N|\right)\right). $$

Clearly, $\tilde{P}_N$ favours configurations where the trajectory is localised on a small number of points. Bolthausen asked what can be said about a typical realisation of $\tilde{P}_N$. The question is particularly natural from the point of view of large deviations theory. Indeed one of the early successes of the theory, due to Donsker and Varadhan [DV75], was a determination of the first order asymptotics of the partition function $Z_N$:

$$ (1.3) \qquad Z_N = \exp\left(-\left(1 + o(1)\right)\chi_d N^{d/d+2}\right), $$

for some $\chi_d > 0$ depending only on the dimension. Bolthausen was able to show that in dimension $d = 2$, under $\tilde{P}_N$ a typical trajectory localises on a Euclidean ball of radius approximately $\rho_2 N^{1/4}$ for some constant $\rho_2 > 0$. His analysis strongly suggests that in general dimensions $d \ge 3$, a similar result holds except that the walk now localises on a ball of radius approximately $\rho_d N^{1/(d+2)}$, where $\rho_d > 0$ is a specific constant depending only on the ambient dimension $d$.

The main goal of this paper is to verify Bolthausen's conjecture. Bolthausen actually provided support for his conjecture by showing that two (admittedly crucial) estimates implied the conjecture in general dimension $d \ge 2$; these two estimates were in turn proved for $d = 2$. The two Theorems 1.1 and 1.2 below provide a proof of these two estimates in the general case $d \ge 3$, thereby proving as a corollary of Bolthausen's paper [Bol94] that his conjecture is true and hence completing his programme. We now state below these two results from which Bolthausen's conjecture follows.

We suppose without loss of generality that

$$ n = N^{1/(d+2)} $$

is an integer. We define the local time $L_N$ as

$$ \forall x \in \mathbb{Z}^d \quad L_N(x) = \sum_{k=0}^{N-1} 1_{\{S_k=x\}}. $$

We define the continuous rescaled version $\ell_N$ of $L_N$ by

$$ (1.4) \qquad \forall x \in \mathbb{R}^d \quad \ell_N(x) = \frac{n^d}{N} L_N(\lfloor nx \rfloor). $$
For $x \in \mathbb{R}^d$, we let $\phi_x$ be the principal eigenfunction (normalised so that $\|\phi_x\|_2^2 := \int_{\mathbb{R}^d} \phi_x^2 = 1)$ of $-\Delta$ in $B(x, \rho_d)$, with Dirichlet boundary conditions. We denote by $L^1(\mathbb{R}^d)$ the set of the integrable Borel functions on $\mathbb{R}^d$ and we use the standard norm:

$$ \forall f \in L^1(\mathbb{R}^d) \quad \|f\|_1 = \int_{\mathbb{R}^d} |f(x)|dx. $$

The first result below is a quantitative shape theorem in the $L^1$ sense for the local time profile at time $N$.

**THEOREM 1.1.** — Let $\mathcal{L}_n$ be the set of functions defined by

$$ \mathcal{L}_n = \left\{ \ell \in L^1(\mathbb{R}^d) : \|\ell\|_1 = 1, \ell \ge 0, \inf_{x \in \mathbb{R}^d} \left\| \ell - (\phi_x)^2 \right\|_1 \ge 1/n^{1/800} \right\}. $$

For $n$ large enough, we have

$$ (1.5) \qquad E\left(e^{-|R_N|}; \ell_N \in \mathcal{L}_n\right) \le \exp\left(-n^d \chi_d - n^{d-\frac{1}{7}}\right) $$

where $\chi_d$ is as in (1.3).

The upper bound obtained in formula (1.5) is in fact negligible compared to the partition function $Z_N$. This is a consequence of another result of [Bol94] which is recalled in Proposition 2.1.

The second main result says that if $x$ is such that $\ell_N$ is close to $(\phi_x)^2$ in the $L^1$ sense above, then actually almost all of the ball of radius $\rho_d n$ around $x$ has been filled by the range of the walk. More precisely, set

$$ \mathcal{G}_{\text{loc},x} = \left\{ \|\ell_N - (\phi_x)^2\|_1 \le \frac{1}{n^{1/800}} \right\}. $$

For $\kappa > 0$ and $x \in \mathbb{R}^d$, we define

$$ \mathcal{R}_{\kappa, x} = \left\{ \forall z \in B(x, \rho_d n(1 - n^{-\kappa})), \ell_N(z) > 0 \right\}. $$

This is the event that the ball of radius $\rho_d n(1 - n^{-\kappa})$ around $x$ is filled.

**THEOREM 1.2.** — There exists $\kappa > 0$ such that, for any $a > 0$,

$$ \frac{1}{Z_N} E \left( e^{-|R_N|}; \mathcal{G}_{\text{loc},x} ; (\mathcal{R}_{\kappa,x})^c \right) = o(N^{-a}). $$

Together with Bolthausen's results [Bol94, see p. 877, immediately below Conjecture 1.3], Theorems 1.1 and 1.2 immediately imply the following Corollary 1.3, which is the main conclusion of our paper.

**COROLLARY 1.3.** — Let us denote by $B(x, r)$ the $d$ dimensional Euclidean ball centered at $x$ of radius $r$. There exists a positive constant $\rho_d$, which depends only on the dimension $d$, such that, for any $\varepsilon > 0$, as $N \to \infty$,

$$ \tilde{P}_N \left( \exists x \in \mathbb{R}^d \ B(x, \rho_d(1-\varepsilon)N^{\frac{1}{d+2}}) \cap \mathbb{Z}^d \subset R_N \subset B(x, \rho_d(1+\varepsilon)N^{\frac{1}{d+2}}) \right) \to 1. $$

We mention here a result obtained along the way, which we feel is interesting in its own right. This is a Donsker-Varadhan large deviation estimate which is valid for the random walk in the full space $\mathbb{Z}^d$, and so bypasses the assumption of compactness
For $x \in \mathbb{R}^d$, we let $\phi_x$ be the principal eigenfunction (normalised so that $\|\phi_x\|_2^2 := \int_{\mathbb{R}^d} \phi_x^2 = 1)$ of $-\Delta$ in $B(x, \rho_d)$, with Dirichlet boundary conditions. We denote by $L^1(\mathbb{R}^d)$ the set of the integrable Borel functions on $\mathbb{R}^d$ and we use the standard norm:

$$ \forall f \in L^1(\mathbb{R}^d) \quad \|f\|_1 = \int_{\mathbb{R}^d} |f(x)|dx. $$

The first result below is a quantitative shape theorem in the $L^1$ sense for the local time profile at time $N$.

**THEOREM 1.1.** — Let $\mathcal{L}_n$ be the set of functions defined by

$$ \mathcal{L}_n = \left\{ \ell \in L^1(\mathbb{R}^d) : \|\ell\|_1 = 1, \ell \ge 0, \inf_{x \in \mathbb{R}^d} \|\ell - (\phi_x)^2\|_1 \ge 1/n^{1/800} \right\}. $$

For $n$ large enough, we have

$$ (1.5) \qquad E\left(e^{-|R_N|}; \ell_N \in \mathcal{L}_n\right) \le \exp\left(-n^d \chi_d - n^{d-\frac{1}{7}}\right) $$

where $\chi_d$ is as in (1.3).

The upper bound obtained in formula (1.5) is in fact negligible compared to the partition function $Z_N$. This is a consequence of another result of [Bol94] which is recalled in Proposition 2.1.

The second main result says that if $x$ is such that $\ell_N$ is close to $(\phi_x)^2$ in the $L^1$ sense above, then actually almost all of the ball of radius $\rho_d n$ around $x$ has been filled by the range of the walk. More precisely, set

$$ \mathcal{G}_{\text{loc},x} = \left\{ \|\ell_N - (\phi_x)^2\|_1 \le \frac{1}{n^{1/800}} \right\}. $$

For $\kappa > 0$ and $x \in \mathbb{R}^d$, we define

$$ \mathcal{R}_{\kappa, x} = \left\{ \forall z \in B(x, \rho_d n(1 - n^{-\kappa})), \ell_N(z) > 0 \right\}. $$

This is the event that the ball of radius $\rho_d n(1 - n^{-\kappa})$ around $x$ is filled.

**THEOREM 1.2.** — There exists $\kappa > 0$ such that, for any $a > 0$,

$$ \frac{1}{Z_N} E \left( e^{-|R_N|}; \mathcal{G}_{\text{loc},x} ; (\mathcal{R}_{\kappa,x})^c \right) = o(N^{-a}). $$

Together with Bolthausen's results [Bol94, see p. 877, immediately below Conjecture 1.3], Theorems 1.1 and 1.2 immediately imply the following Corollary 1.3, which is the main conclusion of our paper.

**COROLLARY 1.3.** — Let us denote by $B(x, r)$ the $d$ dimensional Euclidean ball centered at $x$ of radius $r$. There exists a positive constant $\rho_d$, which depends only on the dimension $d$, such that, for any $\varepsilon > 0$, as $N \to \infty$,

$$ \tilde{P}_N \left( \exists x \in \mathbb{R}^d \ B(x, \rho_d(1-\varepsilon)N^{\frac{1}{d+2}}) \cap \mathbb{Z}^d \subset R_N \subset B(x, \rho_d(1+\varepsilon)N^{\frac{1}{d+2}}) \right) \to 1. $$

We mention here a result obtained along the way, which we feel is interesting in its own right. This is a Donsker-Varadhan large deviation estimate which is valid for the random walk in the full space $\mathbb{Z}^d$, and so bypasses the assumption of compactness
for the state space which underlies [DV75]. Let $D$ be an arbitrary finite subset of $\mathbb{Z}^d$. For $t \in \mathbb{N}$, we define

$$ \tau(D, t) = \inf \{ k \ge 1 : L_k(D) = t \} $$

and we set

$$ \forall x \in D \quad L_t^D(x) = L_{\tau(D, t)} = \sum_{k=0}^{\tau(D, t)-1} 1_{\{S_k=x\}}. $$

The function $L_t^D$ is a function from $D$ to $\mathbb{N}$. We shall work in the functional space $\ell^1(D)$ equipped with the norm

$$ \forall f \in \ell^1(D) \quad \|f\|_{1, D} = \sum_{x \in D} |f(x)|. $$

For a function $f: \mathbb{Z}^d \to \mathbb{R}$, we define

$$ (1.6) \qquad \mathcal{E}(f, D) = \frac{1}{2d} \sum_{y, z \in D : |y-z|=1} (f(y) - f(z))^2. $$

We define $\bar{D}$ as

$$ \bar{D} = D \cup \{ x \in \mathbb{Z}^d : \exists \ y \in D \quad |x - y| = 1 \}. $$

When $D = \mathbb{Z}^d$ we will simply write $\|f\|_1$ and $\mathcal{E}(f)$.

**THEOREM 1.4.** — Let $C$ be a closed convex subset of $\ell^1(D)$. For any $t \ge 1$, we have

$$ \inf_{x \in \bar{D}} P_x \left( \frac{1}{t} L_t^D \in C, \tau(D, t) < \infty \right) \le \exp \left( -t \inf_{h \in C} \frac{1}{2} \mathcal{E}(\sqrt{h}, D) \right). $$

## 1.2. Heuristics

We begin a discussion of the above results (such as Corollary 1.3) with a rough heuristics explaining where the limit shape comes from. Note that a random walk will stay in a box of diameter $n$ for duration $N$ with probability approximately $\exp(-O(N/n^2))$, since it may leave this box with positive probability every $n^2$ units of time. On the other hand, the energetic contribution to (1.2) of such configurations is of order $\exp(-n^d)$. Balancing entropy and energy, we expect that the trajectories that contribute most to (1.2) are such that $n \asymp N^{1/(d+2)}$, which explains the scaling in Corollary 1.3. We now discuss this in a bit more detail, but still ignoring many technical details.

If $U \subset \mathbb{R}^d$ is an open bounded subset, and $n = N^{1/(d+2)}$ is as above, then the probability for the random walk to remain in $nU$ for a long time $N$ is approximately $\exp(-\lambda_U N/(2n^2))$, where $\lambda_U$ is the principal eigenvalue of $-\Delta$ in $U$ with Dirichlet boundary conditions on $\partial U$. Hence the contribution to (1.2) coming from trajectories staying in $nU$ should be well approximated by $\exp(-n^d(\lambda_U/2 + |U|))$, where $|U|$ is the Lebesgue measure of $U$. Using the Faber-Krahn inequality, it can be seen that $\inf_U \{\lambda_U/2 + |U|\}$ is attained when $U$ is a Euclidean ball of radius $r$, say. The radius $r$ can then be determined by noting that principal eigenvalues obey diffusive scaling,
for the state space which underlies [DV75]. Let $D$ be an arbitrary finite subset of $\mathbb{Z}^d$. For $t \in \mathbb{N}$, we define

$$ \tau(D, t) = \inf \{ k \ge 1 : L_k(D) = t \} $$

and we set

$$ \forall x \in D \quad L_t^D(x) = L_{\tau(D, t)} = \sum_{k=0}^{\tau(D, t)-1} 1_{\{S_k=x\}}. $$

The function $L_t^D$ is a function from $D$ to $\mathbb{N}$. We shall work in the functional space $\ell^1(D)$ equipped with the norm

$$ \forall f \in \ell^1(D) \quad \|f\|_{1, D} = \sum_{x \in D} |f(x)|. $$

For a function $f: \mathbb{Z}^d \to \mathbb{R}$, we define

$$ (1.6) \qquad \mathcal{E}(f, D) = \frac{1}{2d} \sum_{y, z \in D: |y-z|=1} (f(y) - f(z))^2. $$

We define $\bar{D}$ as

$$ \bar{D} = D \cup \{ x \in \mathbb{Z}^d : \exists \ y \in D \quad |x - y| = 1 \}. $$

When $D = \mathbb{Z}^d$ we will simply write $\|f\|_1$ and $\mathcal{E}(f)$.

**THEOREM 1.4.** — Let $C$ be a closed convex subset of $\ell^1(D)$. For any $t \ge 1$, we have

$$ \inf_{x \in \bar{D}} P_x \left( \frac{1}{t} L_t^D \in C, \tau(D, t) < \infty \right) \le \exp \left( -t \inf_{h \in C} \frac{1}{2} \mathcal{E}(\sqrt{h}, D) \right). $$

## 1.2. Heuristics

We begin a discussion of the above results (such as Corollary 1.3) with a rough heuristics explaining where the limit shape comes from. Note that a random walk will stay in a box of diameter $n$ for duration $N$ with probability approximately $\exp(-O(N/n^2))$, since it may leave this box with positive probability every $n^2$ units of time. On the other hand, the energetic contribution to (1.2) of such configurations is of order $\exp(-n^d)$. Balancing entropy and energy, we expect that the trajectories that contribute most to (1.2) are such that $n \asymp N^{1/(d+2)}$, which explains the scaling in Corollary 1.3. We now discuss this in a bit more detail, but still ignoring many technical details.

If $U \subset \mathbb{R}^d$ is an open bounded subset, and $n = N^{1/(d+2)}$ is as above, then the probability for the random walk to remain in $nU$ for a long time $N$ is approximately $\exp(-\lambda_U N/(2n^2))$, where $\lambda_U$ is the principal eigenvalue of $-\Delta$ in $U$ with Dirichlet boundary conditions on $\partial U$. Hence the contribution to (1.2) coming from trajectories staying in $nU$ should be well approximated by $\exp(-n^d(\lambda_U/2 + |U|))$, where $|U|$ is the Lebesgue measure of $U$. Using the Faber-Krahn inequality, it can be seen that $\inf_U \{\lambda_U/2 + |U|\}$ is attained when $U$ is a Euclidean ball of radius $r$, say. The radius $r$ can then be determined by noting that principal eigenvalues obey diffusive scaling,
i.e., $\lambda_{B(r)} = \lambda/r^2$, where $\lambda$ is the principal eigenvalue in the unit ball. Hence, if $\omega_d$ is the volume of the unit ball, we deduce that $r = \rho_d$ is obtained as the minimiser of the following functional:

$$ \rho_d = \arg \min \left\{ \frac{\lambda}{2r^2} + \omega_d r^d : r > 0 \right\} = \left( \frac{\lambda}{d\omega_d} \right)^{1/(d+2)} $$

The constant $\rho_d$ is the one which appears in the theorem. As already mentioned, Bolthausen proved the corresponding result in two dimensions [Bol94]. The main problem to extend Bolthausen's proof to dimensions 3 and higher was to extend Lemma 3.1 and Proposition 4.1 from his paper [Bol94]. The rest of his proof is written for arbitrary dimensions $d \ge 3$ and it is solely the statement of these two lemmas which depend on $d$ being equal to 2 in his proof.

[Bol94, Lemma 3.1] can be seen as a quantitative Faber-Krahn inequality on the torus, saying that if a set $U$ is not far from minimising $\lambda_U/2 + |U|$ then $U$ itself is not far from a Euclidean ball. Unfortunately, such an inequality is not available yet in dimensions three and higher. Even an analogue of the quantitative isoperimetric inequality on the torus has not been proved so far. Therefore we cannot use the standard projection of the random walk on the torus, as in Bolthausen's proof. This creates a serious difficulty. Indeed, as far as the probabilistic estimates on the local time are concerned, it is very convenient to work on the torus: the state space of the walk becomes compact and one can readily use the classical large deviations estimates of Donsker and Varadhan [DV75]. The good news is that a quantitative Faber-Krahn inequality has been proved recently in $\mathbb{R}^d$ by Brasco, De Philippis and Velichkov [BDPV15]. Ultimately, we are to use this inequality. Therefore we have to deal with the random walk in the full space and we cannot afford the luxury of projecting its trajectories on the torus. A key point to carry out this program is to develop the relevant large deviations estimates. Indeed, the random walk being transient, the classical Donsker-Varadhan theory cannot be applied directly.

## Warning

In the probability literature, one usually works with the half-Laplacian $\Delta/2$, which is the infinitesimal generator of the Brownian motion. In Bolthausen's paper, the notation $\lambda(G)$ corresponds to half of the quantity defined above. We choose here to stick to the convention employed in the papers on the Faber-Krahn inequality.

## 1.3. Relation with other works

A Brownian analogue of Corollary 1.3 was proved in dimension $d = 2$ by Sznitman [Szn91] using the method of enlargement of obstacles. Very briefly, the starting point of this method (adapted to the discrete setting of this paper) consists in viewing the weighted probability measure $\tilde{P}_N$ as the annealed probability measure corresponding to a random walk in a random medium in which there is an obstacle
i.e., $\lambda_{B(r)} = \lambda/r^2$, where $\lambda$ is the principal eigenvalue in the unit ball. Hence, if $\omega_d$ is the volume of the unit ball, we deduce that $r = \rho_d$ is obtained as the minimiser of the following functional:

$$ \rho_d = \arg \min \left\{ \frac{\lambda}{2r^2} + \omega_d r^d : r > 0 \right\} = \left( \frac{\lambda}{d\omega_d} \right)^{1/(d+2)} . $$

The constant $\rho_d$ is the one which appears in the theorem. As already mentioned, Bolthausen proved the corresponding result in two dimensions [Bol94]. The main problem to extend Bolthausen's proof to dimensions 3 and higher was to extend Lemma 3.1 and Proposition 4.1 from his paper [Bol94]. The rest of his proof is written for arbitrary dimensions $d \ge 3$ and it is solely the statement of these two lemmas which depend on $d$ being equal to 2 in his proof.

[Bol94, Lemma 3.1] can be seen as a quantitative Faber-Krahn inequality on the torus, saying that if a set $U$ is not far from minimising $\lambda_U/2 + |U|$ then $U$ itself is not far from a Euclidean ball. Unfortunately, such an inequality is not available yet in dimensions three and higher. Even an analogue of the quantitative isoperimetric inequality on the torus has not been proved so far. Therefore we cannot use the standard projection of the random walk on the torus, as in Bolthausen's proof. This creates a serious difficulty. Indeed, as far as the probabilistic estimates on the local time are concerned, it is very convenient to work on the torus: the state space of the walk becomes compact and one can readily use the classical large deviations estimates of Donsker and Varadhan [DV75]. The good news is that a quantitative Faber-Krahn inequality has been proved recently in $\mathbb{R}^d$ by Brasco, De Philippis and Velichkov [BDPV15]. Ultimately, we are to use this inequality. Therefore we have to deal with the random walk in the full space and we cannot afford the luxury of projecting its trajectories on the torus. A key point to carry out this program is to develop the relevant large deviations estimates. Indeed, the random walk being transient, the classical Donsker-Varadhan theory cannot be applied directly.

### Warning

In the probability literature, one usually works with the half-Laplacian $\Delta/2$, which is the infinitesimal generator of the Brownian motion. In Bolthausen's paper, the notation $\lambda(G)$ corresponds to half of the quantity defined above. We choose here to stick to the convention employed in the papers on the Faber-Krahn inequality.

## 1.3. Relation with other works

A Brownian analogue of Corollary 1.3 was proved in dimension $d = 2$ by Sznitman [Szn91] using the method of enlargement of obstacles. Very briefly, the starting point of this method (adapted to the discrete setting of this paper) consists in viewing the weighted probability measure $\tilde{P}_N$ as the annealed probability measure corresponding to a random walk in a random medium in which there is an obstacle
at every site with probability $1 - e^{-1}$. Note that $e^{-|R_N|}$ then corresponds to the annealed probability that the walk has not encountered any obstacle for time $N$.

A refinement of this method enabled Povel [Pov99] to establish the same result in dimension $d \ge 3$. It is important to note however that in the continuum, one cannot of course hope that the range of Brownian motion will fill a ball completely – there will always be small holes. For this reason, both results in [Szn91] and [Pov99] are restricted to a statement of the so-called confinement property, i.e., a statement that the range is contained in a ball of the appropriate radius (corresponding to $R = \rho_d n(1 + \varepsilon)$ in our setup). The question of whether the range will visit any macroscopic ball within this ball of radius $R$ is only addressed tangentially, see e.g. [Szn91, Theorem 4.3] and the discussion at the end of Section 1 in [Pov99]. Needless to say, the method of enlargement of obstacles is very different from the strategy employed by Bolthausen in [Bol94]. Curiously, neither [Szn91] nor [Pov99] discuss what their results imply for the discrete case, though both briefly mention the paper [Bol94].

At the time we were finishing this paper, we learnt of the independent and nearly simultaneous work of Ding, Fukushima, Sun and Xu [DFSX18], who obtained an alternative proof of Corollary 1.3. In fact, their result implies a more precise control on the size of the boundary $\partial R_N$ under $\tilde{P}_N$, showing that with high probability, $|\partial R_N| \le (\log n)^c n^{d-1}$ for some $c > 0$ and all for all $N$ large enough. Their starting point is the paper of Povel [Pov99], whose results are used freely in the discrete setting rather than in the continuum. (As pointed out in [DFSX18], a translation of Sznitman's method of enlargement of obstacles to a discrete setup was undertaken previously in [Ant95] – interestingly this predates [Pov99]). Given this, what remains to be proved is that the range of the random walk covers all of the ball of radius $\rho_d n(1 - \varepsilon)$, i.e., our Theorem 1.2. Hence the overlap with our paper is reduced to the proof of this theorem, which occupies Section 8 of this paper. The major differences with the approach of [DFSX18] can be summarised as follows:

- once we have proved Theorem 1.1, we know a bit more than the confinement property, since we know that the local time profile is close in the $L^1$ sense to the eigenfunction. This implies in particular that mesoscopic balls are visited frequently, a step which is therefore easy for us (Lemma 8.2) but which requires an argument in [DFSX18] (more precisely, the authors of [DFSX18] argue that if a ball is not frequently visited it must be close to the boundary).

- We have found a way to control uniformly the probability that a given set of $k$ points is avoided by the random walk in such a mesoscopic ball. Surprisingly, the control we get here is good enough that it works for any configuration of points, no matter what its geometry, and depends only on its cardinality. This is a major technical difference with [DFSX18] where the bound given depends on how many points in the set are far from one another. The key additional idea which allows us to do this here is to partition the points in the set according to their distance to the boundary and only consider points at a given distance from the boundary, where this distance is chosen to maximise the number of such points. This results in an arguably simpler line of reasoning from the conceptual point of view.
at every site with probability $1 - e^{-1}$. Note that $e^{-|R_N|}$ then corresponds to the annealed probability that the walk has not encountered any obstacle for time $N$.

A refinement of this method enabled Povel [Pov99] to establish the same result in dimension $d \ge 3$. It is important to note however that in the continuum, one cannot of course hope that the range of Brownian motion will fill a ball completely – there will always be small holes. For this reason, both results in [Szn91] and [Pov99] are restricted to a statement of the so-called confinement property, i.e., a statement that the range is contained in a ball of the appropriate radius (corresponding to $R = \rho_d n(1 + \varepsilon)$ in our setup). The question of whether the range will visit any macroscopic ball within this ball of radius $R$ is only addressed tangentially, see e.g. [Szn91, Theorem 4.3] and the discussion at the end of Section 1 in [Pov99]. Needless to say, the method of enlargement of obstacles is very different from the strategy employed by Bolthausen in [Bol94]. Curiously, neither [Szn91] nor [Pov99] discuss what their results imply for the discrete case, though both briefly mention the paper [Bol94].

At the time we were finishing this paper, we learnt of the independent and nearly simultaneous work of Ding, Fukushima, Sun and Xu [DFSX18], who obtained an alternative proof of Corollary 1.3. In fact, their result implies a more precise control on the size of the boundary $\partial R_N$ under $\tilde{P}_N$, showing that with high probability, $|\partial R_N| \le (\log n)^c n^{d-1}$ for some $c > 0$ and all for all $N$ large enough. Their starting point is the paper of Povel [Pov99], whose results are used freely in the discrete setting rather than in the continuum. (As pointed out in [DFSX18], a translation of Sznitman's method of enlargement of obstacles to a discrete setup was undertaken previously in [Ant95] – interestingly this predates [Pov99]). Given this, what remains to be proved is that the range of the random walk covers all of the ball of radius $\rho_d n(1 - \varepsilon)$, i.e., our Theorem 1.2. Hence the overlap with our paper is reduced to the proof of this theorem, which occupies Section 8 of this paper. The major differences with the approach of [DFSX18] can be summarised as follows:

- once we have proved Theorem 1.1, we know a bit more than the confinement property, since we know that the local time profile is close in the $L^1$ sense to the eigenfunction. This implies in particular that mesoscopic balls are visited frequently, a step which is therefore easy for us (Lemma 8.2) but which requires an argument in [DFSX18] (more precisely, the authors of [DFSX18] argue that if a ball is not frequently visited it must be close to the boundary).

- We have found a way to control uniformly the probability that a given set of $k$ points is avoided by the random walk in such a mesoscopic ball. Surprisingly, the control we get here is good enough that it works for any configuration of points, no matter what its geometry, and depends only on its cardinality. This is a major technical difference with [DFSX18] where the bound given depends on how many points in the set are far from one another. The key additional idea which allows us to do this here is to partition the points in the set according to their distance to the boundary and only consider points at a given distance from the boundary, where this distance is chosen to maximise the number of such points. This results in an arguably simpler line of reasoning from the conceptual point of view.
We also mention the related work [BY13] which was the initial motivation of our investigation. In this paper, the penalisation by the range $e^{-|R_N|}$ is replaced by the size of the boundary of the range $e^{-|\partial R_N|}$. This turns the random walk into a polymer interface model. A conjecture in [BY13] states that a shape theorem takes place on the scale $n = N^{1/(d+1)}$ instead of $n = N^{1/(d+2)}$. This shape could then be thought of as a Wulff crystal shape for the random walk. Despite partial results in [BY13], this conjecture remains wide open at positive temperature. However, in the limit of zero temperature (for a more general model where the boundary size is measured through i.i.d. random variables attached to edges), Biskup and Procaccia [BP18, BP16] were able to prove this conjecture. Observe that the random media representation which is the starting point of the method of enlargement of obstacles is not available for such a model.

Finally, for another approach to large deviations without compactness, see [MV16].

## Acknowledgements

We thank the authors of [DFSX18] for useful discussions regarding their work. Part of this research was carried out when NB was a guest at Ecole Normale Supérieure, Paris, whose support and hospitality is gratefully acknowledged. We warmly thank the Referees for their precise reading and their numerous comments which helped to improve the paper.

## 2. Further results and organisation of the paper

### 2.1. Preliminary lower bound on the partition function

To explain some further details about our approach (including intermediate theorems of interest in their own right, see below), it will be useful to start by recalling the following lower bound due to Bolthausen on the partition function which is a quantitative improvement on the result of Donsker and Varadhan.

Let $n$ be an integer such that $n^{d+2} = N$. Without loss of generality, we can assume that $N$ is such an integer power, and we do so throughout the paper.

**PROPOSITION 2.1.** — There exists a constant $c \in \mathbb{R}$, which depends on the dimension $d$ only, such that, for $N$ large enough, we have

$$Z_N \geq \exp\left(-\chi_d n^d - cn^{d-1}\right)$$

where

$$\chi_d = \frac{\lambda}{\rho_d^2} + \omega_d \rho_d^d$$

is the same constant which appears in (1.3).

*Proof.* — See [Bol94, Proposition 2.1] (note that the proof is valid in any dimension). □
We also mention the related work [BY13] which was the initial motivation of our investigation. In this paper, the penalisation by the range $e^{-|R_N|}$ is replaced by the size of the boundary of the range $e^{-|\partial R_N|}$. This turns the random walk into a polymer interface model. A conjecture in [BY13] states that a shape theorem takes place on the scale $n = N^{1/(d+1)}$ instead of $n = N^{1/(d+2)}$. This shape could then be thought of as a Wulff crystal shape for the random walk. Despite partial results in [BY13], this conjecture remains wide open at positive temperature. However, in the limit of zero temperature (for a more general model where the boundary size is measured through i.i.d. random variables attached to edges), Biskup and Procaccia [BP18, BP16] were able to prove this conjecture. Observe that the random media representation which is the starting point of the method of enlargement of obstacles is not available for such a model.

Finally, for another approach to large deviations without compactness, see [MV16].

## Acknowledgements

We thank the authors of [DFSX18] for useful discussions regarding their work. Part of this research was carried out when NB was a guest at Ecole Normale Supérieure, Paris, whose support and hospitality is gratefully acknowledged. We warmly thank the Referees for their precise reading and their numerous comments which helped to improve the paper.

## 2. Further results and organisation of the paper

### 2.1. Preliminary lower bound on the partition function

To explain some further details about our approach (including intermediate theorems of interest in their own right, see below), it will be useful to start by recalling the following lower bound due to Bolthausen on the partition function which is a quantitative improvement on the result of Donsker and Varadhan.

Let $n$ be an integer such that $n^{d+2} = N$. Without loss of generality, we can assume that $N$ is such an integer power, and we do so throughout the paper.

**PROPOSITION 2.1.** — There exists a constant $c \in \mathbb{R}$, which depends on the dimension $d$ only, such that, for $N$ large enough, we have

$$Z_N \geq \exp \left( - \chi_d n^d - cn^{d-1} \right)$$

where

$$\chi_d = \frac{\lambda}{\rho_d^2} + \omega_d \rho_d^d$$

is the same constant which appears in (1.3).

*Proof.* — See [Bol94, Proposition 2.1] (note that the proof is valid in any dimension). □
## 2.2. Upper bound on the numerator

Once we have a lower bound on the normalizing constant, the main problem is to obtain an adequate upper bound on the integral of $\exp(-|R_N|)$ over an arbitrary event $\mathcal{A}$. We can then rule out those events $\mathcal{A}$ for which we can obtain an upper bound which is negligible compared to the previous lower bound. Throughout the computations, we use the following convention. For $\mathcal{A}$ an event, we write

$$ (2.1) \qquad E\left(\exp\left(-|R_N|\right); \mathcal{A}\right) = E\left(\exp\left(-|R_N|\right)1_{\mathcal{A}}\right). $$

The central object in our study is the local time of the random walk, defined as

$$ (2.2) \qquad \forall x \in \mathbb{Z}^d \quad L_N(x) = \sum_{k=0}^{N-1} 1_{\{S_k=x\}}. $$

Our estimates will involve its square root, which we denote by $f_N$:

$$ (2.3) \qquad \forall x \in \mathbb{Z}^d \quad f_N(x) = \sqrt{L_N(x)}. $$

In order to compare functions to one another, we will make use of various $\ell^p$ norms, which, unlike Bolthausen [Bol94], we take to be unscaled. Thus we define, for a function $f: \mathbb{Z}^d \to \mathbb{R}$,

$$ (2.4) \qquad \|f\|_p = \left( \sum_{x \in \mathbb{Z}^d} |f(x)|^p \right)^{1/p}. $$

A fundamental step in the proof of Theorem 1.1, which takes up a substantial portion of this paper, is the following quantitative result which allows us to get an upper bound on (2.1).

**THEOREM 2.2.** — Let $\mathcal{F}$ be a collection of functions from $\mathbb{Z}^d$ to $\mathbb{R}^+$. For any $\kappa \ge 1$, we have, for $n$ large enough,

$$ \begin{aligned} E(e^{-|R_N|}; f_N \in \mathcal{F}) &\le \exp(-\kappa n^d) + \exp\left(n^{d-1/8} - \inf \left\{ \left| \left\{ x \in \mathbb{Z}^d : h(x) > 0 \right\} \right| \right\} \right) \\ &\quad + \frac{N}{2} (1 - n^{-1/4}) \left( \max \left( \sqrt{\mathcal{E}(\sqrt{h})} - \frac{1}{n^{9/8}}, 0 \right) \right)^2 \\ &\quad : h \in \ell^1(\mathbb{Z}^d), h \ge 0, \exists f \in \mathcal{F} \quad \left\| h - \frac{1}{N} f^2 \right\|_1 \le \frac{1}{n^{1/16}} \right). \end{aligned} $$

## 2.3. Organisation of paper

Sections 3, 4, and 5 are devoted to the proof of Theorem 2.2. Sections 6 and 7 explain how to deduce Theorem 1.1 from Theorem 2.2. Section 8 deals with a proof of Theorem 1.2.

As the proofs are rather lengthy, let us sum up the main steps of the proofs.
## 2.2. Upper bound on the numerator

Once we have a lower bound on the normalizing constant, the main problem is to obtain an adequate upper bound on the integral of $\exp(-|R_N|)$ over an arbitrary event $\mathcal{A}$. We can then rule out those events $\mathcal{A}$ for which we can obtain an upper bound which is negligible compared to the previous lower bound. Throughout the computations, we use the following convention. For $\mathcal{A}$ an event, we write

$$ (2.1) \qquad E\left(\exp\left(-|R_N|\right); \mathcal{A}\right) = E\left(\exp\left(-|R_N|\right)1_{\mathcal{A}}\right). $$

The central object in our study is the local time of the random walk, defined as

$$ (2.2) \qquad \forall x \in \mathbb{Z}^d \quad L_N(x) = \sum_{k=0}^{N-1} 1_{\{S_k=x\}}. $$

Our estimates will involve its square root, which we denote by $f_N$:

$$ (2.3) \qquad \forall x \in \mathbb{Z}^d \quad f_N(x) = \sqrt{L_N(x)}. $$

In order to compare functions to one another, we will make use of various $\ell^p$ norms, which, unlike Bolthausen [Bol94], we take to be unscaled. Thus we define, for a function $f: \mathbb{Z}^d \to \mathbb{R}$,

$$ (2.4) \qquad \|f\|_p = \left( \sum_{x \in \mathbb{Z}^d} |f(x)|^p \right)^{1/p}. $$

A fundamental step in the proof of Theorem 1.1, which takes up a substantial portion of this paper, is the following quantitative result which allows us to get an upper bound on (2.1).

**THEOREM 2.2.** — Let $\mathcal{F}$ be a collection of functions from $\mathbb{Z}^d$ to $\mathbb{R}^+$. For any $\kappa \ge 1$, we have, for $n$ large enough,

$$ \begin{aligned} E(e^{-|R_N|}; f_N \in \mathcal{F}) &\le \exp(-\kappa n^d) + \exp\left(n^{d-1/8} - \inf \left\{ \left| \left\{ x \in \mathbb{Z}^d : h(x) > 0 \right\} \right| \right\} \right) \\ &\quad + \frac{N}{2} (1 - n^{-1/4}) \left( \max \left( \sqrt{\mathcal{E}(\sqrt{h})} - \frac{1}{n^{9/8}}, 0 \right) \right)^2 \\ &\quad : h \in \ell^1(\mathbb{Z}^d), h \ge 0, \exists f \in \mathcal{F} \quad \left\| h - \frac{1}{N} f^2 \right\|_1 \le \frac{1}{n^{1/16}} \right). \end{aligned} $$

## 2.3. Organisation of paper

Sections 3, 4, and 5 are devoted to the proof of Theorem 2.2. Sections 6 and 7 explain how to deduce Theorem 1.1 from Theorem 2.2. Section 8 deals with a proof of Theorem 1.2.

As the proofs are rather lengthy, let us sum up the main steps of the proofs.
(i) (Section 3) We estimate probabilities of the form $P(\|L_N - g^2\|_{1,D} < \Gamma)$ for some small $\Gamma$, where $\|f\|_{1,D}$ is the norm of the function $f$ restricted to $D$. To this end, we develop a new type of large deviations estimates for the random walk (Theorem 1.4, see Section 3.4 for its proof). In fact, that result involves the infimum over a set of admissible starting points. In order to apply it to the random walk starting from the origin, we have to introduce a correcting factor, which however does not destroy the leading term in the estimates (Section 3.5).

(ii) (Section 4.1) We show that, up to events whose $\tilde{P}_N$ probability is negligible, for some $c > 0$, we have $|R_N| \le cn^d$. This is a direct consequence of the definition of $\tilde{P}_N$.

(iii) (Section 4.2) We show that, up to events whose $\tilde{P}_N$ probability is negligible, for some $\kappa \ge 1$, we have $\mathcal{E}(f_N) \le \kappa n^d \ln n$, where $\mathcal{E}$ is the Dirichlet energy. First we estimate the probability that $f_N$ is equal to a fixed function $f$. This estimate relies on the classical martingale used by Donsker and Varadhan. We then bound the number of functions satisfying the constraint $\text{supp} f \le cn^d$.

From now onwards, we need only to consider trajectories satisfying the points (ii) and (iii). Having a control on the Dirichlet energy yields automatically a control on the norm in $\ell^{2^*}(\mathbb{Z}^d)$, where $2^* = 2d/(d-2)$, via a discrete Sobolev-Poincaré inequality. We will use the three bounds

$$ \mathcal{E}(f_N) \le \kappa n^d \ln n, \quad |R_N| \le cn^d, \quad \|f_N\|_{2^*} \le c_{PS} \sqrt{\kappa n^d \ln n}, $$

to develop an adequate coarse-grained image of the local time.

(iv) (Section 4.3) We partition the space into blocks of side length $n$. We focus on the blocks $B$ such that $\|f_N\|_{2^*,B} \ge \delta n^{d/2^*+1}$. The exponent $d/2^* + 1$ corresponds to the typical situation for a block actively visited by the random walk until time $N$: the number of visits per site should be of order $n^2$, so $f_N$ is of order $n$ throughout the block. We keep record of the indices of these blocks. More precisely, we denote by $X$ the set of the centers of these blocks; of course the set $X$ depends on $f_N$ and is random. We denote by $E$ the union of these blocks and by $D$ the region $E$ enlarged with all the blocks on the frontier. We control the norm of $f_N$ outside the region $E$. This is done with the help of a discrete Poincaré-Sobolev inequality and the control of the $\ell^{2^*}$ norm:

$$ \sum_{x \in \mathbb{Z}^d \setminus E} (f_N(x))^{2^*} \le c_d (\delta^{2^*} n^{d+2^*})^{1-2/2^*} (n^d + \kappa n^d \ln n). $$

(v) (Section 4.4) We introduce a length scale $M$. We partition the space into blocks $B'(x)$ of side length $M$. We perform a local average of $f_N$ on each such block and we get a function $\overline{f}_N^M$. We control the norm of the difference $f_N - \overline{f}_N^M$ with the help of a discrete Poincaré-Wirtinger inequality.

(vi) (Section 5.1) We discretise next the values of the functions $\overline{f}_N^M$ over the blocks $B(x)$ which are included in $E$ with a discretisation step $\eta > 0$. This way we obtain a function $\eta \overline{f}_N^M$, which is the coarse grained profile.
(i) (Section 3) We estimate probabilities of the form $P(\|L_N - g^2\|_{1,D} < \Gamma)$ for some small $\Gamma$, where $\|f\|_{1,D}$ is the norm of the function $f$ restricted to $D$. To this end, we develop a new type of large deviations estimates for the random walk (Theorem 1.4, see Section 3.4 for its proof). In fact, that result involves the infimum over a set of admissible starting points. In order to apply it to the random walk starting from the origin, we have to introduce a correcting factor, which however does not destroy the leading term in the estimates (Section 3.5).

(ii) (Section 4.1) We show that, up to events whose $\tilde{P}_N$ probability is negligible, for some $c > 0$, we have $|R_N| \le cn^d$. This is a direct consequence of the definition of $\tilde{P}_N$.

(iii) (Section 4.2) We show that, up to events whose $\tilde{P}_N$ probability is negligible, for some $\kappa \ge 1$, we have $\mathcal{E}(f_N) \le \kappa n^d \ln n$, where $\mathcal{E}$ is the Dirichlet energy. First we estimate the probability that $f_N$ is equal to a fixed function $f$. This estimate relies on the classical martingale used by Donsker and Varadhan. We then bound the number of functions satisfying the constraint $\text{supp} f \le cn^d$.

From now onwards, we need only to consider trajectories satisfying the points (ii) and (iii). Having a control on the Dirichlet energy yields automatically a control on the norm in $\ell^{2^*}(\mathbb{Z}^d)$, where $2^* = 2d/(d-2)$, via a discrete Sobolev-Poincaré inequality. We will use the three bounds

$$ \mathcal{E}(f_N) \le \kappa n^d \ln n, \quad |R_N| \le cn^d, \quad \|f_N\|_{2^*} \le c_{PS} \sqrt{\kappa n^d \ln n}, $$

to develop an adequate coarse-grained image of the local time.

(iv) (Section 4.3) We partition the space into blocks of side length $n$. We focus on the blocks $B$ such that $\|f_N\|_{2^*,B} \ge \delta n^{d/2^*+1}$. The exponent $d/2^*+1$ corresponds to the typical situation for a block actively visited by the random walk until time $N$: the number of visits per site should be of order $n^2$, so $f_N$ is of order $n$ throughout the block. We keep record of the indices of these blocks. More precisely, we denote by $X$ the set of the centers of these blocks; of course the set $X$ depends on $f_N$ and is random. We denote by $E$ the union of these blocks and by $D$ the region $E$ enlarged with all the blocks on the frontier. We control the norm of $f_N$ outside the region $E$. This is done with the help of a discrete Poincaré-Sobolev inequality and the control of the $\ell^{2^*}$ norm:

$$ \sum_{x \in \mathbb{Z}^d \setminus E} (f_N(x))^{2^*} \le c_d (\delta^{2^*} n^{d+2^*})^{1-2/2^*} (n^d + \kappa n^d \ln n). $$

(v) (Section 4.4) We introduce a length scale $M$. We partition the space into blocks $B'(x)$ of side length $M$. We perform a local average of $f_N$ on each such block and we get a function $\overline{f}_N^M$. We control the norm of the difference $f_N - \overline{f}_N^M$ with the help of a discrete Poincaré-Wirtinger inequality.

(vi) (Section 5.1) We discretise next the values of the functions $\overline{f}_N^M$ over the blocks $B(x)$ which are included in $E$ with a discretisation step $\eta > 0$. This way we obtain a function $\eta \overline{f}_N^M$, which is the coarse grained profile.
At this point, we can write

$$E(e^{-|R_N|}; f_N \in \mathcal{F}) \le \sum_{X,g} E(e^{-|R_N|}; f_N \in \mathcal{F}, \eta \overline{f_N}^M = g),$$

where the summation extends over the admissible set of blocks X and profiles g. Whenever $\eta \overline{f_N}^M = g$, we can show that $\|f_N - g\|_{2,D} < \Gamma_0$, and $\|L_N - g^2\|_{1,D} < \Gamma_1$, where $\Gamma_0, \Gamma_1$ are explicit functions of N.

(vii) (Section 5.2) We apply our large deviations inequality to bound the expectation

$$E(e^{-|R_N|}; \|L_N - g^2\| < \Gamma_1).$$

To do so, we approximate the cardinality of the range $|R_N|$ by the cardinality of the points where the coarse grained profile is quite large. The resulting upper bound depends on an infimum over a set of functions h defined on the domain D, and more specifically on their Dirichlet energy inside D.

(viii) (Section 5.3) With the help of a truncation and the control of the $l^2$* norm outside E, we relate the Dirichlet energy in the full space to the Dirichlet energy restricted to D. This involves essentially a discrete integration by parts.

(ix) (Section 5.4) We use the inequality proved in Step (ix). This way we get an upper bound involving the Dirichlet energy in the full space, however we have to work further to get rid of the truncation operator. After some tedious computations, we obtain an upper bound depending only on the collection $\mathcal{F}$. We plug this upper bound in the previous sums. It remains only to count the number of terms in the sums. We choose finally the parameters M, $\delta$, $\eta$ adequately to get the desired upper bound.

### 2.3.1. Main steps in the proof of Theorem 1.2.

We fix a mesoscopic scale $m = n^{1-2\kappa}$ where $\kappa > 0$ is a small parameter. Suppose $\mathcal{G}_{loc, x}$ holds and take $x = 0$ without loss of generality. We aim to show that the ball of radius $m$ around a point $z$ in the desired range $B(0, \rho_d n(1 - n^{-\kappa}))$ is entirely visited.

(i) (Section 8.1) We first note that deterministically on $\mathcal{G}_{loc, 0}$, the walk spends a lot of time in $B(z, m)$. This is because otherwise there would be a polynomial error in the $L^1$ distance between $l_N$ and $(\phi_x)^2$.

(ii) (Section 8.2) We show that under $\tilde{P}_N$ there are many disjoint portions of the walk of duration $m^2$ where the walk starts and ends inside the bulk of the ball (say, $B(z, m/2)$) and never leaves $B(z, m)$ throughout this interval of time. We call such a portion a bridge. To do so we use a change of measure argument whose cost (i.e., the value of the Radon-Nikodym derivative of this change of measure) is comparable to the entropic term in the partition function $Z_N$: that is, of order $\exp(-(\lambda/2\rho_d^2)n^d)$. Since on $\mathcal{G}_{loc, 0}$ the size of the range $|R_N|$ is also essentially deterministically lower bounded up to a small error, the energetic term $e^{-|R_N|}$ together with the cost of the change of measure is of order at most $Z_N$, which allows us to compare effectively
At this point, we can write

$$E(e^{-|R_N|}; f_N \in \mathcal{F}) \le \sum_{X,g} E(e^{-|R_N|}; f_N \in \mathcal{F}, \eta \overline{f_N}^M = g),$$

where the summation extends over the admissible set of blocks $X$ and profiles $g$. Whenever $\eta \overline{f_N}^M = g$, we can show that $\|f_N - g\|_{2,D} < \Gamma_0$, and $\|L_N - g^2\|_{1,D} < \Gamma_1$, where $\Gamma_0, \Gamma_1$ are explicit functions of $N$.

(vii) (Section 5.2) We apply our large deviations inequality to bound the expectation

$$E(e^{-|R_N|}; \|L_N - g^2\| < \Gamma_1).$$

To do so, we approximate the cardinality of the range $|R_N|$ by the cardinality of the points where the coarse grained profile is quite large. The resulting upper bound depends on an infimum over a set of functions $h$ defined on the domain $D$, and more specifically on their Dirichlet energy inside $D$.

(viii) (Section 5.3) With the help of a truncation and the control of the $\ell^{2*}$ norm outside $E$, we relate the Dirichlet energy in the full space to the Dirichlet energy restricted to $D$. This involves essentially a discrete integration by parts.

(ix) (Section 5.4) We use the inequality proved in Step (ix). This way we get an upper bound involving the Dirichlet energy in the full space, however we have to work further to get rid of the truncation operator. After some tedious computations, we obtain an upper bound depending only on the collection $\mathcal{F}$. We plug this upper bound in the previous sums. It remains only to count the number of terms in the sums. We choose finally the parameters $M, \delta, \eta$ adequately to get the desired upper bound.

### 2.3.1. Main steps in the proof of Theorem 1.2.

We fix a mesoscopic scale $m = n^{1-2\kappa}$ where $\kappa > 0$ is a small parameter. Suppose $\mathcal{G}_{loc, x}$ holds and take $x = 0$ without loss of generality. We aim to show that the ball of radius $m$ around a point $z$ in the desired range $B(0, \rho_d n(1 - n^{-\kappa}))$ is entirely visited.

(i) (Section 8.1) We first note that deterministically on $\mathcal{G}_{loc, 0}$, the walk spends a lot of time in $B(z, m)$. This is because otherwise there would be a polynomial error in the $L^1$ distance between $\ell_N$ and $(\phi_x)^2$.

(ii) (Section 8.2) We show that under $\tilde{P}_N$ there are many disjoint portions of the walk of duration $m^2$ where the walk starts and ends inside the bulk of the ball (say, $B(z, m/2)$) and never leaves $B(z, m)$ throughout this interval of time. We call such a portion a bridge. To do so we use a change of measure argument whose cost (i.e., the value of the Radon-Nikodym derivative of this change of measure) is comparable to the entropic term in the partition function $Z_N$: that is, of order $\exp(-(\lambda/2\rho_d^2)n^d)$. Since on $\mathcal{G}_{loc, 0}$ the size of the range $|R_N|$ is also essentially deterministically lower bounded up to a small error, the energetic term $e^{-|R_N|}$ together with the cost of the change of measure is of order at most $Z_N$, which allows us to compare effectively
$\tilde{P}_N$ to this new measure. A technical difficulty is that the change of measure technique is better implemented in continuous time rather than discrete time. Once we work under this change of measure, it is easy to check that the number of bridges is as desired: indeed, every time the walk is in the bulk of the ball, there is a decent chance that the next $m^2$ units of time will result in a bridge. Moreover, by Step 1 we control the number of trials, so ultimately the desired result follows from standard large deviations for Binomial random variables.

(iii) (Section 8.3) We fix $k \ge 1$ and a set $\mathcal{X}$ of $k$ points in $B(z, m)$, and try to estimate the $\tilde{P}_N$ probability that $\mathcal{X}$ is avoided by the walk. We can condition on everything that happens outside of $B(z, m)$; on the event that the range avoids exactly the set $\mathcal{X}$ the size of the range is then deterministic. Furthermore, if we condition on the number and endpoints of the bridges the probability that all the bridges avoid $\mathcal{X}$ is exactly the product for individual bridges to avoid $\mathcal{X}$. Hence the probability that the range restricted to $B(z, m)$ is strictly smaller than this ball can be written as a sum over $k \ge 1$, and over all subsets $\mathcal{X}$ of size $k$ of the product of probabilities that bridges avoid $\mathcal{X}$.

(iv) (Section 8.4) To estimate the latter we need to control transition probabilities for bridges that are uniform in the starting and end points of the bridge. It is here that it is useful to have taken the starting and end points of the bridge in the bulk of the ball $B(z, m/2)$ and not near the boundary. This shows in particular that the probability for a bridge to find itself at a specific point at distance $r$ from the boundary at some specific time which is neither close to the start or the end of the bridge, is proportional to $(r/m)^2$. This follows essentially from a gambler's ruin probability argument.

(v) (Section 8.5) By the previous step it suffices to estimate the probability that a given bridge avoids $\mathcal{X}$. We aim to find a bound that is uniform on the geometry of $\mathcal{X}$ and depends only on the number of points $k$ in $\mathcal{X}$. Intuitively, the easiest configuration to avoid is when $\mathcal{X}$ is clumped together as a solid ball of radius $R = k^{1/d}$, so this should provide a lower bound on the desired probability. In that case our estimates on the transition probabilities from the previous step show via a moment computation that the probability for a bridge to hit $\mathcal{X}$ should be at least $km^{2-d}/R^2 = k^{1-2/d}m^{2-d}$, independently of the geometry of $\mathcal{X}$ (ignoring boundary effects). This turns out to be true and can be deduced relatively easily from the fact that the Green function of the random walk in $\mathbb{Z}^d$, $d \ge 3$, is essentially monotone in the distance. (Such arguments can be used to prove isoperimetric inequalities for the capacity of a set, but we did not include this here for the sake of brevity).

In order to deal with boundary effects, in a way that is still uniform in the geometry of $\mathcal{X}$, we divide the ball $B(z, m)$ into concentric annuli $A_j$ at distance $2^j$ from the boundary of the ball ($j \ge 1$). If all the points of $\mathcal{X}$ were in the annulus $A_j$ it would be possible to control the boundary effects in a uniform way. Indeed the expected time spent in $\mathcal{X}$ would be, by the gambler's ruin estimate from Step (iv), proportional to $r^2$ where $r = 2^j$ is the distance to the boundary. However the expected time spent in $\mathcal{X}$ starting from a point in $\mathcal{X}$ would also be bounded by a factor proportional to $r^2$
$\tilde{P}_N$ to this new measure. A technical difficulty is that the change of measure technique is better implemented in continuous time rather than discrete time. Once we work under this change of measure, it is easy to check that the number of bridges is as desired: indeed, every time the walk is in the bulk of the ball, there is a decent chance that the next $m^2$ units of time will result in a bridge. Moreover, by Step 1 we control the number of trials, so ultimately the desired result follows from standard large deviations for Binomial random variables.

(iii) (Section 8.3) We fix $k \ge 1$ and a set $\mathcal{X}$ of $k$ points in $B(z, m)$, and try to estimate the $\tilde{P}_N$ probability that $\mathcal{X}$ is avoided by the walk. We can condition on everything that happens outside of $B(z, m)$; on the event that the range avoids exactly the set $\mathcal{X}$ the size of the range is then deterministic. Furthermore, if we condition on the number and endpoints of the bridges the probability that all the bridges avoid $\mathcal{X}$ is exactly the product for individual bridges to avoid $\mathcal{X}$. Hence the probability that the range restricted to $B(z, m)$ is strictly smaller than this ball can be written as a sum over $k \ge 1$, and over all subsets $\mathcal{X}$ of size $k$ of the product of probabilities that bridges avoid $\mathcal{X}$.

(iv) (Section 8.4) To estimate the latter we need to control transition probabilities for bridges that are uniform in the starting and end points of the bridge. It is here that it is useful to have taken the starting and end points of the bridge in the bulk of the ball $B(z, m/2)$ and not near the boundary. This shows in particular that the probability for a bridge to find itself at a specific point at distance $r$ from the boundary at some specific time which is neither close to the start or the end of the bridge, is proportional to $(r/m)^2$. This follows essentially from a gambler's ruin probability argument.

(v) (Section 8.5) By the previous step it suffices to estimate the probability that a given bridge avoids $\mathcal{X}$. We aim to find a bound that is uniform on the geometry of $\mathcal{X}$ and depends only on the number of points $k$ in $\mathcal{X}$. Intuitively, the easiest configuration to avoid is when $\mathcal{X}$ is clumped together as a solid ball of radius $R = k^{1/d}$, so this should provide a lower bound on the desired probability. In that case our estimates on the transition probabilities from the previous step show via a moment computation that the probability for a bridge to hit $\mathcal{X}$ should be at least $km^{2-d}/R^2 = k^{1-2/d}m^{2-d}$, independently of the geometry of $\mathcal{X}$ (ignoring boundary effects). This turns out to be true and can be deduced relatively easily from the fact that the Green function of the random walk in $\mathbb{Z}^d$, $d \ge 3$, is essentially monotone in the distance. (Such arguments can be used to prove isoperimetric inequalities for the capacity of a set, but we did not include this here for the sake of brevity).

In order to deal with boundary effects, in a way that is still uniform in the geometry of $\mathcal{X}$, we divide the ball $B(z, m)$ into concentric annuli $A_j$ at distance $2^j$ from the boundary of the ball ($j \ge 1$). If all the points of $\mathcal{X}$ were in the annulus $A_j$ it would be possible to control the boundary effects in a uniform way. Indeed the expected time spent in $\mathcal{X}$ would be, by the gambler's ruin estimate from Step (iv), proportional to $r^2$ where $r = 2^j$ is the distance to the boundary. However the expected time spent in $\mathcal{X}$ starting from a point in $\mathcal{X}$ would also be bounded by a factor proportional to $r^2$
as well using Step (iv) again. Hence the $r^2$ terms cancel in the moment computation, and we could use the above bound. When $\mathcal{X}$ is not contained in a single annulus $A_j$, we can instead consider $\mathcal{X}_j = \mathcal{X} \cap A_j$, where $A_j$ is chosen so that it contains most points of $\mathcal{X}$. Then since it suffices to hit $\mathcal{X}_j$, we can apply the above lower bound with $k$ replaced by $|\mathcal{X}_j|$. By the choice of $j$, this is at least $k/\log m$ instead of $k$. It turns out that plugging this extra logarithmic factor does not substantially alter the conclusion.

# 3. Martingale estimates

## 3.1. The classical martingale

The crucial ingredient to derive the relevant probabilistic estimates on the random walk is the family of martingales used by Donsker and Varadhan, which we define thereafter. Let $u$ be a positive function defined on $\mathbb{Z}^d$. To the function $u$ we associate the function $V$ defined on $\mathbb{Z}^d$ by

$$ \forall x \in \mathbb{Z}^d \quad V(x) = \frac{1}{2d} \sum_{y \in \mathbb{Z}^d, |x-y|=1} u(y). $$

For $n \ge 0$, we set

$$ M_n = \left( \prod_{k=0}^{n-1} \frac{u(S_k)}{V(S_k)} \right) u(S_n). $$

We claim that the process $(M_n)_{n \in \mathbb{N}}$ is a martingale. Indeed, for any $n \ge 0$,

$$ \begin{aligned} E(M_n | S_0, \dots, S_{n-1}) &= \left( \prod_{k=0}^{n-1} \frac{u(S_k)}{V(S_k)} \right) E(u(S_n) | S_{n-1}) \\ &= \left( \prod_{k=0}^{n-1} \frac{u(S_k)}{V(S_k)} \right) V(S_{n-1}) = M_{n-1}. \end{aligned} $$

In the same way, if the random walk $(S_n)_{n \in \mathbb{N}}$ starts from an arbitrary point $x \in \mathbb{Z}^d$, and if we denote by $P_x$ and $E_x$ the associated probability and expectation, then, under $P_x$, the process $(M_n)_{n \in \mathbb{N}}$ is again a martingale.

## 3.2. The fundamental inequality

Since $(M_n)_{n \in \mathbb{N}}$ is a martingale, then

$$ (3.1) \qquad E_x(M_N) = E_x(M_0) = u(x). $$

Let us express $M_N$ with the help of the local time $L_N$:

$$ \begin{aligned} M_N &= \exp \left( \sum_{0 \le k < N} \ln \frac{u(S_k)}{V(S_k)} \right) u(S_N) \\ &= \exp \left( \sum_{y \in \mathbb{Z}^d} \ln \frac{u(y)}{V(y)} L_N(y) \right) u(S_N). \end{aligned} $$
as well using Step (iv) again. Hence the $r^2$ terms cancel in the moment computation, and we could use the above bound. When $\mathcal{X}$ is not contained in a single annulus $A_j$, we can instead consider $\mathcal{X}_j = \mathcal{X} \cap A_j$, where $A_j$ is chosen so that it contains most points of $\mathcal{X}$. Then since it suffices to hit $\mathcal{X}_j$, we can apply the above lower bound with $k$ replaced by $|\mathcal{X}_j|$. By the choice of $j$, this is at least $k/\log m$ instead of $k$. It turns out that plugging this extra logarithmic factor does not substantially alter the conclusion.

### 3. Martingale estimates

#### 3.1. The classical martingale

The crucial ingredient to derive the relevant probabilistic estimates on the random walk is the family of martingales used by Donsker and Varadhan, which we define thereafter. Let $u$ be a positive function defined on $\mathbb{Z}^d$. To the function $u$ we associate the function $V$ defined on $\mathbb{Z}^d$ by

$$ \forall x \in \mathbb{Z}^d \quad V(x) = \frac{1}{2d} \sum_{y \in \mathbb{Z}^d, |x-y|=1} u(y). $$

For $n \ge 0$, we set

$$ M_n = \left( \prod_{k=0}^{n-1} \frac{u(S_k)}{V(S_k)} \right) u(S_n). $$

We claim that the process $(M_n)_{n \in \mathbb{N}}$ is a martingale. Indeed, for any $n \ge 0$,

$$ \begin{aligned} E(M_n | S_0, \dots, S_{n-1}) &= \left( \prod_{k=0}^{n-1} \frac{u(S_k)}{V(S_k)} \right) E(u(S_n) | S_{n-1}) \\ &= \left( \prod_{k=0}^{n-1} \frac{u(S_k)}{V(S_k)} \right) V(S_{n-1}) = M_{n-1}. \end{aligned} $$

In the same way, if the random walk $(S_n)_{n \in \mathbb{N}}$ starts from an arbitrary point $x \in \mathbb{Z}^d$, and if we denote by $P_x$ and $E_x$ the associated probability and expectation, then, under $P_x$, the process $(M_n)_{n \in \mathbb{N}}$ is again a martingale.

#### 3.2. The fundamental inequality

Since $(M_n)_{n \in \mathbb{N}}$ is a martingale, then

$$ (3.1) \qquad E_x(M_N) = E_x(M_0) = u(x). $$

Let us express $M_N$ with the help of the local time $L_N$:

$$ \begin{aligned} M_N &= \exp \left( \sum_{0 \le k < N} \ln \frac{u(S_k)}{V(S_k)} \right) u(S_N) \\ &= \exp \left( \sum_{y \in \mathbb{Z}^d} \ln \frac{u(y)}{V(y)} L_N(y) \right) u(S_N). \end{aligned} $$
Since $|S_N - S_0| \le N$, then

$$u(S_N) \ge \inf \{ u(y) : |y - x| \le N \}.$$

Reporting this inequality in the martingale equality (3.1), we get the following fundamental inequality.

**LEMMA 3.1.** — For any $N \ge 1$, any $x \in \mathbb{Z}^d$ and any positive function $u$ defined on $\mathbb{Z}^d$, we have

$$E_x \left( \exp \left( \sum_{y \in \mathbb{Z}^d} \ln \frac{u(y)}{V(y)} L_N(y) \right) \right) \le \frac{u(x)}{\inf \{ u(y) : |y - x| \le N \}}.$$

### 3.3. Estimate for a fixed profile

For $f$ a function from $\mathbb{Z}^d$ to $\mathbb{R}$, we define its discrete Dirichlet energy $\mathcal{E}(f)$ by

$$\mathcal{E}(f) = \frac{1}{2d} \sum_{\substack{y, z \in \mathbb{Z}^d \\ |y-z|=1}} (f(y) - f(z))^2.$$

In this section, we shall prove the following estimate for the probability that the square root of the local time is equal to a fixed profile.

**PROPOSITION 3.2.** — Let $\phi$ be a function from $\mathbb{Z}^d$ to $[0, +\infty[$ such that

$$\sum_{y \in \mathbb{Z}^d} \phi(y)^2 = N.$$

For any $N \ge 1$, any $\alpha \in ]0, 1[$, we have

$$P(f_N = \phi) \le \frac{\phi(0)}{\alpha} \exp \left( -\frac{1}{2} \mathcal{E}(\phi) + \alpha \sqrt{N |\text{supp } \phi|} \right).$$

*Proof.* — To bound the probability $P(f_N = \phi)$, we proceed as follows. Let $\alpha \in ]0, 1[$ and let $u : \mathbb{Z}^d \to ]0, +\infty[$ be the positive function defined on $\mathbb{Z}^d$ by

$$\forall y \in \mathbb{Z}^d \quad u(y) = \max(\phi(y), \alpha).$$

Obviously, we have

$$E \left( \exp \left( \sum_{y \in \mathbb{Z}^d} \ln \frac{u(y)}{V(y)} L_N(y) \right) \right) \ge P(f_N = \phi) \exp \left( \sum_{y \in \mathbb{Z}^d} \ln \frac{u(y)}{V(y)} \phi(y)^2 \right).$$

Since the random walk starts from 0, then $f_N(0) \ge 1$, so we need only to consider functions $\phi$ such that $\phi(0) \ge 1$. In this case, we have $u(0) = \phi(0) \ge \alpha$. Applying the fundamental estimate of Lemma 3.1, we get

$$P(f_N = \phi) \le \frac{\phi(0)}{\alpha} \exp \left( - \sum_{y \in \mathbb{Z}^d} \ln \frac{u(y)}{V(y)} \phi(y)^2 \right).$$
Since $|S_N - S_0| \le N$, then

$$u(S_N) \ge \inf \{ u(y) : |y - x| \le N \}.$$

Reporting this inequality in the martingale equality (3.1), we get the following fundamental inequality.

**LEMMA 3.1.** — For any $N \ge 1$, any $x \in \mathbb{Z}^d$ and any positive function $u$ defined on $\mathbb{Z}^d$, we have

$$E_x \left( \exp \left( \sum_{y \in \mathbb{Z}^d} \ln \frac{u(y)}{V(y)} L_N(y) \right) \right) \le \frac{u(x)}{\inf \{ u(y) : |y - x| \le N \}}.$$

### 3.3. Estimate for a fixed profile

For $f$ a function from $\mathbb{Z}^d$ to $\mathbb{R}$, we define its discrete Dirichlet energy $\mathcal{E}(f)$ by

$$\mathcal{E}(f) = \frac{1}{2d} \sum_{\substack{y, z \in \mathbb{Z}^d \\ |y-z|=1}} (f(y) - f(z))^2.$$

In this section, we shall prove the following estimate for the probability that the square root of the local time is equal to a fixed profile.

**PROPOSITION 3.2.** — Let $\phi$ be a function from $\mathbb{Z}^d$ to $[0, +\infty[$ such that

$$\sum_{y \in \mathbb{Z}^d} \phi(y)^2 = N.$$

For any $N \ge 1$, any $\alpha \in ]0, 1[$, we have

$$P(f_N = \phi) \le \frac{\phi(0)}{\alpha} \exp \left( -\frac{1}{2} \mathcal{E}(\phi) + \alpha \sqrt{N|\text{supp } \phi|} \right).$$

*Proof.* — To bound the probability $P(f_N = \phi)$, we proceed as follows. Let $\alpha \in ]0, 1[$ and let $u : \mathbb{Z}^d \to ]0, +\infty[$ be the positive function defined on $\mathbb{Z}^d$ by

$$\forall y \in \mathbb{Z}^d \quad u(y) = \max(\phi(y), \alpha).$$

Obviously, we have

$$E \left( \exp \left( \sum_{y \in \mathbb{Z}^d} \ln \frac{u(y)}{V(y)} L_N(y) \right) \right) \ge P(f_N = \phi) \exp \left( \sum_{y \in \mathbb{Z}^d} \ln \frac{u(y)}{V(y)} \phi(y)^2 \right).$$

Since the random walk starts from 0, then $f_N(0) \ge 1$, so we need only to consider functions $\phi$ such that $\phi(0) \ge 1$. In this case, we have $u(0) = \phi(0) \ge \alpha$. Applying the fundamental estimate of Lemma 3.1, we get

$$P(f_N = \phi) \le \frac{\phi(0)}{\alpha} \exp \left( - \sum_{y \in \mathbb{Z}^d} \ln \frac{u(y)}{V(y)} \phi(y)^2 \right).$$
Next, we have, for $y \in \mathbb{Z}^d$,

$$-\ln \frac{u(y)}{V(y)} = \ln \left( 1 + \frac{V(y) - u(y)}{u(y)} \right) \le \frac{\Delta_1 u(y)}{u(y)},$$

where $\Delta_1$ is the discrete Laplacian operator, defined by

$$\Delta_1 u(y) = V(y) - u(y).$$

Reporting in the previous inequality, we arrive at

$$P(f_N = \phi) \le \frac{\phi(0)}{\alpha} \exp \left( \sum_{y \in \mathbb{Z}^d} \frac{\Delta_1 u(y)}{u(y)} \phi(y)^2 \right).$$

We evaluate next the sum in the exponential. For $y \in \text{supp } \phi$, we have $\phi(y) \ge 1 > \alpha$, whence $\phi(y) = u(y)$, therefore

$$\begin{align*}
\sum_{y \in \mathbb{Z}^d} \frac{\Delta_1 u(y)}{u(y)} \phi(y)^2 &= \sum_{y \in \text{supp } \phi} \Delta_1 u(y) \phi(y) \\
&= \sum_{y \in \text{supp } \phi} \frac{1}{2d} \sum_{z: |z-y|=1} (u(z) - u(y)) \phi(y) \\
&\le \sum_{y \in \text{supp } \phi} \frac{1}{2d} \sum_{z: |z-y|=1} (\phi(z) - \phi(y) + \alpha) \phi(y) \\
&= \frac{1}{2d} \sum_{y, z \in \text{supp } \phi \atop |y-z|=1} \phi(y)\phi(z) + \sum_{y \in \text{supp } \phi} (\alpha\phi(y) - \phi(y)^2) \\
&= -\frac{1}{4d} \sum_{y, z \in \text{supp } \phi \atop |y-z|=1} (\phi(y) - \phi(z))^2 + \alpha \sum_{y \in \text{supp } \phi} \phi(y).
\end{align*}$$

Moreover

$$\left( \sum_{y \in \text{supp } \phi} \phi(y) \right)^2 \le \left( \sum_{y \in \text{supp } \phi} \phi(y)^2 \right) |\text{supp } \phi| = N |\text{supp } \phi|.$$

Putting together the previous inequalities, we obtain the inequality stated in the Proposition 3.2. $\square$

### 3.4. Donsker-Varadhan estimate for the random walk in the full space

In order to estimate the probability that $L_N$ belongs to a ball centered at a fixed function $g^2$, we develop here a deviation inequality, valid for any value of $N$ and for any convex set of functions. This deviation inequality is stated in Theorem 1.4 of the introduction and we prove it here. We use the notation introduced just before the statement of Theorem 1.4.
Next, we have, for $y \in \mathbb{Z}^d$,

$$ -\ln \frac{u(y)}{V(y)} = \ln \left( 1 + \frac{V(y) - u(y)}{u(y)} \right) \le \frac{\Delta_1 u(y)}{u(y)}, $$

where $\Delta_1$ is the discrete Laplacian operator, defined by

$$ \Delta_1 u(y) = V(y) - u(y). $$

Reporting in the previous inequality, we arrive at

$$ P(f_N = \phi) \le \frac{\phi(0)}{\alpha} \exp \left( \sum_{y \in \mathbb{Z}^d} \frac{\Delta_1 u(y)}{u(y)} \phi(y)^2 \right). $$

We evaluate next the sum in the exponential. For $y \in \text{supp } \phi$, we have $\phi(y) \ge 1 > \alpha$, whence $\phi(y) = u(y)$, therefore

$$ \begin{aligned} \sum_{y \in \mathbb{Z}^d} \frac{\Delta_1 u(y)}{u(y)} \phi(y)^2 &= \sum_{y \in \text{supp } \phi} \Delta_1 u(y) \phi(y) \\ &= \sum_{y \in \text{supp } \phi} \frac{1}{2d} \sum_{z: |z-y|=1} (u(z) - u(y)) \phi(y) \\ &\le \sum_{y \in \text{supp } \phi} \frac{1}{2d} \sum_{z: |z-y|=1} (\phi(z) - \phi(y) + \alpha) \phi(y) \\ &= \frac{1}{2d} \sum_{y, z \in \text{supp } \phi \atop |y-z|=1} \phi(y)\phi(z) + \sum_{y \in \text{supp } \phi} (\alpha\phi(y) - \phi(y)^2) \\ &= -\frac{1}{4d} \sum_{y, z \in \text{supp } \phi \atop |y-z|=1} (\phi(y) - \phi(z))^2 + \alpha \sum_{y \in \text{supp } \phi} \phi(y). \end{aligned} $$

Moreover

$$ \left( \sum_{y \in \text{supp } \phi} \phi(y) \right)^2 \le \left( \sum_{y \in \text{supp } \phi} \phi(y)^2 \right) |\text{supp } \phi| = N |\text{supp } \phi|. $$

Putting together the previous inequalities, we obtain the inequality stated in the Proposition 3.2. $\square$

## 3.4. Donsker-Varadhan estimate for the random walk in the full space

In order to estimate the probability that $L_N$ belongs to a ball centered at a fixed function $g^2$, we develop here a deviation inequality, valid for any value of $N$ and for any convex set of functions. This deviation inequality is stated in Theorem 1.4 of the introduction and we prove it here. We use the notation introduced just before the statement of Theorem 1.4.
*Proof.* — Let $u$ be a positive function defined on $\mathbb{Z}^d$ and let $x \in \mathbb{Z}^d$. Let $(M_n)_{n \in \mathbb{N}}$ be the martingale constructed with the function $u$ and the random walk $(S_n)_{n \in \mathbb{N}}$, defined in Section 3.1. We first remark that $\tau(D, t)$ is a stopping time for $(M_n)_{n \in \mathbb{N}}$. Indeed, the event $\{\tau(D, t) = n\}$ is measurable with respect to $L_n(D)$, hence also to $S_1, \dots, S_{n-1}$. We apply next the optional stopping theorem. Let $t, n \ge 1$, we have

$$E_x(M_{n \wedge \tau(D, t)}) = E_x(M_0) = u(x).$$

We note simply $\tau$ instead of $\tau(D, t)$ and we bound from below the left hand member:

$$ (3.2) \quad E_x(M_{n \wedge \tau}) \ge E_x(M_{n \wedge \tau} 1_{\tau < \infty}) \\ = E_x \left( \exp \left( \sum_{y \in \mathbb{Z}^d} \left( \ln \frac{u(y)}{V(y)} \right) L_{n \wedge \tau}(y) \right) u(S_{n \wedge \tau}) 1_{\tau < \infty} \right). $$

From now onwards, we suppose that the function $u$ is superharmonic on $\mathbb{Z}^d \setminus D$, i.e., we suppose that $u$ is such that

$$ (3.3) \quad \forall y \in \mathbb{Z}^d \setminus D \quad u(y) \ge V(y) = \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} u(z). $$

We denote by $S^+$ the collection of the positive functions $u$ defined on $\mathbb{Z}^d$ which satisfy (3.3). The superharmonicity of $u$ implies that

$$ (3.4) \quad \sum_{y \in \mathbb{Z}^d} \left( \ln \frac{u(y)}{V(y)} \right) L_{n \wedge \tau}(y) \ge \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_{n \wedge \tau}(y). $$

Reporting inequality (3.4) in inequality (3.2), we get

$$ u(x) \ge E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_{n \wedge \tau}(y) \right) u(S_{n \wedge \tau}) 1_{\tau < \infty} \right). $$

On the event $\tau < \infty$, we have

$$ \forall y \in D \quad \lim_{n \to \infty} L_{n \wedge \tau}(y) = L_{\tau}(y) = L_{t}^{D}(y), \quad \lim_{n \to \infty} S_{n \wedge \tau} = S_{\tau}. $$

By Fatou's lemma, we have

$$ u(x) \ge E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_t^D(y) \right) u(S_\tau) 1_{\tau < \infty} \right). $$

Yet $S_\tau$ belongs to $\bar{D}$, thus

$$ (3.5) \quad u(x) \ge \left( \inf_{y \in \bar{D}} u(y) \right) E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_t^D(y) \right) 1_{\tau < \infty} \right). $$

Recall that

$$ \bar{D} = D \cup \{ x \in \mathbb{Z}^d : \exists y \in D \ |x - y| = 1 \}. $$
*Proof.* — Let $u$ be a positive function defined on $\mathbb{Z}^d$ and let $x \in \mathbb{Z}^d$. Let $(M_n)_{n \in \mathbb{N}}$ be the martingale constructed with the function $u$ and the random walk $(S_n)_{n \in \mathbb{N}}$, defined in Section 3.1. We first remark that $\tau(D, t)$ is a stopping time for $(M_n)_{n \in \mathbb{N}}$. Indeed, the event $\{\tau(D, t) = n\}$ is measurable with respect to $L_n(D)$, hence also to $S_1, \dots, S_{n-1}$. We apply next the optional stopping theorem. Let $t, n \ge 1$, we have

$$E_x(M_{n \wedge \tau(D, t)}) = E_x(M_0) = u(x).$$

We note simply $\tau$ instead of $\tau(D, t)$ and we bound from below the left hand member:

$$ (3.2) \quad E_x(M_{n \wedge \tau}) \ge E_x(M_{n \wedge \tau} 1_{\tau < \infty}) \\ = E_x \left( \exp \left( \sum_{y \in \mathbb{Z}^d} \left( \ln \frac{u(y)}{V(y)} \right) L_{n \wedge \tau}(y) \right) u(S_{n \wedge \tau}) 1_{\tau < \infty} \right). $$

From now onwards, we suppose that the function $u$ is superharmonic on $\mathbb{Z}^d \setminus D$, i.e., we suppose that $u$ is such that

$$ (3.3) \quad \forall y \in \mathbb{Z}^d \setminus D \quad u(y) \ge V(y) = \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} u(z). $$

We denote by $S^+$ the collection of the positive functions $u$ defined on $\mathbb{Z}^d$ which satisfy (3.3). The superharmonicity of $u$ implies that

$$ (3.4) \quad \sum_{y \in \mathbb{Z}^d} \left( \ln \frac{u(y)}{V(y)} \right) L_{n \wedge \tau}(y) \ge \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_{n \wedge \tau}(y). $$

Reporting inequality (3.4) in inequality (3.2), we get

$$ u(x) \ge E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_{n \wedge \tau}(y) \right) u(S_{n \wedge \tau}) 1_{\tau < \infty} \right). $$

On the event $\tau < \infty$, we have

$$ \forall y \in D \quad \lim_{n \to \infty} L_{n \wedge \tau}(y) = L_{\tau}(y) = L_{t}^{D}(y), \quad \lim_{n \to \infty} S_{n \wedge \tau} = S_{\tau}. $$

By Fatou's lemma, we have

$$ u(x) \ge E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_t^D(y) \right) u(S_\tau) 1_{\tau < \infty} \right). $$

Yet $S_\tau$ belongs to $\bar{D}$, thus

$$ (3.5) \quad u(x) \ge \left( \inf_{y \in \bar{D}} u(y) \right) E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_t^D(y) \right) 1_{\tau < \infty} \right). $$

Recall that

$$ \bar{D} = D \cup \{ x \in \mathbb{Z}^d : \exists y \in D \ |x - y| = 1 \}. $$
Taking now the infimum over $x \in \bar{D}$, we obtain

$$ (3.6) \quad \inf_{x \in \bar{D}} E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_t^D(y) \right) 1_{\tau < \infty} \right) \le 1. $$

We proceed by bounding from below the left hand member of (3.6) as follows: for any $x \in \bar{D}$,

$$ \begin{align} (3.7) \quad E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_t^D(y) \right) 1_{\tau < \infty} \right) & \ge E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_t^D(y) \right) ; \tau < \infty, \frac{1}{t} L_t^D \in C \right) \nonumber \\ & \ge \exp \left( \inf_{g \in C} \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) tg(y) \right) P_x \left( \frac{1}{t} L_t^D \in C, \tau < \infty \right). \end{align} $$

Let us define

$$ (3.8) \quad \phi_t(C) = \inf_{x \in D} P_x \left( \frac{1}{t} L_t^D \in C, \tau < \infty \right). $$

Whenever $\tau < \infty$, the function $\frac{1}{t}L_t^D$ belongs to the set $M_1(D)$ defined by

$$ M_1(D) = \left\{ \phi \in \ell^1(D) : \sum_{x \in D} \phi(x) = 1, \forall x \in D \quad 0 \le \phi(x) \le 1 \right\}. $$

Therefore we can replace the set $C$ by its intersection with $M_1(D)$ in formula (3.7) and the previous inequalities yield that

$$ (3.9) \quad \phi_t(C) \le \exp \left( -t \inf_{g \in C \cap M_1(D)} \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) g(y) \right). $$

This inequality holds for any function $u$ in $S^+$. In order to get a functional which is convex, we perform a change of functions and we set $\phi = \ln u$. We denote by $\mathcal{T}$ the image of $S^+$ under this change of functions, i.e.,

$$ \mathcal{T} = \left\{ \ln u : u \in \S^+ \right\}. $$

We rewrite inequality (3.9) as follows: for any $\phi \in \mathcal{T}$, (3.10)

$$ \phi_t(C) \le \exp \left( -t \inf_{g \in C \cap M_1(D)} \sum_{y \in D} -\ln \left( \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} \exp(\phi(z) - \phi(y)) \right) g(y) \right). $$

We define a map $\Phi$ on $\mathcal{T} \times M_1(D)$ by

$$ \Phi(\phi, g) = \sum_{y \in D} -\ln \left( \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} \exp(\phi(z) - \phi(y)) \right) g(y). $$
Taking now the infimum over $x \in \bar{D}$, we obtain

$$ (3.6) \quad \inf_{x \in \bar{D}} E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_t^D(y) \right) 1_{\tau < \infty} \right) \le 1. $$

We proceed by bounding from below the left hand member of (3.6) as follows: for any $x \in \bar{D}$,

$$ \begin{align} (3.7) \quad E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_t^D(y) \right) 1_{\tau < \infty} \right) &\ge E_x \left( \exp \left( \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) L_t^D(y) \right) ; \tau < \infty, \frac{1}{t} L_t^D \in C \right) \nonumber \\ &\ge \exp \left( \inf_{g \in C} \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) tg(y) \right) P_x \left( \frac{1}{t} L_t^D \in C, \tau < \infty \right). \end{align} $$

Let us define

$$ (3.8) \quad \phi_t(C) = \inf_{x \in D} P_x \left( \frac{1}{t} L_t^D \in C, \tau < \infty \right). $$

Whenever $\tau < \infty$, the function $\frac{1}{t} L_t^D$ belongs to the set $M_1(D)$ defined by

$$ M_1(D) = \left\{ \phi \in \ell^1(D) : \sum_{x \in D} \phi(x) = 1, \forall x \in D \quad 0 \le \phi(x) \le 1 \right\}. $$

Therefore we can replace the set $C$ by its intersection with $M_1(D)$ in formula (3.7) and the previous inequalities yield that

$$ (3.9) \quad \phi_t(C) \le \exp \left( -t \inf_{g \in C \cap M_1(D)} \sum_{y \in D} \left( \ln \frac{u(y)}{V(y)} \right) g(y) \right). $$

This inequality holds for any function $u$ in $S^+$. In order to get a functional which is convex, we perform a change of functions and we set $\phi = \ln u$. We denote by $\mathcal{T}$ the image of $S^+$ under this change of functions, i.e.,

$$ \mathcal{T} = \left\{ \ln u : u \in \S^+ \right\}. $$

We rewrite inequality (3.9) as follows: for any $\phi \in \mathcal{T}$, (3.10)

$$ \phi_t(C) \le \exp \left( -t \inf_{g \in C \cap M_1(D)} \sum_{y \in D} \ln \left( \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} \exp(\phi(z) - \phi(y)) \right) g(y) \right). $$

We define a map $\Phi$ on $\mathcal{T} \times M_1(D)$ by

$$ \Phi(\phi, g) = \sum_{y \in D} - \ln \left( \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} \exp(\phi(z) - \phi(y)) \right) g(y). $$
Optimizing the previous inequality (3.10) over the function $\phi$, we get

$$ (3.11) \qquad \phi_t(C) \le \exp \left( -t \sup_{\phi \in \mathcal{T}} \inf_{g \in C \cap M_1(D)} \Phi(\phi, g) \right). $$

The map $\Phi$ is linear in $g$. We shall next prove that it is convex in $\phi$. In fact, the convexity in $\phi$ is a consequence of the convexity of the functions $t \in \mathbb{R} \mapsto \exp(t)$ and $t \in \mathbb{R}^+ \mapsto -\ln(t)$. The delicate point is to check that the domain of definition of $\Phi$ is convex. This is the purpose of the next Lemma 3.3.

**LEMMA 3.3.** — The set $\mathcal{T}$ is convex.

*Proof.* — Let $\phi, \psi$ belong to $\mathcal{T}$ and let $\alpha, \beta \in ]0, 1[$ be such that $\alpha + \beta = 1$. There exist $u, v \in \mathbb{S}^+$ such that $\phi = \ln u, \psi = \ln v$, whence

$$ \alpha\phi + \beta\psi = \ln(u^{\alpha}v^{\beta}), $$

and we have to check that $w = u^{\alpha}v^{\beta}$ is in $\mathcal{S}^+$. Let $y$ be a fixed point in $\mathbb{Z}^d \setminus D$. We apply the discrete Hölder inequality to the functions $u^{\alpha}, v^{\beta}$, with respect to the measure $\nu_y$ which is the uniform measure on the neighbours of $y$,

$$ \nu_y = \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} \delta_z, $$

and with the exponents $p = 1/\alpha, q = 1/\beta$. We obtain

$$ \int u^{\alpha} v^{\beta} d\nu_y \le \left( \int u d\nu_y \right)^{\alpha} \left( \int v d\nu_y \right)^{\beta}. $$

This inequality can be rewritten as

$$ \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} u^{\alpha}(z) v^{\beta}(z) \le \left( \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} u(z) \right)^{\alpha} \left( \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} v(z) \right)^{\beta} $$

We finally use the fact that $u, v$ are superharmonic to conclude. $\square$

Since the set $D$ is finite, the set $\ell^1(D)$ is finite dimensional, and the map $\Phi$ is continuous with respect to $g$ and any norm on $\ell^1(D)$. Similarly, for any $\phi \in \mathcal{T}$ and $g \in M_1(D)$, the quantity $\Phi(\phi, g)$ depends only on the values of $\phi$ on the set $\bar{D}$, which is finite, thus the map $\Phi$ is also continuous with respect to $\phi$ and the $\ell^1$ norm. Moreover the set $C \cap M_1(D)$ is compact and convex (these are essential conditions in order to apply the minimax theorem). Therefore, by the famous minimax theorem (see [Fan53]),

$$ (3.12) \qquad \sup_{\phi \in \mathcal{T}} \inf_{g \in C \cap M_1(D)} \Phi(\phi, g) = \inf_{g \in C \cap M_1(D)} \sup_{\phi \in \mathcal{T}} \Phi(\phi, g). $$
Optimizing the previous inequality (3.10) over the function $\phi$, we get

$$ (3.11) \qquad \phi_t(C) \le \exp \left( -t \sup_{\phi \in \mathcal{T}} \inf_{g \in C \cap M_1(D)} \Phi(\phi, g) \right). $$

The map $\Phi$ is linear in $g$. We shall next prove that it is convex in $\phi$. In fact, the convexity in $\phi$ is a consequence of the convexity of the functions $t \in \mathbb{R} \mapsto \exp(t)$ and $t \in \mathbb{R}^+ \mapsto -\ln(t)$. The delicate point is to check that the domain of definition of $\Phi$ is convex. This is the purpose of the next Lemma 3.3.

**LEMMA 3.3.** — The set $\mathcal{T}$ is convex.

*Proof.* — Let $\phi, \psi$ belong to $\mathcal{T}$ and let $\alpha, \beta \in ]0, 1[$ be such that $\alpha + \beta = 1$. There exist $u, v \in \mathbb{S}^+$ such that $\phi = \ln u, \psi = \ln v$, whence

$$ \alpha\phi + \beta\psi = \ln(u^{\alpha}v^{\beta}), $$

and we have to check that $w = u^{\alpha}v^{\beta}$ is in $\mathcal{S}^+$. Let $y$ be a fixed point in $\mathbb{Z}^d \setminus D$. We apply the discrete Hölder inequality to the functions $u^{\alpha}, v^{\beta}$, with respect to the measure $\nu_y$ which is the uniform measure on the neighbours of $y$,

$$ \nu_y = \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} \delta_z, $$

and with the exponents $p = 1/\alpha, q = 1/\beta$. We obtain

$$ \int u^{\alpha} v^{\beta} d\nu_y \le \left( \int u d\nu_y \right)^{\alpha} \left( \int v d\nu_y \right)^{\beta}. $$

This inequality can be rewritten as

$$ \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} u^{\alpha}(z) v^{\beta}(z) \le \left( \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} u(z) \right)^{\alpha} \left( \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} v(z) \right)^{\beta} $$

We finally use the fact that $u, v$ are superharmonic to conclude. $\square$

Since the set $D$ is finite, the set $\ell^1(D)$ is finite dimensional, and the map $\Phi$ is continuous with respect to $g$ and any norm on $\ell^1(D)$. Similarly, for any $\phi \in \mathcal{T}$ and $g \in M_1(D)$, the quantity $\Phi(\phi, g)$ depends only on the values of $\phi$ on the set $\bar{D}$, which is finite, thus the map $\Phi$ is also continuous with respect to $\phi$ and the $\ell^1$ norm. Moreover the set $C \cap M_1(D)$ is compact and convex (these are essential conditions in order to apply the minimax theorem). Therefore, by the famous minimax theorem (see [Fan53]),

$$ (3.12) \qquad \sup_{\phi \in \mathcal{T}} \inf_{g \in C \cap M_1(D)} \Phi(\phi, g) = \inf_{g \in C \cap M_1(D)} \sup_{\phi \in \mathcal{T}} \Phi(\phi, g). $$
Let us fix $g \in C \cap M_1(D)$ and let us bound from below $\sup_{\phi \in \mathcal{T}} \Phi(\phi, g)$. Let us fix $\phi \in \mathcal{T}$, we have, by convexity of $-\ln$,

$$ \Phi(\phi, g) \geq -\ln \left( \sum_{y \in D} \left( \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} \exp(\phi(z) - \phi(y)) \right) g(y) \right). $$

Using the inequality $-\ln(t) \geq 1 - t$ for $t > 0$, we get

$$ (3.13) \qquad \Phi(\phi, g) \geq 1 - \sum_{y \in D} \left( \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} \exp(\phi(z) - \phi(y)) \right) g(y) $$

Let $\varepsilon$ be such that

$$ 0 < \varepsilon < \min \{ g(x) : x \in D, g(x) > 0 \}. $$

We define next an adequate function $u_\varepsilon$. The entrance time $T_0$ of $D$ is

$$ T_0 = \inf \{ n \geq 0 : S_n \in D \}. $$

We define

$$ \forall x \in \mathbb{Z}^d \quad u_\varepsilon(x) = E_x \left( \sqrt{\max(g(S_{T_0}), \varepsilon)} \mid T_0 < \infty \right). $$

With this definition, we have that

$$ \forall x \in D \quad u_\varepsilon(x) = \sqrt{\max(g(x), \varepsilon)}. $$

We claim that this function $u_\varepsilon$ belongs to $\mathcal{S}^+$. Obviously it is strictly positive everywhere. The function $u_\varepsilon$ is harmonic on $\mathbb{Z}^d \setminus D$, hence it is also superharmonic. We apply inequality (3.13) with the function $\phi_\varepsilon(x) = \ln u_\varepsilon$ and we get

$$ \begin{align} \sup_{\phi \in \mathcal{T}} \Phi(\phi, g) &\geq \Phi(\phi_\varepsilon, g) = 1 - \sum_{y \in D, g(y) > 0} \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} \frac{u_\varepsilon(z)}{u_\varepsilon(y)} g(y) \nonumber \\ (3.14) \qquad &\qquad = 1 - \sum_{y \in D, g(y) > 0} \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} \frac{u_\varepsilon(z)}{\sqrt{\max(g(y), \varepsilon)}} g(y) \nonumber \\ &\qquad = 1 - \sum_{y \in D} \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} u_\varepsilon(z) \sqrt{g(y)}. \end{align} $$

This inequality holds for $\varepsilon > 0$ sufficiently small. We send next $\varepsilon$ to 0. We have

$$ \forall x \in \mathbb{Z}^d \quad \lim_{\varepsilon \to 0} u_\varepsilon(x) = E_x \left( \sqrt{g(S_{T_0})} \mid T_0 < \infty \right). $$

Passing to the limit as $\varepsilon$ goes to 0 in inequality (3.14), we get

$$ (3.15) \qquad \sup_{\phi \in \mathcal{T}} \Phi(\phi, g) \geq 1 - \sum_{y \in D} \frac{1}{2d} \sum_{\substack{z \in \mathbb{Z}^d \\ |y-z|=1}} E_z \left( \sqrt{g(S_{T_0})} \mid T_0 < \infty \right) \sqrt{g(y)}. $$
Let us introduce the hitting time $T_1$ of $D$ as

$$T_1 = \inf \{ n \ge 1 : S_n \in D \}.$$

Notice that the entrance and hitting time are equal whenever the starting point is in $\mathbb{Z}^d \setminus D$. However, if the starting point belongs to $D$, then $T_0 = 0$ and $T_1 \ge 1$. With the help of $T_1$, we rewrite formula (3.15) as

$$ (3.16) \quad \sup_{\phi \in \mathcal{T}} \Phi(\phi, g) \ge 1 - \sum_{y \in D} E_y \left( \sqrt{g(S_{T_1})} \middle| T_0 < \infty \right) \sqrt{g(y)} \\ = 1 - \sum_{y \in D} \sum_{z \in D} P_y \left( S_{T_1} = z \middle| T_0 < \infty \right) \sqrt{g(z)} \sqrt{g(y)}. $$

Using the time reversibility of the random walk $(S_n)_{n \in \mathbb{N}}$, we have

$$ (3.17) \quad \forall y, z \in D \quad P_y(S_{T_1} = z \mid T_0 < \infty) = P_z(S_{T_1} = y \mid T_0 < \infty), $$

whence

$$ (3.18) \quad \sum_{y \in D} \sum_{z \in D} P_y(S_{T_1} = z \mid T_0 < \infty) g(z) \\ = \sum_{z \in D} \sum_{y \in D} P_z(S_{T_1} = y \mid T_0 < \infty) g(z) = \sum_{z \in D} g(z) = 1. $$

The identities (3.18) yield that

$$ (3.19) \quad 1 - \sum_{y \in D} \sum_{z \in D} P_y(S_{T_1} = z \mid T_0 < \infty) \sqrt{g(z)} \sqrt{g(y)} \\ = \frac{1}{2} \sum_{y \in D} \sum_{z \in D} P_y(S_{T_1} = z \mid T_0 < \infty) \left( \sqrt{g(z)} - \sqrt{g(y)} \right)^2. $$

Reporting (3.19) in (3.16), we get

$$ (3.20) \quad \sup_{\phi \in \mathcal{T}} \Phi(\phi, g) \ge \frac{1}{2} \sum_{y \in D} \sum_{z \in D} P_y(S_{T_1} = z \mid T_0 < \infty) \left( \sqrt{g(z)} - \sqrt{g(y)} \right)^2. $$

Now, for any $y, z \in D$ such that $|y - z| = 1$, we have

$$ P_y(S_{T_1} = z \mid T_0 < \infty) \ge \frac{1}{2d}, $$

thus we have the lower bound

$$ (3.21) \quad \sup_{\phi \in \mathcal{T}} \Phi(\phi, g) \ge \sum_{\substack{y, z \in D \\ |y-z|=1}} \frac{1}{2d} \left( \sqrt{g(z)} - \sqrt{g(y)} \right)^2 = \frac{1}{2} \mathcal{E} \left( \sqrt{g(D)} \right). $$

Taking the infimum with respect to $g \in C \cap M_1(D)$ and coming back to inequality (3.11), we obtain the desired result. □

To clarify the proof of Theorem 1.4 it may be useful to consider the finite Markov chain on $D$ obtained from the simple random walk on $\mathbb{Z}^d$ by restricting it to the times when it visits $D$. This is the Markov chain where the transition probabilities are given by

$$ q(y, z) = P_y(S_{T_1} = z). $$
Let us introduce the hitting time $T_1$ of $D$ as

$$T_1 = \inf \{ n \ge 1 : S_n \in D \}.$$

Notice that the entrance and hitting time are equal whenever the starting point is in $\mathbb{Z}^d \setminus D$. However, if the starting point belongs to $D$, then $T_0 = 0$ and $T_1 \ge 1$. With the help of $T_1$, we rewrite formula (3.15) as

$$ (3.16) \quad \sup_{\phi \in \mathcal{T}} \Phi(\phi, g) \ge 1 - \sum_{y \in D} E_y \left( \sqrt{g(S_{T_1})} \middle| T_0 < \infty \right) \sqrt{g(y)} \\ = 1 - \sum_{y \in D} \sum_{z \in D} P_y \left( S_{T_1} = z \middle| T_0 < \infty \right) \sqrt{g(z)} \sqrt{g(y)}. $$

Using the time reversibility of the random walk $(S_n)_{n \in \mathbb{N}}$, we have

$$ (3.17) \quad \forall y, z \in D \quad P_y(S_{T_1} = z \mid T_0 < \infty) = P_z(S_{T_1} = y \mid T_0 < \infty), $$

whence

$$ (3.18) \quad \sum_{y \in D} \sum_{z \in D} P_y(S_{T_1} = z \mid T_0 < \infty) g(z) \\ = \sum_{z \in D} \sum_{y \in D} P_z(S_{T_1} = y \mid T_0 < \infty) g(z) = \sum_{z \in D} g(z) = 1. $$

The identities (3.18) yield that

$$ (3.19) \quad 1 - \sum_{y \in D} \sum_{z \in D} P_y(S_{T_1} = z \mid T_0 < \infty) \sqrt{g(z)} \sqrt{g(y)} \\ = \frac{1}{2} \sum_{y \in D} \sum_{z \in D} P_y(S_{T_1} = z \mid T_0 < \infty) \left(\sqrt{g(z)} - \sqrt{g(y)}\right)^2. $$

Reporting (3.19) in (3.16), we get

$$ (3.20) \quad \sup_{\phi \in \mathcal{T}} \Phi(\phi, g) \ge \frac{1}{2} \sum_{y \in D} \sum_{z \in D} P_y(S_{T_1} = z \mid T_0 < \infty) \left(\sqrt{g(z)} - \sqrt{g(y)}\right)^2. $$

Now, for any $y, z \in D$ such that $|y - z| = 1$, we have

$$ P_y(S_{T_1} = z \mid T_0 < \infty) \ge \frac{1}{2d}, $$

thus we have the lower bound

$$ (3.21) \quad \sup_{\phi \in \mathcal{T}} \Phi(\phi, g) \ge \sum_{\substack{y, z \in D \\ |y-z|=1}} \frac{1}{2d} \left(\sqrt{g(z)} - \sqrt{g(y)}\right)^2 = \frac{1}{2} \mathcal{E}\left(\sqrt{g(D)}\right). $$

Taking the infimum with respect to $g \in C \cap M_1(D)$ and coming back to inequality (3.11), we obtain the desired result. $\square$

To clarify the proof of Theorem 1.4 it may be useful to consider the finite Markov chain on $D$ obtained from the simple random walk on $\mathbb{Z}^d$ by restricting it to the times when it visits $D$. This is the Markov chain where the transition probabilities are given by

$$ q(y, z) = P_y(S_{T_1} = z). $$
On the vertices $y$ for which all neighbours are in $D$, this chain coincides with the simple random walk. However all the vertices on the boundary of $D$ are also connected to one another, and this chain can jump from any boundary vertex to any other boundary vertex. Such a jump corresponds to an excursion of the simple random walk away from $D$.

The right hand side of (3.20) is nothing but the Dirichlet energy for this Markov chain. Inequality (3.21) shows that the Dirichlet energy of this Markov chain for a function $g: D \to \mathbb{R}$ is always lower bounded by the Dirichlet energy $E(g; D)$. Indeed, we can simply restrict the sum to the transitions on $\mathbb{Z}^d$ and ignore the additional connections along the boundary.

In fact, this argument reduces the simple random walk on the infinite state space $\mathbb{Z}^d$ to a finite state space, in a way that is conceptually reminiscent of the compactification arguments employed to use Donsker-Varadhan large deviation estimates in Bolthausen's work [Bol94] and many other works on large deviations. However, the advantage of this approach is that it does not alter significantly the geometry of the ambient space. This allows us to use functional inequalities that are more readily available in $\mathbb{R}^d$ than on a torus.

### 3.5. Correction for the origin

The problem with the inequality of Theorem 1.4 is the presence of the infimum over $x \in \bar{D}$. In order to go around it, we shall take advantage of the fact that our trajectories are constrained to have a range of cardinality less than $cn^d$. We first bound from below the probability to travel between an arbitrary point of the range and the origin. To this end, we shall use a standard estimate on multinomial coefficients, that we recall next.

**LEMMA 3.4.** — For any $k \ge 1$, $r \ge 2$, any $k_1, \dots, k_r \in \{0, \dots, k\}$ such that $k_1 + \dots + k_r = k$, we have

$$ \left| \frac{1}{k} \ln \frac{k!}{k_1! \cdots k_r!} + \sum_{i=1}^{r} \frac{k_i}{k} \ln \frac{k_i}{k} \right| \le \frac{r}{k} (\ln k + 2). $$

*Proof.* — The proof of this estimate is standard (see for instance [Ell06]). Setting, for $k \in \mathbb{N}$, $f(k) = \ln k! - k \ln k + k$, we have

$$ \begin{aligned} \ln \frac{k!}{k_1! \cdots k_r!} &= \ln k! - \sum_{i=1}^{r} \ln k_i! \\ &= k \ln k - k + f(k) - \sum_{i=1}^{r} (k_i \ln k_i - k_i + f(k_i)) \\ &= - \sum_{i=1}^{r} k_i \ln \frac{k_i}{k} + f(k) - \sum_{i=1}^{r} f(k_i). \end{aligned} $$

Comparing the discrete sum

$$ \ln k! = \sum_{1 \le i \le k} \ln k $$
On the vertices $y$ for which all neighbours are in $D$, this chain coincides with the simple random walk. However all the vertices on the boundary of $D$ are also connected to one another, and this chain can jump from any boundary vertex to any other boundary vertex. Such a jump corresponds to an excursion of the simple random walk away from $D$.

The right hand side of (3.20) is nothing but the Dirichlet energy for this Markov chain. Inequality (3.21) shows that the Dirichlet energy of this Markov chain for a function $g: D \to \mathbb{R}$ is always lower bounded by the Dirichlet energy $E(g; D)$. Indeed, we can simply restrict the sum to the transitions on $\mathbb{Z}^d$ and ignore the additional connections along the boundary.

In fact, this argument reduces the simple random walk on the infinite state space $\mathbb{Z}^d$ to a finite state space, in a way that is conceptually reminiscent of the compactification arguments employed to use Donsker-Varadhan large deviation estimates in Bolthausen's work [Bol94] and many other works on large deviations. However, the advantage of this approach is that it does not alter significantly the geometry of the ambient space. This allows us to use functional inequalities that are more readily available in $\mathbb{R}^d$ than on a torus.

### 3.5. Correction for the origin

The problem with the inequality of Theorem 1.4 is the presence of the infimum over $x \in \bar{D}$. In order to go around it, we shall take advantage of the fact that our trajectories are constrained to have a range of cardinality less than $cn^d$. We first bound from below the probability to travel between an arbitrary point of the range and the origin. To this end, we shall use a standard estimate on multinomial coefficients, that we recall next.

**LEMMA 3.4.** — For any $k \ge 1$, $r \ge 2$, any $k_1, \dots, k_r \in \{0, \dots, k\}$ such that $k_1 + \dots + k_r = k$, we have

$$ \left| \frac{1}{k} \ln \frac{k!}{k_1! \cdots k_r!} + \sum_{i=1}^{r} \frac{k_i}{k} \ln \frac{k_i}{k} \right| \le \frac{r}{k} (\ln k + 2). $$

*Proof.* — The proof of this estimate is standard (see for instance [Ell06]). Setting, for $k \in \mathbb{N}$, $f(k) = \ln k! - k \ln k + k$, we have

$$ \begin{aligned} \ln \frac{k!}{k_1! \cdots k_r!} &= \ln k! - \sum_{i=1}^{r} \ln k_i! \\ &= k \ln k - k + f(k) - \sum_{i=1}^{r} (k_i \ln k_i - k_i + f(k_i)) \\ &= - \sum_{i=1}^{r} k_i \ln \frac{k_i}{k} + f(k) - \sum_{i=1}^{r} f(k_i). \end{aligned} $$

Comparing the discrete sum

$$ \ln k! = \sum_{1 \le i \le k} \ln k $$
to the integral $\int_1^k \ln x \, dx$, we see that $1 \le f(k) \le \ln k + 2$ for all $k \ge 1$. On one hand,

$$f(k) - \sum_{i=1}^{r} f(k_i) \le \ln k + 2 - r \le r(\ln k + 2),$$

on the other hand,

$$f(k) - \sum_{i=1}^{r} f(k_i) \ge 1 - \sum_{i=1}^{r} (\ln k_i + 2) \ge 1 - 2r - r \ln k \ge -r(\ln k + 2)$$

and we have the desired inequalities.

<figure><img src="image_2.png" /></figure>

The box of side length $r > 0$ centered at the origin is the set

$$\Lambda(r) = \{ (x_1, \dots, x_d) \in \mathbb{R}^d : \forall i \in \{1, \dots, d\} \text{, } -r/2 < x_i \le r/2 \}.$$

With the help of Lemma 3.4, we obtain the following lower bound for the symmetric random walk.

**LEMMA 3.5.** — Let $c > 0$. There exists $c' > 0$ such that, for $n$ large enough,

$$\forall k \in \{n^{d+1}, \dots, n^{d+2}\}, \quad \forall x \in \Lambda cn^d,$$

$$P_x(S_k = 0) + P_x(S_{k-1} = 0) \ge \exp(-c'n^{2d}/k).$$

*Proof.* — Let $x = (x_1, \dots, x_d) \in \Lambda cn^d$ and let $k \in \{n^{d+1}, \dots, n^{d+2}\}$. We have

$$P_x(S_k = 0) = P_0(S_k = x) = \sum_{\substack{i_1, \dots, i_d \\ j_1, \dots, j_d}} \frac{k!}{(2d)^k i_1! j_1! \cdots i_d! j_d!},$$

where the sum runs over the indices $i_1, j_1, \dots, i_d, j_d$ such that

$$i_1 - j_1 = x_1, \dots, i_d - j_d = x_d, \quad i_1 + j_1 + \dots + i_d + j_d = k.$$

The index $i_1$ corresponds to the number of moves associated to the vector $(1, 0, \dots, 0)$, the index $j_1$ to the number of moves associated to the vector $(-1, 0, \dots, 0)$, and so on. This set of indices is empty in the case where $k$ and $x_1 + \dots + x_d$ don't have the same parity, that is why we have to consider the sum $P_x(S_k = 0) + P_x(S_{k-1} = 0)$. To simplify the discussion, we assume that the term $P_x(S_k = 0)$ is non-zero. We will get the desired lower bound by considering only one term in the sum, the term corresponding to

$$i_1 = \frac{k}{2d} + \frac{x_1}{2}, \quad j_1 = \frac{k}{2d} - \frac{x_1}{2}, \dots, i_d = \frac{k}{2d} + \frac{x_d}{2}, \quad j_d = \frac{k}{2d} - \frac{x_d}{2}.$$

To be precise, we should take integer parts in the above formula, but this would become a bit messy, so we do as if all the fractions were integers. We get that

$$P_x(S_k = 0) \ge \frac{1}{(2d)^k} \frac{k!}{\left(\frac{k}{2d} + \frac{x_1}{2}\right)! \left(\frac{k}{2d} - \frac{x_1}{2}\right)! \cdots \left(\frac{k}{2d} + \frac{x_d}{2}\right)! \left(\frac{k}{2d} - \frac{x_d}{2}\right)!}.$$
to the integral $\int_1^k \ln x \, dx$, we see that $1 \le f(k) \le \ln k + 2$ for all $k \ge 1$. On one hand,

$$f(k) - \sum_{i=1}^{r} f(k_i) \le \ln k + 2 - r \le r(\ln k + 2),$$

on the other hand,

$$f(k) - \sum_{i=1}^{r} f(k_i) \ge 1 - \sum_{i=1}^{r} (\ln k_i + 2) \ge 1 - 2r - r \ln k \ge -r(\ln k + 2)$$

and we have the desired inequalities.

<figure><img src="image_4.png" /></figure>

The box of side length $r > 0$ centered at the origin is the set

$$\Lambda(r) = \{ (x_1, \dots, x_d) \in \mathbb{R}^d : \forall i \in \{1, \dots, d\} \text{, } -r/2 < x_i \le r/2 \}.$$

With the help of Lemma 3.4, we obtain the following lower bound for the symmetric random walk.

**LEMMA 3.5.** — Let $c > 0$. There exists $c' > 0$ such that, for $n$ large enough,

$$\forall k \in \{n^{d+1}, \dots, n^{d+2}\}, \quad \forall x \in \Lambda cn^d, \\ P_x(S_k = 0) + P_x(S_{k-1} = 0) \ge \exp(-c'n^{2d}/k).$$

*Proof.* — Let $x = (x_1, \dots, x_d) \in \Lambda cn^d$ and let $k \in \{n^{d+1}, \dots, n^{d+2}\}$. We have

$$P_x(S_k = 0) = P_0(S_k = x) = \sum_{\substack{i_1, \dots, i_d \\ j_1, \dots, j_d}} \frac{k!}{(2d)^k i_1! j_1! \cdots i_d! j_d!},$$

where the sum runs over the indices $i_1, j_1, \dots, i_d, j_d$ such that

$$i_1 - j_1 = x_1, \dots, i_d - j_d = x_d, \quad i_1 + j_1 + \dots + i_d + j_d = k.$$

The index $i_1$ corresponds to the number of moves associated to the vector $(1, 0, \dots, 0)$, the index $j_1$ to the number of moves associated to the vector $(-1, 0, \dots, 0)$, and so on. This set of indices is empty in the case where $k$ and $x_1 + \dots + x_d$ don't have the same parity, that is why we have to consider the sum $P_x(S_k = 0) + P_x(S_{k-1} = 0)$. To simplify the discussion, we assume that the term $P_x(S_k = 0)$ is non-zero. We will get the desired lower bound by considering only one term in the sum, the term corresponding to

$$i_1 = \frac{k}{2d} + \frac{x_1}{2}, \quad j_1 = \frac{k}{2d} - \frac{x_1}{2}, \dots, i_d = \frac{k}{2d} + \frac{x_d}{2}, \quad j_d = \frac{k}{2d} - \frac{x_d}{2}.$$

To be precise, we should take integer parts in the above formula, but this would become a bit messy, so we do as if all the fractions were integers. We get that

$$P_x(S_k = 0) \ge \frac{1}{(2d)^k} \frac{k!}{\left(\frac{k}{2d} + \frac{x_1}{2}\right)! \left(\frac{k}{2d} - \frac{x_1}{2}\right)! \cdots \left(\frac{k}{2d} + \frac{x_d}{2}\right)! \left(\frac{k}{2d} - \frac{x_d}{2}\right)!}.$$
Taking the ln and using the inequality of Lemma 3.4, we obtain

$$
\begin{align*}
\ln P_x(S_k = 0) &\ge -k \ln(2d) \\
&\quad - \sum_{i=1}^d \left(\frac{k}{2d} + \frac{x_i}{2}\right) \ln \left(\frac{1}{2d} + \frac{x_i}{2k}\right) + \left(\frac{k}{2d} - \frac{x_i}{2}\right) \ln \left(\frac{1}{2d} - \frac{x_i}{2k}\right) - 2d(\ln k + 2) \\
&\ge - \sum_{i=1}^d \left(\frac{k}{2d} + \frac{x_i}{2}\right) \ln \left(1 + \frac{dx_i}{k}\right) + \left(\frac{k}{2d} - \frac{x_i}{2}\right) \ln \left(1 - \frac{dx_i}{k}\right) - 2d(\ln k + 2) \\
&\ge - \sum_{i=1}^d \left(\frac{k}{2d} + \frac{x_i}{2}\right) \left(\frac{dx_i}{k}\right) - \left(\frac{k}{2d} - \frac{x_i}{2}\right) \left(\frac{dx_i}{k}\right) - 2d(\ln k + 2) \\
&\ge - \sum_{i=1}^d \left(\frac{d}{k}\right) x_i^2 - 2d(\ln k + 2) \ge -d \left(\frac{d}{k}\right) (cn^d)^2 - 2d(\ln k + 2).
\end{align*}
$$

Using the hypothesis on $k$, we conclude that

$$
\ln P_x(S_k = 0) \ge -d^2 c^2 \left(\frac{n^{2d}}{k}\right) - 2d((d+2)\ln n + 2).
$$

Since $n^{2d}/k \ge n^{d-2} \ge n$, then for $n$ large enough, we obtain the desired estimate. $\square$

We will use Lemma 3.5 together with the next proposition in order to have a
deviation inequality for the trajectories starting from the origin. The idea is to
let the random walk evolve naturally over a certain time interval, so that it has a
chance to visit all the points of $\bar{D}$, and in particular the point of $\bar{D}$ realizing the
infimum in the inequality of Theorem 1.4. Of course, we are forced to introduce a
correcting factor, but we will adjust our parameters so that this correcting factor is
not disturbing.

PROPOSITION 3.6. — Let $D$ be an arbitrary subset of $\mathbb{Z}^d$ and let $g$ be a function in $\ell^1(D)$. Let $k, t$ be positive integers with $k < t$. Let $r > 0$. For any $x \in \bar{D}$, we have

$$
P\left(\left\| \frac{1}{t} L_t^D - g^2 \right\|_{1, D} \le r, \tau < \infty \right) \le \frac{2 P_x\left(\left\| \frac{1}{t} L_t^D - g^2 \right\|_{1, D} \le r + 4 \frac{k}{t-k}, \tau < \infty \right)}{P_x(S_k = 0) + P_x(S_{k-1} = 0)}.
$$

*Proof.* — Let $s, t$ be such that $0 < s < t$. We have

$$
\begin{equation} \tag{3.22}
\begin{split}
\left\| \frac{1}{t} L_t^D - \frac{1}{s} L_s^D \right\|_{1,D} &\le \left\| \frac{1}{t} L_t^D - \frac{1}{s} L_t^D \right\|_{1,D} + \left\| \frac{1}{s} L_t^D - \frac{1}{s} L_s^D \right\|_{1,D} \\
&\le \left| \frac{1}{t} - \frac{1}{s} \right| t + \frac{t-s}{s} \le 2 \frac{t-s}{s}.
\end{split}
\end{equation}
$$

Let $x \in \mathbb{Z}^d$ be an arbitrary starting point. Let also $r > 0$ and let $g$ be an arbitrary function from $D$ to $\mathbb{R}$. We condition on the state visited by the random walk at
Taking the ln and using the inequality of Lemma 3.4, we obtain

$$
\begin{align*}
\ln P_x(S_k = 0) &\ge -k \ln(2d) \\
&\quad - \sum_{i=1}^d \left(\frac{k}{2d} + \frac{x_i}{2}\right) \ln \left(\frac{1}{2d} + \frac{x_i}{2k}\right) + \left(\frac{k}{2d} - \frac{x_i}{2}\right) \ln \left(\frac{1}{2d} - \frac{x_i}{2k}\right) - 2d(\ln k + 2) \\
&\ge - \sum_{i=1}^d \left(\frac{k}{2d} + \frac{x_i}{2}\right) \ln \left(1 + \frac{dx_i}{k}\right) + \left(\frac{k}{2d} - \frac{x_i}{2}\right) \ln \left(1 - \frac{dx_i}{k}\right) - 2d(\ln k + 2) \\
&\ge - \sum_{i=1}^d \left(\frac{k}{2d} + \frac{x_i}{2}\right) \left(\frac{dx_i}{k}\right) - \left(\frac{k}{2d} - \frac{x_i}{2}\right) \left(\frac{dx_i}{k}\right) - 2d(\ln k + 2) \\
&\ge - \sum_{i=1}^d \left(\frac{d}{k}\right) x_i^2 - 2d(\ln k + 2) \ge -d \left(\frac{d}{k}\right) (cn^d)^2 - 2d(\ln k + 2).
\end{align*}
$$

Using the hypothesis on $k$, we conclude that

$$
\ln P_x(S_k = 0) \ge -d^2 c^2 \left(\frac{n^{2d}}{k}\right) - 2d((d+2)\ln n + 2).
$$

Since $n^{2d}/k \ge n^{d-2} \ge n$, then for $n$ large enough, we obtain the desired estimate. $\square$

We will use Lemma 3.5 together with the next proposition in order to have a
deviation inequality for the trajectories starting from the origin. The idea is to
let the random walk evolve naturally over a certain time interval, so that it has a
chance to visit all the points of $\bar{D}$, and in particular the point of $\bar{D}$ realizing the
infimum in the inequality of Theorem 1.4. Of course, we are forced to introduce a
correcting factor, but we will adjust our parameters so that this correcting factor is
not disturbing.

PROPOSITION 3.6. — Let $D$ be an arbitrary subset of $\mathbb{Z}^d$ and let $g$ be a function in $\ell^1(D)$. Let $k, t$ be positive integers with $k < t$. Let $r > 0$. For any $x \in \bar{D}$, we have

$$
P\left(\left\| \frac{1}{t} L_t^D - g^2 \right\|_{1, D} \le r, \tau < \infty \right) \le \frac{2 P_x\left(\left\| \frac{1}{t} L_t^D - g^2 \right\|_{1, D} \le r + 4 \frac{k}{t-k}, \tau < \infty \right)}{P_x(S_k = 0) + P_x(S_{k-1} = 0)}.
$$

*Proof.* — Let $s, t$ be such that $0 < s < t$. We have

$$
\begin{equation} \tag{3.22}
\begin{split}
\left\| \frac{1}{t} L_t^D - \frac{1}{s} L_s^D \right\|_{1, D} &\le \left\| \frac{1}{t} L_t^D - \frac{1}{s} L_t^D \right\|_{1, D} + \left\| \frac{1}{s} L_t^D - \frac{1}{s} L_s^D \right\|_{1, D} \\
&\le \left| \frac{1}{t} - \frac{1}{s} \right| t + \frac{t-s}{s} \le 2 \frac{t-s}{s}.
\end{split}
\end{equation}
$$

Let $x \in \mathbb{Z}^d$ be an arbitrary starting point. Let also $r > 0$ and let $g$ be an arbitrary function from $D$ to $\mathbb{R}$. We condition on the state visited by the random walk at
time $t-s$, we apply the strong Markov property and we use twice the inequality (3.22) to get:

$$
\begin{align*}
(3.23) \quad P_x\left(\left\|\frac{1}{t}L_t^D - g^2\right\|_{1,D} \le r, \tau < \infty\right) & \\
&\ge \sum_{y \in \mathbb{Z}^d} P_y\left(S_{t-s} = y, \left\|\frac{1}{s}(L_t^D - L_s^D) - g^2\right\|_{1,D} \le r - 2\frac{t-s}{s}, \tau < \infty\right) \\
&\ge \sum_{y \in \mathbb{Z}^d} P_x(S_{t-s} = y) P_y\left(\left\|\frac{1}{s}L_s^D - g^2\right\|_{1,D} \le r - 2\frac{t-s}{s}, \tau < \infty\right) \\
&\ge P_x(S_{t-s} = 0) P\left(\left\|\frac{1}{t}L_t^D - g^2\right\|_{1,D} \le r - 4\frac{t-s}{s}, \tau < \infty\right). \end{align*}
$$

It might happen that $P_x(S_{t-s} = 0)$ vanishes if $|x|_1$ and $t-s$ don't have the same parity. To avoid this nasty detail, we apply the inequality with $s+1$ instead of $s$. Noting that

$$ \frac{t-s-1}{s+1} \le \frac{t-s}{s}, $$

we get

$$
\begin{align*}
P_x \left( \left\| \frac{1}{t} L_t^D - g^2 \right\|_{1,D} \le r, \tau < \infty \right) & \\
&\ge P_x(S_{t-s-1} = 0) P \left( \left\| \frac{1}{t} L_t^D - g^2 \right\|_{1,D} \le r - 4 \frac{t-s}{s}, \tau < \infty \right).
\end{align*}
$$

Summing this inequality and inequality (3.23), and setting $k = t-s$, we obtain, for any $0 < k < t$,

$$
2 P_x \left( \left\| \frac{1}{t} L_t^D - g^2 \right\|_{1,D} \le r, \tau < \infty \right) \ge \\
\left( P_x(S_k = 0) + P_x(S_{k-1} = 0) \right) P \left( \left\| \frac{1}{t} L_t^D - g^2 \right\|_{1,D} \le r - 4 \frac{k}{t-k}, \tau < \infty \right).
$$

We finally make the change of variable $r' = r - 4 \frac{k}{t-k}$ and we obtain the desired inequality. $\square$

# 4. A priori estimates

## 4.1. Control of the range

We shall obtain a control on the size of $|R_N|$. Let $c > 0$. We write

$$ \tilde{P}_N(|R_N| > cn^d) \le \frac{\exp(-cn^d)}{E(\exp(-|R_N|))}. $$

From [DV79, Theorem 1], there exists a positive constant $k(1, d)$ such that

$$ \lim_{N \to \infty} \frac{1}{n^d} \ln E(\exp(-|R_N|)) = -k(1, d). $$
time $t-s$, we apply the strong Markov property and we use twice the inequal-
ity (3.22) to get:

$$
\begin{align*}
(3.23) \quad P_x\left(\left\|\frac{1}{t}L_t^D - g^2\right\|_{1,D} \le r, \tau < \infty\right) & \\
&\ge \sum_{y \in \mathbb{Z}^d} P_y\left(S_{t-s} = y, \left\|\frac{1}{s}(L_t^D - L_s^D) - g^2\right\|_{1,D} \le r - 2\frac{t-s}{s}, \tau < \infty\right) \\
&\ge \sum_{y \in \mathbb{Z}^d} P_x(S_{t-s} = y) P_y\left(\left\|\frac{1}{s}L_s^D - g^2\right\|_{1,D} \le r - 2\frac{t-s}{s}, \tau < \infty\right) \\
&\ge P_x(S_{t-s} = 0) P\left(\left\|\frac{1}{t}L_t^D - g^2\right\|_{1,D} \le r - 4\frac{t-s}{s}, \tau < \infty\right). \notag
\end{align*}
$$

It might happen that $P_x(S_{t-s} = 0)$ vanishes if $|x|_1$ and $t-s$ don't have the same parity. To avoid this nasty detail, we apply the inequality with $s+1$ instead of $s$. Noting that

$$
\frac{t-s-1}{s+1} \le \frac{t-s}{s},
$$

we get

$$
\begin{align*}
P_x \left( \left\| \frac{1}{t} L_t^D - g^2 \right\|_{1,D} \le r, \tau < \infty \right) & \\
&\ge P_x(S_{t-s-1} = 0) P \left( \left\| \frac{1}{t} L_t^D - g^2 \right\|_{1,D} \le r - 4 \frac{t-s}{s}, \tau < \infty \right). \tag*{\text{a}}
\end{align*}
$$

Summing this inequality and inequality (3.23), and setting $k = t - s$, we obtain, for
any $0 < k < t$,

$$
2 P_x \left( \left\| \frac{1}{t} L_t^D - g^2 \right\|_{1,D} \le r, \tau < \infty \right) \ge \\
\left( P_x(S_k = 0) + P_x(S_{k-1} = 0) \right) P \left( \left\| \frac{1}{t} L_t^D - g^2 \right\|_{1,D} \le r - 4 \frac{k}{t-k}, \tau < \infty \right).
$$

We finally make the change of variable $r' = r - 4 \frac{k}{t-k}$ and we obtain the desired inequality. $\square$

4. A priori estimates

4.1. Control of the range

We shall obtain a control on the size of $|R_N|$. Let $c > 0$. We write

$$
\tilde{P}_N(|R_N| > cn^d) \le \frac{\exp(-cn^d)}{E(\exp(-|R_N|))}.
$$

From [DV79, Theorem 1], there exists a positive constant $k(1, d)$ such that

$$
\lim_{N \to \infty} \frac{1}{n^d} \ln E \left( \exp \left( - |R_N| \right) \right) = -k(1, d).
$$
We conclude that, for any $c > 0$ and for $N$ large enough, we have

$$ (4.1) \qquad \tilde{P}_N(|R_N| > cn^d) \le \exp(-(c-2k(1,d))n^d). $$

## 4.2. Control of the Dirichlet energy

We shall obtain a bound on $\mathcal{E}(f_N)$ conditionally on the size of $|R_N|$.

**PROPOSITION 4.1.** — Let $c \ge 1$ and $\kappa \ge 1$ be such that $\kappa/2 - 4dc > 0$. For $n$ large enough, we have

$$ P(\mathcal{E}(f_N) \ge \kappa n^d \ln n, |R_N| \le cn^d) \le \exp\left(-\left(\frac{\kappa}{2} - 4dc\right)n^d \ln n\right). $$

*Proof.* — Let $\lambda, c > 0$. We write

$$ P(\mathcal{E}(f_N) \ge \lambda n^d, |R_N| \le cn^d) = \sum_{\phi} P(f_N = \phi), $$

where the summation extends over the profiles $\phi: \mathbb{Z}^d \to [0, +\infty[$ such that

$$ \phi(0) \ge 1, \quad \sum_{y \in \mathbb{Z}^d} \phi(y)^2 = N, \quad |\text{supp } \phi| \le cn^d, \quad \mathcal{E}(\phi) \ge \lambda n^d. $$

For such a profile $\phi$, we have, thanks to the inequality of Proposition 3.2:

$$ P(f_N = \phi) \le \frac{N}{\alpha} \exp \left( -\frac{\lambda}{2} n^d + \alpha \sqrt{Ncn^d} \right). $$

For the probability $P(f_N = \phi)$ to be positive, it is necessary that $\text{supp } \phi$ is a connected subset of $\mathbb{Z}^d$ containing the origin, and that $1 \le \phi(y)^2 \le N$ for all $y \in \text{supp } \phi$. The number of possible choices for the support of $\phi$ is bounded by $(c_d)^{cn^d}$, where $c_d$ is a constant depending on the dimension $d$ only. Once the support is fixed, the number of choices for the profile $\phi$ is bounded by $N^{cn^d}$. In the end, the total number of profiles $\phi$ satisfying the previous constraints is bounded by $(c_d N)^{cn^d}$. Therefore

$$ P(\mathcal{E}(f_N) \ge \lambda n^d, |R_N| \le cn^d) \le (c_d N)^{cn^d} \frac{N}{\alpha} \exp \left( -\frac{\lambda}{2} n^d + \alpha \sqrt{Ncn^d} \right). $$

We choose $\alpha$ and $\lambda$ of the form

$$ \alpha = \frac{\ln n}{n}, \quad \lambda = \kappa \ln n. $$

Recalling that $n^{d+2} = N$, the previous inequality can be rewritten as

$$ \begin{aligned} P(\mathcal{E}(f_N) \ge \kappa n^d \ln n, |R_N| \le cn^d) & \\ & \le \frac{n^{d+3}}{\ln n} \exp \left( cn^d \left( \ln c_d + (d+2) \ln n \right) - \frac{\kappa}{2} n^d \ln n + \sqrt{cn^d} \ln n \right) \\ & \le \exp \left( - \left( \frac{\kappa}{2} - 4dc \right) n^d \ln n \right), \end{aligned} $$

where the last inequality holds for $n$ large enough. $\square$

<figure><img src="image_3.png" /></figure>
We conclude that, for any $c > 0$ and for $N$ large enough, we have

$$ (4.1) \qquad \tilde{P}_N(|R_N| > cn^d) \le \exp(-(c-2k(1,d))n^d). $$

## 4.2. Control of the Dirichlet energy

We shall obtain a bound on $\mathcal{E}(f_N)$ conditionally on the size of $|R_N|$.

**PROPOSITION 4.1.** — Let $c \ge 1$ and $\kappa \ge 1$ be such that $\kappa/2 - 4dc > 0$. For $n$ large enough, we have

$$ P(\mathcal{E}(f_N) \ge \kappa n^d \ln n, |R_N| \le cn^d) \le \exp\left(-\left(\frac{\kappa}{2} - 4dc\right)n^d \ln n\right). $$

*Proof.* — Let $\lambda, c > 0$. We write

$$ P(\mathcal{E}(f_N) \ge \lambda n^d, |R_N| \le cn^d) = \sum_{\phi} P(f_N = \phi), $$

where the summation extends over the profiles $\phi: \mathbb{Z}^d \to [0, +\infty[$ such that

$$ \phi(0) \ge 1, \quad \sum_{y \in \mathbb{Z}^d} \phi(y)^2 = N, \quad |\text{supp } \phi| \le cn^d, \quad \mathcal{E}(\phi) \ge \lambda n^d. $$

For such a profile $\phi$, we have, thanks to the inequality of Proposition 3.2:

$$ P(f_N = \phi) \le \frac{N}{\alpha} \exp \left( -\frac{\lambda}{2} n^d + \alpha \sqrt{Ncn^d} \right). $$

For the probability $P(f_N = \phi)$ to be positive, it is necessary that $\text{supp } \phi$ is a connected subset of $\mathbb{Z}^d$ containing the origin, and that $1 \le \phi(y)^2 \le N$ for all $y \in \text{supp } \phi$. The number of possible choices for the support of $\phi$ is bounded by $(c_d)^{cn^d}$, where $c_d$ is a constant depending on the dimension $d$ only. Once the support is fixed, the number of choices for the profile $\phi$ is bounded by $N^{cn^d}$. In the end, the total number of profiles $\phi$ satisfying the previous constraints is bounded by $(c_d N)^{cn^d}$. Therefore

$$ P(\mathcal{E}(f_N) \ge \lambda n^d, |R_N| \le cn^d) \le (c_d N)^{cn^d} \frac{N}{\alpha} \exp \left( -\frac{\lambda}{2} n^d + \alpha \sqrt{Ncn^d} \right). $$

We choose $\alpha$ and $\lambda$ of the form

$$ \alpha = \frac{\ln n}{n}, \quad \lambda = \kappa \ln n. $$

Recalling that $n^{d+2} = N$, the previous inequality can be rewritten as

$$ \begin{aligned} P(\mathcal{E}(f_N) \ge \kappa n^d \ln n, |R_N| \le cn^d) & \le \frac{n^{d+3}}{\ln n} \exp \left( cn^d \left( \ln c_d + (d+2) \ln n \right) - \frac{\kappa}{2} n^d \ln n + \sqrt{cn^d} \ln n \right) \\ & \le \exp \left( - \left( \frac{\kappa}{2} - 4dc \right) n^d \ln n \right), \end{aligned} $$

where the last inequality holds for $n$ large enough. $\square$

<figure><img src="image_5.png" /></figure>
### 4.3. High density blocks

We divide $\mathbb{Z}^d$ into boxes called blocks in the following way. The box of side length $r > 0$ centered at the origin is the set

$$ \Lambda(r) = \{ (x_1, \dots, x_d) \in \mathbb{R}^d : \forall i \in \{1, \dots, d\} \text{ } -r/2 < x_i \le r/2 \}. $$

Let $n$ be a positive integer. For $\underline{x} \in \mathbb{Z}^d$, we define the block indexed by $\underline{x}$ as

$$ B(\underline{x}) = n\underline{x} + \Lambda(n). $$

Note that the blocks partition $\mathbb{R}^d$. We perform here a deterministic construction on any function $f: \mathbb{Z}^d \to \mathbb{R}^+$ in order to record the blocks where the function $f$ has a high density. This construction will be applied to build the coarse grained profile of the function $f_N$. Let $f$ be a function from $\mathbb{Z}^d$ to $\mathbb{R}^+$. Let $n \ge 1$, $\delta > 0$. We recall the notation $2^* = 2d/(d-2)$ and we define

$$ \underline{X}(f, \delta) = \left\{ \underline{x} \in \mathbb{Z}^d : \sum_{y \in B(\underline{x})} (f(y))^{2^*} \ge \delta^{2^*} n^{d+2^*} \right\}. $$

The exponent $d+2^*$ corresponds to the typical situation for a block actively visited by the random walk until time $N$: the number of visits per site should be of order $n^2$, so $f_N$ is of order $n$ throughout the block. The blocks corresponding to vertices outside of $\underline{X}(f, \delta)$ are low density blocks. Our goal is to control the total contribution of these blocks to the $2^*$-norm of $f$.

**LEMMA 4.2.** — There exists a constant $c_d$ depending on the dimension $d$ only such that, for any function $f$ from $\mathbb{Z}^d$ to $\mathbb{R}^+$, we have

$$ \sum_{\underline{x} \in \mathbb{Z}^d \setminus \underline{X}(f, \delta)} \sum_{y \in B(\underline{x})} (f(y))^{2^*} \le c_d (\delta^{2^*} n^{d+2^*})^{1-2/2^*} \left( \frac{1}{n^2} (\|f\|_2)^2 + \mathcal{E}(f) \right). $$

*Proof.* — Let $f$ be a function from $\mathbb{Z}^d$ to $\mathbb{R}^+$. Let $\underline{x} \in \mathbb{Z}^d$. We write

$$ (4.2) \qquad \sum_{y \in B(\underline{x})} (f(y))^{2^*} = \left( \sum_{y \in B(\underline{x})} (f(y))^{2^*} \right)^{1-2/2^*} \left( \sum_{y \in B(\underline{x})} (f(y))^{2^*} \right)^{2/2^*}. $$

To control the last factor, we apply the discrete Poincaré–Sobolev inequality stated in Corollary C.11:

$$ (4.3) \qquad \left( \sum_{y \in B(\underline{x})} (f(y))^{2^*} \right)^{2/2^*} \le (c_{PS})^2 \left( \frac{1}{n} \|f\|_{2, B(\underline{x})} + \sqrt{\mathcal{E}(f, B(\underline{x}))} \right)^2 \\ \le 2(c_{PS})^2 \left( \frac{1}{n^2} (\|f\|_{2, B(\underline{x})})^2 + \mathcal{E}(f, B(\underline{x})) \right). $$

If $\underline{x}$ does not belong to $\underline{X}(f, \delta)$, then we have

$$ (4.4) \qquad \sum_{y \in B(\underline{x})} (f(y))^{2^*} < \delta^{2^*} n^{d+2^*}. $$
### 4.3. High density blocks

We divide $\mathbb{Z}^d$ into boxes called blocks in the following way. The box of side length $r > 0$ centered at the origin is the set

$$ \Lambda(r) = \{ (x_1, \dots, x_d) \in \mathbb{R}^d : \forall i \in \{1, \dots, d\} \text{ } -r/2 < x_i \le r/2 \}. $$

Let $n$ be a positive integer. For $\underline{x} \in \mathbb{Z}^d$, we define the block indexed by $\underline{x}$ as

$$ B(\underline{x}) = n\underline{x} + \Lambda(n). $$

Note that the blocks partition $\mathbb{R}^d$. We perform here a deterministic construction on any function $f: \mathbb{Z}^d \to \mathbb{R}^+$ in order to record the blocks where the function $f$ has a high density. This construction will be applied to build the coarse grained profile of the function $f_N$. Let $f$ be a function from $\mathbb{Z}^d$ to $\mathbb{R}^+$. Let $n \ge 1$, $\delta > 0$. We recall the notation $2^* = 2d/(d-2)$ and we define

$$ \underline{X}(f, \delta) = \left\{ \underline{x} \in \mathbb{Z}^d : \sum_{y \in B(\underline{x})} (f(y))^{2^*} \ge \delta^{2^*} n^{d+2^*} \right\}. $$

The exponent $d+2^*$ corresponds to the typical situation for a block actively visited by the random walk until time $N$: the number of visits per site should be of order $n^2$, so $f_N$ is of order $n$ throughout the block. The blocks corresponding to vertices outside of $\underline{X}(f, \delta)$ are low density blocks. Our goal is to control the total contribution of these blocks to the $2^*$-norm of $f$.

**LEMMA 4.2.** — There exists a constant $c_d$ depending on the dimension $d$ only such that, for any function $f$ from $\mathbb{Z}^d$ to $\mathbb{R}^+$, we have

$$ \sum_{\underline{x} \in \mathbb{Z}^d \setminus \underline{X}(f, \delta)} \sum_{y \in B(\underline{x})} (f(y))^{2^*} \le c_d (\delta^{2^*} n^{d+2^*})^{1-2/2^*} \left( \frac{1}{n^2} (\|f\|_2)^2 + \mathcal{E}(f) \right). $$

*Proof.* — Let $f$ be a function from $\mathbb{Z}^d$ to $\mathbb{R}^+$. Let $\underline{x} \in \mathbb{Z}^d$. We write

$$ (4.2) \qquad \sum_{y \in B(\underline{x})} (f(y))^{2^*} = \left( \sum_{y \in B(\underline{x})} (f(y))^{2^*} \right)^{1-2/2^*} \left( \sum_{y \in B(\underline{x})} (f(y))^{2^*} \right)^{2/2^*}. $$

To control the last factor, we apply the discrete Poincaré–Sobolev inequality stated in Corollary C.11:

$$ (4.3) \qquad \left( \sum_{y \in B(\underline{x})} (f(y))^{2^*} \right)^{2/2^*} \le (c_{PS})^2 \left( \frac{1}{n} \|f\|_{2, B(\underline{x})} + \sqrt{\mathcal{E}(f, B(\underline{x}))} \right)^2 \\ \le 2(c_{PS})^2 \left( \frac{1}{n^2} (\|f\|_{2, B(\underline{x})})^2 + \mathcal{E}(f, B(\underline{x})) \right). $$

If $\underline{x}$ does not belong to $\underline{X}(f, \delta)$, then we have

$$ (4.4) \qquad \sum_{y \in B(\underline{x})} (f(y))^{2^*} < \delta^{2^*} n^{d+2^*}. $$
Plugging inequalities (4.3) and (4.4) into (4.2), we obtain

$$ \sum_{y \in B(\underline{x})} (f(y))^{2*} \leq (\delta^{2*} n^{d+2*})^{1-2/2*} 2(c_{PS})^2 \left( \frac{1}{n^2} (\|f\|_{2, B(\underline{x})})^2 + \mathcal{E}(f, B(\underline{x})) \right). $$

Summing this inequality over the blocks outside of $\underline{X}(f, \delta)$, we get the estimate stated in the lemma. □

## 4.4. Local averaging

In order to build a coarse grained image of the local time, we shall perform a local averaging. The averaging operation is deterministic, so we define it here for any function $f: \mathbb{Z}^d \to \mathbb{R}$. Let $M$ be an integer which is a divisor of $n$. Let $f$ be a function from $\mathbb{Z}^d$ to $\mathbb{R}$. To $f$ we associate a function $\overline{f}^M$ obtained by performing a local average of $f$ over boxes of side length $M$. Let us define the function $\overline{f}^M$ precisely. For $\underline{x} \in \mathbb{Z}^d$, we define the block indexed by $\underline{x}$ of side $M$ as

$$ B'(\underline{x}) = M\underline{x} + \Lambda(M). $$

We define a function $\overline{f}^M$ from $\mathbb{Z}^d$ to $\mathbb{R}$ which is constant on the blocks $B'(\underline{x})$, $\underline{x} \in \mathbb{Z}^d$, by setting

$$ \forall \underline{x} \in \mathbb{Z}^d \quad \forall y \in B'(\underline{x}) \quad \overline{f}^M(y) = \frac{1}{|B'(\underline{x})|} \sum_{z \in B'(\underline{x})} f(z). $$

We have

$$ (4.5) \quad \begin{aligned} \|\overline{f}^M\|_2^2 &= \sum_{x \in \mathbb{Z}^d} (\overline{f}^M(x))^2 \\ &= \sum_{\underline{x} \in \mathbb{Z}^d} |B'(\underline{x})| \left( \frac{1}{|B'(\underline{x})|} \sum_{z \in B'(\underline{x})} f(z) \right)^2 \le \sum_{\underline{x} \in \mathbb{Z}^d} \sum_{z \in B'(\underline{x})} (f(z))^2 = \|f\|_2^2. \end{aligned} $$

We shall next bound the $\ell^2$ norm of the difference between $f$ and $\overline{f}^M$. Let $\underline{x} \in \mathbb{Z}^d$. We apply the discrete Poincaré-Wirtinger inequality stated in Corollary C.12 to the function $f$ and the block $B'(\underline{x})$:

$$ (\|f - \overline{f}^M\|_{2, B'(\underline{x})})^2 \le (M c_{PW})^2 \mathcal{E}(f, B'(\underline{x})). $$

We sum over $\underline{x} \in \mathbb{Z}^d$:

$$ (\|f - \overline{f}^M\|_2)^2 \le (M c_{PW})^2 \sum_{\underline{x} \in \mathbb{Z}^d} \mathcal{E}(f, B'(\underline{x})) \le (M c_{PW})^2 \mathcal{E}(f). $$

Taking the square root, we conclude that

$$ (4.6) \qquad \|f - \overline{f}^M\|_2 \le M c_{PW} \sqrt{\mathcal{E}(f)}. $$
Plugging inequalities (4.3) and (4.4) into (4.2), we obtain

$$ \sum_{y \in B(\underline{x})} (f(y))^{2*} \leq (\delta^{2*} n^{d+2*})^{1-2/2*} 2(c_{PS})^2 \left( \frac{1}{n^2} (\|f\|_{2, B(\underline{x})})^2 + \mathcal{E}(f, B(\underline{x})) \right). $$

Summing this inequality over the blocks outside of $\underline{X}(f, \delta)$, we get the estimate stated in the lemma. □

## 4.4. Local averaging

In order to build a coarse grained image of the local time, we shall perform a local averaging. The averaging operation is deterministic, so we define it here for any function $f: \mathbb{Z}^d \to \mathbb{R}$. Let $M$ be an integer which is a divisor of $n$. Let $f$ be a function from $\mathbb{Z}^d$ to $\mathbb{R}$. To $f$ we associate a function $\overline{f}^M$ obtained by performing a local average of $f$ over boxes of side length $M$. Let us define the function $\overline{f}^M$ precisely. For $\underline{x} \in \mathbb{Z}^d$, we define the block indexed by $\underline{x}$ of side $M$ as

$$ B'(\underline{x}) = M\underline{x} + \Lambda(M). $$

We define a function $\overline{f}^M$ from $\mathbb{Z}^d$ to $\mathbb{R}$ which is constant on the blocks $B'(\underline{x})$, $\underline{x} \in \mathbb{Z}^d$, by setting

$$ \forall \underline{x} \in \mathbb{Z}^d \quad \forall y \in B'(\underline{x}) \quad \overline{f}^M(y) = \frac{1}{|B'(\underline{x})|} \sum_{z \in B'(\underline{x})} f(z). $$

We have

$$ (4.5) \quad \begin{aligned} \|\overline{f}^M\|_2^2 &= \sum_{x \in \mathbb{Z}^d} (\overline{f}^M(x))^2 \\ &= \sum_{\underline{x} \in \mathbb{Z}^d} |B'(\underline{x})| \left( \frac{1}{|B'(\underline{x})|} \sum_{z \in B'(\underline{x})} f(z) \right)^2 \le \sum_{\underline{x} \in \mathbb{Z}^d} \sum_{z \in B'(\underline{x})} (f(z))^2 = \|f\|_2^2. \end{aligned} $$

We shall next bound the $\ell^2$ norm of the difference between $f$ and $\overline{f}^M$. Let $\underline{x} \in \mathbb{Z}^d$. We apply the discrete Poincaré-Wirtinger inequality stated in Corollary C.12 to the function $f$ and the block $B'(\underline{x})$:

$$ (\|f - \overline{f}^M\|_{2, B'(\underline{x})})^2 \le (M c_{PW})^2 \mathcal{E}(f, B'(\underline{x})). $$

We sum over $\underline{x} \in \mathbb{Z}^d$:

$$ (\|f - \overline{f}^M\|_2^2) \le (M c_{PW})^2 \sum_{\underline{x} \in \mathbb{Z}^d} \mathcal{E}(f, B'(\underline{x})) \le (M c_{PW})^2 \mathcal{E}(f). $$

Taking the square root, we conclude that

$$ (4.6) \qquad \|f - \overline{f}^M\|_2 \le M c_{PW} \sqrt{\mathcal{E}(f)}. $$
5. Upper bound: proof of Theorem 2.2

We start here the proof of Theorem 2.2. Let $c \ge 1$ and $\kappa \ge 1$. We consider the event

$$ \mathcal{A} = \{ \mathcal{E}(f_N) \le \kappa n^d \ln n, |R_N| \le cn^d \}. $$

Let $\mathcal{F}$ be a collection of functions from $\mathbb{Z}^d$ to $\mathbb{R}^+$. The estimate on the range (4.1) and Proposition 4.1 yield that, for $n$ large enough,

$$ (5.1) \quad E(e^{-|R_N|}; f_N \in \mathcal{F}) \le E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}) \\ \qquad + \exp\left(-\left(c - 2k(1, d)\right)n^d\right) + \exp\left(-\left(\frac{\kappa}{2} - 4dc\right)n^d \ln n\right). $$

From now onwards, we focus on estimating the term $E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A})$. So we suppose that the event $\mathcal{A}$ occurs and we deal only with trajectories of the random walk belonging to $\mathcal{A}$. Applying Corollary C.13, we have

$$ (5.2) \quad \|f_N\|_{2^*} \le c_{PS} \sqrt{2d\mathcal{E}(f_N)} \le c_{PS} \sqrt{2d\kappa n^d \ln n}. $$

We apply next the deterministic construction of Section 4.3 to the function $f_N$. The corresponding set $\underline{X}(f_N, \delta)$ satisfies:

$$ (5.3) \quad |\underline{X}(f_N, \delta)| \delta^{2^*} n^{d+2^*} \le (\|f_N\|_{2^*})^{2^*}. $$

Therefore, combining inequalities (5.2) and (5.3),

$$ (5.4) \quad |\underline{X}(f_N, \delta)| \le \frac{1}{\delta^{2^*} n^{d+2^*}} \left(c_{PS} \sqrt{2d\kappa n^d \ln n}\right)^{2^*} \le \frac{1}{\delta^{2^*}} (c_{PS})^{2^*} (2d\kappa \ln n)^{2^*/2}. $$

In addition, since the range $R_N$ is connected and has cardinality at most $cn^d$, then certainly the set $\underline{X}(f_N, \delta)$ is included in the box $\Lambda(3cn^{d-1})$; otherwise, the range $R_N$ would contain a vertex which is outside the box $\Lambda(3cn^d)$ (when coming back to the original lattice, the scale is multiplied by $n$), and a connected set containing 0 which exits the box $\Lambda(3cn^d)$ must contain a path of length at least $3cn^d/2$. We denote by $\mathcal{X}(N, \delta)$ the collection of the subsets $X$ of $\mathbb{Z}^d$ satisfying these constraints. There exists a constant $c_d$ depending on the dimension $d$ only such that, for $n$ large enough,

$$ (5.5) \quad |\mathcal{X}(N, \delta)| \le \exp(c_d C_0), $$

where

$$ (5.6) \quad C_0 = \frac{1}{\delta^{2^*}} \kappa^4 (\ln n)^5. $$

We decompose the expectation according to the value $X$ of $\underline{X}$ in $\mathcal{X}(N, \delta)$:

$$ (5.7) \quad E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}) = \sum_{X \in \mathcal{X}(N, \delta)} E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X). $$

We fix next $X \in \mathcal{X}(N, \delta)$ and we shall estimate the probability appearing in the sum. We perform the local averaging on $f_N$, thereby getting the function $\overline{f}_N^M$. Using inequality (4.6), we have

$$ (5.8) \quad \|f_N - \overline{f}_N^M\|_2 \le M c_{PW} \sqrt{\mathcal{E}(f_N)} \le M c_{PW} \sqrt{\kappa n^d \ln n}. $$
5. Upper bound: proof of Theorem 2.2

We start here the proof of Theorem 2.2. Let $c \ge 1$ and $\kappa \ge 1$. We consider the event

$$ \mathcal{A} = \{ \mathcal{E}(f_N) \le \kappa n^d \ln n, |R_N| \le cn^d \}. $$

Let $\mathcal{F}$ be a collection of functions from $\mathbb{Z}^d$ to $\mathbb{R}^+$. The estimate on the range (4.1) and Proposition 4.1 yield that, for $n$ large enough,

$$ (5.1) \quad E(e^{-|R_N|}; f_N \in \mathcal{F}) \le E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}) \\ \qquad + \exp\left(-\left(c - 2k(1, d)\right)n^d\right) + \exp\left(-\left(\frac{\kappa}{2} - 4dc\right)n^d \ln n\right). $$

From now onwards, we focus on estimating the term $E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A})$. So we suppose that the event $\mathcal{A}$ occurs and we deal only with trajectories of the random walk belonging to $\mathcal{A}$. Applying Corollary C.13, we have

$$ (5.2) \quad \|f_N\|_{2^*} \le c_{PS} \sqrt{2d\mathcal{E}(f_N)} \le c_{PS} \sqrt{2d\kappa n^d \ln n}. $$

We apply next the deterministic construction of Section 4.3 to the function $f_N$. The corresponding set $\underline{X}(f_N, \delta)$ satisfies:

$$ (5.3) \quad |\underline{X}(f_N, \delta)| \delta^{2^*} n^{d+2^*} \le (\|f_N\|_{2^*})^{2^*}. $$

Therefore, combining inequalities (5.2) and (5.3),

$$ (5.4) \quad |\underline{X}(f_N, \delta)| \le \frac{1}{\delta^{2^*} n^{d+2^*}} \left( c_{PS} \sqrt{2d\kappa n^d \ln n} \right)^{2^*} \le \frac{1}{\delta^{2^*}} (c_{PS})^{2^*} (2d\kappa \ln n)^{2^*/2}. $$

In addition, since the range $R_N$ is connected and has cardinality at most $cn^d$, then certainly the set $\underline{X}(f_N, \delta)$ is included in the box $\Lambda(3cn^{d-1})$; otherwise, the range $R_N$ would contain a vertex which is outside the box $\Lambda(3cn^d)$ (when coming back to the original lattice, the scale is multiplied by $n$), and a connected set containing 0 which exits the box $\Lambda(3cn^d)$ must contain a path of length at least $3cn^d/2$. We denote by $\mathcal{X}(N, \delta)$ the collection of the subsets $X$ of $\mathbb{Z}^d$ satisfying these constraints. There exists a constant $c_d$ depending on the dimension $d$ only such that, for $n$ large enough,

$$ (5.5) \quad |\mathcal{X}(N, \delta)| \le \exp(c_d C_0), $$

where

$$ (5.6) \quad C_0 = \frac{1}{\delta^{2^*}} \kappa^4 (\ln n)^5. $$

We decompose the expectation according to the value $X$ of $\underline{X}$ in $\mathcal{X}(N, \delta)$:

$$ (5.7) \quad E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}) = \sum_{X \in \mathcal{X}(N, \delta)} E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X). $$

We fix next $X \in \mathcal{X}(N, \delta)$ and we shall estimate the probability appearing in the sum. We perform the local averaging on $f_N$, thereby getting the function $\overline{f}_N^M$. Using inequality (4.6), we have

$$ (5.8) \quad \|f_N - \overline{f}_N^M\|_2 \le M c_{PW} \sqrt{\mathcal{E}(f_N)} \le M c_{PW} \sqrt{\kappa n^d \ln n}. $$
## 5.1. The coarse grained profile

We build here the coarse grained image of the local time. Since $M$ is a divisor of $n$, then each block $B(\underline{x})$, for $\underline{x} \in \mathbb{Z}^d$, is the disjoint union of the blocks $B'(\underline{y})$, $\underline{y} \in \mathbb{Z}^d$, which are included in it. Let us make this statement more precise. For $\underline{x} \in \mathbb{Z}^d$, we denote by $Y(\underline{x})$ the subset of $\mathbb{Z}^d$ defined by:

$$Y(\underline{x}) = \{ \underline{y} \in \mathbb{Z}^d : B'(\underline{y}) \subset B(\underline{x}) \}.$$

With this definition, we have

$$\forall \underline{x} \in \mathbb{Z}^d \quad B(\underline{x}) = \bigcup_{\underline{y} \in Y(\underline{x})} B'(\underline{y}).$$

We recall that the norm $|\cdot|_{\infty}$ is defined by

$$\forall (x_1, \dots, x_d) \in \mathbb{R}^d \quad |(x_1, \dots, x_d)|_{\infty} = \max_{1 \le i \le d} |x_i|.$$

For $X$ a subset of $\mathbb{Z}^d$, we define

$$\widehat{X} = X \cup \{x \in \mathbb{Z}^d \setminus X \exists y \in X \ |x - y|_{\infty} = 1\}.$$

We have the simple bound

$$(5.9) \qquad |\widehat{X}| \le 3^d |X|.$$

We define also

$$Y(X) = \bigcup_{\underline{x} \in X} Y(\underline{x}).$$

Since the blocks $B'(\underline{x})$, $\underline{x} \in \mathbb{Z}^d$, are pairwise disjoint, we have

$$|Y(\widehat{X})| \times |\Lambda(M) \cap \mathbb{Z}^d| \le |\widehat{X}| \times |\Lambda(n) \cap \mathbb{Z}^d|,$$

whence, using inequality (5.9),

$$(5.10) \qquad |Y(\widehat{X})| \le \frac{n^d}{M^d} |\widehat{X}| \le \frac{3^d n^d}{M^d} |X|.$$

We take now $X = \underline{X}(f_N, \delta)$. The function $\overline{f_N}^M$ is constant on each block $B'(\underline{y})$, $\underline{y} \in Y(\widehat{X})$, and

$$\forall x \in \mathbb{Z}^d \quad 0 \le \overline{f_N}^M(x) \le \sup_{\underline{y} \in \mathbb{Z}^d} f_N(\underline{y}) \le \sqrt{N}.$$

We shall work in the domain

$$(5.11) \qquad D = \bigcup_{\underline{x} \in \widehat{X}} B(\underline{x}) = \bigcup_{\underline{y} \in Y(\widehat{X})} B'(\underline{y}).$$

We define also the set

$$(5.12) \qquad E = \bigcup_{\underline{x} \in X} B(\underline{x}).$$

We apply Lemma 4.2 to $f_N$. Recalling that

$$(\|f_N\|_2)^2 = N = n^{d+2}, \quad \mathcal{E}(f_N) \le \kappa n^d \ln n,$$
## 5.1. The coarse grained profile

We build here the coarse grained image of the local time. Since $M$ is a divisor of $n$, then each block $B(\underline{x})$, for $\underline{x} \in \mathbb{Z}^d$, is the disjoint union of the blocks $B'(\underline{y})$, $\underline{y} \in \mathbb{Z}^d$, which are included in it. Let us make this statement more precise. For $\underline{x} \in \mathbb{Z}^d$, we denote by $Y(\underline{x})$ the subset of $\mathbb{Z}^d$ defined by:

$$Y(\underline{x}) = \{ \underline{y} \in \mathbb{Z}^d : B'(\underline{y}) \subset B(\underline{x}) \}.$$

With this definition, we have

$$\forall \underline{x} \in \mathbb{Z}^d \quad B(\underline{x}) = \bigcup_{\underline{y} \in Y(\underline{x})} B'(\underline{y}).$$

We recall that the norm $|\cdot|_{\infty}$ is defined by

$$\forall (x_1, \dots, x_d) \in \mathbb{R}^d \quad |(x_1, \dots, x_d)|_{\infty} = \max_{1 \le i \le d} |x_i|.$$

For $X$ a subset of $\mathbb{Z}^d$, we define

$$\widehat{X} = X \cup \{x \in \mathbb{Z}^d \setminus X \exists y \in X \ |x - y|_{\infty} = 1\}.$$

We have the simple bound

$$(5.9) \qquad |\widehat{X}| \le 3^d |X|.$$

We define also

$$Y(X) = \bigcup_{\underline{x} \in X} Y(\underline{x}).$$

Since the blocks $B'(\underline{x})$, $\underline{x} \in \mathbb{Z}^d$, are pairwise disjoint, we have

$$|Y(\widehat{X})| \times |\Lambda(M) \cap \mathbb{Z}^d| \le |\widehat{X}| \times |\Lambda(n) \cap \mathbb{Z}^d|,$$

whence, using inequality (5.9),

$$(5.10) \qquad |Y(\widehat{X})| \le \frac{n^d}{M^d} |\widehat{X}| \le \frac{3^d n^d}{M^d} |X|.$$

We take now $X = \underline{X}(f_N, \delta)$. The function $\overline{f_N}^M$ is constant on each block $B'(\underline{y})$, $\underline{y} \in Y(\widehat{X})$, and

$$\forall x \in \mathbb{Z}^d \quad 0 \le \overline{f_N}^M(x) \le \sup_{\underline{y} \in \mathbb{Z}^d} f_N(\underline{y}) \le \sqrt{N}.$$

We shall work in the domain

$$(5.11) \qquad D = \bigcup_{\underline{x} \in \widehat{X}} B(\underline{x}) = \bigcup_{\underline{y} \in Y(\widehat{X})} B'(\underline{y}).$$

We define also the set

$$(5.12) \qquad E = \bigcup_{\underline{x} \in X} B(\underline{x}).$$

We apply Lemma 4.2 to $f_N$. Recalling that

$$(\|f_N\|_2)^2 = N = n^{d+2}, \quad \mathcal{E}(f_N) \le \kappa n^d \ln n,$$
we obtain

$$ (5.13) \quad \sum_{x \in \mathbb{Z}^d \setminus E} (f_N(x))^{2*} \le c_d (\delta^{2*} n^{d+2*})^{1-2/2*} (n^d + \kappa n^d \ln n). $$

We discretize next the values of the functions $\overline{f_N}^M$. Let $\eta > 0$. We define the function $\eta \overline{f_N}^M$ by setting

$$ \forall x \in \mathbb{Z}^d \quad \eta \overline{f_N}^M(x) = \eta \left[ \frac{1}{\eta} \overline{f_N}^M(x) \right]. $$

The function $\eta \overline{f_N}^M$ restricted to $D$, denoted by $\eta \overline{f_N}^M|_D$, is the coarse-grained image of the function $f_N$. By construction, we have

$$ \forall x \in \mathbb{Z}^d \quad |\overline{f_N}^M(x) - \eta \overline{f_N}^M(x)| \le \eta, $$

whence, using inequalities (5.4) and (5.9) (recall that our $\ell^p$ norms are unscaled, see the definition in formula (2.4)),

$$ (5.14) \quad \begin{aligned} \left( \| \overline{f_N}^M - \eta \overline{f_N}^M \|_{2,D} \right)^2 &\le \eta^2 |\widehat{X}| n^d \\ &\le \eta^2 3^d \frac{1}{\delta^{2*}} (c_{PS})^{2*} (\kappa \ln n)^{2*/2} n^d. \end{aligned} $$

Putting together inequalities (5.8) and (5.14), we see that, on the event $\underline{X}(f_N, \delta) = X$, we have

$$ (5.15) \quad \| f_N - \eta \overline{f_N}^M \|_{2, D} < \Gamma_0, $$

where

$$ (5.16) \quad \Gamma_0 = M c_{PW} \sqrt{\kappa n^d \ln n} + \left( \eta^2 3^d \frac{1}{\delta^{2*}} (c_{PS})^{2*} (\kappa \ln n)^{2*/2} n^d \right)^{1/2}. $$

The function $\eta \overline{f_N}^M|_D$ belongs to the collection $\mathcal{G}$ of the functions which are constant on each block $B'(y), y \in Y(\widehat{X})$, and with values in the set

$$ \left\{ k\eta : k \in \mathbb{N}, 0 \le k < \frac{\sqrt{N}}{\eta} \right\}. $$

Using inequality (5.10), a simple upper bound on the cardinality of $\mathcal{G}$ is given by

$$ (5.17) \quad |\mathcal{G}| \le \left( \frac{\sqrt{N}}{\eta} \right)^{|Y(\widehat{X})|} \le \left( \frac{\sqrt{N}}{\eta} \right)^{\frac{3^d n^d}{M^d}} |X|. $$

Notice that the collection $\mathcal{G}$ depends on $f_N$ only through the set of blocks $\underline{X}(f_N, \delta)$. More precisely, once we know that $\underline{X}(f_N, \delta) = X$, then $\mathcal{G}$ depends only on $X$ and the parameters $M, \eta$, so we write $\mathcal{G} = \mathcal{G}(X, M, \eta)$. We come back to equation (5.7) and we decompose further the expectation as follows:

$$ (5.18) \quad \begin{aligned} & E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X) \\ &\le \sum_{g \in \mathcal{G}(X, M, \eta)} E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \eta \overline{f_N}^M|_D = g). \end{aligned} $$
we obtain

$$ (5.13) \qquad \sum_{x \in \mathbb{Z}^d \setminus E} (f_N(x))^{2*} \le c_d (\delta^{2*} n^{d+2*})^{1-2/2*} (n^d + \kappa n^d \ln n). $$

We discretize next the values of the functions $\overline{f_N}^M$. Let $\eta > 0$. We define the function $\eta \overline{f_N}^M$ by setting

$$ \forall x \in \mathbb{Z}^d \quad \eta \overline{f_N}^M(x) = \eta \left[ \frac{1}{\eta} \overline{f_N}^M(x) \right]. $$

The function $\eta \overline{f_N}^M$ restricted to $D$, denoted by $\eta \overline{f_N}^M|_D$, is the coarse-grained image of the function $f_N$. By construction, we have

$$ \forall x \in \mathbb{Z}^d \quad |\overline{f_N}^M(x) - \eta \overline{f_N}^M(x)| \le \eta, $$

whence, using inequalities (5.4) and (5.9) (recall that our $\ell^p$ norms are unscaled, see the definition in formula (2.4)),

$$ (5.14) \qquad \begin{aligned} \left( \| \overline{f_N}^M - \eta \overline{f_N}^M \|_{2,D} \right)^2 &\le \eta^2 |\widehat{X}| n^d \\ &\le \eta^2 3^d \frac{1}{\delta^{2*}} (c_{PS})^{2*} (\kappa \ln n)^{2*/2} n^d. \end{aligned} $$

Putting together inequalities (5.8) and (5.14), we see that, on the event $\underline{X}(f_N, \delta) = X$, we have

$$ (5.15) \qquad \|f_N - \eta \overline{f_N}^M\|_{2, D} < \Gamma_0, $$

where

$$ (5.16) \qquad \Gamma_0 = M c_{PW} \sqrt{\kappa n^d \ln n} + \left( \eta^2 3^d \frac{1}{\delta^{2*}} (c_{PS})^{2*} (\kappa \ln n)^{2*/2} n^d \right)^{1/2}. $$

The function $\eta \overline{f_N}^M|_D$ belongs to the collection $\mathcal{G}$ of the functions which are constant on each block $B'(y), y \in Y(\widehat{X})$, and with values in the set

$$ \left\{ k\eta : k \in \mathbb{N}, 0 \le k < \frac{\sqrt{N}}{\eta} \right\}. $$

Using inequality (5.10), a simple upper bound on the cardinality of $\mathcal{G}$ is given by

$$ (5.17) \qquad |\mathcal{G}| \le \left( \frac{\sqrt{N}}{\eta} \right)^{|Y(\widehat{X})|} \le \left( \frac{\sqrt{N}}{\eta} \right)^{\frac{3^d n^d}{M^d}} |X|. $$

Notice that the collection $\mathcal{G}$ depends on $f_N$ only through the set of blocks $\underline{X}(f_N, \delta)$. More precisely, once we know that $\underline{X}(f_N, \delta) = X$, then $\mathcal{G}$ depends only on $X$ and the parameters $M, \eta$, so we write $\mathcal{G} = \mathcal{G}(X, M, \eta)$. We come back to equation (5.7) and we decompose further the expectation as follows:

$$ (5.18) \qquad \begin{aligned} & E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X) \\ &\le \sum_{g \in \mathcal{G}(X, M, \eta)} E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \eta \overline{f_N}^M|_D = g). \end{aligned} $$
Our large deviations inequality will involve the local time $L_N$, so we try to estimate $\|L_N - g^2\|_{1,D}$ once we know that $\eta \overline{f_N}^M|_D = g$. Let $g \in \mathcal{G}(X, M, \eta)$. By the Cauchy-Schwarz inequality,

$$ \|L_N - g^2\|_{1, D} = \|f_N^2 - g^2\|_{1, D} \le \|f_N - g\|_{2, D} \|f_N + g\|_{2, D}. $$

Suppose that $\eta \overline{f_N}^M|_D = g$. Thanks to inequality (5.15), we have

$$ (5.19) \qquad \|g\|_{2,D} \le \|f_N\|_{2,D} + \|g - f_N\|_{2,D} \le \sqrt{N} + \Gamma_0. $$

Setting $\Gamma_1 = \Gamma_0(2\sqrt{N} + \Gamma_0)$, we deduce from the previous inequalities that

$$ (5.20) \qquad \|L_N - g^2\|_{1, D} \le \Gamma_1. $$

Inequality (5.18) and the above inequalities yield that

$$ (5.21) \qquad \begin{aligned} & E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X) \\ & \le \sum_{\substack{g \in \mathcal{G}(X, M, \eta) \\ \|g\|_{2,D} \le \sqrt{N} + \Gamma_0}} E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \|L_N - g^2\|_{1,D} < \Gamma_1). \end{aligned} $$

## 5.2. Continuation of proof of Theorem 2.2

We still fix $g \in \mathcal{G}(X, M, \eta)$. We come back to equation (5.21) and we estimate the expectation

$$ E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \|L_N - g^2\|_{1,D} < \Gamma_1). $$

We need first to bound from below $|R_N|$ when $L_N$ is close to $g^2$. Let $\lambda > 0$. If $x \in D$ is such that $g^2(x) \ge \lambda$ and $|L_N(x) - g^2(x)| < \lambda/2$, then certainly $L_N(x) > 0$. Therefore

$$ (5.22) \qquad \begin{aligned} |R_N| &\ge \left| \left\{ x \in D : g^2(x) \ge \lambda, |L_N(x) - g^2(x)| < \lambda/2 \right\} \right| \\ &\ge \left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| - \left| \left\{ x \in D : |L_N(x) - g^2(x)| \ge \lambda/2 \right\} \right|. \end{aligned} $$

Moreover, by Markov's inequality,

$$ \left| \left\{ x \in D : |L_N(x) - g^2(x)| \ge \lambda/2 \right\} \right| \le \frac{2}{\lambda} \|L_N - g^2\|_{1,D}. $$

We conclude that

$$ (5.23) \qquad \begin{aligned} & E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \|L_N - g^2\|_{1,D} < \Gamma_1) \\ & \le \exp \left( - \left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| + \frac{2\Gamma_1}{\lambda} \right) \times P(\mathcal{B}), \end{aligned} $$

where $\mathcal{B}$ is the event defined by

$$ (5.24) \qquad \mathcal{B} = \left\{ f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \|L_N - g^2\|_{1,D} < \Gamma_1 \right\}. $$
Our large deviations inequality will involve the local time $L_N$, so we try to estimate $\|L_N - g^2\|_{1, D}$ once we know that $\eta \overline{f_N}^M|_D = g$. Let $g \in \mathcal{G}(X, M, \eta)$. By the Cauchy–Schwarz inequality,

$$ \|L_N - g^2\|_{1, D} = \|f_N^2 - g^2\|_{1, D} \le \|f_N - g\|_{2, D} \|f_N + g\|_{2, D}. $$

Suppose that $\eta \overline{f_N}^M|_D = g$. Thanks to inequality (5.15), we have

$$ (5.19) \qquad \|g\|_{2, D} \le \|f_N\|_{2, D} + \|g - f_N\|_{2, D} \le \sqrt{N} + \Gamma_0. $$

Setting $\Gamma_1 = \Gamma_0(2\sqrt{N} + \Gamma_0)$, we deduce from the previous inequalities that

$$ (5.20) \qquad \|L_N - g^2\|_{1, D} \le \Gamma_1. $$

Inequality (5.18) and the above inequalities yield that

$$ (5.21) \qquad \begin{aligned} & E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X) \\ & \le \sum_{\substack{g \in \mathcal{G}(X, M, \eta) \\ \|g\|_{2, D} \le \sqrt{N} + \Gamma_0}} E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \|L_N - g^2\|_{1, D} < \Gamma_1). \end{aligned} $$

## 5.2. Continuation of proof of Theorem 2.2

We still fix $g \in \mathcal{G}(X, M, \eta)$. We come back to equation (5.21) and we estimate the expectation

$$ E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \|L_N - g^2\|_{1, D} < \Gamma_1). $$

We need first to bound from below $|R_N|$ when $L_N$ is close to $g^2$. Let $\lambda > 0$. If $x \in D$ is such that $g^2(x) \ge \lambda$ and $|L_N(x) - g^2(x)| < \lambda/2$, then certainly $L_N(x) > 0$. Therefore

$$ (5.22) \qquad \begin{aligned} |R_N| &\ge \left| \left\{ x \in D : g^2(x) \ge \lambda, \left|L_N(x) - g^2(x)\right| < \lambda/2 \right\} \right| \\ &\ge \left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| - \left| \left\{ x \in D : \left|L_N(x) - g^2(x)\right| \ge \lambda/2 \right\} \right|. \end{aligned} $$

Moreover, by Markov's inequality,

$$ \left| \left\{ x \in D : \left| L_N(x) - g^2(x) \right| \ge \lambda/2 \right\} \right| \le \frac{2}{\lambda} \|L_N - g^2\|_{1, D}. $$

We conclude that

$$ (5.23) \qquad \begin{aligned} & E(e^{-|R_N|}; f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \|L_N - g^2\|_{1, D} < \Gamma_1) \\ & \le \exp \left( - \left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| + \frac{2\Gamma_1}{\lambda} \right) \times P(\mathcal{B}), \end{aligned} $$

where $\mathcal{B}$ is the event defined by

$$ (5.24) \qquad \mathcal{B} = \left\{ f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \|L_N - g^2\|_{1, D} < \Gamma_1 \right\}. $$
It remains to estimate the probability $P(\mathcal{B})$, for which we ultimately wish to use
Theorem 1.4. Recall the set $E$ from (5.12). Then we have

$$
(5.25) \qquad \|L_N\|_{1,\mathrm{D}} \ge \|L_N\|_{1,E} = \|L_N\|_1 - \|L_N\|_{1,\mathbb{Z}^d\setminus E}.
$$

We estimate $\|L_N\|_{1,\mathbb{Z}^d\setminus E}$ in the next Lemma 5.1.

LEMMA 5.1. — For $n$ large enough, we have $\|L_N\|_{1,\mathbb{Z}^d\setminus E} \le \Gamma_2$ where

$$
\Gamma_2 = c \delta^{4/d} n^{d+2} (c_d \kappa \ln n)^{2/2*}.
$$

Proof. — We use Hölder’s inequality with the exponents 2*/2 and d/2 to write

$$
\begin{align*}
\|L_N\|_{1,\mathbb{Z}^d\setminus E} &\le \sum_{\underline{x} \in \mathbb{Z}^d \setminus X} \sum_{y \in B(\underline{x})} (f_N(y))^2 \\
&\le \left( \sum_{\underline{x} \in \mathbb{Z}^d \setminus X} \sum_{y \in B(\underline{x})} (f_N(y))^{2*} \right)^{2/2*} |\text{supp } f_N \setminus E|^{1-2/2*}.
\end{align*}
$$

Moreover, on the event $\mathcal{A}$, we have

$$
|\text{supp } f_N \setminus E| \le |\text{supp } f_N| \le cn^d.
$$

Using also inequality (5.13), we conclude that $\|L_N : \|_{1,\mathbb{Z}^d\setminus E} \le \Gamma_2$. $\square$

<figure><img src="image_4.png" /></figure>

It follows from inequality (5.25) and Lemma 5.1 that

$$
P(\mathcal{B}) = P(\mathcal{B}, \|L_N\|_{1,D} \ge N - \Gamma_2) = \sum_{N - \Gamma_2 \le t \le N} P(\mathcal{B}, \|L_N\|_{1,D} = t).
$$

Now, if $\|L_N\|_{1,\mathrm{D}} = t$, then $\tau(D,t) < \infty$ and $L_N(y) = L_t^D(y)$ for any $y \in \mathrm{D}$, thus

$$
\|L_N - g^2\|_{1,\mathrm{D}} = \|L_t^D - g^2\|_{1,\mathrm{D}},
$$

and we obtain the bound

$$
(5.26) \quad P(\mathcal{B}) \le \sum_{N-\Gamma_2 \le t \le N} P\left(f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \|L_t^D - g^2\|_{1,D} < \Gamma_1, \tau < \infty\right).
$$

Let us fix $t$ such that

$$
(5.27) \qquad N - \Gamma_2 \le t \le N.
$$

The time has now come to make specific choices for the parameters $\delta, M, \eta, \lambda$ intro-
duced in the course of the proof (recall that $\lambda$ was introduced in (5.22)). We suppose
that

$$
(5.28) \qquad \delta = \frac{1}{n^\alpha}, \quad M = n^\beta, \quad \eta = \frac{1}{n^\gamma}, \quad \lambda = n^\rho,
$$

where $\alpha, \beta, \gamma, \rho$ are positive exponents, which satisfy furthermore

$$
(5.29) \quad \beta < 1, \quad \frac{2^*}{2}\alpha - \gamma < \beta, \quad 2^*\alpha < d\beta, 1 + \beta < \rho, \quad 2 - 4\alpha/d < \rho, \quad \rho < 2.
$$

These conditions imply that, as $N$ or $n$ goes to $\infty$,

$$
(5.30) \quad \Gamma_0 \underset{n \to \infty}{\overset{\ln}{\sim}} n^{d/2+\beta}, \quad \Gamma_1 \underset{n \to \infty}{\overset{\ln}{\sim}} n^{d+1+\beta}, \quad \Gamma_2 \underset{n \to \infty}{\overset{\ln}{\sim}} n^{d+2-4\alpha/d},
$$
It remains to estimate the probability $P(\mathcal{B})$, for which we ultimately wish to use
Theorem 1.4. Recall the set $E$ from (5.12). Then we have

$$
(5.25) \qquad \|L_N\|_{1,\mathrm{D}} \ge \|L_N\|_{1,E} = \|L_N\|_1 - \|L_N\|_{1,\mathbb{Z}^d \setminus E}.
$$

We estimate $\|L_N\|_{1,\mathbb{Z}^d \setminus E}$ in the next Lemma 5.1.

LEMMA 5.1. — For $n$ large enough, we have $\|L_N\|_{1,\mathbb{Z}^d\setminus E} \le \Gamma_2$ where

$$
\Gamma_2 = c \delta^{4/d} n^{d+2} (c_d \kappa \ln n)^{2/2*}.
$$

*Proof*. — We use Hölder's inequality with the exponents $2^*/2$ and $d/2$ to write

$$
\begin{align*}
\|L_N\|_{1,\mathbb{Z}^d\setminus E} &\le \sum_{\underline{x} \in \mathbb{Z}^d \setminus X} \sum_{y \in B(\underline{x})} (f_N(y))^2 \\
&\le \left( \sum_{\underline{x} \in \mathbb{Z}^d \setminus X} \sum_{y \in B(\underline{x})} (f_N(y))^{2*} \right)^{2/2*} |\text{supp } f_N \setminus E|^{1-2/2*}.
\end{align*}
$$

Moreover, on the event $\mathcal{A}$, we have

$$
|\text{supp } f_N \setminus E| \le |\text{supp } f_N| \le cn^d.
$$

Using also inequality (5.13), we conclude that $\|L_N : \|_{1,\mathbb{Z}^d\setminus E} \le \Gamma_2$.

<figure><img src="image_6.png" /></figure>

It follows from inequality (5.25) and Lemma 5.1 that

$$
P(\mathcal{B}) = P(\mathcal{B}, \|L_N\|_{1,D} \ge N - \Gamma_2) = \sum_{N - \Gamma_2 \le t \le N} P(\mathcal{B}, \|L_N\|_{1,D} = t).
$$

Now, if $\|L_N\|_{1,D} = t$, then $\tau(D,t) < \infty$ and $L_N(y) = L_t^D(y)$ for any $y \in D$, thus

$$
\|L_N - g^2\|_{1,\mathrm{D}} = \|L_t^D - g^2\|_{1,\mathrm{D}},
$$

and we obtain the bound

$$
(5.26) \quad P(\mathcal{B})
\le \sum_{N - \Gamma_2 \le t \le N} P\left(f_N \in \mathcal{F}, \mathcal{A}, \underline{X}(f_N, \delta) = X, \|L_t^D - g^2\|_{1,\mathrm{D}} < \Gamma_1, \tau < \infty\right).
$$

Let us fix $t$ such that

$$
(5.27) \qquad N - \Gamma_2 \le t \le N.
$$

The time has now come to make specific choices for the parameters $\delta, M, \eta, \lambda$ intro-
duced in the course of the proof (recall that $\lambda$ was introduced in (5.22)). We suppose
that

$$
(5.28) \qquad \delta = \frac{1}{n^{\alpha}}, \quad M = n^{\beta}, \quad \eta = \frac{1}{n^{\gamma}}, \quad \lambda = n^{\rho},
$$

where $\alpha, \beta, \gamma, \rho$ are positive exponents, which satisfy furthermore

$$
(5.29) \quad \beta < 1, \quad \frac{2^*}{2}\alpha - \gamma < \beta, \quad 2^*\alpha < d\beta, 1 + \beta < \rho, \quad 2 - 4\alpha/d < \rho, \quad \rho < 2.
$$

These conditions imply that, as $N$ or $n$ goes to $\infty$,

$$
(5.30) \qquad \Gamma_0 \underset{n \to \infty}{\overset{\ln}{\sim}} n^{d/2+\beta}, \quad \Gamma_1 \underset{n \to \infty}{\overset{\ln}{\sim}} n^{d+1+\beta}, \quad \Gamma_2 \underset{n \to \infty}{\overset{\ln}{\sim}} n^{d+2-4\alpha/d},
$$
where $\sim_{n \to \infty}^{\ln}$ means that the logarithms are equivalent. In particular, we have

$$ (5.31) \qquad \frac{\Gamma_0}{\sqrt{N}} \to 0, \quad \frac{\Gamma_1}{N} \to 0, \quad \frac{\Gamma_2}{N} \to 0, \quad \frac{n^{d+1}}{\Gamma_1} \to 0, $$

whence for $n$ large enough

$$ (5.32) \qquad \Gamma_0 < \sqrt{N}, \quad \Gamma_1 < 3\Gamma_0\sqrt{N}, \quad n^{d+1} < \Gamma_1 < n^{d+2}, \quad \Gamma_2 < N/2. $$

We apply Proposition 3.6 with $r = \Gamma_1/t$, and $k = \lfloor \Gamma_1 \rfloor$: for any $x \in \bar{D}$, we have

$$ \begin{aligned} P(\|L_t^D - g^2\|_{1,D} < \Gamma_1, \tau < \infty) &= P\left(\left\|\frac{1}{t}L_t^D - \frac{1}{t}g^2\right\|_{1,D} < \frac{\Gamma_1}{t}, \tau < \infty\right) \\ &\le \frac{2 P_x\left(\left\|\frac{1}{t}L_t^D - \frac{1}{t}g^2\right\|_{1,D} \le \frac{\Gamma_1}{t} + 4\frac{\Gamma_1}{t-\Gamma_1}, \tau < \infty\right)}{P_x(S_{\lfloor \Gamma_1 \rfloor} = 0) + P_x(S_{\lfloor \Gamma_1 \rfloor-1} = 0)}. \end{aligned} $$

Moreover, using (5.27) and (5.31), for $n$ large enough,

$$ \frac{\Gamma_1}{t} + 4\frac{\Gamma_1}{t-\Gamma_1} \le \frac{5\Gamma_1}{t-\Gamma_1} \le \frac{7\Gamma_1}{t}. $$

Since $|R_N| \le cn^d$, then the range $R_N$ is included in the box $\Lambda(2cn^d)$ and its trace on the renormalized lattice is included in the box $\Lambda(2cn^{d-1})$. The set $\bar{D}$ is obtained by enlarging slightly this trace and then coming back to the original lattice, hence it is included in the box $\Lambda(3cn^d)$. We bound the denominator with the help of Lemma 3.5 (notice that $n^{d+1} < \Gamma_1 < n^{d+2}$) and we take the infimum over $x \in \bar{D}$:

$$ (5.33) \qquad P\left(\|L_t^D - g^2\|_{1,D} < \Gamma_1, \tau < \infty\right) \\ \le 2 \exp\left(c' \frac{n^{2d}}{[\Gamma_1]}\right) \inf_{x \in \bar{D}} P_x\left(\left\|\frac{1}{t}L_t^D - \frac{1}{t}g^2\right\|_{1,D} < \frac{7\Gamma_1}{t}, \tau < \infty\right). $$

For $k \in \mathbb{N}$ and $r > 0$, we define the closed convex set

$$ C(g, k, r) = \left\{ h \in \ell^1(D) : \left\| h - \frac{1}{k} g^2 \right\|_{1, D} \le r \right\}. $$

We apply the deviation inequality of Theorem 1.4 to the set $C(g, t, 7\Gamma_1/t)$:

$$ (5.34) \qquad \inf_{x \in \bar{D}} P_x \left( \left\| \frac{1}{t} L_t^D - \frac{1}{t} g^2 \right\|_{1, D} \le \frac{7\Gamma_1}{t}, \tau < \infty \right) \\ \le \exp \left( -t \inf_{h \in C(g, t, 7\Gamma_1/t)} \frac{1}{2} \mathcal{E}(\sqrt{h}, D) \right). $$

The previous inequalities (5.33) and (5.34) yield that

$$ (5.35) \qquad P\left(\|L_t^D - g^2\|_{1,D} < \Gamma_1, \tau < \infty\right) \\ \le 2 \exp\left(c' \frac{n^{2d}}{[\Gamma_1]} - t \inf_{h \in C(g, t, 7\Gamma_1/t)} \frac{1}{2} \mathcal{E}(\sqrt{h}, D)\right). $$
where $\sim_{n \to \infty}^{\ln}$ means that the logarithms are equivalent. In particular, we have

$$ (5.31) \qquad \frac{\Gamma_0}{\sqrt{N}} \to 0, \quad \frac{\Gamma_1}{N} \to 0, \quad \frac{\Gamma_2}{N} \to 0, \quad \frac{n^{d+1}}{\Gamma_1} \to 0, $$

whence for $n$ large enough

$$ (5.32) \qquad \Gamma_0 < \sqrt{N}, \quad \Gamma_1 < 3\Gamma_0\sqrt{N}, \quad n^{d+1} < \Gamma_1 < n^{d+2}, \quad \Gamma_2 < N/2. $$

We apply Proposition 3.6 with $r = \Gamma_1/t$, and $k = \lfloor \Gamma_1 \rfloor$: for any $x \in \bar{D}$, we have

$$ \begin{aligned} P(\|L_t^D - g^2\|_{1,D} < \Gamma_1, \tau < \infty) &= P\left(\left\|\frac{1}{t}L_t^D - \frac{1}{t}g^2\right\|_{1,D} < \frac{\Gamma_1}{t}, \tau < \infty\right) \\ &\le \frac{2 P_x\left(\left\|\frac{1}{t}L_t^D - \frac{1}{t}g^2\right\|_{1,D} \le \frac{\Gamma_1}{t} + 4\frac{\Gamma_1}{t-\Gamma_1}, \tau < \infty\right)}{P_x(S_{\lfloor \Gamma_1 \rfloor} = 0) + P_x(S_{\lfloor \Gamma_1 \rfloor-1} = 0)}. \end{aligned} $$

Moreover, using (5.27) and (5.31), for $n$ large enough,

$$ \frac{\Gamma_1}{t} + 4\frac{\Gamma_1}{t-\Gamma_1} \le \frac{5\Gamma_1}{t-\Gamma_1} \le \frac{7\Gamma_1}{t}. $$

Since $|R_N| \le cn^d$, then the range $R_N$ is included in the box $\Lambda(2cn^d)$ and its trace on the renormalized lattice is included in the box $\Lambda(2cn^{d-1})$. The set $\bar{D}$ is obtained by enlarging slightly this trace and then coming back to the original lattice, hence it is included in the box $\Lambda(3cn^d)$. We bound the denominator with the help of Lemma 3.5 (notice that $n^{d+1} < \Gamma_1 < n^{d+2}$) and we take the infimum over $x \in \bar{D}$:

$$ (5.33) \qquad P\left(\|L_t^D - g^2\|_{1,D} < \Gamma_1, \tau < \infty\right) \\ \le 2 \exp\left(c' \frac{n^{2d}}{\lfloor \Gamma_1 \rfloor}\right) \inf_{x \in \bar{D}} P_x\left(\left\|\frac{1}{t}L_t^D - \frac{1}{t}g^2\right\|_{1,D} < \frac{7\Gamma_1}{t}, \tau < \infty\right). $$

For $k \in \mathbb{N}$ and $r > 0$, we define the closed convex set

$$ C(g, k, r) = \left\{ h \in \ell^1(D) : \left\| h - \frac{1}{k} g^2 \right\|_{1, D} \le r \right\}. $$

We apply the deviation inequality of Theorem 1.4 to the set $C(g, t, 7\Gamma_1/t)$:

$$ (5.34) \qquad \inf_{x \in \bar{D}} P_x \left( \left\| \frac{1}{t} L_t^D - \frac{1}{t} g^2 \right\|_{1, D} \le \frac{7\Gamma_1}{t}, \tau < \infty \right) \\ \le \exp \left( -t \inf_{h \in C(g, t, 7\Gamma_1/t)} \frac{1}{2} \mathcal{E}(\sqrt{h}, D) \right). $$

The previous inequalities (5.33) and (5.34) yield that

$$ (5.35) \qquad P\left(\|L_t^D - g^2\|_{1,D} < \Gamma_1, \tau < \infty\right) \\ \le 2 \exp\left(c' \frac{n^{2d}}{\lfloor \Gamma_1 \rfloor} - t \inf_{h \in C(g, t, 7\Gamma_1/t)} \frac{1}{2} \mathcal{E}(\sqrt{h}, D)\right). $$
We deal next with the infimum in the exponential. Our first goal is to obtain a bound which depends on $N$ (and not on $t$). Let $h \in C(g, t, 7\Gamma_1/t)$. We have

$$ \begin{aligned} \left\|h - \frac{1}{N}g^2\right\|_{1,D} &\le \left\|h - \frac{1}{t}g^2\right\|_{1,D} + \left\|\frac{1}{t}g^2 - \frac{1}{N}g^2\right\|_{1,D} \\ &\le \frac{7\Gamma_1}{t} + \left|\frac{1}{t} - \frac{1}{N}\right| \left\|g^2\right\|_{1,D}. \end{aligned} $$

Now, from (5.27), we have

$$ \left|\frac{1}{t} - \frac{1}{N}\right| = \frac{N-t}{Nt} \le \frac{\Gamma_2}{N(N-\Gamma_2)}. $$

Therefore, using the inequalities (5.19), (5.27) and (5.32), we get

$$ \begin{aligned} \left\|h - \frac{1}{N}g^2\right\|_{1,D} &\le \frac{7\Gamma_1}{t} + \frac{\Gamma_2}{N(N-\Gamma_2)} \left(\Gamma_0 + \sqrt{N}\right)^2 \\ &\le \frac{7\Gamma_1}{N-\Gamma_2} + \frac{4\Gamma_2}{N-\Gamma_2} \le \frac{14\Gamma_1}{N} + \frac{8\Gamma_2}{N}. \end{aligned} \quad (5.36) $$

Setting

$$ r(N) = \frac{14\Gamma_1}{N} + \frac{8\Gamma_2}{N}, $$

we conclude that

$$ C\left(g, t, \frac{7\Gamma_1}{t}\right) \subset C\left(g, N, r(N)\right). $$

Recalling that $t \ge N - \Gamma_2$, inequality (5.35) now implies

$$ \begin{aligned} P\left(\left\|L_t^D - g^2\right\|_{1,D} < \Gamma_1, \tau < \infty\right) &\le 2 \exp \left( c' \frac{n^{2d}}{[\Gamma_1]} - (N - \Gamma_2) \inf \left\{ \frac{1}{2} \mathcal{E}(\sqrt{h}, D) : h \in C(g, N, r(N)) \right\} \right). \end{aligned} $$

The good point is that this upper bound does not depend any more on $t$. Plugging this upper bound in equations (5.23) and (5.26), we obtain

$$ \begin{aligned} (5.37) \quad E(e^{-|R_N|}; \mathcal{B}) &\le 2(\Gamma_2 + 1) \exp \left( - \left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| + \frac{2\Gamma_1}{\lambda} \right) \\ &\quad + c' \frac{n^{2d}}{[\Gamma_1]} - (N - \Gamma_2) \inf \left\{ \frac{1}{2} \mathcal{E}(\sqrt{h}, D) : h \in C(g, N, r(N)) \right\}. \end{aligned} $$

Our next goal is to remove the dependence on $g$ in the upper bound. We wish to obtain an upper bound which depends only on the set $\mathcal{F}$. To do so, we shall control the Dirichlet energy $\mathcal{E}(\sqrt{h}, D)$ restricted to $D$ with the help of the Dirichlet energy $\mathcal{E}(\sqrt{h})$ in the whole space. Of course, this creates a correcting factor, which we study in the next section.
We deal next with the infimum in the exponential. Our first goal is to obtain a bound which depends on $N$ (and not on $t$). Let $h \in C(g, t, 7\Gamma_1/t)$. We have

$$ \begin{aligned} \left\|h - \frac{1}{N}g^2\right\|_{1,D} &\le \left\|h - \frac{1}{t}g^2\right\|_{1,D} + \left\|\frac{1}{t}g^2 - \frac{1}{N}g^2\right\|_{1,D} \\ &\le \frac{7\Gamma_1}{t} + \left|\frac{1}{t} - \frac{1}{N}\right| \left\|g^2\right\|_{1,D}. \end{aligned} $$

Now, from (5.27), we have

$$ \left|\frac{1}{t} - \frac{1}{N}\right| = \frac{N-t}{Nt} \le \frac{\Gamma_2}{N(N-\Gamma_2)}. $$

Therefore, using the inequalities (5.19), (5.27) and (5.32), we get

$$ \begin{aligned} \left\|h - \frac{1}{N}g^2\right\|_{1,D} &\le \frac{7\Gamma_1}{t} + \frac{\Gamma_2}{N(N-\Gamma_2)} \left(\Gamma_0 + \sqrt{N}\right)^2 \\ &\le \frac{7\Gamma_1}{N-\Gamma_2} + \frac{4\Gamma_2}{N-\Gamma_2} \le \frac{14\Gamma_1}{N} + \frac{8\Gamma_2}{N}. \end{aligned} \quad (5.36) $$

Setting

$$ r(N) = \frac{14\Gamma_1}{N} + \frac{8\Gamma_2}{N}, $$

we conclude that

$$ C\left(g, t, \frac{7\Gamma_1}{t}\right) \subset C\left(g, N, r(N)\right). $$

Recalling that $t \ge N - \Gamma_2$, inequality (5.35) now implies

$$ \begin{aligned} P\left(\left\|L_t^D - g^2\right\|_{1,D} < \Gamma_1, \tau < \infty\right) &\le 2 \exp\left(c' \frac{n^{2d}}{[\Gamma_1]} - (N - \Gamma_2) \inf\left\{\frac{1}{2}\mathcal{E}(\sqrt{h}, D) : h \in C(g, N, r(N))\right\}\right). \end{aligned} $$

The good point is that this upper bound does not depend any more on $t$. Plugging this upper bound in equations (5.23) and (5.26), we obtain

$$ \begin{aligned} (5.37) \quad E(e^{-|R_N|}; \mathcal{B}) &\le 2(\Gamma_2 + 1) \exp\left(-\left|\left\{x \in D : g^2(x) \ge \lambda\right\}\right| + \frac{2\Gamma_1}{\lambda}\right) \\ &\quad + c' \frac{n^{2d}}{[\Gamma_1]} - (N - \Gamma_2) \inf\left\{\frac{1}{2}\mathcal{E}(\sqrt{h}, D) : h \in C(g, N, r(N))\right\}. \end{aligned} $$

Our next goal is to remove the dependence on $g$ in the upper bound. We wish to obtain an upper bound which depends only on the set $\mathcal{F}$. To do so, we shall control the Dirichlet energy $\mathcal{E}(\sqrt{h}, D)$ restricted to $D$ with the help of the Dirichlet energy $\mathcal{E}(\sqrt{h})$ in the whole space. Of course, this creates a correcting factor, which we study in the next section.
### 5.3. Truncation

We first define a truncation operator associated to the set $X$. Let $\phi: \mathbb{R}^d \to [0, 1]$ be a function such that

* $\text{supp} \phi \subset \Lambda(7/4)$,

* $\phi$ is piecewise affine on $\Lambda(7/4) \setminus \Lambda(5/4)$,

* $\phi$ is equal to 1 on $\Lambda(5/4)$,

* the gradient of $\phi$ has Euclidean norm less than 4 on $\Lambda(7/4) \setminus \Lambda(5/4)$.

To the set $X$, we associate the function $\phi_X$ defined by

$$ \forall y \in \mathbb{Z}^d \quad \phi_X(y) = \max \{ \phi(y/n - x) : x \in X \}. $$

By construction, we have

$$ (5.38) \qquad \text{supp} \phi_X \subset \bigcup_{x \in X} \Lambda(nx, 2n) \subset D, $$

where the domain $D$ was defined in (5.11). Let $f$ be any function in $\ell^1(\mathbb{Z}^d)$. We define the function $\phi_X f$ by setting

$$ \forall y \in \mathbb{Z}^d \quad (\phi_X f)(y) = \phi_X(y)f(y). $$

If $f$ is a function in $\ell^1(D)$, we extend $f$ outside $D$ by setting $f(x) = 0$ for $x \in \mathbb{Z}^d \setminus D$ and the previous definition still makes sense. We recall that the set $E$ is defined in (5.12).

**PROPOSITION 5.2.** — Let $f$ be any function in $\ell^1(D)$. We have the inequality

$$ \mathcal{E}(f, D) \geq \left( \max \left( \sqrt{\mathcal{E}(\phi_X f)} - \frac{4}{n} \|f\|_{2, D \setminus E, 0} \right) \right)^2. $$

*Proof.* — Since the support of $\phi_X f$ is included in $D$ (see the inclusion (5.38)), then we have

$$ \begin{aligned} \mathcal{E}(\phi_X f) &= \mathcal{E}(\phi_X f, D) = \frac{1}{2d} \sum_{\substack{y,z \in D \\ |y-z|=1}} \left( \phi_X(y)f(y) - \phi_X(z)f(z) \right)^2 \\ &= \frac{1}{2d} \sum_{\substack{y,z \in D \\ |y-z|=1}} \left( \phi_X(y)(f(y) - f(z)) - (\phi_X(z) - \phi_X(y))f(z) \right)^2 \\ &= \frac{1}{2d} \sum_{\substack{y,z \in D \\ |y-z|=1}} \left( \left(\phi_X(y)\right)^2 (f(y) - f(z))^2 + \left(\phi_X(z) - \phi_X(y)\right)^2 (f(z))^2 \right. \\ & \qquad \left. - 2\phi_X(y)(f(y) - f(z))(\phi_X(z) - \phi_X(y))f(z) \right). \end{aligned} $$

From the definition of $\phi_X$, it follows that if $|y-z| = 1$, then $|\phi_X(z) - \phi_X(y)| \le 4/n$, and $\phi_X(z) = \phi_X(y)$ unless both $y, z$ are in $D \setminus E$. Therefore we have the following bound:

$$ \mathcal{E}(\phi_X f) \le \mathcal{E}(f, D) + \left(\frac{4}{n}\right)^2 \sum_{\substack{y, z \in D \setminus E \\ |y-z|=1}} f(z)^2 + \frac{4}{nd} \sum_{\substack{y, z \in D \setminus E \\ |y-z|=1}} |f(y) - f(z)| |f(z)|. $$
### 5.3. Truncation

We first define a truncation operator associated to the set $X$. Let $\phi: \mathbb{R}^d \to [0, 1]$ be a function such that

* $\text{supp} \phi \subset \Lambda(7/4)$,

* $\phi$ is piecewise affine on $\Lambda(7/4) \setminus \Lambda(5/4)$,

* $\phi$ is equal to 1 on $\Lambda(5/4)$,

* the gradient of $\phi$ has Euclidean norm less than 4 on $\Lambda(7/4) \setminus \Lambda(5/4)$.

To the set $X$, we associate the function $\phi_X$ defined by

$$ \forall y \in \mathbb{Z}^d \quad \phi_X(y) = \max \{ \phi(y/n - x) : x \in X \}. $$

By construction, we have

$$ (5.38) \qquad \text{supp} \phi_X \subset \bigcup_{x \in X} \Lambda(nx, 2n) \subset D, $$

where the domain $D$ was defined in (5.11). Let $f$ be any function in $\ell^1(\mathbb{Z}^d)$. We define the function $\phi_X f$ by setting

$$ \forall y \in \mathbb{Z}^d \quad (\phi_X f)(y) = \phi_X(y)f(y). $$

If $f$ is a function in $\ell^1(D)$, we extend $f$ outside $D$ by setting $f(x) = 0$ for $x \in \mathbb{Z}^d \setminus D$ and the previous definition still makes sense. We recall that the set $E$ is defined in (5.12).

**PROPOSITION 5.2.** — Let $f$ be any function in $\ell^1(D)$. We have the inequality

$$ \mathcal{E}(f, D) \ge \left( \max \left( \sqrt{\mathcal{E}(\phi_X f)} - \frac{4}{n} \|f\|_{2, D \setminus E, 0} \right) \right)^2. $$

*Proof.* — Since the support of $\phi_X f$ is included in $D$ (see the inclusion (5.38)), then we have

$$ \begin{align*} \mathcal{E}(\phi_X f) &= \mathcal{E}(\phi_X f, D) = \frac{1}{2d} \sum_{\substack{y,z \in D \\ |y-z|=1}} (\phi_X(y)f(y) - \phi_X(z)f(z))^2 \\ &= \frac{1}{2d} \sum_{\substack{y,z \in D \\ |y-z|=1}} \left( \phi_X(y)(f(y) - f(z)) - (\phi_X(z) - \phi_X(y))f(z) \right)^2 \\ &= \frac{1}{2d} \sum_{\substack{y,z \in D \\ |y-z|=1}} \left( \left(\phi_X(y)\right)^2 (f(y) - f(z))^2 + \left(\phi_X(z) - \phi_X(y)\right)^2 (f(z))^2 \right. \\ & \qquad \left. - 2\phi_X(y)(f(y) - f(z))(\phi_X(z) - \phi_X(y))f(z) \right). \end{align*} $$

From the definition of $\phi_X$, it follows that if $|y-z| = 1$, then $|\phi_X(z) - \phi_X(y)| \le 4/n$, and $\phi_X(z) = \phi_X(y)$ unless both $y, z$ are in $D \setminus E$. Therefore we have the following bound:

$$ \mathcal{E}(\phi_X f) \le \mathcal{E}(f, D) + \left(\frac{4}{n}\right)^2 \sum_{\substack{y, z \in D \setminus E \\ |y-z|=1}} f(z)^2 + \frac{4}{nd} \sum_{\substack{y, z \in D \setminus E \\ |y-z|=1}} |f(y) - f(z)| |f(z)|. $$
Using the Cauchy–Schwarz inequality, we get

$$
\sum_{\substack{y, z \in D \setminus E \\ |y-z|=1}} |f(y) - f(z)| |f(z)| \\
\le \left( \sum_{\substack{y, z \in D \setminus E \\ |y-z|=1}} (f(y) - f(z))^2 \sum_{\substack{y, z \in D \setminus E \\ |y-z|=1}} (f(z))^2 \right)^{\frac{1}{2}} \\
\le \sqrt{2d\mathcal{E}(f, D \setminus E)} \sqrt{2d} \|f\|_{2, D \setminus E} = 2d \sqrt{\mathcal{E}(f, D)} \|f\|_{2, D \setminus E}.
$$

Reporting in the previous inequality, we have

$$
\begin{align*}
\mathcal{E}(\phi_X f) &\le \mathcal{E}(f, D) + \frac{16}{n^2} (\|f\|_{2, D \setminus E})^2 + \frac{8}{n} \sqrt{\mathcal{E}(f, D)} \|f\|_{2, D \setminus E} \\
&= \left( \sqrt{\mathcal{E}(f, D)} + \frac{4}{n} \|f\|_{2, D \setminus E} \right)^2,
\end{align*}
$$

from which we deduce easily the inequality stated in the proposition.

<figure><img src="image_5.png" /></figure>

5.4. End of proof of Theorem 2.2

We come back to inequality (5.37). We wish to obtain an upper bound which
depends on the set $\mathcal{F}$ and not on $g$. We know that $f_N$ belongs to $\mathcal{F}$, so we pick a
function $h$ in $C(g, N, r(N))$ and we try to control the distance between $\frac{1}{N}L_N$ and
$\phi_X^2 h$. We write

$$
\left\| \frac{1}{N} L_N - \phi_X^2 h \right\|_1 \le \left\| \frac{1}{N} L_N - \frac{1}{N} \phi_X^2 L_N \right\|_1 + \left\| \frac{1}{N} \phi_X^2 L_N - \phi_X^2 h \right\|_1
$$

and we control separately each term. For the first term, we use the fact that $\phi_X$ is
equal to 1 on $E$ and Lemma 5.1 to get

$$
(5.39) \qquad \left\| \frac{1}{N} L_N - \frac{1}{N} \phi_X^2 L_N \right\|_1 \le \left\| \frac{1}{N} L_N \right\|_{1, \mathbb{Z}^d \setminus E} \le \frac{\Gamma_2}{N}.
$$

For the second term, we have, recalling that supp $\phi_X \subset D$ and the definition of $\mathcal{B}$
in (5.24), and using (5.36),

$$
\begin{align*}
\left\| \frac{1}{N} \phi_X^2 L_N - \phi_X^2 h \right\|_1 &\le \left\| \frac{1}{N} L_N - h \right\|_{1, D} \\
(5.40) \qquad &\le \left\| \frac{1}{N} L_N - \frac{1}{N} g^2 \right\|_{1, D} + \left\| \frac{1}{N} g^2 - h \right\|_{1, D} \\
&\le \frac{\Gamma_1}{N} + r(N). \qedhere
\end{align*}
$$

Inequalities (5.39) and (5.40) together yield

$$
(5.41) \qquad \left\| \frac{1}{N} L_N - \phi_X^2 h \right\|_1 \le \frac{\Gamma_2}{N} + \frac{\Gamma_1}{N} + r(N).
$$
Using the Cauchy–Schwarz inequality, we get

$$
\sum_{\substack{y, z \in D \setminus E \\ |y-z|=1}} |f(y) - f(z)| |f(z)| \\
\le \left( \sum_{\substack{y, z \in D \setminus E \\ |y-z|=1}} (f(y) - f(z))^2 \sum_{\substack{y, z \in D \setminus E \\ |y-z|=1}} (f(z))^2 \right)^{\frac{1}{2}} \\
\le \sqrt{2d \mathcal{E}(f, D \setminus E)} \sqrt{2d} \|f\|_{2, D \setminus E} = 2d \sqrt{\mathcal{E}(f, D)} \|f\|_{2, D \setminus E}.
$$

Reporting in the previous inequality, we have

$$
\begin{align*}
\mathcal{E}(\phi_X f) &\le \mathcal{E}(f, D) + \frac{16}{n^2} (\|f\|_{2, D \setminus E})^2 + \frac{8}{n} \sqrt{\mathcal{E}(f, D)} \|f\|_{2, D \setminus E} \\
&= \left( \sqrt{\mathcal{E}(f, D)} + \frac{4}{n} \|f\|_{2, D \setminus E} \right)^2,
\end{align*}
$$

from which we deduce easily the inequality stated in the proposition.

<figure><img src="image_7.png" /></figure>

5.4. End of proof of Theorem 2.2

We come back to inequality (5.37). We wish to obtain an upper bound which
depends on the set $\mathcal{F}$ and not on $g$. We know that $f_N$ belongs to $\mathcal{F}$, so we pick a
function $h$ in $C(g, N, r(N))$ and we try to control the distance between $\frac{1}{N}L_N$ and
$\phi_X^2 h$. We write

$$
\left\| \frac{1}{N} L_N - \phi_X^2 h \right\|_1 \le \left\| \frac{1}{N} L_N - \frac{1}{N} \phi_X^2 L_N \right\|_1 + \left\| \frac{1}{N} \phi_X^2 L_N - \phi_X^2 h \right\|_1
$$

and we control separately each term. For the first term, we use the fact that $\phi_X$ is
equal to 1 on $E$ and Lemma 5.1 to get

$$
(5.39) \qquad \left\| \frac{1}{N} L_N - \frac{1}{N} \phi_X^2 L_N \right\|_1 \le \left\| \frac{1}{N} L_N \right\|_{1, \mathbb{Z}^d \setminus E} \le \frac{\Gamma_2}{N}.
$$

For the second term, we have, recalling that supp $\phi_X \subset D$ and the definition of $\mathcal{B}$
in (5.24), and using (5.36),

$$
\begin{align*}
\left\| \frac{1}{N} \phi_X^2 L_N - \phi_X^2 h \right\|_1 &\le \left\| \frac{1}{N} L_N - h \right\|_{1, D} \\
(5.40) \qquad &\le \left\| \frac{1}{N} L_N - \frac{1}{N} g^2 \right\|_{1, D} + \left\| \frac{1}{N} g^2 - h \right\|_{1, D} \\
&\le \frac{\Gamma_1}{N} + r(N). \qedhere
\end{align*}
$$

Inequalities (5.39) and (5.40) together yield

$$
(5.41) \qquad \left\| \frac{1}{N} L_N - \phi_X^2 h \right\|_1 \le \frac{\Gamma_2}{N} + \frac{\Gamma_1}{N} + r(N).
$$
Furthermore, we have, by inequalities (5.20) and (5.41),

$$
(5.42) \qquad \left\| \frac{1}{N} g^2 - \phi_X^2 h \right\|_{1,D} \le \left\| \frac{1}{N} g^2 - \frac{1}{N} L_N \right\|_{1,D} + \left\| \frac{1}{N} L_N - \phi_X^2 h \right\|_{1,D} \\
\le \frac{\Gamma_1}{N} + \frac{\Gamma_2}{N} + \frac{\Gamma_1}{N} + r(N).
$$

Let us set

$$
(5.43) \qquad \Gamma_3 = \frac{\Gamma_2}{N} + 2\frac{\Gamma_1}{N} + r(N) \le \frac{16\Gamma_1}{N} + \frac{9\Gamma_2}{N}.
$$

We work next on the first term in the exponential appearing in (5.37). For any
$f \in \ell^1(D)$, we have

$$
\left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| \ge \left| \left\{ x \in D : f(x) \ge \frac{2\lambda}{N}, \left| f(x) - \frac{g^2(x)}{N} \right| < \frac{\lambda}{N} \right\} \right| \\
\ge \left| \left\{ x \in D : f(x) \ge \frac{2\lambda}{N} \right\} \right| - \left| \left\{ x \in D : \left| f(x) - \frac{1}{N} g^2(x) \right| \ge \frac{\lambda}{N} \right\} \right|.
$$

Moreover, by Markov's inequality,

$$
\left| \left\{ x \in D : \left| f(x) - \frac{1}{N} g^2(x) \right| \ge \frac{\lambda}{N} \right\} \right| \le \frac{N}{\lambda} \left\| f - \frac{1}{N} g^2 \right\|_{1, D},
$$

whence

$$
\left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| \ge \left| \left\{ x \in D : f(x) \ge \frac{2\lambda}{N} \right\} \right| - \frac{N}{\lambda} \left\| f - \frac{1}{N} g^2 \right\|_{1,D}.
$$

Let $h \in C(g, N, r(N))$ and let us apply this inequality with $f = \phi_X^2 h$. Together with inequality (5.42), we obtain

$$
\left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| \ge \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| - \frac{N}{\lambda} \Gamma_3.
$$

Taking the supremum over $h$ in $C(g, N, r(N))$, we get

$$
\left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| \\
\ge \sup \left\{ \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| : h \in C(g, N, r(N)) \right\} - \frac{N}{\lambda} \Gamma_3.
$$
Furthermore, we have, by inequalities (5.20) and (5.41),

$$ (5.42) \qquad \begin{aligned} \left\| \frac{1}{N} g^2 - \phi_X^2 h \right\|_{1,D} &\le \left\| \frac{1}{N} g^2 - \frac{1}{N} L_N \right\|_{1,D} + \left\| \frac{1}{N} L_N - \phi_X^2 h \right\|_{1,D} \\ &\le \frac{\Gamma_1}{N} + \frac{\Gamma_2}{N} + \frac{\Gamma_1}{N} + r(N). \end{aligned} $$

Let us set

$$ (5.43) \qquad \Gamma_3 = \frac{\Gamma_2}{N} + 2\frac{\Gamma_1}{N} + r(N) \le \frac{16\Gamma_1}{N} + \frac{9\Gamma_2}{N}. $$

We work next on the first term in the exponential appearing in (5.37). For any $f \in \ell^1(D)$, we have

$$ \left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| \ge \left| \left\{ x \in D : f(x) \ge \frac{2\lambda}{N}, \left| f(x) - \frac{g^2(x)}{N} \right| < \frac{\lambda}{N} \right\} \right| \\ \ge \left| \left\{ x \in D : f(x) \ge \frac{2\lambda}{N} \right\} \right| - \left| \left\{ x \in D : \left| f(x) - \frac{1}{N} g^2(x) \right| \ge \frac{\lambda}{N} \right\} \right|. $$

Moreover, by Markov's inequality,

$$ \left| \left\{ x \in D : \left| f(x) - \frac{1}{N} g^2(x) \right| \ge \frac{\lambda}{N} \right\} \right| \le \frac{N}{\lambda} \left\| f - \frac{1}{N} g^2 \right\|_{1, D}, $$

whence

$$ \left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| \ge \left| \left\{ x \in D : f(x) \ge \frac{2\lambda}{N} \right\} \right| - \frac{N}{\lambda} \left\| f - \frac{1}{N} g^2 \right\|_{1, D}. $$

Let $h \in C(g, N, r(N))$ and let us apply this inequality with $f = \phi_X^2 h$. Together with inequality (5.42), we obtain

$$ \left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| \ge \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| - \frac{N}{\lambda} \Gamma_3. $$

Taking the supremum over $h$ in $C(g, N, r(N))$, we get

$$ \left| \left\{ x \in D : g^2(x) \ge \lambda \right\} \right| \\ \ge \sup \left\{ \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| : h \in C(g, N, r(N)) \right\} - \frac{N}{\lambda} \Gamma_3. $$
Plugging this into inequality (5.37), we arrive at

$$
\begin{align*}
E(e^{-|R_N|}; \mathcal{B}) &\le 2(\Gamma_2 + 1) \exp \left( \frac{N}{\lambda}\Gamma_3 + \frac{2\Gamma_1}{\lambda} + c' \frac{n^{2d}}{[\Gamma_1]} \right. \\
&\qquad \left. - \sup \left\{ \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| : h \in C(g, N, r(N)) \right\} \right. \\
&\qquad \left. - (N - \Gamma_2) \inf \left\{ \frac{1}{2} \mathcal{E}(\sqrt{h}, D) : h \in C(g, N, r(N)) \right\} \right) \\
&\le 2(\Gamma_2 + 1) \exp \left( \frac{N}{\lambda}\Gamma_3 + \frac{2\Gamma_1}{\lambda} + c' \frac{n^{2d}}{[\Gamma_1]} \right. \\
&\qquad \left. - \inf \left\{ \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| + \frac{N - \Gamma_2}{2} \mathcal{E}(\sqrt{h}, D) : h \in C(g, N, r(N)) \right\} \right).
\end{align*}
$$

Let again $h \in C(g, N, r(N))$. We apply Proposition 5.2 to the function $f = \sqrt{h}$:

$$
\mathcal{E}(\sqrt{h}, D) \ge \left( \max \left( \sqrt{\mathcal{E}(\phi_X \sqrt{h})} - \frac{4}{n} \|\sqrt{h}\|_{2, D \setminus E}, 0 \right) \right)^2 .
$$

Now, using inequalities (5.39), (5.40) and (5.43), we get

$$
\begin{align*}
\left(\|\sqrt{h}\|_{2, D \setminus E}\right)^2 \\
&= \|h\|_{1, D \setminus E} \le \left\|h - \frac{1}{N} L_N\right\|_{1, D \setminus E} + \left\|\frac{1}{N} L_N\right\|_{1, \mathbb{Z}^d \setminus E} \le \frac{\Gamma_1}{N} + r(N) + \frac{\Gamma_2}{N} \le \Gamma_3.
\end{align*}
$$

We conclude that

$$
\begin{align*}
(5.44) \quad E(e^{-|R_N|}; \mathcal{B}) &\le 2(\Gamma_2 + 1) \exp \left( \frac{N}{\lambda}\Gamma_3 + \frac{2\Gamma_1}{\lambda} + c' \frac{n^{2d}}{[\Gamma_1]} \right. \\
&\qquad \left. - \inf \left\{ \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| \right. \right. \\
&\qquad \left. \left. + \frac{N - \Gamma_2}{2} \left( \max \left( \sqrt{\mathcal{E}(\phi_X \sqrt{h})} - \frac{4\sqrt{\Gamma_3}}{n}, 0 \right) \right)^2 : h \in C(g, N, r(N)) \right\} \right). \\
&\le \frac{\Gamma_1}{N} + r(N) + \frac{\Gamma_2}{N} \le \Gamma_3.
\end{align*}
$$

Our next goal is to remove the term $2\lambda/N$ appearing in the infimum. Let us fix again $h \in C(g, N, r(N))$. We define an auxiliary function $\tilde{h}$ by setting

$$
\forall x \in \mathbb{Z}^d \quad \tilde{h}(x) = \left( \max \left( \phi_X \sqrt{h}(x) - \sqrt{\frac{2\lambda}{N}}, 0 \right) \right)^2 .
$$

Let also define

$$
A = \left\{ x \in \mathbb{Z}^d : \phi_X \sqrt{h}(x) > \sqrt{\frac{2\lambda}{N}} \right\} = \left\{ x \in \mathbb{Z}^d : \tilde{h}(x) > 0 \right\}.
$$

Obviously, we have $A \subset D$ (since supp $\phi_X \subset D$) and

$$
|A| \le \left| \left\{ x \in D : \phi_X^2 h(x) \ge \frac{2\lambda}{N} \right\} \right|.
$$
Plugging this into inequality (5.37), we arrive at

$$
\begin{align*}
E(e^{-|R_N|}; \mathcal{B}) &\le 2(\Gamma_2 + 1) \exp \left( \frac{N}{\lambda}\Gamma_3 + \frac{2\Gamma_1}{\lambda} + c' \frac{n^{2d}}{[\Gamma_1]} \right. \\
&\qquad \left. - \sup \left\{ \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| : h \in C(g, N, r(N)) \right\} \right. \\
&\qquad \left. - (N - \Gamma_2) \inf \left\{ \frac{1}{2} \mathcal{E}(\sqrt{h}, D) : h \in C(g, N, r(N)) \right\} \right) \\
&\le 2(\Gamma_2 + 1) \exp \left( \frac{N}{\lambda}\Gamma_3 + \frac{2\Gamma_1}{\lambda} + c' \frac{n^{2d}}{[\Gamma_1]} \right. \\
&\qquad \left. - \inf \left\{ \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| + \frac{N - \Gamma_2}{2} \mathcal{E}(\sqrt{h}, D) : h \in C(g, N, r(N)) \right\} \right).
\end{align*}
$$

Let again $h \in C(g, N, r(N))$. We apply Proposition 5.2 to the function $f = \sqrt{h}$:

$$
\mathcal{E}(\sqrt{h}, D) \ge \left( \max \left( \sqrt{\mathcal{E}(\phi_X \sqrt{h})} - \frac{4}{n} \|\sqrt{h}\|_{2, D \setminus E}, 0 \right) \right)^2 .
$$

Now, using inequalities (5.39), (5.40) and (5.43), we get

$$
\begin{align*}
& (\|\sqrt{h}\|_{2, D \setminus E})^2 \\
&= \|h\|_{1, D \setminus E} \le \left\| h - \frac{1}{N} L_N \right\|_{1, D \setminus E} + \left\| \frac{1}{N} L_N \right\|_{1, \mathbb{Z}^d \setminus E} \le \frac{\Gamma_1}{N} + r(N) + \frac{\Gamma_2}{N} \le \Gamma_3.
\end{align*}
$$

We conclude that

$$
\begin{align*}
(5.44) \quad E(e^{-|R_N|}; \mathcal{B}) &\le 2(\Gamma_2 + 1) \exp \left( \frac{N}{\lambda}\Gamma_3 + \frac{2\Gamma_1}{\lambda} + c' \frac{n^{2d}}{[\Gamma_1]} \right. \\
&\qquad \left. - \inf \left\{ \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| \right. \right. \\
&\qquad \left. \left. + \frac{N - \Gamma_2}{2} \left( \max \left( \sqrt{\mathcal{E}(\phi_X \sqrt{h})} - \frac{4\sqrt{\Gamma_3}}{n}, 0 \right) \right)^2 : h \in C(g, N, r(N)) \right\} \right).
\end{align*}
$$

Our next goal is to remove the term $2\lambda/N$ appearing in the infimum. Let us fix again $h \in C(g, N, r(N))$. We define an auxiliary function $\tilde{h}$ by setting

$$
\forall x \in \mathbb{Z}^d \quad \tilde{h}(x) = \left( \max \left( \phi_X \sqrt{h}(x) - \sqrt{\frac{2\lambda}{N}}, 0 \right) \right)^2 .
$$

Let also define

$$
A = \left\{ x \in \mathbb{Z}^d : \phi_X \sqrt{h}(x) > \sqrt{\frac{2\lambda}{N}} \right\} = \left\{ x \in \mathbb{Z}^d : \tilde{h}(x) > 0 \right\}.
$$

Obviously, we have $A \subset D$ (since supp $\phi_X \subset D$) and

$$
|A| \le \left| \left\{ x \in D : \phi_X^2 h(x) \ge \frac{2\lambda}{N} \right\} \right|.
$$
We have then

$$
\begin{align*}
\mathcal{E}(\sqrt{\tilde{h}}) &= \frac{1}{2d} \sum_{\substack{y, z \in \mathbb{Z}^d \\ |y-z|=1}} (\sqrt{\tilde{h}(y)} - \sqrt{\tilde{h}(z)})^2 \\
&= \frac{1}{2d} \sum_{\substack{y, z \in A \\ |y-z|=1}} (\phi_X \sqrt{\tilde{h}}(y) - \phi_X \sqrt{\tilde{h}}(z))^2 + \frac{1}{d} \sum_{\substack{y \in A, z \notin A \\ |y-z|=1}} (\phi_X \sqrt{\tilde{h}}(y) - \sqrt{\frac{2\lambda}{N}})^2 \\
&\le \mathcal{E}(\phi_X \sqrt{\tilde{h}}).
\end{align*}
$$

We conclude that

$$
(5.45) \quad \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| + \frac{N-\Gamma_2}{2} \left( \max \left( \sqrt{\mathcal{E}(\phi_X \sqrt{h})} - \frac{4\sqrt{\Gamma_3}}{n}, 0 \right) \right)^2 \\
\ge \left| \left\{ x \in \mathbb{Z}^d : \tilde{h}(x) > 0 \right\} \right| + \frac{N-\Gamma_2}{2} \left( \max \left( \sqrt{\mathcal{E}(\sqrt{\tilde{h}})} - \frac{4\sqrt{\Gamma_3}}{n}, 0 \right) \right)^2 .
$$

We evaluate next the distance between $\tilde{h}$ and $L_N/N$. To that end, we introduce the function

$$
\forall x \in \mathbb{Z}^d \quad \frac{1}{N} \widetilde{L}_N(x) = \left( \max \left( \frac{1}{\sqrt{N}} f_N(x) - \sqrt{\frac{2\lambda}{N}}, 0 \right) \right)^2,
$$

and we write

$$
(5.46) \quad \left\| \tilde{h} - \frac{1}{N} L_N \right\|_1 \le \left\| \tilde{h} - \frac{1}{N} \widetilde{L}_N \right\|_1 + \left\| \frac{1}{N} \widetilde{L}_N - \frac{1}{N} L_N \right\|_1 .
$$

We shall control the first term with the help of the following Lemma 5.3.

LEMMA 5.3. — For any $s, t > 0$, any $a > 0$, we have

$$
\left| \left( \max(\sqrt{t}-a, 0) \right)^2 - \left( \max(\sqrt{s}-a, 0) \right)^2 \right| \le |t-s|.
$$

Proof. — If $\sqrt{t} \ge \sqrt{s} \ge a$, then

$$
\begin{align*}
& \left( \max(\sqrt{t}-a,0) \right)^2 - \left( \max(\sqrt{s}-a,0) \right)^2 \\
&= (\sqrt{t}-a)^2 - (\sqrt{s}-a)^2 \\
&= t-s - 2a(\sqrt{t}-\sqrt{s}) \le t-s.
\end{align*}
$$
We have then

$$
\begin{align*}
\mathcal{E}(\sqrt{\tilde{h}}) &= \frac{1}{2d} \sum_{\substack{y, z \in \mathbb{Z}^d \\ |y-z|=1}} (\sqrt{\tilde{h}(y)} - \sqrt{\tilde{h}(z)})^2 \\
&= \frac{1}{2d} \sum_{\substack{y, z \in A \\ |y-z|=1}} (\phi_X \sqrt{\tilde{h}}(y) - \phi_X \sqrt{\tilde{h}}(z))^2 + \frac{1}{d} \sum_{\substack{y \in A, z \notin A \\ |y-z|=1}} (\phi_X \sqrt{\tilde{h}}(y) - \sqrt{\frac{2\lambda}{N}})^2 \\
&\le \mathcal{E}(\phi_X \sqrt{\tilde{h}}).
\end{align*}
$$

We conclude that

$$
(5.45) \quad \left| \left\{ x \in D : (\phi_X^2 h)(x) \ge \frac{2\lambda}{N} \right\} \right| + \frac{N - \Gamma_2}{2} \left( \max \left( \sqrt{\mathcal{E}(\phi_X \sqrt{h})} - \frac{4\sqrt{\Gamma_3}}{n}, 0 \right) \right)^2 \\
\ge \left| \left\{ x \in \mathbb{Z}^d : \tilde{h}(x) > 0 \right\} \right| + \frac{N - \Gamma_2}{2} \left( \max \left( \sqrt{\mathcal{E}(\sqrt{\tilde{h}})} - \frac{4\sqrt{\Gamma_3}}{n}, 0 \right) \right)^2 .
$$

We evaluate next the distance between $\tilde{h}$ and $L_N/N$. To that end, we introduce the function

$$
\forall x \in \mathbb{Z}^d \quad \frac{1}{N} \widetilde{L}_N(x) = \left( \max \left( \frac{1}{\sqrt{N}} f_N(x) - \sqrt{\frac{2\lambda}{N}}, 0 \right) \right)^2,
$$

and we write

$$
(5.46) \quad \left\| \tilde{h} - \frac{1}{N} L_N \right\|_1 \le \left\| \tilde{h} - \frac{1}{N} \widetilde{L}_N \right\|_1 + \left\| \frac{1}{N} \widetilde{L}_N - \frac{1}{N} L_N \right\|_1 .
$$

We shall control the first term with the help of the following Lemma 5.3.

LEMMA 5.3. — For any $s, t > 0$, any $a > 0$, we have

$$
\left| \left( \max(\sqrt{t}-a, 0) \right)^2 - \left( \max(\sqrt{s}-a, 0) \right)^2 \right| \le |t-s|.
$$

Proof. — If $\sqrt{t} \ge \sqrt{s} \ge a$, then

$$
\begin{align*}
& \left( \max(\sqrt{t} - a, 0) \right)^2 - \left( \max(\sqrt{s} - a, 0) \right)^2 \\
&= (\sqrt{t} - a)^2 - (\sqrt{s} - a)^2 \\
&= t - s - 2a(\sqrt{t} - \sqrt{s}) \le t - s.
\end{align*}
$$
If $\sqrt{t} \ge a \ge \sqrt{s}$, then

$$ \begin{aligned} & \left( \max(\sqrt{t}-a, 0) \right)^2 - \left( \max(\sqrt{s}-a, 0) \right)^2 \\ &= \left(\sqrt{t}-a\right)^2 \le \left(\sqrt{t}-\sqrt{s}\right)^2 \\ &= \left(\frac{t-s}{\sqrt{t}+\sqrt{s}}\right)^2 \le (t-s) \frac{t+s}{\left(\sqrt{t}+\sqrt{s}\right)^2} \le t-s. \end{aligned} $$

In each case, we obtain the desired inequality.

Now, thanks to Lemma 5.3 applied with

<figure><img src="image_6.png" /></figure>

$$ a = \sqrt{2\lambda/N}, \quad t = \phi_X^2 h(x), \quad s = \frac{1}{N} L_N(x), $$

we have

$$ \left\| \tilde{h} - \frac{1}{N} L_N \right\|_1 \le \sum_{x \in \mathbb{Z}^d} \left| \phi_X^2 h(x) - \frac{1}{N} L_N(x) \right| = \left\| \phi_X^2 h - \frac{1}{N} L_N \right\|_1 \le \Gamma_3, $$

where the last inequality is a consequence of inequalities (5.41) and (5.43). We deal finally with the second term of formula (5.46). We set $a = \sqrt{2\lambda/N}$ and we define

$$ B = \left\{ x \in \mathbb{Z}^d : \frac{1}{N} L_N(x) \ge a^2 \right\}. $$

We have

$$ \begin{aligned} \left\| \frac{1}{N} L_N - \frac{1}{N} L_N \right\|_1 &= \sum_{x \in B} \left| \left( \frac{1}{\sqrt{N}} f_N(x) - a \right)^2 - \frac{1}{N} L_N(x) \right| + \sum_{x \in \mathbb{Z}^d \setminus B} \frac{1}{N} L_N(x) \\ &\le \sum_{x \in B} \left| a^2 - 2a \frac{1}{\sqrt{N}} f_N(x) \right| + a^2 \left| \text{supp } f_N \right| \\ &\le 3a \sum_{x \in B} \left| \frac{1}{\sqrt{N}} f_N(x) \right| + a^2 \left| \text{supp } f_N \right| \\ &\le 3a \left| \text{supp } f_N \right|^{1/2} \left\| \frac{1}{N} L_N \right\|_1^{1/2} + a^2 \left| \text{supp } f_N \right| \\ &\le 3 \sqrt{\frac{2\lambda}{N}} cn^d + \frac{2\lambda}{N} cn^d \le 4 \sqrt{\frac{2c\lambda}{n^2}}, \end{aligned} $$

where the last inequalities come from the fact that, on the event $\mathcal{A}$, the range of the random walk has cardinality at most $cn^d$, and that $\lambda/n^2 = n^{\rho-2}$ goes to 0 as $n$ goes to $\infty$. Plugging the previous inequalities in inequality (5.46), we obtain that

$$ \left\| \tilde{h} - \frac{1}{N} L_N \right\|_1 \le \Gamma_3 + 4 \sqrt{\frac{2c\lambda}{n^2}}. $$

We conclude that, if $h \in C(g, N, r(N))$ and $f_N \in \mathcal{F}$, then $\tilde{h} \in V(\mathcal{F}, \Gamma_4, N)$, where

$$ \Gamma_4 = \Gamma_3 + 4 \sqrt{\frac{2c\lambda}{n^2}}, $$