# Fluctuation results for size of the vacant set for random walks on discrete
torus

Partha Dey  and  Daesung Kim  University of Illinois at Urbana Champaign, 1409
W Green Street, Urbana, Illinois 61801<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We consider one or more independent random walks on the $d\geqslant 3$
dimensional discrete torus. The walks start from vertices chosen independently
and uniformly at random. We analyze the fluctuation behavior of the size of
some random sets arising from the trajectories of the random walks at a time
proportional to the size of the torus. Examples include vacant sets and the
intersection of ranges. The proof relies on a refined analysis of tail
estimates for hitting time and can be applied for other vertex-transitive
graphs.

###### Key words and phrases:

Random Walk, Variance, Green’s function, Random interlacement.

###### 2010 Mathematics Subject Classification:

Primary: 60G50, 60F99.

##  1\. Introduction

Consider finitely many independent random walks on the $d\geqslant 3$
dimensional discrete torus with large side length, each starting from vertices
chosen independently and uniformly at random. We are interested in the mean
and fluctuation behavior of the size of some random sets arising from the
trajectories of the random walks at a time proportional to the size of the
torus. Examples include the vacant set or the set of vertices not visited by
any of the walks; the size of the intersection of ranges, among others.

In particular, we fix a positive integer $\ell\geqslant 1$, where $\ell$
denotes the number of independent random walks. The discrete torus is denoted
by $\mathds{Z}_{n}^{d}=(\mathds{Z}/n\mathds{Z})^{d}$, with side length $n$.
Note that $n$ controls the size of the graph and we are interested in the
large $n$ limit with a fixed $d$. We consider $\ell$ many independent
$\frac{1}{2}$–lazy random walks $(X_{t,i})_{t\geqslant
0},i\in[\ell]:=\\{1,2,\ldots,\ell\\}$ starting from
$X_{0,i}=\xi_{i},i\in[\ell]$, respectively, where $\xi_{i}$’s are i.i.d.
uniformly distributed over $\mathds{Z}_{n}^{d}$. We will use $\pi=\pi_{n}$ to
denote the uniform distribution over $\mathds{Z}_{n}^{d}$.

We define the range of the $i$-th random walk at time $t$ as

$\displaystyle\mathcal{R}_{i}(t):=\\{X_{s,i}\mid s=0,1,\ldots,t\\}\quad\text{
for }i=1,2,\ldots,\ell;$ (1)

the size of vacant set, _i.e.,_ the number of vertices not visited by any of
the $\ell$ walks at time $t$ as

$\displaystyle
V_{n}^{(\ell)}(t):=\left|\mathds{Z}_{n}^{d}\setminus\cup_{i=1}^{\ell}\mathcal{R}_{i}(t)\right|,$
(2)

and the size of the intersection of ranges at time $t$ as

$\displaystyle
R_{n}^{(\ell)}(t):=\left|\cap_{i=1}^{\ell}\mathcal{R}_{i}(t)\right|.$ (3)

If we define $\tau_{i}(v)$ as the hitting time at the vertex $v$ for the
$i$-th random walk, _i.e.,_

$\displaystyle\tau_{i}(v):=\min\\{t\geqslant 0\mid X_{t,i}=v\\},$

then we have for all $t\geqslant 0$

$\displaystyle
V_{n}^{(\ell)}(t)=\sum_{v\in\mathds{Z}_{n}^{d}}\prod_{i=1}^{\ell}\mathbf{1}_{\\{\tau_{i}(v)>t\\}}\text{
and
}R_{n}^{(\ell)}(t)=\sum_{v\in\mathds{Z}_{n}^{d}}\prod_{i=1}^{\ell}\mathbf{1}_{\\{\tau_{i}(v)\leqslant
t\\}}.$

One can easily check that

$\operatorname{\mathds{E}}V_{n}^{(\ell)}(t)=n^{d}\operatorname{\mathds{P}}_{\pi}(\tau_{1}(0)>t)^{\ell}\text{
and
}\operatorname{\mathds{E}}R_{n}^{(\ell)}(t)=n^{d}\operatorname{\mathds{P}}_{\pi}(\tau_{1}(0)\leqslant
t)^{\ell}.$

In particular when $t/n^{d}\to u$ we have
$n^{-d}\operatorname{\mathds{E}}V_{n}^{(\ell)}(t)\to e^{-\ell u/G(0)}$ and
$n^{-d}\operatorname{\mathds{E}}R_{n}^{(\ell)}(t)\to(1-e^{-u/G(0)})^{\ell}$ as
$n\to\infty$ where

$\displaystyle G(\xi)=G_{1/2}(\xi)$ $\displaystyle=\text{ expected number of
visits to $\xi$}$ $\displaystyle\qquad\text{ for a $1/2$\ndash lazy random
walk on $\mathds{Z}^{d}$ starting from }0.$

The above result follows from standard literature, for instance see
[BH91]*Equation (2.26), [AB92]*Theorem 1 or [TW2011]*Proposition 3.7.
Moreover, for an $\varepsilon$–lazy random walk, one can easily check that
$G_{\varepsilon}(\cdot)=(1-\varepsilon)^{-1}G_{\ast}(\cdot)$, where $G_{\ast}$
is the classical Green’s function for the simple random walk on
$\mathds{Z}^{d}$. If needed, we will use $G(0;\mathds{Z}^{d})$ instead of
$G(0)$ to emphasize the dependence on the dimension $d$.

For $\xi\in\mathds{Z}^{d}_{n}$, we define

$\displaystyle g_{n}(\xi)$
$\displaystyle:=\sum_{t=0}^{\infty}(\operatorname{\mathds{P}}_{0}(X_{t}=\xi)-\operatorname{\mathds{P}}_{\pi}(X_{t}=\xi))$
$\displaystyle\text{ and }g_{n}^{\prime}(\xi)$
$\displaystyle:=\sum_{t=1}^{\infty}t(\operatorname{\mathds{P}}_{0}(X_{t}=\xi)-\operatorname{\mathds{P}}_{\pi}(X_{t}=\xi)).$

Note that, heuristically $g_{n}(0)$ is the difference between the expected
number of visits to 0 by two $\frac{1}{2}$–lazy random walks on
$\mathds{Z}^{d}_{n}$ starting from the origin and the uniform distribution,
respectively, up to a large multiple of the mixing time. Moreover, for fixed
$\xi\in\mathds{Z}^{d}$, we have $g_{n}(\xi)\to G(\xi)$ as $n\to\infty$. One
can easily check that

$g^{\prime}_{n}(0)=\sum_{\xi\in\mathds{Z}^{d}_{n}}g_{n}(\xi)^{2}-g_{n}(0)>0.$

We remark that $g_{n}^{\prime}(0)$ stays bounded in $d\geqslant 5$ and
$g_{n}^{\prime}(0)$ grows at rate $\log n$ when $d=4$, and at rate $n$ when
$d=3$. See Lemma 2.1 for an upper bound on the growth rate of $g_{n}(\xi)$ and
$g_{n}^{\prime}(\xi)$. We write down the mean behavior with first order
correction in the following Lemma.

######  Lemma 1.1.

Let $d\geqslant 3$ and $\ell\geqslant 1$ be fixed. Define
$u:=(t+1)/n^{d}\in(0,\infty)$, then

$\displaystyle\operatorname{\mathds{E}}(V_{n}^{(\ell)}(t))=n^{d}e^{-\frac{\ell
u}{g_{n}(0)}}+\ell\left(\frac{ug_{n}^{\prime}(0)}{g_{n}(0)^{3}}+\frac{u}{2g_{n}(0)^{2}}-\frac{g^{\prime}_{n}(0)}{g_{n}(0)^{2}}\right)+O(n^{-d+3}).$

Our first main result is the following explicit variance for
$V_{n}^{(\ell)}(t)$. Define

$\displaystyle\sigma_{n,\ell}^{2}(t):=\operatorname{Var}(V_{n}^{(\ell)}(t)).$
(4)

######  Theorem 1.2.

Let $d\geqslant 5$ and $\ell\geqslant 1$ be fixed. Assume that $t/n^{d}\to
u\in(0,\infty)$. There exists a function $\nu_{d}:(0,\infty)\to(0,\infty)$
such that

$\displaystyle\lim_{n\to\infty}\frac{1}{n^{d}}\sigma_{n,\ell}^{2}(t)=\nu_{d}(2\ell
u/G(0)).$

Moreover, we have an explicit formula for $\nu_{d}(u)$ given by

$\displaystyle\nu_{d}(u)=e^{-u}\sum_{\xi\in\mathds{Z}^{d}}\left(\exp\left(\frac{uG(\xi)}{G(0)+G(\xi)}\right)-1-\frac{uG(\xi)}{G(0)+G(\xi)}+\frac{uG(\xi)^{2}(G(\xi)-\mathds{1}_{\\{\xi=0\\}})}{G(0)^{2}(G(0)+G(\xi))}\right).$
(5)

Note that the limiting variance in (5) is strictly positive as
$e^{x}-1-x\geqslant x^{2}/2>0$ for $x>0$ and $G(0)>1$. Also, it is finite as
$\sum_{\xi\in\mathds{Z}^{d}}G(\xi)^{2}<\infty$ for $d\geqslant 5$.

One can see from the proof of Theorem 1.2 that $n^{-d}\sigma_{n,\ell}^{2}(t)$
is governed by $\sum_{\xi\in\mathds{Z}^{d}_{n}}g_{n}(\xi)^{2}$. This sum can
be written as $g_{n}^{\prime}(0)+g_{n}(0)$, whose growth rate is

$h_{d}(n):=\begin{cases}n&\text{ when }d=3,\\\ \log n&\text{ when }d=4\text{
and},\\\ 1&\text{ when }d\geqslant 5.\end{cases}$

Thus, it is expected that the correct scaling order for the variance is
$n^{4}$ when $d=3$ and $n^{4}\log n$ when $d=4$, and heuristically the
variance with right scaling converges to the sum of the second order term of
the exponential in (5). The following theorem affirms that this is indeed the
case.

######  Theorem 1.3.

Let $d\in\\{3,4\\}$ and $\ell\geqslant 1$ be fixed. Assume that $t/n^{d}\to
u\in(0,\infty)$. Then we have

$\displaystyle\lim_{n\to\infty}\frac{1}{n^{d}h_{d}(n)}\sigma_{n,\ell}^{2}(t)=\nu_{d}(2\ell
u/G(0)).$

where $h_{3}(n)=n$, $h_{4}(n)=\log n$,

$\displaystyle\nu_{d}(u)=\frac{1}{2}\alpha_{d}u^{2}e^{-u},$ (6)

and

$\displaystyle\alpha_{3}:=\frac{9}{\pi^{4}\cdot
G(0;\mathds{Z}^{3})^{2}}\sum_{v\in\mathds{Z}^{3}}\left\|v\right\|^{-4},\quad\alpha_{4}:=\frac{16}{\pi^{4}\cdot
G(0;\mathds{Z}^{4})^{2}}\lim_{n\to\infty}\frac{1}{\log n}\sum_{\|v\|\leqslant
n}\|v\|^{-4}.$

One can quickly check that the limit in $\alpha_{4}$ exists and is finite.
Note that this constant also appears in the fluctuation behavior for competing
random walks in [Miller2013a].

######  Remark 1.4.

One can extend the fluctuation behavior of the vacant set from discrete-time
random walks to continuous-time random walks. Let $(T(s))_{s\geqslant 0}$ be a
Poisson process with intensity 1, independent of $X_{t}$. Let $Y_{s}=X_{T(s)}$
and $\widetilde{V}_{n}^{(\ell)}(t)$ be the vacant set of $Y_{s}$ up to time
$t$. Then, the variance of $\widetilde{V}_{n}^{(\ell)}(t)$ can be computed via
conditioning with Lemma 1.1 and Theorems 1.2, 1.3. Indeed, it follows that

$\displaystyle\operatorname{Var}(\widetilde{V}_{n}^{(\ell)}(t))=\operatorname{\mathds{E}}(\operatorname{Var}(\widetilde{V}_{n}^{(\ell)}(t)\mid
T(t)=s))+\operatorname{Var}(\operatorname{\mathds{E}}(\widetilde{V}_{n}^{(\ell)}(t)\mid
T(t)=s)),$

for $t\approx un^{d}$. Then, we apply the fluctuation results for
$V_{n}^{(\ell)}(s)$.

######  Remark 1.5.

We remark that the order of the variance $\sigma_{n,\ell}^{2}(t)$ at $t\approx
un^{d}$ is the same as that of the variance for competing random walks in
[Miller2013a]. Unlike our proof, which relies on an elementary and analytic
approach using the generating function of hitting probabilities, Miller
[Miller2013a] made use of the conditioning argument at the mixing time to
obtain the cancellation in the expansion of the variance, which leads to the
precise asymptotic for the variance. It would be interesting to get a
probabilistic proof and interpretation of our results on the asymptotic of the
variance $\sigma_{n,\ell}^{2}(t)$.

We can generalize the above result to the size of the intersection of ranges
and similar sets in the following way. For any subset $I\subseteq[\ell]$, we
define

$\displaystyle R_{n,\ell}^{I}(t):=\sum_{v\in\mathds{Z}^{d}_{n}}\prod_{i\in
I}\mathbf{1}_{\\{\tau_{i}(v)\leqslant t\\}}\prod_{j\in
I^{c}}\mathbf{1}_{\\{\tau_{j}(v)>t\\}}$

as the number of vertices in $\mathds{Z}_{n}^{d}$ that are visited by walks
indexed by $I$ but not by walks indexed by $[\ell]\setminus I$ at time $t$. We
define the random vector indexed by $I\subseteq[\ell]$

$\boldsymbol{R}_{n,\ell}(t):=(R_{n,\ell}^{I}(t))_{I\subseteq[\ell]}.$

Note that $R_{n,\ell}^{\emptyset}(t)=V_{n}^{(\ell)}(t)$ and
$R_{n}^{[\ell]}(t)=R_{n}^{(\ell)}(t)$ as defined in (2) and (3). We can
compute the variance-covariance structure for the random vector
$\boldsymbol{R}_{n,\ell}(t)$ when $t\approx un^{d}$.

######  Theorem 1.6.

For $I,J\subseteq[\ell]$ and $t/n^{d}\to u\in(0,\infty)$, we have

$\displaystyle\lim_{n\to\infty}\frac{1}{n^{d}h_{d}(n)}\operatorname{Cov}(R_{n,\ell}^{I}(t),R_{n,\ell}^{J}(t))$
$\displaystyle\qquad=\sum_{m=0}^{\left|I\cup
J\right|}\theta_{k,r,m}(\exp(-u/G(0)))\cdot\nu_{d}(2(\ell-m)u/G(0))$

where $k=\left|I\cap J\right|,r=\left|I\Delta J\right|$, $\nu_{d}(\cdot)$ is
as given by (5)–(6), and

$\displaystyle\theta_{k,r,m}(a):=\sum_{j=(m-k)_{+}}^{r\wedge
m}\binom{k}{m-j}\binom{r}{j}(1-2a)^{m-j}(-1)^{r-j}a^{j}.$

######  Remark 1.7.

Under suitable assumptions, our analysis could be applied to general vertex-
transitive graphs with $g_{n}(0)$ bounded above. In particular, we consider
the vacant set of an $\varepsilon$–lazy random walk on the hyper-cube
$\mathds{Z}_{2}^{n}$. Since we have explicit formulas for the Green’s
function, the eigenvalues, and the eigenfunctions as in [ChungYau200a]*Section
7, we can apply our method to obtain the fluctuation behavior of the vacant
set as $n\to\infty$. Suppose $\xi\in\mathds{Z}^{n}_{2}$ belongs to the $k$-th
level for $0\leqslant k\leqslant n$, then the Green’s function is given by

$\displaystyle g_{n}(\xi)$
$\displaystyle=\frac{1}{(1-\varepsilon)2^{n}}\sum_{v\in\mathds{Z}^{n}_{2},v\neq
0}\frac{n}{\left\|v\right\|_{1}}\cdot(-1)^{\langle v,\xi\rangle}$
$\displaystyle=\frac{1}{(1-\varepsilon)2^{n}}\left(\sum_{i=1}^{n}\frac{n}{i}\binom{n}{i}-2\sum_{i=1}^{k}\frac{1}{\binom{n-1}{i-1}}\sum_{j=i}^{n}\binom{n}{j}\right)$

see [Beveridge2016a]*Section 4 and [ChungYau200a]*Example 4. In particular,
$g_{n}(0)\to 2/(1-\varepsilon)$ as $n\to\infty$. Similarly, using the spectral
representation one can compute that $g^{\prime}_{n}(0)\to
4/(1-\varepsilon)^{2}-2/(1-\varepsilon)$. Thus,
$\sum_{\xi\in\mathds{Z}_{2}^{n}}g_{n}(\xi)^{2}-g_{n}(0)^{2}\to 0$. Then, when
$t/2^{n}\to u$, the variance of the size of the vacant set $V_{n}^{(\ell)}(t)$
is of order $2^{n}$ and

$2^{-n}\operatorname{Var}(V_{n}^{(\ell)}(t))\to\nu((1-\varepsilon)\ell
u)\text{ with }\nu(x)=e^{-x}(e^{x/2}-1-(1-\varepsilon)x/4).$

One might need to verify the detail somewhere else for other vertex-transitive
graphs such as the Cayley graph of the symmetric group $S_{n}$.

The first step in the proof of Theorem 1.2 and 1.3 is the following
simplification, which follows from the transitivity of the graph and
independence of the random walks:

$\displaystyle\operatorname{Var}(V_{n}^{(\ell)}(t))$
$\displaystyle=n^{d}\sum_{\xi\in\mathds{Z}_{n}^{d}}\left(\operatorname{\mathds{P}}(\tau(0,\xi)>t)^{\ell}-\operatorname{\mathds{P}}(\tau(0)>t)^{2\ell}\right)$
(7)

where

$\displaystyle\tau(0,\xi):=\inf\\{t\geqslant 0:X_{t}\in\\{0,\xi\\}\\}$

is the hitting time of the set $\\{0,\xi\\}$ for the random walk $X_{t}$. In
particular, we need a precise estimate of the tail behavior for the hitting
time.

######  Lemma 1.8.

For $d\geqslant 3$, $\xi\in\mathds{Z}^{d}_{n}$, and
$u=(t+1)/n^{d}\in(0,\infty)$, we have

$\displaystyle\operatorname{\mathds{P}}_{\pi}(\tau(0,\xi)>t)$
$\displaystyle=e^{-\frac{u}{f_{n}(\xi)}}\left(1+\frac{u}{n^{d}}\left(\frac{f^{\prime}_{n}(\xi)}{f_{n}(\xi)^{3}}+\frac{1}{2f_{n}(\xi)^{2}}\right)-\frac{f_{n}^{\prime}(\xi)}{n^{d}f_{n}(\xi)^{2}}\right)$
$\displaystyle\qquad\qquad+O(n^{-2d+3})$

where

$\displaystyle f_{n}(\xi):=\frac{1}{2}(g_{n}(0)+g_{n}(\xi)),\quad
f_{n}^{\prime}(\xi):=\frac{1}{2}(g_{n}^{\prime}(0)+g_{n}^{\prime}(\xi)).$ (8)

######  Remark 1.9.

It is easy to check that $0\leqslant f^{\prime}_{n}(\xi)\leqslant
f^{\prime}_{n}(0)$ for all $\xi$ using the spectral representation (12).
Moreover, $n^{-d}\sum_{\xi}f^{\prime}_{n}(\xi)=\frac{1}{2}f^{\prime}_{n}(0).$

###  1.1. Related Literature

We first review the relevant literature on the range of simple random walks on
the square lattice $\mathds{Z}^{d}$. Dvoretzky and Erdös [DE51] proved the
strong law of large numbers for the range on $\mathds{Z}^{d}$ for $d\geqslant
2$. A central limit theorem was obtained by Jain and Orey [JO68]. They showed
that for strongly transient random walks, the variance of the range up to time
$t$ is of order $t$, and the range with a suitable normalization converges to
normal distribution. Note that a simple random walk on $\mathds{Z}^{d}$ is
strongly transient if and only if $d\geqslant 5$. Later, Jain and Pruitt
[JP70clt] considered the general transient case. It was shown in [JP70clt]
that the variance of the range up to time $t$ is of order $t$ if $d=4$, and
$t\log t$ if $d=3$, and that the central limit theorem holds for $d=3,4$. The
recurrent case ($d=2$) was studied by Le Gall [LeGall], who proved that if
$\mathcal{R}_{t}$ is the range up to time $t$, then
$(\mathcal{R}_{t}-\operatorname{\mathds{E}}(\mathcal{R}_{t}))/(t(\log
t)^{-2})$ converges to the intersection local time of a planar Brownian
motion, which is a non-Gaussian distribution.

There have been efforts to study the capacity of the range of random walks on
$\mathds{Z}^{d}$. For a finite set $A\subset\mathds{Z}^{d}$ in $d\geqslant 3$,
the capacity of $A$ is defined by the probability that a simple random walk
starting from $A$ never returns to $A$. Jain and Orey [JO68] showed the law of
large numbers for the capacity of the range of a simple random walk when
$d\geqslant 5$. Later, Chang [Chang17] extended the result for $d=3,4$.
Furthermore, it was shown in [Chang17] that when $d=3$, the capacity of the
range converges to that of Brownian motion. Recently, Asselar, Schapira, and
Sousi [ASS18zd, ASS19z4] derived the central limit theorems for the capacity
of the range when $d\geqslant 6$ and $d=4$.

Sznitman [Sznitman2010] introduced the random interlacement model to study the
trace left by a simple random walk in a discrete torus $\mathds{Z}^{d}_{n}$
for a time $n^{d}$. The random interlacement at level $u$, denoted by
$\mathcal{I}^{u}$, can be constructed via a Poisson point process on the set
of doubly infinite nearest neighbor paths on $\mathds{Z}^{d}$ with intensity
measure given in terms of the Newtonian capacity. The model provides the local
picture of the trace left by a simple random walk in a discrete torus.

One of the applications of the random interlacement model is to investigate
the percolative properties of the vacant set on $\mathds{Z}^{d}_{n}$ up to
time proportional to the size of the discrete torus. It was shown in
[Sznitman2010] that there exists a critical $u_{\ast}$ such that the vacant
set does not percolate for large $u>u_{\ast}$ when $d\geqslant 3$, and
percolates for small $u<u_{\ast}$ when $d\geqslant 7$. Later, Teixeira and
Windisch [TW2011] showed that if $u>0$ is large enough, then the volumes of
all the components of the vacant set are of order $(\log n)^{\lambda(u)}$ and
if $u>0$ is small enough then there exists a macroscopic component. They also
proved that if $d\geqslant 5$, the macroscopic component is unique in the
small $u$ regime. The proofs of these results are based on couplings of a
simple random walk on $\mathds{Z}^{d}$ with the random interlacement.

Unlike the percolation of the vacant set, the fluctuation of the size of the
vacant set does not have any threshold at the time level $u$. This is because
the local behavior of the random walk is crucial in the study of the
percolative property. At the same time, the variance of the size of the vacant
set depends on both global and local pictures.

The random interlacement captures the local behavior of a simple random walk
on the discrete torus, in a sense that one can be approximated by the other as
$n\to\infty$ in a box of size smaller order than the size of the torus.
Consider the vacant set left by the random interlacement $\mathcal{I}^{u}$ in
a box $[-n/2,n/2)^{d}$, say
$W^{u}_{n}:=[-n/2,n/2)^{d}\setminus\mathcal{I}^{u}$. Since
$\operatorname{\mathds{P}}(\\{x,y\\}\subset
W^{u}_{n})=\exp(-2u/(G_{\ast}(0)+G_{\ast}(x-y)))$ where $G_{\ast}(x)$ is the
Green’s function for $\mathds{Z}^{d}$, the variance of the vacant set
$W^{u}_{n}$ can be computed as

$\displaystyle\operatorname{Var}(W^{u}_{n})=n^{d}\sum_{\xi\in[-\frac{n}{2},\frac{n}{2})^{d}}\left(e^{-\frac{2u}{G_{\ast}(0)+G_{\ast}(\xi)}}-e^{-\frac{2u}{G_{\ast}(0)}}\right)+o(1).$

Note that the sum in the right-hand side does not converge as $n\to\infty$ for
$d\geqslant 3$, while the sum in (5) does. Compared to Theorem 1.2, one can
see that the contribution from the global fluctuation matters in the variance
computation of the vacant set $V^{(l)}_{n}(t)$.

The vacant set $\mathcal{V}_{n}(t)$ at a time of order $n^{d}\log n^{d}$ was
studied in [Al91, Bel, MS17]. The cover time $\tau_{\mathrm{cov}}$ is the
maximum of the hitting times $\tau(\xi)$ over $\xi\in\mathds{Z}^{d}_{n}$. Let
$t_{\mathrm{cov}}=\max_{x}\operatorname{\mathds{E}}_{x}[\tau_{\mathrm{cov}}]$.
It is well-known that $t_{\mathrm{cov}}=C_{d}n^{d}\log n^{d}(1+o(1))$ as
$n\to\infty$. Belius [Bel] proved that the fluctuations of
$\tau_{\mathrm{cov}}$ are governed by the Gumbel distribution, in a sense that
$\tau_{\mathrm{cov}}/(C_{d}n^{d})-\log n^{d}$ converges to Gumbel in law as
$n\to\infty$ for $d\geqslant 3$. He also showed that the scaling limit of the
vacant set up to time $C_{d}n^{d}\log n^{d}$ as a set-valued process in
$(\mathds{R}/\mathds{Z})^{d}$ is indeed a Poisson point process.
Heuristically, the Gumbel fluctuation of the cover time implies that, at a
time of order $n^{d}\log n^{d}$, the hitting times $\tau(\xi)$,
$\xi\in\mathds{Z}^{d}_{n}$, are approximately almost exponential and
independent. A natural question is the limiting behavior of the vacant set
$\mathcal{V}_{n}(t)$ at a time $t=\alpha t_{\mathrm{cov}}(1+o(1))$ for
$\alpha>0$. Miller and Sousi [MS17] showed that there are two thresholds
$\alpha_{0}(d)<\alpha_{1}(d)$ such that $\mathcal{V}_{n}(t)$ is approximately
Bernoulli random variable indexed by $\mathds{Z}^{d}_{n}$ if
$\alpha>\alpha_{1}(d)$, and the total variation distance between
$\mathcal{V}_{n}(t)$ and Bernoulli random variable is 1 if
$\alpha<\alpha_{0}(d)$.

Miller [Miller2013a] investigated the fluctuation behavior of the trace by
competing random walks. Consider $\ell$ independent simple random walks
$(X_{t,i})$, $i\in[\ell]$, on $\mathds{Z}^{d}_{n}$. We assume that each site
$\xi$ is painted by $i$ irreversibly at time $t$ if $X_{t,i}=\xi$. Let
$\mathcal{A}_{i}(t)$ be the set of sites painted by $i$ up to time $t$. Miller
[Miller2013a] computed the limiting behavior of the variance of
$\left|\mathcal{A}_{i}(\infty)\right|$ for $d\geqslant 3$ and $\ell=2$.
Indeed, it was shown that the order of the variance of
$\left|\mathcal{A}_{i}(\infty)\right|$ has the same order as the sum of
squares of the $\mathds{Z}^{d}$ Green’s function, which coincides with our
fluctuation behavior. He also extended the result to vertex-transitive graphs
with some assumptions on the mixing time and provided precise limits of the
variances for the hypercube and the Cayley graph of $S_{n}$ as a corollary.

###  1.2. Roadmap

The article is structured as follows. In Section 2 we provide notations,
background details, and preliminary results for the later analysis. Section 3
contains the proof for accurately computing coefficients from specific
functions of a power series, which will play a crucial role in estimating the
upper tail behavior for the hitting time of two-point sets. We provide proof
of auxiliary results in Section 4 and proof of the main theorems in Section 5.
Finally, we conclude with a discussion and list of open problems in Section 6.

##  2\. Preliminaries

###  2.1. Notations and Conventions

For the rest of the article we use $X_{t}$ and $S_{t}$ for $\frac{1}{2}$–lazy
random walks on $\mathds{Z}^{d}_{n}$ and $\mathds{Z}^{d}$, respectively. We
explicitly write the dependence on $n,d$ when needed. For a set
$A\subseteq\mathds{Z}_{n}^{d}$, the hitting time for $A$ is denoted by

$\tau(A):=\inf\\{t\geqslant 0:X_{t}\in A\\}.$

We will add extra subscript $i$ when working with the $i$–th lazy random walk.
If $A=\\{x\\}$ or $A=\\{x,y\\}$, we simply write $\tau(x)$ and $\tau(x,y)$,
instead of $\tau(A)$. Let $\operatorname{\mathds{P}}$ and
$\operatorname{\mathds{E}}$ be the probability and the expectation of $X_{t}$
starting from the uniform distribution $\pi_{n}$ on $\mathds{Z}_{n}^{d}$. We
will use $\operatorname{\mathds{P}}_{\xi}$ and
$\operatorname{\mathds{E}}_{\xi}$ to denote the probability and the
expectation of $X_{t}$ starting from $X_{0}=\xi$. For
$v=(v_{1},v_{2},\cdots,v_{d})$ in $\mathds{Z}^{d}_{n}$ and $p\in[1,\infty)$,
we use the notation

$\left\|v\right\|_{p}:=\bigl{(}|v_{1}|^{p}\wedge(n-|v_{1}|)^{p}+|v_{2}|^{p}\wedge(n-|v_{2}|)^{p}+\cdots+|v_{d}|^{p}\wedge(n-|v_{d}|)^{p}\bigr{)}^{1/p}.$

For simplicity, we drop the subscript $p$ when $p=2$, that is,
$\left\|v\right\|=\left\|v\right\|_{2}$.

We will write $a_{n}\lesssim b_{n}$, when there exists a finite positive
constant $c$ such that $a_{n}\leqslant cb_{n}$ for all $n$. Similarly, we will
use $a_{n}\simeq b_{n}$, when $a_{n}\lesssim b_{n}$ and $b_{n}\lesssim a_{n}$.
We will also use $a_{n}=O(b_{n})$ or $b_{n}=\Omega(a_{n})$ for $a_{n}\lesssim
b_{n}$ and $a_{n}=\Theta(b_{n})$ for $a_{n}\simeq b_{n}$.

###  2.2. Green’s Function

We recall the Green’s functions and their basic properties on $\mathds{Z}^{d}$
and $\mathds{Z}^{d}_{n}$. For further detail, we refer [ChungYau200a]*Section
7 for the discrete torus, and [Lawler, LawlerLimic] for the lattice. The
Green’s function on $\mathds{Z}^{d}_{n}$ for a $\frac{1}{2}$–lazy simple
random walk is defined by

$\displaystyle
g_{n}(\xi,\eta)=\sum_{t=0}^{\infty}(\operatorname{\mathds{P}}_{\xi}(X_{t}=\eta)-\pi(\eta)).$
(9)

For simplicity, we use the notation $g_{n}(\xi):=g_{n}(0,\xi)$ and drop the
subscript $n$ when there is no ambiguity. For a $\frac{1}{2}$–lazy simple
random walk $S_{t}$ on $\mathds{Z}^{d}$, the Green’s function $G(\xi,\eta)$ is
the expected number of visit to $\eta$ from $\xi$,

$\displaystyle
G(\xi,\eta)=\operatorname{\mathds{E}}_{\xi}\left(\sum_{t=0}^{\infty}\mathbf{1}_{\\{X_{t}=\eta\\}}\right)=\sum_{t=0}^{\infty}\operatorname{\mathds{P}}_{\xi}(X_{t}=\eta).$

Let $G(\xi):=G(0,\xi)$.

The Green’s function has the following spectral representation. The Laplacian
matrix for the random walk is given by
$\Delta_{n}=I-P_{n}=\frac{1}{2}(I-\frac{1}{2d}A_{n})$ where $A_{n}$ is the
adjacency matrix of $\mathds{Z}^{d}_{n}$, that is, $A_{n}(\xi,\eta)=1$ if
$\xi$ is a neighbor of $\eta$ for $\xi,\eta\in\mathds{Z}^{d}_{n}$, and
otherwise 0. Let $e_{n}(x):=\exp(2\pi ix/n)$, for $x\in\mathds{R}$. It is
well-known that

$\displaystyle\varphi_{v}(\xi)=n^{-\frac{d}{2}}e_{n}(\langle
v,\xi\rangle),\quad\xi\in\mathds{Z}^{d}_{n}$ (10)

for $v\in\mathds{Z}^{d}_{n}$ gives a complete set of orthonormal
eigenfunctions for $\Delta_{n}$ with the corresponding eigenvalues

$\displaystyle\lambda_{v}:=\frac{1}{2}\biggl{(}1-\frac{1}{d}\sum_{j=1}^{d}\cos\bigl{(}2\pi
v_{j}/n\bigr{)}\biggr{)}=\frac{1}{d}\sum_{j=1}^{d}\sin^{2}(\pi
v_{j}/n)\in[0,1].$ (11)

In particular, $\Delta_{n}$ is diagonalizable and

$\displaystyle\Delta_{n}(\xi,\eta)=\sum_{v\in\mathds{Z}_{n}^{d}}\lambda_{v}\varphi_{v}(\xi)\overline{\varphi_{v}(\eta)}\quad\text{
for }\xi,\eta\in\mathds{Z}_{n}^{d}$

where $\bar{z}$ denotes the complex conjugate of $z\in\mathds{C}$. Then, the
Green’s function can be written as

$\displaystyle
g_{n}(\xi,\eta)=\sum_{v\in\mathds{Z}^{d}_{n}\setminus\\{0\\}}\frac{1}{\lambda_{v}}\varphi_{v}(\xi)\overline{\varphi_{v}(\eta)}=n^{-d}\sum_{v\in\mathds{Z}^{d}_{n}\setminus\\{0\\}}\frac{1}{\lambda_{v}}e_{n}(\langle\xi-\eta,v\rangle).$
(12)

Using the spectral representation, one can see that the Green’s function
$G(\xi)$ for $\mathds{Z}^{d}$ ($d\geqslant 3$) is the limit of $g_{n}(\xi)$ as
$n\to\infty$. Indeed, we have

$\displaystyle
G(\xi)=\lim_{n\to\infty}g_{n}(\xi)=\int_{[0,1]^{d}}\frac{d}{\sum_{j=1}^{d}\sin^{2}(\pi
x_{j})}e^{2\pi i\xi\cdot x}\,dx\text{ for all }\xi\in\mathds{Z}^{d}.$

Let $\varphi_{d}(x):=\frac{d}{\sum_{j=1}^{d}\sin^{2}(\pi x_{j})}$ for
$x\in[0,1]^{d}$, then $G(\xi)$ is the Fourier transform of $\varphi$. By
Plancherel’s identity ([Grafakos]*Proposition 3.1.16), if $d\geqslant 5$ then

$\displaystyle\int_{[0,1]^{d}}\varphi_{d}(x)^{2}\,dx=\sum_{\xi\in\mathds{Z}^{d}}G(\xi)^{2}.$

This fact will be used in the proof of the main results (see (20)).

###  2.3. Generating Function

The Green’s generating function for the torus is defined by

$\displaystyle
g_{n}(\xi,\eta;z):=\sum_{t=0}^{\infty}\left(\operatorname{\mathds{P}}_{\xi}(X_{t}=\eta)-\pi(\eta)\right)z^{t}\text{
for }z\in\mathds{C},\left|z\right|<1.$ (13)

For simplicity, we use $g_{n}(\xi;z)=g_{n}(0,\xi;z)$ and drop the subscript
$n$ if there is no ambiguity. Note that the spectral representation provides

$\displaystyle
g_{n}(\xi,\eta;z)=\sum_{v\in\mathds{Z}^{d}_{n}\setminus\\{0\\}}\frac{1}{1-z\widehat{\lambda}_{v}}\varphi_{v}(\xi)\overline{\varphi_{v}(\eta)}=n^{-d}\sum_{v\in\mathds{Z}^{d}_{n}\setminus\\{0\\}}\frac{e_{n}(\langle\xi-\eta,v\rangle)}{1-z\widehat{\lambda}_{v}}$
(14)

where $\widehat{\lambda}_{v}:=1-\lambda_{v}$. Also note that $g_{n}(\xi;z)$ is
defined for $z\notin\\{\widehat{\lambda}_{v}^{-1}\mid
v\in\mathds{Z}_{n}^{d}\setminus\\{0\\}\\}$ and $g_{n}(\xi)=g_{n}(\xi;1)$.
Moreover, the Green’s generating function defined in (13) satisfies

$\displaystyle\sum_{\xi\in\mathds{Z}_{n}^{d}}g_{n}(\xi;z)=0\text{ for all }z.$

Let

$\displaystyle g_{n}^{\prime}(\xi;1):=\frac{d}{dz}g_{n}(\xi;z)\Big{|}_{z=1}$
$\displaystyle=\sum_{t=0}^{\infty}t\left(\operatorname{\mathds{P}}_{\xi}(X_{t}=\eta)-\pi(\eta)\right)$
$\displaystyle=n^{-d}\sum_{v\in\mathds{Z}_{n}^{d}\setminus\\{0\\}}(1-\lambda_{v})\lambda_{v}^{-2}e_{n}(\langle\xi,v\rangle).$

We simply denote by $g_{n}^{\prime}(\xi)=g_{n}^{\prime}(\xi;1)$. One can
easily check that

$\displaystyle\sum_{\xi\in\mathds{Z}_{n}^{d}}g_{n}(\xi)^{2}=n^{-d}\sum_{v\in\mathds{Z}_{n}^{d}\setminus\\{0\\}}\lambda_{v}^{-2}=g_{n}(0)+g_{n}^{\prime}(0).$

For $\xi\in\mathds{Z}^{d}$ and $z\in\mathds{C}$ with $\left|z\right|<1$, we
define
$G^{\prime}(\xi;z)=\sum_{t=0}^{\infty}z^{t}\operatorname{\mathds{P}}_{0}(S_{t}=\xi)$
and

$\displaystyle
G^{\prime}(\xi)=\frac{d}{dz}G(\xi;z)|_{z=1}=\sum_{t=0}^{\infty}t\operatorname{\mathds{P}}_{0}(S_{t}=\xi)>0$

where $S_{t}$ is a $\frac{1}{2}$–lazy simple random walk on $\mathds{Z}^{d}$.
Note that $\lim_{n\to\infty}g_{n}^{\prime}(\xi)=G^{\prime}(\xi)$ for each
$\xi\in\mathds{Z}^{d}$ when $d\geqslant 5$. The Green’s generating function
has a probabilistic interpretation. Consider two independence
$\frac{1}{2}$–lazy simple random walks on $\mathds{Z}^{d}$, $S_{t,1}$ and
$S_{t,2}$ starting at $0$ and $\xi$ respectively. Then,
$\operatorname{\mathds{E}}\left|\\{(s,t)\mid S_{s,1}=S_{t,2}\\}\right|$,
expected size of the intersection of two random walk trajectories (counted
with multiplicities), can be written as

$\displaystyle\sum_{v\in\mathds{Z}^{d}}G(v)G(v-\xi)$
$\displaystyle=\sum_{t,s=0}^{\infty}\operatorname{\mathds{P}}_{0,\xi}(S_{t,1}=S_{s,2})$
$\displaystyle=\sum_{t,s=0}^{\infty}\sum_{v\in\mathds{Z}^{d}}\operatorname{\mathds{P}}_{0}(S_{t,1}=v)\operatorname{\mathds{P}}_{\xi}(S_{s,2}=v)$
$\displaystyle=\sum_{t,s=0}^{\infty}\operatorname{\mathds{P}}_{0}(S_{t+s}=\xi)=\sum_{t=0}^{\infty}(t+1)\operatorname{\mathds{P}}_{0}(S_{t}=\xi)=G(\xi)+G^{\prime}(\xi).$
(15)

In this paper, the main results are given in terms of the Green’s function $G$
for a $\frac{1}{2}$–lazy random walk on $\mathds{Z}^{d}$. If needed, one can
replace $G$ with the standard Green’s function $G_{\ast}$ with minor
modification. If $G_{\varepsilon}(\xi)$ is the Green’s function for the
$\varepsilon$–lazy random walk on $\mathds{Z}^{d}$, $\varepsilon\in(0,1)$,
then one can see that

$\displaystyle
G_{\varepsilon}(\xi)=\frac{1}{1-\varepsilon}G_{\ast}(\xi),\qquad
G_{\varepsilon}^{\prime}(\xi)=\frac{\varepsilon}{(1-\varepsilon)^{2}}G_{\ast}(\xi)+\frac{1}{(1-\varepsilon)^{2}}G_{\ast}^{\prime}(\xi).$

In particular, we have $G(\xi)=2G_{\ast}(\xi)$ and
$G^{\prime}(\xi)=2G_{\ast}(\xi)+4G_{\ast}^{\prime}(\xi)$.

The following Lemma 2.1 will be used to compute the growth rate of
$g_{n}^{\prime}(0)$ depending on $n$ and the dimension $d$ by taking $k=2$.

######  Lemma 2.1.

For $k\geqslant 1$, we have

$\displaystyle\frac{1}{n^{d}}\sum_{v\in\mathds{Z}_{n}^{d}\setminus\\{0\\}}\lambda_{v}^{-k}\simeq\begin{cases}1&\text{
if }d>2k\\\ \log n&\text{ if }d=2k\\\ n^{2k-d}&\text{ otherwise}.\end{cases}$

As a direct consequence, we have

$\displaystyle\frac{d^{k}}{dz^{k}}g_{n}(0;z)\biggl{|}_{z=1}\simeq\begin{cases}1&\text{
if }d>2k+2\\\ \log n&\text{ if }d=2k+2\\\ n^{2k+2-d}&\text{
otherwise}.\end{cases}$

###### Proof.

From (11), it is easy to see that
$\lambda_{v}\simeq\left\|v\right\|^{2}/(dn^{2})$. Thus, we have

$\displaystyle\sum_{v\in\mathds{Z}_{n}^{d}\setminus\\{0\\}}\lambda_{v}^{-k}\simeq
n^{2k}\sum_{v\in\mathds{Z}_{n}^{d}\setminus\\{0\\}}\left\|v\right\|^{-2k}\simeq
n^{2k}\sum_{r=1}^{n}r^{-2k}r^{d-1}\simeq\begin{cases}n^{d}&\text{ if }d>2k\\\
n^{d}\log n&\text{ if }d=2k\\\ n^{2k}&\text{ otherwise}.\end{cases}$

The second assertion follows from the fact that

$\displaystyle\frac{d^{k}}{dz^{k}}g_{n}(0;z)\biggl{|}_{z=1}=\frac{k!}{n^{d}}\sum_{v\in\mathds{Z}_{n}^{d}\setminus\\{0\\}}\lambda_{v}^{-(k+1)}(1-\lambda_{v})^{k}$

and this completes the proof. $\blacksquare$

The next Lemma 2.2 tells us that $g_{n}(\xi)$ and $g^{\prime}_{n}(\xi)$
converge to 0 as $\left\|\xi\right\|$ becomes large, uniformly in $n$, which
will be frequently used in the proofs of the main results. The proof is given
in Section 4.

######  Lemma 2.2.

We have

$\displaystyle g_{n}(\xi)$
$\displaystyle=O(n^{-\min\\{d-2,2\\}}+(1+\left\|\xi\right\|)^{-\min\\{d-2,(d+2)/2\\}})\quad\text{
for }d\geqslant 3,$ $\displaystyle g^{\prime}_{n}(\xi)$
$\displaystyle=O(n^{-\min\\{d-4,(d-2)/2\\}}+(1+\left\|\xi\right\|)^{-\min\\{d-4,d/2\\}})\quad\text{
for }d\geqslant 5$

uniformly in $n,\xi\in\mathds{Z}_{n}^{d}$.

Let

$\displaystyle f_{n}(\xi;z)$
$\displaystyle:=\frac{1}{2}(g_{n}(0;z)+g_{n}(\xi;z))\qquad\text{ and }\qquad
f_{n}(\xi):=f_{n}(\xi;1).$ (16)

The generating function for $\operatorname{\mathds{P}}(\tau(0,\xi)>t)$ can be
expressed in terms of the function $f_{n}(\xi;z)$ as follows (see [BH91]).

######  Lemma 2.3.

For $\left|z\right|<1$ and $\xi\in\mathds{Z}_{n}^{d}$, we have

$\displaystyle\sum_{t=0}^{\infty}z^{t}\operatorname{\mathds{P}}(\tau(0,\xi)>t)=\frac{f_{n}(\xi;z)}{n^{-d}+(1-z)f_{n}(\xi;z)}.$
(17)

From Lemma 2.3, finding a precise estimate on the hitting probability
$\operatorname{\mathds{P}}(\tau(0,\xi)>t)$, boils down to a refined analysis
on the coefficients of the series expansion of the function on the right-hand
side in (17). We investigate the series expansion of such functions in Section
3. We give a proof of Lemma 2.3 for completeness.

###### Proof of Lemma 2.3.

Suppose $\xi\in\mathds{Z}^{d}_{n}\setminus\\{0\\}$ and $\left|z\right|<1$. Let

$g^{+}_{n}(\xi;z):=\sum_{t=0}^{\infty}z^{t}\operatorname{\mathds{P}}_{0}(X_{t}=\xi).$

Note that $g^{+}_{n}(\xi;z)=g_{n}(\xi;z)+n^{-d}(1-z)^{-1}$ and
$\sum_{\xi\in\mathds{Z}^{d}_{n}}g^{+}_{n}(\xi;z)=(1-z)^{-1}$. For
$x\in\mathds{Z}_{n}^{d}$, we have

$\displaystyle g^{+}_{n}(x;z)+g^{+}_{n}(x+\xi;z)$
$\displaystyle=\sum_{t=0}^{\infty}z^{t}\operatorname{\mathds{P}}_{0}(X_{t}\in\\{x,x+\xi\\})$
$\displaystyle=\sum_{t=0}^{\infty}\sum_{s=0}^{t}z^{t}\operatorname{\mathds{P}}_{0}(X_{t}\in\\{x,x+\xi\\},\tau(x,x+\xi)=s)$
$\displaystyle=\sum_{s=0}^{\infty}\sum_{t=0}^{\infty}z^{t+s}\operatorname{\mathds{P}}_{0}(X_{t+s}\in\\{x,x+\xi\\},\tau(x,x+\xi)=s).$

Applying the Markov property at $\tau_{x}$ and $\tau_{x+\xi}$, we have

$\displaystyle\operatorname{\mathds{P}}_{0}(X_{t+s}=x,\tau(x,x+\xi)=s)$
$\displaystyle\quad=\operatorname{\mathds{P}}_{0}(X_{t+s}=x,\tau(x,x+\xi)=s=\tau(x))+\operatorname{\mathds{P}}_{0}(X_{t+s}=x,\tau(x,x+\xi)=s=\tau(x+\xi))$
$\displaystyle\quad=(\operatorname{\mathds{P}}_{0}(X_{t}=0)+\operatorname{\mathds{P}}_{0}(X_{t}=\xi))\operatorname{\mathds{P}}_{0}(\tau(x,x+\xi)=s).$

Thus, we get

$\displaystyle g^{+}_{n}(x;z)+g^{+}_{n}(x+\xi;z)$
$\displaystyle=(g^{+}_{n}(0;z)+g^{+}_{n}(\xi;z))\sum_{s=0}^{\infty}z^{s}\operatorname{\mathds{P}}_{0}(\tau(x,x+\xi)=s).$

Averaging over $x$, we have

$\displaystyle 2n^{-d}(1-z)^{-1}$
$\displaystyle=(2n^{-d}(1-z)^{-1}+2f_{n}(\xi;z))\sum_{s=0}^{\infty}z^{s}\operatorname{\mathds{P}}(\tau(0,\xi)=s)$
$\displaystyle\text{ or
}\sum_{s=0}^{\infty}z^{s}\operatorname{\mathds{P}}(\tau(0,\xi)=s)$
$\displaystyle=\frac{n^{-d}}{n^{-d}+(1-z)f_{n}(\xi;z)}.$

Therefore,

$\displaystyle\sum_{t=0}^{\infty}z^{t}\operatorname{\mathds{P}}(\tau(0,\xi)>t)$
$\displaystyle=\sum_{t=0}^{\infty}\sum_{s=t+1}^{\infty}z^{t}\operatorname{\mathds{P}}(\tau(0,\xi)=s)$
$\displaystyle=\sum_{s=1}^{\infty}\sum_{t=0}^{s-1}z^{t}\operatorname{\mathds{P}}(\tau(0,\xi)=s)$
$\displaystyle=\sum_{s=0}^{\infty}(1-z^{s})(1-z)^{-1}\operatorname{\mathds{P}}(\tau(0,\xi)=s)$
$\displaystyle=\frac{1}{1-z}\left(1-\frac{n^{-d}}{n^{-d}+(1-z)f_{n}(\xi;z)}\right)=\frac{f_{n}(\xi;z)}{n^{-d}+(1-z)f_{n}(\xi;z)}.$

The same argument holds for the case $\xi=0$. $\blacksquare$

From the uniform convergence of $g_{n}(\xi)$ and
$\left|g_{n}(\xi)\right|\leqslant g_{n}(0)$, one can guess that $f_{n}(\xi)$
is uniformly away from 0 in $n$. The next lemma asserts that this is the case.
The proof is given in Section 4.

######  Lemma 2.4.

There exists $C>0$ independent of $n$, such that $f_{n}(\xi)\geqslant C$ for
all $\xi\in\mathds{Z}_{n}^{d}$.

##  3\. Series expansion

Fix an integer $k\geqslant 1$. Let $\alpha_{0},\alpha_{i},i\in[k]$ be a
sequence of positive real numbers and
$\zeta_{0}:=1<\zeta_{1}<\zeta_{2}<\cdots<\zeta_{k}$ be an increasing sequence
of real numbers. Define the function

$\displaystyle f(z)=\sum_{i=1}^{k}\alpha_{i}(\zeta_{i}-z)^{-1}\text{ for
}z\notin\\{\zeta_{i},i\in[k]\\}.$

We notice that $f$ is denoted by a generic function of such form only in this
section and different from the one in (16).

######  Lemma 3.1.

The degree $k$ polynomial given by

$P_{k}(z):=\sum_{i=0}^{k}\alpha_{i}\prod_{0\leqslant j\leqslant k,j\neq
i}(\zeta_{j}-z)=(\alpha_{0}+(1-z)f(z))\prod_{1\leqslant j\leqslant
k}(\zeta_{j}-z)$

has $k$ distinct real roots $\gamma_{1}<\gamma_{2}<\cdots<\gamma_{k}$.
Moreover, we have
$1<\gamma_{1}<\zeta_{1}<\gamma_{2}<\zeta_{2}<\cdots<\gamma_{k}<\zeta_{k}$ and
if $\gamma:=1+\alpha_{0}/f(1)<\zeta_{1}$, then

$\displaystyle 1+\frac{\alpha_{0}}{f(\gamma)}\leqslant\gamma_{1}\leqslant
1+\frac{\alpha_{0}}{f(1)}.$

###### Proof of Lemma 3.1.

We note that the function $\phi(z):=\alpha_{0}(1-z)^{-1}+f(z)$ is continuous
and strictly increasing in each of the interval $(\zeta_{i-1},\zeta_{i})$ for
$i\in[k]$. Moreover, $\phi(\zeta_{i}-)=\infty,\phi(\zeta_{i}+)=-\infty$ for
each $i=0,1,\ldots,k$. Thus there is a root of $\phi$ in the interval
$(\zeta_{i-1},\zeta_{i})$, say $\gamma_{i}$, for $i\in[k]$. Now, any root of
$\phi$ is also a root of $P_{k}(z):=\phi(z)(1-z)\prod_{1\leqslant j\leqslant
k}(\zeta_{j}-z)$. Since $P_{k}$ is a degree $k$ polynomial, it has exactly $k$
roots and thus $\gamma_{i},i\in[k]$ are all the roots of $P_{k}$.

Note that, $f$ is strictly increasing in each of the interval $(1,\zeta_{1})$.
Assume that, $\gamma:=1+\alpha_{0}/f(1)<\zeta_{1}$. It is easy to check that
$\hat{\phi}(z):=\alpha_{0}+(1-z)f(z)$ satisfies $\hat{\phi}(1)=\alpha_{0}>0$
and
$\hat{\phi}(\gamma)=\alpha_{0}-\alpha_{0}f(\gamma)/f(1)<\alpha_{0}-\alpha_{0}=0$.
Thus $\gamma_{1}<\gamma$.

Moreover, $\alpha_{0}+(1-\gamma_{1})f(\gamma_{1})=0$ implies that
$\gamma_{1}=1+\alpha_{0}/f(\gamma_{1})>1+\alpha_{0}/f(\gamma)$ as $f$ is
increasing and we are done. $\blacksquare$

Note that we have

$\displaystyle
f(\gamma_{i})=\frac{\alpha_{0}}{\gamma_{i}-1}>0,f^{\prime}(\gamma_{i})=\sum_{j=1}^{k}\alpha_{j}(\zeta_{j}-\gamma_{i})^{-2}>0\text{
for }i\in[k].$

In applications we have $\alpha_{0}/f(1)\approx n^{-d}\ll\zeta_{1}-1\approx
n^{-2}$ for $d\geqslant 3$ and thus we have a good control on the first root
$\gamma_{1}\approx 1+\alpha_{0}/f(1)$.

Let $\hat{\alpha}_{i},i\in[k]$ be another sequence of positive real numbers.
Define the function

$\displaystyle\hat{f}(z)=\sum_{i=1}^{k}\hat{\alpha}_{i}(\zeta_{i}-z)^{-1}\text{
for }z\notin\\{\zeta_{i},i\in[k]\\}$

and

$\displaystyle g(z):=\frac{\hat{f}(z)}{\alpha_{0}+(1-z)f(z)}\text{ for
}z\notin\\{\gamma_{i},i\in[k]\\}.$

Here we define
$g(\zeta_{i}):=\frac{\hat{\alpha}_{i}}{(1-\zeta_{i})\alpha_{i}}$ so that $g$
is continuously differentiable everywhere except at
$\gamma_{1},\gamma_{2},\ldots,\gamma_{k}$.

######  Lemma 3.2.

We have

$\displaystyle
g(z)=\sum_{i=1}^{k}\frac{1}{\gamma_{i}-z}\cdot\frac{\hat{f}(\gamma_{i})/f(\gamma_{i})}{1+\alpha_{0}f^{\prime}(\gamma_{i})f(\gamma_{i})^{-2}}\text{
for }z\notin\\{\gamma_{i},i\in[k]\\}.$

In particular, the coefficient of $z^{t},t\geqslant 0$ in the series expansion
of $g$ around $0$ is given by

$\displaystyle\sum_{i=1}^{k}\frac{\hat{f}(\gamma_{i})}{f(\gamma_{i})}\cdot\frac{\gamma_{i}^{-t-1}}{1+\alpha_{0}f^{\prime}(\gamma_{i})f(\gamma_{i})^{-2}}=\frac{\hat{f}(\gamma_{1})}{f(\gamma_{1})}\cdot\frac{\gamma_{1}^{-t-1}}{1+\alpha_{0}f^{\prime}(\gamma_{1})f(\gamma_{1})^{-2}}+e(t)$

where

$\displaystyle\left|e(t)\right|\leqslant\max_{i\in[k]}\left|\frac{\hat{f}(\gamma_{i})}{f(\gamma_{i})}\right|\cdot\zeta_{1}^{-t}.$

###### Proof of Lemma 3.2.

We can write $g$ as a ratio of a degree $(k-1)$ and a degree $k$-polynomial,
as

$\displaystyle
g(z)=\frac{\hat{f}(z)\prod_{i=1}^{k}(\zeta_{i}-z)}{(\alpha_{0}+(1-z)f(z))\prod_{i=1}^{k}(\zeta_{i}-z)}=\frac{\sum_{i=1}^{k}\hat{\alpha}_{i}\prod_{1\leqslant
j\leqslant k,j\neq i}(\zeta_{j}-z)}{\sum_{i=0}^{k}\alpha_{i}\prod_{0\leqslant
j\leqslant k,j\neq i}(\zeta_{j}-z)}.$

The denominator has $k$ distinct real roots given by $\gamma_{i},i\in[k]$.
Thus we can write

$\displaystyle g(z)=\sum_{i=1}^{k}a_{i}(\gamma_{i}-z)^{-1}$

for some real numbers $a_{i},i\in[k]$. Moreover, we have

$\displaystyle
a_{i}=\lim_{z\to\gamma_{i}}(\gamma_{i}-z)g(z)=\frac{-\hat{f}(\gamma_{i})}{(\alpha_{0}+(1-z)f(z))^{\prime}|_{z=\gamma_{i}}}=\frac{\hat{f}(\gamma_{i})}{f(\gamma_{i})+(\gamma_{i}-1)f^{\prime}(\gamma_{i})}.$

Finally we used the fact that
$f(\gamma_{i})=\frac{\alpha_{0}}{\gamma_{i}-1}>0$.

The coefficient result follows since
$(\gamma_{i}-z)^{-1}=\sum_{t=0}^{\infty}\gamma_{i}^{-t-1}z^{t}$ for
$\left|z\right|<1$ and the bound on
$e(t):=\sum_{i=2}^{k}a_{i}\cdot\gamma_{i}^{-t-1}$ follows as
$\gamma_{i}>\zeta_{1}>1$ for all $i>1$ and

$\displaystyle\left|e(t)\right|\leqslant\sum_{i=2}^{k}\left|a_{i}\right|\cdot\gamma_{i}^{-t-1}\leqslant\zeta_{1}^{-t}\cdot\max_{i\in[k]}\left|\frac{\hat{f}(\gamma_{i})}{f(\gamma_{i})}\right|\cdot\sum_{i=1}^{k}\frac{\gamma_{i}^{-1}}{1+\alpha_{0}f^{\prime}(\gamma_{1})/f(\gamma_{1})^{2}}$

and the last sum is $f(0)/(\alpha_{0}+f(0))<1$. $\blacksquare$

In our case, we have $\gamma_{1}\approx
1+\Theta(\alpha_{0}),\alpha_{0}=\Theta(n^{-d}),t=\Theta(n^{d}),\zeta_{1}=1+\Theta(n^{-2})$,
thus the error term is $\exp(-\Theta(n^{d-2}))$ whereas the first term is
$\Theta(1)$.

##  4\. Proofs of Auxiliary Results

###  4.1. Proof of Lemma 2.2

By symmetry and translation invariance, it suffices to assume that
$0\leqslant\xi_{j}\leqslant\frac{n}{2}$ for all $j=1,2,\ldots,d$. Recall that
$\pi(\xi)=n^{-d}$ is the uniform distribution. Let $T_{\text{mix}}$ be the
mixing time. It is well known (see [LPW]*Chapter 4) that
$T_{\text{mix}}=O(n^{2})$ and there exist $\bar{\gamma}>0,c>0$ such that

$\displaystyle\sup_{\xi\in\mathds{Z}_{n}^{d}}\left|\operatorname{\mathds{P}}_{0}(X_{t}=\xi)-\pi(\xi)\right|=O(n^{-d}e^{-\bar{\gamma}t/n^{2}})$

for $t\geqslant cn^{2}$. In particular,

$\displaystyle\sum_{t=cn^{2}}^{\infty}\left|\operatorname{\mathds{P}}_{0}(X_{t}=\xi)-\pi(\xi)\right|$
$\displaystyle=O(n^{-d+2})$ $\displaystyle\text{ and
}\sum_{t=cn^{2}}^{\infty}t\left|\operatorname{\mathds{P}}_{0}(X_{t}=\xi)-\pi(\xi)\right|$
$\displaystyle=O(n^{-d+4}).$

Clearly, $\operatorname{\mathds{P}}_{0}(X_{t}=\xi)=0$ for
$t<\left\|\xi\right\|_{1}$. Thus, what is left is to control the contribution
for $\left\|\xi\right\|_{1}\leqslant t\leqslant cn^{2}$.

Let $S_{t}$ be a $\frac{1}{2}$–lazy random walk on $\mathds{Z}^{d}$. We can
couple the two random walks $(S_{t},X_{t})$ on
$\mathds{Z}^{d},\mathds{Z}_{n}^{d}$, respectively, by defining
$X_{t}=S_{t}\mod n$, coordinate-wise. Then

$\displaystyle\operatorname{\mathds{P}}_{0}(X_{t}=\xi)=\sum_{k\in\mathds{Z}^{d},\left\|\xi+nk\right\|_{1}\leqslant
t}\operatorname{\mathds{P}}_{0}(S_{t}=\xi+nk).$

In time $t=O(n^{2})$, the random walk $S_{t}$ can visit upto distance of order
$n$ with high probability and
$\left\|\xi+nk\right\|_{1}=\Omega(\max\\{n,\left\|\xi\right\|_{1}\\})$ for
$k\neq 0$. In fact, from the local limit theorem (see [Lawler]*Theorem 1.2.1),
it follows that there exists $K>0$ such that

$\displaystyle\operatorname{\mathds{P}}_{0}(S_{t}=\xi+nk)\lesssim\left(\frac{d}{2\pi
t}\right)^{\frac{d}{2}}e^{-\frac{d\left\|\xi+nk\right\|^{2}}{2t}}+\left\|\xi+nk\right\|^{-2}t^{-\frac{d}{2}}$

for $t\geqslant K$. Assume that $\left\|\xi\right\|_{1}\geqslant K$. We have

$\displaystyle
I_{1}:=\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{\begin{subarray}{c}k\in\mathds{Z}^{d}\\\
\left\|\xi+nk\right\|_{1}\leqslant
t,\left\|k\right\|\leqslant\sqrt{d}\end{subarray}}\left\|\xi+nk\right\|^{-2}t^{-\frac{d}{2}}\lesssim\left\|\xi\right\|^{-2}\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}t^{-\frac{d}{2}}\simeq\left\|\xi\right\|^{-\frac{d+2}{2}}.$

If $\left\|k\right\|>\sqrt{d}$, using
$\left\|\xi/n\right\|\leqslant\sqrt{d}/2$, we have
$\frac{1}{2}\left\|k\right\|<\left\|k+\xi/n\right\|<2\left\|k\right\|$ and

$\displaystyle\sum_{\begin{subarray}{c}k\in\mathds{Z}^{d}\\\
\left\|\xi+nk\right\|_{1}\leqslant
t,\left\|k\right\|>\sqrt{d}\end{subarray}}\left\|\xi+nk\right\|^{-2}$
$\displaystyle\lesssim
n^{-2}\sum_{k\in\mathds{Z}^{d},\left\|k\right\|<Ct/n}\left\|k\right\|^{-2}\simeq
n^{-d}t^{d-2}.$

Thus

$\displaystyle
I_{2}:=\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{\begin{subarray}{c}k\in\mathds{Z}^{d}\\\
\left\|\xi+nk\right\|_{1}\leqslant
t,\left\|k\right\|>\sqrt{d}\end{subarray}}\left\|\xi+nk\right\|^{-2}t^{-\frac{d}{2}}$
$\displaystyle\simeq
n^{-d}\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}t^{\frac{d}{2}-2}\simeq n^{-2}.$

On the other hand,

$\displaystyle
I_{3}:=\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{\begin{subarray}{c}k\in\mathds{Z}^{d}\\\
\left\|\xi+nk\right\|_{1}<t,\left\|k\right\|\leqslant\sqrt{d}\end{subarray}}t^{-\frac{d}{2}}e^{-\frac{d\left\|\xi+nk\right\|^{2}}{2t}}$
$\displaystyle\lesssim\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}t^{-\frac{d}{2}}e^{-\frac{d\left\|\xi\right\|^{2}}{2t}}$
$\displaystyle\simeq\int_{0}^{\infty}t^{-\frac{d}{2}}e^{-\frac{d\left\|\xi\right\|^{2}}{2t}}\simeq\left\|\xi\right\|^{2-d}$

and

$\displaystyle I_{4}$
$\displaystyle:=\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{\begin{subarray}{c}k\in\mathds{Z}^{d}\\\
\left\|\xi+nk\right\|_{1}<t,\left\|k\right\|>\sqrt{d}\end{subarray}}t^{-\frac{d}{2}}e^{-\frac{d\left\|\xi+nk\right\|^{2}}{2t}}$
$\displaystyle\lesssim\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{k\in\mathds{Z}^{d},\left\|k\right\|<Ct/n}t^{-\frac{d}{2}}e^{-\frac{dn^{2}\left\|k\right\|^{2}}{8t}}\lesssim
n^{2-d}.$

In the last inequality, we used the fact that
$\sum_{k\in\mathds{Z}^{d}}s^{-\frac{d}{2}}e^{-C\|k\|^{2}/s}\lesssim 1$.
Therefore,

$\displaystyle\left|g_{n}(\xi)\right|$
$\displaystyle\leqslant\sum_{t=cn^{2}}^{\infty}\left|\operatorname{\mathds{P}}_{0}(X_{t}=\xi)-\pi(\xi)\right|+\sum_{t=0}^{cn^{2}}\pi(\xi)+\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\operatorname{\mathds{P}}_{0}(X_{t}=\xi)$
$\displaystyle\lesssim n^{2-d}+I_{1}+I_{2}+I_{3}+I_{4}$ $\displaystyle\lesssim
n^{2-d}+\left\|\xi\right\|^{-\frac{d+2}{2}}+\left\|\xi\right\|^{2-d}+n^{2-d}+n^{-2}.$

We now prove the second assertion. Since
$g_{n}(\xi;z)=\sum_{t=0}^{\infty}z^{t}(\operatorname{\mathds{P}}_{0}(X_{t}=\xi)-\pi(\xi))$,
$g_{n}^{\prime}(\xi)$ can be written as

$\displaystyle
g_{n}^{\prime}(\xi)=\frac{d}{dz}g_{n}^{\prime}(\xi;z)\biggr{|}_{z=1}=\sum_{t=0}^{\infty}t(\operatorname{\mathds{P}}_{0}(X_{t}=\xi)-\pi(\xi)).$

As before, it suffices to estimate the summation over
$\left\|\xi\right\|_{1}\leqslant t\leqslant cn^{2}$. Let $\beta\in(1,2)$. Then

$\displaystyle J_{1}$
$\displaystyle:=\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{\begin{subarray}{c}k\in\mathds{Z}^{d}\\\
\left\|\xi+nk\right\|_{1}<n^{\beta}\end{subarray}}\left\|\xi+nk\right\|^{-2}t^{-\frac{d}{2}+1}$
$\displaystyle\lesssim\left\|\xi\right\|^{-2}\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}t^{-\frac{d}{2}+1}+n^{-2}\sum_{t=0}^{cn^{2}}\sum_{\begin{subarray}{c}k\in\mathds{Z}^{d}\\\
\left\|k\right\|<Cn^{\beta-1}\end{subarray}}\left\|k\right\|^{-2}t^{-\frac{d}{2}+1}$
$\displaystyle\lesssim\left\|\xi\right\|^{-\frac{d}{2}}+n^{(2-d)(2-\beta)}$

and

$\displaystyle J_{2}$
$\displaystyle:=\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{\begin{subarray}{c}k\in\mathds{Z}^{d}\\\
\left\|\xi+nk\right\|_{1}<n^{\beta}\end{subarray}}t^{-\frac{d}{2}+1}e^{-\frac{\left\|\xi+nk\right\|^{2}}{t}}$
$\displaystyle\lesssim\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}t^{-\frac{d}{2}+1}e^{-\frac{d\left\|\xi\right\|^{2}}{2t}}+\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{\begin{subarray}{c}k\in\mathds{Z}^{d}\\\
\left\|k\right\|<Cn^{\beta-1}\end{subarray}}t^{-\frac{d}{2}+1}e^{-\frac{dn^{2}\left\|k\right\|^{2}}{8t}}$
$\displaystyle\lesssim\left\|\xi\right\|^{4-d}+n^{4-d}.$

By [Lawler]*Lemma 1.5.1, we get

$\displaystyle
J_{3}:=\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{n^{\beta}\leqslant\left\|\xi+nk\right\|_{1}<t}t\operatorname{\mathds{P}}_{0}(S_{t}=\xi+nk)$
$\displaystyle\lesssim\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{n^{\beta}\leqslant\left\|\xi+nk\right\|_{1}<t}t\operatorname{\mathds{P}}_{0}(\left\|S_{t}\right\|\geqslant
cn^{\beta+1})$
$\displaystyle\lesssim\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}\sum_{n^{\beta}\leqslant\left\|\xi+nk\right\|_{1}<t}te^{-\frac{cn^{\beta+1}}{t}}$
$\displaystyle\lesssim n^{d+4}e^{-cn^{\beta-1}}.$

Thus, the local central limit theorem yields that for large
$\left\|\xi\right\|$,

$\displaystyle|g_{n}^{\prime}(\xi)|$
$\displaystyle\leqslant\sum_{t=cn^{2}}^{\infty}t\left|\operatorname{\mathds{P}}_{0}(X_{t}=\xi)-\pi(\xi)\right|+\sum_{t=0}^{cn^{2}}t\pi(\xi)+\sum_{t=\left\|\xi\right\|_{1}}^{cn^{2}}t\operatorname{\mathds{P}}_{0}(X_{t}=\xi)$
$\displaystyle\lesssim n^{4-d}+J_{1}+J_{2}+J_{3}$ $\displaystyle\lesssim
n^{4-d}+n^{(2-d)(2-\beta)}+n^{d+4}e^{-cn^{\beta-1}}+\left\|\xi\right\|^{-\frac{d}{2}}+\left\|\xi\right\|^{4-d}$

as desired.

###  4.2. Proof of Lemma 2.4

Take $\varepsilon=G(0)/4>0$. By Lemma 2.2, there exist positive integers
$N_{1}$ and $K$ such that

$\left|g_{n}(0)-G(0)\right|\leqslant\varepsilon,\left|g_{n}(\xi)\right|\leqslant\varepsilon\text{
for all }\left\|\xi\right\|\geqslant K,\xi\in\mathds{Z}_{n}^{d},n\geqslant
N_{1}.$

Moreover, we can choose $N\geqslant N_{1}$, such that

$\sup_{\left\|\xi\right\|\leqslant
K}\left|g_{n}(\xi)-G(\xi)\right|\leqslant\varepsilon\text{ for all }n\geqslant
N.$

Fix $n\geqslant N$. Recall that $f_{n}(\xi)=(g_{n}(0)+g_{n}(\xi))/2$. For
$\xi\in\mathds{Z}_{n}^{d}$ with $\left\|\xi\right\|\geqslant K$ we have

$\displaystyle
f_{n}(\xi)\geqslant\frac{1}{2}G(0)-\frac{1}{2}\left|g_{n}(0)-G(0)\right|-\frac{1}{2}\left|g_{n}(\xi)\right|\geqslant\varepsilon.$

For $\xi\in\mathds{Z}_{n}^{d}$ with $\left\|\xi\right\|\leqslant K$ we have

$\displaystyle
f_{n}(\xi)\geqslant\frac{1}{2}(G(0)+G(\xi))-\frac{1}{2}\left|g_{n}(0)-G(0)\right|-\frac{1}{2}\left|g_{n}(\xi)-G(\xi)\right|\geqslant\varepsilon.$

###  4.3. Proof of Lemma 1.8

Let $k:=\left|\\{\lambda_{v}\mid v\in\mathds{Z}_{n}^{d}\\}\right|-1$. We order
the elements of the set $\\{1/\widehat{\lambda}_{v}\mid
v\in\mathds{Z}_{n}^{d}\setminus\\{0\\}\\}$ as
$\zeta_{1}<\zeta_{2}<\cdots<\zeta_{k}$. Clearly we have,

$\displaystyle\zeta_{1}=\frac{1}{1-\min_{v\in\mathds{Z}_{n}^{d}\setminus\\{0\\}}\lambda_{v}}=\frac{1}{1-d^{-1}\sin^{2}(\pi/n)}=1+\frac{\pi^{2}}{dn^{2}}(1+o(1))$

where the minimum is achieved at $\pm e_{i},i\in[d]$. One can also see that

$\displaystyle f_{n}(\xi;z)=\sum_{i=1}^{k}\alpha_{i}(\xi)(\zeta_{i}-z)^{-1}$

where $\alpha_{i}(\xi)\geqslant 0$ and $\alpha_{1}(\xi)\neq 0$. We fix
$\xi\in\mathds{Z}^{d}_{n}$ and simply write $\alpha_{i}(\xi)=\alpha_{i}$. Let
$\alpha_{0}=\frac{1}{n^{d}}$ and $\zeta_{0}=1$. By Lemma 3.1, there exist the
distinct roots $\gamma_{1}(\xi)<\gamma_{2}(\xi)<\cdots<\gamma_{k}(\xi)$ for
the equation

$\displaystyle P_{k}(z):=\sum_{i=0}^{k}\alpha_{i}\prod_{0\leqslant j\leqslant
k,j\neq i}(\zeta_{j}-z)=(\alpha_{0}+(1-z)f_{n}(\xi;z))\prod_{1\leqslant
j\leqslant k}(\zeta_{j}-z)=0.$

It then follows from Lemma 2.3 and Lemma 3.2, for $t=\Theta(n^{d})$ and
$f=\widehat{f}$, that

$\displaystyle\operatorname{\mathds{P}}(\tau(0,\xi)>t)$
$\displaystyle=\sum_{i=1}^{k}\frac{\gamma_{i}(\xi)^{-t-1}}{1+n^{-d}f^{\prime}_{n}(\xi;\gamma_{i}(\xi))f_{n}(\xi;\gamma_{i}(\xi))^{-2}}$
$\displaystyle=\frac{\gamma_{1}(\xi)^{-t-1}}{1+n^{-d}f^{\prime}_{n}(\xi;\gamma_{1}(\xi))f_{n}(\xi;\gamma_{1}(\xi))^{-2}}+e(t)$
(18)

where $\left|e(t)\right|\leqslant\zeta_{1}^{-t}\leqslant e^{-\Theta(n^{d-2})}$
and $\gamma_{1}(\xi)=1+\frac{n^{-d}}{f_{n}(\xi;\gamma_{1}(\xi))}$. From now
on, we use $r_{n}(\xi)=\gamma_{1}(\xi)$ to emphasize its dependence on $n$.

Let $z=r_{n}(\xi)$, then $z-1=\frac{1}{n^{d}f_{n}(\xi;z)}$. We use the
notations $f_{n}(\xi)=f_{n}(\xi;1)$ and
$f_{n}^{\prime}(\xi)=f_{n}^{\prime}(\xi;1)$. There exist $\widetilde{z}$ and
$\overline{z}$ between 1 and $\gamma_{1}$ such that

$\displaystyle f_{n}(\xi;z)$
$\displaystyle=f_{n}(\xi)+f^{\prime}_{n}(\xi)(z-1)+\frac{1}{2}f_{n}^{\prime\prime}(\xi;\widetilde{z})(z-1)^{2}$
$\displaystyle=f_{n}(\xi)+\frac{f^{\prime}_{n}(\xi)}{n^{d}f_{n}(\xi)}\left(1+\frac{f^{\prime}_{n}(\xi;\overline{z})}{n^{d}f_{n}(\xi)f_{n}(\xi;z)}\right)^{-1}+\frac{f_{n}^{\prime\prime}(\xi;\widetilde{z})}{2n^{2d}f_{n}(\xi;z)^{2}}.$

Note that,
$\left|f^{\prime\prime}(\xi;z)\right|\leqslant|f^{\prime\prime}_{n}(0)|\leqslant
n^{-d}\sum_{v\in\mathds{Z}_{n}^{d}\setminus\\{0\\}}\left|\lambda_{v}\right|^{-3}$
for $\left|z\right|\leqslant 1$. By Lemma 2.1 with $k=3$, we have
$f_{n}^{\prime\prime}(\xi;\widetilde{z})=O(n^{3})$. It then follows from Lemma
2.4 that

$\displaystyle
f_{n}(\xi;r_{n}(\xi))=f_{n}(\xi)\left(1+\frac{f^{\prime}_{n}(\xi)}{n^{d}f_{n}(\xi)^{2}}+O(n^{3-2d})\right).$
(19)

Applying (19) to $r_{n}(\xi)$, we get

$\displaystyle\log(r_{n}(\xi))$
$\displaystyle=\log\left(1+\frac{1}{n^{d}f_{n}(\xi;r_{n}(\xi))}\right)$
$\displaystyle=\log\left(1+\frac{1}{n^{d}f_{n}(\xi)}\left(1-\frac{f^{\prime}_{n}(\xi)}{n^{d}f_{n}(\xi)^{2}}+O(n^{3-2d})\right)\right)$
$\displaystyle=\frac{1}{n^{d}f_{n}(\xi)}-\frac{1}{n^{2d}}\left(\frac{f^{\prime}_{n}(\xi)}{f_{n}(\xi)^{3}}+\frac{1}{2f_{n}(\xi)^{2}}\right)+O(n^{3-3d}),$

which yields

$\displaystyle
r_{n}(\xi)^{-(t+1)}=e^{-\frac{u}{f_{n}(\xi)}}\left(1+\frac{u}{n^{d}}\left(\frac{f^{\prime}_{n}(\xi)}{f_{n}(\xi)^{3}}+\frac{1}{2f_{n}(\xi)^{2}}\right)+O(n^{3-2d})\right).$

By (19) and (18), we conclude

$\displaystyle\operatorname{\mathds{P}}(\tau(0,\xi)>t)$
$\displaystyle=\frac{r_{n}(\xi)^{-t-1}}{1+n^{-d}f^{\prime}_{n}(\xi;r_{n}(\xi))f_{n}(\xi;r_{n}(\xi))^{-2}}+e(t)$
$\displaystyle=e^{-\frac{u}{f_{n}(\xi)}}\left(1+\frac{u}{n^{d}}\left(\frac{f^{\prime}_{n}(\xi)}{f_{n}(\xi)^{3}}+\frac{1}{2f_{n}(\xi)^{2}}\right)-\frac{f_{n}^{\prime}(\xi)}{n^{d}f_{n}(\xi)^{2}}\right)+O(n^{3-2d}).$

##  5\. Proofs of Main Results

###  5.1. Proof of Theorem 1.2

For simplicity, we will omit the subscript $n$ in $f_{n},g_{n}$. By Lemma 1.8
and (7), we have

$\displaystyle n^{-d}\operatorname{Var}(V_{n}^{(\ell)}(t))$
$\displaystyle=\sum_{\xi\in\mathds{Z}_{n}^{d}}(\operatorname{\mathds{P}}(\tau(0,\xi)>t)^{\ell}-\operatorname{\mathds{P}}(\tau(0)>t)^{2\ell})$
$\displaystyle=\sum_{\xi\in\mathds{Z}_{n}^{d}}(e^{-\frac{\ell
u}{f(\xi)}}-e^{-\frac{2\ell
u}{f(0)}})+\frac{\ell}{n^{d}}\sum_{\xi\in\mathds{Z}_{n}^{d}}e^{-\frac{\ell
u}{f(\xi)}}\left(u\left(\frac{f^{\prime}(\xi)}{f(\xi)^{3}}+\frac{1}{2f(\xi)^{2}}\right)-\frac{f^{\prime}(\xi)}{f(\xi)^{2}}\right)$
$\displaystyle\quad-2\ell e^{-\frac{2\ell
u}{f(0)}}\left(u\left(\frac{f^{\prime}(0)}{f(0)^{3}}+\frac{1}{2f(0)^{2}}\right)-\frac{f^{\prime}(0)}{f(0)^{2}}\right)+o(1).$

It follows from $\sum_{\xi\in\mathds{Z}^{d}_{n}}g(\xi)=0$ that

$\displaystyle\sum_{\xi\in\mathds{Z}_{n}^{d}}(e^{-\frac{\ell
u}{f(\xi)}}-e^{-\frac{2\ell u}{f(0)}})$ $\displaystyle\qquad=e^{-\frac{2\ell
u}{f(0)}}\left(\sum_{\xi\in\mathds{Z}_{n}^{d}}\left(e^{\frac{\ell
ug(\xi)}{f(0)f(\xi)}}-1-\frac{\ell ug(\xi)}{f(0)f(\xi)}\right)-\frac{\ell
u}{f(0)^{2}}\sum_{\xi\in\mathds{Z}_{n}^{d}}\frac{g(\xi)^{2}}{f(\xi)}\right).$

Recall that $f_{n}(\xi)\geqslant C>0$ for all $n$ and $\xi$ by Lemma 2.4.
Since $e^{t}-1-t\leqslant\frac{1}{2}t^{2}\max\\{e^{t},1\\}$ and
$g(\xi)\leqslant g(0)=f(0)$, we have

$\displaystyle e^{\frac{\ell ug(\xi)}{f(0)f(\xi)}}-1-\frac{\ell
ug(\xi)}{f(0)f(\xi)}$ $\displaystyle\leqslant\frac{1}{2}\left(\frac{\ell
ug(\xi)}{f(0)f(\xi)}\right)^{2}\max\\{e^{\frac{\ell
ug(\xi)}{f(0)f(\xi)}},1\\}$
$\displaystyle\leqslant\frac{\ell^{2}u^{2}}{2C^{2}}\max\\{e^{\frac{\ell
u}{C}},1\\}g(\xi)^{2}.$

Since $\lim_{n\to\infty}g_{n}(\xi)=G(\xi)$ for each $\xi$ and

$\displaystyle\lim_{n\to\infty}\sum_{\xi\in\mathds{Z}^{d}_{n}}g(\xi)^{2}=\lim_{n\to\infty}\frac{1}{n^{d}}\sum_{v\in\mathds{Z}^{d}_{n}}\frac{1}{\lambda_{v}^{2}}=\int_{[0,1]^{d}}\varphi_{d}(x)^{2}\,dx=\sum_{\xi\in\mathds{Z}^{d}}G(\xi)^{2}<\infty$
(20)

for $d\geqslant 5$ where $\varphi_{d}(x)=d(\sum_{j=1}^{d}\sin^{2}(\pi
x_{j}))^{-1}$, the dominated convergence theorem implies that

$\displaystyle\lim_{n\to\infty}\sum_{\xi\in\mathds{Z}_{n}^{d}}(e^{-\frac{\ell
u}{f(\xi)}}-e^{-\frac{2\ell u}{f(0)}})$
$\displaystyle=\sum_{\xi\in\mathds{Z}^{d}}\left(e^{-\frac{2\ell
u}{(G(0)+G(\xi))}}-e^{-\frac{2\ell u}{G(0)}}-2\ell ue^{-\frac{2\ell
u}{G(0)}}\frac{G(\xi)}{G(0)^{2}}\right).$

By Lemma 2.2, for any $\varepsilon>0$, there exist $N$ and $K$ such that
$\left|f_{n}(\xi)-\frac{1}{2}G(0)\right|<\varepsilon$ and
$\left|f^{\prime}_{n}(\xi)-\frac{1}{2}G^{\prime}(0)\right|<\varepsilon$ for
all $n\geqslant N$ and $\left\|\xi\right\|\geqslant K$. Thus, one can see that

$\displaystyle\frac{1}{n^{d}}\sum_{\xi\in\mathds{Z}_{n}^{d}}e^{-\frac{\ell
u}{f(\xi)}}\left(u\left(\frac{f^{\prime}(\xi)}{f(\xi)^{3}}+\frac{1}{2f(\xi)^{2}}\right)-\frac{f^{\prime}(\xi)}{f(\xi)^{2}}\right)$
$\displaystyle\qquad\qquad\to 2e^{-\frac{2\ell
u}{G(0)}}\left(\frac{2uG^{\prime}(0)}{G(0)^{3}}+\frac{u}{G(0)^{2}}-\frac{G^{\prime}(0)}{G(0)^{2}}\right)$

as $n\to\infty$. Therefore, it follows from (2.3) that

$\displaystyle\lim_{n\to\infty}n^{-d}\operatorname{Var}(V_{n}^{(\ell)}(t))$
$\displaystyle=\sum_{\xi\in\mathds{Z}^{d}}\left(e^{-\frac{2\ell
u}{(G(0)+G(\xi))}}-e^{-\frac{2\ell u}{G(0)}}-2\ell ue^{-\frac{2\ell
u}{G(0)}}\frac{G(\xi)}{G(0)^{2}}\right)$ $\displaystyle\quad+2\ell
ue^{-\frac{2\ell
u}{G(0)}}\left(\frac{G^{\prime}(0)}{G(0)^{3}}+\frac{1}{2G(0)^{2}}\right)$
$\displaystyle=\nu_{d}(2\ell u/G(0))$

where

$\displaystyle\nu_{d}(u):=e^{-u}\sum_{\xi\in\mathds{Z}^{d}}\left(\exp\left(\frac{uG(\xi)}{G(0)+G(\xi)}\right)-1-\frac{uG(\xi)}{G(0)}\right)+ue^{-u}\left(\frac{G^{\prime}(0)}{G(0)^{2}}+\frac{1}{2G(0)}\right).$

Using $G(0)+G^{\prime}(0)=\sum_{\xi\in\mathds{Z}^{d}}G(\xi)^{2}$, we conclude

$\displaystyle e^{u}\nu_{d}(u)$
$\displaystyle=\sum_{\xi\in\mathds{Z}^{d}}\left(\exp\left(\frac{uG(\xi)}{G(0)+G(\xi)}\right)-1-\frac{uG(\xi)}{G(0)}+\frac{uG(\xi)^{2}}{G(0)^{2}}\right)-\frac{1}{2G(0)}$
$\displaystyle=\sum_{\xi\in\mathds{Z}^{d}}\left(\exp\left(\frac{uG(\xi)}{G(0)+G(\xi)}\right)-1-\frac{uG(\xi)}{G(0)+G(\xi)}+\frac{uG(\xi)^{3}}{G(0)^{2}(G(0)+G(\xi))}\right)-\frac{1}{2G(0)}$
$\displaystyle=\sum_{\xi\in\mathds{Z}^{d}}\left(\exp\left(\frac{uG(\xi)}{G(0)+G(\xi)}\right)-1-\frac{uG(\xi)}{G(0)+G(\xi)}+\frac{uG(\xi)^{2}(G(\xi)-\mathds{1}_{\\{\xi=0\\}})}{G(0)^{2}(G(0)+G(\xi))}\right).$

###  5.2. Proof of Theorem 1.3

Note that $g_{n}^{\prime}(0)\to\infty$ as $n\to\infty$ for $d=3,4$. Again, we
will omit the subscript $n$ in $f_{n},g_{n}$, for simplicity. We have

$\displaystyle\frac{1}{n^{d}g^{\prime}(0)}\operatorname{Var}(V_{n}^{(\ell)}(t))$
$\displaystyle=\frac{1}{g^{\prime}(0)}\sum_{\xi\in\mathds{Z}_{n}^{d}}(\operatorname{\mathds{P}}(\tau(0,\xi)>t)^{\ell}-\operatorname{\mathds{P}}(\tau(0)>t)^{2\ell})$
$\displaystyle=\frac{1}{g^{\prime}(0)}\sum_{\xi\in\mathds{Z}_{n}^{d}}(e^{-\frac{\ell
u}{f(\xi)}}-e^{-\frac{2\ell
u}{f(0)}})+\frac{\ell}{n^{d}}\sum_{\xi\in\mathds{Z}_{n}^{d}}\left(\frac{ue^{-\frac{\ell
u}{f(\xi)}}}{f(\xi)^{3}}-\frac{e^{-\frac{\ell
u}{f(\xi)}}}{f(\xi)^{2}}\right)\frac{f^{\prime}(\xi)}{g^{\prime}(0)}$
$\displaystyle\quad-2\ell\left(\frac{ue^{-\frac{2\ell
u}{g(0)}}}{g(0)^{3}}-\frac{e^{-\frac{2\ell u}{g(0)}}}{g(0)^{2}}\right)+o(1).$

Here the $o(1)$ is $O(n^{3-d}/g^{\prime}(0))$. Let $\varepsilon>0$. By Lemma
2.2, there exist $N$ and $K$ such that for all $n\geqslant N$ and
$\left\|\xi\right\|\geqslant K$, $\left|g(\xi)\right|<\varepsilon$. Note that
there exist $C_{1},C_{2}$ independent of $n$ and $\xi$ such that
$0<C_{1}\leqslant f(\xi)\leqslant C_{2}<\infty$ by Lemma 2.4 and
$\left|g(\xi)\right|\leqslant g(0)$. Consider

$\psi(x):=ux^{-3}e^{-\ell u/x}-x^{-2}e^{-\ell u/x}$

for $x\in[C_{1},C_{2}]$. One can easily see that $\psi$ is bounded and
Lipschitz on $[C_{1},C_{2}]$. Indeed, there exists $C_{3}$ such that
$\left|\psi(x)-\psi(y)\right|\leqslant C_{3}(\left|x-y\right|\wedge 1)$ and
for $x,y\in[C_{1},C_{2}]$ and for $i=1,2$. Thus,

$\displaystyle\left|\psi(f(\xi))-\psi(g(0)/2)\right|$
$\displaystyle=\left|\left(\frac{ue^{-\frac{\ell
u}{f(\xi)}}}{f(\xi)^{3}}-\frac{e^{-\frac{\ell
u}{f(\xi)}}}{f(\xi)^{2}}\right)-\left(\frac{8ue^{-\frac{2\ell
u}{g(0)}}}{g(0)^{3}}-\frac{4e^{-\frac{2\ell
u}{g(0)}}}{g(0)^{2}}\right)\right|$ $\displaystyle\leqslant
C_{3}\left|f(\xi)-\frac{1}{2}g(0)\right|.$

Note that

$\displaystyle\frac{1}{n^{d}}\sum_{\xi\in\mathds{Z}_{n}^{d}}\psi(g(0)/2)\frac{f^{\prime}(\xi)}{g^{\prime}(0)}=\frac{1}{2}\psi(g(0)/2)=\frac{4ue^{-\frac{2\ell
u}{G(0)}}}{G(0)^{3}}-\frac{2e^{-\frac{2\ell u}{G(0)}}}{G(0)^{2}}.$

because $\sum_{\xi\in\mathds{Z}^{d}_{n}}g^{\prime}(\xi)=0$, and that
$0\leqslant f^{\prime}(\xi)\leqslant g^{\prime}(0)$ for all $n,\xi$. Since
$\left|f(\xi)-\frac{1}{2}g(0)\right|<\varepsilon/2$ for all $n\geqslant N$, we
get

$\displaystyle\left|\frac{1}{n^{d}}\sum_{\xi\in\mathds{Z}_{n}^{d}}\left(\psi(f(\xi))-\psi(g(0)/2)\right)\frac{f^{\prime}(\xi)}{g^{\prime}(0)}\right|$
$\displaystyle\quad\leqslant\frac{\varepsilon
C_{3}}{2n^{d}}\sum_{\xi\in\mathds{Z}_{n}^{d},\left\|\xi\right\|\geqslant
K}\frac{f^{\prime}(\xi)}{g^{\prime}(0)}+\frac{C_{3}}{n^{d}}\sum_{\xi\in\mathds{Z}_{n}^{d},\left\|\xi\right\|<K}\frac{f^{\prime}(\xi)}{g^{\prime}(0)}$
$\displaystyle\quad\leqslant\frac{\varepsilon
C_{3}}{2}+\frac{C_{4}K^{d}}{n^{d}},$

which yields in turn that

$\displaystyle\lim_{n\to\infty}\frac{\ell}{n^{d}}\sum_{\xi\in\mathds{Z}_{n}^{d}}\left(\frac{ue^{-\frac{\ell
u}{f(\xi)}}}{f(\xi)^{3}}-\frac{e^{-\frac{\ell
u}{f(\xi)}}}{f(\xi)^{2}}\right)\frac{f^{\prime}(\xi)}{g^{\prime}(0)}$
$\displaystyle=2\ell e^{-\frac{2\ell
u}{G(0)}}\left(\frac{2u}{G(0)^{3}}-\frac{1}{G(0)^{2}}\right).$

On the other hand, if

$\displaystyle w_{n}=w=2\ell u/g_{n}(0),$ (21)

then

$\displaystyle\sum_{\xi\in\mathds{Z}_{n}^{d}}(e^{-\frac{\ell
u}{f(\xi)}}-e^{-\frac{2\ell u}{f(0)}})$
$\displaystyle=e^{-w}\sum_{\xi\in\mathds{Z}_{n}^{d}}(e^{-\frac{wg(\xi)}{g(0)+g(\xi)}}-1).$

It follows from Lemma 2.4 and $\left|e^{s}-1-s-s^{2}/2\right|\leqslant
C(a)|s|^{3}$ for $|s|\leqslant a$, that

$\displaystyle\left|e^{-\frac{wg(\xi)}{g(0)+g(\xi)}}-1-\frac{wg(\xi)}{g(0)+g(\xi)}-\frac{w^{2}g(\xi)^{2}}{2(g(0)+g(\xi))^{2}}\right|\leqslant\frac{w^{3}\left|g(\xi)\right|^{3}}{6(g(0)+g(\xi))^{3}}\leqslant\frac{w^{3}}{C}\left|g(\xi)\right|^{3}.$

We claim that

$\displaystyle\lim_{n\to\infty}\frac{1}{g^{\prime}(0)}\sum_{\xi\in\mathds{Z}^{d}_{n}}\left|g(\xi)\right|^{3}=0.$
(22)

Indeed, this follows from

$\displaystyle\frac{\sum_{\xi\in\mathds{Z}^{d}_{n}}\left|g(\xi)\right|^{3}}{\sum_{\xi\in\mathds{Z}^{d}_{n}}g(\xi)^{2}}$
$\displaystyle\leqslant\frac{\sum_{\xi\in\mathds{Z}^{d}_{n},\left\|\xi\right\|<K}\left|g(\xi)\right|^{3}}{\sum_{\xi\in\mathds{Z}^{d}_{n}}g(\xi)^{2}}+\varepsilon\frac{\sum_{\xi\in\mathds{Z}^{d}_{n},\left\|\xi\right\|\geqslant
K}g(\xi)^{2}}{\sum_{\xi\in\mathds{Z}^{d}_{n}}g(\xi)^{2}}\leqslant\frac{CK^{d}}{\sum_{\xi\in\mathds{Z}^{d}_{n}}g(\xi)^{2}}+\varepsilon<2\varepsilon$

for large $n$, and
$g^{\prime}(0)=\sum_{\xi\in\mathds{Z}^{d}_{n}}g(\xi)^{2}-g(0)\to\infty$ as
$n\to\infty$. Thus, we obtain

$\displaystyle\lim_{n\to\infty}\frac{1}{g^{\prime}(0)}\sum_{\xi\in\mathds{Z}^{d}_{n}}\left(e^{-\frac{wg(\xi)}{g(0)+g(\xi)}}-1-\frac{wg(\xi)}{g(0)+g(\xi)}-\frac{w^{2}g(\xi)^{2}}{2(g(0)+g(\xi))^{2}}\right)=0.$

Using $\sum_{\xi\in\mathds{Z}^{d}_{n}}g(\xi)=0$, one can write

$\displaystyle\sum_{\xi\in\mathds{Z}^{d}_{n}}\frac{g(\xi)}{g(0)+g(\xi)}$
$\displaystyle=-\sum_{\xi\in\mathds{Z}^{d}_{n}}\frac{g(\xi)^{2}}{g(0)(g(0)+g(\xi))}$
$\displaystyle=\sum_{\xi\in\mathds{Z}^{d}_{n}}\frac{g(\xi)^{3}}{g(0)^{2}(g(0)+g(\xi))}-\sum_{\xi\in\mathds{Z}^{d}_{n}}\frac{g(\xi)^{2}}{g(0)^{2}}.$

By Lemma 2.4 and the claim (22), we conclude that

$\displaystyle\lim_{n\to\infty}\frac{1}{g^{\prime}(0)}\sum_{\xi\in\mathds{Z}^{d}_{n}}\frac{g(\xi)}{g(0)+g(\xi)}$
$\displaystyle=-\frac{1}{G(0)^{2}}.$

Here, we used the fact that
$\frac{1}{g^{\prime}(0)}\sum_{\xi\in\mathds{Z}^{d}_{n}}g(\xi)^{2}\to 1$ as
$n\to\infty$. Similarly,

$\displaystyle\lim_{n\to\infty}\frac{1}{g^{\prime}(0)}\sum_{\xi\in\mathds{Z}^{d}_{n}}\frac{g(\xi)^{2}}{(g(0)+g(\xi))^{2}}$
$\displaystyle=\frac{1}{G(0)^{2}}.$

Thus, for $w$ as defined in (21) we have

$\displaystyle\lim_{n\to\infty}\frac{e^{-w}}{g^{\prime}(0)}\sum_{\xi\in\mathds{Z}_{n}^{d}}(e^{-\frac{wg(\xi)}{g(0)+g(\xi)}}-1)$
$\displaystyle=2\ell e^{-\frac{2\ell u}{G(0)}}\left(\frac{\ell
u^{2}}{G(0)^{4}}-\frac{u}{G(0)^{3}}\right).$

Therefore,

$\displaystyle\lim_{n\to\infty}\frac{\operatorname{Var}(V_{n}^{(\ell)}(t))}{n^{d}g_{n}^{\prime}(0)}$
$\displaystyle=2\ell e^{-\frac{2\ell u}{G(0)}}\left(\frac{\ell
u^{2}}{G(0)^{4}}-\frac{u}{G(0)^{3}}\right)+2\ell e^{-\frac{2\ell
u}{G(0)}}\left(\frac{2u}{G(0)^{3}}-\frac{1}{G(0)^{2}}\right)$
$\displaystyle\qquad\qquad-2\ell e^{-\frac{2\ell
u}{G(0)}}\left(\frac{u}{G(0)^{3}}-\frac{1}{G(0)^{2}}\right)$
$\displaystyle=2\ell^{2}u^{2}e^{-\frac{2\ell u}{G(0)}}G(0)^{-4}.$

Let $\alpha_{d}:=\lim_{n\to\infty}\frac{g^{\prime}(0)}{h_{d}(n)G(0)^{2}}$,
then it follows from
$\sum_{\xi\in\mathds{Z}^{d}_{n}}g_{n}(\xi)^{2}=g_{n}(0)+g_{n}^{\prime}(0)$,
$g_{n}^{\prime}(0)\to\infty$, and $g_{n}(0)<\infty$ for $d=3,4$ that

$\displaystyle\alpha_{d}=\lim_{n\to\infty}\frac{1}{h_{d}(n)G(0;\mathds{Z}^{d})^{2}}\sum_{\xi\in\mathds{Z}^{d}_{n}}g_{n}(\xi)^{2}.$

It follows from Lemma 2.1 that $\alpha_{d}$ is finite for $d=3,4$. To
simplify, $\alpha_{d}$ further, first we consider the case $d=3$.

Using the spectral representation of $g_{n}(\xi)$ and (11), we see

$\displaystyle\frac{1}{n}\sum_{\xi\in\mathds{Z}^{3}_{n}}g_{n}(\xi)^{2}=\frac{1}{n^{4}}\sum_{v\in\mathds{Z}^{3}_{n}}\lambda_{v}^{-2}=\frac{9}{\pi^{4}}\sum_{v\in\mathds{Z}^{3}_{n}}\left(\frac{n^{2}}{\pi^{2}}\sum_{j=1}^{3}\sin^{2}(\pi
v_{j}/n)\right)^{-2}.$

We split the summation over $v$ in the right hand side into two parts
$\left\|v\right\|\geqslant K_{0}$ and $\left\|v\right\|<K_{0}$, where
$K_{0}>0$ will be determined later. Then, we have

$\displaystyle\sum_{v\in\mathds{Z}^{3}_{n},\left\|v\right\|\geqslant
K_{0}}\left(\frac{n^{2}}{\pi^{2}}\sum_{j=1}^{3}\sin^{2}(\pi
v_{j}/n)\right)^{-2}\leqslant
C\sum_{v\in\mathds{Z}^{3}_{n},\left\|v\right\|\geqslant
K_{0}}\left\|v\right\|^{-4}\leqslant\frac{C}{K_{0}}.$

On the other hand, we choose $n$ large enough that

$\displaystyle\sum_{v\in\mathds{Z}^{3}_{n},\left\|v\right\|<K_{0}}\left(\frac{n^{2}}{\pi^{2}}\sum_{j=1}^{3}\sin^{2}(\pi
v_{j}/n)\right)^{-2}=\sum_{v\in\mathds{Z}^{3}_{n},\left\|v\right\|<K_{0}}\left\|v\right\|^{-4}+o(1).$

By taking large enough $K_{0}$, we conclude

$\displaystyle\alpha_{3}=\lim_{n\to\infty}\frac{g^{\prime}_{n}(0)}{nG(0)^{2}}=\lim_{n\to\infty}\frac{1}{nG(0)^{2}}\sum_{\xi\in\mathds{Z}^{3}_{n}}g_{n}(\xi)^{2}=\frac{9}{\pi^{4}G(0)^{2}}\sum_{v\in\mathds{Z}^{3}}\left\|v\right\|^{-4}.$

Similarly, for $d=4$, we have

$\displaystyle\alpha_{4}=\lim_{n\to\infty}\frac{1}{n^{4}\log n\cdot
G(0)^{2}}\sum_{\xi\in\mathds{Z}^{4}_{n}}\lambda_{v}^{-2}=\frac{16}{\pi^{4}G(0)^{2}}\lim_{n\to\infty}\frac{1}{\log
n}\sum_{v\in\mathds{Z}^{4}_{n}}\left(\frac{n^{2}}{\pi^{2}}\sum_{j=1}^{4}\sin^{2}(\pi
v_{j}/n)\right)^{-2}.$

Let $\varepsilon\in(0,1)$. Using $|\sin t|\leqslant Ct$ for all $t$ and $\sin
t=t+O(t^{3})$ as $t\to 0$, we obtain

$\displaystyle\frac{1}{\log n}\sum_{\|v\|\geqslant
n^{\varepsilon}}\left(\frac{n^{2}}{\pi^{2}}\sum_{j=1}^{4}\sin^{2}(\pi
v_{j}/n)\right)^{-2}$ $\displaystyle\leqslant\frac{C}{\log
n}\sum_{\|v\|\geqslant n^{\varepsilon}}\|v\|^{-4}$
$\displaystyle\lesssim\frac{1}{\log
n}\int_{n^{\varepsilon}}^{n}r^{-1}\,dr\lesssim\frac{\left|\log\varepsilon\right|}{\log
n}$

and

$\displaystyle\lim_{n\to\infty}\frac{1}{\log n}\sum_{\|v\|\leqslant
n^{\varepsilon}}\left(\frac{n^{2}}{\pi^{2}}\sum_{j=1}^{4}\sin^{2}(\pi
v_{j}/n)\right)^{-2}$ $\displaystyle=\lim_{n\to\infty}\frac{1}{\log
n}\sum_{\|v\|\leqslant n^{\varepsilon}}\|v\|^{-4}.$

Since this holds for any $\varepsilon\in(0,1)$, we get

$\displaystyle\alpha_{4}=\frac{16}{\pi^{4}G(0)^{2}}\lim_{n\to\infty}\frac{1}{\log
n}\sum_{\|v\|\leqslant n}\|v\|^{-4}.$

###  5.3. Proof of Theorem 1.6

A direct computation yields

$n^{-d}\operatorname{\mathds{E}}(R_{n,\ell}^{I}(t)R_{n,\ell}^{J}(t))=\sum_{\xi\in\mathds{Z}^{d}_{n}}\operatorname{\mathds{P}}(\tau(0,\xi)\leqslant
t)^{|I\cap J|}\operatorname{\mathds{P}}(\tau(0,\xi)>t)^{|I^{c}\cap
J^{c}|}\operatorname{\mathds{P}}(\tau(0)\leqslant t<\tau(\xi))^{|I\Delta J|}.$

Let

$|I\cap J|=k,\ |I^{c}\cap J^{c}|=k^{\prime},\ |I\Delta J|=r,\
\operatorname{\mathds{P}}(\tau(0)>t)=a\text{ and
}\operatorname{\mathds{P}}(\tau(0,\xi)>t)=b.$

Then $k+k^{\prime}+r=\ell$ and

$\displaystyle
n^{-d}\operatorname{\mathds{E}}(R_{n,\ell}^{I}(t)R_{n,\ell}^{J}(t))$
$\displaystyle=\sum_{\xi\in\mathds{Z}^{d}_{n}}(1-2a+b)^{k}b^{k^{\prime}}(a-b)^{r}$
$\displaystyle=\sum_{\xi\in\mathds{Z}^{d}_{n}}\sum_{i=0}^{k}\sum_{j=1}^{r}\binom{k}{i}\binom{r}{j}(1-2a)^{i}(-1)^{r-j}a^{j}b^{k-i+k^{\prime}+r-j}$
$\displaystyle=\sum_{\xi\in\mathds{Z}^{d}_{n}}\sum_{m=0}^{k+r}b^{\ell-m}\left(\sum_{j=(m-k)_{+}}^{r\wedge
m}\binom{k}{m-j}\binom{r}{j}(1-2a)^{m-j}(-1)^{r-j}a^{j}\right)$
$\displaystyle=\sum_{m=0}^{k+r}\theta_{k,r,m}(a)\sum_{\xi\in\mathds{Z}^{d}_{n}}b^{\ell-m}.$

Similarly, we have

$\displaystyle\operatorname{\mathds{E}}(R_{n,\ell}^{I}(t))\operatorname{\mathds{E}}(R_{n,\ell}^{J}(t))=n^{2d}\sum_{m=0}^{k+r}a^{2(\ell-m)}\theta_{k,r,m}(a)$

and so

$\displaystyle\operatorname{Cov}(R_{n,\ell}^{I}(t),R_{n,\ell}^{J}(t))$
$\displaystyle=\sum_{m=0}^{k+r}\theta_{k,r,m}(a)\cdot
n^{d}\sum_{\xi\in\mathds{Z}^{d}_{n}}(b^{\ell-m}-a^{2(\ell-m)})$
$\displaystyle=\sum_{m=0}^{k+r}\theta_{k,r,m}(a)\cdot\sigma_{n,\ell-m}^{2}(t).$

By Theorem 1.2, we conclude

$\displaystyle\lim_{n\to\infty}\frac{1}{n^{d}h_{d}(n)}\operatorname{Cov}(R_{n,\ell}^{I}(t),R_{n,\ell}^{J}(t))=\sum_{m=0}^{\left|I\right|+\left|J\right|}\theta_{k,r,m}(e^{-\frac{u}{G(0)}})\nu_{d}((\ell-m)u).$

##  6\. Discussion and Further Questions

Figure 1. Histograms with fitted Gaussian density based on $2000$ samples in
dimension $d=3,4$ and $5$, respectively.

  1. (1)

As we have seen, our proofs are based on a precise tail probability of the
hitting time at two points, which follows from an analytic observation on the
generation function of hitting probabilities. A natural question is whether
one can obtain an accurate tail behavior on the hitting time based on a
probabilistic argument such as conditioning or constructing an appropriate
coupling. Such an approach might give us an intuitive explanation of the
asymptotic behavior and enable us to understand how the variance is created
and grows.

  2. (2)

Once the limiting behavior of the mean and the variance of the size of the
vacant set is known, it is natural to ask if the size of the vacant set with
an appropriate normalization converges to a limiting distribution. Simulation
results for $d=3,4,5$ (see Figure 1) suggest that Gaussian central limit
theorem hold for all $d\geqslant 3$ and $u>0$. It would also be interesting to
figure out the covariance structure of the vacant sets at different times and
see if the vacant set’s size as a stochastic process indexed by $u$ converges
to a Gaussian process.

  3. (3)

Instead of the size of the vacant set, one can consider the vacant set
$\mathcal{V}^{(\ell)}_{n}(un^{d})$ as a set-valued process indexed by $u$.
Then, it would be interesting to see the scaling limit of the vacant set up to
a time proportional to the size of $\mathds{Z}^{d}_{n}$ as a subset of the
continuum torus $[0,1]^{d}$. Note that up to the cover time of order
$n^{d}\log n$, the scaling limit of the vacant set is studied by [Bel, MS17].

  4. (4)

Miller [Miller2013a] studied the trace by two competing random walks on the
discrete torus $\mathds{Z}^{d}_{n}$ until the torus is fully covered. It is
natural to consider the trace at a time scale proportional to $n^{d}$. In
particular, one can ask how the variance behaves as the time level grows and
see if there is a time threshold for the limiting variance.

## References