# Moderate deviations for the self-normalized random walk in random scenery

Tal Peretz111Technion - Israel Institute of Technology. E-mail:
<EMAIL_ADDRESS>
###### Abstract

Let $G$ be an infinite connected graph with vertex set $V$. Let
$\\{S_{n}:n\in\mathbb{N}_{0}\\}$ be the simple random walk on $G$ and let
$\\{\xi(v):v\in V\\}$ be a collection of i.i.d. random variables which are
independent of the random walk. Define the random walk in random scenery as
$T_{n}=\sum_{k=0}^{n}\xi(S_{k})$, and the normalization variables
$V_{n}=(\sum_{k=0}^{n}\xi^{2}(S_{k}))^{1/2}$ and $L_{n,2}=(\sum_{v\in
V}\ell^{2}_{n}(v))^{1/2}$. For $G=\mathbb{Z}^{d}$ and $G=\mathbb{T}_{d}$, the
$d$-ary tree, we provide large deviations results for the self-normalized
process $T_{n}\sqrt{n}/(L_{n,2}V_{n})$ under only finite moment assumptions on
the scenery.

_Keywords and phrases._ Moderate deviations; Self-normalized partial sums;
Random walk in random scenery; Local times
MSC 2010 _subject classifications._ Primary 60F10; Secondary 60G50, 60K37.

##  1 Introduction

Let $G$ be an infinite connected graph with vertex set $V$ and let
$\\{S_{n}:n\in\mathbb{N}_{0}\\}$ be the simple random walk on $G$ started at a
distinguished vertex $o\in V$. Denote the law and expectation of this walk by
$P$ and $E$. Let $\\{\xi(v):v\in V\\}$ be independent copies of a random
variable $\xi$, which we denote as the scenery. Denote the law of the scenery
by $\mathbb{P}$ and the expectation with respect to this law by $\mathbb{E}$.
We will always assume $\mathbb{E}\xi=0$ and $\sigma^{2}=\mathbb{E}\xi^{2}>0$.
The random walk in random scenery (RWRS) is the process
$\\{T_{n}:n\in\mathbb{N}_{0}\\}$ defined by

$\displaystyle T_{n}=\sum_{k=0}^{n}\xi(S_{k})=\sum_{v\in V}\ell_{n}(v)\xi(v),$

where $\ell_{n}(v)=\sum_{k=0}^{n}\mathbbm{1}{\\{S_{k}=v\\}}$ is the local time
of $v$ at time $n$. This process was introduced for the case
$G=\mathbb{Z}^{d}$ by Kesten and Spitzer [10], and by Borodin [5]
independently and at the same time in order to introduce new scaling and self-
similar laws. However for $d\geq 3$, when the random walk by time $n$ visits
most points a constant amount of times, [10] showed under appropriate
assumptions on the distribution of $\xi$ that $T_{n}/\sqrt{n}$ converges in
distribution to a Gaussian random variable. More recently, large and moderate
deviations of $T_{n}$ have been studied for $G=\mathbb{Z}^{d}$ in [2, 3, 7, 8,
9]. Fleischmann, Mortërs and Wachtel [8] proved a moderate deviations
principle (MDP) for $d\geq 3$. Assuming Cramér’s condition, i.e. that there
exists $\theta>0$ such that $\mathbb{E}e^{\theta|\xi|}<\infty$, they showed
that

$\displaystyle\lim_{n\rightarrow\infty}y_{n}^{-2}\log\mathbb{P}\otimes
P(T_{n}/\sqrt{n}\geq y_{n})=-\frac{1}{2\sigma^{2}(2G(0)-1)}$ (1.1)

for $y_{n}=o(n^{1/6})$, where $G(\cdot)$ is the Green’s function of the random
walk. We write $a_{n}=o(b_{n})$ or $a_{n}\ll b_{n}$ if
$\lim_{n\to\infty}a_{n}/b_{n}=0$ for positive sequences $a_{n}$ and $b_{n}$.
In contrast with moderate deviations of sums of i.i.d. random variables, in
[3] it was shown that this regime is maximal under Cramér’s condition. That
is, more assumptions need to be made on the scenery in order to get moderate
deviations when $y_{n}$ grows faster than $n^{1/6}$.

There has been a recent interest in proving large deviations for sums of
i.i.d. random variables under minimal moment assumptions. It is well
understood that if one replaces the normalization constant by self-
normalization, this is possible. In [13], Shao provided self-normalized large
and moderate deviations for the partial sum of i.i.d. random variables, while
only making assumptions on the second moment. In [7], Feng, Shao and Zeitouni
extended this framework to RWRS by proving a Crámer type moderate deviations.
Define

$\displaystyle V_{n}^{2}=\sum_{k=0}^{n}\xi^{2}(S_{k})=\sum_{v\in
V}\ell_{n}(v)\xi^{2}(v)$

and

$\displaystyle L^{2}_{n,2}=\sum_{v\in V}\ell^{2}_{n}(v).$

For the simple random walk on $\mathbb{Z}^{d}$ for $d\geq 3$, it is known (see
[8, 10]) that

$\displaystyle T_{n}/\sqrt{n}$
$\displaystyle\xrightarrow{d}N(0,\sigma^{2}(2G(0)-1)),\enspace
L^{2}_{n,2}/n\xrightarrow{p}2G(0)-1\enspace\text{and}\enspace
V_{n}^{2}/n\xrightarrow{p}\sigma^{2},$

so that we have the self-normalized central limit theorem

$\displaystyle\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\xrightarrow{d}N(0,1).$

In [7], they proved that if $d\geq 4$ and there exists $\alpha>0$ and
$c_{\alpha}>0$ such that $\mathbb{P}(\xi\geq t)\leq
2e^{-c_{\alpha}t^{\alpha}}$ for $t>0$, then

$\displaystyle\mathbb{P}\otimes P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq
x\right)\sim 1-\Phi(x)$ (1.2)

uniformly for $x\in[0,O(n^{\tau})]$ and any $0<\tau<\alpha/(6\alpha+4)$. Here
$\Phi(\cdot)$ is the standard normal distribution function, and we write
$a_{n}\sim b_{n}$ if $\lim_{n\to\infty}a_{n}/b_{n}=1$ for positive sequences
$a_{n}$ and $b_{n}$. By self-normalizing, [7] was able to achieve a MDP while
only assuming sub-exponential tails on the scenery, which contrasts (1.1).
However, for a suitable range of $y_{n}$, one would expect

$\displaystyle-\infty<\liminf_{n\to\infty}y_{n}^{-2}\log\mathbb{P}\otimes
P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq
y_{n}\right)\leq\limsup_{n\to\infty}y_{n}^{-2}\log\mathbb{P}\otimes
P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq y_{n}\right)<0$ (1.3)

under only finite moment assumptions on the scenery, i.e.
$\mathbb{E}|\xi|^{\kappa}<\infty$ for some fixed $\kappa>0$. In the same
paper, the authors showed that if $\xi$ has the probability density function
$\frac{1}{2}\alpha(1+|t|)^{-1-\alpha}$ for some $\alpha>0$ and $(\log
n)^{1/2}\ll y_{n}\ll n^{1/2}$, then

$\displaystyle\liminf_{n\to\infty}y_{n}^{-2d/(d+2)}(\log
n)^{-2/(d+2)}\log\mathbb{P}\otimes
P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq y_{n}\right)>-\infty.$ (1.4)

Since $y_{n}^{2}\gg y_{n}^{2d/(d+2)}(\log n)^{2/(d+2)}$, this lower bound
shows that moderate deviations of the form (1.3) does not hold when
$y_{n}\gg(\log n)^{1/2}$ if one is only to assume finite moment conditions on
$\xi$.

The lower bound is achieved by considering the event in which the random walk
occupies the ball $\\{z\in\mathbb{Z}^{d}:|z|\leq R\\}$ for time $y_{n}^{2}$,
and taking each of the scenery values inside the ball to be of size $O(n)$.
The probability of the former event is roughly $\exp(-y_{n}^{2}/R^{2})$, and
for the latter event $n^{-R^{d}}=\exp(-R^{d}\log n)$. Since the random walk
and the scenery are independent of one other, we get the lower bound
$\exp(-y_{n}^{2}/R^{2}-R^{d}\log n)$ which, optimized over $R$, yields (1.4).
From this example, we observe that deviations of the self-normalized RWRS
depend on the interplay between the scenery and the random walk. Furthermore,
we see that this process is sensitive to the correlation of the local times
due to the heavy tails of the scenery.

Motivated by this phenomenon, in this paper we study self-normalized moderate
deviations for graphs other than the lattice. We expect that for graphs where
the simple random walk has weakly-dependent local times, moderate deviations
of the form (1.3) are attainable. A natural candidate for such graphs are
trees, since regeneration epochs of the random walk on the tree have
exponential tails (see Section 3 for definitions). Lastly, we also provide an
upper bound that complements (1.4).

##  2 Main results

Let $\mathbb{T}_{d}$ be the $d$-ary tree rooted at $o$, i.e. $\deg(v)=d+1$ for
$v\neq o$ and $\deg(o)=d$. In this paper we will always assume $d\geq 2$.
Since the simple random walk on $\mathbb{T}_{d}$ is transient, it follows that
for $G=\mathbb{T}_{d}$ we have $T_{n}/\sqrt{n}$ converges weakly to a normal
random variable. The following theorem provides precise asymptotics for the
self-normalized RWRS on $\mathbb{T}_{d}$ while only making finite moment
assumptions on the scenery.

######  Theorem 2.1.

Let $G=\mathbb{T}_{d}$ and let $y_{n}$ be a positive sequence such that
$y_{n}\to\infty$.

  1. 1.

Suppose that $\mathbb{E}\xi^{4}<\infty$ and $y_{n}=o(n^{1/6})$. We then have

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2}\log\mathbb{P}\otimes
P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq
y_{n}\right)\leq-\frac{c_{d}}{2},$ (2.1)

where $c_{d}$ is a positive constant independent of $n$, and $c_{d}\uparrow 1$
as $d\to\infty$.

  2. 2.

Suppose $\mathbb{E}\xi^{6}<\infty$ and $y_{n}=o(n^{1/6})$. We then have

$\displaystyle\liminf_{n\to\infty}y_{n}^{-2}\log\mathbb{P}\otimes
P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq y_{n}\right)\geq-\frac{1}{2}.$
(2.2)

In light of (1.4), the following theorem provides a sharp upper bound for the
self-normalized RWRS on the lattice when only assuming finite moment
conditions on the scenery.

######  Theorem 2.2.

Let $G=\mathbb{Z}^{d}$ for $d\geq 3$ and let $y_{n}$ be a positive sequence
such that $(\log n)^{1/2}\ll y_{n}\ll n^{1/6}$. If $\mathbb{E}\xi^{4}<\infty$,
then

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2d/(d+2)}(\log
n)^{-2/(d+2)}\log\mathbb{P}\otimes
P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq y_{n}\right)<0.$ (2.3)

######  Remark 2.1.

For Theorems 2.1 and 2.2 we assume that $y_{n}\ll n^{1/6}$. In this regime,
the deviation comes from the moderate deviation of the scenery. When $y_{n}\gg
n^{1/6}$, the deviation comes from large deviations for the local time
statistics $L_{n,2}$ and $L_{n,3}$, see Section 3 for definitions.

The rest of the paper is organized as follows. In Section 3, we study
concentration inequalities for different local time statistics that will aid
us in the proof of Theorem 2.1. Our main tool will be the regeneration
structure of the random walk on the tree. In Sections 4 and 5, we prove the
upper and lower bound of Theorem 2.1. In Section 6 we review the necessary
concentration inequalities for local time in the lattice, and in Section 7 we
prove Theorem 2.2.

##  3 Local time for $\mathbb{T}_{d}$

For the rest of the paper will write $P_{v}$ and $E_{v}$ when the random walk
is conditioned on starting at $v\in V$. We will also denote $a_{n}\asymp
b_{n}$ if
$0<\liminf_{n\to\infty}a_{n}/b_{n}\leq\limsup_{n\to\infty}a_{n}/b_{n}<\infty$
for positive sequences $a_{n}$ and $b_{n}$.

###  3.1 Regeneration times

Our proofs for the concentration of local times will utilize the regenerative
structure of the random walk on the tree. For $v\in V$, denote the level of
$v$ by $|v|$, which is the length of the unique geodesic between $v$ and $o$.
We define regeneration times as

$\displaystyle\tau_{1}=\inf\\{n\in\mathbb{N}:|S_{n}|\neq|S_{k}|\>\text{for
all}\>k<n\>\text{and}\>|S_{k}|\neq|S_{n-1}|\>\text{for all}\>k>n\\}$

and for $j\in\mathbb{N}$

$\displaystyle\tau_{j+1}=\inf\\{n>\tau_{j}:|S_{n}|\neq|S_{k}|\>\text{for
all}\>k<n\>\text{and}\>|S_{k}|\neq|S_{n-1}|\>\text{for all}\>k>n\\}.$

Regeneration times were studied in [6, 11] for biased random walks on Galton-
Watson trees. Rerunning the same proofs, we can conclude that the simple
random walk on $\mathbb{T}_{d}$ has infinitely many regeneration times such
that $\\{\tau_{j+1}-\tau_{j}\\}_{j\geq 1}$ is an i.i.d. sequence which is
independent of $\tau_{1}$, and that $\tau_{1}$ and $\tau_{2}-\tau_{1}$ have
exponential moments. The following lemma shows that as $d$ tends to infinity,
the tails of the regeneration times become lighter.

######  Lemma 3.1.

Define

$\displaystyle s_{d}=\sup\\{\lambda\geq
0:Ee^{\lambda\tau_{1}}<\infty\>\>\text{and}\>\>Ee^{\lambda(\tau_{2}-\tau_{1})}<\infty\\}.$

We then have $s_{d}\geq\frac{1}{3}\log((d+1)/3)+\frac{1}{3}-\frac{1}{d+1}$.

###### Proof.

Since we are only concerned with the levels of $\mathbb{T}_{d}$, we can
consider our random walk as a Markov chain on $\mathbb{N}_{0}$ starting at
$0$, with transition probabilities $p_{0,1}=1$, $p_{j,j+1}=d/(d+1)$ and
$p_{j,j-1}=1/(d+1)$ for $j\in\mathbb{N}$. We claim that

$\displaystyle\\{\tau_{1}=k\\}\subset\\{\text{RW took at least $\lfloor
k/3\rfloor$ steps backwards by time $k$}\\}.$

Observe that $|S_{\tau_{1}}|\leq\lfloor\tau_{1}/3\rfloor$. This is because for
every $m\in\mathbb{N}_{0}$ such that $m<|S_{\tau_{1}}|$, the random walk must
visit $m$ at least twice. Now suppose by contradiction the random walk took
less than $\lfloor k/3\rfloor$ steps backwards, which means the random walk
took more than $k-\lfloor k/3\rfloor$ steps forward. This implies
$|S_{\tau_{1}}|>\lfloor k/3\rfloor$, which is a contradiction. Applying the
Chernoff inequality to the binomial random variable $Z$ with parameters
$k\in\mathbb{N}_{0}$ and $1/(d+1)$, it follows that for all $x\geq k/(d+1)$

$\displaystyle
P(Z>x)\leq\exp\left(-x\log\left(\frac{x}{k/(d+1)}\right)+x-\frac{k}{d+1}\right).$

By our inclusion and the above inequality, we have

$\displaystyle P(\tau_{1}=k)\leq P(Z\geq
k/3)\leq\exp\left(-\frac{k}{3}\log((d+1)/3)+\frac{k}{3}-\frac{k}{d+1}\right).$

Hence when $\lambda<\frac{1}{3}\log((d+1)/3)+\frac{1}{3}-\frac{1}{d+1}$, which
is strictly positive when $d>2$, we have $Ee^{\lambda\tau_{1}}<\infty$. We are
left to bound $P(\tau_{2}-\tau_{1}=k)$. Rerunning the proof of Lemma 4.3 in
[6], we conclude that there exists a constant $C>0$ such that for every $k$ we
have $P(\tau_{2}-\tau_{1}=k)\leq C\cdot P(\tau_{1}=k)$. This finishes the
proof. ∎

###  3.2 Concentration inequalities

We introduce the various local time statistics of the simple random walk on
$\mathbb{T}_{d}$ used throughout the remainder of this paper. The one we are
most interested in is the size of the level sets of the local time

$\displaystyle L_{n}(t)=|\\{v\in V:\ell_{n}(v)>t\\}|.$

Let $\mathcal{R}_{n}=\\{S_{0},\ldots,S_{n-1}\\}$ be the range of the random
walk at time $n$. Setting $\lambda_{d}=s_{d}/2$, we define

$\displaystyle\mathcal{L}^{(n)}=\mathcal{L}=\left\\{v\in\mathcal{R}_{n}:\ell_{n}(v)<\frac{4}{\lambda_{d}}\log
n\right\\}$

to be the set of vertices with small local time. Another statistic that
appears throughout the proof is

$\displaystyle\mathscr{L}_{n}=\sum_{v\in\mathcal{L}^{c}}\ell_{n}(v).$

For $q\in\mathbb{N}$, denote the $q$-fold self-intersection local time by

$\displaystyle L_{n,q}=\left(\sum_{v\in V}\ell_{n}^{q}(v)\right)^{1/q}.$

The $q$-fold self-intersection local times often appear in the study of RWRS
because they quantify the number of times the random walk visits the same
sites, see [3] for a discussion for the case $\mathbb{Z}^{d}$. Throughout the
paper, we will frequently use the fact that

$\displaystyle L_{n,q}^{q}\geq n.$ (3.1)

Lastly, denote the maximum of the local times by

$\displaystyle L_{n,\infty}=\max_{v\in\mathcal{R}_{n}}\ell_{n}(v).$

We will denote $\theta_{k}=\tau_{k}-\tau_{k-1}$ for $k\geq 1$ and
$\theta_{1}=\tau_{1}$ to be the regeneration epochs. Our main ingredient for
deriving concentration inequalities for the local time will be the existence
of regeneration epochs, and that they have exponential moments.

######  Lemma 3.2.

Suppose $u\geq 1$ and $t\geq 1$. There exists a constant $M>0$ independent of
$u$ and $t$ such that for $\beta\in(0,\lambda_{d}/2]$ we have

$\displaystyle
E\exp\left(\beta\sum_{k=1}^{n}\theta_{k}\cdot\mathbbm{1}\\{\theta_{k}>t\\}\right)\leq\exp(Mn\exp(-\beta
t/2)),$ (3.2)

which implies

$\displaystyle P(L_{n}(t)\geq u)\leq\exp(Mn\exp(-\beta t/2)-\beta tu).$ (3.3)

###### Proof.

We begin by making a few observations. Firstly, at the $k$th regeneration
epoch $\theta_{k}$, there are at most $\lfloor\theta_{k}/t\rfloor$ vertices
$v$ satisfying $\ell_{n}(v)>t$. Secondly, any visited site is visited during a
single regeneration epoch. Since by time $n$ there are at most $n$
regeneration times, we get

$\displaystyle
L_{n}(t)\leq\sum_{k=1}^{n}\left\lfloor\theta_{k}/t\right\rfloor\cdot\mathbbm{1}\\{\theta_{k}>t\\}.$

Combining this inequality with the Chebyshev inequality, we have for any
$\beta\in(0,\lambda_{d}]$

$\displaystyle P(L_{n}(t)\geq u)$ $\displaystyle\leq
P\left(\sum_{k=1}^{n}\theta_{k}\cdot\mathbbm{1}\\{\theta_{k}>t\\}\geq
ut\right)$ $\displaystyle\leq\exp(-\beta
ut)\prod_{k=1}^{n}E\exp\left(\beta\theta_{k}\cdot\mathbbm{1}\\{\theta_{k}>t\\}\right),$

where the last inequality uses the fact that the regeneration epochs are
independent. We are left to bound the exponential moment. Again by the
Chebyshev inequality, we have $P(\theta_{k}>t)\leq M\exp(-\beta t)$ for some
positive constant $M$. Assuming $\beta\in(0,\lambda_{d}/2]$, we have

$\displaystyle\prod_{k=1}^{n}E\exp\left(\beta\theta_{k}\cdot\mathbbm{1}\\{\theta_{k}>t\\}\right)$
$\displaystyle\leq\prod_{k=1}^{n}\bigg{(}E[\exp\left(\beta\theta_{k}\right)\mathbbm{1}\\{\theta_{k}>t\\}]+1\bigg{)}$
$\displaystyle\leq\prod_{k=1}^{n}\bigg{(}(E\exp\left(2\beta\theta_{k}\right))^{1/2}P(\theta_{k}>t)^{1/2}+1\bigg{)}$
$\displaystyle\leq\exp(Mn\exp(-\beta t/2)).$

∎

######  Lemma 3.3.

There exists an $M>0$ such that for any $u\geq 1$

$\displaystyle P\left(\mathscr{L}_{n}\geq u\right)\leq
M\exp(-\lambda_{d}u/2).$

###### Proof.

We have the inequality
$\mathscr{L}_{n}\leq\sum_{k=1}^{n}\theta_{k}\cdot\mathbbm{1}\\{\theta_{k}>\frac{4}{\lambda_{d}}\log
n\\}$. The Chebyshev inequality combined with an application of (3.2) finishes
the proof. ∎

######  Lemma 3.4.

Suppose $x>1$. Then there exists a constant $c_{1}>0$ independent of $n$ and
$x$ such that

$\displaystyle P(L_{n,\infty}\geq x)\leq n\exp(-c_{1}(x-1)).$

###### Proof.

For $v\in V$, define $T^{+}_{v}=\inf\\{n\geq 1:S_{n}=v\\}$ to be the return
time of $v$ and let $p_{v}=P_{v}(T^{+}_{v}=+\infty)$ be the escape probability
starting at $v$. Observe that the probability of escaping from $o$ is the same
as the probability of escaping from $v$ conditioned on the event of
$\\{|S_{1}|>|v|\\}$. Therefore,

$\displaystyle
p_{o}=P_{v}(T^{+}_{v}=+\infty||S_{1}|>|v|)=\frac{P_{v}(T_{v}^{+}=+\infty,|S_{1}|>|v|)}{P_{v}(|S_{1}|>|v|)}\leq\frac{P_{v}(T_{v}^{+}=+\infty)}{P_{v}(|S_{1}|>|v|)}=\frac{d+1}{d}p_{v}.$

We now have the uniform lower bound $p_{v}\geq p_{o}d/(d+1).$ By the strong
Markov property, we have

$\displaystyle P_{v}(\ell_{n}(v)\geq
x)\leq(1-p_{v})^{x-1}\leq\left(1-\frac{d}{d+1}p_{o}\right)^{x-1}.$

Using the same proof as Lemma 18 in [8], we have

$\displaystyle P(L_{n,\infty}\geq x)\leq\sum_{v\in V}P(\ell_{n}(v)\geq x)$
$\displaystyle=\sum_{v\in
V}\sum_{k=1}^{n}P(T_{v}^{+}=k)P_{v}(\ell_{n-k}(v)\geq x)$
$\displaystyle\leq\sum_{v\in V}P_{v}(\ell_{n}(v)\geq
x)\sum_{k=1}^{n}P(T_{v}^{+}=k)$
$\displaystyle\leq\left(1-\frac{d}{d+1}p_{o}\right)^{x-1}\sum_{v\in
V}P(T_{v}^{+}\leq n).$

We finish by observing $\sum_{v\in V}P(T_{v}^{+}\leq n)\leq\sum_{v\in
V}\sum_{k=1}^{n}P(S_{k}=v)=n$. ∎

######  Lemma 3.5.

Fix an integer $q\geq 2$. There exist positive constants $B_{q}$ and $c_{q}$
such that

$\displaystyle\limsup_{n\to\infty}n^{-1/q}\log P\bigg{(}L_{n,q}^{q}\geq
B_{q}n\bigg{)}\leq-c_{q}.$

###### Proof.

Fix $B_{q}>0$ and define the events $E=\\{L_{n,q}^{q}\geq B_{q}n\\}$ and
$F=\\{L_{n,\infty}>n^{1/q}\\}$. By Lemma 3.4, we are left to bound $P(E\cap
F^{c})$, which we will do by bounding the probability that the level sets of
the local time are large. Define the sets

$\displaystyle\mathcal{D}_{k}=\left\\{v\in V:2^{k-1}<\ell_{n}(v)\leq
2^{k}\right\\}$

for $k=0,\ldots,\lceil\log_{2}(n^{1/q})\rceil=K_{2}$, and define the events

$\displaystyle D_{k}$
$\displaystyle=\left\\{|\mathcal{D}_{k}|>\frac{8Mn}{\lambda_{d}}\frac{e^{-\lambda_{d}2^{k-1}/8}}{2^{k-1}}\right\\}\enspace$
$\displaystyle\text{for}\enspace
k=0,\ldots,K_{1}=\lfloor\log_{2}(\frac{8}{\lambda_{d}}\log n)\rfloor$
$\displaystyle D_{k}$
$\displaystyle=\left\\{|\mathcal{D}_{k}|>\frac{n^{1/q}}{2^{k-1}}\right\\}\enspace$
$\displaystyle\text{for}\enspace k=K_{1}+1,\ldots,K_{2}.$

For $k=1,\ldots,K_{1}$, we apply (3.3) for $\beta=\lambda_{d}/4$ and get

$\displaystyle P(D_{k})\leq
P\left(L_{n}(2^{k-1})\geq\frac{8Mn}{\lambda_{d}}\frac{e^{-\lambda_{d}2^{k-1}/8}}{2^{k-1}}\right)\leq\exp\left(-Mne^{-\lambda_{d}2^{k-1}/8}\right)\leq\exp(-Mn^{1/2}).$

For $v\in\mathcal{D}_{k}$ for $k=K_{1}+1,\ldots,K_{2}$ we have
$\ell_{n}(v)\geq 4\log n/\lambda_{d}$, so we can apply (3.3) with parameter
$\beta=\lambda_{d}/2$ to get

$\displaystyle P(D_{k})\leq
P\left(L_{n}(2^{k-1})\geq\frac{n^{1/q}}{2^{k-1}}\right)\leq\exp\left(M-\frac{\lambda_{d}}{2}n^{1/q}\right).$

By the union bound it follows that there exists $c_{q}>0$ independent of $n$
such that

$\displaystyle\limsup_{n\to\infty}n^{-1/q}\log
P\left(\cup_{k=0}^{K_{2}}D_{k}\right)\leq-c_{q}.$

It is left to show $E\cap F^{c}\subset\left(\cup_{k=0}^{K_{2}}D_{k}\right)\cap
F^{c}$. On the event $F^{c}$, we have $V=\cup_{k=0}^{K_{2}}\mathcal{D}_{k}$.
Therefore, on the event $\left(\cup_{k=0}^{K_{2}}D_{k}\right)^{c}\cap F^{c}$,
we get

$\displaystyle
L_{n,q}^{q}\leq\sum_{k=0}^{K_{2}}2^{qk}|\mathcal{D}_{k}|\leq\frac{8Mn}{\lambda_{d}}\sum_{k=0}^{K_{1}}2^{(q-1)k+1}e^{-\lambda_{d}2^{k-1}/8}+n^{1/q}\sum_{k=K_{1}+1}^{K_{2}}2^{(q-1)k+1}\leq
B_{q}n$

for some constant $B_{q}$. ∎

##  4 Proof of the upper bound (2.1)

Our strategy will be to decompose $T_{n}/V_{n}$ into summands according to the
size of the local times and scenery values. The probability that $T_{n}/V_{n}$
is large will be rewritten as the probability that each summand is large. The
probability that the summand over small local time and scenery value is large
essentially reduces to the regime of bounded i.i.d. random variables, see
Lemma 4.1. The probability that the summands over large local time and large
scenery value is large will be bounded by the events $\mathscr{L}_{n}$ and
$|\mathcal{E}^{c}|$ are large, see definitions below.

Without loss of generality, assume $\mathbb{E}\xi^{2}=1$. Before we continue,
we introduce notation for the rest of the proof. Define the sets

$\displaystyle\mathcal{L}^{(n)}=\mathcal{L}=\left\\{v\in\mathcal{R}_{n}:\ell_{n}(v)<\frac{4}{\lambda_{d}}\log
n\right\\}\qquad\text{and}\qquad\mathcal{E}^{(n)}=\mathcal{E}=\left\\{v\in\mathcal{R}_{n}:\xi(v)<\frac{\sqrt{n}}{y_{n}\log^{2}n}\right\\},$

as well as the partial sums

$\displaystyle T_{n,1}$
$\displaystyle=\sum_{v\in\mathcal{L}\cap\mathcal{E}}\ell_{n}(v)\xi(v),$
$\displaystyle V^{2}_{n,1}$
$\displaystyle=\sum_{v\in\mathcal{L}\cap\mathcal{E}}\ell_{n}(v)\xi^{2}(v),$
$\displaystyle T_{n,2}$
$\displaystyle=\sum_{v\in\mathcal{L}\cap\mathcal{E}^{c}}\ell_{n}(v)\xi(v),$
$\displaystyle V^{2}_{n,2}$
$\displaystyle=\sum_{v\in\mathcal{L}\cap\mathcal{E}^{c}}\ell_{n}(v)\xi^{2}(v)$
$\displaystyle T_{n,3}$
$\displaystyle=\sum_{v\in\mathcal{L}^{c}}\ell_{n}(v)\xi(v),$ $\displaystyle
V^{2}_{n,3}$ $\displaystyle=\sum_{v\in\mathcal{L}^{c}}\ell_{n}(v)\xi^{2}(v),$

so that $T_{n}=T_{n,1}+T_{n,2}+T_{n,3}$ and
$V^{2}_{n}=V^{2}_{n,1}+V^{2}_{n,2}+V^{2}_{n,3}$. Before we prove the upper
bound, we need a few auxiliary results.

######  Lemma 4.1.

Suppose $1\ll y_{n}\ll n^{1/6}$ and $\mathbb{E}\xi^{4}<\infty$. We then have

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2}\log\mathbb{P}\otimes
P\left(\frac{T_{n,1}\sqrt{n}}{V_{n,1}L_{n,2}}\geq
y_{n}\right)\leq-\frac{1}{2}.$

######  Lemma 4.2.

Suppose that $\mathbb{E}|\xi^{m}|<\infty$ for some fixed $m\in\mathbb{N}$. For
$x>0$, we have

$\displaystyle\mathbb{P}\otimes P(|\mathcal{E}^{c}|\geq
x)\leq\left(e\mathbb{E}|\xi^{m}|\frac{y_{n}^{m}\log^{2m}(n)}{xn^{m/2-1}}\right)^{x}.$

###### Proof of (2.1).

Fix $\epsilon\in(0,1)$. We have

$\displaystyle\mathbb{P}\otimes P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq
y_{n}\right)$ $\displaystyle\leq\mathbb{P}\otimes
P\left(\frac{T_{n,1}\sqrt{n}}{V_{n,1}L_{n,2}}\geq\epsilon y_{n}\right)$
$\displaystyle+\mathbb{P}\otimes
P\left(\frac{T_{n,2}\sqrt{n}}{V_{n,2}L_{n,2}}\geq(1-\epsilon)y_{n}/2\right)$
$\displaystyle+\mathbb{P}\otimes
P\left(\frac{T_{n,3}\sqrt{n}}{V_{n,3}L_{n,2}}\geq(1-\epsilon)y_{n}/2\right)$
$\displaystyle\eqqcolon P_{1}+P_{2}+P_{3}.$

To bound $P_{1}$, we simply apply Lemma 4.1

$\displaystyle P_{1}=\mathbb{P}\otimes
P\left(\frac{T_{n,1}\sqrt{n}}{V_{n,1}L_{n,2}}\geq\epsilon
y_{n}\right)\leq\exp\left(-\frac{\epsilon^{2}}{2}y_{n}^{2}(1-o(1))\right).$

To bound $P_{2}$, we observe that by (3.1) and the Cauchy-Schwartz inequality,

$\displaystyle\frac{T_{n,2}\sqrt{n}}{V_{n,2}L_{n,2}}\leq\frac{T_{n,2}}{V_{n,2}}=\frac{\sum_{v\in\mathcal{L}\cap\mathcal{E}^{c}}\ell_{n}(v)\xi(v)}{\sqrt{\sum_{v\in\mathcal{L}\cap\mathcal{E}^{c}}\ell_{n}(v)\xi^{2}(v)}}\leq\sqrt{\sum_{v\in\mathcal{L}\cap\mathcal{E}^{c}}\ell_{n}(v)}\leq\sqrt{\frac{4}{\lambda_{d}}\log
n|\mathcal{E}^{c}|}.$

Combining the above inequality and Lemma 4.2 yields

$\displaystyle
P_{2}=\mathbb{P}\left(\frac{T_{n,2}\sqrt{n}}{V_{n,2}L_{n,2}}\geq(1-\epsilon)y_{n}/2\right)$
$\displaystyle\leq\mathbb{P}\left(|\mathcal{E}^{c}|\geq(1-\epsilon)^{2}\frac{\lambda_{d}}{16}\frac{y_{n}^{2}}{\log
n}\right)$
$\displaystyle\leq\left(\frac{e\mathbb{E}\xi^{4}}{(1-\epsilon)^{2}\lambda_{d}/16}\frac{y_{n}^{2}\log^{9}n}{n}\right)^{(1-\epsilon)^{2}\frac{\lambda_{d}}{16}\frac{y_{n}^{2}}{\log
n}}$
$\displaystyle=\exp\left(-(1-\epsilon)^{2}\frac{\lambda_{d}}{16}y_{n}^{2}\left(\frac{\log(n/y_{n}^{2})}{\log
n}-o(1)\right)\right)$
$\displaystyle\leq\exp\left(-(1-\epsilon)^{2}\frac{\lambda_{d}}{24}y_{n}^{2}(1-o(1))\right).$

To bound $P_{3}$, we again use (3.1) and the Cauchy-Schwartz inequality

$\displaystyle\frac{T_{n,3}\sqrt{n}}{V_{n,3}L_{n,2}}\leq\frac{T_{n,3}}{V_{n,3}}=\frac{\sum_{v\in\mathcal{L}^{c}}\ell_{n}(v)\xi(v)}{\sqrt{\sum_{v\in\mathcal{L}^{c}}\ell_{n}(v)\xi^{2}(v)}}\leq\sqrt{\sum_{v\in\mathcal{L}^{c}}\ell_{n}(v)}=\sqrt{\mathscr{L}_{n}}.$

Applying this as well as Lemma 3.3 gives us

$\displaystyle
P_{3}=P\left(\frac{T_{n,3}\sqrt{n}}{V_{n,3}L_{n,2}}\geq(1-\epsilon)y_{n}/2\right)\leq
P\left(\mathscr{L}_{n}\geq(1-\epsilon)^{2}y_{n}^{2}/4\right)\leq
M\exp\left(-(1-\epsilon)^{2}\frac{\lambda_{d}}{8}y_{n}^{2}\right).$

We conclude that for $d\geq 2$

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2}\log\mathbb{P}\otimes
P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq
y_{n}\right)<-\min\left\\{\frac{\epsilon^{2}}{2},(1-\epsilon)^{2}\frac{\lambda_{d}}{24},(1-\epsilon)^{2}\frac{\lambda_{d}}{8}\right\\}.$

Recall from Lemma 3.1 that $\lambda_{d}\uparrow\infty$ as $d\to\infty$. Hence
for $d$ large enough we can let $\epsilon=1-(24/\lambda_{d})^{1/2}$, and get

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2}\log\mathbb{P}\otimes
P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq
y_{n}\right)\leq-\frac{1}{2}(1-(24/\lambda_{d})^{1/2})^{2}.$

Letting $c_{d}=(1-(24/\lambda_{d})^{1/2})^{2}$ finishes the proof.

∎

We are left to prove Lemmas 4.1 and 4.2. The first lemma is a self-normalized
moderate deviation result; since our sum is over vertices with small local
time, the proof is very similar to the i.i.d. regime. The proof of the second
lemma is a straightforward Chernoff inequality.

###### Proof of Lemma 4.1.

Recall the local time statistics
$\mathscr{L}_{n}=\sum_{v\in\mathcal{L}^{c}}\ell_{n}(v)$,
$L_{n,2}^{2}=\sum_{v\in V}\ell_{n}^{2}(v)$ and $L_{n,3}^{3}=\sum_{v\in
V}\ell_{n}^{3}(v)$. We begin by defining the atypical event

$\displaystyle
A=\left\\{L_{n,2}^{2}>B_{2}n\right\\}\cup\left\\{L_{n,3}^{3}>B_{3}n\right\\}\cup\\{\mathscr{L}_{n}\geq
y_{n}^{2}\log n\\}.$

Since $y_{n}=o(n^{1/6})$, by Lemmas 3.5 and 3.3 we have

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2}\log P(A)=-\infty.$

Hence we are left to bound

$\displaystyle\mathbb{P}\otimes
P\left(\left\\{\frac{T_{n,1}\sqrt{n}}{V_{n,1}L_{n,2}}\geq y_{n}\right\\}\cap
A^{c}\right).$

Fix $\delta\in(0,1)$. We decompose our probability with respect to the size of
$V_{n,1}$:

$\displaystyle\mathbb{P}\otimes
P\left(\left\\{\frac{T_{n,1}\sqrt{n}}{V_{n,1}L_{n,2}}\geq y_{n}\right\\}\cap
A^{c}\right)$ $\displaystyle\leq\mathbb{P}\otimes
P\left(\\{V_{n,1}^{2}\leq\delta n\\}\cap A^{c}\right)+\mathbb{P}\otimes
P\left(\left\\{\frac{T_{n,1}}{L_{n,2}}\geq\delta^{1/2}y_{n}\right\\}\cap
A^{c}\right)$ $\displaystyle\eqqcolon I_{1}+I_{2}.$

We first show that $I_{1}$ is negligible. By the Chebyshev inequality, for any
$\kappa>0$ we have

$\displaystyle\mathbb{P}(V_{n,1}^{2}<\delta n)$
$\displaystyle\leq\exp(\kappa\delta n)\mathbb{E}[\exp(-\kappa V_{n,1}^{2})]$
$\displaystyle=\exp(\kappa\delta
n)\prod_{v\in\mathcal{L}}\mathbb{E}[\exp(-\kappa\ell_{n}(v)\xi^{2}(v)\mathbbm{1}\\{v\in\mathcal{E}\\})].$

By monotone convergence, we have
$\mathbb{E}[\xi^{2}(v)\mathbbm{1}\\{v\in\mathcal{E}\\}]=1-o(1)$. Using this,
and that $e^{-x}\leq 1-x+x^{2}/2$ for $x\geq 0$, we have

$\displaystyle\mathbb{E}[\exp(-\kappa\ell_{n}(v)\xi^{2}(v)\mathbbm{1}\\{v\in\mathcal{E}\\})]$
$\displaystyle\leq\mathbb{E}[1-\kappa\ell_{n}(v)\xi^{2}(v)\mathbbm{1}_{v\in\mathcal{E}}+{\kappa^{2}}\ell_{n}^{2}(v)\xi^{4}(v)\mathbbm{1}\\{v\in\mathcal{E}\\}/2]$
$\displaystyle\leq
1-\kappa\ell_{n}(v)(1-o(1))+\mathbb{E}[\xi^{4}]\kappa^{2}\ell_{n}^{2}(v)/2$
$\displaystyle\leq\exp(-\kappa\ell_{n}(v)(1-o(1))+\mathbb{E}[\xi^{4}]\kappa^{2}\ell_{n}^{2}(v)/2).$

On the event $A^{c}$, we have $\sum_{v\in\mathcal{L}}\ell_{n}(v)\geq
n-y_{n}^{2}\log n$. We then get

$\displaystyle I_{1}$ $\displaystyle\leq\exp(\kappa\delta
n)E\left[\exp\left(-\kappa\sum_{v\in\mathcal{L}}\ell_{n}(v)(1-o(1))+\mathbb{E}[\xi^{4}]\kappa^{2}\sum_{v\in\mathcal{L}}\ell_{n}^{2}(v)/2\right)\mathbbm{1}_{A^{c}}\right]$
$\displaystyle\leq\exp(-\kappa(1-\delta)n(1-o(1))+B_{2}\mathbb{E}[\xi^{4}]\kappa^{2}n/2).$

Optimizing over $\kappa$ gives the bound

$\displaystyle
I_{1}\leq\exp\left(-\frac{(1-\delta)^{2}}{2B_{2}\mathbb{E}[\xi^{4}]}n(1-o(1))\right),$

and since $y_{n}=o(n^{1/6})$, we have for ever $\delta\in(0,1)$

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2}\log I_{1}=-\infty.$

The rest of the proof is left to bound $I_{2}$. Applying Chebyshev’s
inequality with $\delta^{1/2}y_{n}$, we have

$\displaystyle I_{2}$ $\displaystyle\leq\exp(-\delta
y_{n}^{2})\cdot\mathbb{E}\otimes
E\left[\exp(\delta^{1/2}y_{n}T_{n,1}/L_{n,2})\mathbbm{1}_{A^{c}}\right]$
$\displaystyle=\exp(-\delta y_{n}^{2})\cdot
E\left[\prod_{v\in\mathcal{L}}\mathbb{E}\left[\exp\left(\delta^{1/2}y_{n}\frac{\ell_{n}(v)}{L_{n,2}}\xi(v)\mathbbm{1}\\{v\in\mathcal{E}\\}\right)\right]\mathbbm{1}_{A^{c}}\right].$

Since $L_{n,2}\geq n^{1/2}$, for $v\in\mathcal{L}$ we have

$\displaystyle\delta^{1/2}y_{n}\frac{\ell_{n}(v)}{L_{n,2}}\xi(v)\mathbbm{1}\\{v\in\mathcal{E}\\}\leq\frac{4\delta^{1/2}}{\lambda_{d}\log
n}.$

There exists a constant $C>0$ such that for any $x\leq 1$,

$\displaystyle e^{x}\leq 1+x+x^{2}/2+C|x|^{3}.$

By this, and that $\mathbb{E}[\xi(v)\mathbbm{1}\\{v\in\mathcal{E}\\}]\leq 0$,
we have for large enough $n$

$\displaystyle I_{2}\leq$ $\displaystyle\exp(-\delta
y_{n}^{2})E\left[\prod_{v\in\mathcal{L}}\left(1+\frac{\delta}{2}\frac{\ell^{2}_{n}(v)}{L^{2}_{n,2}}y_{n}^{2}+O(1)\frac{\ell^{3}_{n}(v)}{L_{n,2}^{3}}y_{n}^{3}\right)\mathbbm{1}_{A^{c}}\right]$
$\displaystyle\leq$ $\displaystyle\exp(-\delta
y_{n}^{2})E\left[\prod_{v\in\mathcal{L}}\exp\left(\frac{\delta}{2}\frac{\ell^{2}_{n}(v)}{L^{2}_{n,2}}y_{n}^{2}+O(1)\frac{\ell^{3}_{n}(v)}{L_{n,2}^{3}}y_{n}^{3}\right)\mathbbm{1}_{A^{c}}\right]$
$\displaystyle\leq$ $\displaystyle\exp(-\delta
y_{n}^{2}/2)E\left[\exp\left(O(1)\frac{L_{n,3}^{3}}{L_{n,2}^{3}}y_{n}^{3}\right)\mathbbm{1}_{A^{c}}\right].$

Since $L^{3}_{n,3}\asymp n$ and $L^{2}_{n,2}\asymp n$ on the event $A^{c}$, as
well as that $y_{n}=o(n^{1/6})$, we have the bound

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2}\log I_{2}\leq-\frac{\delta}{2}.$

Taking $\delta\uparrow 1$ finishes the proof. ∎

###### Proof of Lemma 4.2.

Observe that

$\left\\{\mathbbm{1}\left\\{|\xi(v)|>\frac{\sqrt{n}}{y_{n}\log^{2}n}\right\\}:v\in\mathcal{R}_{n}\right\\}$

are i.i.d. random variables with respect to $\mathbb{P}$, and that by Markov’s
inequality we have

$\displaystyle\mathbb{P}\left(|\xi(v)|\geq\frac{\sqrt{n}}{y_{n}\log^{2}n}\right)\leq\mathbb{E}|\xi^{m}|\frac{y_{n}^{m}\log^{2m}(n)}{n^{m/2}}.$

Applying the Chernoff inequality to the binomial random variable $Z$ with
parameters $n\in\mathbb{N}_{0}$ and $p\in[0,1]$, it follows that for all $x>0$

$\displaystyle P(Z>x)\leq\left(\frac{enp}{x}\right)^{x}.$

Using this, and that $|\mathcal{R}_{n}|\leq n$ $P$-a.s, we have

$\displaystyle\mathbb{P}\otimes P\left(|\mathcal{E}^{c}|\geq x\right)$
$\displaystyle=E\left[\mathbb{P}\left(\sum_{v\in\mathcal{R}_{n}}\mathbbm{1}\left\\{|\xi(v)|>\frac{\sqrt{n}}{y_{n}\log^{2}n}\right\\}>x\right)\right]$
$\displaystyle\leq
E\left[\left(\frac{e|\mathcal{R}_{n}|\mathbb{P}\left(|\xi(v)|\geq\frac{\sqrt{n}}{y_{n}\log^{2}n}\right)}{x}\right)^{x}\right]$
$\displaystyle\leq\left(\frac{en\mathbb{P}\left(|\xi(v)|\geq\frac{\sqrt{n}}{y_{n}\log^{2}n}\right)}{x}\right)^{x}$
$\displaystyle\leq\left(e\mathbb{E}|\xi^{m}|\frac{y_{n}^{m}\log^{2m}(n)}{xn^{m/2-1}}\right)^{x}.$

∎

##  5 Proof of the lower bound (2.2)

The following proof is a straightforward application of the techniques used in
the proof of Theorem 2.2 in [7]. Without loss of generality, assume
$\mathbb{E}\xi^{2}=1$. Let $x,y$ and $b$ be positive numbers. By the the
Cauchy-Schwartz inequality we have

$\displaystyle xy\leq\frac{1}{2}\left(\frac{x^{2}}{b}+y^{2}b\right).$

Letting $b=y_{n}L_{n,2}/n$, $x=y_{n}L_{n,2}/\sqrt{n}$ and $y=V_{n}$, we get

$\displaystyle\mathbb{P}\otimes P\left(T_{n}\geq
V_{n}\frac{y_{n}L_{n,2}}{\sqrt{n}}\right)$ $\displaystyle\geq$
$\displaystyle\mathbb{P}\otimes
P\left(T_{n}\geq\frac{1}{2b}\left(b^{2}V^{2}_{n}+y_{n}^{2}\frac{L^{2}_{n,2}}{n}\right)\right)$
$\displaystyle=$ $\displaystyle\mathbb{P}\otimes P\left(\sum_{v\in
V}\ell_{n}(v)(2b\xi(v)-b^{2}\xi^{2}(v))\geq
y_{n}^{2}\frac{L^{2}_{n,2}}{n}\right)$ $\displaystyle\geq$ $\displaystyle
E\left[\mathbb{P}\left(\sum_{v\in V}\ell_{n}(v)(2b\xi(v)-b^{2}\xi^{2}(v))\geq
y_{n}^{2}\frac{L^{2}_{n,2}}{n}\right)\mathbbm{1}\\{L_{n,2}^{2}\leq
B_{2}n,L_{n,3}^{3}\leq B_{3}n\\}\right].$

We are left to bound the inner probability, for which we will use Theorem 2
from [12]. Assume the random walk is fixed such that

$\displaystyle L_{n,2}^{2}\leq B_{2}n\qquad\text{and}\qquad L_{n,3}^{3}\leq
B_{3}n.$ (5.1)

Defining $\eta(v)=2b\xi(v)-b^{2}\xi^{2}(v)$, we have

$\displaystyle\mathbb{P}\left(\sum_{v\in
V}\ell_{n}(v)(2b\xi(v)-b^{2}\xi^{2}(v))\geq
y_{n}^{2}\frac{L^{2}_{n,2}}{n}\right)=\mathbb{P}\left(\sum_{v\in
V}\ell_{n}(v)(\eta(v)-\mathbb{E}\eta(v))\geq
2y_{n}^{2}\frac{L^{2}_{n,2}}{n}\right).$

Define

$\displaystyle M_{n}^{2}$ $\displaystyle=\sum_{v\in
V}\ell_{n}^{2}(v)\mathbb{E}(\eta(v)-\mathbb{E}\eta(v))^{2},$
$\displaystyle\Gamma_{n}$ $\displaystyle=\sum_{v\in
V}\ell_{n}^{3}(v)\mathbb{E}|\eta(v)-\mathbb{E}\eta(v)|^{3},$ $\displaystyle
Q_{n}$ $\displaystyle=\frac{\Gamma_{n}}{M_{n}^{3}},$ $\displaystyle x$
$\displaystyle=\frac{2y_{n}^{2}L_{n,2}^{2}}{nM_{n}}.$

Since $L_{n,q}^{q}\geq n$ for $q=2$ and $q=3$, by (5.1) we have
$L^{2}_{n,2}\asymp n$ and $L^{3}_{n,3}\asymp n$. We thus get

$\displaystyle
M_{n}^{2}=L_{n,2}^{2}(4b^{2}-4b^{3}\mathbb{E}\xi^{3}+b^{4}(\mathbb{E}\xi^{4}-1))\asymp
y_{n}^{2}\qquad\text{and}\qquad\Gamma_{n}\asymp
L_{n,3}^{3}b^{3}\asymp\frac{y_{n}^{3}}{n^{1/2}},$

which in turn implies

$\displaystyle Q_{n}\asymp\frac{1}{n^{1/2}}\qquad\text{and}\qquad x\asymp
y_{n}\ll n^{1/2}\asymp Q_{n}^{-1}.$

It now follows from Theorem 2.1 in [12] that there exists positive constants
$c_{1}$ and $c_{2}$ independent of $n$ such that

$\displaystyle\mathbb{P}\left(\sum_{v\in
V}\ell_{n}(v)(\eta(v)-\mathbb{E}\eta(v))\geq\frac{2y_{n}^{2}L_{n,2}^{2}}{n}\right)$
$\displaystyle\geq\left(1-\Phi\left(\frac{2y_{n}^{2}L_{n,2}^{2}}{nM_{n}}\right)\right)\left(1-c_{1}Q_{n}x\right)\exp\left(-c_{2}Q_{n}x^{3}\right)$
$\displaystyle=\left(1-\Phi\left(\frac{2y_{n}^{2}L_{n,2}^{2}}{nM_{n}}\right)\right)\left(1-o(1)\right)\exp\left(-o(1)\right),$

since $Q_{n}x^{3}\asymp y_{n}^{3}/n^{1/2}$ and $y_{n}=o(n^{1/6})$. Since
$L_{n,2}\asymp n^{1/2}$ and $y_{n}=o(n^{1/4})$, we have

$\displaystyle M_{n}=2\frac{L_{n,2}^{2}y_{n}}{n}(1-o(1)).$

By Lemma 3.5 and that $y_{n}=o(n^{1/4}),$ we get $P\left(\\{L_{n,2}^{2}\leq
B_{2}n\\}\cap\\{L_{n,3}^{3}\leq B_{3}n\\}\right)\sim 1$. Putting everything
together, we have

$\displaystyle\mathbb{P}\otimes P\left(\frac{T_{n}\sqrt{n}}{V_{n}L_{n,2}}\geq
y_{n}\right)$
$\displaystyle\geq(1-o(1))(1-\Phi(y_{n}))P\left(\\{L_{n,2}^{2}\leq
B_{2}n\\}\cap\\{L_{n,3}^{3}\leq B_{3}n\\}\right)$ $\displaystyle\sim
1-\Phi(y_{n}).$

This finishes the proof.

##  6 Local time for $\mathbb{Z}^{d}$

We review the necessary concentration inequalities required for the proof of
Theorem 2.2. The following inequality was provided in Proposition 3.3 in [4].

######  Lemma 6.1.

Define $L_{n}(t)=|\\{z\in\mathbb{Z}^{d}:\ell_{n}(z)>t\\}|$. There exists
positive constants $c_{1},c_{2},c_{3}$ such that for $t>c_{1}\log n$ and
$u\geq 1$, we have

$\displaystyle P(L_{n}(t)>u)\leq c_{3}\exp(-c_{2}\cdot tu^{1-2/d}).$

Based on this last lemma, we easily get the following estimate which will be
needed in the proof of Theorem 2.2.

######  Lemma 6.2.

Suppose $y_{n}^{2}\gg\log n$ and let $t_{*}=y_{n}^{4/(d+2)}(\log
n)^{d/(d+2)}$. Then there exists a positive constant $C_{1}$ such that

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2d/(d+2)}(\log
n)^{-2/(d+2)}P\left(\sum_{z:\ell_{n}(z)>t_{*}}\ell_{n}(z)\geq
y_{n}^{2}\right)\leq-C_{1}.$

###### Proof.

Define the sets

$\displaystyle\mathcal{D}_{k}=\\{z\in\mathbb{Z}^{d}:2^{k}t_{*}<\ell_{n}(z)\leq
2^{k+1}t_{*}\\}$

for $k=0,\ldots,K$, where $K$ satisfies $2^{K+1}t_{*}=y_{n}^{2d/(d+2)}(\log
n)^{2/(d+2)}$. Let $a_{k}=\epsilon\cdot y_{n}^{2}2^{-2k/(d-2)}$, where
$\epsilon>0$ is chosen such that $\sum_{k=0}^{\infty}a_{k}\leq y_{n}^{2}$. We
have

$\displaystyle P\left(\sum_{z:\ell_{n}(z)>t_{*}}\ell_{n}(z)\geq
y_{n}^{2}\right)$
$\displaystyle\leq\sum_{k=0}^{K}P\left(\sum_{z\in\mathcal{D}_{k}}\ell_{n}(z)\geq
a_{k}\right)+P\left(L_{n,\infty}>2^{K+1}t_{*}\right).$

Reviewing the proof of Lemma 3.4, we see that the conclusion holds for any
graph $G$ that satisfies $\inf_{v\in V}P_{v}(T_{v}^{+}=\infty)>0$. Since this
applies to the graph $\mathbb{Z}^{d}$ for $d\geq 3$, we can bound the second
term on the right-hand side by Lemma 3.4. The first term on the right-hand
side is bounded by

$\displaystyle\sum_{k=0}^{K}P\left(|\mathcal{D}_{k}|\geq\frac{a_{k}}{2^{k+1}t_{*}}\right)$
$\displaystyle\leq\sum_{k=0}^{K}\exp\left(-\left(\frac{a_{k}}{2}\right)^{1-2/d}(2^{k}t_{*})^{2/d}\right)$
$\displaystyle\leq(K+1)\exp(-C_{2}y_{n}^{2d/(d+2)}(\log n)^{2/(d+2)}),$

where the first inequality follows from Lemma 6.1 and the fact that
$t_{*}\gg\log n$ since we assume $y_{n}^{2}\gg\log n$. We finish by observing
that combinatorial factor is negligible since $K=O(\log y_{n})$. ∎

As in the proof of 2.1, we will need large deviations for the self-
intersection local time
$L_{n,2}^{2}=\sum_{z\in\mathbb{Z}^{d}}\ell_{n}^{2}(z)$. The following result
follows from Proposition 1.1 and Remark 1.3 in [1], as well as Proposition 1.5
in [3].

######  Lemma 6.3.

Let $\\{S_{n}:n\in\mathbb{N}_{0}\\}$ be the simple random walk on
$\mathbb{Z}^{d}$ and suppose $d\geq 3$. For $y>2G(0)-1$, we have

$\displaystyle\limsup_{n\to\infty}n^{-1/3}\log P(L^{2}_{n,2}\geq y\cdot n)<0.$

##  7 Proof of Theorem 2.2

We begin by defining the sets

$\displaystyle\mathcal{E}^{(n)}=\mathcal{E}=\left\\{z\in\mathcal{R}_{n}:\xi(z)\leq\frac{\sqrt{n}}{y_{n}\log^{2}n}\right\\}\qquad\text{and}\qquad\mathcal{L}^{(n)}=\mathcal{L}=\left\\{z\in\mathbb{Z}^{d}:\ell_{n}(z)\leq
y_{n}^{4/(d+2)}(\log n)^{d/(d+2)}\right\\}.$

We define the partial sums

$\displaystyle T_{n,1}$
$\displaystyle=\sum_{z\in\mathcal{L}\cap\mathcal{E}}\ell_{n}(z)\xi(z),$
$\displaystyle V^{2}_{n,1}$
$\displaystyle=\sum_{z\in\mathcal{L}\cap\mathcal{E}}\ell_{n}(z)\xi^{2}(z),$
$\displaystyle T_{n,2}$
$\displaystyle=\sum_{z\in\mathcal{L}\cap\mathcal{E}^{c}}\ell_{n}(z)\xi(z),$
$\displaystyle V^{2}_{n,2}$
$\displaystyle=\sum_{z\in\mathcal{L}\cap\mathcal{E}^{c}}\ell_{n}(z)\xi^{2}(z)$
$\displaystyle T_{n,3}$
$\displaystyle=\sum_{z\in\mathcal{L}^{c}}\ell_{n}(z)\xi(z),$ $\displaystyle
V^{2}_{n,3}$ $\displaystyle=\sum_{z\in\mathcal{L}^{c}}\ell_{n}(z)\xi^{2}(z).$

Applying (3.1), we have

$\displaystyle\mathbb{P}\otimes P\left(T_{n}\sqrt{n}/(V_{n}L_{n,2})\geq
y_{n}\right)\leq\mathbb{P}\otimes P\left(T_{n}/V_{n}\geq y_{n}\right)$
$\displaystyle\leq$ $\displaystyle\mathbb{P}\otimes P(T_{n,1}/V_{n}\geq
y_{n}/3)+\mathbb{P}\otimes P(T_{n,2}/V_{n}\geq y_{n}/3)+\mathbb{P}\otimes
P(T_{n,3}/V_{n}\geq y_{n}/3).$

As in the proof of (2.1), we apply the Cauchy-Schwartz inequality and get that
this bounded by

$\displaystyle\mathbb{P}\otimes P(T_{n,1}/V_{n}\geq y_{n}/3)+\mathbb{P}\otimes
P\left(|\mathcal{E}^{c}|\geq y_{n}^{2d/(d+2)}\log
n^{-d/(d+2)}/9\right)+P\left(\sum_{z\in\mathcal{L}^{c}}\ell_{n}(z)\geq
y_{n}^{2}/9\right).$

Reviewing the proof of Lemma 4.2, we see that the conclusion holds for any
random walk that satisfies $|\mathcal{R}_{n}|\leq n$. Since this holds for the
simple random walk on $\mathbb{Z}^{d}$, we can apply Lemma 4.2 with the
assumption $\mathbb{E}\xi^{4}<\infty$, to get

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2d/(d+2)}(\log
n)^{-2/(d+2)}\log\mathbb{P}\otimes P(|\mathcal{E}^{c}|\geq
y_{n}^{2d/(d+2)}\log n^{-d/(d+2)}/9)<0.$

By Lemma 6.2, we have

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2d/(d+2)}(\log n)^{-2/(d+2)}\log
P\left(\sum_{z\in\mathcal{L}^{c}}\ell_{n}(z)\geq y_{n}^{2}/9\right)<0.$

The rest of the proof is nearly identical to the proof of Lemma 4.1. For
$B>2G(0)-1$, we have

$\displaystyle\mathbb{P}\otimes P\left(T_{n,1}/V_{n}\geq y_{n}\right)$
$\displaystyle\leq\mathbb{P}\otimes P\left(\\{V_{n}^{2}\leq
n/4\\}\cap\\{L_{n,2}^{2}\leq Bn\\}\right)$ $\displaystyle+\mathbb{P}\otimes
P\left(\\{T_{n,1}/n^{1/2}\geq y_{n}/2\\}\cap\\{L^{2}_{n,2}\leq
Bn\\}\right)+P(L_{n,2}^{2}>Bn)$ $\displaystyle\eqqcolon I_{1}+I_{2}+I_{3}.$

By Lemma 6.3 and that $y_{n}=o(n^{1/6})$, we have

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2d/(d+2)}(\log n)^{-2/(d+2)}\log
I_{3}=-\infty,$

and by the same proof as in Lemma 4.1, we have

$\displaystyle\limsup_{n\to\infty}y_{n}^{-2d/(d+2)}(\log n)^{-2/(d+2)}\log
I_{1}=-\infty,$

and so we are left to bound $I_{2}$. By Chebyshev’s inequality, for any
$\alpha_{n}>0$ we have

$\displaystyle I_{2}\leq\exp(-y_{n}\alpha_{n}/2)\cdot
E\left[\prod_{z\in\mathcal{L}}\mathbb{E}\left[\exp\left(\ell_{n}(z)\xi(z)\frac{\alpha_{n}}{n^{1/2}}\mathbbm{1}\\{z\in\mathcal{E}\\}\right)\right]\mathbbm{1}\\{L_{n,2}^{2}\leq
B_{2}n\\}\right].$

We set $\alpha_{n}=y_{n}^{(d-2)/(d+2)}(\log n)^{2/(d+2)}$, and observe that
there exists $C>0$ such that for $z\in\mathcal{L}$, we have

$\displaystyle\ell_{n}(z)\xi(z)\frac{\alpha_{n}}{n^{1/2}}\mathbbm{1}\\{z\in\mathcal{E}\\}\leq
C/\log n.$

There exists a constant $C>0$ such that for $x\leq 1$ we have $e^{x}\leq
1+x+Cx^{2}$. Combining both facts yields the inequality

$\displaystyle\mathbb{E}\left[\exp\left(\ell_{n}(z)\xi(z)\frac{\alpha_{n}}{n^{1/2}}\mathbbm{1}\\{z\in\mathcal{E}\\}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[1+\ell_{n}(z)\xi(z)\frac{\alpha_{n}}{n^{1/2}}\mathbbm{1}\\{z\in\mathcal{E}\\}+C\frac{\ell^{2}_{n}(z)}{n}\xi^{2}(z)\alpha_{n}^{2}\mathbbm{1}\\{z\in\mathcal{E}\\}\right]$
$\displaystyle\leq\exp\left(C\frac{\ell_{n}^{2}(z)}{n}\alpha_{n}^{2}\right).$

We thus have

$\displaystyle I_{2}$ $\displaystyle\leq\exp(-y_{n}^{2d/(d+2)}(\log
n)^{2/(d+2)}/2+CB_{2}y_{n}^{(2d-4)/(d+2)}(\log n)^{4/(d+2)}).$

Observe that $y_{n}^{2d/(d+2)}(\log n)^{2/(d+2)}\gg y_{n}^{(2d-4)/(d+2)}(\log
n)^{4/(d+2)}$ precisely when $y^{2}_{n}\gg\log n$, which completes the proof.

Acknowledgements. I would like to thank my M.Sc. advisor Ofer Zeitouni for his
guidance and support throughout all stages of this work. This project has
received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No.
692452). Thank you to both reviewers for providing detailed feedback that
greatly improved the content and flow of the manuscript.

## References

  * [1] Asselah, A. Large deviations estimates for self-intersection local times for simple random walk in $\mathbb{Z}^{3}$.  Probability theory and related fields 141, 1-2 (2008), 19–45.
  * [2] Asselah, A., and Castell, F. A note on random walk in random scenery.  Annales de l’I.H.P. Probabilités et statistiques 43, 2 (2007), 163–173.
  * [3] Asselah, A., and Castell, F. Random walk in random scenery and self-intersection local times in dimensions d $\geq$ 5\.  Probability Theory and Related Fields 138, 1-2 (2 2007), 1–32.
  * [4] Asselah, A., and Schapira, B. Moderate deviations for the range of a transient random walk. II.  arXiv:1909.01925, 2019.
  * [5] Borodin, A. N. Limit theorems for sums of independent random variables defined on a nonrecurrent random walk.  Journal of Soviet Mathematics 20, 3 (Oct 1982), 2130–2137.
  * [6] Dembo, A., Gantert, N., Peres, Y., and Zeitouni, O. Large deviations for random walks on galton–watson trees: averaging and uncertainty.  Probability Theory and Related Fields 122, 2 (Feb 2002), 241–288.
  * [7] Feng, X., Shao, Q.-M., and Zeitouni, O. Self-normalized moderate deviations for random walk in random scenery.  Journal of Theoretical Probability (2019), 1–22.
  * [8] Fleischmann, K., Mörters, P., and Wachtel, V. Moderate deviations for a random walk in random scenery.  Stochastic Processes and their Applications 118, 10 (2008), 1768 – 1802.
  * [9] Gantert, N., van der Hofstad, R., and König, W. Deviations of a random walk in a random scenery with stretched exponential tails.  Stochastic processes and their applications 116, 3 (2006), 480–492.
  * [10] Kesten, H., and Spitzer, F. A limit theorem related to a new class of self similar processes.  Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 50, 1 (Jan 1979), 5–25.
  * [11] Lyons, R., Pemantle, R., and Peres, Y. Biased random walks on galton–watson trees.  Probability Theory and Related Fields 106, 2 (Oct 1996), 249–264.
  * [12] Nagaev, S. V. Lower bounds on large deviation probabilities for sums of independent random variables.  Theory of Probability and Its Applications 46, 1 (2002), 79–102.
  * [13] Shao, Q.-M. Self-normalized large deviations.  The Annals of Probability 25, 1 (1997), 285–328.


accepts $\mathbf{X}$ [22]. We say that $\operatorname{BLP}+\operatorname{AIP}$
_solves_ $\operatorname{PCSP}(\mathbf{A},\mathbf{B})$ if for every instance
$\mathbf{X}$ accepted by $\operatorname{BLP}+\operatorname{AIP}$ we have
$\mathbf{X}\to\mathbf{B}$.

We denote by
$\mathscr{M}_{\operatorname{\operatorname{BLP}+\operatorname{AIP}}}$ the
minion whose $L$-ary objects are pairs $(\mathbf{q},\mathbf{z})$, where
$\mathbf{q}\in\mathbb{Q}^{L}$ is a stochastic vector and
$\mathbf{z}\in\mathbb{Z}^{L}$ is an affine vector, with the property that, for
every $i\in[L]$, $q_{i}=0$ implies $z_{i}=0$. As before, the minor operation
is defined as in Section 4.1; i.e., if
$(\mathbf{q},\mathbf{z})\in\mathscr{M}_{\operatorname{\operatorname{BLP}+\operatorname{AIP}}}^{(L)}$
and $\pi:[L]\to[L^{\prime}]$, then
$(\mathbf{q},\mathbf{z})_{/\pi}=({P_{\pi}}\mathbf{q},{P_{\pi}}\mathbf{z})$,
where ${P_{\pi}}$ is the $L^{\prime}\times L$ matrix whose $(i,j)$-th entry is
$1$ if $\pi(j)=i$, and $0$ otherwise.

A $(2L+1)$-ary operation $f:A^{2L+1}\to B$ is called _$2$ -block symmetric_ if
$f(a_{1},\ldots,a_{2L+1})=f(a_{\pi(1)},\ldots,a_{\pi(2L+1)})$ for every
$a_{1},\ldots,a_{2L+1}\in A$ and every permutation $\pi:[2L+1]\to[2L+1]$ that
preserves parity.

The power of $\operatorname{BLP}+\operatorname{AIP}$ for PCSPs is
characterised in the following result.

######  Theorem 40 ([22]).

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template. The following are
equivalent:

  1. (1)

$\operatorname{BLP}+\operatorname{AIP}$ solves
$\operatorname{PCSP}(\mathbf{A},\mathbf{B})$.

  2. (2)

$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ admits a minion homomorphism from
$\mathscr{M}_{\operatorname{\operatorname{BLP}+\operatorname{AIP}}}$.

  3. (3)

$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains $2$-block-symmetric
operations of all odd arities.

##  Appendix B Proof of Lemma 22

In this section, we shall prove Lemma 22, which we restate below. The proof is
based on that of [8, Lemma 4.4], which concerns minions of functions.

######  Lemma (Lemma 22 restated).

Let $\mathscr{M}$ be a minion and let $(\mathbf{A},\mathbf{B})$ be a PCSP
template. Then there is a minion homomorphism from $\mathscr{M}$ to
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ if and only if
$\mathbb{F}_{\mathscr{M}}(\mathbf{A})\to\mathbf{B}$.

###### Proof.

Let $A=[n]$, and let $\sigma$ be the signature of $\mathbf{A}$ and
$\mathbf{B}$. Suppose
$\xi:\mathscr{M}\to\operatorname{Pol}(\mathbf{A},\mathbf{B})$ is a minion
homomorphism, and consider the function

$\displaystyle f:\mathscr{M}^{(n)}$ $\displaystyle\to B$ $\displaystyle M$
$\displaystyle\mapsto\xi(M)(1,\dots,n).$

For $R\in\sigma$ of arity $k$, consider a tuple $(M_{1},\dots,M_{k})\in
R^{\mathbb{F}_{\mathscr{M}}(\mathbf{A})}$. List the elements of
$R^{\mathbf{A}}$ as $\mathbf{a}^{(1)},\dots,\mathbf{a}^{(m)}$. From Definition
21, $\exists Q\in\mathscr{M}^{(m)}$ such that $M_{i}=Q_{/\pi_{i}}$ for each
$i\in[k]$, where $\pi_{i}:[m]\to A$ maps $j$ to the $i$-th coordinate of
$\mathbf{a}^{(j)}$. It follows that, for each $i\in[k]$,

$\displaystyle f(M_{i})$
$\displaystyle=f(Q_{/\pi_{i}})=\xi(Q_{/\pi_{i}})(1,\dots,n)=\xi(Q)_{/\pi_{i}}(1,\dots,n)=\xi(Q)(\pi_{i}(1),\dots,\pi_{i}(m)).$

Hence,

$\displaystyle f(M_{1},\dots,M_{k})$
$\displaystyle=(\xi(Q)(\pi_{1}(1),\dots,\pi_{1}(m)),\dots,\xi(Q)(\pi_{k}(1),\dots,\pi_{k}(m)))=\xi(Q)(\mathbf{a}^{(1)},\dots,\mathbf{a}^{(m)})\in
R^{\mathbf{B}}$

since $\xi(Q)$ is a polymorphism of $(\mathbf{A},\mathbf{B})$. Therefore, $f$
is a homomorphism from $\mathbb{F}_{\mathscr{M}}(\mathbf{A})$ to $\mathbf{B}$.

Conversely, let $f:\mathbb{F}_{\mathscr{M}}(\mathbf{A})\to\mathbf{B}$ be a
homomorphism, and consider the function
$\xi:\mathscr{M}\to\operatorname{Pol}(\mathbf{A},\mathbf{B})$ defined by
$\xi(M)(a_{1},\dots,a_{L})=f(M_{/\rho})$ for each $L\in\mathbb{N}$,
$M\in\mathscr{M}^{(L)}$, $(a_{1},\dots,a_{L})\in A^{L}$, where

$\displaystyle\rho:[L]$ $\displaystyle\to[n]$ $\displaystyle i$
$\displaystyle\mapsto a_{i}.$

Let us first check that $\xi$ is well defined – i.e., that
$\xi(M)\in\operatorname{Pol}(\mathbf{A},\mathbf{B})$. For $R\in\sigma$ of
arity $k$, consider a matrix $Z\in A^{L,k}$ such that each row of $Z$
corresponds to a tuple in $R^{\mathbf{A}}$. We need to show that $\xi(M)(Z)\in
R^{\mathbf{B}}$. Consider the maps

$\displaystyle\tau:[L]$ $\displaystyle\to R^{\mathbf{A}}$
$\displaystyle\rho_{j}:[L]$ $\displaystyle\to[n]$
$\displaystyle\pi_{j}:R^{\mathbf{A}}$ $\displaystyle\to[n]$ $\displaystyle i$
$\displaystyle\mapsto Z^{T}\mathbf{e}_{i},$ $\displaystyle i$
$\displaystyle\mapsto\mathbf{e}_{i}^{T}Z\mathbf{e}_{j},$
$\displaystyle\mathbf{a}$ $\displaystyle\mapsto\mathbf{e}_{j}^{T}\mathbf{a},$

for $j\in[k]$. Observe that $\rho_{j}=\pi_{j}\circ\tau$, and set
$Q=M_{/\tau}\in\mathscr{M}^{(|R^{\mathbf{A}}|)}$. We obtain

$\displaystyle\xi(M)(Z)$
$\displaystyle=f(M_{/\rho_{1}},\dots,M_{/\rho_{k}})=f(M_{/\pi_{1}\circ\tau},\dots,M_{/\pi_{k}\circ\tau})=f(Q_{/\pi_{1}},\dots,Q_{/\pi_{k}})\in
R^{\mathbf{B}}$

since $(Q_{/\pi_{1}},\dots,Q_{/\pi_{k}})\in
R^{\mathbb{F}_{\mathscr{M}}(\mathbf{A})}$ and $f$ is a homomorphism. Finally,
we show that $\xi$ is a minion homomorphism. Clearly, $\xi$ preserves arities.
To check that it preserves minors, let $M\in\mathscr{M}^{(L)}$ and take a map
$\pi:[L]\to[L^{\prime}]$. Given $(a_{1},\dots,a_{L^{\prime}})\in
A^{L^{\prime}}$, consider the maps

$\displaystyle\rho^{\prime}:[L^{\prime}]$ $\displaystyle\to[n]$
$\displaystyle\rho^{\prime\prime}:[L]$ $\displaystyle\to[n]$ $\displaystyle i$
$\displaystyle\mapsto a_{i},$ $\displaystyle i$ $\displaystyle\mapsto
a_{\pi(i)},$

and observe that $\rho^{\prime\prime}=\rho^{\prime}\circ\pi$. We obtain

$\displaystyle\xi(M_{/\pi})(a_{1},\dots,a_{L^{\prime}})$
$\displaystyle=f((M_{/\pi})_{/\rho^{\prime}})=f(M_{/\rho^{\prime}\circ\pi})=f(M_{/\rho^{\prime\prime}})=\xi(M)(a_{\pi(1)},\dots,a_{\pi(L)})$
$\displaystyle=\xi(M)_{/\pi}(a_{1},\dots,a_{L^{\prime}}),$

which yields $\xi(M_{/\pi})=\xi(M)_{/\pi}$, as desired. ∎

##  Appendix C H-block-symmetric polymorphisms

Let $\mathcal{C}=(\mathcal{C}_{1},\dots,\mathcal{C}_{\ell})$ be a partition of
${c}\in\mathbb{N}$; i.e., the sets $\mathcal{C}_{i}$ are pairwise disjoint and
their union is $[{c}]$. Let ${c}_{i}=|\mathcal{C}_{i}|$, so that
${c}=\sum_{i\in[\ell]}{c}_{i}$. For each $i\in[\ell]$, we consider the unique
monotonically increasing function $\vartheta_{i}:[{c}_{i}]\rightarrow[{c}]$
such that $\vartheta_{i}([{c}_{i}])=\mathcal{C}_{i}$. We also consider the
function $\chi_{i}:\mathcal{C}_{i}\to[{c}_{i}]$ such that
$\vartheta_{i}\circ\chi_{i}$ is the inclusion map of $\mathcal{C}_{i}$ in
$[{c}]$. Given ${c}^{\prime}\in\mathbb{N}$ and a map
$\pi:[{c}]\rightarrow[{c}^{\prime}]$, we let
$\pi_{(i)}=\pi\circ\vartheta_{i}$.

######  Definition 41.

Let $A,B$ be finite sets, and consider a function $f:A^{c}\rightarrow B$ for
some ${c}\in\mathbb{N}$. Given an $m\times|A|$ tie matrix $H$ and a partition
$\mathcal{C}=(\mathcal{C}_{1},\dots,\mathcal{C}_{\ell})$ of ${c}$, we say that
$f$ is _$H$ \- $\mathcal{C}$-block-symmetric_ if

$\displaystyle f_{/\pi}(\mathbf{a})=f(\mathbf{a})$
$\displaystyle\forall\pi:[{c}]\rightarrow[{c}]\mbox{ permutation such that
}\pi(\mathcal{C}_{i})=\mathcal{C}_{i}\hskip 5.69046pt\forall i\in[\ell],$
$\displaystyle\forall\mathbf{a}\in A^{c}\mbox{ such that
}({P^{T}_{\vartheta_{i}}}\mathbf{a})^{\\#}\mbox{ is $H$-tieless}\hskip
5.69046pt\forall i\in[\ell].$

We say that $f$ is _$H$ -block-symmetric_ with _width_ $W$ if $W$ is the
largest integer for which there is a partition $\mathcal{C}$ of ${c}$ such
that each part of $\mathcal{C}$ has size at least $W$ and $f$ is _$H$ \-
$\mathcal{C}$-block-symmetric_.111111The notion of $H$-block-symmetric
operation is the $H$-analogue of that of block-symmetric operation in [22]
(cf. Theorem 40). Without loss of generality, we consider $A=[n]$.

######  Lemma 42.

Let $f:A^{c}\rightarrow B$ be $H$\- $\mathcal{C}$-block-symmetric for some
$m\times n$ tie matrix $H$ ($m\in\mathbb{N}$) and some partition
$\mathcal{C}=(\mathcal{C}_{1},\dots,\mathcal{C}_{\ell})$ of ${c}$. Consider
two maps $\pi,\tilde{\pi}:[{c}]\rightarrow[n]$ such that, for each
$i\in[\ell]$,
${P_{\pi_{(i)}}}\mathbf{1}_{{c}_{i}}={P_{\tilde{\pi}_{(i)}}}\mathbf{1}_{{c}_{i}}$
and the vector ${P_{\pi_{(i)}}}\mathbf{1}_{{c}_{i}}$ is $H$-tieless. Then

$\displaystyle f_{/\pi}(1,\dots,n)=f_{/\tilde{\pi}}(1,\dots,n).$

###### Proof.

For $i\in[\ell]$ and $a\in[n]$, we have

$\displaystyle|\pi_{(i)}^{-1}(a)|=\mathbf{e}_{a}^{T}{P_{\pi_{(i)}}}\mathbf{1}_{{c}_{i}}=\mathbf{e}_{a}^{T}{P_{\tilde{\pi}_{(i)}}}\mathbf{1}_{{c}_{i}}=|\tilde{\pi}_{(i)}^{-1}(a)|.$

Hence, we can consider bijections
$\varphi_{i,a}:\pi_{(i)}^{-1}(a)\rightarrow\tilde{\pi}_{(i)}^{-1}(a)$ for each
$i\in[\ell],a\in[n]$. The union

$\displaystyle\varphi_{i}=\bigcup_{a\in[n]}\varphi_{i,a}:[{c}_{i}]\rightarrow[{c}_{i}]$

is also a bijection. Define $\varphi:[{c}]\to[{c}]$ by letting
$\varphi\big{|}_{\mathcal{C}_{i}}=\vartheta_{i}\circ\varphi_{i}\circ\chi_{i}$
for each $i\in[\ell]$. Notice that $\varphi(\mathcal{C}_{i})=\mathcal{C}_{i}$
for each $i\in[\ell]$, so $\varphi$ is a bijection. Take $j\in[{c}]$ and
suppose that $j\in\mathcal{C}_{i}$. We have

$\displaystyle(\tilde{\pi}\circ\varphi)(j)=\tilde{\pi}(\varphi(j))=\tilde{\pi}(\vartheta_{i}(\varphi_{i}(\chi_{i}(j))))=\tilde{\pi}_{(i)}(\varphi_{i,\pi_{(i)}(\chi_{i}(j))}(\chi_{i}(j)))=\pi_{(i)}(\chi_{i}(j))=(\pi\circ\vartheta_{i}\circ\chi_{i})(j)=\pi(j)$

and, hence, $\tilde{\pi}\circ\varphi=\pi$. Let
$\tilde{\mathbf{a}}=(\tilde{\pi}(1),\dots,\tilde{\pi}({c}))$. Notice that, for
each $i\in[\ell]$ and $a\in[n]$,

$\displaystyle\mathbf{e}_{a}^{T}({P^{T}_{\vartheta_{i}}}\tilde{\mathbf{a}})^{\\#}$
$\displaystyle=|\\{j\in[{c}_{i}]:\mathbf{e}_{j}^{T}{P^{T}_{\vartheta_{i}}}\tilde{\mathbf{a}}=a\\}|=|\\{j\in[{c}_{i}]:\mathbf{e}_{\vartheta_{i}(j)}^{T}\tilde{\mathbf{a}}=a\\}|=|\\{j\in[{c}_{i}]:\tilde{\pi}(\vartheta_{i}(j))=a\\}|$
$\displaystyle=|\\{j\in[{c}_{i}]:\tilde{\pi}_{(i)}(j)=a\\}|=\mathbf{e}_{a}^{T}{P_{\tilde{\pi}_{(i)}}}\mathbf{1}_{{c}_{i}}$

and, therefore,
$({P^{T}_{\vartheta_{i}}}\tilde{\mathbf{a}})^{\\#}={P_{\tilde{\pi}_{(i)}}}\mathbf{1}_{{c}_{i}}={P_{{\pi}_{(i)}}}\mathbf{1}_{{c}_{i}}$,
which is $H$-tieless. Using that $f$ is $H$\- $\mathcal{C}$-block-symmetric,
we find

$\displaystyle
f_{/\tilde{\pi}}(1,\dots,n)=f(\tilde{\mathbf{a}})=f_{/\varphi}(\tilde{\mathbf{a}})=(f_{/\varphi})_{/\tilde{\pi}}(1,\dots,n)=f_{/\tilde{\pi}\circ\varphi}(1,\dots,n)=f_{/\pi}(1,\dots,n),$

as required. ∎

######  Theorem 43.

Let $(\mathbf{A},\mathbf{B})$ be a PCSP template and suppose
$\operatorname{Pol}(\mathbf{A},\mathbf{B})$ contains $H$-block-symmetric
operations of arbitrarily large width for some $m\times|A|$ tie matrix $H$,
$m\in\mathbb{N}$. Then there exists a minion homomorphism from $\mathscr{C}$
to $\operatorname{Pol}(\mathbf{A},\mathbf{B})$.

###### Proof.

For $D\in\mathbb{N}$, consider the subminion $\mathscr{C}_{D}$ of
$\mathscr{C}$ described in Section 4.2. Observe that
$S=\\{M:(M,\bm{\mu})\in\mathscr{C}_{D}^{(n)}\\}$ is a finite set of skeletal
matrices. Therefore, we can apply the Tiebreak Lemma 35 to find a stochastic
finitely supported vector ${\mathbf{v}}\in\mathbb{Q}^{\aleph_{0}}$ with
$\mathbf{e}_{1}^{T}{\mathbf{v}}>0$ such that $M{\mathbf{v}}$ is $H$-tieless
for any $M\in S$. Since ${\mathbf{v}}$ is finitely supported, we can find
$N^{\prime}\in\mathbb{N}$ such that $N^{\prime}{\mathbf{v}}$ has integer
entries. Let $\sigma_{1}^{H}$ denote the largest singular value of $H$ – i.e.,
the square root of the largest eigenvalue of $H^{T}H$. Set
$N=2\lceil\sigma_{1}^{H}+1\rceil D^{2}N^{\prime}$, and let $f$ be an
$H$-block-symmetric polymorphism of width ${W}\geq N^{2}$. Letting $c$ be the
arity of $f$, consider a partition
$\mathcal{C}=(\mathcal{C}_{1},\dots,\mathcal{C}_{\ell})$ of $c$ such that
$c_{i}=|\mathcal{C}_{i}|\geq W$ for each $i\in[\ell]$ and $f$ is $H$\-
$\mathcal{C}$-block-symmetric. Write ${c}_{i}=N\alpha_{i}+\beta_{i}$ with
$\alpha_{i},\beta_{i}\in\mathbb{N}_{0}$, $\beta_{i}\leq N-1$. Note that
$N^{2}\leq W\leq{c}_{i}=N\alpha_{i}+\beta_{i}\leq
N\alpha_{i}+N-1<N(\alpha_{i}+1)$, so $N<\alpha_{i}+1$ and, hence,
$\beta_{i}<\alpha_{i}$.

Consider the function

$\displaystyle\xi_{D}:\mathscr{C}_{D}\rightarrow\operatorname{Pol}(\mathbf{A},\mathbf{B})$

defined as follows. Given $L\in\mathbb{N}$ and
$(M,\bm{\mu})\in\mathscr{C}_{D}^{(L)}$, for each $i\in[\ell]$ take the map
$\varphi_{i}:[{c}_{i}]\rightarrow[L]$ such that the corresponding
$L\times{c}_{i}$ matrix $P_{\varphi_{i}}$ is

$\displaystyle{P_{\varphi_{i}}}=\begin{pmatrix}\mathbf{1}^{T}_{\mathbf{e}_{1}^{T}(\alpha_{i}NM{\mathbf{v}}+\beta_{i}\bm{\mu})}&\mathbf{0}^{T}&\dots&\mathbf{0}^{T}\\\
\mathbf{0}^{T}&\mathbf{1}^{T}_{\mathbf{e}_{2}^{T}(\alpha_{i}NM{\mathbf{v}}+\beta_{i}\bm{\mu})}&\dots&\mathbf{0}^{T}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathbf{0}^{T}&\mathbf{0}^{T}&\dots&\mathbf{1}^{T}_{\mathbf{e}_{L}^{T}(\alpha_{i}NM{\mathbf{v}}+\beta_{i}\bm{\mu})}\end{pmatrix}.$
(6)

To verify that (6) is well defined, observe first that

$\displaystyle\sum_{j=1}^{L}\mathbf{e}_{j}^{T}(\alpha_{i}NM{\mathbf{v}}+\beta_{i}\bm{\mu})=\mathbf{1}_{L}^{T}(\alpha_{i}NM{\mathbf{v}}+\beta_{i}\bm{\mu})=\alpha_{i}N\mathbf{1}_{L}^{T}M{\mathbf{v}}+\beta_{i}\mathbf{1}_{L}^{T}\bm{\mu}=\alpha_{i}N\mathbf{1}_{\aleph_{0}}^{T}{\mathbf{v}}+\beta_{i}=\alpha_{i}N+\beta_{i}={c}_{i}.$

Moreover, for each $j\in[L]$,
$\mathbf{e}_{j}^{T}(\alpha_{i}NM{\mathbf{v}}+\beta_{i}\bm{\mu})=\mathbf{e}_{j}^{T}(2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil
D(DM)(N^{\prime}{\mathbf{v}})+\beta_{i}\bm{\mu})$ is an integer. If
$\mathbf{e}_{j}^{T}(\alpha_{i}NM{\mathbf{v}}+\beta_{i}\bm{\mu})$ was negative,
then $\mathbf{e}_{j}^{T}\bm{\mu}<0$. By the requirement $(c_{4})$ in
Definition 12, this would imply that $\mathbf{e}_{j}^{T}M\mathbf{e}_{1}>0$
and, hence,
$0<\mathbf{e}_{j}^{T}M\mathbf{e}_{1}\mathbf{e}_{1}^{T}{\mathbf{v}}\leq\mathbf{e}_{j}^{T}M{\mathbf{v}}$.
As a consequence, $\mathbf{e}_{j}^{T}(DM)(N^{\prime}{\mathbf{v}})\geq 1$ so
that

$\displaystyle\mathbf{e}_{j}^{T}(\alpha_{i}NM{\mathbf{v}}+\beta_{i}\bm{\mu})=2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil
D\mathbf{e}_{j}^{T}(DM)(N^{\prime}{\mathbf{v}})+\beta_{i}\mathbf{e}_{j}^{T}\bm{\mu}\geq
2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil
D+\beta_{i}\mathbf{e}_{j}^{T}\bm{\mu}\geq\alpha_{i}D-\beta_{i}D>0,$

which is a contradiction. In conclusion, the numbers
$\mathbf{e}_{j}^{T}(\alpha_{i}NM{\mathbf{v}}+\beta_{i}\bm{\mu})$ are
nonnegative integers summing up to ${c}_{i}$, so (6) is well defined.

Consider the function $\varphi:[c]\to[L]$ defined by
$\varphi\big{|}_{\mathcal{C}_{i}}=\varphi_{i}\circ\chi_{i}$ $\forall
i\in[\ell]$, and let $\xi_{D}((M,\bm{\mu}))\coloneqq f_{/\varphi}$. Clearly,
$\xi_{D}((M,\bm{\mu}))\in\operatorname{Pol}(\mathbf{A},\mathbf{B})$. We claim
that the map $\xi_{D}$ is a minion homomorphism. It is straightforward to
check that $\xi_{D}$ preserves arities so, to conclude, we need to show that
it also preserves minors. Take $L^{\prime}\in\mathbb{N}$ and choose a map
$\pi:[L]\rightarrow[L^{\prime}]$. Letting
$\tilde{\varphi}_{i}:[{c}_{i}]\rightarrow[L^{\prime}]$ be the map
corresponding to the matrix

$\displaystyle{P_{\tilde{\varphi}_{i}}}=\begin{pmatrix}\mathbf{1}^{T}_{\mathbf{e}_{1}^{T}(\alpha_{i}N{P_{\pi}}M{\mathbf{v}}+\beta_{i}{P_{\pi}}\bm{\mu})}&\mathbf{0}^{T}&\dots&\mathbf{0}^{T}\\\
\mathbf{0}^{T}&\mathbf{1}^{T}_{\mathbf{e}_{2}^{T}(\alpha_{i}N{P_{\pi}}M{\mathbf{v}}+\beta_{i}{P_{\pi}}\bm{\mu})}&\dots&\mathbf{0}^{T}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathbf{0}^{T}&\mathbf{0}^{T}&\dots&\mathbf{1}^{T}_{\mathbf{e}_{L^{\prime}}^{T}(\alpha_{i}N{P_{\pi}}M{\mathbf{v}}+\beta_{i}{P_{\pi}}\bm{\mu})}\end{pmatrix}$

for each $i\in[\ell]$, and considering $\tilde{\varphi}:[c]\to[L^{\prime}]$
such that
$\tilde{\varphi}\big{|}_{\mathcal{C}_{i}}=\tilde{\varphi}_{i}\circ\chi_{i}$
$\forall i\in[\ell]$, we see that
$\xi_{D}((M,\bm{\mu})_{/\pi})=f_{/\tilde{\varphi}}$. Moreover,
$\xi_{D}((M,\bm{\mu}))_{/\pi}=(f_{/\varphi})_{/\pi}=f_{/\pi\circ\varphi}$,
where $\varphi$ is the map defined above. Take
${\mathbf{a}}=(a_{1},\dots,a_{L^{\prime}})\in A^{L^{\prime}}$, and consider
the map

$\displaystyle\pi_{\mathbf{a}}:[L^{\prime}]$ $\displaystyle\rightarrow[n]$
$\displaystyle i$ $\displaystyle\mapsto a_{i}.$

Observe that

$\displaystyle f_{/\tilde{\varphi}}(\mathbf{a})$ $\displaystyle=$
$\displaystyle(f_{/\tilde{\varphi}})_{/\pi_{\mathbf{a}}}(1,\dots,n)$
$\displaystyle=$ $\displaystyle
f_{/\pi_{\mathbf{a}}\circ\tilde{\varphi}}(1,\dots,n)$ and, similarly,
$\displaystyle f_{/\pi\circ\varphi}(\mathbf{a})$ $\displaystyle=$
$\displaystyle(f_{/\pi\circ\varphi})_{/\pi_{\mathbf{a}}}(1,\dots,n)$
$\displaystyle=$ $\displaystyle
f_{/\pi_{\mathbf{a}}\circ\pi\circ\varphi}(1,\dots,n).$ (7)

Notice that, for each $i\in[\ell]$, $\varphi\circ\vartheta_{i}=\varphi_{i}$
and $\tilde{\varphi}\circ\vartheta_{i}=\tilde{\varphi}_{i}$. Hence,

$\displaystyle{P_{(\pi_{\mathbf{a}}\circ\tilde{\varphi})_{(i)}}}\mathbf{1}_{c_{i}}$
$\displaystyle={P_{\pi_{\mathbf{a}}\circ\tilde{\varphi}\circ\vartheta_{i}}}\mathbf{1}_{c_{i}}={P_{\pi_{\mathbf{a}}}}{P_{\tilde{\varphi}\circ\vartheta_{i}}}\mathbf{1}_{c_{i}}={P_{\pi_{\mathbf{a}}}}{P_{\tilde{\varphi}_{i}}}\mathbf{1}_{c_{i}}={P_{\pi_{\mathbf{a}}}}(\alpha_{i}N{P_{\pi}}M{\mathbf{v}}+\beta_{i}{P_{\pi}}\bm{\mu})$
$\displaystyle={P_{\pi_{\mathbf{a}}}}{P_{\pi}}(\alpha_{i}NM{\mathbf{v}}+\beta_{i}\bm{\mu})={P_{\pi_{\mathbf{a}}}}{P_{\pi}}{P_{\varphi_{i}}}\mathbf{1}_{c_{i}}={P_{\pi_{\mathbf{a}}\circ\pi\circ\varphi\circ\vartheta_{i}}}\mathbf{1}_{c_{i}}={P_{(\pi_{\mathbf{a}}\circ\pi\circ\varphi)_{(i)}}}\mathbf{1}_{c_{i}}.$

We claim that the vector
${P_{(\pi_{\mathbf{a}}\circ\tilde{\varphi})_{(i)}}}\mathbf{1}_{c_{i}}={P_{\pi_{\mathbf{a}}\circ\tilde{\varphi}_{i}}}\mathbf{1}_{c_{i}}$
is $H$-tieless. Let
${\mathbf{u}}=(u_{t})=H{P_{\pi_{\mathbf{a}}\circ\tilde{\varphi}_{i}}}\mathbf{1}_{c_{i}}$;
the claim is equivalent to ${\mathbf{u}}$ being tieless. Let
${\mathbf{w}}=(w_{t})=\alpha_{i}NH{P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}$
and ${\mathbf{z}}=(z_{t})=\beta_{i}H{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}$,
so that ${\mathbf{u}}={\mathbf{w}}+{\mathbf{z}}$. Choose
${t},{t}^{\prime}\in[m]$ such that ${t}\neq{t}^{\prime}$ and $u_{t}\neq 0$. We
need to show that $u_{t}\neq u_{{t}^{\prime}}$. Suppose $w_{t}=0$. We can
write $H^{T}\mathbf{e}_{t}=\sum_{g\in G}\lambda_{g}\mathbf{e}_{g}$ for
$G=\operatorname{supp}(H^{T}\mathbf{e}_{t})$, where each $\lambda_{g}$ is a
positive integer (note that $G\neq\emptyset$ since, otherwise,
$H^{T}\mathbf{e}_{t}=\mathbf{0}_{n}$, which would imply $u_{t}=0$). Let
${F}=(\pi_{\mathbf{a}}\circ\pi)^{-1}(G)$. From $w_{t}=0$, we obtain

$\displaystyle
0=\mathbf{e}_{t}^{T}H{P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}=(H^{T}\mathbf{e}_{t})^{T}{P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}$
$\displaystyle=$ $\displaystyle\sum_{g\in
G}\lambda_{g}\mathbf{e}_{g}^{T}{P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}=\sum_{g\in
G}\lambda_{g}\sum_{j\in(\pi_{\mathbf{a}}\circ\pi)^{-1}(g)}\mathbf{e}_{j}^{T}M{\mathbf{v}}$

and, hence, the following chain of implications holds:

$\displaystyle\begin{array}[]{lllll}&\displaystyle 0=\sum_{g\in
G}\sum_{j\in(\pi_{\mathbf{a}}\circ\pi)^{-1}(g)}\mathbf{e}_{j}^{T}M{\mathbf{v}}=\sum_{j\in{F}}\mathbf{e}_{j}^{T}M{\mathbf{v}}&\displaystyle\hskip
5.69046pt\Rightarrow&\displaystyle\mathbf{e}_{j}^{T}M{\mathbf{v}}=0&{\forall
j\in{F}}\\\\[7.0pt]
\Rightarrow&\displaystyle\mathbf{e}_{j}^{T}M\mathbf{e}_{1}=0\hskip
28.45274pt{\forall j\in{F}}&\hskip
5.69046pt\Rightarrow&\displaystyle\mathbf{e}_{j}^{T}\bm{\mu}=0&{\forall
j\in{F}}\end{array}$

(where the second implication follows from $\mathbf{e}_{1}^{T}{\mathbf{v}}>0$,
and the third follows from $(c_{4})$ in Definition 12). Hence,

$\displaystyle
z_{t}=\beta_{i}\mathbf{e}_{t}^{T}H{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}=\beta_{i}\sum_{g\in
G}\lambda_{g}\mathbf{e}_{g}^{T}{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}=\beta_{i}\sum_{g\in
G}\lambda_{g}\sum_{j\in(\pi_{\mathbf{a}}\circ\pi)^{-1}(g)}\mathbf{e}_{j}^{T}\bm{\mu}=0,$

so that $u_{t}=w_{t}+z_{t}=0$, a contradiction. Hence, $w_{t}>0$. Observe that
$(M_{/\pi_{\mathbf{a}}\circ\pi},\bm{\mu}_{/\pi_{\mathbf{a}}\circ\pi})\in\mathscr{C}_{D}^{(n)}$
and, hence, $M_{/\pi_{\mathbf{a}}\circ\pi}\in S$. By the choice of
${\mathbf{v}}$, this implies that the vector
${P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}=M_{/\pi_{\mathbf{a}}\circ\pi}{\mathbf{v}}$
is $H$-tieless; i.e., $H{P_{\pi_{\mathbf{a}}\circ\pi}}M{\mathbf{v}}$ is
tieless. It follows that the vector
$H{P_{\pi_{\mathbf{a}}\circ\pi}}(DM)(N^{\prime}{\mathbf{v}})=\frac{1}{2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil
D}{\mathbf{w}}$ is also tieless; being it entrywise integer, and since
$\frac{1}{2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil D}w_{t}>0$, we obtain

$\displaystyle\left|\frac{1}{2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil
D}w_{t}-\frac{1}{2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil
D}w_{{t}^{\prime}}\right|\geq 1$ that yields
$\displaystyle|w_{t}-w_{{t}^{\prime}}|\geq
2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil D.$

Denote the $\ell_{1}$-norm and the $\ell_{2}$-norm of a vector by
$\|\cdot\|_{1}$ and $\|\cdot\|_{2}$, respectively. Recall that the largest
singular value of a matrix is its spectral operator norm – i.e.,
$\sigma_{1}^{H}=\max_{\mathbf{0}\neq\mathbf{x}\in\mathbb{R}^{n}}\frac{\|H\mathbf{x}\|_{2}}{\|\mathbf{x}\|_{2}}$
(see [47]). In particular,
$\|H\mathbf{x}\|_{2}\leq\sigma_{1}^{H}\|\mathbf{x}\|_{2}$ for each vector
$\mathbf{x}$ of size $n$. Using the Cauchy-Schwarz inequality and the fact
that the $\ell_{1}$-norm of a vector is greater than or equal to its
$\ell_{2}$-norm, we find

$\displaystyle|z_{t}-z_{{t}^{\prime}}|$
$\displaystyle=\beta_{i}|(\mathbf{e}_{t}-\mathbf{e}_{{t}^{\prime}})^{T}H{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}|\leq\beta_{i}\|\mathbf{e}_{t}-\mathbf{e}_{{t}^{\prime}}\|_{2}\|H{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}\|_{2}\leq\beta_{i}\|\mathbf{e}_{t}-\mathbf{e}_{{t}^{\prime}}\|_{2}\sigma_{1}^{H}\|{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}\|_{2}$
$\displaystyle\leq\beta_{i}\|\mathbf{e}_{t}-\mathbf{e}_{{t}^{\prime}}\|_{1}\lceil\sigma_{1}^{H}+1\rceil\|{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}\|_{1}=2\beta_{i}\lceil\sigma_{1}^{H}+1\rceil\mathbf{1}_{n}^{T}|{P_{\pi_{\mathbf{a}}\circ\pi}}\bm{\mu}|\leq
2\beta_{i}\lceil\sigma_{1}^{H}+1\rceil\mathbf{1}_{n}^{T}{P_{\pi_{\mathbf{a}}\circ\pi}}|\bm{\mu}|$
$\displaystyle=2\beta_{i}\lceil\sigma_{1}^{H}+1\rceil\mathbf{1}_{L}^{T}|\bm{\mu}|\leq
2\beta_{i}\lceil\sigma_{1}^{H}+1\rceil
D<2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil D.$

We conclude the proof of the claim by noting that

$\displaystyle|u_{t}-u_{{t}^{\prime}}|=|(w_{t}-w_{{t}^{\prime}})-(z_{{t}^{\prime}}-z_{t})|\geq|w_{t}-w_{{t}^{\prime}}|-|z_{t}-z_{{t}^{\prime}}|>2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil
D-2\alpha_{i}\lceil\sigma_{1}^{H}+1\rceil D=0,$

which implies $u_{t}\neq u_{{t}^{\prime}}$. As a consequence, the vector
${P_{(\pi_{\mathbf{a}}\circ\tilde{\varphi})_{(i)}}}\mathbf{1}_{c_{i}}$ is
$H$-tieless. We can then apply Lemma 42 to conclude that
$f_{/\pi_{\mathbf{a}}\circ\tilde{\varphi}}(1,\dots,n)=f_{/\pi_{\mathbf{a}}\circ\pi\circ\varphi}(1,\dots,n)$.
Hence, by (C), $f_{/\tilde{\varphi}}=f_{/\pi\circ\varphi}$. Therefore,
$\xi_{D}((M,\bm{\mu})_{/\pi})=\xi_{D}((M,\bm{\mu}))_{/\pi}$, as required. It
follows that $\xi_{D}$ is a minion homomorphism.

Since the set of polymorphisms of $(\mathbf{A},\mathbf{B})$ of arity $L$ is
finite for every $L\in\mathbb{N}$, we can apply Proposition 25 to conclude
that there exists a minion homomorphism
$\zeta:\mathscr{C}\rightarrow\operatorname{Pol}(\mathbf{A},\mathbf{B})$. ∎

## References

  * [1] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  J. ACM, 45(3):501–555, 1998.  doi:10.1145/278298.278306.
  * [2] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs: A new characterization of NP.  J. ACM, 45(1):70–122, 1998.  doi:10.1145/273865.273901.
  * [3] Albert Atserias and Víctor Dalmau.  Promise Constraint Satisfaction and Width.  In Proc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 1129–1153, 2022.  arXiv:2107.05886, doi:10.1137/1.9781611977073.48.
  * [4] Per Austrin, Amey Bhangale, and Aditya Potukuchi.  Improved inapproximability of rainbow coloring.  In Proc. 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA’20), pages 1479–1495, 2020.  arXiv:1810.02784, doi:10.1137/1.9781611975994.90.
  * [5] Per Austrin, Venkatesan Guruswami, and Johan Håstad.  (2+$\epsilon$)-Sat is NP-hard.  SIAM J. Comput., 46(5):1554–1573, 2017.  arXiv:2013/159, doi:10.1137/15M1006507.
  * [6] Libor Barto.  The collapse of the bounded width hierarchy.  J. Log. Comput., 26(3):923–943, 2016.  doi:10.1093/logcom/exu070.
  * [7] Libor Barto, Diego Battistelli, and Kevin M. Berg.  Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case.  In Proc. 38th International Symposium on Theoretical Aspects of Computer Science (STACS’21), volume 187 of LIPIcs, pages 10:1–10:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  arXiv:2010.04623, doi:10.4230/LIPIcs.STACS.2021.10.
  * [8] Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal.  Algebraic approach to promise constraint satisfaction.  J. ACM, 68(4):28:1–28:66, 2021.  arXiv:1811.00970, doi:10.1145/3457606.
  * [9] Libor Barto and Marcin Kozik.  Constraint Satisfaction Problems Solvable by Local Consistency Methods.  J. ACM, 61(1), 2014.  Article No. 3.  doi:10.1145/2556646.
  * [10] Libor Barto and Marcin Kozik.  Robustly solvable constraint satisfaction problems.  SIAM J. Comput., 45(4):1646–1669, 2016.  arXiv:1512.01157, doi:10.1137/130915479.
  * [11] Libor Barto, Andrei Krokhin, and Ross Willard.  Polymorphisms, and how to use them.  In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1–44. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017.  doi:10.4230/DFU.Vol7.15301.1.
  * [12] Libor Barto, Jakub Opršal, and Michael Pinsker.  The wonderland of reflections.  Isr. J. Math, 223(1):363–398, Feb 2018.  arXiv:1510.04521, doi:10.1007/s11856-017-1621-9.
  * [13] Libor Barto and Michael Pinsker.  Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems).  SIAM J. Comput., 49(2):365–393, 2020.  doi:10.1137/18M1216213.
  * [14] Joel Berman, Pawel Idziak, Petar Marković, Ralph McKenzie, Matthew Valeriote, and Ross Willard.  Varieties with few subalgebras of powers.  Trans. Am. Math. Soc., 362(3):1445–1473, 2010.
  * [15] Christian Bessiere and Romuald Debruyne.  Theoretical analysis of singleton arc consistency and its extensions.  Artif. Intell., 172(1):29–41, 2008.  doi:10.1016/j.artint.2007.09.001.
  * [16] Avrim Blum.  New approximation algorithms for graph coloring.  J. ACM, 41(3):470–516, 1994.  doi:10.1145/176584.176586.
  * [17] Manuel Bodirsky, Barnaby Martin, and Antoine Mottet.  Discrete temporal constraint satisfaction problems.  J. ACM, 65(2):9:1–9:41, 2018.  arXiv:1503.08572, doi:10.1145/3154832.
  * [18] Manuel Bodirsky, Antoine Mottet, Miroslav Olšák, Jakub Opršal, Michael Pinsker, and Ross Willard.  $\omega$-categorical structures avoiding height 1 identities.  Trans. Am. Math. Soc., 374(1):327–350, 2021.  arXiv:2006.12254, doi:10.1090/tran/8179.
  * [19] Joshua Brakensiek and Venkatesan Guruswami.  An algorithmic blend of LPs and ring equations for promise CSPs.  In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’19), pages 436–455, 2019.  arXiv:1807.05194, doi:10.1137/1.9781611975482.28.
  * [20] Joshua Brakensiek and Venkatesan Guruswami.  Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.  SIAM J. Comput., 50(6):1663–1700, 2021.  arXiv:1704.01937, doi:10.1137/19M128212X.
  * [21] Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep.  Conditional Dichotomy of Boolean Ordered Promise CSPs.  In Proc. 48th International Colloquium on Automata, Languages, and Programming (ICALP’21), volume 198 of LIPIcs, pages 37:1–37:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.  arXiv:2102.11854, doi:10.4230/LIPIcs.ICALP.2021.37.
  * [22] Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný.  The power of the combined basic LP and affine relaxation for promise CSPs.  SIAM J. Comput., 49:1232–1248, 2020.  arXiv:1907.04383, doi:10.1137/20M1312745.
  * [23] Alex Brandts, Marcin Wrochna, and Stanislav Živný.  The complexity of promise SAT on non-Boolean domains.  ACM Trans. Comput. Theory, 13(4):26:1–26:20, 2021.  arXiv:1911.09065, doi:10.1145/3470867.
  * [24] Alex Brandts and Stanislav Živný.  Beyond PCSP(1-in-3,NAE).  Information and Computation, 2022.  arXiv:2104.12800, doi:10.1016/j.ic.2022.104954.
  * [25] Andrei Bulatov.  Bounded relational width.  Unpublished manuscript, 2009.  URL: https://www2.cs.sfu.ca/~abulatov/papers/relwidth.pdf.
  * [26] Andrei Bulatov, Peter Jeavons, and Andrei Krokhin.  Classifying the complexity of constraints using finite algebras.  SIAM J. Comput., 34(3):720–742, 2005.  doi:10.1137/S0097539700376676.
  * [27] Andrei A. Bulatov.  A dichotomy theorem for constraint satisfaction problems on a 3-element set.  J. ACM, 53(1):66–120, 2006.  doi:10.1145/1120582.1120584.
  * [28] Andrei A. Bulatov.  A dichotomy theorem for nonuniform CSPs.  In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), pages 319–330, 2017.  arXiv:1703.03021, doi:10.1109/FOCS.2017.37.
  * [29] Andrei A. Bulatov and Víctor Dalmau.  A Simple Algorithm for Mal’tsev Constraints.  SIAM J. Comput., 36(1):16–27, 2006.  doi:10.1137/050628957.
  * [30] Hubie Chen, Víctor Dalmau, and Berit Grußien.  Arc consistency and friends.  J. Log. Comput., 23(1):87–108, 2013.  doi:10.1093/logcom/exr039.
  * [31] Lorenzo Ciardo and Stanislav Živný.  Hierarchies of minion tests for PCSPs through tensors.  In Proc. 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA’23), 2023.  To appear.  arXiv:2207.02277.
  * [32] Lorenzo Ciardo and Stanislav Živný.  CLAP: A New Algorithm for Promise CSPs.  In Proc. 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), pages 1057–1068, 2022.  arXiv:2107.05018, doi:10.1137/1.9781611977073.46.
  * [33] David A. Cohen.  Tractable decision for a constraint language implies tractable search.  Constraints, 9(3):219–229, 2004.  doi:10.1023/B:CONS.0000036045.82829.94.
  * [34] Víctor Dalmau.  There are no pure relational width 2 constraint satisfaction problems.  Inf. Process. Lett., 109(4):213–218, 2009.  doi:10.1016/j.ipl.2008.10.005.
  * [35] Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, and Jakub Opršal.  Robust algorithms with polynomial loss for near-unanimity CSPs.  SIAM J. Comput., 48(6):1763–1795, 2019.  arXiv:1607.04787, doi:10.1137/18M1163932.
  * [36] Víctor Dalmau and Andrei A. Krokhin.  Robust Satisfiability for CSPs: Hardness and Algorithmic Results.  ACM Trans. Comput. Theory, 5(4):15:1–15:25, 2013.  doi:10.1145/2540090.
  * [37] Víctor Dalmau and Justin Pearson.  Closure functions and width 1 problems.  In Proc. 4th International Conference on Principles and Practice of Constraint Programming (CP’99), volume 1713 of Lecture Notes in Computer Science, pages 159–173. Springer, 1999.  doi:10.1007/978-3-540-48085-3\\_12.
  * [38] Romuald Debruyne and Christian Bessière.  Some Practicable Filtering Techniques for the Constraint Satisfaction Problem.  In Proc. 15th International Joint Conference on Artificial Intelligence (IJCAI’97), pages 412–417. Morgan Kaufmann, 1997.
  * [39] Irit Dinur.  The PCP theorem by gap amplification.  J. ACM, 54(3):12, 2007.  doi:10.1145/1236457.1236459.
  * [40] Irit Dinur, Oded Regev, and Clifford Smyth.  The hardness of 3-uniform hypergraph coloring.  Comb., 25(5):519–535, September 2005.  doi:10.1007/s00493-005-0032-4.
  * [41] Tomás Feder and Moshe Y. Vardi.  The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory.  SIAM J. Comput., 28(1):57–104, 1998.  doi:10.1137/S0097539794266766.
  * [42] Miron Ficak, Marcin Kozik, Miroslav Olšák, and Szymon Stankiewicz.  Dichotomy for Symmetric Boolean PCSPs.  In Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP’19), volume 132, pages 57:1–57:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019.  arXiv:1904.12424, doi:10.4230/LIPIcs.ICALP.2019.57.
  * [43] M. R. Garey and David S. Johnson.  The complexity of near-optimal graph coloring.  J. ACM, 23(1):43–49, 1976.  doi:10.1145/321921.321926.
  * [44] Venkatesan Guruswami and Sanjeev Khanna.  On the hardness of 4-coloring a 3-colorable graph.  SIAM J. Discret. Math., 18(1):30–40, 2004.  doi:10.1137/S0895480100376794.
  * [45] Venkatesan Guruswami and Sai Sandeep.  d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors.  In Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP’20), volume 168 of LIPIcs, pages 62:1–62:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.ICALP.2020.62.
  * [46] Pavol Hell and Jaroslav Nešetřil.  On the complexity of H-coloring.  J. Comb. Theory, Ser. B, 48(1):92–110, 1990.  doi:10.1016/0095-8956(90)90132-J.
  * [47] Roger A Horn and Charles R Johnson.  Matrix analysis.  Cambridge university press, 2012.
  * [48] Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard.  Tractability and learnability arising from algebras with few subpowers.  SIAM J. Comput., 39(7):3023–3037, 2010.  doi:10.1137/090775646.
  * [49] Peter G. Jeavons.  On the Algebraic Structure of Combinatorial Problems.  Theor. Comput. Sci., 200(1-2):185–204, 1998.  doi:10.1016/S0304-3975(97)00230-2.
  * [50] Peter G. Jeavons, David A. Cohen, and Marc Gyssens.  Closure Properties of Constraints.  J. ACM, 44(4):527–548, 1997.  doi:10.1145/263867.263489.
  * [51] Sanjeev Khanna, Nathan Linial, and Shmuel Safra.  On the hardness of approximating the chromatic number.  Comb., 20(3):393–415, 2000.  doi:10.1007/s004930070013.
  * [52] Subhash Khot.  Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring.  In Proc. 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS’01), pages 600–609. IEEE Computer Society, 2001.  doi:10.1109/SFCS.2001.959936.
  * [53] Subhash Khot.  On the power of unique 2-prover 1-round games.  In Proc. 34th Annual ACM Symposium on Theory of Computing (STOC’02), pages 767–775. ACM, 2002.  doi:10.1145/509907.510017.
  * [54] Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolínek.  The complexity of general-valued CSPs.  SIAM J. Comput., 46(3):1087–1110, 2017.  arXiv:1502.07327, doi:10.1137/16M1091836.
  * [55] Vladimir Kolmogorov, Johan Thapper, and Stanislav Živný.  The power of linear programming for general-valued CSPs.  SIAM J. Comput., 44(1):1–36, 2015.  arXiv:1311.4219, doi:10.1137/130945648.
  * [56] Marcin Kozik.  Solving CSPs Using Weak Local Consistency.  SIAM J. Comput., 50(4):1263–1286, 2021.  arXiv:1605.00565, doi:10.1137/18M117577X.
  * [57] Marcin Kozik and Joanna Ochremiak.  Algebraic properties of valued constraint satisfaction problem.  In Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP’15), volume 9134 of Lecture Notes in Computer Science, pages 846–858. Springer, 2015.  arXiv:1403.0476, doi:10.1007/978-3-662-47672-7_69.
  * [58] Andrei Krokhin and Jakub Opršal.  The complexity of 3-colouring $H$-colourable graphs.  In Proc. 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS’19), pages 1227–1239, 2019.  arXiv:1904.03214, doi:10.1109/FOCS.2019.00076.
  * [59] Gábor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou.  Linear programming, width-1 CSPs, and robust satisfaction.  In Proc. 3rd Innovations in Theoretical Computer Science (ITCS’12), pages 484–495. ACM, 2012.  doi:10.1145/2090236.2090274.
  * [60] Gábor Kun and Mario Szegedy.  A new line of attack on the dichotomy conjecture.  Eur. J. Comb., 52:338–367, 2016.  doi:10.1016/j.ejc.2015.07.011.
  * [61] Alan K. Mackworth.  Consistency in networks of relations.  Artif. Intell., 8(1):99–118, 1977.  doi:10.1016/0004-3702(77)90007-8.
  * [62] Anatolii Malcev.  Untersuchungen aus dem gebiete der mathematischen logik.  Journal of Symbolic Logic, 2(2), 1937.
  * [63] Prasad Raghavendra.  Optimal algorithms and inapproximability results for every CSP?  In Proc. 40th Annual ACM Symposium on Theory of Computing (STOC’08), pages 245–254, 2008.  doi:10.1145/1374376.1374414.
  * [64] Danny Rorabaugh, Claude Tardif, and David L. Wehlau.  Logical compactness and constraint satisfaction problems.  Log. Methods Comput. Sci., 13(1), 2017.  doi:10.23638/LMCS-13(1:1)2017.
  * [65] Thomas Schaefer.  The complexity of satisfiability problems.  In Proc. 10th Annual ACM Symposium on the Theory of Computing (STOC’78), pages 216–226, 1978.  doi:10.1145/800133.804350.
  * [66] Johan Thapper and Stanislav Živný.  The complexity of finite-valued CSPs.  J. ACM, 63(4):37:1–37:33, 2016.  arXiv:1210.2987, doi:10.1145/2974019.
  * [67] Johan Thapper and Stanislav Živný.  The power of Sherali-Adams relaxations for general-valued CSPs.  SIAM J. Comput., 46(4):1241–1279, 2017.  arXiv:1606.02577, doi:10.1137/16M1079245.
  * [68] Johan Thapper and Stanislav Živný.  The limits of SDP relaxations for general-valued CSPs.  ACM Trans. Comput. Theory, 10(3):12:1–12:22, 2018.  arXiv:1612.01147, doi:10.1145/3201777.
  * [69] Avi Wigderson.  Improving the performance guarantee for approximate graph coloring.  J. ACM, 30(4):729–735, 1983.  doi:10.1145/2157.2158.
  * [70] Marcin Wrochna and Stanislav Živný.  Improved hardness for $H$-colourings of $G$-colourable graphs.  In Proc. 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA’20), pages 1426–1435, 2020.  arXiv:1907.00872, doi:10.1137/1.9781611975994.86.
  * [71] Dmitriy Zhuk.  A proof of the CSP dichotomy conjecture.  J. ACM, 67(5):30:1–30:78, 2020.  arXiv:1704.01914, doi:10.1145/3402029.