The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters
It is shown that the KNS-spectral measure of the typical Schreier graph of the action of 3-generated 2-group of intermediate growth constructed by the first author in 1980 on the boundary of binary rooted tree coincides with the Kesten’s spectral measure, and coincides (up to affine transformation o...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2012
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/152209 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters / R.I. Grigorchuk, Ya.S. Krylyuk // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 2. — С. 237–272. — Бібліогр.: 39 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-152209 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1522092019-06-09T01:25:18Z The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters Grigorchuk, R.I. Krylyuk, Ya.S. It is shown that the KNS-spectral measure of the typical Schreier graph of the action of 3-generated 2-group of intermediate growth constructed by the first author in 1980 on the boundary of binary rooted tree coincides with the Kesten’s spectral measure, and coincides (up to affine transformation of R) with the density of states of the corresponding diatomic linear chain. Jacoby matrix associated with Markov operator of simple random walk on these graphs is computed. It shown shown that KNS and Kesten's spectral measures of the Schreier graph based on the orbit of the point 1∞ are different but have the same support and are absolutely continuous with respect to the Lebesgue measure. 2012 Article The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters / R.I. Grigorchuk, Ya.S. Krylyuk // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 2. — С. 237–272. — Бібліогр.: 39 назв. — англ. 1726-3255 2010 MSC:20F, 20P, 37A, 60J, 82D. http://dspace.nbuv.gov.ua/handle/123456789/152209 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
It is shown that the KNS-spectral measure of the typical Schreier graph of the action of 3-generated 2-group of intermediate growth constructed by the first author in 1980 on the boundary of binary rooted tree coincides with the Kesten’s spectral measure, and coincides (up to affine transformation of R) with the density of states of the corresponding diatomic linear chain. Jacoby matrix associated with Markov operator of simple random walk on these graphs is computed. It shown shown that KNS and Kesten's spectral measures of the Schreier graph based on the orbit of the point 1∞ are different but have the same support and are absolutely continuous with respect to the Lebesgue measure. |
| format |
Article |
| author |
Grigorchuk, R.I. Krylyuk, Ya.S. |
| spellingShingle |
Grigorchuk, R.I. Krylyuk, Ya.S. The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters Algebra and Discrete Mathematics |
| author_facet |
Grigorchuk, R.I. Krylyuk, Ya.S. |
| author_sort |
Grigorchuk, R.I. |
| title |
The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters |
| title_short |
The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters |
| title_full |
The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters |
| title_fullStr |
The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters |
| title_full_unstemmed |
The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters |
| title_sort |
spectral measure of the markov operator related to 3-generated 2-group of intermediate growth and its jacobi parameters |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2012 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/152209 |
| citation_txt |
The spectral measure of the Markov operator related to 3-generated 2-group of intermediate growth and its Jacobi parameters / R.I. Grigorchuk, Ya.S. Krylyuk // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 2. — С. 237–272. — Бібліогр.: 39 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT grigorchukri thespectralmeasureofthemarkovoperatorrelatedto3generated2groupofintermediategrowthanditsjacobiparameters AT krylyukyas thespectralmeasureofthemarkovoperatorrelatedto3generated2groupofintermediategrowthanditsjacobiparameters AT grigorchukri spectralmeasureofthemarkovoperatorrelatedto3generated2groupofintermediategrowthanditsjacobiparameters AT krylyukyas spectralmeasureofthemarkovoperatorrelatedto3generated2groupofintermediategrowthanditsjacobiparameters |
| first_indexed |
2025-07-13T02:32:58Z |
| last_indexed |
2025-07-13T02:32:58Z |
| _version_ |
1837497306723647488 |
| fulltext |
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 13 (2012). Number 2. pp. 237 – 272
c© Journal “Algebra and Discrete Mathematics”
The spectral measure of the Markov operator
related to 3-generated 2-group of intermediate
growth and its Jacobi parameters1
R. I. Grigorchuk and Ya. S. Krylyuk
Abstract. It is shown that the KNS-spectral measure of
the typical Schreier graph of the action of 3-generated 2-group of
intermediate growth constructed by the first author in 1980 on the
boundary of binary rooted tree coincides with the Kesten’s spectral
measure, and coincides (up to affine transformation of R) with the
density of states of the corresponding diatomic linear chain.
Jacoby matrix associated with Markov operator of simple random
walk on these graphs is computed. It shown shown that KNS and
Kesten’s spectral measures of the Schreier graph based on the orbit
of the point 1∞ are different but have the same support and are
absolutely continuous with respect to the Lebesgue measure.
Introduction
The diatomic linear chain is one of the most studied and used models
in physics and chemistry [Bri53]. What can relate this model to the
torsion group of intermediate growth G, a highly non-commutative object
constructed by the first author in [Gri80]. The goal of this article is to
describe the relation between these two apparently completely different
instances and to draw some consequences.
1The first author is supported by NSF grants DMS-0456185 and DMS-06000975.
Both authors are supported by Max-Planck Institut of Mathematiks, Bonn.
2010 MSC: 20F, 20P, 37A, 60J, 82D.
Key words and phrases: group of intermediate growth, diatomic linear chain,
random walk, spectral measure, Schreier graph, discrete Laplacian.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
238 The spectral measure of the Markov operator
Let us start with some history. The groups of Burnside type (i.e.
finitely generated infinite torsion groups [Gol64, GL02]) and the groups of
intermediate (between polynomial and exponential) growth [Gri83, Gri84]
had appeared respectively in 60-th and 80-th of the last century, and
during decades were considered as exotic groups.
A rich source of such interesting examples is the class of so-called au-
tomata groups introduced in 1963 and studied in [Hoř63, Ale72, GNS00b].
Recent developments show that this class together with the closely re-
lated classes of self-similar groups and branch groups introduced in [Gri88,
Gri00a, Gri00b] (see also the monograph of V. Nekrashevych [Nek05])
play important role in various studies in mathematics and other areas of
science.
In this paper we will show how groups of intermediate growth can be
used to interpret classical results from the new perspective, and to bring
a broader vision to some facts known for a long time. Our investigation
is based on results from [BG00a].
Namely we will describe the connection between G and the diatomic
linear chain model [Whe84, Gau84], expressed in the form of a relation
between associated Jacobi parameters and spectral measures.
The part of the paper is devoted to a simple introduction to the theory
of Schreier graphs related to self-similar groups acting on rooted trees
and to their spectral theory. Additional information on this topic can
be find in [BG00a, Gri05, Gri11]. Appendix contains the computation of
some integrals needed in the proof of the main statements.
While Cayley graphs of finitely generated groups are very popular in
combinatorial group theory and its geometric branches, Schreier graphs
didn’t play a big role (at least in infinite group theory) until recently. Ac-
tions of self-similar groups on regular rooted trees demonstrate usefulness
of Schreier graphs in different topics of holomorphic dynamics [Nek05],
fractal geometry [BGN03], and combinatorics [GŠ06].
One of the interesting ideas related to groups generated by finite
automata is to use them for constructing families of expanders. If imple-
mented, it would provide a new construction of expanders, much more
effective in practice than the existing constructions. The first step in
this direction has been made in [Gri11] where the so called asymptotic
expanders are constructed using finite automata. Proving that some finite
automata may produce a sequence of expanders has to go through compu-
tation (or estimation) of the second after 1 (in the decreasing direction)
eigenvalue of the Markov operator of Schreier graphs arising from the ac-
tion of the group on levels of the regular rooted tree. This is related to the
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 239
computation of the spectrum, i.e. to the diagonalization of the operator
(the involved operators are self-adjoint and therefore diagonalizable).
Another example leading to a spectral problem is the well known
combinatorial problem related to Hanoi Towers game on k ≥ 4 pegs (see
[GŠ06] [GŠ07]).
The problem of computation of spectra of operators (or graphs) related
to self-similar groups is hard and solved only in a few cases [BG00b,
GŻ01, GSŠ07a]. The tested examples are related to finite Mealy type
automata generating amenable (in von Neumann sense [vN29])) groups.
It is known that amenable infinite groups can not be used for construction
of expanders by taking the sequence of finite quotients. Nevertheless
even in the amenable case the study of spectra of associated objects is a
challenging problem as it could be related to other topics, for instance, to
the topics around the Atiyah Problem on L2-Betti numbers, as shown in
[GLSŻ00]. Although this problem has been solved recently [Aus09, Gra09,
LW10, PSZ10] there is still a lot of open questions around and one of
them is if different groups from the Lampligher group can contribute to
the problem.
There is no universal method for computing the spectrum, but there
is a general method based on Schur complement transformation of matri-
ces with operator valued entries which works well in certain situations
[GSŠ07b, GN07], in particular in the one that we are going to discuss.
Let us consider an easier problem. Namely, using the classical algorithm
(say of Hessenberg) let us transform the matrix of the Markov operator
to the tridiagonal form and consider it as a Jacobi matrix. We would
like to determine what type of Jacobi matrices can appear in this way,
what type of orthogonal polynomials correspond to these matrices, and
which spectral information (including the information about spectral
measures) is obtained in the process. We expect that the Jacobi matrices
and orthogonal polynomials arising from self-similar groups to possess
some interesting properties.
The goal of this article to follow this plan (at least in part) in the case
of the group G. The definition of this group in various forms (including the
one given by the action on binary rooted tree) will be given in Section 3.
Notions related to graphs and spectral measures will appear in Section 2.
The study of asymptotic properties of graphs and groups is related to
the study of spectral measures, first of all of the so called Kesten spectral
measure which is the spectral measure of the Markov operator associated
with the random walk on the group.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
240 The spectral measure of the Markov operator
Recent investigations show usefulness of the so called Kesten-von
Neumann-Serre (KNS) spectral measure [BG00a]. It is analogous to
integrated density of states in mathematical physics and can be rigorously
defined for any graph which is the limit of a covering sequence of finite
graphs [GŻ01, GŻ04]. Our main result is the following
Theorem 1. Let Γ = Γ(G, P, γ) be a Schreier graph of the group G, where
γ is any point of the boundary of the binary rooted tree on which G acts,
except in the orbit of the point 1∞, and let P = stG(γ). Then
• The KNS spectral measure of Γ coincides with the Kesten’s spectral
measure, and coincides (up to affine transformation of R) with the
density of states of the corresponding diatomic linear chain.
• The Jacobi matrix associated to the Markov operator and the initial
vector δγ given by the δ-function at vertex γ is
J =
a1 b1 0 0 0 0 . . .
b1 a2 b2 0 0 0 . . .
0 b2 a3 b3 0 0 . . .
. . .
,
where the diagonal elements an = 1 for n = 1, 2, 3, . . . and
b1 =
√
5,
bn =
√
2n + 4
2n + 1
if n is even,
√
2n+1 + 1
2n−1 + 1
if n is odd, n ≥ 3.
The coincidence of spectral measures is not an absolute phenomenon
due to the following result.
Theorem 2. For the graph Γ and γ belonging to the orbit of 1∞ the Kesten
and KNS spectral measures are different, but have the same support and
are absolutely continuous with respect to Lebesgue measure (the density
of Kesten spectral measure is explicitly computed in Lemma 6.1).
We would like to mention that some of results presented in this paper
are already known ([BG00a, GŻ04], so the paper can be considered partly
as a survey. Also authors are aware that part of the results may be
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 241
obtained in a shorter way. We preferred to use longer but classical way,
based on application of Stieltjes transform.
It would be interesting to check whether in the case of a contracting
self-similar group ([Nek05, Gri11]), the uniform the Kesten and KNS
spectral measures coincide for almost all points on the boundary of the
tree, or whether at least the measures have the same support for all
boundary points.
1. Groups acting on rooted trees, automata groups and
related representations
In this paper we shall consider only the torsion group G of intermediate
growth defined in [Gri83, Gri84] (see the definition in Section 3), but in
order to put our investigation in the general perspective let us briefly
review the necessary facts and definitions from the theory of groups acting
on regular rooted trees (see, for instance [BG00a, Nek05]). Let Σ be a
finite alphabet. The vertex set of the tree T = TΣ is the set of finite
sequences over Σ; two sequences are connected by an edge when one
can be obtained from the other by right-adjunction of a letter in Σ. The
top node is an empty sequence, and the "children" of σ are all the σs,
for s ∈ Σ. We suppose Σ = Z/dZ, with the operation s̄ = s + 1 mod d.
Let a, called the rooted automorphism of TΣ, be the automorphism of T
defined by a(sσ) = s̄σ: it acts non-trivially on the first symbol only, and
geometrically is realized as a cyclic permutation of the d subtrees just
below the root.
For any subgroup G < A (A is the group of all automorphisms of the
tree T ) stG(σ) denotes the subgroup of G consisting of automorphisms
that fix the sequence σ, and stG(n) denotes the subgroup of G consisting
of the automorphisms that fix all sequences of length n:
stG(σ) = {g ∈ G | gσ = σ}, stG(n) =
⋂
σ∈Σn
stG(σ).
The stG(n) are normal subgroups of finite index in G.
A subgroup G < A is level-transitive if the action of G on Σn is
transitive for all n ∈ N. We shall always implicitly make this assumption.
G acts naturally on the boundary ∂T = {0, . . . , d − 1}N, and this
action preserves the uniform Bernoulli measure ν on the compact space
∂T . We associate the dynamical system (G, ∂T, ν) to the group G.
This dynamical system is naturally isomorphic to the dynamical
system (G, [0, 1],m), where m is the Lebesgue measure, and G acts on
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
242 The spectral measure of the Markov operator
[0, 1] by measure-preserving transformations in the following way: let
g ∈ G, and γ ∈ [0, 1] be a d-adic irrational point with base-d expansion
0.γ1γ2 . . .. Then g(γ) = 0.δ1δ2 . . ., where the infinite sequence (γ1, γ2, . . .)
is mapped by g to (δ1, δ2, . . .). This defines the action of G on a subset of
full measure of [0, 1].
Definition 1.1. The infinite sequences σ, τ : N → Σ are confinal if there
is N ∈ N such that σn = τn for all n ≥ N .
Confinality is an equivalence relation, and equivalence classes are
called confinality classes.
A ray e in T is an infinite geodesic starting at the root of T , or
equivalently an element of the boundary ∂T = ΣN.
Let G < A and e be a ray. The associated parabolic subgroup is
P = stG(e) =
⋂
n≥0 Pn, where Pn = stG(en) and en is the length-n
prefix of e.
Since G acts on the boundary ∂T of the tree by homeomorphisms (with
respect to the natural topology on ∂T ) and preserves the uniform measure
on the boundary, we have a unitary representation π of G in L2(∂T, ν),
or equivalently in L2([0, 1],m). Let Hn be the space of L2(∂T, ν) spanned
by the characteristic functions χσ supported on the rays e starting by
σ, for all σ ∈ Σn. It is of dimension dn, and can equivalently be seen as
spanned by the characteristic functions in L2([0, 1],m) of the intervals of
the form [(i− 1)d−n, id−n], 1 ≤ i ≤ dn. These Hn are invariant subspaces,
and admit representations πn = π|Hn
. Since πn−1 is a subrepresentation
of πn, we set π⊥
n = πn ⊖ πn−1, so that π =
∞⊕
n=0
π⊥
n .
Denote by ρG/P the quasi-regular representation of G in ℓ2(G/P )
given by the left action and, for n ≥ 1, denote by ρG/Pn
the finite-
dimensional representations of G in ℓ2(G/Pn). Since G is level-transitive,
the representations πn and ρG/Pn
are unitary equivalent.
Definition 1.2. Let G be a group generated by a set S and H be a
subgroup of G. The Schreier graph S(G,H, S) is the directed graph on
the vertex set G/H, with an edge from gH to sgH withevery s ∈ S and
every gH ∈ G/H. The base point of S(G,H, S) is the coset H.
If a group G acts on a set X and x ∈ X, then the Schreier graph
Γ(G,S, stG(x)) can be interpreted as the connected component of the
graph of action (i.e. the graph whose vertices are the points of orbit of x
and two vertices are joined by an edge if one can pass from one vertex to
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 243
another by the action of a generator). In the case of a transitive action
the graph of the action is isomorphic to the Schreier graph.
Let Γn be the Schreier graph of the action of a group G on the n-th
level of the tree and let Γ be the Schreier graph of the action of G on the
boundary with the set of vertices belonging to the orbit of some point
ξ ∈ ∂T . Let vn be a vertex of the ray ξ at level n. We consider Γn as a
marked graph with a distinguished vertex vn and Γ as a marked graph with
a distinguished vertex ξ. Then Γn converge to Γ in the natural topology
on the space of marked graphs of given degree (two graphs are close in this
topology if they have isomorphic neighborhoods of large radius around
distinguished vertices) [GŻ99]. On the language of representations this
corresponds to the approximation of the infinite dimensional quasi-regular
representation ρG/P by the finite-dimensional ρG/Pn
, n ∈ N.
Definition 1.3. The Markov operatorMn on Γn is the operator on ℓ2(Γn)
given by
(Mnf)(v) =
1
|S|
∑
w∼v
f(w),
where w ∼ v means that w is a neighbor of v in Γn. This formula defines
a Markov operator M also on Γ and more generally on any regular locally
finite graph.
We have parallel definitions of Hecke type operators M̃n and M̃
for the quasi-regular representations ρG/Pn
and ρG/P in the Hilbert
spaces ℓ2(G/Pn) and ℓ2(G/P ) respectively. For example, M̃n is defined
on ℓ2(G/Pn) by formula
(M̃nf)(x) =
1
|S|
∑
s∈S
(ρG/Pn
(s)f)(x) for x ∈ ℓ2(G/Pn).
It is clear that in the case of a level transitive action we can identify M̃n
with Mn and M̃ with M as they are symmetric.
The study of the Markov operator M̃ with a distinguished vector δP
(i.e. the study of the corresponding spectral measure, the Jacobi matrix,
etc.) is closely related to the study of the simple random walk on Γ.
This allows to employ the convergence of the marked graphs {Γn} to
Γ in the space of marked graphs in order to find the spectral measure
µ of Γ (i.e. the spectral measure of M̃ , with initial vector δP ) and the
corresponding Jacobi matrix J for (M̃, δP )).
We shall prove that in the case of group G, the measure µ coincides with
the KNS-measure calculated in [BG00a]. Generally, it is a very interesting
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
244 The spectral measure of the Markov operator
question what kind of measures and what kind of Jacobi matrices and
the corresponding orthogonal polynomials stand behind a group acting
on a regular rooted tree, in particular, an automaton group. Computer
experiments of drawing histograms of spectra associated with automata,
even with a small number of states, show that corresponding distributions
and their supports may have complicated topological and measurable
structure and there is a lot of open questions in this area [BGK+07].
2. Spectral measures
Let Γ be a graph and M be its Markov operator. For any two vertices
x, y and n ∈ N let pn
x,y be the probability that a simple random walk
starting at x will be at y after n steps. Recall that if δv is the characteristic
vector of the vertex v, then
pn
x,y = 〈Mnδx|δy〉.
Spectral measures (not necessary positive) are given by their distributions
(or spectral functions) σx,y via the moments
pn
x,y =
1∫
−1
λn dσx,y(λ) ∀n ∈ N,
or, equivalently,
σx,y(λ) = 〈M(λ)δx|δy〉,
where M(λ) is the spectral decomposition of M . In case x = y the
distribution determines a positive probabilistic measure. Set σx = σx,x.
The corresponding measure dσx(λ) is called the Kesten spectral measures
as it was introduced in [Kes59] in the situation of Markov operators
corresponding to symmetric random walks on groups. (In the case of
the uniform distribution on a finite generating set Kesten measure is the
spectral measure of the Markov operator on the corresponding Cayley
graph of the group). We will usually identify spectral functions and
corresponding measures, but will be more careful when using them in
integral expressions.
It is natural to expect that if Γ is infinite, regular and connected,
then all the measures σx are equivalent, and in particular, have the same
support, but there is no proof of this fact as far as we know.
One of approaches to study infinite graphs is to approximate them by
finite graphs and to use limit type theorems.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 245
The traditional way is to approximate infinite graphs by ascending
sequence of finite subgraphs. For instance in the case of an amenable
graph one can use the approximation by a sequence of Fölner sets. Recent
studies show the usefulness of another approach when the infinite graph
is the limit of a covering sequence of finite graphs. This is the case of
Schreier graph of the group G and other groups acting on rooted trees.
In the algebraic language this corresponds to the approximation of the
infinite group by its finite quotients. To be more precise, consider the
family of subgroups
H ≤ G,H =
∞⋂
n=1
Hn,
where Hn is a descending sequence of subgroups of finite index in G. Then
the sequence of finite graphs Tn = S(G,Hn, S) is a covering sequence (in
the sense that each next graph covers the previous one) which converges
to the graph T = S(G,H, S) in the space of regular marked graphs of
degree |S|, and the following statement holds.
Proposition 2.1 ([GŻ99]). Let σn and σ be the Kesten measures of the
Schreier graphs Tn and T . Then σn(λ) → σ(λ) weakly.
On the other hand, we have the counting measure τn on each finite
Schreier graph Tn , counting the average number of eigenvalues in any
given interval. The measures τn converge to some measure τ∗ which was
called in [GŻ04] the KNS spectral measure on T . This is analogous to the
notion of integrated density of states often used in mathematical physics
literature. The existence of the limit measure τ∗ is the corollary of one of
results of Serre [Ser97].
Problem 1. Under what conditions on marked graph T which is the
limit of covering sequence Tn of finite marked graphs the KNS−spectral
measure τ∗ coincides with the Kesten spectral measure?
As we shall show this is the case for the two ended Shreier graphs of
3-generated 2-group G of intermediate growth with the standard set of
generators S = {a, b, c, d}.
In this case the corresponding KNS measure is a continuous measure,
given, up to multiplication by 4 and shift by 1 along R is given by the
following formula:
τ∗(dλ) =
|λ| dλ
π
√
(λ+ 3)(λ+ 1)(λ− 1)(3 − λ)
, λ ∈ [−3,−1] ∪ [1, 3]. (2.1)
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
246 The spectral measure of the Markov operator
The measure τ∗ was computed in [BG00a] in the following way. The
Markov operator M on the infinite Schreier graph Γ is replaced by the
operator 4M and is included in a two parametric family of operators
Q(λ, µ). These operators are in certain sense approximated by operators
Qn(λ, µ) in 2n dimensional space and include, for the value λ = −1, µ =
−1, the operator 4Mn where Mn is the Markov operator on the n-th
approximation Γn of the graph Γ by the Shreier graphs of the action of G
on the n-th level of the tree, n = 1, . . . . The operator 4Mn is represented
by the following matrix
3 1 0 0 0 . . . 0
1 1 2 0 0 . . . 0
0 2 1 1 0 . . . 0
0 0 1 1 2 . . . 0. . . . . . . . . . . . . . . . . . . . . . . . .
0 0 0 . . . 1 2 0
0 0 0 . . . 2 1 1
0 0 0 . . . 0 1 3
of size 2n in a suitable basis (related to nonstandard ordering of vertices
of the n-th level of the tree discussed in Section 3). A tricky compu-
tation based on the existence of a recursion between the spectrums of
Qn(λ, µ), n = 1, 2, . . . which involves a two dimensional rational map and
the semiconjugacy of this map to the Chebyshev-von Neumann-Ulam
map x → 2x2 − 1 results in that the spectrum of the above matrix is
{1 ±
√
5 − 4 cos(θ) : θ ∈ 2πZ/2n} − {0, 2}.
When n → ∞ the distribution of values of θ tends to the uniform
distribution and hence the distribution of eigenvalues of the above matrix
tends to the image of the uniform distribution under the functions {1 ±√
5 − 4 cos(θ)}, that is to the distribution supported in [−2, 0] ∪ [2, 4]
with density
|x− 1|
π
√
x(x− 2)(x+ 2)(4 − x)
.
The shift of R by 1 (which corresponds to transform 4M → 4M − 1)
gives the above measure 2.1.
Let us compare the way in which this measure appears in diatomic
linear chain on one hand and in association with G on the other hand.
The reader is advised to consult [Whe84] and [Gau84] for details on used
notions and formulas.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 247
The allowed frequencies ω± of the one-dimensional diatomic linear
chain are given by
ω±
γ
=
(
1
m
+
1
M
)
±
[(
1
m
+
1
M
)2
− 4 sin2 θ
mM
]1/2
,
where δ is the harmonic force constant, and m and M are the masses
of the two kinds of particles which alternate on the chain.
Setting x = (ω/ωm)2 where ωm = {2δ[1/m+ 1/M)]}1/2 gives
x =
1
2
{1 ± [1 − y sin2 θ]1/2},
where
y =
4mM
(m+M)2
.
The allowed values of x lie in the union of two intervals 0 ≤ x ≤
r/(1 + r) and 1/(1 + r) ≤ x ≤ 1 where r = m/M .
The values of θ are uniformly distributed on (0, π/2) and therefore x
is distributed in the union of the above intervals with the law given by
the density
|1 − 2x|
2π
√
x(1 − x)[r/(1 + r) − x][(1 + r)−1 − x]
.
In the case m = 1,M = 2 the parameter r = 1/2. The linear transform
z = 6x− 2 leads to the distribution 2.1.
The same type of argument shows that there is a relation between
the diatomic linear chain to the model of Markov operator related to G
and Γ in the case of arbitrary value of the parameter r.
3. The group G and its Schreier graphs
In the sequel we shall need only information about the Schreier graphs
Γn and Γ related to group G, but for completeness lets us recall the original
definition from [Gri00a] of this group as well as the realization of it by
a finite automaton. Also we will describe the corresponding action on a
2-regular rooted tree T2.
The vertices of this tree can be naturally identified with the words
over the alphabet Σ = {0, 1} (the words of length n correspond to the
vertices of level n). One can view the tree as embedded into a plane (with
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
248 The spectral measure of the Markov operator
the root at the top) and with the lexicographic ordering of vertices of
n-th level given by 0 < 1.
Then a is the automorphism permuting the top two branches of T2.
Let define b recursively as the automorphism which acts as a on the left
branch and as c on the right, where c is the automorphism which acts as a
on the left branch and as d on the right, and finally d is the automorphism
which acts as 1 on the left branch and as b on the right. In formula,
b(0xσ) = 0x̄σ, b(1σ) = 1c(σ),
c(0xσ) = 0x̄σ, c(1σ) = 1d(σ),
d(0xσ) = 0xσ, d(1σ) = 1b(σ),
where σ represents any finite binary sequence. G is the group of automor-
phisms of the tree T2 generated by {a, b, c, d}. It is readily checked that
these generators are of order 2 and that {1, b, c, d} constitute a group iso-
morphic to the Klein group. Therefore any of the generators {b, c, d} can
be omitted from generating set (but we prefer to keep all of them). One
can visualize the definition of generators by Figure 1, where e represents
the trivial action below a vertex and ǫ represents a switch.
Originally the group G was defined in [Gri80] by its action on the
interval [0, 1] from which rational dyadic points are removed. This defini-
tion is presented by Figure 2 where P stands for permutation of halves
of the interval and I represents the identity transformation.
More precisely, the transformations a, b, c, d ) act as
a(z) =
z +
1
2
if z <
1
2
z − 1
2
if z ≥ 1
2
b(z) =
0
a a 1 a ...
1
4
3
8
7 1
2
c(z) =
0
a a ...1 a
d(z) = a a 1 ... 1
Here the subintervals represent the whole interval [0, 1], labeled with
either a or 1 (the identity transformation) which act on the described
subintervals in a similar way as a or id act on [0, 1].
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 249
e e
e
e
e
e
e
e
e
e
e
P(c)
e
e
e
P(b)P(a)
P(d)
ε
ε
ε
ε
ε
ε
ε
Figure 1. Action on the tree
0
0 1/2
1/2
1/2 3/4 7/8
0
0
b
c
d
a
P
P P I
P P
PP
I
I
...
...
...
1
1
1
1
...
...
3/4 7/8 ...
3/4 7/8
Figure 2. Action on the interval [0, 1]
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
250 The spectral measure of the Markov operator
Also G can be defined as a group generated by the automaton given by
Figure 3 (the identity and non-identity elements of the symmetric group
on two symbols are represented as 1 and ε and are used to label states of
the automaton). For more on automata groups (called also self-similar
groups) see [GŠ07, GNS00a, BGK+07, Nek05].
1
1
1
1
0
0
0
ε
0,1
1 d
ba
c
1
Figure 3. The automaton for G.
The action of G on the interval preserves the Lebesgue measure m
and the action on ∂T2 preserves the uniform measure ν (which is the
Bernoulli {1/2, 1/2} measure). It is easy to see that there is a natural
isomorphism of two dynamical systems (G, [0, 1],m) and (G, ∂T2, ν) given
by the presentation of 2−adic irrational points by corresponding binary
sequences (which in turn are identified with points of the boundary).
Now we are going to summarize the known information about the
Schreier graphs Γn and the orbit graph Γ = Γζ of the action of G on the
orbit of ζ ∈ ∂T2.
The sequence Γn is the sequence of substitutional graphs i.e. can be
described by the initial graph called the axiom (in our case it is the graph
given by Figure 5 and represents the action of G on the first level of the
tree) and by the substitutional rule that allows to get Γn+1 from Γn (in
our case the substitutional rule is presented by Figures 6 and 7).
The application of one (respectively two) times of the rule to the
axiom gives the Schreier graphs for levels 2 (respectively 3) represented
on the bottom of Figure 4 (it takes some time to realize that the graphs
of the action of G on levels of the tree represented in the top part of
Figure 4 are isomorphic to the corresponding graphs given in the bottom
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 251
10
0010 1101
010110 100000 001101 111011
Figure 4.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
252 The spectral measure of the Markov operator
a
0
b
d d
cc
1
b
Figure 5. Axiom.
d
b
c
aa
a
vu
d
1u 1v
Figure 6. Rule 1.
u b v u c v u d v
d b c1u 1v 1u 1v 1u 1v
Figure 7. Rule 2.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 253
part (see the more precise statement about the isomorphism below). The
iteration of this process allows to build Γn for any n = 1, 2....
The vertices of Γn are naturally identified with Σn where Σ = {0, 1}
is supplied with the lexicographic ordering:
00 . . . 0, 00 . . . 1, . . . , 11 . . . 1
(the ordering of the vertices on nth level of T2 from the left to the right).
On the other hand, in order to realize Γn as a chain with one loop at
each vertex (as was suggested in [BG00a]) we need to consider another
ordering. This new ordering, to which we shall refer as the non-standard
ordering, is defined by induction ; if the ordering of Σi−1 is (σ1, . . . , σ2i−1),
the ordering of Σi is
(1σ1, 0σ1, 0σ2, 1σ2, 1σ3, 0σ3, . . . , 0σ2i−1 , 1σ2i−1).
The non-standard ordering gives the possibility to draw the figure of the
Schreier graph in the form of a chain as is shown in Figure 4.
Figure 8. Two ends.
Now let γ ∈ ∂T2 be any point of the boundary and vn be a vertex
belonging to the path γ and to the n-th level of the tree. Then, as
mentioned above the sequence of marked graphs (Γn, vn) converges in
the space of marked labeled graphs to the infinite marked graph (Γ(γ), γ)
whose vertices are points of the orbit of γ and γ is the distinguished vertex
of the graph.
It is known (and easy to see) that the partition of the action of G
on ∂T2 in orbits is the confinality partition described in Definition 1.1.
Another fact is that the infinite graphs Γγ are all isomorphic to the graph
represented in Figures either 8 or 9. In other words, these are graphs
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
254 The spectral measure of the Markov operator
looking as a two-periodic chain with one or two ends and with a loop
at each vertex (except for the left vertex in one ended case, which has
three loops). More precisely, if γ is not in the orbit of point 1∞ then Γγ
is isomorphic to the two ended chain, while for the points in the orbit of
1∞ the graph is the one ended chain.
The labeling of the graph depends on γ. For the case of 0∞ it is
presented in the bottom of the Figure 8 and the case of 1∞ is presented
inFigure 9.
Figure 9. One end.
For the rest of the text we will choose the distinguished vertex o = 0∞ and
will denote by en its n-th vertex 0n. The vertex e3 = 000 is on the 3-rd
place according to the non-standard ordering. Generally, en will occupy
K(n) − th place according to the non-standard ordering, where
K(n) =
{
1
3(2n+1 + 2) if n is odd,
1
3(2n+1 + 1) if n is even.
Observe that K(n) asymptotically behaves as 2
3m, where m = 2n and
n → ∞. Therefore the limit of graphs (Γn, en) is the two ended chain as
was already mentioned.
4. Calculation of the Green function for Γ
In this Section we shall compute the Green function of the simple
random walk on the two ended Schreier graph Γ of the group G (more
precisely on its modification obtained by deletion of loops). This is not
difficult and surely the expression for the function exists somewhere in
literature, but we were unable to find a reference. The computation of the
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 255
Green function can be provided by standard probabilistic methods but
instead we will use a small "trick" coming from the theory of orthogonal
polynomials and moments problem. The matrix M0
n = 4Mn − 1, where
4Mn is the “adjacency” matrix for Γn, has the size 2n and has the following
tridiagonal form:
M0
n =
2 1 0 0 0 . . . 0
1 0 2 0 0 . . . 0
0 2 0 1 0 . . . 0
0 0 1 0 2 . . . 0. . . . . . . . . . . . . . . . . . . . . . . . .
0 0 0 . . . 0 0 1
0 0 0 . . . 0 1 2
.
M0
n can be interpreted as the “adjacency” matrix of the graph Γ0
n, when
we remove from Γn one loop out each vertex. Graph Γ0
n is a 3-regular
graph and 1
3M
0
n can be interpreted as the Markov operator on the graph
Γ0
n. Since the marked vertex en = 0n in the graph Γ0
n is on the K(n) ≈ 2
32n
place, Γ0
n converge to the infinite directed graph Γ0, which determines
the Markov chain X given in Figure 10.
X qpqq p
q p q p q qp
p q
−3 −2 −1 0 1 2 3 4
:
Figure 10. The Markov chain X, corresponding to Γ0.
Here p = 2/3, q = 1
3 . In order to calculate the Green function (also called
random walk generating function) ϕX(t) of this Markov chain,
ϕX(t) =
∞∑
n=0
Pn
1,1t
n,
(Pn
1,1 is the probability of return to the initial point 1 of random walk
after n steps) we notice that ϕX(t) is the even part of the walk generating
function ϕY (t) = ΣQn
1,1t
n of the following semi-infinite Markov chain Y
given in Figure 11 below.
1 2
q
qp
pq
q
pY:
3 4
Figure 11. The Markov chain Y .
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
256 The spectral measure of the Markov operator
Lemma 4.1. There is one to one correspondence between the even length
paths on X starting at 1 and ending at 1 and even length paths on Y
starting at 1 and ending at 1. The length and the transition probabilities
under this correspondence are preserved.
In order to get this correspondence one imagines the mirror “perpen-
dicular” to our chain (assuming that states are at integer points on the
x-axis) at x = 1
2 and use the reflection of those parts of the trajectory
that stay to the left of 1.
Lemma 4.1 implies that
ϕX(t) =
ϕY (t) + ϕY (−t)
2
. (4.1)
Now, in order to calculate ϕY (t), we shall calculate the moment
generating function
mY (z) =
m̃0
z
+
m̃1
z2
+ · · ·
of the matrix, which is 3-times the matrix of transition probabilities of
the Markov chain Y , i.e. of the following infinite tridiagonal matrix M0,
M0 =
2 1 0 0 0 . . .
1 0 2 0 0 . . .
0 2 0 1 0 . . .
0 0 1 0 2 . . .
. . . . . . . . . . . .
,
where m̃n is the (1, 1) position matrix element of the n−th power of
matrix M0 (we assume that the rows and columns of M0 are numerated
by numbers 1, 2, . . . i.e. by states of the Markov chain Y ). Using the well
known correspondence between the moment generating function of the
Jacobi matrices and the continued fraction (see, for example, [Akh65])
we have asymptotic expansion
mY (z) =
1
z − 2 − 1
z − 4
z − 1
z − 4
z − . . .
. (4.2)
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 257
Consider ψ(z) =
1
z − 4
z − 1
z − 4
z − . . .
.
Obviously,
ψ(z) =
1
z − 4
z − ψ(z)
, (4.3)
which immediately implies that ψ(z) is a root of quadratic equation
z[ψ(z)]2 − (z2 − 3)ψ(z) + z = 0. (4.4)
i.e
ψ(z) =
z2 − 3 −
√
z4 − 10z2 + 9
2z
(4.5)
with the appropriate choice of a branch of the square root function.
Therefore,
mY (z) =
1
z − 2 − ψ(z)
=
1
z − 2 − z2−3−
√
z4−10z2+9
2z
=
2z
z2 − 4z + 3 +
√
z4 − 10z2 + 9
.
We will omit the index Y and write m(z). Next we can calculate
ϕM0(t) = m̃0 + m̃1t+ m̃2t
2 + · · · .
Since
ϕM0(t) =
1
t
m
(
1
t
)
=
2
t2
1
t2 − 4
t + 3 +
√
1
t4 − 10
t2 + 9
= − 1
4t
(
1 −
√(
1 + 3t
1 − 3t
)(
1 + t
1 − t
))
,
we get,
ϕM0(t) = − 1
4t
(
1 −
√(
1 + 3t
1 − 3t
)(
1 + t
1 − t
))
. (4.6)
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
258 The spectral measure of the Markov operator
The walk generating function of the paths on Y starting at 1 and ending
at 1, ϕY (t) is related to ϕM0(t) by equation ϕM0(t) = ϕY (3t). Now we
are ready to calculate the walk generating function for X,ϕX(t). Recall
that ϕX(t) is the even part of ϕY (t). Let ϕ(t) is the even part of ϕM0(t).
(It is clear that ϕ(t) = ϕX(3t).) We have
ϕ(t) =
ϕM0(t) + ϕM0(−t)
2
=
1
2
{
− 1
4t
[
1 −
√(
1 + 3t
1 − 3t
)(
1 + t
1 − t
)]
+
1
4t
[
1 −
√(
1 − 3t
1 + 3t
)(
1 − t
1 + t
)]}
=
1√
(1 − 3t)(1 + 3t)(1 − t)(1 + t)
.
Hence,
ϕ(t) = ϕX(3t) =
1√
(1 − 3t)(1 + 3t)(1 − t)(1 + t)
. (4.7)
and we are done with the computation.
5. Proof of the result
Define m1(z) from the equation
m1(z) =
1
z
ϕ
(
1
z
)
. (5.1)
i.e
m1(z) =
z√
(z + 3)(z − 3)(z − 1)(z + 1)
. (5.2)
Remark 1. There is a shortcut to obtain m1(z) from m(z) directly. It
is clear that m1(z) is the odd part of m(z). Hence, m1(z) = m(z)−m(−z)
2 .
We shall obtain the same formula for m1(z).
Recall that for any measure dσ(x) on R with a compact support its
Stieltjes transform S(z) is defined by
S(z) =
∫
R
dσ(x)
z − x
, x ∈ C.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 259
From what we have discussed follows that
m1(z) =
m0
z
+
m1
z2
+ · · ·
is the Stieltjes transform of the spectral measure of the operator 4M − 1
and initial vector δγ , γ = 0∞ where M is the Markov operator of simple
random walk on (two ended) graph Γ.
Theorem 1 will follow from the next two propositions. Observe first of
all that in two-ended case (i.e. when γ /∈ Orbit(1∞)) the Kesten spectral
measure does not depend on γ as the change of γ corresponds (up to
isomorphism of graphs) to the change of initial point in Markov chain
X, but this does not lead to the change of transition probabilities and
therefore does not effect the measure. Therefore, we can choose γ = 0∞.
Proposition 5.1. The KNS-measure for the Markov operator M with
initial vector δγ, γ = 0∞, coincides with the Kesten measure of the marked
Schreier graph (Γ, γ).
Proof. It follows immediately from the equation 5.2, the calculation of the
KNS-measure in [BG00a] (the measure is presented by formula 2.1), the
fact that the coincidence of Stieltjes transforms implies the coincidence
of measures, and the Lemma 5.1 the proof of which is postponed to the
Appendix.
Lemma 5.1. Let ρ be a measure with support B = [−3,−1] ∪ [1, 3] given
by the following density function
p(x) =
|x|
π
√
(x+ 3)(x+ 1)(x− 1)(3 − x)
, x ∈ B.
Then the Stieltjes transform of ρ is f(z) = z√
(z+3)(z−3)(z+1)(z−1)
.
Proposition 5.2. The Jacobi matrix J0 of the operator 4M − 1 for
the Schreier graph of the group G and initial vector δγ, γ = 0∞ has the
following tridiagonal form
J0 =
0 b1 0 0 . . .
b1 0 b2 0 . . .
0 b2 0 b3 . . .
0 0 b3 0 . . .
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
260 The spectral measure of the Markov operator
where
b1 =
√
5,
bn =
√
2n + 4
2n + 1
if n is even,
√
2n+1 + 1
2n−1 + 1
if n is odd, n ≥ 3.
Proof. Proposition 5.2 follows from the results of [Gau84], where the
Jacobian parameters are calculated for a class of densities, including
density
dρ(t) =
∣∣∣t− 1
2
∣∣∣
π
√
t
(
t− 1
3
) (
t− 2
3
)
(1 − t)
dt,
which is different from the density (2.1) just by the affine transformation.
As was already mentioned in the introduction, this measure is related
to the diatomic linear model in chemistry (see [Gau84], [Whe84] and
references therein).
To be more precise, let us show how to get the Jacobi parameters
from the results of [Gau84]. First of all, let us mention that the Jacobi
parameters, Kesten spectral measure, Green function for the random work
with beginning at the distinguished point of a Scheier graph, and moments
of the Kesten spectral measure determine each other. The graph (Γ, γ) is
the limit of the sequence (Γn, vn) where vn = 0n, the graph Γn looks like
a chain of length 2n, and the distinguished point vn occupies the place
K(n) ≈ 2
32n in this chain. It is obvious that the Green functions Gn(z)
of (Γn, vn) in some neighborhood of 0 converge pointwise to the Green
function G(z) of (Γ, γ) (indeed, we have the stabilization of coefficients
for each power of z in the asymptotic expansion of G(z)). This, in fact,
corresponds to the convergence of Kesten spectral measures of (Γn, vn) to
the Kesten spectral measure of (Γ, γ). The same holds for the moments
and for the Jacobi parameters. Hence, we may start with the spectral
measure given by density (5.2) and compute the corresponding Jacobi
parameters. The computation was made in [Gau84] even in more general
setting.
Consider the symmetric Jacobi matrix J0 corresponding to operator
4M −1 with the elements on upper and lower diagonals b1, b2, . . . (getting
zeros along the main diagonal). Our bi correspond to
√
βi, where βi are
parameters from the Gautschi paper used there to describe the recurrent
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 261
relations for the orthogonal polynomials. To see this, remind that starting
with a symmetric Jacobi matrix
a1 b1 0 0 . . .
b1 a2 b2 0 . . .
0 b2 a3 b3 . . .
0 0 b3 a4 . . .
. . . . . . . . . . . .
one gets a sequence of orthogonal polynomials {pk(λ)} satisfying the
recurrent relation
bk−1pk−2(λ) + akpk−1(λ) + bkpk(λ) = λpk−1(λ).
The corresponding {pk(λ)} are polynomials of degree k, but not monic.
To be able to use the formulas from [Gau84] we have to replace {pk(λ)}
by proportional monic polynomials qk(λ). Let qk(λ) = b1b2 · · · bkpk(λ).
Then we have
bk−1
qk−2
b1 . . . bk−2
+ ak
qk−1
b1 . . . bk−1
+ bk
qk
b1 . . . bk−1
= λ
qk−1
b1 . . . bk−1
.
After multiplication by b1 . . . bk−1 we obtain
b2
k−2qk−2 + akqk−1 + qk = λqk−1,
which is equivalent to
qk = (λ− ak)qk−1 − b2
k−1qk−2.
As Gautschi’s paper deals with monic orthogonal polynomials and
uses the above recurrent formula, we have to take the square root of
parameters βi as was mentioned above.
Again returning to notations of Gautschi paper, we notice that in our
case r = 1/2 for the two-sided Markov chain represented by Figure 3,
ξ =
1 − r
1 + r
=
1
3
(the parameter ξ appears on page 473 of [Gau84]), and
η =
1 − ξ
1 + ξ
=
1
2
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
262 The spectral measure of the Markov operator
(the definition of η is just before the formula (5.6) on page 480 of [Gau84]).
Now, we use the formulas (5.6) and (5.7) from [Gau84] to find β2k and
β2k+1, respectively. We have
β2k =
1
4
(
1 − 1
3
)2
1 =
((
1
2
)2k
)
/
(
1 +
(
1
2
)2k
)
=
1
9
(
22k + 4
22k + 1
)
,
β1 =
1
2
(
1 +
(
1
3
)2
)
=
5
9
,
β2k+1 =
1
4
(
1 +
(
1
3
)2
)(
1 +
(
1
2
)2k+2
)
/
(
1 +
(
1
2
)2k
)
=
1
9
(
22k+2 + 1
22k + 1
)
which completes the proof of Proposition 5.2 and therefore the proof of
Theorem 1.
Proof. The proof of Theorem 2 is based on the same type arguments that
were used for the proof of Theorem 1 and on Lemma 6.1 the proof of
which is done in the Appendix.
6. Appendix
The integrals needed for proofs of the technical lemmas can be com-
puted using the computers software. Nevertheless, in order to be com-
pletely rigorous in our arguments, we provide in this Appendix the proof of
Lemma 5.1 as well as of Lemma 6.1. We start with the proof of Lemma 5.1.
Proof. Introduce the ε-neighborhood of the set B in w-complex plane
B(ε) = {w ∈ C | d(w,B) ≤ ε} (0 < ε < 1).
Let ∂B(ε) = γ = γ1 ∪ γ2 and
-3 -1 1 3
1
2
γ
γ
Figure 12.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 263
let g(z) be the Stieltjes transform of ρ:
g(z) =
∫
B
(
1
z − x
) |x|
π
√
(x+ 3)(x+ 1)(x− 1)(3 − x)
dx. (6.1)
Introduce an auxiliary path integral Iε(z) of the function
h(w) =
1
(z − w)
w√
(w + 3)(w + 1)(w − 1)(w − 3)
,
namely
Iε(z) =
∫
γ
(
1
z − w
)
w dw√
(w + 3)(w + 1)(w − 1)(w − 3)
. (6.2)
In order to calculate g(z) defined by (6.1) we consider limit in (6.2) as ε
approaches 0. On one hand, using the right hand side of (6.2) this limit
turns out to be proportional to g(z). On the other hand, we can calculate
the path integral (6.2) using the residue calculus and then take limit as
ε → 0. We will find the Stieltjes transform of the measure ρ.
In order to calculate Iε(z) using the residue calculus, we will apply
Cauchy’s Integral formula for the open region D in w-plane with the
boundary γ ∪ CR ∪ Cr. Here CR is the circle with center at 0 of radius
(big enough) R, Cr is the circle of radius (small enough) r with center at
z (see Figure 12).
Before we will proceed further we need to fix which branch of h(w) we are
considering in D and check that this branch defines holomorphic function
in D. Since
h(w) =
(
1
z − w
)
w√
(w + 3)(w + 1)(w − 1)(w − 3)
=
1
(z − w)
w√
w + 3 ·
√
w + 1 ·
√
w − 1 ·
√
w − 3
we need to choose branches for each square root in the denominator.
We indicate the branch for
√
w in the complex plane with the cut along
the negative part of the real part: if w = reiθ where θ is the angle
from positive real axis to w, r = |w|, then
√
w =
√
r e
iθ
2 . Similarly we
choose branches for each square root with obvious modification. For such
identified branches of h(w) we can check that h(w) is a holomorphic
function on D. For example, let us assume that we choose the path τ that
goes only along γ1 but not γ2, starting with the point P on the real axis.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
264 The spectral measure of the Markov operator
1 3-3 -1
z
C
Cr
γ
21
γ
R
Figure 13.
√
w − 1 and
√
w − 3 are holomorphic functions on τ , but both
√
w + 1
and
√
w + 3 are changing sign when we make their continuation along
τ . Since h(w) contains their product
√
w + 3 ·
√
w + 1, it will not change.
The same is true for a path that goes along γ2, since in this case
√
w + 3
and
√
w + 1 will not change, only both
√
w − 1 and
√
w − 3 will change.
Again, since they participate in h(w) as a product, the function h(w) will
not change. Hence, the Monodromy Theorem guarantees that h(w) with
this choice of branches for the square root is holomorphic in D.
We can apply the Cauchy Integral Formula for the region D and a
holomorphic function h(w) in D:
∫
CR
h(w)dw =
∫
γ
h(w) dw +
∫
Cr
h(w) dw. (6.3)
Now
∣∣∣∣∣∣∣
∫
CR
h(w) dw
∣∣∣∣∣∣∣
≤
∫
CR
|w| dw
|(z − w)||
√
(w + 3)(w + 1)(w − 1)(w − 3)|
∼ R
R ·R2
· 2nR =
2π
R
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 265
-3 -1 1 3
τ
P
γ
1
γ
2
.
Figure 14.
and approaches 0 as R → +∞. From (6.3) it follows that
∫
γ
h(w) dw = −
∫
Cr
h(w) dw. (6.4)
Since the disc with boundary Cr contains only one singular point of h(w),
namely, w = z,
∫
Cr
h(w) dw = −2πi · Res h(w)|w=z
= −2πi(−1)
w√
(w + 3)(w + 1)(w − 1)(w − 3)
∣∣∣
w=z
= 2πi
z√
(z + 3)(z + 1)(z − 1)(z − 3)
.
From (6.4) we have
∫
γ
h(w) dw = −2πi
z√
(z + 3)(z + 1)(z − 1)(z − 3)
. (6.5)
Letus investigate now the limit lim
ε→0
I(z)
1 3−3 −1
+
1
+
2
1
C’ C’’ C’’C’
21 2
γγ
−
γ
1
−
γ
2
Figure 15.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
266 The spectral measure of the Markov operator
Since, I(z) =
∫
γ1
h(w) dw +
∫
γ2
h(w) dw, we compute the limit for each
∫
γi
h(w) dw (i = 1, 2). We have
∫
γ1
h(w) dw =
∫
C′
1
h(w) dw+
∫
γ+
1
h(w) dw+
∫
C′′
1
h(w) dw+
∫
γ−
1
h(w) dw. (6.6)
First, we show that the integrals over C ′
1 and C ′′
1 converge to 0 as ε → 0.
We have for C ′
1:
∣∣∣∣∣∣∣
∫
C′
1
h(w) dw
∣∣∣∣∣∣∣
≤ max
C′
1
|h(w)| length C ′
1 = max
C′
1
|h(w)| · πε.
Now |h(w)| = 1
|
√
w+3| ·
∣∣∣∣
w
(z−w)
√
(w+1)(w−1)(w−3)
∣∣∣∣ ≤ 1√
ε
M ′
1(ε), whereM ′
1(ε) =
max
C′
1
∣∣∣∣
w
(z−w)
√
(w+1)(w−1)(w−3)
∣∣∣∣. Since the function w
(z−w)
√
(w+1)(w−1)(w−3)
is holomorphic at w = −3 we have M ′
1(ε) ≤ M ′
1 (some constant) for
0 < ε ≤ 1
2 . Hence
∣∣∣∣∣∣
∫
C′
1
h(w) dw
∣∣∣∣∣∣
≤ 1√
ε
· M ′
1 · πε = πM ′
1
√
ε. Therefore,
lim
ε→0
∫
C′
1
h(w) dw = 0. Similarly, lim
ε→0
∫
C′′
1
h(w) dw = 0. Now, lim
ε→0
∫
γ+
1
h(w) dw =
−1∫
−3
[lim
ε→0
h(x+ iε)]dx. Note that
lim
ε→0
h(x+ iε) =
x
(z − x)
√
x+ 3 ·
√
−(x+ 1) · i ·
√
−(x− 1) · i ·
√
−(x− 3) · i
=
x
(z − x)i3
√
(x+ 3)(x+ 1)(x− 1)(3 − x)
= (−i) −x
(z − x)
√
(x+ 3)(x+ 1)(x− 1)(3 − x)
= (−i) |x|
(z − x)
√
(x+ 3)(x+ 1)(x− 1)(3 − x)
.
On the other hand, for x ∈ [−3,−1] lim
ε→0
h(x− iε) = − lim
ε→0
h(x+ iε), since
3 branches, namely 1√
w+1
, 1√
w−1
, and 1√
w−3
change their signs. Because
the direction of γ−
1 is the opposite to the direction of γ+
1 , we immediately
obtain that
lim
ε→0
∫
γ−
1
h(w) dw = lim
ε→0
∫
γ+
1
h(w) dw,
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 267
and
lim
ε→0
∫
γ1
h(w) dw = −2i
−1∫
−3
|x| dx
(z − x)
√
(x+ 3)(x+ 1)(x− 1)(3 − x)
. (6.7)
Similarly, we obtain
lim
ε→0
∫
γ2
h(w) dw = −2i
3∫
1
|x| dx
(z − x)
√
(x+ 3)(x+ 1)(x− 1)(3 − x)
, (6.8)
and
lim
ε→0
h(x+ iε) =
x
(z − x)
√
x+ 3
√
x+ 1 ·
√
x− 1 · i
√
−(x− 3)
= −i x
(z − x)
√
(x+ 3)(x+ 1)(x− 1)(3 − x)
= −i |x|
(z − x)
√
(x+ 3)(x+ 1)(x− 1)(3 − x)
(since x > 0 in this case).) Therefore
lim
ε→0
∫
γ
h(w) dw = −2iπ · g(z). (6.9)
Comparing (6.5) and (6.9) we derive
f(z) =
z√
(z + 3)(z + 1)(z − 1)(z − 3)
, (6.10)
as required.
Lemma 6.1. The spectral measure of the operator 4M − 1 and the initial
vector δη, where M is the Markov operator on the one-ended Screier graph
corresponding to the orbit of the point η = 1∞ is the continuous measure
with the following density function:
p1(x) =
1
4π
√
(x+ 1)(x+ 3)
(x− 1)(3 − x)
, x ∈ [−3,−1] ∪ [1, 3].
Proof. The proof is similar to the proof of Lemma 5.1 with some modi-
fications. We need to prove that the Stieltjes transform of the measure
p1(x) dx is the function computed in section 4
m(z) = −1
4
(
1 −
√
(z + 1)(z + 3)
(z − 1)(z − 3)
)
=
2z
z2 − 4z + 3 +
√
z4 − 10z2 + 9
.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
268 The spectral measure of the Markov operator
Consider
I1(z) =
∫
γ
h1(w) dx, (6.11)
where
h1(w) =
1
(z − w)
√
(w + 1)(w + 3)
(w − 1)(w − 3)
. (6.12)
Then we follow exactly the same scheme as in the proof of Lemma 5.1.
The only difference is that the function h1(w) is not regular any more
at w = ∞, and that is why we need to calculate
∫
CR
h1(w) dw using the
residue of h1(w) at w = ∞. Using substitution w = 1
u we have
h1
(
1
u
)
=
1(
z − 1
u
)
√√√√√
(
1
u + 1
) (
1
u + 3
)
(
1
u − 1
) (
1
u − 3
)
=
1(
z − 1
u
)
√
(1 + u)(1 + 3u)
(1 − u)(1 − 3u)
=
u
(uz − 1)
√
(1 + u)(1 + 3u)
(1 − u)(1 − 3u)
.
Now
h1(w) dw = h1
(
1
u
)
d
(
1
u
)
= h1
(
1
u
)(
− 1
u2
)
du
= − 1
u(uz − 1)
√
(1 + u)(1 + 3u)
(1 − u)(1 − 3u)
du
Res h1
(
1
u
)
d
(
1
u
) ∣∣∣
u=0
= −
[
1
uz − 1
√
(1 + u)(1 + 3u)
(1 − u)(1 − 3u)
∣∣∣∣∣
∣∣∣∣
u=0
= 1.
Hence,
∫
CR
h1(w) dw = +2πi. Therefore,
∫
γ
h1(w) dw =
∫
CR
h1(w) dw−
∫
Cr
h1(w) dw = +2πi−
∫
Cr
h1(w) dw. (6.13)
Now
∫
Cr
h1(w) dw = −2πi · res h1(w)|w=z
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 269
= −2πi · (−1)
√
(w + 1)(w + 3)
(w − 1)(w − 3)
∣∣∣
w=z
= 2π
√
(z + 1)(z + 3)
(z − 1)(z − 3)
.
Hence,
I1(z) =
∫
γ
h1(w) dw = +2πi− 2πi
√
(z + 1)(z + 3)
(z − 1)(z − 3)
. (6.14)
On the other hand,
lim
ε→0
I1(z) = 2
−1∫
−3
1
(z − x)
i
√
−(x+ 1) ·
√
x+ 3
i
√
−(x− 1) · i
√
−(x− 3)
dx
+ 2
3∫
1
1
(z − x)
√
x+ 1 ·
√
x+ 3√
x− 1 · i
√
−(x− 3)
dx
= −2i
−1∫
−3
1
(z − x)
√(
x+ 1
x− 1
)(
x+ 3
3 − x
)
dx
+
3∫
1
1
(z − x)
√(
x+ 1
x− 1
)(
x+ 3
3 − x
)
dx
= −2i · 4πS1(z) = −8πim(z),
where m(z) is the Stieltjes transform of the measure µ1. Comparing the
last equation with (6.14) we obtain
+2πi− 2πi
√
(z + 1)(z + 3)
(z − 1)(z − 3)
= −8πim(z),
and hence,
m(z) = −1
4
+
1
4
√
(z + 1)(z + 3)
(z − 1)(z − 3)
= −1
4
[
1 −
√
(z + 1)(z + 3)
(z − 1)(z − 3)
]
(6.15)
as required.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
270 The spectral measure of the Markov operator
References
[Akh65] N. I. Akhiezer, The classical moment problem and some related questions
in analysis, Translated by N. Kemmer, Hafner Publishing Co., New York,
1965. MR MR0184042 (32 #1518)
[Ale72] S. V. Alešin, Finite automata and the Burnside problem for periodic groups,
Mat. Zametki 11 (1972), 319–328. MR MR0301107 (46 #265)
[Aus09] T. Austin, Rational group ring elements with kernels having irrational
dimension, (available at http://arxiv.org/abs/math.GR/0909.2360 ), 2009.
[BG00a] L. Bartholdi and R. I. Grigorchuk, On the spectrum of Hecke type operators
related to some fractal groups, Tr. Mat. Inst. Steklova 231 (2000), no. Din.
Sist., Avtom. i Beskon. Gruppy, 5–45. MR MR1841750 (2002d:37017)
[BG00b] Laurent Bartholdi and Rostislav I. Grigorchuk, Spectra of non-commutative
dynamical systems and graphs related to fractal groups, C. R. Acad. Sci.
Paris Sér. I Math. 331 (2000), no. 6, 429–434. MR MR1792481 (2001i:37012)
[BGK+07] Ye. V. Bondarenko, R. I. Grigorchuk, R.V. Kravchenko, Y. V. Muntyan,
V. V. Nekrashevich, D. M. Savchuk, and Z. Sunik, On classification of the
groups, which are generated by automatons with three states on alphabet with
two letters, and on some questions concerned with such groups, Naukovy
Visnyk Chernivetskogo Universytetu: Zbirnyk Naukovyh Prats 336-337
(2007).
[BGN03] Laurent Bartholdi, Rostislav Grigorchuk, and Volodymyr Nekrashevych,
From fractal groups to fractal sets, Fractals in Graz 2001, Trends Math.,
Birkhäuser, Basel, 2003, pp. 25–118. MR MR2091700
[Bri53] L. Brillouin, Wave propagation in periodic structures. Electric filters and
crystal lattices, Dover Publications Inc., New York, N. Y., 1953, 2d ed. MR
MR0052978 (14,704a)
[Gau84] Walter Gautschi, On some orthogonal polynomials of interest in theoretical
chemistry, BIT 24 (1984), no. 4, 473–483. MR MR764820 (86d:65030)
[GL02] Rostislav I. Grigorchuk and Igor Lysenok, Burnside problem, The Consice
handbook of algebra, A.V. Mikhalev and Gunter F. Pilz (eds.), Kluwer
Academic Publishers, 2002, pp. 111–115.
[GLSŻ00] Rostislav I. Grigorchuk, Peter Linnell, Thomas Schick, and Andrzej Żuk,
On a question of Atiyah, C. R. Acad. Sci. Paris Sér. I Math. 331 (2000),
no. 9, 663–668. MR MR1797748 (2001m:57050)
[GN07] Rostislav Grigorchuk and Volodymyr Nekrashevych, Self-similar groups,
operator algebras and Schur complement, J. Mod. Dyn. 1 (2007), no. 3,
323–370. MR MR2318495
[GNS00a] R. I. Grigorchuk, V. V. Nekrashevich, and V. I. Sushchanskĭı, Automata,
dynamical systems, and groups, Tr. Mat. Inst. Steklova 231 (2000), no. Din.
Sist., Avtom. i Beskon. Gruppy, 134–214. MR MR1841755 (2002m:37016)
[GNS00b] , Automata, dynamical systems, and infinite groups, Tr. Mat. Inst.
Steklova 231 (2000), no. Din. Sist., Avtom. i Beskon. Gruppy, 134–214. MR
MR1841755 (2002m:37016)
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
R. I. Grigorchuk, Ya. S. Krylyuk 271
[Gol64] E. S. Golod, On nil-algebras and finitely approximable p-groups, Izv. Akad.
Nauk SSSR Ser. Mat. 28 (1964), 273–276. MR MR0161878 (28 #5082)
[Gra09] I. Grabowski, On the atiyah problem for the lamplighter groups, (available
at http://arxiv.org/abs/math.GR/1009.0229 ), 2009.
[Gri80] R. I. Grigorčuk, On Burnside’s problem on periodic groups, Funktsional.
Anal. i Prilozhen. 14 (1980), no. 1, 53–54. MR MR565099 (81m:20045)
[Gri83] R. I. Grigorchuk, On the Milnor problem of group growth, Dokl. Akad. Nauk
SSSR 271 (1983), no. 1, 30–33. MR MR712546 (85g:20042)
[Gri84] , Degrees of growth of finitely generated groups and the theory of
invariant means, Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), no. 5, 939–985.
MR MR764305 (86h:20041)
[Gri88] , Semigroups with cancellations of degree growth, Mat. Zametki 43
(1988), no. 3, 305–319, 428. MR MR941053 (89f:20065)
[Gri00a] , Branch groups, Mat. Zametki 67 (2000), no. 6, 852–858. MR
MR1820639 (2001i:20057)
[Gri00b] , Just infinite branch groups, New horizons in pro-p groups, Progr.
Math., vol. 184, Birkhäuser Boston, Boston, MA, 2000, pp. 121–179. MR
MR1765119 (2002f:20044)
[Gri05] Rostislav Grigorchuk, Solved and unsolved problems around one group,
Infinite groups: geometric, combinatorial and dynamical aspects, Progr.
Math., vol. 248, Birkhäuser, Basel, 2005, pp. 117–218. MR MR2195454
[Gri11] R. I. Grigorchuk, Some topics of group actions on rooted trees, The Pro-
ceedings of the Steklov Institute of Math. 273 (2011), 64–175.
[GŠ06] Rostislav Grigorchuk and Zoran Šuniḱ, Asymptotic aspects of Schreier graphs
and Hanoi Towers groups, C. R. Math. Acad. Sci. Paris 342 (2006), no. 8,
545–550. MR MR2217913 (2006k:20048)
[GŠ07] , Self-similarity and branching in group theory, Groups St. Andrews
2005, I, London Math. Soc. Lecture Note Ser., vol. 339, Cambridge Univ.
Press, Cambridge, 2007, pp. 36–95.
[GSŠ07a] Rostislav Grigorchuk, Dmytro Savchuk, and Zoran Šunić, The spectral prob-
lem, substitutions and iterated monodromy, Probability and mathematical
physics, CRM Proc. Lecture Notes, vol. 42, Amer. Math. Soc., Providence,
RI, 2007, pp. 225–248. MR 2352271 (2008h:20040)
[GSŠ07b] Rostislav Grigorchuk, Dmytro Savchuk, and Zoran Šuniḱ, The spectral prob-
lem, substitutions and iterated monodromy, Probability and Mathematical
Physics, A Volume in Honor of Stanislav Molchanov, CRM Proceedings
and Lecture Notes, vol. 42, American Mathematical Society, Providence,
Rhode Island USA, 2007, pp. 225–248.
[GŻ99] Rostislav I. Grigorchuk and Andrzej Żuk, On the asymptotic spectrum of
random walks on infinite families of graphs, Random walks and discrete
potential theory (Cortona, 1997), Sympos. Math., XXXIX, Cambridge Univ.
Press, Cambridge, 1999, pp. 188–204. MR MR1802431 (2002e:60118)
[GŻ01] , The lamplighter group as a group generated by a 2-state automa-
ton, and its spectrum, Geom. Dedicata 87 (2001), no. 1-3, 209–244. MR
MR1866850 (2002j:60009)
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
272 The spectral measure of the Markov operator
[GŻ04] , The Ihara zeta function of infinite graphs, the KNS spectral measure
and integrable maps, Random walks and geometry, Walter de Gruyter GmbH
& Co. KG, Berlin, 2004, pp. 141–180. MR MR2087782
[Hoř63] J. Hořeiš, Transformations defined by finite automata (in Russian), Prob-
lemy Kibernetiki 9 (1963), 23–26.
[Kes59] Harry Kesten, Symmetric random walks on groups, Trans. Amer. Math.
Soc. 92 (1959), 336–354. MR MR0109367 (22 #253)
[LW10] F. Lehner and S. Wagner, Free lamplighter groups and a question of atiyah,
(available at http://arxiv.org/abs/math.GR/1005.2347 ), 2010.
[Nek05] Volodymyr Nekrashevych, Self-similar groups, Mathematical Surveys and
Monographs, vol. 117, American Mathematical Society, Providence, RI,
2005. MR MR2162164 (2006e:20047)
[PSZ10] M. Pichot, T. Schick, and A. Zuk, Closed manifolds with transcendental
l2-betti numbers, (available at http://arxiv.org/abs/math.GR/1005.1147 ),
2010.
[Ser97] Jean-Pierre Serre, Répartition asymptotique des valeurs propres de
l’opérateur de Hecke Tp, J. Amer. Math. Soc. 10 (1997), no. 1, 75–102. MR
MR1396897 (97h:11048)
[vN29] John von Neumann, Zur allgemeinen Theorie des Masses, Fund. Math. 13
(1929), 73–116 and 333, = Collected works, vol. I, pages 599–643.
[Whe84] John C. Wheeler, Modified moments and continued fraction coefficients
for the diatomic linear chain, The Journal of Chemical Physics 80 (1984),
no. 1, 472–476.
Contact information
R. I. Grigorchuk Department of Mathematics, Mailstop 3368
Texas A&M University College Station, TX
77843-3368, USA
E-Mail: grigorch@math.tamu.edu
Ya. S. Krylyuk Mathematics Department, De Anza College,
21250 Stevens Creek Blvd, Cupertino, CA 95014,
USA
Received by the editors: 03.04.2012
and in final form 03.04.2012.
R. I. Grigorchuk, Ya. S. Krylyuk
|