1. Introduction
Let
$\Gamma$
be a countable group and
$\mu$
be a probability measure on it. A
$\mu$
-random walk
$\{w_n\}_{n \in {\mathbb Z}_+}$
starting from the identity
$\textrm {id}$
is defined by
$w_n\,:\!=\,x_1 \cdots x_n$
and
$w_0\,:\!=\,\textrm {id}$
for an independent, identically distributed sequence
$x_1, x_2, \ldots$
with the common law
$\mu$
. The distribution of
$w_n$
is the
$n$
-fold convolution
$\mu _n\,:\!=\,\mu ^{\ast n}$
. The noise sensitivity problem for random walks on groups asks: Does resampling a small fraction of increments
$x_1, x_2, \ldots$
produce an almost independent copy of
$w_n$
or a highly correlated copy of
$w_n$
?
The precise definition is as follows. For a real
$\rho \in [0, 1]$
, let
\begin{equation*} \pi ^\rho \,:\!=\,\rho (\mu \times \mu ) +(1-\rho )\mu _{\textrm {diag}} \quad \text{on $\Gamma \times \Gamma $}, \end{equation*}
where
$\mu \times \mu$
denotes the product measure and
$\mu _{\textrm {diag}}((x, y))\,:\!=\,\mu (x)$
if
$x=y$
and
$0$
otherwise. Let us consider a
$\pi ^\rho$
-random walk
$\{{\boldsymbol w}_n\}_{n\in {\mathbb Z}_+}$
starting from the identity on
$\Gamma \times \Gamma$
. We say that the
$\mu$
-random walk is noise sensitive in total variation if
\begin{equation*} \lim _{n \to \infty }\|\pi ^\rho _n-\mu _n \times \mu _n\|_{\textrm {TV}} =0 \quad \text{for all $\rho \in (0, 1]$}. \end{equation*}
In the above, the total variation distance coincides with the half of
$\ell ^1$
-norm,
\begin{equation*} \|\nu _1-\nu _2\|_{\textrm {TV}}=\max _{A \subset \Gamma \times \Gamma }|\nu _1(A)-\nu _2(A)|=\frac {1}{2}\sum _{{\boldsymbol x} \in \Gamma \times \Gamma }|\nu _1({\boldsymbol x})-\nu _2({\boldsymbol x})|, \end{equation*}
where
$\nu _i$
are probability measures on
$\Gamma \times \Gamma$
,
$i=1, 2$
. Since we use only total variation distance in the definitions, let us simply say noise sensitive if there is no danger of confusion.
If a
$\mu$
-random walk on
$\Gamma$
is noise sensitive, then informally speaking, the situation is as in the following: For each fixed
$\rho \in (0, 1]$
even though it is close to
$0$
, resampling a
$\rho$
-portion of increments produces an asymptotically independent copy of the original
$\mu$
-random walk.
The definition of noise sensitivity for random walks on groups was introduced by Benjamini and Brieussel in [Reference Benjamini and Brieussel2, Definition 2.1]. In their paper, they discuss the notion and the variants not only in total variation (there it is called
$\ell ^1$
-noise sensitivity) but also in other distances or in terms of entropy. See also the related discussion in [Reference Kalai4, Section 3.3.4]. It has been observed that on finite groups random walks are noise sensitive in all natural definitions [Reference Benjamini and Brieussel2, Proposition 5.1]. This raises a challenge to find finitely generated infinite groups on which random walks are noise sensitive. Further the problem becomes more restrictive by measuring the distance in total variation. A simple observation using the central limit theorem shows that standard random walks on finite rank free abelian groups
${\mathbb Z}^m$
are not noise sensitive [Reference Benjamini and Brieussel2, Theorem 1.1 (1)]. Benjamini and Brieussel have shown that on the infinite dihedral group some lazy simple random walk is noise sensitive [Reference Benjamini and Brieussel2, Theorem 1.4]. So far, this has been the only known random walk which is noise sensitive in total variation on a finitely generated infinite group. We provide a class of such groups on which natural random walks are noise sensitive.
Theorem 1.1.
Let
$\Gamma$
be an affine Weyl group with the standard set of generators
$S$
, and
$\mu$
be a probability measure on
$\Gamma$
such that the support of
$\mu$
equals
$S\cup \{\textrm {id}\}$
. For all
$\rho \in (0, 1]$
,
\begin{equation*} \lim _{n \to \infty }\|\pi ^\rho _n-\mu _n\times \mu _n\|_{\textrm {TV}}=0, \end{equation*}
that is, the
$\mu$
-random walk on
$\Gamma$
is noise sensitive in total variation.
For the definition of affine Weyl groups, see Section 2.1. The infinite dihedral group
\begin{equation*} D_\infty \,:\!=\,\langle s_1, s_2 \mid s_1^2=s_2^2=\textrm {id} \rangle \quad \text{with $S=\{s_1, s_2\}$} \end{equation*}
is an example of affine Weyl group called type
$\widetilde A_1$
. See more examples of affine Weyl groups in Section 4.2. In fact, there exist a constant
$C\gt 0$
and an integer
$m\gt 0$
such that for all integer
$n\gt 1$
,
\begin{equation*} \|\pi ^\rho _n-\mu _n\times \mu _n\|_{\textrm {TV}} \le \frac {C(\log n)^m}{\sqrt {n}}. \end{equation*}
This strengthening of Theorem 1.1 is stated below as Theorem 4.1.
In Theorem 1.1, the laziness (i.e.
$\mu (\textrm {id})\gt 0$
) is crucial since otherwise the random walk on that group is not necessarily noise sensitive. This in particular shows that the noise sensitivity is a property of the random walk rather than the group as was pointed out in [Reference Benjamini and Brieussel2]. Let us note that the
$\mu$
-random walk on the infinite dihedral group considered there has a particular form:
$\mu (s_1)=\mu (s_2)=\mu (\textrm {id})=1/3$
. It is not clear from their proof whether changing the laziness (i.e. the measure on the identity element) would still provide a noise sensitive random walk or not. We show that this is indeed the case, furthermore,
$\mu$
is allowed to be a non-uniform distribution on
$S\cup \{\textrm { id}\}$
.
In general, the following is known for a finitely supported probability measure
$\mu$
: If either the group
$\Gamma$
admits a surjective homomorphism onto
$\mathbb Z$
, or
$(\Gamma , \mu )$
is non-Liouville, that is, there exists a non-constant bounded
$\mu$
-harmonic function on
$\Gamma$
, then a
$\mu$
-random walk on
$\Gamma$
is not noise sensitive [Reference Benjamini and Brieussel2, Theorem 1.1 (2)]. In a more specific class of
$(\Gamma , \mu )$
(where possibly
$\Gamma$
does or does not admit a surjective homomorphism onto
$\mathbb Z$
), a strong negation of noise sensitivity has been shown for non-elementary word hyperbolic groups, for example, free groups of rank at least
$2$
. If
$\mu$
is non-elementary and has a finite first moment, then there exists a
$\rho _0 \in (0, 1]$
such that
$\|\pi ^\rho _n -\mu _n\times \mu _n\|_{\textrm {TV}} \to 1$
as
$n \to \infty$
for all
$\rho \in [0, \rho _0)$
[Reference Tanaka11, Theorem 1.3]. In this generality, it is not known as to whether
$\rho _0=1$
or not. Note that it is rather straightforward to check that
$\rho _0=1$
for simple random walks on free semi-groups of rank at least
$2$
, cf. [Reference Tanaka11, Introduction].
1.1. Outline of the proof of Theorem 1.1
An affine Weyl group
$(\Gamma , S)$
with the standard set of generators
$S$
is associated with some Euclidean space
${\mathbb R}^m$
. The group
$\Gamma$
acts on
${\mathbb R}^m$
isometrically and generators act as reflections relative to hyperplanes. The group
$\Gamma$
has the form
$\Lambda \rtimes W$
where
$\Lambda$
is identified with a lattice in
${\mathbb R}^m$
and
$W$
is a finite group (called a spherical Weyl group). There is a point
$o$
in
${\mathbb R}^m$
such that the orbit map
${\Phi }: x \mapsto x.o$
is injective. Taking a conjugate by a translation if necessary, we assume that
$o$
is the origin in
${\mathbb R}^m$
(see Section 2.1 for the precise discussion). A main ingredient is to establish a local central limit theorem (Theorem 3.6). We define a discrete normal distribution
${\mathcal N}^{\Phi }_{n{\Sigma }}$
on
$\Gamma$
induced from the normalised restriction on
${\Phi }(\Gamma )$
of the
$m$
-dimensional Gaussian density function with a covariance matrix
$n{\Sigma }$
. Further we show the following: The distribution
$\mu _n$
is approximated by
${\mathcal N}^{\Phi }_{n{\Sigma }}$
uniformly on
$\Gamma$
within an error of order
$n^{-\frac {m+1}{2}}$
as
$n$
tends to infinity. The local central limit theorem itself follows from a classical argument based on characteristic functions. Some more general results (other than the Cayley graphs of affine Weyl groups) have been proved, for example, in [Reference Krámli and Szász5,Reference Pollicott and Sharp9,Reference Kotani, Shirai and Sunada7, and [Reference Sunada10]. We provide the proof of the local central limit theorem in our setting with an error estimate. Furthermore, we use an explicit form of matrix
$\Sigma$
in terms of harmonic
$1$
-forms on a finite quotient graph of the Cayley graph by the lattice
$\Lambda$
. The matrix
$\Sigma$
is obtained as some limiting form, which has previously appeared in the literature of symbolic dynamics, see for example [Reference Pollicott and Sharp9]; however, the explicit form in Theorem 3.6 plays an important role.
We apply this discussion to
$(\Gamma \times \Gamma , \pi ^\rho )$
for
$\rho \in (0, 1]$
. The local central limit theorem enables us to show that there exists a constant
$C\gt 0$
such that for all large enough
$n$
,
\begin{equation*} \|\pi ^\rho _n-{\mathcal N}^{\Phi }_{n{\Sigma }^\rho }\|_{\textrm {TV}} \le \frac {C(\log n)^m}{\sqrt {n}}. \end{equation*}
See Theorem 3.8. (For the discussion on the sharpness of this bound, see Remark 3.9.) If
$\mu$
has support
$S\cup \{\textrm {id}\}$
, then
$\pi ^\rho$
has support
$(S\cup \{\textrm {id}\})^2$
consisting of elements of order at most
$2$
. The explicit formula of the covariance matrix implies that
${\Sigma }^\rho$
has a block diagonal form and
${\Sigma }^\rho ={\Sigma }^1$
for all
$\rho \in (0, 1]$
. (This is the only part where we use the particular structure of the generating set). Thus by the triangle inequality we conclude Theorem 1.1 (in Theorem 4.1). Let us note that if the support of
$\mu$
does not contain
$\textrm {id}$
, then the support of
$\pi ^\rho$
does not generate the group
$\Gamma \times \Gamma$
(cf. Section 4.1).
1.2. Organisation
In Section 2, we introduce affine Weyl groups and discuss background. In Section 3, we show the local central limit theorem in a slightly extended setting (Theorem 3.6). In Section 4, we deduce noise sensitivity for affine Weyl groups (Theorem 4.1), presenting explicit examples (Section 4.2). In Appendix A, we include the result (Theorem A.1) on
${\mathbb Z}^m$
for the sake of convenience.
1.3. Notations
For a constant
$C$
, we write
$C=C_{\Sigma }$
to indicate its dependence on
$\Sigma$
. For non-negative real-valued functions
$f$
and
$g$
on a common (sub-)set of non-negative integers
${\mathbb Z}_+$
, we write
$f(n)=O(g(n))$
or
$f\ll g$
if there exists a constant
$C$
such that
$f(n)\le C g(n)$
for all large enough
$n$
. We also write
$f(n)=O_{\Sigma }(g(n))$
if
$C=C_{{\Sigma }}$
in the above notation. Further we write
$f(n)=\Omega (g(n))$
if there exists a constant
$c\gt 0$
such that
$f(n) \ge c g(n)$
for all large enough
$n$
, and
$f(n)=\Theta (g(n))$
if
$f\ll g$
and
$g\ll f$
. For a set
$A$
, we denote by
$|A|$
the cardinality.
2. Preliminaries
For a group
$\Gamma$
and for a subset
$A$
in
$\Gamma$
, we write
$\Gamma =\langle A \rangle$
if
$\Gamma$
is generated by
$A$
as a semigroup, that is, every element in
$\Gamma$
is obtained as a product of some finite sequence of elements from
$A$
. Let
$\Gamma$
be a finitely generated group with a finite symmetric set of generators
$S$
, that is,
$\Gamma =\langle S \rangle$
and
$S$
is invariant under the map
$s \mapsto s^{-1}$
. It holds that, in fact,
$s=s^{-1}$
for all
$s \in S$
if
$S$
consists of involutions. (This is the case of an (affine) Weyl group
$(\Gamma , S)$
in the following discussion.) Let
$\textrm {Cay}(\Gamma , S)$
be the (right) Cayley graph of
$\Gamma$
with respect to
$S$
, that is, the set of vertices is
$\Gamma$
and an edge
$\{x, y\}$
is defined if and only if
$x^{-1}y \in S$
. Since
$S$
is invariant under
$s \mapsto s^{-1}$
, the Cayley graph is defined as an undirected graph. For
$x \in \Gamma$
, let
$|x|_S$
denote the word norm with respect to
$S$
, that is, the graph distance between
$\textrm {id}$
and
$x$
in
$\textrm {Cay}(\Gamma , S)$
.
2.1 Affine Weyl groups
Let
$(\Gamma , S)$
be an affine Weyl group where
$S$
is a canonical finite set of generators, consisting of involutions, that is,
$s^2=\textrm {id}$
for every
$s \in S$
. The group
$\Gamma$
admits a semi-direct product structure
$\Gamma =\Lambda \rtimes W$
where the subgroup
$W$
called the spherical Weyl group is finite and the normal subgroup
$\Lambda$
is isomorphic to a free abelian group of finite rank. For a thorough background on the subject, we refer to [Reference Abramenko and Brown1]. We also refer to Section 4.2 for the examples most relevant to the present discussion.
The group
$\Gamma$
is equipped with an isometric action on the standard Euclidean space
${\mathbb R}^m$
for some
$m\ge 1$
, where each generator
$s \in S$
acts as a reflection with respect to an affine hyperplane. The action is properly discontinuous and admits a relatively compact convex fundamental domain with nonempty interior
$C_0$
called a chamber. The group
$\Gamma$
acts on the set of chambers
${\mathcal C}\,:\!=\,\{x C_0\}_{x \in \Gamma }$
simply transitively, that is, for all
$C_1, C_2 \in {\mathcal C}$
there exists
$x \in \Gamma$
such that
$C_1=xC_2$
, and if
$x C_0=C_0$
, then
$x=\textrm { id}$
. The normal subgroup
$\Lambda$
acts freely (i.e. without fixed points) as translations on
${\mathbb R}^m$
. The
$\Lambda$
-orbit of the origin is a lattice:
\begin{equation*} \big \{ a_1 v_1+\cdots +a_m v_m : a_1, \ldots , a_m \in {\mathbb Z}\big \}, \end{equation*}
where
$v_1, \ldots , v_m$
form a basis in
${\mathbb R}^m$
. We identify
$\Lambda$
with the lattice in
${\mathbb R}^m$
. Note that the action of
$W$
preserves
$\Lambda$
.
The affine Weyl group
$(\Gamma , S)$
is called reducible if there exist nontrivial affine Weyl groups generated by
$S_1$
and
$S_2$
respectively with
$S=S_1\times \left \{ \textrm {id} \right \} \cup \left \{ \textrm {id} \right \}\times S_2$
for which
$\Gamma =\langle S_1 \rangle \times \langle S_2 \rangle$
, and irreducible otherwise. The group
$\Gamma$
we consider is possibly (and basically) reducible. Irreducible ones are completely classified in terms of root systems. For example, the affine Weyl group of type
$\widetilde A_1$
is the infinite dihedral group
\begin{equation*} \langle s_1, s_2 \mid s_1^2=s_2^2=\textrm {id} \rangle , \end{equation*}
where
$s_1$
and
$s_2$
act as reflections with respect to
$0$
(the origin) and
$1$
, respectively, in
$\mathbb R$
. A chamber has the form of interval
$[0, 1)$
.
Let us fix a point
$o$
in the interior of a chamber and define
\begin{equation*} {\Phi }: \Gamma \to {\mathbb R}^m, \quad x \mapsto x.o. \end{equation*}
The map
$\Phi$
is injective since
$\Gamma$
acts on the set of chambers simply transitively, and is
$\Gamma$
-equivariant, that is,
${\Phi }(xy)=x.{\Phi }(y)$
for all
$x, y \in \Gamma$
. Let us call
${\Phi }:\Gamma \to {\mathbb R}^m$
an associated equivariant embedding. Since the generators act as reflections with respect to affine hyperplanes, it is illustrative to consider that
$\textrm {Cay}(\Gamma , S)$
is realised in
${\mathbb R}^m$
via the map
$\Phi$
. Namely, the vertices are placed inside of the chambers as the orbit
$x.o$
for
$x \in \Gamma$
and an edge is a line segment connecting two vertices for which one is obtained from the other by a reflection of the form
$x s x^{-1}$
for
$s \in S$
and
$x \in \Gamma$
.
The group
$\Lambda$
itself acts on
$\textrm {Cay}(\Gamma , S)$
from left freely as automorphisms of the graph. Let us consider the quotient graph
$G=\Lambda \backslash \textrm {Cay}(\Gamma , S)$
. The graph
$G=(V(G), E^{un}(G))$
is finite, the set of vertices
$V(G)$
is
$W$
and the set of edges
$E^{un}(G)$
consists of undirected edges. Note, however, that
$G$
is not the right Cayley graph of
$W$
with respect to the image
$\overline S$
of
$S$
under the quotient map
$\Lambda \rtimes W \to W$
. This is because the quotient map restricted on
$S$
is not bijective onto
$\overline S$
. The graph
$G$
has possibly multiple edges.
2.2 Pointed finite networks as quotients
The main interest is on an affine Weyl group
$\Gamma$
and the canonical set of generators
$S$
. It is, however, useful to discuss a slightly more general setting. Let
$\Gamma$
be a virtually finite rank free abelian group, that is,
$\Gamma$
admits a finite rank free abelian group
$\Lambda$
as a finite index subgroup. We assume that
$\Gamma$
acts on an
${\mathbb R}^m$
isometrically with a relatively compact fundamental domain with nonempty interior, and that
$\Lambda$
acts as translations and is identified with a lattice in
${\mathbb R}^m$
. Let us fix a point
$o$
in the interior of such a fundamental domain of
$\Gamma$
and define
${\Phi }:\Gamma \to {\mathbb R}^m$
by
$x \mapsto x.o$
. The map
$\Phi$
is equivariant with
$\Gamma$
-actions and injective. For a finite symmetric set of generators
$S$
in
$\Gamma$
, let
\begin{equation*} G\,:\!=\,\Lambda \backslash \textrm {Cay}(\Gamma , S). \end{equation*}
The quotient
$G=(V(G), E^{un}(G))$
is a finite (undirected) graph possibly with multiple edges (whence a multi-graph) and with loops. It holds that
$V(G)=\Lambda \backslash \Gamma$
and
\begin{equation*} E^{un}(G)=\{\{x, x.s\} \ : \ x \in \Lambda \backslash \Gamma , \ s \in S\}, \end{equation*}
where
$\{x, x.s\}$
and
$\{x.s, x\}$
are identified. For the examples, see Section 4.2.
Let
$\mu$
be a probability measure on
$\Gamma$
such that the support
$\textrm {supp}\, \mu$
of
$\mu$
is finite, that
$\Gamma =\langle \textrm {supp}\, \mu \rangle$
, and that
$\mu$
is symmetric, that is,
$\mu (s)=\mu (s^{-1})$
for every
$s \in \textrm {supp}\, \mu$
. If we define
$S=\textrm {supp}\, \mu$
, then
$S$
is a finite symmetric set of generators. Let
\begin{equation*} p(\{x, x.s\})\,:\!=\,\mu (s) \quad \text{for $\{x, x.s\} \in E^{un}(G)$}. \end{equation*}
This defines a Markov chain on
$G=\Lambda \backslash \textrm {Cay}(\Gamma , S)$
with transition probabilities
\begin{equation*} \sum _{s \in S, y=x.s}\mu (s) \quad \text{for $x, y \in \Lambda \backslash \Gamma $}. \end{equation*}
Note that this Markov chain is irreducible, that is, it visits every vertex from every other vertex after some time since
$\Gamma =\langle \textrm {supp}\, \mu \rangle$
. Furthermore, it is reversible with respect to the uniform distribution
$\pi$
on the set of vertices
$V(G)=\Lambda \backslash \Gamma$
. Indeed, since
$\mu$
is symmetric, it holds that
\begin{equation} \pi (x) p(\{x, x.s\})=\pi (x.s) p(\{x.s, x\}) \quad \text{for $\{x, x.s\} \in E^{un}(G)$}, \end{equation}
where
$\pi (x)=1/|V(G)|$
for
$x \in V(G)$
. Note that if
$\mu (\textrm {id})\gt 0$
, then
$p(x, x) \ge \mu (\textrm {id})\gt 0$
for every
$x \in V(G)$
. For each
$\{x, y\} \in E^{un}(G)$
, let us define the conductance by
\begin{equation*} c(\{x, y\})\,:\!=\,\pi (x)p(\{x, y\}). \end{equation*}
This is well-defined since
$c(\{x, y\})=c(\{y, x\})$
by (2.1). Note that
$c(\{x, y\})\gt 0$
for all
$\{x, y\} \in E^{un}(G)$
. Let
$x_0 \in \Lambda \backslash \Gamma$
denote the coset containing
$\textrm {id}$
. Let us call
$(G, c, x_0)$
the pointed (finite) network as the finite multi-graph
$G$
equipped with the conductance
$c:E^{un}(G) \to (0, \infty )$
and the point
$x_0$
.
3. Local central limit theorems
3.1
Harmonic
$1$
-forms on finite graphs
Let
$(G, c, x_0)$
be the pointed finite network. Henceforth it is convenient to consider
$G$
as a graph with orientations where each edge (and loop) has both possible orientations. Let
\begin{equation*} E(G)\,:\!=\,\big \{(x, y), (y, x) \ : \ \{x, y\} \in E^{un}(G)\big \}. \end{equation*}
For
$e=(x, y)$
, we write
$\overline e=(y, x)$
. The ‘reversing direction’ operation
$\overline {\ \cdot \ }: E(G) \to E(G)$
,
$e\mapsto \overline e$
, defines a bijection and
$\overline {\overline e}=e$
for
$e \in E(G)$
. For
$e=(x, y) \in E(G)$
, let us denote by
$oe\,:\!=\,x$
the origin and by
$te\,:\!=\,y$
the terminus of
$e$
respectively. We have that
$o\overline e=te$
for
$e \in E(G)$
. Let us also consider
$\textrm {Cay}(\Gamma , S)$
as a graph with orientations, defining both possible orientations for each edge and loop. Letting
$c(e)\,:\!=\,c(x, y)$
and
$p(e)\,:\!=\,p(x, y)$
for
$e=(x, y)$
, we have that
$c(e)=c(\overline e)$
and
$c(e)=\pi (oe)p(e)$
for
$e \in E(G)$
. It holds that by the definition of conductance,
\begin{equation*} \pi (x)=\sum _{e \in E_x} c(e), \quad \text{where $E_x\,:\!=\,\big \{e \in E(G) \ : \ oe=x\big \}$ for $x \in V(G)$}. \end{equation*}
Let us define the
$\mathbb C$
-linear space of complex-valued functions on
$V(G)$
by
\begin{equation*} C^0(G, {\mathbb C})\,:\!=\,\big \{f: V(G) \to {\mathbb C}\big \} \end{equation*}
equipped with the inner product
$\langle f_1, f_2 \rangle _\pi \,:\!=\,\sum _{x \in V(G)}f_1(x)\overline {f_2(x)}\pi (x)$
, where
$\overline {a}$
stands for the complex-conjugate of
$a \in {\mathbb C}$
. Similarly, let
$C^0(G, {\mathbb R})$
be the
$\mathbb R$
-linear space of real-valued functions on
$V(G)$
endowed with the inner product as the restriction of
$\langle \cdot , \cdot \rangle _\pi$
. Further let us define the
$\mathbb R$
-linear space of real-valued
$1$
-forms on
$E(G)$
by
\begin{equation*} C^1(G, {\mathbb R})\,:\!=\,\big \{\omega : E(G) \to {\mathbb R} \ : \ \text{$\omega (\overline e)=-\omega (e)$ for $e \in E(G)$}\big \} \end{equation*}
equipped with the inner product
$\langle \omega _1, \omega _2 \rangle _c\,:\!=\,(1/2)\sum _{e \in E(G)}\omega _1(e)\omega _2(e)c(e)$
. The differential
$d: C^0(G, {\mathbb R}) \to C^1(G, {\mathbb R})$
is the
$\mathbb R$
-linear map defined by
\begin{equation*} df(e)\,:\!=\,f(te)-f(oe) \quad \text{for $e \in E(G)$}. \end{equation*}
Moreover, the adjoint
$d^\ast :C^1(G, {\mathbb R}) \to C^0(G, {\mathbb R})$
with respect to the inner products is obtained by
\begin{equation*} d^\ast \omega (x)\,:\!=\,-\sum _{e \in E_x}\frac {1}{\pi (x)}c(e) \omega (e) \quad \text{for $x \in V(G)$}. \end{equation*}
It holds that for
$f \in C^0(G, {\mathbb R})$
and
$\omega \in C^1(G, {\mathbb R})$
,
\begin{equation} \langle df, \omega \rangle _c=\langle f, d^\ast \omega \rangle _\pi . \end{equation}
Note that if we define the transition operator
$P$
on
$C^0(G, {\mathbb R})$
to itself by
\begin{equation*} Pf(x)\,:\!=\,\sum _{e \in E_x}\frac {1}{\pi (x)}c(e)f(te) \quad \text{for $x \in V(G)$}, \end{equation*}
then
$d^\ast d=I-P$
where
$I$
is the identity operator. Let us define the space of harmonic
$1$
-forms by
\begin{equation*} H^1\,:\!=\,\big \{\omega \in C^1(G, {\mathbb R}) \ : \ d^\ast \omega =0\big \}. \end{equation*}
Note that
$H^1=(\textrm {Im} d)^\bot$
the orthogonal complement of the image
$\textrm {Im} d$
by (3.1). The fact that we use in the sequel is that for every
$1$
-form
$\omega \in C^1(G, {\mathbb R})$
there exists a unique harmonic
$1$
-form
$u \in H^1$
and some
$f \in C^0(G, {\mathbb R})$
such that
\begin{equation*} u+df=\omega . \end{equation*}
The
$u$
is obtained as the
$H^1$
-part in the orthogonal decomposition
$C^0(G, {\mathbb R})=H^1\oplus \textrm {Im} d$
. Note that
$f$
is not unique since every
$f$
added a constant function satisfies the relation.
Remark 3.1. If we endow
$G$
with a structure of
$1$
-dimensional CW complex, then the
$1$
-cohomology group with real coefficient is defined as
$H^1(G, {\mathbb R})\,:\!=\,C^1(G, {\mathbb R})/\textrm {Im} d$
. The fact mentioned above means that every
$1$
-cohomology class is represented by a unique harmonic
$1$
-form. Although all these notions are not needed in our discussion, it might be useful to grasp an idea behind some of our computations.
3.2 Perturbations of transfer operators
For each
$1$
-form
$\omega \in C^1(G, {\mathbb R})$
, let us define the transfer operator on
$C^0(G, {\mathbb C})$
by
\begin{equation*} {\mathcal L}_\omega f(x)\,:\!=\,\sum _{e \in E_x}p(e) e^{2\pi i \omega (e)}f(te) \quad \text{for $x \in V(G)$}. \end{equation*}
Here
$i=\sqrt {-1}$
. In this particular setting where
$\mu$
is symmetric, the transfer operator is self-adjoint on
$(C^0(G, {\mathbb C}), \langle \cdot , \cdot \rangle _\pi )$
. Hence, it has real eigenvalues. Let
$\lambda (\omega )$
be the largest eigenvalue of
${\mathcal L}_\omega$
. If
$\omega =0$
, then
$\lambda (0)=1$
and this is a simple eigenvalue by the Perron–Frobenius theorem since
${\mathcal L}_0=P$
and
$P$
is irreducible. We apply to an analytic perturbation in
$\omega$
: for a small enough neighbourhood
$U$
of
$0$
in
$C^1(G, {\mathbb R})$
, the function
$U \to {\mathbb R}$
,
$\omega \mapsto \lambda (\omega )$
is real analytic. Moreover, corresponding eigenvectors
$f_\omega$
depend analytically in
$\omega \in U$
with
$f_0={\bf 1}$
(the constant vector with all
$1$
’s). This follows from the implicit function theorem for
$\det (tI-{\mathcal L}_\omega )=0$
around
$(t, \omega )=(1, 0)$
in this finite graph setting. Note that if we consider
$\omega +d{\varphi }$
for
${\varphi } \in C^0(G, {\mathbb R})$
in place of
$\omega$
, then
${\mathcal L}_{\omega +d{\varphi }}=e^{-2\pi i{\varphi }}{\mathcal L}_\omega e^{2\pi i{\varphi }}$
, where
$(e^{\varphi } f)(x)\,:\!=\,e^{{\varphi }(x)}f(x)$
for
$x \in V(G)$
, and thus
\begin{equation*} \lambda (\omega +d{\varphi })=\lambda (\omega ). \end{equation*}
This shows that
$\lambda (\omega )$
depends only on the harmonic
$H^1$
-part of
$\omega$
. Let
\begin{equation*} \beta (\omega )\,:\!=\,\log \lambda (\omega ). \end{equation*}
Since
${\mathcal L}_0=P$
which has a simple eigenvalue
$\lambda (0)=1$
, there exists a small enough open neighbourhood
$U$
of
$0$
in
$C^1(G, {\mathbb R})$
such that
$\lambda (\omega )$
is a simple eigenvalue of
${\mathcal L}_{\omega }$
and
$\beta (\omega )=\log \lambda (\omega )$
is well-defined for all
$\omega \in U$
. It holds that
$\beta (0)=0$
since
$\lambda (0)=1$
.
Lemma 3.2.
Let
$\lambda (\omega )=e^{\beta (\omega )}$
and
$f_\omega$
be the eigenvalue and the corresponding eigenvector of
${\mathcal L}_\omega$
such that
$f_0={\bf 1}$
and
$\langle f_\omega , {\bf 1} \rangle _\pi =1$
for
$\omega \in U$
where
$U$
is a neighbourhood of
$0$
in
$C^1(G, {\mathbb R})$
. For all harmonic
$1$
-forms
$u, u_i \in H^1$
on
$G$
and real parameters
$r, r_i$
for
$i=1,2,3$
, the following holds:
\begin{equation} \frac {d}{dr}\Big |_{r=0}\beta (ru)=0, \end{equation}
\begin{equation} \frac {d}{dr}\Big |_{r=0}f_{ru}(x)=0 \quad \text{for all $x \in V(G)$}, \end{equation}
\begin{equation} \frac {\partial ^2}{\partial r_1 \partial r_2}\Big |_{(r_1, r_2)=(0, 0)}\beta (r_1 u_1+r_2 u_2)=-4\pi ^2 \sum _{e \in E(G)}u_1(e)u_2(e)c(e), \end{equation}
and
\begin{equation} \frac {\partial ^3}{\partial r_1 \partial r_2 \partial r_3}\Big |_{(r_1, r_2, r_3)=(0, 0, 0)}\beta (r_1u_1+r_2u_2+r_3u_3)=0. \end{equation}
Proof.
Let
$f_\omega$
be the eigenvector normalised as stated. Since
$\overline {{\mathcal L}_\omega f_\omega }={\mathcal L}_{-\omega }\overline {f_\omega }$
holds for all
$\omega$
and
$\lambda (\omega )$
is real for all
$\omega$
in a small enough neighbourhood of
$0$
in
$C^1(G, {\mathbb R})$
, it holds that
$\lambda ({-}\omega )=\overline {\lambda (\omega )}=\lambda (\omega )$
. Thus,
$\beta ({-}\omega )=\beta (\omega )$
for all
$\omega \in U$
and all odd time derivatives of
$\beta$
at
$0$
vanish. This in particular implies (3.2) and (3.5).
For every
$1$
-form
$u$
, it holds that
$ru \in U$
for all small enough real
$r$
and
\begin{equation} \left \langle \frac {d}{d r}\Big |_{r=0}f_{ru}, {\bf 1}\right \rangle _\pi =0. \end{equation}
Moreover, since
$P$
is self-adjoint with respect to
$\langle \cdot ,\cdot \rangle _\pi$
and
$P{\bf 1}={\bf 1}$
, by (3.6) it holds that
\begin{equation} \left \langle P\left (\frac {d}{d r}\Big |_{r=0}f_{ru}\right ), {\bf 1}\right \rangle _\pi =\left \langle \frac {d}{d r}\Big |_{r=0}f_{ru}, P{\bf 1}\right \rangle _\pi =\left \langle \frac {d}{d r}\Big |_{r=0}f_{ru}, {\bf 1}\right \rangle _\pi =0. \end{equation}
We will also use the analogous identities to (3.6) and (3.7) for the second derivatives of the normalisation:
$\langle f_\omega , {\bf 1} \rangle _\pi =1$
for
$\omega \in U$
.
First differentiating
${\mathcal L}_{r u}f_{ru}=e^{\beta (ru)}f_{ru}$
at
$r=0$
yields for each
$x \in V(G)$
,
\begin{equation} \sum _{e \in E_x}\left (p(e)(2\pi i u(e))+p(e)\frac {d}{d r}\Big |_{r=0}f_{r u}(te)\right )= \frac {d}{d r}\Big |_{r=0}\beta (ru)+\frac {d}{d r}\Big |_{r=0}f_{ru}(x), \end{equation}
where we have used
$f_0={\bf 1}$
. Let us note that (3.8) above yields by (3.2) which we have just shown and by that
$d^\ast u=0$
,
\begin{equation*} P\left (\frac {d}{d r}\Big |_{r=0}f_{ru}\right )(x)=\frac {d}{d r}\Big |_{r=0}f_{ru}(x) \quad \text{for each $x \in V(G)$}. \end{equation*}
Since
$P$
has the simple eigenvalue
$1$
, this implies that
$(d/d r)|_{r=0}f_{ru}$
is constant. By (3.6), for every harmonic
$1$
-from
$u$
, it holds that
$(d/dr)|_{r=0}f_{ru}(x)=0$
for all
$x \in V(G)$
, showing (3.3).
For all
$1$
-forms
$u_1$
and
$u_2$
and for all small enough reals
$r_1$
and
$r_2$
, it holds that
\begin{equation*} {\mathcal L}_{r_1 u_1+r_2 u_2}f_{r_1, r_2}=e^{\beta _{r_1, r_2}}f_{r_1, r_2} \quad \text{where $\beta _{r_1, r_2}\,:\!=\,\beta (r_1u_1+r_2u_2)$ and $f_{r_1, r_2}\,:\!=\,f_{r_1 u_1+r_2 u_2}$}. \end{equation*}
Taking the second derivatives at
$(r_1, r_2)=(0, 0)$
of both terms yields by (3.2), (3.3) and that
$f_0={\bf 1}$
, for each
$x \in V(G)$
,
\begin{align*} &\sum _{e \in E_x}\Bigg (p(e)({-}4\pi ^2 u_1(e)u_2(e))+p(e)\frac {\partial ^2}{\partial r_1 \partial r_2}\Big |_{(r_1, r_2)=(0, 0)}f_{r_1, r_2}(te)\Bigg )\\ &\qquad \qquad \qquad \qquad \qquad \qquad =\frac {\partial ^2}{\partial r_1 \partial r_2}\Big |_{(r_1, r_2)=(0, 0)}\beta _{r_1, r_2} +\frac {\partial ^2}{\partial r_1 \partial r_2}\Big |_{(r_1, r_2)=(0, 0)}f_{r_1, r_2}(x). \end{align*}
Evaluating the inner products of the above terms with
$\bf 1$
leads
\begin{align*} &-4\pi ^2\sum _{e \in E(G)}c(e)u_1(e)u_2(e) +\left \langle P\left (\frac {\partial ^2}{\partial r_1 \partial r_2}\Big |_{(r_1, r_2)=(0, 0)}f_{r_1, r_2}\right ), {\bf 1}\right \rangle _\pi \\ &\qquad \qquad \qquad \qquad \qquad \qquad =\frac {\partial ^2}{\partial r_1 \partial r_2}\Big |_{(r_1, r_2)=(0, 0)}\beta _{r_1, r_2} +\left \langle \frac {\partial ^2}{\partial r_1 \partial r_2}\Big |_{(r_1, r_2)=(0, 0)}f_{r_1, r_2}, {\bf 1}\right \rangle _\pi . \end{align*}
The second terms in the left hand side and in the right hand side respectively are
$0$
since they are the second derivatives on the normalisation (cf. (3.6) and (3.7)). This proves (3.4).
3.3
An explicit Hessian formula in terms of harmonic
$1$
-forms
Recall that
${\Phi }:\Gamma \to {\mathbb R}^m$
,
$x \mapsto x.o$
. Taking a conjugate to the action of
$\Gamma$
by a translation in
${\mathbb R}^m$
, we assume that
$o$
is the origin, whence
${\Phi }(\textrm {id})=0$
. The function
$(x, y) \mapsto {\Phi }(y)-{\Phi }(x)$
for (oriented) edges
$(x, y)$
in
$\textrm {Cay}(\Gamma , S)$
is invariant under the action by
$\Lambda$
. Indeed, this follows since
$\Lambda$
is identified with a lattice and acts as translations in
${\mathbb R}^m$
. Therefore this descends to an
${\mathbb R}^m$
-valued function on
$E(G)$
, which we denote by
$e \mapsto {\Phi }_e$
for
$e \in E(G)$
. Note that
${\Phi }_{\overline e}=-{\Phi }_e$
for each
$e \in E(G)$
. Let
$\langle \cdot , \cdot \rangle$
be the standard inner product in
${\mathbb R}^m$
. For each
$v \in {\mathbb R}^m$
, let
\begin{equation*} \widehat v(e)\,:\!=\,\langle v, {\Phi }_e \rangle \quad \text{for $e \in E(G)$}. \end{equation*}
This
$\widehat v$
defines a
$1$
-form on
$G$
. For
$v \in {\mathbb R}^m$
near
$0$
, let
$\beta (v)\,:\!=\,\beta (\widehat v)$
where
$e^{\beta (v)}$
is the largest eigenvalue of the transfer operator
${\mathcal L}_{\widehat v}$
. Let us define the Hessian of
$\beta$
at
$0$
in
${\mathbb R}^m$
with the standard coordinate
$(r_1, \ldots , r_m)$
by
\begin{equation*} \textrm {Hess}_0\beta \,:\!=\,\left (\frac {\partial ^2}{\partial r_k\partial r_l}\Big |_{(r_1, \ldots , r_m)=(0, \ldots , 0)}\beta (r_1, \ldots , r_m)\right )_{k, l=1, \ldots , m}. \end{equation*}
For the pointed finite network
$(G, c, x_0)$
and
${\Phi }:\Gamma \to {\mathbb R}^m$
, we compute
$\textrm {Hess}_0\beta$
.
Lemma 3.3.
The Hessian
$\textrm {Hess}_0 \beta$
of
$\beta$
at
$0$
in
${\mathbb R}^m$
is non-degenerate and negative definite. Moreover, it holds that
\begin{equation} \langle v_1, \textrm {Hess}_0 \beta \, v_2 \rangle =-4\pi ^2\sum _{e \in E(G)}u_1(e)u_2(e)c(e), \end{equation}
where
$u_i$
is defined as the harmonic part of
$\widehat v_i$
for
$v_i \in {\mathbb R}^m$
,
$i=1, 2$
.
Proof.
For every
$v \in {\mathbb R}^m$
, we have
$\widehat v(e)=\langle v, {\Phi }_e \rangle$
for
$e \in E(G)$
, and
$u$
is the harmonic part of
$\widehat v$
, that is, the unique
$u \in H^1$
such that
$u+df=\widehat v$
for some
$f \in C^0(G, {\mathbb R})$
. Note that the resulting map
$v \mapsto u$
is
$\mathbb R$
-linear. Since
$\beta (v)$
depends only on the harmonic part of
$v$
, Lemma3.2 (3.4) implies that
\begin{align*} \langle v_1, \textrm {Hess}_0\beta \, v_2 \rangle &=\frac {\partial ^2}{\partial r_1 \partial r_2}\Big |_{(r_1, r_2)=(0, 0)}\beta (r_1 v_1+r_2 v_2)\\ &=\frac {\partial ^2}{\partial r_1 \partial r_2}\Big |_{(r_1, r_2)=(0, 0)}\beta (r_1 u_1+r_2 u_2)=-4\pi ^2\sum _{e \in E(G)}u_1(e)u_2(e) c(e). \end{align*}
This shows (3.9).
Let
$v_1, \ldots , v_m$
be a basis of the lattice in
${\mathbb R}^m$
:
$\Lambda =\big \{ a_1 v_1+\cdots +a_m v_m : a_1, \ldots , a_m \in {\mathbb Z}\big \}$
. For each
$v_k={\Phi }(v_k) \in \Lambda$
under the identification of
$\Lambda$
with the lattice, there exists a path
$(\widetilde e_1, \ldots , \widetilde e_n)$
from
$\textrm {id}$
to
$v_k$
in
$\textrm {Cay}(\Gamma , S)$
since the Cayley graph is connected. Let
$(e_1, \ldots , e_n)$
be the image in
$G$
of that path under the covering map from
$\textrm {Cay}(\Gamma , S)$
. Note that the image is a cycle:
$x_0=oe_1$
,
$te_i=oe_{i+1}$
for
$i=1, \ldots , n-1$
and
$te_n=x_0$
. Thus,
$\sum _{l=1}^n df(e_l)=0$
and
$\sum _{l=1}^n u(e_l)=\sum _{l=1}^n (u(e_l)+df(e_l))=\sum _{l=1}^n \widehat v(e_l)$
. Furthermore,
\begin{align*} \sum _{l=1}^n \widehat v(e_l)=\sum _{l=1}^n \langle v, {\Phi }_{e_l} \rangle =\sum _{l=1}^n \langle v, {\Phi }(t\widetilde e_l)-{\Phi }(o\widetilde e_l) \rangle =\left\langle v, \sum _{l=1}^n({\Phi }(t\widetilde e_l)-{\Phi }(o\widetilde e_l)) \right\rangle . \end{align*}
The last term equals
$\langle v, v_k \rangle$
since
$\sum _{l=1}^n ({\Phi }(t\widetilde e_l)-{\Phi }(o\widetilde e_l))={\Phi }(t\widetilde e_n)-{\Phi }(o \widetilde e_1)=v_k$
. This shows the following: For each
$k=1, \ldots , m$
there exists a cycle
$(e_1, \ldots , e_n)$
in
$G$
with
$x_0=oe_1$
and
$te_n=x_0$
such that
\begin{equation} \sum _{l=1}^n u(e_l)=\langle v, v_k \rangle . \end{equation}
For
$v \in {\mathbb R}^m$
, let us assume that
$\langle v, \textrm {Hess}_0\beta \, v \rangle =0$
. It holds that
$u=0$
by (3.9), and thus
$\langle v, v_k \rangle =0$
for every
$k=1, \ldots , m$
by (3.10). Hence,
$v=0$
since
$v_1, \ldots , v_m$
form a basis of a lattice in
${\mathbb R}^m$
. This shows that
$\textrm {Hess}_0\beta$
is non-degenerate. Furthermore
$\textrm {Hess}_0\beta$
is negative definite by (3.9).
Remark 3.4. Let us consider the Hessian
$\textrm {Hess}_{H^1}\beta$
of
$\beta$
at
$0$
on
$H^1$
, that is,
\begin{equation*} \langle u_1, \textrm {Hess}_{H^1}\beta \, u_2 \rangle _\pi =\frac {\partial ^2}{\partial r_1 \partial r_2}\Big |_{(r_1, r_2)=(0, 0)}\beta (r_1 u_1+r_2 u_2) \quad \text{for $u_1, u_2 \in H^1$}, \end{equation*}
where
$H^1 \to H^1: u \mapsto \textrm {Hess}_{H^1}\beta \, u$
defines an
$\mathbb R$
-linear map. Lemma3.2 (3.4) implies that
\begin{equation*} \langle u_1, \textrm {Hess}_{H^1}\beta \, u_2 \rangle _\pi =-4\pi ^2 \sum _{e \in E(G)}u_1(e)u_2(e)c(e), \end{equation*}
which shows that
$\textrm {Hess}_{H^1}\beta$
is non-degenerate and negative definite on
$H^1$
. There exists a natural inclusion
${\mathbb R}^m=H^1({\mathbb R}^m / \Lambda , {\mathbb R}) \to H^1(G, {\mathbb R})$
, represented by
${\mathbb R}^m\to H^1: v \mapsto u$
in Lemma3.3. In this identification,
$\textrm {Hess}_0\beta$
is the restriction of
$\textrm {Hess}_{H^1}\beta$
to
${\mathbb R}^m$
, and this implies that
$\textrm {Hess}_0\beta$
is non-degenerate and negative definite. A thorough framework is found in [Reference Sunada10]. We use the explicit form of
$\textrm {Hess}_0\beta$
later in our discussion.
3.4 Local central limit theorems
For every positive integer
$n \in {\mathbb Z}_{\gt 0}$
, it holds that
\begin{equation} {\mathcal L}_{\widehat v}^n {\bf 1}(x_0)=\sum _{(e_1, \ldots , e_n)}p(e_1)\cdots p(e_n)e^{2\pi i (\widehat v(e_1)+\cdots +\widehat v(e_n))}. \end{equation}
In the above the summation runs over all directed paths
$(e_1, \ldots , e_n)$
starting from
$x_0$
in
$G$
, that is,
$oe_1=x_0$
and
$t e_k=o e_{k+1}$
for each
$k=1, \ldots , n-1$
. For each such path
$(e_1, \ldots , e_n)$
, there exists a unique path
$(\widetilde e_1, \ldots , \widetilde e_n)$
which is a lift of the path, starting from
$\textrm {id}$
in
$\textrm {Cay}(\Gamma , S)$
. By a lift we mean that the path
$(e_1, \ldots , e_n)$
is the image of
$(\widetilde e_1, \ldots , \widetilde e_n)$
under the covering map
$\textrm {Cay}(\Gamma , S) \to G=\Lambda \backslash \textrm {Cay}(\Gamma , S)$
. The definition of the
$1$
-form
$\widehat v$
on
$G$
implies the following:
\begin{align*} \widehat v(e_1)+\cdots +\widehat v(e_n) &=\langle v, {\Phi }_{e_1} \rangle +\cdots +\langle v, {\Phi }_{e_n} \rangle \\ &=\langle v, {\Phi }(t\widetilde e_1)-{\Phi }(o \widetilde e_1) \rangle +\cdots +\langle v, {\Phi }(t\widetilde e_n)-{\Phi }(o\widetilde e_n) \rangle =\langle v, {\Phi }(t\widetilde e_n) \rangle , \end{align*}
where
${\Phi }(o\widetilde e_1)={\Phi }(\textrm {id})=0$
. Recall that
$p(e)=\mu (s)$
for
$e=(x, x.s) \in E(G)$
and
$s \in S$
in the pointed finite network
$(G, c, x_0)$
. By (3.11), it holds that
\begin{equation*} {\mathcal L}^n_{\widehat v}{\bf 1}(x_0)=\sum _{(\widetilde e_1, \ldots , \widetilde e_n)}\mu (s_1)\cdots \mu (s_n)e^{2\pi i \langle v, {\Phi }(t\widetilde e_n) \rangle } =\sum _{x \in \Gamma }\mu _n(x)e^{2\pi i \langle v, {\Phi }(x) \rangle }. \end{equation*}
In the above, the (edge) path
$(\widetilde e_1, \ldots , \widetilde e_n)$
is represented as the (vertex) path on
$\textrm {id}$
,
$s_1$
,
$s_1 s_2$
,
$\ldots$
,
$s_1\cdots s_n$
in
$\textrm {Cay}(\Gamma , S)$
. Therefore, letting
\begin{equation*} {\varphi }_{\mu _n}(v)\,:\!=\,\sum _{x \in \Gamma }\mu _n(x)e^{2\pi i\langle v, {\Phi }(x) \rangle } \quad \text{for $v \in {\mathbb R}^m$}, \end{equation*}
we have the following: For all
$v \in {\mathbb R}^m$
and all
$n\in {\mathbb Z}_{\gt 0}$
,
\begin{equation} {\mathcal L}_{\widehat v}^n{\bf 1}(x_0)={\varphi }_{\mu _n}(v). \end{equation}
Let
$\Lambda ^\ast$
be the dual lattice of
$\Lambda$
, that is,
\begin{equation*} \Lambda ^\ast \,:\!=\,\left\{a_1 v_1^\ast +\cdots +a_m v_m^\ast \ : \ a_1, \ldots , a_m \in {\mathbb Z}\right\}, \end{equation*}
where
$v_1^\ast , \ldots , v_m^\ast$
form the dual basis of
$v_1, \ldots , v_m$
in
${\mathbb R}^m$
:
$\langle v_k^\ast , v_l \rangle =1$
if
$k=l$
and
$0$
else. The fundamental parallelotope of
$\Lambda ^\ast$
in
${\mathbb R}^m$
is denoted by
\begin{equation*} D\,:\!=\,\left\{r_1 v_1^\ast +\cdots +r_m v_m^\ast \in {\mathbb R}^m \ : \ |r_i| \le 1/2, \ i=1, \ldots , m\right\}. \end{equation*}
The volume of
$D$
is assumed to be
$1$
up to a homothety in
${\mathbb R}^m$
. The Fourier inversion formula shows that for all
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{equation} \mu _n(x)=\int _D {\varphi }_{\mu _n}(v)e^{-2\pi i \langle v, {\Phi }(x) \rangle }\,dv \quad \text{for $x \in \Gamma $}. \end{equation}
For
$\delta \gt 0$
, let
\begin{equation*} D_\delta \,:\!=\,\left\{r_1 v_1^\ast +\cdots +r_m v_m^\ast \in {\mathbb R}^m \ : \ |r_i| \lt \delta , \ i=1, \ldots , m\right\}. \end{equation*}
Lemma 3.5.
If
$\mu (\textrm {id})\gt 0$
, then for all small enough
$\delta \gt 0$
, there exists a constant
$c_\delta \gt 0$
such that for all
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{equation*} |{\varphi }_{\mu _n}(v)|\le \sqrt {|V(G)|}\cdot e^{-c_\delta n} \quad \text{for all $v \in D \setminus D_\delta $}. \end{equation*}
Proof.
This uses a standard perturbation argument; we provide a proof for the sake of completeness. For
$v \in {\mathbb R}^m$
, let
$\|{\mathcal L}_{\widehat v}\|\,:\!=\,\max _{\|f\|_\pi =1}\|{\mathcal L}_{\widehat v}f\|_\pi$
where
$\|\cdot \|_\pi$
is the associated norm in
$C^0(G, {\mathbb C})$
. Since
${\mathcal L}_{\widehat v}$
is self-adjoint, the eigenvalues are real and the operator norm
$\|{\mathcal L}_{\widehat v}\|$
is the spectral radius
$|\lambda (v)|$
, that is, the largest eigenvalue in absolute value. Note that
$|\lambda (v)|\le 1$
. For
$v \in D$
, if
$|\lambda (v)|=1$
, then the condition
$\mu (\textrm {id})\gt 0$
implies that
$v=0$
(in which case in fact
$\lambda (0)\neq -1$
). Indeed, for the maximal eigenvalue
$\lambda (v)$
in absolute value and a corresponding eigenvector
$f_v$
, we have
${\mathcal L}_{\widehat v}f_v=\lambda (v)f_v$
. Taking absolute values shows that
$|f_v|\le P|f_v|$
, implying that
$|f_v|$
is a non-zero constant since
$P$
is irreducible. Further since
$f_v$
is an eigenvector with the eigenvalue
$1$
in absolute value,
$\lambda (v)f_v(x)$
and
$e^{2\pi i \langle v, {\Phi }_e \rangle }f_v(te)$
for
$e \in E_x$
are on a common circle in the complex plane for each
$x \in V(G)$
. Since
${\mathcal L}_{\widehat v}f_v=\lambda (v)f_v$
, it holds that for all
$x \in V(G)$
and for all
$e \in E_x$
,
\begin{equation} \lambda (v) f_v(x)=e^{2\pi i \langle v, {\Phi }_e \rangle }f_v(te). \end{equation}
If
$\mu (\textrm {id})\gt 0$
, then for each
$v_k \in \Lambda$
there exists an edge path from
$\textrm {id}$
to
$v_k$
in
$\textrm {Cay}(\Gamma , S)$
of length with a given (in particular, even) parity. Applying to (3.14) along the image of the path in
$G$
successively yields
$\langle v, v_k \rangle \in {\mathbb Z}$
. This holds for a basis
$v_1, \ldots , v_k$
of
$\Lambda$
, implying that
$v \in \Lambda ^\ast$
. Therefore if
$v \in D$
, then
$v=0$
.
We have shown that
$|\lambda (v)|\lt 1$
for all
$v \in D\setminus \{0\}$
, and in this finite dimensional setting,
$v \mapsto \|{\mathcal L}_{\widehat v}\|=|\lambda (v)|$
is continuous. Thus for a small enough
$\delta \gt 0$
, there exists a constant
$c_\delta \gt 0$
such that
$|\lambda (v)| \le e^{-c_{\delta }}$
on a compact set
$D \setminus D_\delta$
. Since
\begin{equation*} |{\mathcal L}_{\widehat v}^n{\bf 1}(x_0)| \sqrt {\pi (x_0)} \le \|{\mathcal L}_{\widehat v}^n{\bf 1}\|_\pi \le |\lambda (v)|^{n} \|{\bf 1}\|_\pi , \end{equation*}
$\|{\bf 1}\|_\pi =1$
and
$\pi (x_0)=1/|V(G)|$
, by (3.12), we conclude the claim.
For an associated
$\Gamma$
-equivariant embedding
${\Phi }:\Gamma \to {\mathbb R}^m$
,
$x \mapsto x.o$
and a non-degenerate positive definite matrix
$\Sigma$
, let
\begin{equation*} \xi _{{\Sigma }}(x)\,:\!=\,\frac {1}{(2\pi )^{\frac {m}{2}}\sqrt {\det {\Sigma }}}e^{-\frac {1}{2}\langle {\Phi }(x), {\Sigma }^{-1}({\Phi }(x)) \rangle } \quad \text{for $x \in \Gamma $}. \end{equation*}
Theorem 3.6 (Local central limit theorem). Let
$\Gamma$
be a virtually finite rank free abelian group acting on
${\mathbb R}^m$
isometrically with a relatively compact fundamental domain which contains the origin in the interior. Let
$\mu$
be a probability measure on
$\Gamma$
such that the support
$\textrm {supp}\, \mu$
is finite,
$\Gamma =\langle \textrm {supp}\, \mu \rangle$
and
$\mu$
is symmetric. If
$\mu (\textrm {id})\gt 0$
, then the following holds: There exist a non-degenerate positive definite matrix
$\Sigma$
and a constant
$C\gt 0$
such that
\begin{equation*} \sup _{x \in \Gamma }|\mu _n(x)-\xi _{n{\Sigma }}(x)|\le \frac {C}{n^{\frac {m+1}{2}}} \quad \text{ for all $n \in {\mathbb Z}_{\gt 0}$}. \end{equation*}
Moreover, the matrix
$\Sigma$
is obtained by
\begin{equation} \langle v_1, {\Sigma } v_2 \rangle =\sum _{e \in E(G)}u_1(e)u_2(e)c(e), \end{equation}
where
$u_i$
is the harmonic part of
$\widehat v_i$
for
$v_i \in {\mathbb R}^m$
for
$i=1, 2$
.
Proof.
For all
$\delta \gt 0$
, the Fourier inversion formula (3.13) and the change of variables
$v \mapsto v/\sqrt {n}$
yield the following: For
$n \in {\mathbb Z}_{\gt 0}$
and for
$x\in \Gamma$
,
\begin{align*} \mu _n(x)&=\int _{D_{\delta }}{\varphi }_{\mu _n}\left (v\right )e^{-2\pi i \langle v, {\Phi }(x) \rangle }\,dv+\int _{D\setminus D_\delta } {\varphi }_{\mu _n}(v)e^{-2\pi i \langle v, {\Phi }(x) \rangle }\,dv\\ &=\frac {1}{n^{\frac {m}{2}}}\int _{D_{\delta \sqrt {n}}}{\varphi }_{\mu _n}\left (\frac {v}{\sqrt {n}}\right )e^{-2\pi i \langle v, {\Phi }(x) \rangle /\sqrt {n}}\,dv+\int _{D\setminus D_\delta } {\varphi }_{\mu _n}(v)e^{-2\pi i \langle v, {\Phi }(x) \rangle }\,dv. \end{align*}
Since
$\mu (\textrm {id})\gt 0$
, Lemma3.5 shows that for all small enough
$\delta \gt 0$
, there exists a constant
$c_\delta \gt 0$
such that for all
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{equation*} \sup _{v \in D\setminus D_\delta }|{\varphi }_{\mu _n}(v)|=O\left (e^{-c_\delta n}\right ). \end{equation*}
We will analyse the first integral in the last displayed equation. For
$v\in {\mathbb R}^m$
, let
$\widehat v=u+d{\varphi }$
and
$u$
be the harmonic
$H^1$
-part of
$\widehat v$
for some
${\varphi }\in C^0(G, {\mathbb R})$
. There exists a constant
$C$
such that such
$\varphi$
can be chosen to satisfy
$\|{\varphi }\|_\infty \le C\|v\|$
. Indeed, letting
$v=\sum _{i=1}^m \alpha _i v_i$
for the standard basis
$v_1, \ldots , v_m$
, and
$\alpha _1, \ldots , \alpha _m \in {\mathbb R}$
, we choose
${\varphi }_i$
such that
$\widehat v_i=u_i+d{\varphi }_i$
, and define
${\varphi }\,:\!=\,\sum _{i=1}^m \alpha _i {\varphi }_i$
. This yields the inequality with
$C=\sqrt {m}\max _{i=1, \ldots , m}\|{\varphi }_i\|_\infty$
.
We have
${\mathcal L}_{\widehat v}=e^{-2\pi i{\varphi }}{\mathcal L}_u e^{2\pi i{\varphi }}$
. By (3.12), up to replacing
$c_\delta$
by a smaller positive value,
\begin{equation*} {\varphi }_{\mu _n}(v)=e^{n\beta (v)}\left (\langle e^{2\pi {\varphi }}{\bf 1}, f_{u} \rangle _\pi e^{-2\pi i{\varphi }(x_0)}f_{u}(x_0)+O(e^{-c_\delta n})\right ) \quad \text{for $v \in D_\delta $}, \end{equation*}
where
$f_u$
is the normalised eigenvector of
${\mathcal L}_u$
of eigenvalue
$e^{\beta (v)}$
. By Lemma3.3, the Hessian of
$\beta$
at
$0$
on
${\mathbb R}^m$
is obtained by
$\textrm {Hess}_0\beta =-4\pi ^2{\Sigma }$
. Lemma3.2 implies that by the Taylor theorem,
\begin{equation*} \beta (v)=-2\pi ^2\langle v, {\Sigma } v \rangle +O(\|v\|^4) \quad \text{for $v \in D_\delta $}. \end{equation*}
Therefore, for all
$n \in {\mathbb Z}_{\gt 0}$
and for all
$v \in D_{\delta \sqrt {n}}$
,
\begin{equation*} \beta \left (\frac {v}{\sqrt {n}}\right )=-\frac {2\pi ^2}{n}\langle v, {\Sigma } v \rangle +O\left (\frac {\|v\|^4}{n^2}\right ). \end{equation*}
Replacing by
$\delta$
a smaller positive constant if necessary, we have that for all
$v \in D_{\delta \sqrt {n}}$
,
\begin{equation*} e^{n\beta \left (\frac {v}{\sqrt {n}}\right )}\le \left (1-\frac {\pi ^2}{n}\langle v, {\Sigma } v \rangle \right )^n \le e^{-\pi ^2 \langle v, {\Sigma } v \rangle }. \end{equation*}
Since
$|{\varphi }_{\mu _n}(v/\sqrt {n})| \le C_\delta e^{-\pi ^2\langle v, {\Sigma } v \rangle }$
for all
$v \in D_{\delta \sqrt {n}}$
, for all large enough
$n$
,
\begin{align*} &\frac {1}{n^{\frac {m}{2}}}\int _{D_{\delta \sqrt {n}}\setminus D_{n^{1/8}}}\Big |{\varphi }_{\mu _n}\left (\frac {v}{\sqrt {n}}\right )e^{-2\pi i \langle v, {\Phi }(x) \rangle /\sqrt {n}}\Big |\,dv \le \frac {C_\delta }{n^{\frac {m}{2}}}\int _{D_{\delta \sqrt {n}}\setminus D_{n^{1/8}}}e^{-\pi ^2 \langle v, {\Sigma } v \rangle }\,dv\\ &\le \frac {C_\delta '}{n^{\frac {m}{2}}}\int _{c_0 n^{1/8}}^{c_1\delta \sqrt {n}}e^{-c r^2}r^{m-1}\,dr \le \frac {C_\delta '}{n^{\frac {m}{2}}}\int _{c_0 n^{1/8}}^{c_1\delta \sqrt {n}}r e^{-\alpha r^2}\,dr =O\left (\frac {1}{n^{\frac {m}{2}}}e^{-\alpha c_0^2n^{1/4}}\right )\ll \frac {1}{n^{\frac {m+1}{2}}}. \end{align*}
In the above,
$C_\delta , C_\delta ', c, c_0, c_1$
, and
$\alpha$
(where
$c\gt \alpha$
) are positive constants; we have used the polar coordinate and the positive definiteness of
$\Sigma$
in the second inequality, and that
$e^{-c r^2}r^{m-1} \le e^{-\alpha r^2}r$
for all large
$r$
in the third inequality.
Furthermore, for all
$n \in {\mathbb Z}_{\gt 0}$
and for all
$v \in D_{n^{1/8}}$
, since
$\|v\|^4/n \ll 1/\sqrt {n}$
,
\begin{equation*} {\varphi }_{\mu _n}\left (\frac {v}{\sqrt {n}}\right )=e^{-2\pi ^2\langle v, {\Sigma } v \rangle }(1+R_n(v)) \left (\left\langle e^{2\pi i{\varphi }/\sqrt {n}}{\bf 1}, f_{u/\sqrt {n}} \right\rangle _\pi e^{-2\pi i{\varphi }(x_0)/\sqrt {n}} f_{u/\sqrt {n}}(x_0)+O(e^{-c_\delta n})\right ), \end{equation*}
where
$R_n(v)=O\left (\|v\|^4/n\right )$
. For the normalised eigenvector
$f_{u}$
of
$e^{\beta (v)}$
for
$u$
near
$0$
, since
$f_0={\bf 1}$
, by Lemma3.2 (3.3) the Taylor theorem shows the following: for each
$x \in V(G)$
,
\begin{equation*} f_{u/\sqrt {n}}(x)=1+O\left (\frac {\|u\|^2}{n}\right ). \end{equation*}
Furthermore, since
$\|u\|\le \|v\|$
and
$\|{\varphi }\|_\infty \le C\|v\|$
, for
$v \in D_{\delta \sqrt {n}}$
,
\begin{align*} \left\langle e^{2\pi i {\varphi }/\sqrt {n}}{\bf 1}, f_{u/\sqrt {n}} \right\rangle _\pi e^{-2\pi i{\varphi }(x_0)/\sqrt {n}}f_{u/\sqrt {n}}(x_0) &= \left (1+O\left (\frac {\|{\varphi }\|_\infty }{\sqrt {n}}\right )\right )\left (1+O\left (\frac {\|v\|^2}{n}\right )\right )\\ &=1+O\left (\frac {\|v\|}{\sqrt {n}}\right ). \end{align*}
Note that the change of variable
$v\mapsto v/\sqrt {n}$
yields
$u\mapsto u/\sqrt {n}$
and
${\varphi }\mapsto {\varphi }/\sqrt {n}$
. For each
$k\ge 0$
,
\begin{equation*} \int _{D_{n^{1/8}}}e^{-2\pi ^2\langle v, {\Sigma } v \rangle } \frac {\|v\|^k}{\sqrt {n}}\,dv\le \frac {1}{\sqrt {n}}\int _{{\mathbb R}^m}\|v\|^k e^{-2\pi ^2\langle v, {\Sigma } v \rangle }\,dv=O\left (\frac {1}{\sqrt {n}}\right ). \end{equation*}
Summarising the above estimates with
$e^{-c_\delta n}\ll n^{-\frac {m+1}{2}}$
yields for
$x\in \Gamma$
and for
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{align} \mu _n(x)&=\frac {1}{n^{\frac {m}{2}}}\int _{D_{n^{1/8}}}e^{-2\pi ^2\langle v, {\Sigma } v \rangle } e^{-2\pi i \langle v, {\Phi }(x) \rangle /\sqrt {n}}\,dv+O\left (\frac {1}{n^{\frac {m+1}{2}}}\right ). \end{align}
A direct computation on the Fourier transform yields for all
$n \in {\mathbb Z}_{\gt 0}$
and for all
$x \in \Gamma$
,
\begin{equation*} \xi _{n{\Sigma }}(x)=\frac {1}{n^{\frac {m}{2}}}\int _{{\mathbb R}^m}e^{-2\pi i \langle v, {\Phi }(x) \rangle /\sqrt {n}}e^{-2\pi ^2 \langle v, {\Sigma } v \rangle }\,dv. \end{equation*}
Abusing notations, we have a constant
$\alpha \gt 0$
such that for all
$n \in {\mathbb Z}_{\gt 0}$
and uniformly in
$x \in \Gamma$
,
\begin{equation} \xi _{n{\Sigma }}(x)=\frac {1}{n^{\frac {m}{2}}}\int _{D_{n^{1/8}}}e^{-2\pi i \langle v, {\Phi }(x) \rangle /\sqrt {n}}e^{-2\pi ^2 \langle v, {\Sigma } v \rangle }\,dv+O\left (\frac {1}{n^{\frac {m}{2}}}e^{-\alpha n^{1/4}}\right ). \end{equation}
Therefore by (3.16) and (3.17), for all
$n \in {\mathbb Z}_{\gt 0}$
and uniformly in
$x \in \Gamma$
,
\begin{equation*} \mu _n(x)=\xi _{n{\Sigma }}(x)+O\left (\frac {1}{n^{\frac {m+1}{2}}}\right ). \end{equation*}
Furthermore, the explicit form of
$\Sigma$
is obtained by Lemma3.3, as claimed.
Lemma 3.7.
Let
$\mu$
be a probability measure on
$\Gamma$
such that
$\textrm {supp}\, \mu$
is finite and
$\Gamma =\langle \textrm {supp}\, \mu \rangle$
, and
$\{w_n\}_{n\in {\mathbb Z}_+}$
be a
$\mu$
-random walk with
$w_0=\textrm {id}$
. There exists a constant
$C\gt 0$
such that for all
$n \in {\mathbb Z}_{\gt 0}$
and for all real
$r \gt 0$
,
\begin{equation*} {\mathbb P}\big (|w_n|_S \ge r\big )\le C\exp \left({-}\frac {r^2}{C n}\right). \end{equation*}
Proof. The proof follows from the Gaussian estimates established in a more general setting ([Reference Hebisch and Saloff-Coste3, the proof of Theorem 9.1] and [Reference Woess12, Chapter 14]). We provide an alternative proof adapted to this setting for the sake of completeness.
Note that if
$\{{\Phi }(w_n)\}_{n \in {\mathbb Z}_+}$
is a martingale with respect to the filtration associated with
$\{w_n\}_{n \in {\mathbb Z}_+}$
, then the proof follows from a concentration inequality. In general,
$\{{\Phi }(w_n)\}_{n \in {\mathbb Z}_+}$
is not a martingale. What we do below is to replace
$\Phi$
by another
$\Lambda$
-equivariant map which makes the images of
$w_n$
form a martingale.
First we claim that there exists a
$\Lambda$
-equivariant harmonic map
${\Phi }_H: \Gamma \to {\mathbb R}^m$
. This is a map satisfying the following:
${\Phi }_H(gx)={\Phi }_H(x)+g$
for all
$x \in \Gamma$
and for all
$g \in \Lambda$
under the identification between
$\Lambda$
and a lattice in
${\mathbb R}^m$
, and
\begin{equation*} \sum _{s \in \textrm {supp}\, \mu }\left ({\Phi }_H(xs)-{\Phi }_H(x)\right )\mu (s)=0 \quad \text{for each $x \in \Gamma $}. \end{equation*}
This map is obtained from a
$\Lambda$
-equivariant lift of a Dirichlet energy minimising map from
$G=(V(G), E(G))$
with weights on edges
$c(e)$
for
$e \in E(G)$
into the flat torus
${\mathbb R}^m/\Lambda$
equipped with metric as a quotient of the standard Euclidean space. The existence of such a map is shown by a simple variational calculus [Reference Kotani and Sunada6, Theorem 2.3] (see also [Reference Sunada10, Chapter 7]). (In general,
${\Phi }_H$
is not necessarily injective, but this does not affect the following discussion.) For a
$\Lambda$
-equivariant harmonic map
${\Phi }_H$
, we have a martingale
$\{{\Phi }_H(w_n)\}_{n \in {\mathbb Z}_+}$
with respect to the natural filtration.
Next note that the map
${\Phi }_H$
yields a quasi-isometry between
$\textrm {Cay}(\Gamma , S)$
and
${\mathbb R}^m$
. In particular, there exist constants
$c_0, c_1\gt 0$
such that
\begin{equation} \|{\Phi }_H(x)\|_\infty \ge c_0|x|_S-c_1 \quad \text{for all $x \in \Gamma $}. \end{equation}
In the above,
$\|\cdot \|_\infty$
denotes the
$\ell _\infty$
-norm in
${\mathbb R}^m$
.
Finally, each component of
${\Phi }_H(w_n)$
in the coordinate of
${\mathbb R}^m$
is a martingale with a uniformly bounded difference
$B$
for some
$B\gt 0$
. Hence a union bound and the Azuma-Hoeffding inequality show that by (3.18), for all
$r \in {\mathbb Z}_+$
and for all
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{equation*} {\mathbb P}\left (|w_n|_S \ge (r+c_1)/c_0\right ) \le {\mathbb P}\left (\|{\Phi }_H(w_n)\|_\infty \ge r\right ) \le 2m\exp \left({-}\frac {r^2}{2B^2 n}\right). \end{equation*}
Therefore, taking a large enough constant
$C\gt 0$
concludes the inequality as claimed.
For the
$\xi _{{\Sigma }}$
in Theorem 3.6, let us define a discrete normal distribution
${\mathcal N}^{\Phi }_{\Sigma }$
on
$\Gamma$
by
\begin{equation*} {\mathcal N}^{\Phi }_{\Sigma }(x)\,:\!=\,\frac {1}{Z}\xi _{\Sigma }(x) \quad \text{where $Z\,:\!=\,\sum _{x \in \Gamma }\xi _{\Sigma }(x)$ for $x \in \Gamma $}. \end{equation*}
Theorem 3.8.
In the same setting and assumption as in Theorem 3.6
, there exists a constant
$C\gt 0$
such that for all integers
$n\gt 1$
,
\begin{equation*} \|\mu _n-{\mathcal N}^{\Phi }_{n{\Sigma }}\|_{\textrm {TV}} \le \frac {C(\log n)^{\frac {m}{2}}}{\sqrt {n}}. \end{equation*}
Proof.
The local central limit theorem (Theorem 3.6) implies that there exists a constant
$C\gt 0$
such that for all
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{equation} \sup _{x \in \Gamma }|\mu _n(x)-\xi _{n{\Sigma }}(x)|\le \frac {C}{n^{\frac {m+1}{2}}}. \end{equation}
For a
$\mu$
-random walk
$\{w_n\}_{n \in {\mathbb Z}_+}$
with
$w_0=\textrm {id}$
on
$\Gamma$
, Lemma3.7, there exists a constant
$C\gt 0$
such that for all
$n \in {\mathbb Z}_{\gt 0}$
and for all
$r\gt 0$
,
\begin{equation} {\mathbb P}\big (|w_n|_S \ge r\big ) \le C\exp \left({-}\frac {r^2}{C n}\right). \end{equation}
A direct computation on
$\xi _{n{\Sigma }}$
yields for a (possibly different) constant
$C\gt 0$
, for all
$n\gt 0$
and for all
$r\gt C\sqrt {n}$
,
\begin{equation} \sum _{|x|_S \ge r}\xi _{n{\Sigma }}(x) \le C\exp \left({-}\frac {r^2}{C n}\right). \end{equation}
Indeed, this follows from an approximation by a Gaussian
$f_{{\Sigma }}$
on
${\mathbb R}^m$
for which
$\xi _{{\Sigma }}=f_{\Sigma }\circ {\Phi }$
, and that
$\Phi$
yields a quasi-isometry between
$\textrm {Cay}(\Gamma , S)$
and
${\mathbb R}^m$
. Note that
${\mathbb R}^m=\bigcup _{x \in \Gamma }x\overline C_0$
for the closure
$\overline C_0$
of a relatively compact fundamental domain
$C_0$
of
$\Gamma$
. For
$v_i \in {\mathbb R}^m$
,
$i=1, 2$
, the following holds:
\begin{align*} |\langle v_1, {\Sigma }^{-1}v_1 \rangle -\langle v_2, {\Sigma }^{-1}v_2 \rangle | &= \left |\int _0^1 \frac {d}{dt}\langle v_1+t(v_2-v_1), {\Sigma }^{-1}(v_1+t(v_2-v_1)) \rangle \,dt\right | \\ &\le 2\int _0^1 |\langle v_2-v_1, {\Sigma }^{-1}(v_1+t(v_2-v_1)) \rangle |\,dt \\ &\le 2\|{\Sigma }^{-1}\|\|v_1-v_2\|\max \{\|v_1\|, \|v_2\|\}. \end{align*}
Letting
$\textrm {diam } C_0$
denote the diameter of
$\overline C_0$
, we have that by the above inequality, if
$v_i \in x\overline C_0$
and
$\|v_i\| \ge \textrm {diam } C_0$
,
$i=1, 2$
, then
$\|v_1-v_2\| \le \|v_2\|$
and
\begin{equation*} |\langle v_1, {\Sigma }^{-1}v_1 \rangle -\langle v_2, {\Sigma }^{-1}v_2 \rangle |\le 2\|{\Sigma }^{-1}\|\|v_1-v_2\|(\|v_2\|+\|v_1-v_2\|) \le 4\|{\Sigma }^{-1}\|\textrm {diam } C_0 \|v_2\|. \end{equation*}
Thus, for all
$v_i \in x \overline C_0$
,
$i=1, 2$
,
\begin{equation*} f_{n{\Sigma }}(v_1) \le f_{n{\Sigma }}(v_2)e^{\frac {c}{n}\|v_2\|}, \quad \text{where $c\,:\!=\,2\|{\Sigma }^{-1}\|\textrm {diam } C_0$}. \end{equation*}
Since
${\Sigma }^{-1}$
is positive definite, there exists a constant
$\alpha \gt 0$
such that
$\langle v, {\Sigma }^{-1}v \rangle \ge \alpha \|v\|^2$
for
$v \in {\mathbb R}^m$
. Therefore, noting that
$\|{\Phi }(x)\| \ge c_0|x|_S-c_1$
for all
$x \in \Gamma$
, we estimate
\begin{equation*} \sum _{|x|_S \ge r} \xi _{n{\Sigma }}(x) \le \frac {1}{\textrm {vol}(C_0)}\int _{\|v\| \ge c_0 r-c_1}\frac {1}{(2\pi n)^{\frac {m}{2}}\sqrt {\det {\Sigma }}}e^{-\frac {\alpha }{2n}\|v\|^2+\frac {c}{n}\|v\|}\,dv, \end{equation*}
for
$r \ge (\textrm {diam } C_0+c_1)/c_0$
, where
$\textrm {vol}(C_0)$
is the volume of
$C_0$
. By the change of variables
$v \mapsto \sqrt {n}v$
, the right hand side equals the following:
\begin{align*} &\frac {1}{\textrm {vol}(C_0)}\int _{\|v\| \ge (c_0 r-c_1)/\sqrt {n}}\frac {1}{(2\pi )^{\frac {m}{2}}\sqrt {\det {\Sigma }}}e^{-\frac {\alpha }{2}\|v\|^2+\frac {c}{\sqrt {n}}\|v\|}\,dv\\ &\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad =c_{m, {\Sigma }}\int _{(c_0 r-c_1)/\sqrt {n}}^\infty e^{-\frac {\alpha }{2}s^2+\frac {c}{\sqrt {n}}s}s^{m-1}\,ds, \end{align*}
where
$c_{m, {\Sigma }}$
is a constant depending only on
$\Sigma$
and
$m$
in the polar coordinate. Thus,
\begin{align*} \int _{(c_0 r-c_1)/\sqrt {n}}^\infty e^{-\frac {\alpha }{2}\left (s-\frac {c}{\alpha \sqrt {n}}\right )^2+\frac {c^2}{2\alpha n}}s^{m-1}\,ds =e^{\frac {c^2}{2\alpha n}}\int _{R}^\infty e^{-\frac {\alpha }{2}s^2}\left (s+\frac {c}{\alpha \sqrt {n}}\right )^{m-1}\,ds, \end{align*}
where
$R\,:\!=\,(c_0 r-c_1)/\sqrt {n}-c/(\alpha \sqrt {n})$
by change of variables. There exists a constant
$C\gt 0$
such that
$\left (s+c/(\alpha \sqrt {n})\right )^{m-1}\le s e^{\frac {\alpha }{4}s^2}$
for all
$s\gt C$
. Hence, there exists a constant
$C\gt 0$
such that for all
$n\gt 0$
and
$r\gt C\sqrt {n}$
, the last term is at most
\begin{equation*} e^{\frac {c^2}{2\alpha n}}\int _{R}^\infty se^{-\frac {\alpha }{4}s^2}\,ds =e^{\frac {c^2}{2\alpha n}}\frac {2}{\alpha }e^{-\frac {\alpha }{4}R^2} \le C e^{-\frac {r^2}{C n}}. \end{equation*}
This shows (3.21).
Combining (3.19), (3.20), and (3.21) yields for all
$n\gt 0$
and for all
$r\gt C\sqrt {n}$
,
\begin{align*} \|\mu _n-\xi _{n{\Sigma }}\|_1 &=\sum _{|x|_S \le r}|\mu _n(x)-\xi _{n{\Sigma }}(x)|+\sum _{|x|_S \gt r}|\mu _n(x)-\xi _{n{\Sigma }}(x)|\\ &\le |B_{S}(r)|\frac {C}{n^{\frac {m+1}{2}}}+2C\exp \left({-}\frac {r^2}{C n}\right). \end{align*}
In the above
$B_S(r)\,:\!=\,\{x \in \Gamma \ : \ |x|_S \le r\}$
. Note that
$|B_S(r)|=\Theta (r^m)$
, in particular,
$|B_S(r)|\le C r^m$
for all
$r \in {\mathbb Z}_+$
for a constant
$C\gt 0$
independent of
$r$
since
$\Phi$
is a
$\Lambda$
-equivariant injective map from
$\Gamma$
into
${\mathbb R}^m$
. Letting
$r=A\sqrt {n \log n}$
for a constant
$A\gt 0$
, we have
$r\gt C\sqrt {n}$
for all
$n \in {\mathbb Z}_{\gt 0}$
, and
\begin{equation*} \|\mu _n-\xi _{n{\Sigma }}\|_1 \le \frac {C^2 A^m(\log n)^{\frac {m}{2}}}{\sqrt {n}}+\frac {2C}{n^{A^2/C}}. \end{equation*}
Fixing a large enough constant
$A$
such that
$A^2/C\gt 1/2$
shows that there exists a constant
$C_1$
such that for all
$n\gt 1$
,
\begin{equation} \|\mu _n-\xi _{n{\Sigma }}\|_1 \le \frac {C_1(\log n)^{\frac {m}{2}}}{\sqrt {n}}. \end{equation}
Note that there exists a constant
$c\gt 0$
such that for all
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{equation} \sum _{x \in \Gamma }\xi _{n{\Sigma }}(x)=1+\sum _{x \in \Gamma \setminus \{\textrm {id}\}}\xi _{n{\Sigma }}(x)=1+O(e^{-cn}). \end{equation}
Indeed, since
${\mathbb Z}^m$
is a finite index subgroup of
$\Gamma$
and
$\Phi$
is a
${\mathbb Z}^m$
-equivariant embedding with a discrete image in
${\mathbb R}^m$
, the Poisson summation formula (cf. (A.1) in Appendix A) on finitely many orbits of
${\mathbb Z}^m$
shows (3.23). This implies that for all
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{equation*} \|\xi _{n{\Sigma }}-{\mathcal N}^{\Phi }_{n{\Sigma }}\|_1 =\sum _{x \in \Gamma }\Big |\xi _{n{\Sigma }}(x)-\frac {1}{\sum _{z \in \Gamma }\xi _{n{\Sigma }}(z)}\xi _{n{\Sigma }}(x)\Big |=O(e^{-c n}). \end{equation*}
Therefore, this together with (3.22), adjusting a constant factor
$C$
yields the claim.
Remark 3.9. The inequality (3.22) suffices for our purpose in
Theorem 4.1
below. If
$\Phi$
is
$\mu$
-harmonic, then the estimate in
Theorem 3.8
becomes
$O((\log n)^{\frac {m}{2}}/n)$
. In this case, the estimate is sharp up the factor
$O((\log n)^{m/2})$
. Indeed, the local central limit theorem provides an example satisfying that
$\|\mu _n-{\mathcal N}^{\Phi }_{n{\Sigma }}\|_{\textrm {TV}}=\Omega (1/n)$
, for example, a lazy simple random walk on
${\mathbb Z}^m$
.
4. Applications to noise sensitivity problem
4.1 Noise sensitivity on affine Weyl groups
Let
$(\Gamma , S)$
be an affine Weyl group where
$S$
is a canonical set of generators consisting of involutions. We have
$\Gamma =\Lambda \rtimes W$
as in Section 2.1. For a probability measure
$\mu$
on
$\Gamma$
and for all
$\rho \in [0, 1]$
, we recall that
$\pi ^\rho =\rho (\mu \times \mu )+(1-\rho )\mu _{\textrm {diag}}$
, where
$\mu \times \mu$
denote the product measure and
$\mu _{\textrm {diag}}((x, y))=\mu (x)$
if
$x=y$
and
$0$
otherwise.
For each
$\rho \in [0, 1]$
, the measure
$\pi ^\rho$
is defined on
$\Gamma \times \Gamma =(\Lambda \times \Lambda )\rtimes (W\times W)$
, for which
$S_\ast \,:\!=\,(S\cup \{\textrm {id}\})^2$
is a generating set of order at most
$2$
. On the one hand, if
$\textrm {supp}\, \mu =S\cup \{\textrm {id}\}$
, then
$\textrm {supp}\, \pi ^\rho =S_\ast$
for all
$\rho \in (0, 1]$
. On the other hand, however, if
$\rho =0$
or
$\textrm {supp}\, \mu =S$
(in which case, the support of
$\mu$
does not contain
$\textrm { id}$
), then
$\textrm {supp}\, \pi ^\rho$
never generate
$\Gamma \times \Gamma$
. Indeed, every affine Weyl group
$\Gamma$
admits a surjective homomorphism onto
$\{\pm 1\}$
through the determinant of the isometry part in the natural affine representation. The product group
$\Gamma \times \Gamma$
admits a surjective homomorphism onto
$\{\pm 1\}^2$
. If
$\textrm {supp}\, \mu$
does not contain
$\textrm {id}$
, then
$\textrm {supp}\, \pi ^\rho$
for
$\rho \in (0, 1]$
only generates a proper subgroup of
$\Gamma \times \Gamma$
(of index
$2$
). Furthermore, if
$\rho =0$
, then
$\textrm {supp}\, \pi ^\rho$
generates the diagonal subgroup isomorphic to
$\Gamma$
in
$\Gamma \times \Gamma$
.
Theorem 4.1.
Let
$(\Gamma , S)$
be an affine Weyl group, and
$\mu$
be a probability measure on
$\Gamma$
such that the support of
$\mu$
equals
$S\cup \{\textrm {id}\}$
. For all
$\rho \in (0, 1]$
, the
$\pi ^\rho$
-random walk on
$\Gamma \times \Gamma$
starting from the identity satisfies the following: There exist a constant
$C\gt 0$
and an integer
$m\gt 0$
such that for all integers
$n\gt 1$
,
\begin{equation*} \|\pi ^\rho _n-\mu _n\times \mu _n\|_{\textrm {TV}} \le \frac {C(\log n)^m}{\sqrt {n}}. \end{equation*}
In particular, for all
$\rho \in (0, 1]$
,
\begin{equation*} \lim _{n \to \infty }\|\pi ^\rho _n-\mu _n\times \mu _n\|_{\textrm {TV}}=0, \end{equation*}
that is, the
$\mu$
-random walk on
$\Gamma$
is noise sensitive in total variation.
Proof.
Let us apply to
$\Gamma \times \Gamma$
and
$\pi ^\rho$
the discussion we have made so far. Fix a point
$o$
in the interior of a chamber for
$\Gamma$
in the associated Euclidean space
${\mathbb R}^m$
. We assume that
$o$
is the origin after taking a conjugate by a translation for the action of
$\Gamma$
if necessary. Let
${\Phi }\,:\!=\,{\Phi }^{(1)}\times {\Phi }^{(2)}: \Gamma \times \Gamma \to {\mathbb R}^m \times {\mathbb R}^m$
,
$(x_1, x_2)\mapsto (x_1.o, x_2.o)$
, where
${\Phi }^{(i)}(x)=x.o$
for
$x \in \Gamma$
and for
$i=1, 2$
. For all
$\rho \in (0, 1]$
, the support of
$\pi ^\rho$
is finite,
$\Gamma \times \Gamma =\langle \textrm {supp}\, \pi ^\rho \rangle$
, and
$\pi ^\rho$
is symmetric since every element in
$\textrm {supp}\, \pi ^\rho =S_\ast =(S\cup \{\textrm {id}\})^2$
has the order at most
$2$
. Further let
$G\,:\!=\,(\Lambda \times \Lambda )\backslash \textrm {Cay}(\Gamma \times \Gamma , S_\ast )$
equipped with the conductance
$c({\boldsymbol e})$
for
${\boldsymbol e} \in E(G)$
induced from
$\pi ^\rho$
. We consider the corresponding pointed finite network
$(G, c, x_0)$
where
$x_0$
is the identity element in
$W\times W=(\Lambda \times \Lambda ) \backslash (\Gamma \times \Gamma )$
. For all
$\rho \in (0, 1]$
, the corresponding Markov chain on
$G$
is irreducible and satisfies that
$p(x, x)\gt 0$
for every
$x \in V(G)$
since
$\pi ^\rho (\textrm {id})\gt 0$
.
Let
${\Sigma }^\rho$
be the matrix for
$\pi ^\rho$
in the local central limit theorem (Theorem 3.6), let us show that
${\Sigma }^\rho ={\Sigma }^1$
for all
$\rho \in (0, 1]$
. Namely, in the block diagonal form along the decomposition
${\mathbb R}^m\times {\mathbb R}^m$
, we prove the following: For all
$\rho \in (0, 1]$
,
\begin{equation*} {\Sigma }^\rho = \begin{pmatrix} {\Sigma }^\mu & 0\\ 0 & {\Sigma }^\mu \end{pmatrix}, \end{equation*}
where
${\Sigma }^\mu$
is the matrix
${\Sigma }^\mu$
for
$\mu$
in the local central limit theorem. Theorem 3.6 shows that
${\Sigma }^\rho$
is obtained by
\begin{equation} \langle {\boldsymbol v}_1, {\Sigma }^\rho {\boldsymbol v}_2 \rangle =\sum _{{\boldsymbol e} \in E(G)}{\boldsymbol u}_1({\boldsymbol e}){\boldsymbol u}_2({\boldsymbol e})c({\boldsymbol e}), \end{equation}
for
${\boldsymbol v}_1, {\boldsymbol v}_2 \in {\mathbb R}^m\times {\mathbb R}^m$
and
${\boldsymbol u}_i$
is the harmonic part of the
$1$
-form
$\widehat {\boldsymbol v}_i=(\langle {\boldsymbol v}_i, {\Phi }_{\boldsymbol e} \rangle )_{{\boldsymbol e} \in E(G)}$
for
$i=1, 2$
.
First let us show that
$\langle {\boldsymbol v}_1, {\Sigma }^\rho {\boldsymbol v}_2 \rangle =0$
for all
${\boldsymbol v}_1=(v_1, 0), {\boldsymbol v}_2=(0, v_2) \in {\mathbb R}^m\times {\mathbb R}^m$
. For each edge
${\boldsymbol e}=((x_1, x_2), (x_1.s_1, x_2.s_2)) \in E(G)$
, we write
$e_i=(x_i, x_i.s_i)$
for
$x_i \in W$
and
$s_i \in S\cup \{\textrm {id}\}$
for
$i=1, 2$
. For such
${\boldsymbol v}_1, {\boldsymbol v}_2$
, we have that
\begin{equation} \widehat {\boldsymbol v}_i({\boldsymbol e})=\langle {\boldsymbol v}_i, {\Phi }_{\boldsymbol e} \rangle =\langle v_i, {\Phi }^{(i)}_{e_i} \rangle =\widehat v_i(e_i) \quad \text{for $i=1, 2$}. \end{equation}
Let
${\boldsymbol u}_i$
be the harmonic part of
$\widehat {\boldsymbol v}_i$
, and
$u_i$
be the harmonic part of
$\widehat v_i$
for each
$i=1, 2$
. It holds that
\begin{equation} {\boldsymbol u}_i({\boldsymbol e})=u_i(e_i) \quad \text{for $i=1, 2$}. \end{equation}
Indeed, let
$\widetilde u_i({\boldsymbol e})\,:\!=\,u_i(e_i)$
for
$i=1, 2$
. These define harmonic
$1$
-forms on
$G$
: This follows since
$S_\ast =(S\cup \{\textrm {id}\})^2$
and each marginal of
$\pi ^\rho$
is
$\mu$
. Furthermore by the definition of
$u_i$
, it holds that for some
$f_i:W \to {\mathbb R}$
,
\begin{equation} \widehat v_i(x, x.s)=u_i(x, x.s)+df_i(x, x.s) \quad \text{for $x \in W$ and $s \in S$}. \end{equation}
Hence by (4.2) and (4.4), letting
$\widetilde f_i: V(G) \to {\mathbb R}$
by
$\widetilde f_i((x_1, x_2))\,:\!=\,f_i(x_i)$
for
$(x_1, x_2)\in V(G)=W\times W$
for
$i=1, 2$
yields
\begin{equation*} \widehat {\boldsymbol v}_i({\boldsymbol e})=\widetilde u_i({\boldsymbol e})+d\widetilde f_i({\boldsymbol e}) \quad \text{for ${\boldsymbol e} \in E(G)$}. \end{equation*}
The uniqueness of harmonic part concludes (4.3).
The right hand side in (4.1) is computed as in the following: By (4.3), it holds that
\begin{align*} &\sum _{{\boldsymbol e} \in E(G)}{\boldsymbol u}_1({\boldsymbol e}){\boldsymbol u}_2({\boldsymbol e})c({\boldsymbol e}) =\sum _{{\boldsymbol e} \in E(G)}u_1(e_1)u_2(e_2)c({\boldsymbol e})\\ &=\sum _{(x_1, x_2)\in W\times W}\sum _{(s_1, s_2) \in S_\ast }u_1(x_1, x_1.s_1)u_2(x_2, x_2.s_2)\pi ((x_1, x_2))\pi ^\rho ((s_1, s_2)). \end{align*}
Note that the summation over
$(s_1, s_2) \in S_\ast$
is restricted to
$S \times S$
since
$u_i(x, x)=0$
for
$x \in W$
and for each
$i=1, 2$
. Furthermore
$\pi ((x, y))=1/|W|^2$
for all
$(x, y) \in W\times W$
. Hence the last term times the factor
$|W|^2$
leads the following:
\begin{align*} &\sum _{x_1 \in W, s_1 \in S}u_1(x_1, x_1.s_1)\sum _{x_2 \in W, s_2 \in S}u_2(x_2, x_2.s_2)\pi ^\rho ((s_1, s_2))\\ &=\sum _{x_1 \in W, s_1 \in S}u_1(x_1, x_1.s_1)\frac {1}{2}\sum _{x_2 \in W, s_2 \in S}(u_2(x_2, x_2.s_2)+u_2(x_2.s_2, x_2))\pi ^\rho ((s_1, s_2))=0. \end{align*}
In the above, we have used that
$s_2=s_2^{-1}$
and
$\pi ^\rho ((s_1, s_2))=\pi ^\rho ((s_1, s_2^{-1}))$
for each
$(s_1, s_2) \in S\times S$
in the first equality, and that
$u_2(x_2, x_2.s_2)=-u_2(x_2.s_2, x_2)$
for all
$x_2 \in W$
and all
$s_2 \in S$
in the last equality. Therefore, for all
${\boldsymbol v}_1=(v_1, 0), {\boldsymbol v}_2=(0, v_2) \in {\mathbb R}^m \times {\mathbb R}^m$
, it holds that
$\langle {\boldsymbol v}_1, {\Sigma }^\rho {\boldsymbol v}_2 \rangle =0$
.
Next since each marginal of
$\pi ^\rho$
is
$\mu$
, for
${\boldsymbol v}_1=(v_1, 0), {\boldsymbol v}_2=(v_2, 0) \in {\mathbb R}^m \times {\mathbb R}^m$
,
\begin{align*} \langle {\boldsymbol v}_1, {\Sigma }^\rho {\boldsymbol v}_2 \rangle =\langle v_1, {\Sigma }^\mu v_2 \rangle . \end{align*}
The same equality holds for
${\boldsymbol v}_1=(0, v_1), {\boldsymbol v}_2=(0, v_2) \in {\mathbb R}^m \times {\mathbb R}^m$
. Summarising all the above discussion, we obtain
${\Sigma }^\rho ={\Sigma }^1$
for all
$\rho \in (0, 1]$
.
Finally, Theorem 3.8 shows that for all
$\rho \in (0, 1]$
, there exists a constant
$C\gt 0$
such that for all
$n\gt 1$
, by the triangle inequality,
\begin{equation*} \|\pi ^\rho _n-\mu _n\times \mu _n\|_{\textrm {TV}} \le \|\pi ^\rho _n-{\mathcal N}^{\Phi }_{n{\Sigma }^\rho }\|_{\textrm {TV}}+\|\mu _n\times \mu _n-{\mathcal N}^{\Phi }_{n{\Sigma }^1}\|_{\textrm {TV}}\le \frac {2C(\log n)^m}{\sqrt {n}}. \end{equation*}
This concludes the first claim. The second claim follows from the first claim.
4.2 Examples
Let us provide explicit examples of random walks on the affine Weyl groups of type
$\widetilde A_1 \times \widetilde A_1$
,
$\widetilde A_2$
, and
$\widetilde C_2$
. Figures 1, 3, and 4, respectively, describe the Cayley graphs of the groups with the corresponding sets of generators (the solid lines with dots). The associated action of each group on
${\mathbb R}^2$
consists of reflections with respect to lines (indicated as dotted lines) with a fundamental domain (coloured in dark grey). The lattice has a larger fundamental domain (coloured in light grey).
4.2.1. Type
$\widetilde A_1\times \widetilde A_1$
Let us consider the infinite dihedral group:
\begin{equation*} D_\infty =\langle s_1, s_2 \mid s_1^2=s_2^2=\textrm {id} \rangle . \end{equation*}
Let
$S\,:\!=\,\{s_1, s_2\}$
. The pair
$(D_\infty , S)$
is the affine Weyl group of type
$\widetilde A_1$
, and the product group
$D_\infty \times D_\infty$
with the standard set of generators
$S\times \{\textrm {id}\}\cup \{\textrm { id}\}\times S$
is the affine Weyl group of type
$\widetilde A_1 \times \widetilde A_1$
. The group
$D_\infty \times D_\infty$
is isomorphic to
${\mathbb Z}^2 \rtimes ({\mathbb Z}/2)^2$
. We define
${\Phi }={\Phi }^{(1)}\times {\Phi }^{(2)}:D_\infty \times D_\infty \to {\mathbb R}^2$
in a way that the origin is the barycenter of a fundamental chamber (which is a square of side length
$1/2$
). The lattice is identified with the standard integer lattice (Figure 1).
The Cayley graph of
$D_\infty \times D_\infty$
with the set of generators
$S_\ast$
(where loops corresponding to
$\textrm {id}$
are omitted) and the group action on
${\mathbb R}^2$
.
Let
$\mu$
be a probability measure on
$D_\infty$
such that
$\textrm {supp}\, \mu =S\cup \{\textrm {id}\}$
, and
$\pi ^\rho$
be the associated probability measure on
$D_\infty \times D_\infty$
for
$\rho \in (0, 1]$
. The measure
$\pi ^\rho$
has the support
$S_\ast =(S\cup \{\textrm {id}\})^2$
. The quotient graph
$G={\mathbb Z}^2\setminus \textrm {Cay}(D_\infty \times D_\infty , S_\ast )$
is described in Figure 2.
The quotient graph
$G={\mathbb Z}^2\backslash \textrm {Cay}(D_\infty \times D_\infty , S_\ast )$
where
$S_\ast =(S\cup \{\textrm {id}\})^2$
and
$S=\{s_1, s_2\}$
.
First, we consider the case when
$\mu (s_1)$
and
$\mu (s_2)$
are equal, that is,
\begin{equation*} \mu (s_1)=\mu (s_2)=\frac {1}{2}(1-\mu (\textrm {id})) \quad \text{and} \quad 0\lt \mu (\textrm {id})\lt 1. \end{equation*}
In this case, for
$v_1=(1, 0), v_2=(0, 1) \in {\mathbb R}^2$
, the
$1$
-forms
$(\langle v_i, {\Phi }_{\boldsymbol e} \rangle )_{{\boldsymbol e} \in E(G)}$
for
$i=1,2$
are harmonic. A direct computation yields
\begin{equation*} {\Sigma }^\rho = \begin{pmatrix} \frac {1}{4}(1-\mu (\textrm {id})) & 0\\ 0 & \frac {1}{4}(1-\mu (\textrm {id})) \end{pmatrix} \quad \text{for $\rho \in (0, 1]$}. \end{equation*}
Next in the case when
$\mu (s_1)$
and
$\mu (s_2)$
are not necessarily equal, the harmonic
$1$
-forms
\begin{equation*} u_i({\boldsymbol e})=\langle v_i, {\Phi }_{\boldsymbol e} \rangle -df_i({\boldsymbol e}) \quad \text{for ${\boldsymbol e} \in E(G)$ and $i=1, 2$}, \end{equation*}
are obtained by (possibly non-constant) functions
$f_i:V(G) \to {\mathbb R}$
. For
$i=1$
, let
\begin{equation*} f_1((0, 0))=f_1((0, 1))=\frac {\mu (s_2)}{2(1-\mu (\textrm {id}))} \quad \text{and} \quad f_1((1, 0))=f_1((1, 1))=\frac {\mu (s_1)}{2(1-\mu (\textrm {id}))}. \end{equation*}
The values of the harmonic
$1$
-form
$u_1$
on the two oriented edges from
$(0,0)$
to
$(1, 0)$
satisfy the following:
\begin{align*} u_1((0,0), (0.s_1, 0))+f_1((1,0))-f_1((0,0))&={\Phi }^{(1)}((s_1.o, o))-{\Phi }^{(1)}((o,o))=\frac {1}{2},\\ u_1((0,0),(0.s_2, 0))+f_1((1,0))-f_1((0,0))&={\Phi }^{(1)}((s_2.o,o))-{\Phi }^{(1)}((o,o))=-\frac {1}{2}. \end{align*}
Similar identities hold on the four oriented edges from
$(0, 0)$
to
$(1, 1)$
, from
$(0, 1)$
to
$(1, 0)$
, respectively, and on the two oriented edges from
$(0, 1)$
to
$(1, 1)$
. The values of
$u_1$
on the two oriented edges from
$(0, 0)$
to
$(0, 1)$
, and from
$(1, 0)$
to
$(1, 1)$
, respectively, are
$0$
. The harmonic
$1$
-form
$u_2$
is obtained analogously. A direct computation yields
\begin{equation*} {\Sigma }^\rho = \begin{pmatrix} \frac {\mu (s_1)\mu (s_2)}{1-\mu (\textrm {id})} & \quad 0\\[4pt] 0 & \quad \frac {\mu (s_1)\mu (s_2)}{1-\mu (\textrm {id})} \end{pmatrix} \quad \text{for $\rho \in (0, 1]$}. \end{equation*}
4.2.2. Type
$\widetilde A_2$
Let us consider the affine Weyl group of type
$\widetilde A_2$
:
\begin{equation*} \Gamma =\langle s_1, s_2, s_3 \mid s_1^2=s_2^2=s_3^2=(s_1s_2)^3=(s_2s_3)^3=(s_3s_1)^3=1 \rangle \end{equation*}
with
$S=\{s_1, s_2, s_3\}$
. The Cayley graph
$\textrm {Cay}(\Gamma , S)$
and the group action on
${\mathbb R}^2$
is described in Figure 3 (left). The group
$\Gamma$
is isomorphic to
${\mathbb Z}^2 \rtimes \mathfrak{S}_3$
where
$\mathfrak{S}_3$
is the symmetric group on the set
$\{1, 2, 3\}$
. The quotient graph
$G={\mathbb Z}^2\backslash \textrm {Cay}(\Gamma , S)$
is described in Figure 3 (right).
The Cayley graph of the affine Weyl group
$(\Gamma , S)$
of type
$\widetilde A_2$
and the action on
${\mathbb R}^2$
(left), and the quotient graph
$G={\mathbb Z}^2\backslash \textrm {Cay}(\Gamma , S)$
(right).
Let us consider
${\Phi }:\Gamma \to {\mathbb R}^2$
such that the origin is the barycenter of a fundamental chamber (which is an equilateral triangle of side length
$(2\sqrt {3})^{1/2}/3$
). A fundamental domain for the
${\mathbb Z}^2$
-action is a hexagon of unit area. Let
$\mu$
be a probability measure on
$\Gamma$
such that
\begin{equation*} \mu (s_1)=\mu (s_2)=\mu (s_3)=\frac {1}{3}(1-\mu (\textrm {id})) \quad \text{and} \quad 0\lt \mu (\textrm {id})\lt 1. \end{equation*}
The matrix for
$\mu$
in the local central limit theorem (Theorem 3.6) is computed as
\begin{equation*} {\Sigma }^\mu = \begin{pmatrix} \frac {\sqrt {3}}{27}(1-\mu (\textrm {id})) & 0\\[4pt] 0 & \frac {\sqrt {3}}{27}(1-\mu (\textrm {id})) \end{pmatrix}. \end{equation*}
4.2.3. Type
$\widetilde C_2$
Let us consider the affine Weyl group of type
$\widetilde C_2$
:
\begin{equation*} \Gamma =\langle s_1, s_2, s_3 \mid s_1^2=s_2^2=s_3^2=(s_1s_2)^4=(s_2s_3)^4=(s_3s_1)^2=1 \rangle \end{equation*}
with
$S=\{s_1, s_2, s_3\}$
. The Cayley graph
$\textrm {Cay}(\Gamma , S)$
and the group action on
${\mathbb R}^2$
is described in Figure 4 (left). The group
$\Gamma$
is isomorphic to
${\mathbb Z}^2 \rtimes (({\mathbb Z}/2)^2\rtimes \mathfrak{S}_2)$
where
$({\mathbb Z}/2)^2\rtimes \mathfrak{S}_2$
is the signed permutations on the set
$\{1, 2\}$
. The quotient graph
$G$
of the Cayley graph with the set of generators
$S$
by the lattice
${\mathbb Z}^2$
is described in Figure 4 (right).
The Cayley graph of the affine Weyl group
$(\Gamma , S)$
of type
$\widetilde C_2$
and the action on
${\mathbb R}^2$
(left), and the quotient graph
$G={\mathbb Z}^2\backslash \textrm {Cay}(\Gamma , S)$
(right).
Let us consider
${\Phi }:\Gamma \to {\mathbb R}^2$
such that the origin is the barycenter of a square of side length
$1/4$
(where a fundamental chamber is an isosceles right triangle of equal side length
$1/2$
). A fundamental domain for the
${\mathbb Z}^2$
-action has unit area. Let
$\mu$
be a probability measure on
$\Gamma$
such that
\begin{equation*} \mu (s_1)=\mu (s_2)=\mu (s_3)=\frac {1}{3}(1-\mu (\textrm {id})) \quad \text{and} \quad 0\lt \mu (\textrm {id})\lt 1. \end{equation*}
The matrix for
$\mu$
in the local central limit theorem (Theorem 3.6) is computed as
\begin{equation*} {\Sigma }^\mu = \begin{pmatrix} \frac {1}{24}(1-\mu (\textrm {id})) & 0\\[4pt] 0 & \frac {1}{24}(1-\mu (\textrm {id})) \end{pmatrix}. \end{equation*}
Acknowledgments
The author would like to thank Professor Jérémie Brieussel for helpful comments on an earlier version of this paper and discussions, and Professors Benoit Collins, Naotaka Kajino, Shu Kanazawa, Tomoki Kawahira, Tomoyuki Shirai, and Kouji Yano for useful comments and discussions. He also thanks the anonymous referees for constructive comments and suggestions. The author is partially supported by JSPS Grant-in-Aid for Scientific Research JP20K03602 and JP24K06711.
Appendix A. Noise sensitivity problem on
${\mathbb Z}^m$
Theorem A.1.
Let
$m$
be a positive integer and
$\mu$
be a probability measure on
${\mathbb Z}^m$
. If
$\mu$
has a finite second moment and the support generates the group as a semigroup, then
\begin{equation*} \lim _{\rho \to 1}\limsup _{n \to \infty }\|\pi ^\rho _n-\mu _n\times \mu _n\|_{\textrm {TV}}=0 \quad {and} \quad \lim _{\rho \to 0}\liminf _{n \to \infty }\|\pi ^\rho _n-\mu _n\times \mu _n\|_{\textrm {TV}} =1. \end{equation*}
Let
$\Sigma$
be a non-degenerate positive definite (covariance) matrix of size
$m$
and
\begin{equation*} f_{\Sigma }(v)\,:\!=\,\frac {1}{\sqrt {(2\pi )^m \det {\Sigma }}}e^{-\frac {1}{2}\langle v, {\Sigma }^{-1}v \rangle } \quad \text{for $v \in {\mathbb R}^m$}. \end{equation*}
Let us define the function
$F(v)\,:\!=\,\sum _{x\in {\mathbb Z}^m}f_{\Sigma }(x+v)$
for
$v \in {\mathbb R}^m$
. Note that since
$F$
is
${\mathbb Z}^m$
-periodic on
${\mathbb R}^m$
, it is regarded as a function on
$[0, 1)^m$
. Let
\begin{equation*} \widehat F(x)\,:\!=\,\int _{[0, 1)^m}F(v)e^{-2\pi i \langle v, x \rangle }\,dv \quad \text{and} \quad \widehat f_{\Sigma }(x)\,:\!=\,\int _{{\mathbb R}^m}f_{\Sigma }(v)e^{-2\pi i \langle v, x \rangle }\,dv \quad \text{for $x \in {\mathbb Z}^m$}. \end{equation*}
Since
$f_{\Sigma }$
is in the Schwartz class on
${\mathbb R}^m$
, we have
$\widehat F(x)=\widehat f_{\Sigma }(x)$
for
$x \in {\mathbb Z}^m$
and
\begin{equation*} F(v)=\sum _{x \in {\mathbb Z}^m}\widehat f_{\Sigma }(x)e^{2\pi i \langle x, v \rangle }, \end{equation*}
where the right hand side is absolutely convergent. In the case when
$v=0$
, the Poisson summation formula is obtained by a direct computation,
\begin{equation*} \sum _{x \in {\mathbb Z}^m}f_{\Sigma }(x)=\sum _{x \in {\mathbb Z}^m}\widehat f_{\Sigma }(x)=\sum _{x \in {\mathbb Z}^m}e^{-2\pi ^2\langle x, {\Sigma } x \rangle }. \end{equation*}
Thus, there exists a constant
$c_{\Sigma }\gt 0$
such that for all
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{equation} \sum _{x \in {\mathbb Z}^m}f_{n{\Sigma }}(x)=\sum _{x \in {\mathbb Z}^m}e^{-2\pi ^2n\langle x, {\Sigma } x \rangle }=1+O_{\Sigma }(e^{-c_{\Sigma } n}). \end{equation}
Let
${\Sigma }_1$
and
${\Sigma }_2$
be covariance matrices of size
$m$
. First, we consider the upper bound. For every real
$\lambda \gt 0$
and for every
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{align} &\sum _{\|x\| \le \lambda n^{1/2}}|f_{n{\Sigma }_1}(x)-f_{n{\Sigma }_2}(x)| \nonumber \\ &\le \sum _{\|x\| \le \lambda n^{1/2}}\left |f_{n{\Sigma }_1}(x)-\sqrt {\frac {\det {\Sigma }_2}{\det {\Sigma }_1}}f_{n{\Sigma }_2}(x)\right |+\sum _{\|x\| \le \lambda n^{1/2}}\left |1-\sqrt {\frac {\det {\Sigma }_2}{\det {\Sigma }_1}}\right |f_{n{\Sigma }_2}(x). \end{align}
The first sum in (A.2) is estimated as follows: For
$x \in {\mathbb Z}^m$
,
\begin{align*} \Big |1-e^{-\frac {1}{2n}\langle x, ({\Sigma }_2^{-1}-{\Sigma }_1^{-1})x \rangle }\Big | \le e^{\frac {1}{2n}|\langle x, ({\Sigma }_2^{-1}-{\Sigma }_1^{-1})x \rangle |}- e^{-\frac {1}{2n}|\langle x, ({\Sigma }_2^{-1}-{\Sigma }_1^{-1})x \rangle |}. \end{align*}
Since
$|\langle x, ({\Sigma }_2^{-1}-{\Sigma }_1^{-1})x \rangle |\le \|{\Sigma }_2^{-1}-{\Sigma }_1^{-1}\|\|x\|^2$
, for
$x \in {\mathbb Z}^m$
with
$\|x\|\le \lambda n^{1/2}$
,
\begin{equation*} \Big |1-e^{-\frac {1}{2n}\langle x, ({\Sigma }_2^{-1}-{\Sigma }_1^{-1})x \rangle }\Big | \le e^{\frac {\lambda ^2}{2}\|{\Sigma }_2^{-1}-{\Sigma }_1^{-1}\|}-e^{-\frac {\lambda ^2}{2}\|{\Sigma }_2^{-1}-{\Sigma }_1^{-1}\|}=2\sinh \left (\frac {\lambda ^2}{2}\|{\Sigma }_2^{-1}-{\Sigma }_1^{-1}\|\right ). \end{equation*}
Therefore the first sum in the right hand side of (A.2) is at most
\begin{align*} \sum _{\|x\| \le \lambda n^{1/2}} \Big |1-e^{-\frac {1}{2n}\langle x, ({\Sigma }_2^{-1}-{\Sigma }_1^{-1})x \rangle }\Big |f_{n{\Sigma }_1}(x) \le 3\lambda ^2\|{\Sigma }_2^{-1}-{\Sigma }_1^{-1}\|\left (1+O_{{\Sigma }_1}(e^{-c_{{\Sigma }_1}n})\right ), \end{align*}
if
$\|{\Sigma }_2^{-1}-{\Sigma }_1^{-1}\| \le 2/\lambda ^2$
for all
$n \in {\mathbb Z}_{\gt 0}$
and for all
$\lambda \gt 0$
by (A.1). The second sum in the right hand side of (A.2) is at most, for all
$n \in {\mathbb Z}_{\gt 0}$
, by (A.1),
\begin{align*} \left |1-\sqrt {\frac {\det {\Sigma }_2}{\det {\Sigma }_1}}\right |\sum _{x \in {\mathbb Z}^m} f_{n{\Sigma }_2}(x) =\left |1-\sqrt {\frac {\det {\Sigma }_2}{\det {\Sigma }_1}}\right |\left (1+O_{{\Sigma }_2}(e^{-c_{{\Sigma }_2}n})\right ). \end{align*}
Summarising the above estimates yields for every
$\lambda \gt 0$
, there exist constants
$C_{1, 2, \lambda }=C_{{\Sigma }_1, {\Sigma }_2, \lambda }\gt 0$
and
$c_{1, 2}=c_{{\Sigma }_1, {\Sigma }_2}\gt 0$
such that for all
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{align} \sum _{\|x\| \le \lambda n^{1/2}}|f_{n{\Sigma }_1}(x)-f_{n{\Sigma }_2}(x)| \le 3\lambda ^2\|{\Sigma }_2^{-1}-{\Sigma }_1^{-1}\|+\left |1-\sqrt {\frac {\det {\Sigma }_2}{\det {\Sigma }_1}}\right |+C_{1, 2, \lambda } e^{-c_{1,2}n}. \end{align}
Next let us consider the lower bound. Noting that
$\sqrt {f_1-f_2} \ge \sqrt {f_1}-\sqrt {f_2}$
for
$f_1 \ge f_2 \ge 0$
, we have by squaring both sides and summing over
${\mathbb Z}^m$
,
\begin{align*} \|f_{n{\Sigma }_1}-f_{n{\Sigma }_2}\|_1 \ge \sum _{x \in {\mathbb Z}^m}f_{n{\Sigma }_1}(x)+\sum _{x\in {\mathbb Z}^m}f_{n{\Sigma }_2}(x)-2\sum _{x \in {\mathbb Z}^m}\sqrt {f_{n{\Sigma }_1}(x)f_{n{\Sigma }_2}(x)}. \end{align*}
In the following, we assume that
${\Sigma }_1^{-1}+{\Sigma }_2^{-1}$
is invertible. In that case, by (A.1),
\begin{align*} \sum _{x \in {\mathbb Z}^m}\sqrt {f_{n{\Sigma }_1}(x)f_{n{\Sigma }_2}(x)} &=\sum _{x \in {\mathbb Z}^m}\frac {1}{(2\pi )^{\frac {m}{2}}(\det (n{\Sigma }_1)\det (n{\Sigma }_2))^{\frac {1}{4}}} e^{-\frac {1}{4n}\langle x, ({\Sigma }_1^{-1}+{\Sigma }_2^{-1})x \rangle }\\ &=\frac {2^{\frac {m}{2}}(\det \left (({\Sigma }_1^{-1}+{\Sigma }_2^{-1})^{-1}\right ))^{\frac {1}{2}}}{(\det {\Sigma }_1 \det {\Sigma }_2)^{\frac {1}{4}}} \sum _{x \in {\mathbb Z}^m}e^{-4\pi ^2 n\langle x, ({\Sigma }_1^{-1}+{\Sigma }_2^{-1})^{-1}x \rangle }. \end{align*}
Let us focus on the special case when
$m=2$
, and
\begin{equation*} {\Sigma }^1=\sigma ^2 \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix} \quad \text{and} \quad {\Sigma }^\rho =\sigma ^2 \begin{pmatrix} 1 & 1-\rho \\ 1-\rho & 1 \end{pmatrix} \quad \text{for $\sigma \gt 0$ and $0\lt \rho \le 1$}. \end{equation*}
In this case,
\begin{align*} ({\Sigma }^1)^{-1}+({\Sigma }^\rho )^{-1} =\frac {1}{\sigma ^2} \begin{pmatrix} 1+\frac {1}{\rho (2-\rho )} & -\frac {1-\rho }{\rho (2-\rho )}\\ -\frac {1-\rho }{\rho (2-\rho )} & 1+\frac {1}{\rho (2-\rho )} \end{pmatrix}. \end{align*}
Furthermore,
$\det {\Sigma }^1=\sigma ^4$
,
$\det {\Sigma }^\rho =\sigma ^4\rho (2-\rho )$
and
\begin{equation*} \det \left (({\Sigma }^1)^{-1}+({\Sigma }^\rho )^{-1}\right )=\frac {1}{\sigma ^4}\left (\left (1+\frac {1}{\rho (2-\rho )}\right )^2-\left (\frac {1-\rho }{\rho (2-\rho )}\right )^2\right ). \end{equation*}
Hence one computes for all small enough
$\rho \gt 0$
,
\begin{align*} \frac {2}{(\rho (2-\rho ))^{\frac {1}{4}}\left (\left (1+\frac {1}{\rho (2-\rho )}\right )^2-\left (\frac {1-\rho }{\rho (2-\rho )}\right )^2\right )^{\frac {1}{2}}} =\frac {2(\rho (2-\rho ))^{\frac {3}{4}}}{\sqrt {(\rho (2-\rho )+1)^2-(1-\rho )^2}}\lt 2\rho ^{\frac {1}{4}}. \end{align*}
Summarising the above computations and letting
$n \to \infty$
yield, for all small enough
$\rho \gt 0$
,
\begin{equation} \liminf _{n \to \infty }\|f_{n{\Sigma }^\rho }-f_{n{\Sigma }^1}\|_1 \ge 2-4\rho ^{\frac {1}{4}}. \end{equation}
Proof of Theorem A.1
Noting that
${\mathbb E}_{\pi ^\rho _n} {\boldsymbol w}_n$
is independent of
$\rho \in [0, 1]$
, we assume that
$\mu$
has mean zero up to shifting by the mean. Further, we assume that
$\mu$
is aperiodic (i.e. for each
$x\in {\mathbb Z}^m$
for all large enough
$n$
one has
$\mu _n(x)\gt 0$
) and the general case is reduced to this case by dividing the times according to the period. For
$0\lt \rho \le 1$
, we note that
$\pi ^\rho$
is aperiodic since
$\pi ^\rho$
and
$\mu \times \mu$
have the same support in
${\mathbb Z}^{2m}$
. Let
${\Sigma }^\rho$
and
${\Sigma }^1$
denote the covariance matrices of size
$2m$
for
$\pi ^\rho$
and
$\mu \times \mu$
, respectively.
First let us show the upper bound in the claim. For all real
$\lambda \gt 0$
and integers
$n \in {\mathbb Z}_{\gt 0}$
,
\begin{align*} \sum _{\|{\boldsymbol x}\|\gt \lambda n^{1/2}}\pi ^\rho _n({\boldsymbol x})={\mathbb P}_{\pi ^\rho }\left (\|{\boldsymbol w}_n\|\gt \lambda n^{1/2}\right ) &\le \frac {1}{\lambda ^2 n}{\mathbb E}_{\pi ^\rho _n} \|{\boldsymbol w}_n\|^2 =\frac {2}{\lambda ^2}{\mathbb E}_\mu |x|^2, \end{align*}
by the Chebyshev inequality. This shows that (recalling that
$\pi ^1=\mu \times \mu$
)
\begin{equation} \sum _{\|{\boldsymbol x}\|\gt \lambda n^{1/2}}|\pi ^\rho _n({\boldsymbol x})-\mu _n\times \mu _n({\boldsymbol x})|\le \frac {4}{\lambda ^2}{\mathbb E}_\mu |x|^2. \end{equation}
Since
$\pi ^\rho$
is aperiodic for
$\rho \in (0, 1]$
, then the local central limit theorem [Reference Lawler and Limic8, Theorem 2.3.9] shows the following: There exists a sequence
$\delta _n\gt 0$
such that
$\delta _n \to 0$
as
$n\to \infty$
, for all
$n \in {\mathbb Z}_{\gt 0}$
and for all
${\boldsymbol x}\in {\mathbb Z}^{2m}$
,
\begin{equation} |\pi ^\rho _n({\boldsymbol x})-f_{n{\Sigma }^\rho }({\boldsymbol x})| \le \frac {\delta _n}{n^m} \quad \text{and} \quad |\mu _n\times \mu _n({\boldsymbol x})-f_{n{\Sigma }^1}({\boldsymbol x})|\le \frac {\delta _n}{n^m}. \end{equation}
Note that there exists a constant
$C_m\gt 0$
such that for all real
$\lambda \gt 0$
and all
$n \in {\mathbb Z}_{\gt 0}$
, the number of
${\boldsymbol x} \in {\mathbb Z}^{2m}$
with
$\|{\boldsymbol x}\|\le \lambda n^{1/2}$
is at most
$C_m \lambda ^{2m} n^m$
. Therefore it holds that
\begin{align} \sum _{\|{\boldsymbol x}\|\le \lambda n^{1/2}}|\pi ^\rho _n({\boldsymbol x})-\mu _n\times \mu _n({\boldsymbol x})| \le C_m\lambda ^{2m} n^m \cdot \frac {2\delta _n}{n^m}+ \sum _{\|{\boldsymbol x}\|\le \lambda n^{1/2}}|f_{n{\Sigma }^\rho }({\boldsymbol x})-f_{n{\Sigma }^1}({\boldsymbol x})|. \end{align}
Hence by (A.3), (A.5), and (A.7), for every
$\lambda \gt 0$
,
\begin{equation*} \limsup _{n \to \infty } \|\pi ^\rho _n-\mu _n\times \mu _n\|_1 \le 3\lambda ^2\|({\Sigma }^\rho )^{-1}-({\Sigma }^1)^{-1}\|+\left |1-\sqrt {\frac {\det {\Sigma }^\rho }{\det {\Sigma }^1}}\right |+\frac {4}{\lambda ^2}{\mathbb E}_\mu |x|^2. \end{equation*}
Since
${\Sigma }^\rho \to {\Sigma }^1$
as
$\rho \to 1$
, we obtain
\begin{equation*} \limsup _{\rho \to 1}\limsup _{n \to \infty } \|\pi ^\rho _n-\mu _n\times \mu _n\|_1 \le \frac {4}{\lambda ^2}{\mathbb E}_\mu |x|^2. \end{equation*}
This holds for all
$\lambda \gt 0$
, and thus we obtain in the total variation distance
\begin{equation*} \lim _{\rho \to 1}\limsup _{n \to \infty }\|\pi ^\rho _n-\mu _n\times \mu _n\|_{\textrm {TV}} =0. \end{equation*}
This shows the upper bound in the claim.
Next, let us show the lower bound in the claim. The general case reduces to the case when
$m=1$
since a projection
${\mathbb Z}^m \to {\mathbb Z}$
(whence
${\mathbb Z}^{2m} \to {\mathbb Z}^2$
) to a coordinate only decreases the total variation distance. Let
${\Sigma }={\Sigma }^{\rho }$
. For
${\boldsymbol x}_i \in {\mathbb R}^m$
,
$i=1, 2$
,
\begin{align*} |\langle {\boldsymbol x}_1, {\Sigma }^{-1}{\boldsymbol x}_1 \rangle -\langle {\boldsymbol x}_2, {\Sigma }^{-1}{\boldsymbol x}_2 \rangle | &\le 2\int _0^1 |\langle {\boldsymbol x}_2-{\boldsymbol x}_1, {\Sigma }^{-1}({\boldsymbol x}_1+t({\boldsymbol x}_2-{\boldsymbol x}_1)) \rangle |\,dt\\ &\le 2\|{\Sigma }^{-1}\|\|{\boldsymbol x}_1-{\boldsymbol x}_2\| \max \{\|{\boldsymbol x}_1\|, \|{\boldsymbol x}_2\|\}. \end{align*}
Thus, if
$\|{\boldsymbol x}_1-{\boldsymbol x}_2\|_\infty \le 1$
(where
$\|\cdot \|_\infty$
denotes the supremum norm) and
$\|{\boldsymbol x}_i\| \ge \sqrt {2}$
,
$i=1, 2$
, then
$\|{\boldsymbol x}_1-{\boldsymbol x}_2\| \le \|{\boldsymbol x}_2\|$
and
\begin{equation*} |\langle {\boldsymbol x}_1, {\Sigma }^{-1}{\boldsymbol x}_1 \rangle -\langle {\boldsymbol x}_2, {\Sigma }^{-1}{\boldsymbol x}_2 \rangle | \le 2\|{\Sigma }^{-1}\|\|{\boldsymbol x}_1-{\boldsymbol x}_2\| (\|{\boldsymbol x}_2\|+\|{\boldsymbol x}_1-{\boldsymbol x}_2\|) \le 4\sqrt {2}\|{\Sigma }^{-1}\|\|{\boldsymbol x}_2\|. \end{equation*}
This shows that for
${\boldsymbol x}_i \in {\mathbb R}^m$
such that
$\|{\boldsymbol x}_1-{\boldsymbol x}_2\|_\infty \le 1$
and
$\|{\boldsymbol x}_i\|\ge \sqrt {2}$
,
$i=1, 2$
,
\begin{equation*} f_{n{\Sigma }}({\boldsymbol x}_1) \le f_{n{\Sigma }}({\boldsymbol x}_2)e^{\frac {c_{\Sigma }}{n}\|{\boldsymbol x}_2\|}, \quad \text{where $c_{\Sigma }\,:\!=\,2\sqrt {2}\|{\Sigma }^{-1}\|$}. \end{equation*}
Therefore, we obtain
\begin{align*} \sum _{\|{\boldsymbol x}\| \gt \lambda n^{\frac {1}{2}}}f_{n{\Sigma }}({\boldsymbol x}) \le \int _{\|{\boldsymbol x}\|\ge \lambda n^{\frac {1}{2}}-\sqrt {2}}\frac {1}{\sqrt {(2\pi )^2 \det (n{\Sigma })}}e^{-\frac {1}{2n}\langle {\boldsymbol x}, {\Sigma }^{-1}{\boldsymbol x} \rangle +\frac {c_{\Sigma }}{n}\|{\boldsymbol x}\|}\,d{\boldsymbol x}. \end{align*}
Since
${\Sigma }^{-1}$
is positive definite, there exists a constant
$\alpha \gt 0$
such that
$\langle {\boldsymbol x}, {\Sigma }^{-1}{\boldsymbol x} \rangle \ge \alpha \|{\boldsymbol x}\|^2$
for all
${\boldsymbol x} \in {\mathbb R}^m$
, and
\begin{equation*} -\frac {1}{2n}\langle {\boldsymbol x}, {\Sigma }^{-1}{\boldsymbol x} \rangle +\frac {c_{\Sigma }}{n}\|{\boldsymbol x}\| \le -\frac {\alpha }{2n}\|{\boldsymbol x}\|^2+\frac {c_{\Sigma }}{n}\|{\boldsymbol x}\| =-\frac {\alpha }{2n}\left (\|{\boldsymbol x}\|-\frac {c_{\Sigma }}{\alpha }\right )^2+\frac {c_{\Sigma }^2}{2\alpha n}. \end{equation*}
This shows that the last integral is at most, by the change of variables
${\boldsymbol x} \mapsto \sqrt {n}{\boldsymbol x}$
,
\begin{align*} &\int _{\|{\boldsymbol x}\| \ge \lambda n^{\frac {1}{2}}-\sqrt {2}}\frac {1}{\sqrt {(2\pi )^2 \det (n{\Sigma })}}e^{-\frac {\alpha }{2n}\left (\|{\boldsymbol x}\|-\frac {c_{\Sigma }}{\alpha }\right )^2+\frac {c_{\Sigma }^2}{2\alpha n}}\,d{\boldsymbol x}\\ &=\frac {e^{\frac {c_{\Sigma }^2}{2\alpha n}}}{2\pi \sqrt {\det {\Sigma }}}\int _{\|{\boldsymbol x}\|\ge (\lambda n^{\frac {1}{2}}-\sqrt {2})/\sqrt {n}}e^{-\frac {\alpha }{2}\left (\|{\boldsymbol x}\|-\frac {c_{\Sigma }}{\alpha \sqrt {n}}\right )^2}\,d{\boldsymbol x} =\frac {e^{\frac {c_{\Sigma }^2}{2\alpha n}}}{\sqrt {\det {\Sigma }}}\int _{(\lambda n^{\frac {1}{2}}-\sqrt {2})/\sqrt {n}}^\infty e^{-\frac {\alpha }{2}\left (s-\frac {c_{\Sigma }}{\alpha \sqrt {n}}\right )^2}s\,ds. \end{align*}
In the above, the last equality has used the polar coordinate. There exists a constant
$C_{\Sigma }\gt 0$
such that
$s+c_{\Sigma }/(\alpha \sqrt {n}) \le s e^{\frac {\alpha }{4}s^2}$
for all
$s\gt C_{\Sigma }$
and all
$n\ge 1$
. The last term above equals by the change of variables, for
$R\,:\!=\,(\lambda n^{\frac {1}{2}}-\sqrt {2})/\sqrt {n}-c_{\Sigma }/(\alpha \sqrt {n})$
,
\begin{equation*} \frac {e^{\frac {c_{\Sigma }^2}{2\alpha n}}}{\sqrt {\det {\Sigma }}}\int _{R}^\infty e^{-\frac {\alpha }{2}s^2}\left (s+\frac {c_{\Sigma }}{\alpha \sqrt {n}}\right )\,ds \le \frac {e^{\frac {c_{\Sigma }^2}{2\alpha n}}}{\sqrt {\det {\Sigma }}}\int _{R}^\infty e^{-\frac {\alpha }{4}s^2}s\,ds =\frac {e^{\frac {c_{\Sigma }^2}{2\alpha n}}}{\sqrt {\det {\Sigma }}}\frac {2}{\alpha }e^{-\frac {\alpha }{4}R^2}. \end{equation*}
Note that for all
$n\gt (c_{\Sigma }/\alpha )^2+2$
,
\begin{equation*} R=(\lambda n^{\frac {1}{2}}-\sqrt {2})/\sqrt {n}-c_{\Sigma }/(\alpha \sqrt {n}) \ge \lambda -\sqrt {2}/\sqrt {n}-1 \ge \lambda -2. \end{equation*}
Hence, there exist constants
$c_\rho , C_\rho \gt 0$
such that for all
$n\gt C_\rho$
and all
$\lambda \ge C_\rho$
,
\begin{equation*} \sum _{\|{\boldsymbol x}\| \gt \lambda n^{\frac {1}{2}}}f_{n{\Sigma }}({\boldsymbol x}) \le C_\rho e^{-c_\rho \lambda ^2}. \end{equation*}
Therefore, together with (A.6), there exist (possibly different) constants
$c_\rho , C_\rho \gt 0$
depending only on
$\rho$
such that the following holds: For all
$n\gt C_\rho$
and all
$\lambda \ge C_\rho$
,
\begin{align*} &\|\pi ^\rho _n-\mu _n\times \mu _n\|_1 \ge \sum _{\|{\boldsymbol x}\| \le \lambda n^{1/2}}|\pi _n^\rho ({\boldsymbol x})-\mu _n\times \mu _n({\boldsymbol x})|\\ &\ge \sum _{\|{\boldsymbol x}\| \le \lambda n^{1/2}}|f_{n{\Sigma }^\rho }({\boldsymbol x})-f_{n{\Sigma }^1}({\boldsymbol x})|-2C_m\lambda ^{2m} \delta _n \ge \|f_{n{\Sigma }^\rho }-f_{n{\Sigma }^1}\|_1-2C_\rho e^{-c_\rho \lambda ^2}-2C_m\lambda ^{2m} \delta _n. \end{align*}
Thus by (A.4), letting
$n \to \infty$
, we obtain for all small enough
$\rho \gt 0$
,
\begin{equation*} \liminf _{n\to \infty }\|\pi ^\rho _n-\mu _n\times \mu _n\|_1 \ge 2-4\rho ^{\frac {1}{4}}-2C_\rho e^{-c_\rho \lambda ^2}. \end{equation*}
In total variation distance, letting
$\lambda \to \infty$
and then
$\rho \to 0$
yields
\begin{equation*} \lim _{\rho \to 0}\liminf _{n \to \infty }\|\pi ^\rho _n-\mu _n\times \mu _n\|_{\textrm {TV}} =1, \end{equation*}
as required.
