ON THE SPECTRUM OF HECKE TYPE OPERATORS RELATED TO SOME FRACTAL GROUPS

LAURENT BARTHOLDI AND ROSTISLAV I. GRIGORCHUK

Abstract. We give the first example of a connected 4-regular graph whose Laplace operator’s spectrum is a Cantor set, as well as several other computations of spectra following a common “finite approximation” method. These spectra are simple transforms of the Julia sets associated to some quadratic maps. The graphs involved are Schreier graphs of fractal groups of intermediate growth, and are also “substitutional graphs”. We also formulate our results in terms of Hecke type operators related to some irreducible quasi-regular representations of fractal groups and in terms of the Markovian operator associated to noncommutative dynamical systems via which these fractal groups were originally defined in [Gri80].

In the computations we performed, the self-similarity of the groups is reflected in the self-similarity of some operators; they are approximated by finite counterparts whose spectrum is computed by an ad hoc factorization process.

1. Introduction

The Hecke, Markov, and Laplace operators occur in various guises throughout mathematics. We start by a review of their more common appearances.

1.1. Discrete Laplacian and Hecke type Operators. Let G = (V, E) be a locally finite graph: there are maps α, ω : E → V giving the extremities of edges, and every vertex v ∈ V has finite degree deg v = |{e ∈ E| α(e) = v}|. Therefore all edges are oriented, and G may have loops (α(e) = ω(e)) and multiple edges. The discrete Laplace operator of G is the operator Δ = 1 − M on ℓ^{2}(V, deg), where M is the “adjacency” or Markovian operator

(Mf)(v) = \frac{1}{deg v} ∑_{e∈E: α(e)=v} f(ω(e)).

The theory of discrete Laplace operators Δ has a long history, and is a popular topic of contemporary mathematics [CDS79, Woe94]. In the context of random walks on graphs, one usually considers the Markovian operator M rather than Δ: if e_{v} be

Date: November 3, 1999. 1991 Mathematics Subject Classification. 20F50 (Periodic groups; locally finite groups), 20C12 (Integral representations of infinite groups), 11F25 (Hecke-Petersson operators), 43A65 (Representations of groups) .

Key words and phrases. Spectrum; Laplace Operator; Hecke Type Operator; Markov Operator; Noncommutative Dynamical System; Quasi-regular Representation; Fractal Group; Branch Group; Finite Automaton; Substitutional Graph.

The second author wishes to express his thanks to the “Swiss National Science Foundation” and the Max-Planck Institute in Bonn for their support.

the Dirac delta function at the vertex v, then ⟨M^{n}e_{v}|e_{w}⟩ is the probability of a random walk starting at v to reach w in n steps. If the random walk is symmetric, then M is a self-adjoint operator and its spectrum lies in [−1, 1]. The spectral properties of M contain valuable information for the theory of random walks and discrete potential, graph theory, abstract harmonic analysis, the theory of operator algebras, etc. For instance, a theorem by Harry Kesten [Kes59], generalized by different mathematicians (see [Woe94] and [CGH99] with its bibliography) asserts that G is amenable if and only if 1 is in the spectrum of M. Note that the random walk need not be simple (probabilities of moving in different directions may be different); a Markovian operator can still be associated to the walk. Let us finally mention a more general setting, developed these last years [Nov97]: the (discrete) Schrödinger operators Δ + P, where P is diagonal, and the coefficients of Δ may depend on the vertex they correspond to.

The theory of Hecke type operators was developed in parallel: if π : G → U(H) is a unitary representation of a finitely generated group G given with a symmetric generating system S = {s_{1}, …, s_{m}} = S^{−1} in a Hilbert space H, then one associates to π a self-adjoint operator H on H:

H = ∑_{i=1}^{m} p(i)π(s_{i}),

for some p(i) ∈ ℂ. The most important choice is p(i) = \frac{1}{m} for all i ∈ \{1, …, m\}; we shall restrict to this choice in the sequel, and assume, when no weight is given, that this one is used.

Operators of Hecke type play an important role in mathematical physics [Con94], Arakelov theory in number theory (see [Li96], [Ser97] and [Ser95] for the connection between number theory and operators), and Ramanujan graphs [Lub94]. The group-theoretical content of H, mainly in the case of the regular representation, was studied by Pierre de la Harpe, A. Guyan Robertson and Alain Valette in [HRV93a, HRV93b], and in many other papers — see the bibliography in [Woe94].

1.2. Spectra of Noncommutative Dynamical Systems. Let T be an invertible measure-preserving transformation of a measure space (X, μ), and let A be the corresponding unitary operator in L^{2}(X, μ), given by (Af)(x) = f(T^{−1}x). By the spectrum of the dynamical system one usually means the spectrum of the operator A, or, as is almost the same, the spectrum of the self-adjoint operator A + A^{−1}. These last spectra are in correspondence through the map z ↦ z + z^{−1}. If T is aperiodic, then spec(A + A^{−1}) = [−1, 1].

By a noncommutative dynamical system we mean a collection S of invertible measure-class-preserving transformations on a measure space (X, μ), that do not necessarily commute. Let G be the group generated by S. It has a natural unitary representation π in (L^{2}(X, μ)) given by

(π(g)f)(x) = \sqrt{𝔤(x)}f(g^{−1}x),

where 𝔤(x) = dgμ(x)/dμ(x) is the Radon-Nikodým derivative. The spectrum of the dynamical system S is the spectrum of the Hecke type operator associated to G, S ∪ S^{−1} and π. In case |S| = 1, this definition reduces to the previous, classical one.

1.3. Examples. One of the most famous operators of Hecke type is the Harper-Mathieu-Peierls operator H_{λ} on ℓ^{2}(ℤ) acting on infinite sequences f : ℤ → ℂ by

(H_{λ}(f)) (n) = f(n − 1) + f(n + 1) + (2 cos λn)f(n),

for any λ ∈ ℝ. These H_{λ} are the Hecke type operators associated to the Heisenberg group

\{(\begin{matrix}1 & m & p \\ & 1 & n \\ & & 1 \end{matrix})| m, n, p ∈ ℤ\} ≅ ⟨a, b, c| [a, b] = c, [a, c] = [b, c] = 1⟩

and its representation π_{λ} in ℓ^{2}(ℤ), where π_{λ}(a) acts by translation: [π_{λ}(a)](f)(n) = f(n − 1), and π_{λ}(b) acts by pointwise multiplication with the function e^{iλn}, namely [π_{λ}(b)](f)(n) = e^{iλn}f(n).

The Harper operator is the operator related to the Quantum Hall effect, and originally arose in connection with the two-dimensional lattice. One can start from any Cayley graph, and construct a corresponding Harper operator, which would be the discrete analogue of the magnetic Laplacian [CHMM98].

The spectral properties of this operator were thoroughly investigated; if λ is a Liouville number, the spectrum of H_{λ} is a Cantor set [BS82]. We note that H_{λ} is a Schrödinger operator on the one-dimensional lattice. By Fourier transform, it can be realized as an element of the cross product C^{∗}-algebra R_{λ} ⋉ C(𝕊^{1}), where R_{λ} is the dynamical system generated by an angle-λ rotation on 𝕊^{1} and C(𝕊^{1}) denotes the algebra of continuous functions on the circle.

Another example was studied by David Kazhdan [Kaž65]. Let α and β be two noncommuting rotations in the plane ℝ^{2}. They generate a group G with a unitary action π on L^{2}(ℝ^{2}). Kazhdan studies the operator M = π(α) + π(α^{−1}) + π(β)+π(β^{−1}) and shows that its Fourier transform decomposes as a direct integral of operators acting on functions on the circle. Each of these is an element of R_{λ} ⋉ B(𝕊^{1}), where B(𝕊^{1}) denotes the bounded functions on the circle, and happens to be a Schrödinger operator; spectral properties of these operators are then used to show that the orbits of G in ℝ^{2} are uniformly distributed.

1.4. Main Results. We produce examples of operators of Hecke type with Cantor set spectrum, but where additionally the representations π involved are quasiregular. This produces graphs whose Laplace operators have totally discontinuous spectrum, namely the associated Schreier graphs. Our main results read:

Theorem 1.1. 1. There is a connected 4-regular graph of polynomial growth, which is a Schreier graph of a group of intermediate growth, and whose Laplacian’s spectrum is a Cantor set.

2. There is a connected 4-regular graph of polynomial growth, which is a Schreier graph of a group of intermediate growth, and whose Laplacian’s spectrum is the union of a Cantor set K and a countable set P of isolated points whose accumulation set is K.

3. There are noncommutative dynamical systems generated by 2 transformations whose spectrum are the same as in the above two points.

4. The above spectra are calculated explicitly. The Cantor set K is of the form F (J) where F is a simple algebraic function and J is the Julia set of a quadratic map z ↦ z^{2} − λ, where λ = 45/16 in the first case and λ = 6 in the second case. J is the set of points of the form

±\sqrt{λ ± \sqrt{λ ± \sqrt{λ ± \sqrt{…}}}}.

To the best of our knowledge, these are the first examples of graphs of constant vertex degree whose spectrum is totally disconnected. There are, however, examples of Schrödinger operators on ℤ (or ℝ) with nowhere dense spectrum; they are obtained as Harper operators (as mentioned above) or following a result by Jürgen Moser [Mos81].

There are also examples of random walks on non-regular graphs, but with vertex degrees 1 or 3, whose spectrum is the union of a countable set and a Cantor set of null Lebesgue measure [Mal95].

Similarly we produce Hecke type operators of quasi-regular representations that have the same spectra as above. These are probably the first examples of quasiregular representations of virtually torsion-free groups with totally discontinuous spectrum; at least, the representations π_{λ} of the Heisenberg group are not quasiregular, but come from the cross-product construction, which is often used to produce interesting examples. In the sequel we produce interesting examples of spectra using purely non-commutative dynamical systems and associated methods.

The graphs mentioned in Theorem 1.1 are Schreier graphs of some fractal groups. They are of polynomial growth and have a clear “fractal” appearance; see Figure 10. By a fractal group we mean a group which acts on a regular rooted tree T , such that this action has some self-similar properties; this notion is very much related to that of branch group introduced in [Gri98]. The Schreier graphs S(G, P, S) are defined in 3.1; in our examples we take for P the stabilizer st_{G}(e) of an infinite ray starting at the root of T , i.e. an element of the boundary ∂T .

The parabolic subgroups P = st_{G}(e) have the remarkable property of being weakly maximal: [G : P] = ∞ but [G : L] < ∞ for all L ≩ P. The corresponding quasi-regular representations ρ_{G/P} are irreducible, and ⋂_{g∈G} P^{g} = 1. We thus have an important family of faithful irreducible representations of G, that deserves further investigation.

The first example of group of fractal type was constructed in [Gri80] as an example of infinite torsion 2-group; it was described as a set of measure-preserving transformations of the interval [0, 1], but can equivalently be described by its action on a rooted tree (the binary expansion of a real in [0, 1] giving a path in the rooted binary tree). Later many new examples of this sort appeared [GS83b, Gri83, BG98]. It then became clear that the study of these groups via their tree action was most fruitful and led to interesting ideas and results; for a survey see [Gri98]; and for an introduction to the first example, G, see [Har, CMS98].

Among the five groups we consider, two (Γ and \overline{Γ}) are virtually torsion-free, and have a totally disconnected spectrum. The existence of such groups lends some hope to the existence of torsion-free fractal groups whose Laplace operator has a totally disconnected spectrum, or at least a gap in the spectrum. Such an example would provide a counterexample to the Kaplansky-Kadison conjecture on idempotents (that implies that the spectrum of the Laplace operator related to the regular representation is connected), and to the Baum-Connes conjecture [Val89]. Note that if such a group existed, it would be non-amenable [HK97].

The method used in the computations is the following: we compute explicitly the spectrum of the finite graph S(G, P_{n}, S), where P_{n} is the stabilizer of the rightmost vertex in the nth row of the tree T . Then some arguments, coming from [Lub95, GŻ97, MV98] but adapted to our goals, are used to obtain the spectrum of the infinite graphs from the finite spectra.

1.5. Notation. We assume all groups act on the left on sets, and write g^{h} = hgh^{−1} and [g, h] = ghg^{−1}h^{−1}. We also write ⟨S⟩ and ⟨S⟩^{G} for the subgroup and normal subgroup of G generated by S. The regular representation of G in ℓ^{2}(G) is written ρ_{G}, and the quasi-regular representation of G in ℓ^{2}(G/H) is written ρ_{G/H}. The symmetric group on a set S of cardinality n is written 𝔖_{S} or 𝔖_{n}.

1.6. Guide to Quick Reading. We present in this paper five computations of spectra related to groups; however, the reader interested solely in examples of graphs with Cantor-set spectrum may wish to skip the group-theoretic discussion. In this case the sections 4.3 and 5 should describe the construction in a fairly self-contained manner.

2. Groups acting on rooted trees

The groups we shall consider will all be subgroups of the group Aut(T ) of automorphisms of a regular rooted tree T . Let Σ be a finite alphabet. The vertex set of the tree 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 the empty sequence ∅, and the children of σ are all the σs, for s ∈ Σ. We suppose Σ = ℤ/dℤ, with the operation \overline{s} = s + 1 mod d. Let a, called the rooted automorphism of T_{Σ}, be the automorphism of T_{Σ} defined by a(sσ) = \overline{s}σ: it acts nontrivially on the first symbol only, and geometrically is realized as a cyclic permutation of the d subtrees just below the root.

Fix some Σ and let A = Aut(T_{Σ}). For any subgroup G < A, let st_{G}(σ) denote the subgroup of G consisting of the automorphisms that fix the sequence σ, and st_{G}(n) denote the subgroup of G consisting of the automorphisms that fix all sequences of length n:

st_{G}(σ) = {g ∈ G| gσ = σ}, st_{G}(n) = ⋂_{σ∈Σ^{n}} st_{G}(σ).

The st_{G}(n) are normal subgroups of finite index of G; in particular st_{G}(1) is of index at most d!. Let G_{n} be the quotient G/ st_{G}(n). If g ∈ A is an automorphism fixing the sequence σ, we denote by g_{|σ} the element of A corresponding to the restriction to sequences starting by σ:

σg_{|σ}(τ) = g(στ).

As the subtree starting from any vertex is isomorphic to the initial tree T_{Σ}, we obtain this way a map

ϕ : \begin{cases}st_{A}(1) → A^{Σ} \\ h ↦ (h_{|0}, …, h_{|d−1}) \end{cases} (1)

which is an embedding.

Definition 2.1. A subgroup G < A is level-transitive if the action of G on Σ^{n} is transitive for all n ∈ ℕ. We shall always implicitly make that assumption.

G is fractal if for every vertex σ of T_{Σ} one has st_{G}(σ)_{|σ} ≅ G, where the isomorphism is given by identification of T_{Σ} with its subtree rooted at σ.

For a sequence σ and an automorphism g ∈ A, we denote by g^{σ} the element of A acting as g on the sequences starting by σ, and trivially on the others:

g^{σ}(στ) = σg(τ), g^{σ}(τ) = τ if τ doesn’t start by σ.

Let G < A be a group acting faithfully, and transitively on each level, on a rooted tree T_{Σ}. The rigid stabilizer of σ is rist_{G}(σ) = {g^{σ}| g ∈ G} ∩ G. We say G has infinite rigid stabilizers if all the rist_{G}(σ) are infinite.

Definition 2.2. 1. G is a regular branch group if it has a finite-index subgroup K < st_{G}(1) such that

K^{Σ} < ϕ(K).

2. A subgroup G < A is a branch group if for every n ≥ 1 there exists a subgroup L_{n} < A and an embedding

L_{n} × ⋯ × L_{n} ↪ st_{G}(n),

where the direct product is indexed by Σ^{n}, the injection is given on each factor by (ℓ, σ) ↦ ℓ^{σ}, and the image is normal of finite index in st_{G}(n).

3. G is a weak branch group if all of its rigid stabilizers rist_{G}(σ) are infinite.

If G is fractal, one has for all n an embedding st_{G}(n) < G^{d^{n}}. Note that the definition of a branch group admits an even more general setting — see [Gri98]. Four of our examples will be regular branch groups, and the last one will not be a branch, but rather a weak branch group. The following lemma shows that, for fractal groups, 1 implies 2 implies 3 in Definition 2.2.

Lemma 2.3. If G is a fractal, regular branch group, then it is a branch group. If G is a branch group, then it is a weak branch group.

Proof. Assume G is a regular branch group on its subgroup K. Define L_{n} = K for all n. Clearly st_{G}(n) contains the direct product L_{n}^{Σ^{n}}, and it is of finite index in G^{Σ^{n}}, so all the more of finite index in st_{G}(n). The second implication holds because branch groups are infinite, and ‘finite index in infinite group’ is stronger than ‘infinite’.

In the sequel we shall be concerned with subgroups G of A that are finitely generated, fractal, and contain the rooted automorphism a. These groups will be naturally equipped with the restriction of the map ϕ defined in (1), a descending sequence of normal subgroups H_{n} = st_{G}(n) and an approximating sequence of finite quotients G_{n} = G/H_{n}. These quotients can be seen as subgroups of the symmetric group 𝔖_{Σ^{n}} on Σ^{n}. More details on all of these groups and their subgroups appear in [BG98].

2.1. Dynamical Systems. Assume as above that a group G generated by a set S acts on the d-regular rooted tree T = {0, …, d − 1}^{∗}. Then G acts naturally on the boundary ∂T = {0, …, d − 1}^{ℕ}, and this action preserves the uniform Bernoulli measure ν on the compact space ∂T . We associate thus a dynamical system (G, S, ∂T , ν) to the group G.

This dynamical system is naturally isomorphic to a dynamical system (G, S, [0, 1], m), where m is the Lebesgue measure, and G (generated by S) acts on [0, 1] by measurepreserving transformations in the following way: let g ∈ G, and γ ∈ [0, 1] a d-adic irrational 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].

The orbits of G on ∂T can be made explicit as follows:

Definition 2.4. Two infinite sequences σ, τ : ℕ → Σ are confinal if there is an N ∈ ℕ such that σ_{n} = τ_{n} for all n ≥ N.

Confinality is an equivalence relation, and equivalence classes are called confinality classes.

Proposition 2.5. Let G be a group acting on a regular rooted tree T , and assume that for any generator g ∈ G and infinite sequence σ, the sequences σ and gσ differ only in finitely many places. Then the confinality classes of the action of G on ∂T are unions of orbits. If moreover st_{G}(σ) contains the rooted automorphism a for all σ ∈ T , the orbits of the action are confinality classes.

The dynamics of the actions of a group on the boundary of a tree from the point of view of confinality are investigated in more detail in in [NS99]. We remark that the five example groups—G, G̃, Γ, \overline{Γ}, \overline{\overline{Γ}}—we shall consider satisfy the conditions of the proposition above.

2.2. Growth of Groups and Parabolic Subgroups. We recall some facts about word-growth of groups and sets on which they act.

Definition 2.6. Let G be a group generated by a finite set S, let X be a set upon which G acts transitively, and choose x ∈ X. The growth of X is the function γ : ℕ → ℕ defined by

γ(n) = |{gx ∈ X| |g| ≤ n}|,

where |g| denotes the minimal length of g when written as a word over S. By the growth of G we mean the growth of the action of G on itself by left-multiplication.

Given two functions f, g : ℕ → ℕ, we write f ⪯ g if there is a constant C ∈ ℕ such that f(n) < Cg(Cn + C) + C for all n ∈ ℕ, and f ∼ g if f ⪯ g and g ⪯ f.

The equivalence class of the growth of X is independent of the choice of S and of x.

X is of polynomial growth if γ(n) ⪯ n^{d} for some d. It is of exponential growth if γ(n) ⪰ e^{n}. It is of intermediate growth in the remaining cases. This trichotomy does not depend on the choice of x.

Assume now that G is a group acting on the tree Σ^{∗}, and that a subset S ⊂ G is given.

Definition 2.7. The portrait of g ∈ G with respect to S is a subtree of Σ^{∗}, with inner vertices labeled by 𝔖_{Σ} and leaf vertices labeled by S ∪ {1}. It is defined recursively as follows: if g ∈ S ∪ {1}, the portrait of g is the subtree reduced to the root vertex, labeled by g itself. Otherwise, let α ∈ 𝔖_{Σ} be the permutation of the top branches of Σ^{∗} such that gα^{−1} ∈ st_{G}(1); let (g_{0}, …, g_{d−1}) = ϕ(gα^{−1}) and let T_{i} be the portrait of g_{i}. Then the portrait of g is the subtree of Σ^{∗} with α labeling the root vertex and subtrees T_{0}, …, T_{d−1} connected to the root.

The depth of g ∈ G is the height (length of a maximal path starting at the root vertex) ∂(g) ∈ ℕ ∪ {∞} of the portrait of g.

Therefore the depth of g is finite if and only if the portrait of G is finite. Both are finite for all groups we consider in this paper, and the depth may be estimated using the following lemma:

Lemma 2.8. Assume S generates G and ϕ : g ↦ (g_{1}, …, g_{d}) defined in (1) has the property that |g_{i}| < |g| for all i. Then every g ∈ G has a finite portrait. If moreover there are constants λ, μ with μ/(1 − λ) < 2 such that |g_{i}| ≤ λ|g| + μ for all i, then asymptotically when |g| → ∞

∂(g) ≤ log_{1/λ} |g|.

Proof. Consider the ‘level’ function

F (n) = max_{|g|<n} ∂(g).

Then F is increasing, and by assumption F (2) = 0, F (n) ≤ F (λn + μ) + 1. It then follows that

F (n) ≤ F (λn + μ) + 1 ≤ ⋯ ≤ F (λ^{k}n + λ^{k−1}μ + ⋯ + λμ + μ) + k;

let us take for k a natural number satisfying λ^{k}n + λ^{k−1}μ + ⋯ + λμ + μ ≤ 2, for instance

k = ⌈log_{λ} \frac{2 − μ/(1 − λ)}{n − mu/(1 − λ)}⌉ ,

where ⌈x⌉ is the least integer greater than x. The result follows, because then F (n) ≤ k and k ∼ log_{1/λ} n.

Scholium 2.9. For all groups considered in this paper, we have |g_{i}| ≤ \frac{1}{2}|g| + \frac{1}{2} for their natural generating systems, as can be checked on the tables describing ϕ. As a consequence, they all satisfy ∂(g) ≾ log_{2} |g|.

Definition 2.10. Let T = Σ^{∗} be a rooted tree. A ray e in T is an infinite geodesic starting at the root of T , or equivalently an element of ∂T = Σ^{ℕ}.

Let G < A and e be a ray. The associated parabolic subgroup is st_{G}(e) = ∩_{n≥0} st_{G}(e_{n}), where e_{n} is the length-n prefix of e.

Assume that G satisfies the conditions of Lemma 2.8. Then we have the

Proposition 2.11. Let G < A satisfy the conditions of Proposition 2.5 and Lemma 2.8 (for the constant λ), and let P be a parabolic subgroup. Then G/P, as a G-set, is of polynomial growth of degree at most log_{1/λ}(d). If moreover G is level-transitive, then G/P ’s asymptotical growth is polynomial of degree log_{1/λ}(d).

Proof. Suppose that P = st_{G}(e). Then G/P can be identified with the G-orbit of e, and, by Proposition 2.5, with the set of all infinite sequences over Σ that eventually coincide with e. If ∂(g) < k, it sends the infinite sequence e to one of the d^{k} sequences in Σ^{k}e_{k} …; thus the image of e under the set of elements of depth at most k is of cardinality bounded by d^{k}. The image of e under the set of elements of length at most n is then asymptotically bounded by d^{log_{1/λ}(n)} = n^{log_{1/λ}(d)}, by Lemma 2.8.

We now recall some facts on commensurators:

Definition 2.12. The commensurator of a subgroup H of G is

comm_{G}(H) = {g ∈ G| H ∩ H^{g} is of finite index in H and H^{g}}.

Equivalently, letting H act on the left on the cosets {gH},

comm_{G}(H) = {g ∈ G| H · (gH) and H · (g^{−1}H) are finite orbits}.

Proposition 2.13 ([BG98]). Let G be a weak branch group and let P be a parabolic subgroup. Then comm_{G}(P) = P.

Theorem 2.14 (Mackey [Mac76, BH97]). Let P < G be any subgroup inclusion. Then the quasi-regular representation ρ_{G/P} is irreducible if and only if comm_{G}(P) = P.

Therefore, for all weak branch groups ρ_{G/P} is irreducible.

The following lemma is well known:

Lemma 2.15. Let H < G be a subgroup of finite index. Then the orbits of H on G/H, the double cosets HgH < G and the irreducible components of the G-space ℓ^{2}(G/H) are all in bijection.

Therefore, the orbits of P_{n} = P · st_{G}(n) on Σ^{n} are in bijection with the decomposition of ρ_{G/P_{n}} in irreducible subrepresentations.

2.3. Groups and Finite Automata. There are various uses of automata in group theory, most notably as word acceptors, where the automata recognize some words as group elements and perform operations on these words [ECH^{+}92]; and as transducers or sequential machines (see [Eil74, Chapter XI] or [GC71]), where the automata themselves are the elements of the group, and are distinguished by the transformation they perform on their input. The former use gives rise to the theory of automatic groups; we propose to call the latter automata groups. The automata they are built with are called Mealy machines or Moore machines (see [Glu61] or [Bra84, page 109]).

We present a restricted definition of finite transducers. In the standard terminology, they would be called invertible transducers.

Definition 2.16. Let Σ be a finite alphabet. A finite transducer on Σ is a finite directed graph G = (V, E), a labeling λ : E → Σ of the edges such that for each vertex v ∈ V the restriction of λ is a bijection between {e ∈ E| α(e) = v} and Σ, and a labeling τ : V → 𝔖_{Σ} of the nodes (called states) by the symmetric group on Σ.

An initial transducer G_{q} is a finite transducer G with a distinguished initial state q ∈ V.

Let G be a finite transducer, and {G_{q}}_{q∈V} be the set of its initial transducers. Each G_{q} defines an automorphism \overline{G_{q}} of the rooted tree T_{Σ} as follows: let σ = σ_{0} … σ_{n} be a vertex of T . Let e be the edge of G_{q} labeled σ_{0}. Define recursively

\overline{G_{q}}(σ_{0} … σ_{n}) = τ(q)(σ_{0})\overline{G_{ω(e)}}(σ_{1} … σ_{n}).

We shall call two initial transducers G_{q} and G′_{q′} equivalent if their actions \overline{G_{q}} and \overline{G′_{q′}} on Σ^{∗} are the same. Every initial transducer is equivalent to a unique transducer that is minimal with respect to its number of nodes [Eil74, Chapter XII, Theorem 4.1].

Define now G(G) as the group generated by the \overline{G_{q}}, where q ranges over the set of states of G. We call such a group an automata group. The following fact is well known, and dates back to Jiří Hořejš in the early 60’s [Hoř63]:

Proposition 2.17. Let G_{q} and G′_{q′} be finite initial transducers on the same alphabet

Σ. Then \overline{G_{q}}^{−1} and \overline{G_{q}} ∘ \overline{G′_{q′}} can be represented as finite initial transducers.

In general different transducers can generate isomorphic groups. For instance, consider the three-vertex transducer in the middle of Figure 2. The group it generates is isomorphic (and even conjugate in A) to the one generated by the following two-state transducer G on Σ = {0, 1, 2}, because the elements t̃, ã satisfy the same recursions as t, a (see Subsection 3.3):

[figure: 1; t̃; ε; ã; 0, 1; 2; Σ]

Here ε is the cycle (0, 1, 2) ∈ 𝔖_{3}. The actions of Gt̃ and Gã are as follows:

Gt̃(2 … 2σ_{m} … σ_{n}) = 2 … 2ε(σ_{m}) … ε(σ_{n})  when σ_{m} ≠ 2,
Gã(σ_{0} … σ_{n}) = ε(σ_{0}) … ε(σ_{n}).

2.4. The Group G. We give here some basic facts about the first of our examples, the group G [Gri80, Gri84]. We take Σ = {0, 1}. Recall a is the automorphism permuting the top two branches of T_{2}. Let recursively b be the automorphism

[figure: 1; ε; a; 1; d; 1; b; 1; c; 0; 0, 1; 0; 1; 0; 1; 1; 0, 1; 1; ε; a; 1; d̃; 1; b̃; 1; c̃; 0; 0, 1; 0; 1; 0; 1; 1; 0, 1]

Figure 1. The Finite Transducers for G and G̃

acting as a on the right branch and c on the left, c be the automorphism acting as a on the right branch and d on the left, and d be the automorphism acting as 1 on the right branch and b on the left. In formulæ,

b(0xσ) = 0\overline{x}σ,  b(1σ) = 1c(σ),
c(0xσ) = 0\overline{x}σ,  c(1σ) = 1d(σ),
d(0xσ) = 0xσ,  d(1σ) = 1b(σ).

G is the group generated by {a, b, c, d}. It is readily checked that these generators are of order 2 and that {1, b, c, d} constitutes a Klein group; one of the generators {b, c, d} can thus be omitted.

G was originally defined in [Gri80] as the following dynamical system acting on the interval [0, 1] from which rational dyadic points are removed:

a(z) = \begin{cases}z + \frac{1}{2} & if z < \frac{1}{2} \\ z − \frac{1}{2} & if z ≥ \frac{1}{2}, \end{cases}

b(z) =  a  a 1 a.._{0}  _{\frac{1}{2}}  _{\frac{3}{4}}  _{\frac{7}{8}}  _{1}
c(z) =  a  1 a a..
d(z) =  1  a a 1..

Here the intervals represent [0, 1], with either a or 1 (the identity transformation) acting on the described subintervals in a similar way as a or 1 act on [0, 1]. Finally, G is also an automata group, see the left graph in Figure 1 (the trivial and nontrivial elements of 𝔖_{2} are represented as 1 and ϵ and are used to label states).

Recall the map ϕ defined in (1); it restricts to an embedding ϕ : H → G × G given by

ϕ : \begin{cases}b → (a, c), b^{a} → (c, a) \\ c → (a, d), c^{a} → (d, a) \\ d → (1, b), d^{a} → (b, 1), \end{cases} (2)

where H = st_{G}(1) = ⟨b, c, d⟩^{G} is an index-2 subgroup. Consider also K = ⟨(ab)^{2}⟩^{G}. Let e be the infinite sequence 0^{∞}; set P_{n} = st_{G}(0^{n}) and P = st_{G}(e) = ∩_{n≥0}P_{n} as above. Clearly P_{n} has index 2^{n} in G, as G acts transitively on Σ^{n}, and P has infinite index.

We note the following facts about G: it

• is an infinite torsion 2-group;

• is of intermediate growth, and therefore amenable (see Definition 3.3);

• is fractal, and regular branch on its subgroup K;

• is just infinite;

• has a recursive presentation with infinitely many relators; these relators are obtained as iterates of a substitution on a finite set of words [Lys85];

• is residually finite, and more precisely has a natural sequence of finite approximating quotients G_{n} = G/ st_{G}(n), of order 2^{5·2^{n−3}+2} for n ≥ 3 (and order 2^{2^{n}−1} for n ≤ 3);

• has a faithful action on the set G/P, of linear growth by Proposition 2.11;

• has a faithful action an ∂T whose orbits are confinality classes.

The decomposition of ρ_{G/P_{n}} in irreducibles is given by the following lemma, combined with Lemma 2.15:

Lemma 2.18 ([BG98]). P_{n} has n + 1 orbits in Σ^{n}; they are 0^{n} and the 0^{i}1Σ^{n−1−i} for 0 ≤ i < n. The orbits of P in T_{Σ} are the 0^{i}Σ^{∗} for all i ∈ ℕ.

2.5. The Group G̃. We describe briefly another fractal group, acting on the same tree T_{2} as G. More details appear in [BG98]. We denote again by a the automorphism permuting the top two branches, and let recursively b̃ be the automorphism acting as a on the right branch and c̃ on the left, c̃ be the automorphism acting as 1 on the right branch and d̃ on the left, and d̃ be the automorphism acting as 1 on the right branch and b̃ on the left. In formulæ,

b̃(0xσ) = 0\overline{x}σ,  b̃(1σ) = 1c̃(σ),
c̃(0σ) = 0σ,  c̃(1σ) = 1d̃(σ),
d̃(0σ) = 0σ,  d̃(1σ) = 1b̃(σ).

Then G̃ is the group generated by {a, b̃, c̃, d̃}. Clearly all these generators are of order 2, and {b̃, c̃, d̃} is elementary abelian of order 8. It can be defined using the second automaton in Figure 1, or as the dynamical system

a(z) = \begin{cases}z + \frac{1}{2} & if z < \frac{1}{2} \\ z − \frac{1}{2} & if z ≥ \frac{1}{2}, \end{cases}
b̃(z) =  a  1 1 a..
c̃(z) =  1  1 a 1..
d̃(z) =  1  a 1 1..

Recall the map ϕ defined in (1); it restricts to an embedding ϕ : H̃ → G̃ × G̃ given by

ϕ : \begin{cases}b̃ → (a, c̃), b̃^{a} → (c̃, a) \\ c̃ → (1, d̃), c̃^{a} → (d, 1) \\ d̃→ (1, b̃), d̃^{a} → (b̃, 1), \end{cases}

where H̃ = stG̃(1) = ⟨b̃, c̃, d̃⟩G̃ is an index-2 subgroup. Consider also K̃ = ⟨(ab̃)^{2}, (ad̃)^{2}⟩G̃. Let again e be the infinite sequence 0^{∞}; set P̃_{n} = stG̃(0^{n}) of index 2^{n}, and P̃ = stG̃(e) = ∩_{n≥0}P̃_{n} of infinite index.

We note the following facts about G, proved in [BG98]: it

• is an infinite group containing G = ⟨a, b̃c̃, c̃d̃, d̃b̃⟩ as an infinite-index subgroup, and has 2-torsion elements as well as infinite-order elements;

• is of intermediate growth, and therefore is amenable;

• is fractal, and regular branch on its subgroup K̃;

• is just infinite;

• has a recursive presentation with infinitely many relators; these relators are obtained as iterates of a substitution on a finite set of words. All of G̃’s relators have even length with respect to the generating set {a, b̃, c̃, d̃}, so its Cayley graph is bipartite;

• is residually finite, and more precisely has a natural sequence of finite approximating quotients G̃_{n} = G̃/ stG̃(n), of order 2^{13·2^{n−4}+2} for n ≥ 4 (and order 2^{2^{n}−1} for n ≤ 4).

• has a faithful action on the set G̃/P̃, of linear growth by Proposition 2.11;

• has a faithful action an ∂T whose orbits are confinality classes.

The decomposition of ρ_{G̃/P̃_{n}} in irreducibles is given by the following lemma, combined with Lemma 2.15:

Lemma 2.19. P̃_{n} has n + 1 orbits in Σ^{n}; they are 0^{n} and the 0^{i}1Σ^{n−1−i} for 0 ≤ i < n. The orbits of P̃ in T_{Σ} are the 0^{i}Σ^{∗} for all i ∈ ℕ.

2.6. GGS groups. We next study three examples of a family of groups called GGS groups (the terminology was introduced by Gilbert Baumslag [Bau93] and refers to Rostislav Grigorchuk, Narain Gupta and Said Sidki). Let p be a prime number. Denote a the automorphism of T_{p} permuting cyclically the top p branches. Let ϵ = (ϵ_{0}, …, ϵ_{p−2}) ∈ (ℤ/p)^{p−1}. Define recursively the automorphism t_{ϵ} of T_{p} by

t(xyσ) = x(y + ϵ_{x})σ if 0 ≤ x ≤ p − 2, t((p − 1)σ) = (p − 1)t(σ).

Then G_{ϵ} is the subgroup of Aut(T_{p}) generated by {a, t}.

The following results have their roots in [Gri80, GS83b] and are known as part of folklore; for a proof see [Gri98]:

Theorem 2.20. G_{ϵ} is an infinite group if an only if ϵ ≠ (0, …, 0). It is a torsion group if and only if ∑ ϵ_{i} = 0.

Theorem 2.21 ([Bar99]). For all ϵ, the group G_{ϵ} is of subexponential growth, and therefore is amenable.

[figure: ε; a; 1; Σ; 1; s; Σ; 0; 1; 2; ε; a; 1; t; 1; 0, 1; Σ; Σ; 2]

[figure: ε; a; 1; r; 1; ε^{2}; 0; Σ; Σ; 1; 2; Σ]

Figure 2. The Automata for Γ, \overline{Γ} and \overline{\overline{Γ}}

Let G = G_{ϵ} be as above. Let e = (p − 1)^{∞} be the rightmost path in T_{p} and let P = st_{G}(e). Proposition 2.11 applies, so G/P has polynomial growth of degree at most log_{2}(p).

2.7. The Group Γ. As always denote by a the rooted automorphism of T_{3} permuting cyclically the top three branches. Let s be the automorphism of T_{3} defined recursively by

s(0xσ) = 0\overline{x}σ,  s(1xσ) = 1xσ,  s(2σ) = 2s(σ).

Then Γ is the subgroup of Aut(T_{3}) generated by {a, s}; its growth was studied by Jacek Fabrykowski and Narain Gupta [FG91]. It can also be defined using automata, as in Figure 2, or as the dynamical system

a(z) = \begin{cases}z + \frac{1}{3} & if z < \frac{2}{3} \\ z − \frac{2}{3} & if z ≥ \frac{2}{3}, \end{cases}

s(z) =  a  1  a 1 a.._{0}  _{\frac{1}{3}}  _{\frac{2}{3}}  _{\frac{7}{9}}  _{\frac{8}{9}}  _{1}

Set H = st_{Γ}(1) = ⟨s⟩^{Γ}; then ϕ : H → Γ × Γ × Γ can be expressed as

ϕ : {s → (a, 1, s), s^{a} → (s, a, 1), s^{a^{2}} → (1, s, a). (3)

Define the elements x = as, y = sa of Γ, and let K be the subgroup of Γ generated by x and y. Then K is normal in Γ, because y^{s} = x^{−1}y^{−1}, y^{a^{−1}} = y^{−1}x^{−1}, y^{s^{−1}} = y^{a} = a, and similar relations hold for conjugates of x. Moreover K is of index 3 in Γ, with transversal ⟨a⟩. Let L be the subgroup of K generated by [K, K] and cubes in K.

Theorem 2.22 ([BG98]). Γ is a regular branch, fractal group. The subgroup K of Γ is torsion-free; thus Γ is virtually torsion-free. The finite quotients Γ_{n} = Γ/H_{n} of Γ have order 3^{3^{n−1}+1} for n ≥ 2, and 3 for n = 1.

2.8. The Group \overline{Γ}. Let a be as in the previous subsection, and let t be the automorphism of T_{3} defined recursively by

t(0xσ) = 0\overline{x}σ,  t(1xσ) = 1\overline{x}σ,  t(2σ) = 2t(σ).

Then \overline{Γ} is the subgroup of Aut(T_{3}) generated by \{a, t\}. The associated dynamical system is

a(z) = \begin{cases}z + \frac{1}{3} & if z < \frac{2}{3} \\ z − \frac{2}{3} & if z ≥ \frac{2}{3}, \end{cases}
t(z) =  a  a  a a a.. .

Set H = st\overline{Γ}(1) = ⟨t⟩\overline{Γ}; then ϕ : H → \overline{Γ} × \overline{Γ} × \overline{Γ} can be expressed as

ϕ : {t → (a, a, t), t^{a} → (t, a, a), t^{a^{2}} → (a, t, a).

Define the elements x = ta^{−1}, y = a^{−1}t of \overline{Γ}, and let \overline{K} be the subgroup of \overline{Γ} generated by x and y. Then \overline{K} is normal in \overline{Γ}, because x^{t} = y^{−1}x^{−1}, x^{a} = x^{−1}y^{−1}, x^{t^{−1}} = x^{a^{−1}} = y, and similar relations hold for conjugates of y. Moreover \overline{K} is of index 3 in \overline{Γ}, with transversal ⟨a⟩.

Theorem 2.23 ([BG98]). \overline{Γ} is a fractal group and is weak branch, but not branch. The subgroup \overline{K} of \overline{Γ} is torsion-free; thus \overline{Γ} is virtually torsion-free. The finite quotients \overline{Γ}_{n} = \overline{Γ}/H_{n} of \overline{Γ} have order 3^{\frac{1}{4} (3^{n}+2n+3)} for n ≥ 2, and 3^{\frac{1}{2} (3^{n}−1)} for n ≤ 2.

2.9. The Group \overline{\overline{Γ}}. Let again a denote the automorphism of T_{3} permuting cyclically the top three branches. Let now r be the automorphism of T_{3} defined recursively by

r(0xσ) = 0\overline{x}σ,  r(1xσ) = 1\overline{\overline{x}}σ,  r(2σ) = 2r(σ).

Then \overline{\overline{Γ}} is the subgroup of Aut(T_{3}) generated by \{a, r\}; it was studied by Gupta and Sidki [GS83a, GS83b, Sid87a, Sid87b]. The associated dynamical system is

a(z) = \begin{cases}z + \frac{1}{3} & if z < \frac{2}{3} \\ z − \frac{2}{3} & if z ≥ \frac{2}{3}, \end{cases}
r(z) =  ^{a  a^{2}  a a^{2} a..} .

Set H = st\overline{\overline{Γ}}(1) = ⟨r⟩\overline{\overline{Γ}}; then ϕ : H → \overline{\overline{Γ}} × \overline{\overline{Γ}} × \overline{\overline{Γ}} con be expressed as

ϕ : {r → (a, a^{2}, r), r^{a} → (r, a, a^{2}), r^{a^{2}} → (a^{2}, r, a).

Theorem 2.24 ([BG98]). \overline{\overline{Γ}} is a just infinite torsion 3-group. It is branch and fractal. The finite quotients \overline{\overline{Γ}}_{n} = \overline{\overline{Γ}}/H_{n} of Γ have order 3^{2·3^{n−2}+1} for n ≥ 2, and 3 for n = 1.

3. Unitary Representations and Hecke type Operators

The five groups introduced in the previous section share the property of acting faithfully on a regular rooted tree; natural representations arise from this fact. In this chapter we suppose G is any group acting level-transitively on a regular tree.

We defined in Subsection 2.1 the boundary ∂T of the tree on which G acts. Since G preserves the uniform measure on this boundary, we have a unitary representation π of G in L^{2}(∂T , ν), or equivalently in L^{2}([0, 1], m). Let H_{n} be the subspace of L^{2}(∂T , ν) spanned by the characteristic functions χ_{σ} of the rays e starting by σ, for all σ ∈ Σ^{n}. It is of dimension d^{n}, and can equivalently be seen as spanned by the characteristic functions in L^{2}([0, 1], m) of intervals of the form [(i − 1)d^{−n}, id^{−n}], 1 ≤ i ≤ d^{n}. These H_{n} are invariant subspaces, and afford representations π_{n} = π_{|H_{n}}. As clearly π_{n−1} is a subrepresentation of π_{n}, we set π_{n}^{⊥} = π_{n} ⊖ π_{n−1}, so that π = ⊕_{n=0}^{∞}π_{n}^{⊥}.

Denote by ρ_{G/H} the quasi-regular representation of G in ℓ^{2}(G/H) and by ρ_{G/H_{n}} the finite-dimensional representations of G in ℓ^{2}(G/H_{n}). Since G is level-transitive, the representations π_{n} and ρ_{G/H_{n}} are unitary equivalent.

Definition 3.1. Let G be a group generated by a set S and H a subgroup of G. The Schreier graph S(G, H, S) of G/H is the directed graph on the edge set G/H, with for every s ∈ S and every gH ∈ G/H an edge from gH to sgH. The base point of S(G, H, S) is the coset H.

Note that S(G, 1, S) is the Cayley graph of G relative to S. It may happen that S(G, P, S) have loops and multiple edges even if S is disjoint from H. Schreier graphs are |S|-regular graphs, and any degree-regular graph G containing a 1-factor (i.e. a regular subgraph of degree 1; there is always one if G has even degree) is a Schreier graph [Lub95, Theorem 5.4].

Definition 3.2. Let G be a group generated by a finite symmetric set S. The spectrum spec(τ) of a representation τ : G → U(H) with respect to the given set of generators is the spectrum of Δ_{τ} = ∑_{s∈S} τ(s) seen as an bounded operator on H.

As the vertices of S(G, H, S) coincide with the set G/H, it is easy to see that Δ_{τ} /|S| − 1 is unitary equivalent to the Laplacian operator on S(G, H, S), and therefore has same spectrum.

Definition 3.3. Let G be a group acting on a set X. This action is amenable in the sense of von Neumann [vN29] if there exists a finitely additive measure μ on X, invariant under the action of G, with μ(X) = 1.

A group G is amenable if its action on itself by left-multiplication is amenable.

Amenability can be tested using the following criterion, due to Følner for the regular action [Føl57] (see also [CGH99] and the literature cited there):

Theorem 3.4. Assume the group G acts on a discrete set X. Then the action is amenable if and only for every if for every λ > 0 and every g ∈ G there exists a finite subset F ⊂ X such that |F △gF | < λ|F |, where △ denotes symmetric difference and | · | cardinality.

Using this criterion it is easy to see that any G-space X of subexponential growth is amenable. In particular the G-spaces G/P are of polynomial growth when the conditions of Proposition 2.11 are fulfilled, and therefore are amenable. The following result belongs to the common lore, and we don’t know of a reference to its proof. Our attention was drawn to it by Marc Burger and Alain Valette:

Proposition 3.5. Let H < G be any subgroup. Then the quasi-regular representation ρ_{G/H} is weakly contained in ρ_{G} if and only if H is amenable.

Proof. If H is amenable, then the trivial one-dimensional representation 1_{H} of H is weakly contained in ρ_{H}. Inducing up, ρ_{G/H} = Ind_{H}^{G} 1_{H} is weakly contained in ρ_{G} = Ind_{H}^{G}(ρ_{H}).

Conversely, if ρ_{G/H} is weakly contained in ρ_{G}, we obtain by restricting to H that ρ_{G/H}_{|H} is weakly contained in ρ_{G}_{|H}. Now 1_{H} is a subrepresentation of ρ_{G/H}_{|H}, because the Dirac mass at H is H-fixed; and ρ_{G}_{|H} = [G : H]ρ_{H} by Frobenius reciprocity. It follows that 1_{H} is weakly contained in [G : H]ρ_{H}, and therefore that H is amenable.

The following statements allows one to compare spectra of diverse representations.

Theorem 3.6. Let G be a group acting on a regular rooted tree, and let π, π_{n} and π_{n}^{⊥} be as above.

1. If G is weak branch, then ρ_{G/P} is an irreducible representation of infinite dimension.

2. π is a reducible representation of infinite dimension whose irreducible components are precisely those of the π_{n}^{⊥} (and thus are all finite-dimensional). Moreover

spec(π) = \overline{⋃_{n≥0} spec(π_{n})} = \overline{⋃_{n≥0} spec(π_{n}^{⊥})}.

3. The spectrum of ρ_{G/P} is contained in \overline{∪_{n≥0} spec(ρ_{G/P_{n}})} = \overline{∪_{n≥0} spec(π_{n})}, and thus is contained in the spectrum of π. If moreover either P or G/P are amenable, these spectra coincide, and if P is amenable, they are contained in the spectrum of ρ_{G}:

spec(ρ_{G/P}) = spec(π) = \overline{⋃_{n≥0} spec(π_{n})} ⊆ spec(ρ_{G}).

4. Δ_{π} has a pure-point spectrum, and its spectral radius r(Δ_{π}) = s ∈ ℝ is an eigenvalue, while the spectral radius r(Δ_{ρ_{G/P}}) is not an eigenvalue of Δ_{ρ_{G/P}}. Thus Δ_{ρ_{G/P}} and Δ_{π} are different operators having the same spectrum.

Proof. The first statement follows from Mackey’s theorem 2.14 and Proposition 2.13. The second holds because π splits as the direct sum of the π_{n}^{⊥}’s, and is weakly equivalent to the direct sum of the π_{n}’s.

It was mentioned that ρ_{G/P_{n}} and π_{n} are equivalent: they are both finite-dimensional and act on G-equivalent sets, namely G/H_{n} and Σ^{n}. The third statement then follows from Proposition 3.5 and Propositions 3.8 and 3.9 below.

It is obvious that s is an eigenvalue of Δ_{π} with constant eigenfunction. Now the fourth follows from Proposition 5 in [GŻ97].

Since all of our example groups are amenable, the spectra computed in the next section are included in spec(ρ_{G}). Moreover, as G̃ has a bipartite Cayley graph, spec(ρG̃) is symmetrical about 1 and contains [0, 4] (as we shall show in Section 4.2), so is [−4, 4].

We finish this subsection by turning to a question of Mark Kać [Kać96]: “Can one hear the shape of a drum?” This question was answered in the negative in [GWW92], and we here answer by the negative to a related question: “Can one hear a representation?” Indeed ρ_{G/P} and π have same spectrum (i.e. cannot be distinguished by hearing), but are not equivalent. Furthermore, if G is a branched group, there are uncountably many nonequivalent representations within {ρ_{G/ st_{G}(e)}| e ∈ ∂T }, as is shown in [BG98].

The same question may be asked for graphs: “are there two non-isomorphic graphs with same spectrum?” There are finite examples, obtained through the notion of Sunada pair [Lub95]. Cédric Béguin, Alain Valette and Andrzej Żuk produced the following example in [BVŻ97]: let Γ be the integer Heisenberg group (free 2-step nilpotent on 2 generators x, y). Then Δ = x+x^{−1}+y+y^{−1} has spectrum [−2, 2], which is also the spectrum of ℤ^{2} for an independent generating set. As a consequence, their Cayley graphs have same spectrum, but are not quasi-isometric (they do not have the same growth).

Using the result of Nigel Higson and Gennadi Kasparov [HK97] (giving a partial positive answer to the Baum-Connes conjecture), we may infer the following

Proposition 3.7. Let Γ be a torsion-free amenable group with finite generating set S = S^{−1} such that there is a map ϕ : Γ → ℤ/2ℤ with ϕ(S) = {1}. Then

spec(∑_{s∈S} ρ(s)) = [−|S|, |S|].

In particular, there are countably many non-quasi-isometric graphs with the same spectrum, including the graphs of ℤ^{d}, of free nilpotent groups and of suitable torsion-free groups of intermediate growth (for the first examples, see [Gri85]).

Proof. Since Γ is amenable, |S| is in its spectrum. By the existence of ϕ, the Cayley graph of Γ with respect to S is two-colourable (i.e. bipartite), so its spectrum is symmetrical, and therefore contains −|S|. By the Baum-Connes conjecture, proved for this case by Higson and Kasparov, the C^{∗}-algebra C_{r}^{∗}(ρ(Γ)) contains no idempotents. It follows by functional integration that ρ’s spectrum is connected, so is [−|S|, |S|] as claimed.

3.1. Approximations of Operators and Spectra. We now prove the claimed inclusions of spectra, in part relying on C^{∗}-algebraic results.

Proposition 3.8. Let {H_{n}}_{n≥0} be a descending family of finite-index subgroups of G, and set H = ⋂_{n≥0} H_{n}. Let τ and τ_{n} be the quasi-regular representations of G on G/H and G/H_{n} respectively. Then

spec τ ⊆ \overline{⋃_{n≥0} spec τ_{n}}.

Proof. Let S and S_{n} be the Schreier graphs S(G, H, S) and S(G, H_{n}, S) respectively, and mark in them the vertices H and H_{n}. Then S_{n} ⟹_{n→∞} S in the sense

of [GŻ97], that is, coincide with S in ever increasing balls centered at H_{n}; therefore, for their associated spectral measures, σ_{n}(λ) ⟹_{n→∞} σ(λ), in the sense of weak convergence. Therefore the support of dσ is contained in the closure of the union of the supports of dσ_{n}, and the proposition follows.

Alternate Proof. The quasi-regular representation τ is weakly contained in ⊕_{n≥0}τ_{n}, by “approximation of coefficients” [Dix77, Theorem 3.4.9]. Indeed, as δ_{H}, the Dirac function at H, is a cyclic vector for τ, it is enough to see that the function

g ↦ ⟨τ(g)δ_{H}|δ_{H}⟩ = \begin{cases}1 & if g ∈ H \\ 0 & otherwise \end{cases}

can be pointwise approximated on G be coefficients of the τ_{n}’s. But

⟨τ_{n}(g)δ_{H_{n}}|δ_{H_{n}}⟩ = \begin{cases}1 & if g ∈ H_{n} \\ 0 & otherwise \end{cases} ,

so

lim_{n→∞}⟨τ_{n}(g)δ_{H_{n}}|δ_{H_{n}}⟩ = ⟨τ(g)δ_{H}|δ_{H}⟩.

We then have a surjection C^{∗}(⊕_{n≥0}τ_{n}) ↠ C^{∗}(τ), where C^{∗}(ρ) is the C^{∗}-algebra generated by the image of ρ. The spectrum inclusions follow.

Proposition 3.9. Let {H_{n}}_{n≥0} be a descending family of finite-index subgroups of G, and set H = ⋃_{n≥0} H_{n}. Let τ and τ_{n} be the quasi-regular representations of G on G/H and G/H_{n} respectively. Assume moreover that the action of G on G/H is amenable, i.e. that S(G, H, S) is amenable. Then

spec τ = \overline{⋃_{n≥0} spec τ_{n}}.

Proof. Let S be the Schreier graph S(G, H, S). Choose μ ∈ spec τ_{n}, with a corresponding eigenvector v : G/H_{n} → ℂ. As S is amenable, there is a Følner sequence {F_{k}} in S, i.e. a family of subsets of V (S) with |F_{k}|/|∂F_{k}| → 0 as k → ∞. Define now functions v_{k} on S,

v_{k}(gH) = \begin{cases}v(gH_{n}) & if gH ∈ F_{k}, \\ 0 & otherwise. \end{cases}

Then ∥Δ_{τ} v_{k} − μv_{k}∥ ≤ |∂F_{k}| · ∥v∥. If we let Ω be a fundamental domain of G/H_{n} in S, of diameter δ, and let ∂_{δ}(F_{k}) denote the δ-neighbourhood of F_{k}, then we have |Ω| · ∥v_{k}∥ ≥ (|F_{k}| − |∂_{δ}F_{k}|)∥v∥, whence

∥Δ_{τ} \frac{v_{k}}{∥v_{k}∥} − μ\frac{v_{k}}{∥v_{k}∥}∥ ≤ \frac{|Ω| · |∂F_{k}|}{|F_{k}| − |∂_{δ}F_{k}|} → 0,

so μ ∈ spec τ.

3.2. Spectral Measures. In parallel to the computation of spectra, interesting questions arise in relation to properties of spectral measures associated to Markovian operators. There are two approaches to spectral measures, one via a solution to the moment problem and one via trace states in von Neumann algebras.

Let G be a graph, and let M be its Markovian operator. For any x, y ∈ V (G) and n ∈ ℕ let p_{x,y}^{n} be the probability that a simple random walk starting at x be at y after n steps. Recall that if M_{v} be the characteristic vector of the vertex v, then

p_{x,y}^{n} = ⟨M^{n}δ_{x}|δ_{y}⟩.

Define the spectral measures σ_{x,y} by

p_{x,y}^{n} = ∫_{−1}^{1} λ^{n}dσ_{x,y}(λ) ∀n ∈ ℕ,

or equivalently as

σ_{x,y}(λ) = ⟨M(λ)δ_{x}|δ_{y}⟩,

where M(λ) is the spectral decomposition of M (the operator coinciding with M on eigenfunctions whose eigenvalue is at most λ). Set σ_{x} = σ_{x,x}. These measures are called the Kesten spectral measures, as they were introduced in [Kes59].

Proposition 3.10. If G is connected, then all the measures σ_{x,y} are equivalent.

Therefore there is only one type of Kesten spectral measure, up to equivalence.

Now let N be a von Neumann algebra with a finite state τ. For any self-adjoint element a ∈ N one can define a spectral measure τ_{a} by τ_{a}(λ) = τ(a(λ)), where a(λ) is the spectral decomposition of a. We shall call τ_{a} the von Neumann spectral measure associated to a.

For instance, such a situation appears if N is finite-dimensional, or more generally of finite type. Another important example is when N is the von Neumann algebra generated by the left-regular representation of a group. In this case the von Neumann spectral measure is given by τ_{a}(λ) = ⟨a(λ)δ_{1}, δ_{1}⟩, where δ_{1} is the Dirac function in the identity of the group. Therefore in this case the von Neumann and Kesten spectral measures of a Markovian operator coincide. A similar situation occurs if N is a hyperfinite algebra of type II_{1}, but there δ_{1} should be replaced by any cyclic vector. If N is any algebra of type II_{1} there is a canonical trace of the form τ(a) = ∑_{i}⟨ax_{i}, x_{i}⟩, for some (in general infinite) sequence of vectors (x_{i}).

Let P be a subgroup of a group G and suppose that the von Neumann algebra generated by ρ_{G/P} has finite trace. Then for any symmetric system S of generators of G the von Neumann spectral measure τ_{a} = τ_{∑_{s∈S} s} can be defined. We also call τ_{a} the von Neumann spectral measure of the Schreier graph G = S(G, P, S).

In case G is finite, the von Neumann spectral measure is just a “histogram”, counting in any given interval the “average number of eigenvalues” that belong to it.

Suppose now that P = ∩_{n=1}^{∞}P_{n}, where the P_{n} are subgroups of finite index of G. Then the sequence of finite graphs G_{n} = S(G, P_{n}, S) converges to the graph G in the sense of [GŻ97], and the following statement holds:

Proposition 3.11 ([GŻ97]). Let σ_{n} and σ be the Kesten spectral measures of the Schreier graphs G_{n} and G based at P_{n} and P respectively.

Then we have σ_{n}(λ) ⟹ σ(λ) in the sense of weak convergence.

In case the subgroups P_{n} are normal and P = 1, we deduce from this proposition the convergence of the corresponding spectral measures τ_{n} to τ, since in this case σ_{n} = τ_{n} and σ = τ. These results were obtained by Wolfgang Lück [Lüc94] and Michael Farber [Far98] using different methods.

It is interesting to study the conditions under which the spectral measures τ_{n} of finite graphs S(G, P_{n}, S) converge to some limit τ_{∗} (which we call the empiric spectral measure), and, in case the von Neumann spectral measure τ is well defined for a graph S(G, P, S) (for instance, for a quasi-regular representation ρ_{G/P} generating a von Neumann algebra of finite type), under which conditions we have τ = τ_{∗}. Also, in the last case, when do we have σ = τ?

Unfortunately, in our situation, the von Neumann algebra generated by ρ_{G/P} is the algebra of all bounded operators so it has no a good state.

More investigations should be done in order to clarify the meaning of our computations of empiric spectral measures in the examples that follow.

3.3. Operator Recursions. Let H be an infinite-dimensional Hilbert space, and suppose Φ : H → H ⊕ ⋯ ⊕ H is an isomorphism, where the domain of Φ is a sum of d ≥ 2 copies of H. Let S be a finite subset of U(H), and suppose that for all s ∈ S, if we write Φ^{−1}sΦ as an operator matrix (s_{i,j})_{i,j∈{1,...,d}} where the s_{i,j} are operators in H, then s_{i,j} ∈ S ∪ {0, 1}.

This is precisely the setting in which we will compute the spectra of our five example groups: for G, we have d = 2 and S = {a, b, c, d} with

a = (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) , b = (\begin{matrix}a & 0 \\ 0 & c \end{matrix}) ,

c = (\begin{matrix}a & 0 \\ 0 & d \end{matrix}) , d = (\begin{matrix}1 & 0 \\ 0 & b \end{matrix}) .

For G̃, we also have d = 2, and S = {a, b̃, c̃, d̃} given by

b = (\begin{matrix}a & 0 \\ 0 & c \end{matrix}) ,  c = (\begin{matrix}1 & 0 \\ 0 & d \end{matrix}) ,  d = (\begin{matrix}1 & 0 \\ 0 & b \end{matrix}) .

For Γ = ⟨a, s⟩, \overline{Γ} = ⟨a, t⟩ and \overline{\overline{Γ}} = ⟨a, r⟩, we have d = 3 and

a = (\begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}) , s = (\begin{matrix}a & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & s \end{matrix}) ,

t = (\begin{matrix}a & 0 & 0 \\ 0 & a & 0 \\ 0 & 0 & t \end{matrix}) , r = (\begin{matrix}a & 0 & 0 \\ 0 & a^{2} & 0 \\ 0 & 0 & r \end{matrix}) .

Each of these operators is unitary. The families S = {a, b, c, d}, … generate subgroups G(S) of U(H). The choice of the isomorphism Φ defines a unitary representation of ⟨S⟩.

We note, however, that the expression of each operator as a matrix of operators does not uniquely determine the operator, in the sense that different isomorphisms Φ can yield non-isomorphic operators satisfying the same recursions. Even if Φ is fixed, it may happen that different operators satisfy the same recursions. We consider two types of isomorphisms in this paper: H = ℓ^{2}(G/P), where Φ is derived from the ϕ defined in (1); the second case considered is H = L^{2}(∂T ), where Φ : H → H^{Σ} is defined by Φ(f)(σ) = (f(0σ), …, f((d − 1)σ)), for f ∈ L^{2}(∂T ) and σ ∈ ∂T . There are actually uncountably many non-equivalent isomorphisms, giving uncountably many non-equivalent representations of the same group, as we indicated just before Subsection 3.1.

4. Computations of Finite Spectra

Here we compute explicitly the spectra of the representations π_{n} described in Section 3. For our five examples, the general principle will be the same: obtain recurrence relations on the matrices of the representation and compute eigenvalues by recurrence. We end each subsection with a computation of the spectral measure τ_{Δ}.

4.1. The group G. Recall the finite quotient G_{n} acts faithfully on {0, 1}^{n}. If we denote by a_{n}, b_{n}, c_{n}, d_{n} the permutation matrices of this representation, we have

a_{0} = b_{0} = c_{0} = d_{0} = (1),

a_{n} = (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) , b_{n} = (\begin{matrix}a_{n−1} & 0 \\ 0 & c_{n−1} \end{matrix}) ,

c_{n} = (\begin{matrix}a_{n−1} & 0 \\ 0 & d_{n−1} \end{matrix}) , d_{n} = (\begin{matrix}1 & 0 \\ 0 & b_{n−1} \end{matrix}) .

The Hecke type operator of π_{n} is

Δ_{n} = a_{n} + b_{n} + c_{n} + d_{n} = (\begin{matrix}2a_{n−1} + 1 & 1 \\ 1 & Δ_{n−1} − a_{n−1} \end{matrix}) ,

ON THE SPECTRUM OF HECKE TYPE OPERATORS RELATED TO SOME FRACTAL GROUPS 23

and we wish to compute its spectrum. We start by proving a slightly stronger result: define

Q_{n}(λ, μ) = Δ_{n} − (λ + 1)a_{n} − (μ + 1)

and

Φ_{0} = 2 − μ − λ,
Φ_{1} = 2 − μ + λ,
Φ_{2} = μ^{2} − 4 − λ^{2},
Φ_{n} = Φ_{n−1}^{2} − 2(2λ)^{2^{n−2}}  (n ≥ 3).

Lemma 4.1. For n ≥ 2 we have

|Q_{n}(λ, μ)| = (4 − μ^{2})^{2^{n−2}} |Q_{n−1} (\frac{2λ^{2}}{4 − μ^{2}} , μ + \frac{μλ^{2}}{4 − μ^{2}} )| (n ≥ 2).

Proof.

|Q_{n}(λ, μ)| = |\begin{matrix}2a_{n−1} − μ & −λ \\ −λ & Δ_{n−1} − a_{n−1} − (1 + μ) \end{matrix}|

= |\begin{matrix}2a_{n−1} − μ & −λ \\ (2a_{n−1} − μ)\frac{−λ(2a_{n−1}+μ)}{4−μ^{2}} & Δ_{n−1} − a_{n−1} − (1 + μ) \end{matrix}|

= |\begin{matrix}2a_{n−1} − μ & −λ \\ 0 & Δ_{n−1} − a_{n−1} − (1 + μ) − \frac{λ^{2}}{4−μ^{2}} (2a_{n−1} + μ) \end{matrix}|

= |2a_{n−1} − μ| · |Δ_{n−1} − (1 + \frac{2λ^{2}}{4 − μ^{2}} ) a_{n−1} − (1 + μ + \frac{μλ^{2}}{4 − μ^{2}} )|;

now

|2a_{n−1} − μ| = |\begin{matrix}−μ & 2 \\ 2 & −μ \end{matrix}|_{2^{n−1}} = (μ^{2} − 4)^{2^{n−2}}

so the lemma follows. Lemma 4.2. For all n we have

|Q_{n}| = Φ_{0}Φ_{1} ⋯ Φ_{n}.

Proof. By direct computation,

Q_{0}(λ, μ) = (2 − μ − λ), Q_{1}(λ, μ) = (\begin{matrix}2 − μ & −λ \\ −λ & 2 − μ \end{matrix}) ,

so |Q_{0}| = Φ_{0} and |Q_{1}| = Φ_{0}Φ_{1}.

Let us temporarily agree to write

λ′ = \frac{2λ^{2}}{4 − μ^{2}}  Φ_{i} = Φ_{i}(λ, μ)
μ′ = μ + \frac{μλ^{2}}{4 − μ^{2}}  Φ′_{i} = Φ_{i}(λ′, μ′).

24 LAURENT BARTHOLDI AND ROSTISLAV I. GRIGORCHUK

We will prove by recurrence that

(2 − μ)Φ′_{0} = Φ_{0}Φ_{1},
(2 + μ)Φ′_{1} = −Φ_{2},
(4 − μ^{2})Φ′_{2} = −Φ_{3},
(4 − μ^{2})^{2^{n−2}}Φ′_{n} = Φ_{n+1}  (n ≥ 3).

Indeed

(2 − μ)Φ′_{0} = (2 − μ)(2 − μ) − \frac{μλ^{2}}{2 + μ} − \frac{2λ^{2}}{2 + μ}
= (2 − μ)^{2} − λ^{2} = Φ_{0}Φ_{1};
(2 + μ)Φ′_{1} = (2 + μ)(2 − μ) − \frac{μλ^{2}}{2 − μ} + \frac{2λ^{2}}{2 − μ}
= 4 − μ^{2} + λ^{2} = −Φ_{2};
(4 − μ^{2})Φ′_{2} = (4 − μ^{2})(μ^{2} − 4) + 2μ^{2}λ^{2} + \frac{(μλ^{2})^{2}}{4 − μ^{2}} − \frac{(2λ^{2})^{2}}{4 − μ^{2}}
= − [(μ^{2} − 4)^{2} − 2μ^{2}λ^{2} + λ^{4}]
= − [(μ^{2} − 4 − λ^{2})^{2} − 8λ^{2}] = −Φ_{3};

and for n ≥ 3,

(4 − μ^{2})^{2^{n−2}}Φ′_{n} = (4 − μ^{2})^{2^{n−2}}(Φ′_{n−1})^{2} − (4 − μ^{2})^{2^{n−2}}2(2λ′)^{2^{n−2}}
= ((4 − μ^{2})^{2^{n−3}}Φ′_{n−1})^{2} − 2(4λ^{2})^{2^{n−2}}
= (±Φ_{n})^{2} − 2(2λ)^{2^{n−1}} = Φ_{n+1}.

Now using Lemma 4.1 we have for n ≥ 3

|Q_{n}(λ, μ)| = (4 − μ^{2})^{2^{n−2}}|Q_{n−1}(λ′, μ′)|
= (4 − μ^{2})^{2^{n−2}}Φ′_{0}Φ′_{1} ⋯ Φ′_{n−1}

= (2 − μ)Φ′_{0}(2 + μ)Φ′_{1}(4 − μ^{2})Φ′_{2} ⋯ (4 − μ)^{2^{n−3}}Φ′_{n−1}

= Φ_{0}Φ_{1}Φ_{2} ⋯ Φ_{n},

proving the claim. Proposition 4.3. For all n we have

{(λ, μ) : Q_{n}(λ, μ) non invertible} = {(λ, μ) : Φ_{0}(λ, μ) = 0}∪{(λ, μ) : Φ_{1}(λ, μ) = 0}

∪ \{(λ, μ) : 4 − μ^{2} + λ^{2} + 4λ cos (\frac{2πj}{2^{n}} ) = 0 for some j = 1, …, 2^{n−1} − 1\}.

Proof. We prove by recurrence that for all n, k with 0 ≤ k ≤ n − 2 we have

Φ_{n} = ∏_{t=0}^{2^{k}−1} (Φ_{n−k} − 2(2λ)^{2^{n−2−k}} cos (\frac{2π(2t + 1)}{2^{k+2}})) . (4)

μ  λ

Figure 3. The spectrum of Q_{n}(λ, μ) for G and G̃

Indeed for k = 0 equality holds trivially, and if k > 0 we combine the terms for t and 2^{k} − 1 − t, with t < 2^{k−1}: letting A_{k,t} designate the t-th term,

A_{k,t}A_{k,2^{k}−1−t} = Φ_{n−k}^{2} − 4(2λ)^{2^{n−k−1}} cos^{2} (\frac{2π(2t + 1)}{2^{k+2}})

= Φ_{n−k}^{2} − 2 (1 + (2λ)^{2^{n−k−1}} cos (\frac{2π(2t + 1)}{2^{k+1}}))

= Φ_{n−k+1} − 2(2λ)^{2^{n−k−1}} cos (\frac{2π(2t + 1)}{2^{k+1}})

= A_{k−1,t},

so ∏_{t=0}^{2^{k}−1} A_{k,t} = ∏_{t=0}^{2^{k−1}−1} A_{k−1,t}. Letting k = n − 2 in (4) proves the proposition, in light of Lemma 4.2.

In the (λ, μ) system, the spectrum of Q_{n} is thus a collection of 2 lines and 2^{n−1}−1 hyperbolæ. The spectrum of Δ_{n} is precisely the set of θ such that |Q_{n}(−1, θ−1)| = 0. From Proposition 4.3 we obtain

spec(Δ_{n}) = \{1 ± \sqrt{5 − 4 cos ϕ} : ϕ ∈ 2πℤ/2^{n}\} \ \{0, −2\}.

The first eigenvalues are 4; 2; 1 ± \sqrt{5}; 1 ± \sqrt{5 ± 2\sqrt{2}}; 1 ± \sqrt{5 ± 2\sqrt{2 ± \sqrt{2}}}; etc.

The numbers of the form ±\sqrt{λ ± \sqrt{λ ± \sqrt{…}}} appear as preimages of the quadratic map z^{2} − λ, and after closure produce a Julia set for this map (see [Bar88]). In the given example this Julia set is just an interval. In the examples that follow in Subsection 4.3 the spectra are simple transformations of Julia sets which are totally disconnected—this behaviour is explained by Lemma 4.12 and the remark after its proof.

Corollary 4.4. The spectrum of π, for the group G, is

spec(Δ) = [−2, 0] ∪ [2, 4].

We now investigate the empiric spectral measure τ_{Δ}, as defined in Subsection 3.2. We constructed in the previous paragraph a one-to-one map χ : [0, π] × {±1} → ℝ defined by

χ(θ, ϵ) = 1 + ϵ\sqrt{5 + 4 cos θ}.

The spectrum is uniformly distributed in [0, π] × {±1} by Proposition 4.3, and χ is by assumption a measure-preserving map, so the measure τ(A) of any subset A of ℝ can be evaluated as

τ(A) = vol(χ^{−1}(A)),

where vol is the uniform measure on [0, π] × {±1}. The measure dτ_{Δ}(x) = g(x)dx we are seeking is thus given by

g(x) = \frac{1}{2π} \frac{∂}{∂x}χ^{−1}(x) = \frac{1 − x}{4π\sqrt{1 − (\frac{(x−1)^{2}−5}{4})^{2}}} .

The eigenvectors of Δ_{n} can be expressed as follows. Let λ be an eigenvalue and define by induction the sequence

v_{1} = 1; v_{2} = λ − 3; v_{i} = \begin{cases}\frac{(λ−1)v_{i−1}−v_{i−2}}{2} & if i ≥ 3, i ≡ 1[2]; \\ (λ − 1)v_{i−1} − 2v_{i−2} & if i ≥ 3, i ≡ 0[2]. \end{cases}

Define also by induction for all i ≥ 0 the following ordering of Σ^{i}: if the ordering of Σ^{i−1} is (σ_{1}, …, σ_{2^{i−1}}), the ordering of Σ^{i} is

(1σ_{1}, 0σ_{1}, 0σ_{2}, 1σ_{2}, 1σ_{3}, …, 0σ_{2^{i−1}}, 1σ_{2^{i−1}}).

Lemma 4.5. If λ is an eigenvalue of Δ_{n}, and (σ_{1}, …, σ_{2^{n}}) is the ordering described above, then the eigenvector corresponding to λ has value v_{i} on the vertex σ_{i}.

Proof. Consider the Schreier graph G_{n} = S(G, P_{n}, S) described in Subsection 5.1. It has vertex set {1, …, 2^{n}}, a simple edge between 2i−1 and 2i for all i, a double edge between 2i and 2i + 1 for all i, a loop at each i, and a triple loop at 1 and 2^{n}. The homogeneous space G_{n}/P_{n} is isomorphic to X graph through the correspondence σ_{i} ↦ i. The choices of v_{i} clearly define an eigenvector for λ, because v_{2^{n}} = 0 if λ is an eigenvalue for Δ_{n}.

It is then possible to express the characteristic function of any vertex as a linear combination of the eigenvectors described above, and to explicitly compute the

f  λ

Figure 4. The empiric spectral measure for G

corresponding Kesten spectral measure. We shall not develop here this topic; but we note that the coordinates of the eigenvectors (of norm 1) vary greatly in absolute value, so the spectral measure may be very different to the empiric spectral measure.

4.2. The Group G̃. The computation of the spectrum of π_{n} for G̃ amounts to the following proposition. As before, we define Δ̃_{n} = a_{n} + b̃_{n} + c̃_{n} + d̃_{n}, viewed as a 2^{n} × 2^{n} matrix, and let

Q̃_{n}(λ, μ) = Δ̃_{n} − (λ + 1)a_{n} − (μ + 2).

Proposition 4.6. Then for all n we have

Q̃_{n}(λ, μ) = \frac{1}{2}Q_{n}(2λ, 2μ).

Proof. The proof follows by recurrence on n: first it is readily checked that Q̃_{0}(λ, μ) = (1 − μ − λ); then for n ≥ 1 we compute

\frac{1}{2}Q_{n}(2λ, 2μ) = \frac{1}{2} (\begin{matrix}2a_{n−1} − 2μ & −2λ \\ −2λ & Δ_{n−1} − a_{n−1} − (2μ + 1) \end{matrix})

= (\begin{matrix}a_{n−1} − μ & −λ \\ −λ & \frac{1}{2}Q_{n−1}(0, 2μ) \end{matrix}) = (\begin{matrix}a_{n−1} − μ & −λ \\ −λ & Q̃_{n−1}(0, μ) \end{matrix})

= (\begin{matrix}a_{n−1} − μ & −λ \\ −λ & Δ̃_{n−1} − a_{n−1} − (μ + 2) \end{matrix}) = Q̃_{n}(λ, μ).

We can now obtain the spectrum of π_{n} by setting λ = −1 in Q̃_{n}(λ, μ) and solving for μ; in view of the previous proposition and the computations performed for G_{n}, we obtain:

Proposition 4.7. The spectrum of G̃_{n} is

\{2 + 2 cos (\frac{2πj}{2^{n+1}} )| j = 0, …, 2^{n} − 1\} .

Proof. The spectrum consists precisely of the μ + 2 such that Q̃_{n}(−1, μ) = 0; this amounts to Q_{n}(−2, 2μ) = 0. Now this holds when Φ_{0}(−2, 2μ) = 0, Φ_{1}(−2, 2μ) = 0 or 4 − (2μ)^{2} + 4 − 4 cos(2πj/2^{n})(−2) = 0 for some j = 1, …, 2^{n−1} − 1. These give respectively μ = 2, μ = 0 and μ = ±\sqrt{2 − 2 cos(2πj/2^{n})}, which after simplification yield the proposition.

The first eigenvalues are 4; 2; 2 ± \sqrt{2}; 2 ± \sqrt{2 ± \sqrt{2}}; 2 ± \sqrt{2 ± \sqrt{2 ± \sqrt{2}}}; etc.

Corollary 4.8. The spectrum of π, for the group G̃, is

spec(Δ) = [0, 4].

Note that the spectrum of Δ is positive! This can never happen to regular representations [HRV93a], and indeed the spectrum of the regular representation of G̃ is [−4, 4], since it contains [0, 4] and is symmetrical about 0 (as the Cayley graph C(G̃, S) is bipartite).

Again we may compute the empiric spectral measure τ_{Δ}. Recall that there is a measure-preserving map χ : [0, π] → ℝ given by θ ↦ 2+2 cos θ, where [0, π] has the Lebesgue measure. The measure dτ_{Δ} = g(x)dx we are seeking is then associated to

g(x) = \frac{1}{π} \frac{∂}{∂x}χ^{−1}(x) = \frac{1}{π\sqrt{4x − x^{2}}} .

4.3. The Group Γ. Recall that the finite quotient Γ_{n} acts faithfully on {0, 1, 2}^{n}. Denote by a_{n} and s_{n} the matrices of the action. We have

a_{0} = s_{0} = (1),

a_{n} = (\begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}) , s_{n} = (\begin{matrix}a_{n−1} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & s_{n−1} \end{matrix}) .

ON THE SPECTRUM OF HECKE TYPE OPERATORS RELATED TO SOME FRACTAL GROUPS 29

The combinatorial Laplacian of Γ_{n} is

Δ_{n} = a_{n} + a_{n}^{−1} + s_{n} + s_{n}^{−1} = (\begin{matrix}a_{n−1} + a_{n−1}^{−1} & 1 & 1 \\ 1 & a_{n−1} + a_{n−1}^{−1} & 1 \\ 1 & 1 & s_{n−1} + s_{n−1}^{−1} \end{matrix}) .

For ease of notation, let us define operators

A_{n} = a_{n} + a_{n}^{−1}, S_{n} = s_{n} + s_{n}^{−1},

Q_{n}(λ, μ) = S_{n} + λA_{n} − μ,

and polynomials

α = 2 − μ + λ, β = 2 − μ − λ,
γ = μ^{2} − λ^{2} − μ − 2, δ = μ^{2} − λ^{2} − 2μ − λ.

Lemma 4.9. We have

|Q_{0}(λ, μ)| = 2 + 2λ − μ = α + λ,
|Q_{1}(λ, μ)| = (2 + 2λ − μ)(2 − λ − μ)^{2} = (α + λ)β^{2},

|Q_{n}(λ, μ)| = (αβγ^{2})^{3^{n−2}} |Q_{n−1} (\frac{λ^{2}β}{αγ} , μ + \frac{2λ^{2}δ}{αγ} )| (n ≥ 2).

Proof. We compute the determinant:

|Q_{n}(λ, μ)| = |S_{n} + λA_{n} − μ| = |\begin{matrix}A_{n−1} − μ & λ & λ \\ λ & 2 − μ & λ \\ λ & λ & S_{n−1} − μ \end{matrix}|

= |\begin{matrix}2 − μ − λ & λ + μ − A_{n−1} & 0 \\ λ & A_{n−1} − μ & λ \\ λ & λ & S_{n−1} − μ \end{matrix}|

= |\begin{matrix}1 & 0 & 0 \\ ∗ & (2 − μ)A_{n−1} + (μ^{2} − λ^{2} − 2μ) & λ \\ ∗ & λA_{n−1} + λ(2 − 2λ − 2μ) & S_{n−1} − μ \end{matrix}|

= |S_{n−1} − μ − \frac{λ^{2}(1 − 2λ − μ + A_{n−1})}{(1 − μ)A_{n−1} + μ^{2} − λ^{2}} | · |(1 − μ)A_{n−1} + μ^{2} − λ^{2}|

= |S_{n−1} − μ + λ^{2} \frac{βA_{n−1} + 2δ}{αγ} | (αβγ^{2})^{3^{n−2}},

which completes the proof of the lemma, using the easily verified equations

\frac{1}{πA_{n} + ρ} = \frac{πA_{n} − π − ρ}{(2π + ρ)(π − ρ)},

|πA_{n} + ρ| = |\begin{matrix}ρ & π & π \\ π & ρ & π \\ π & π & ρ \end{matrix}|_{3^{n}} = ((π − ρ)^{2}(2π + ρ))^{3^{n−1}}

valid for all scalar π and ρ.

Consider now the quadratic forms H_{θ} = μ^{2} − λμ − 2λ^{2} − 2 − μ + θλ,

30 LAURENT BARTHOLDI AND ROSTISLAV I. GRIGORCHUK

Figure 5. The Functions F for Γ and \overline{Γ}

and the function F : [−4, 5] → [−4, 5] (see Figure 5 left) given by

F (θ) = 4 − 2θ − θ^{2}.

Let X_{2} = {−1}, and iteratively define X_{n} = F^{−1}(X_{n−1}) for all n ≥ 3. Note that |X_{n}| = 2^{n−2}. Lemma 4.10. We have for all n ≥ 2 the factorization

|Q_{n}(λ, μ)| = (2 + 2λ − μ)(2 − λ − μ)^{3^{n−1}+1} ∏_{\begin{matrix}2≤m≤n \\ θ∈X_{m} \end{matrix}} H_{θ}^{3^{n−m}+1}. (5)

Proof. Let us write temporarily

λ′ = \frac{λ^{2}β}{αγ} , μ′ = μ + \frac{2λ^{2}δ}{αγ} ,

and P′ = P (λ′, μ′) for P in {α, β, γ, δ, H_{θ}}. Then we have

α′ + λ′ = \frac{β(α + λ)}{α}, β′ = \frac{βH_{−1}}{γ} ,

H_{θ}(λ′, μ′) = \frac{β ∏_{ν∈F^{−1}(θ)} H_{ν}(λ, μ)}{αγ}.

μ  λ

Figure 6. The spectrum of Q_{n}(λ, μ) for Γ

Now, first Q_{2}(λ, μ) = (α+λ)β^{4}H_{−1}^{2} as claimed; then by induction, using Lemma 4.9, we have for n ≥ 3

|Q_{n}(λ, μ)| = (αβγ2)^{3^{n−2}} |Q_{n−1}(λ′, μ′)|

= (αβγ^{2})^{3^{n−2}}(α′ + λ′)β′^{3^{n−2}+1} ∏_{\begin{matrix}2≤m≤n−1 \\ θ∈X_{m} \end{matrix}} H′_{θ}^{3^{n−1−m}+1}

= (αβγ^{2})^{3^{n−2}} \frac{β(α + λ)}{α} (\frac{βH_{−1}}{γ} )^{3^{n−2}+1} (\frac{β}{αγ} )^{3^{n−2}−1} ∏_{\begin{matrix}2≤m≤n \\ θ∈X_{m} \end{matrix}} H_{θ}^{3^{n−m}+1}

= (α + λ)β^{3^{n−1}+1} ∏_{\begin{matrix}2≤m≤n \\ θ∈X_{m} \end{matrix}} H_{θ}^{3^{n−m}+1}

as claimed.

Thus, according to the previous proposition, the spectrum of Q_{n} is a collection of two lines and 2^{n−1} − 1 hyperbolæ H_{θ} with θ ∈ X_{2} ⊔ X_{3} ⊔ ⋯ ⊔ X_{n}. The spectrum of Δ_{n} is obtained by solving |Q_{n}(1, μ)| = 0, as given in the following proposition.

Figure 7. The Cantor-Set spectrum of Δ_{n} for Γ

Proposition 4.11. Let π_{±} : [−4, 5] → [−2, 4] be defined by π_{±}(θ) = 1 ± \sqrt{5 − θ}. Then

spec Δ_{0} = {4};
spec Δ_{1} = {1, 4};

spec Δ_{n} = {1, 4} ∪ ⋃_{2≤m≤n} π_{±}(X_{m}) (n ≥ 2).

Proof. Solving H_{θ}(1, μ) = 0 gives μ = π_{±}(θ). The result then follows from the factorization of |Q_{n}| as a product of H_{θ}’s given by Lemma 4.15.

Lemma 4.12. Let F : [a, b] → ℝ be a smooth unimodal map with negative Schwartzian derivative (for instance, a quadratic map), and F (a) = F (b) = a. Choose ξ ∈ [a, b], and form

K = ⋂_{n=0}^{∞} F^{−n}([a, b]), L = \overline{⋃_{n=0}^{∞} F^{−n}(\{ξ\})}.

Then the following cases may occur:

F([a, b]) ⊂ [a, b]: Then K = [a, b].

F([a, b]) = [a, b]: Then K = L = [a, b].

F([a, b]) ⊃ [a, b]: Then K is a Cantor set of null Lebesgue measure. If ξ ∈ K, then L = K, otherwise L = K ⊔ C, where C is a countable set of isolated points accumulating on K.

Proof. In the first case: K is clearly [a, b], because F^{−1}([a, b]) = [a, b].

Now assume that F ([a, b]) ⊇ [a, b], and define two continuous maps g_{1}, g_{2} : [a, b] → [a, b] such that F^{−1}(x) = {g_{1}(x), g_{2}(x)}. Then Π = ⟨g_{1}, g_{2}⟩ is a free semigroup, because g_{1} and g_{2} have disjoint image-interiors.

In the second case: K is obviously all [a, b], because F^{−1}([a, b]) = [a, b]. Clearly Π-orbit of ξ, is dense in [a, b] = g_{1}([a, b]) ∪ g_{2}([a, b]), so its closure L is [a, b].

In the last case: we first show that K ⊆ L. Since K = g_{1}(K) ⊔ g_{2}(K), every point in K is specified by an infinite sequence of g_{i}’s applied to some point. Since the g_{i}’s are contracting, the choice of that point is unimportant — hence we may choose ξ, and this proves the claim. If ξ ∈ K, then clearly L ⊆ K and we are done. Otherwise, set C = ∪F^{−n}({ξ}), which is a countable set of isolated points. Clearly K and C are disjoint (else ξ would be in K). Finally C accumulates on the infinite orbits under ⟨g_{1}, g_{2}⟩, hence on K.

Let O = [a, b] \ F^{−1}([a, b]). Then O disconnects [a, b], and F^{−1}(O) disconnects each of the connected components of [a, b] \ O, etc., so K is disconnected. Take any point x ∈ K; then for all n ∈ ℕ we may write x = w(x_{n}) for some x_{n} ∈ K and some word w ∈ Π of length n. Taking some x′_{n} ∈ K close to x_{n} and letting n tend to infinity gives a sequence in K converging to x. Since K is clearly closed, it is perfect, so is a Cantor set. Finally m(K) = lim_{n→∞}(1 − m(O))^{n} = 0, where m denotes the Lebesgue measure.

Let us make a few remarks concerning this lemma:

• The behaviour of L in the first case seems unpredictable. It is fortunately not needed for our purposes.

• The second case arises in connection with G and G̃, the third (with ξ ∉ K) with Γ and (with ξ ∈ K) with \overline{Γ} and \overline{\overline{Γ}}.

• Much more is known on the forward and inverse orbits of points under a unimodal map. See for instance [dMvS93, pages 10 and 327–351] for more information.

• K is the Julia set of the dynamical system F, i.e. the closure of the set of points whose (forward) orbit does not diverge to infinity. Indeed K consists precisely in those points whose orbit remains in [a, b]. Examples of Julia sets of a similar nature (occurring in the study of the quadratic map), with nested square-root expressions, appear in [Bar88, page 277] — see also the bibliography there.

The previous lemma gives the structure of the spectrum of Γ:

Corollary 4.13. The spectrum of π for the group Γ is the closure of the set

\{ \begin{matrix}4 & (μ = 0) \\ 1 & (μ = \frac{1}{3}) \\ 1 ± \sqrt{6} & (μ = \frac{1}{9}) \\ 1 ± \sqrt{6 ± \sqrt{6}} & (μ = \frac{1}{3^{3}} ) \\ 1 ± \sqrt{6 ± \sqrt{6 ± \sqrt{6}}} & (μ = \frac{1}{3^{4}} ) \\ … \end{matrix} \} .

It is the union of a Cantor set of null Lebesgue measure that is symmetrical about 1, and a countable collection of isolated points supporting the empiric spectral measure, which has the values indicated as μ.

4.4. The Group \overline{Γ}. Recall the finite quotient Γ_{n} acts faithfully on \{0, 1, 2\}^{n}. Denote by a_{n} and t_{n} the matrices of this action. We have

a_{0} = t_{0} = (1),

a_{n} = (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) , t_{n} = (\begin{matrix}a_{n−1} & 0 & 0 \\ 0 & a_{n−1} & 0 \\ 0 & 0 & t_{n−1} \end{matrix}) .

The combinatorial Laplacian of Γ_{n} is

Δ_{n} = a_{n} + a_{n}^{−1} + t_{n} + t_{n}^{−1} = (\begin{matrix}a_{n−1} + a_{n−1}^{−1} & 1 & 1 \\ 1 & a_{n−1} + a_{n−1}^{−1} & 1 \\ 1 & 1 & t_{n−1} + t_{n−1}^{−1} \end{matrix}) .

For ease of notation, let us define operators

A_{n} = a_{n} + a_{n}^{−1}, T_{n} = t_{n} + t_{n}^{−1},
Q_{n}(λ, μ) = T_{n} + λA_{n} − μ,

and polynomials

α = 2 − μ + λ, β = 2 − μ − λ,
γ = 1 + μ + λ, δ = 1 + μ − λ.

Lemma 4.14. We have

|Q_{0}(λ, μ)| = α + λ,
|Q_{1}(λ, μ)| = (α + λ)β^{2},

|Q_{n}(λ, μ)| = (γδ)^{2·3^{n−2}}(αβ)^{3^{n−2}} |Q_{n−1} (\frac{−2λ^{2}}{αδ} , μ + \frac{2λ^{2}(μ − λ − 1)}{αδ})| (n ≥ 2).

ON THE SPECTRUM OF HECKE TYPE OPERATORS RELATED TO SOME FRACTAL GROUPS 35

Proof. We compute the determinant:

|Q_{n}(λ, μ)| = |T_{n} + λA_{n} − μ| = |\begin{matrix}A_{n−1} − μ & λ & λ \\ λ & A_{n−1} − μ & λ \\ λ & λ & T_{n−1} − μ \end{matrix}|

= |\begin{matrix}A_{n−1} − μ − λ & 0 & 0 \\ λ & A_{n−1} − μ + λ & λ \\ λ & 2λ & T_{n−1} − μ \end{matrix}|

= |T_{n−1} − μ − \frac{2λ^{2}}{A_{n−1} − μ + λ}| · |A_{n−1} − μ + λ| · |A_{n−1} − μ − λ|

= |T_{n−1} − μ − 2λ^{2} \frac{A_{n−1} + μ − λ − 1}{(2 − μ + λ)(1 + μ − λ)}| · |A_{n−1} − μ + λ| · |A_{n−1} − μ − λ|

which completes the proof of the lemma, using the easily verified equations

\frac{1}{A_{n} − θ} = \frac{A_{n} + θ − 1}{(2 − θ)(1 + θ)},

|A_{n} − θ| = |\begin{matrix}−θ & 1 & 1 \\ 1 & −θ & 1 \\ 1 & 1 & −θ \end{matrix}|_{3^{n−1}} = ((θ + 1)^{2}(2 − θ))^{3^{n−1}}

valid for all scalar θ.

Consider again the quadratic forms

H_{θ} = μ^{2} − λμ − 2λ^{2} − 2 − μ + θλ,

and consider the real function (see Figure 5 right)

F (θ) = \frac{12 + θ − θ^{2}}{2} .

Let X_{3} = {2}, Y_{3} = {−1} and iteratively define X_{n} = F^{−1}(X_{n−1}) and Y_{n} = F^{−1}(Y_{n−1}) for all n ≥ 4. Note that |X_{n}| = |Y_{n}| = 2^{n−3}. Lemma 4.15. We have for all n ≥ 2 the factorization

|Q_{n}(λ, μ)| = (α + λ)β^{3^{n−2}+1}γ^{3^{n−1}−1}(δ − λ)^{3^{n−2}−1} ∏_{\begin{matrix}3≤m≤n \\ θ∈X_{m} \end{matrix}} H_{θ}^{3^{n−m}+1} ∏_{\begin{matrix}3≤m<n \\ θ∈Y_{m} \end{matrix}} H_{θ}^{3^{n−m}−1} ∏_{θ∈X_{n+1}} H_{θ}^{2}. (6)

Proof. Let us write temporarily

λ′ = \frac{−2λ^{2}}{αδ} , μ′ = μ + \frac{2λ^{2}(μ − λ − 1)}{αδ},

and P′ = P (λ′, μ′) for P in {α, β, γ, δ, H_{θ}}. Then we have

α′ + λ′ = \frac{β(α + λ)}{α}, β′ = \frac{−H_{2}}{δ} , γ′ = \frac{γ(δ − λ)}{δ}, δ′ − λ′ = \frac{−H_{−1}}{α} ,

H_{θ}(λ′, μ′) = \frac{∏_{ν∈F^{−1}(θ)} H_{ν}(λ, μ)}{αδ}.

Now, first Q_{2}(λ, μ) = (α+λ)β^{2}γ^{2}H_{2}^{2} as claimed; then by induction, using Lemma 4.14, we have for n ≥ 3

|Q_{n}(λ, μ)| = (γδ)^{2·3^{n−2}}(αβ)^{3^{n−2}} |Q_{n−1}(λ′, μ′)|

= (γδ)^{2·3^{n−2}}(αβ)^{3^{n−2}}(α′ + λ′)β′^{3^{n−3}+1}γ′^{3^{n−2}−1}(δ′ − λ′)^{3^{n−3}−1}

∏_{\begin{matrix}3≤m≤n−1 \\ θ∈X_{m} \end{matrix}} H′_{θ}^{3^{n−1−m}+1} ∏_{\begin{matrix}3≤m<n−1 \\ θ∈Y_{m} \end{matrix}} H′_{θ}^{3^{n−1−m}−1} ∏_{θ∈X_{n}} H′_{θ}^{2}

= (γδ)^{2·3^{n−2}}(αβ)^{3^{n−2}} \frac{β(α + λ)}{α} (\frac{−H_{2}}{δ} )^{3^{n−3}+1} (\frac{γ(δ − λ)}{δ})^{3^{n−2}−1} (\frac{−H_{−1}}{α} )^{3^{n−3}−1}

(αδ)^{−2·3^{n−3}} ∏_{\begin{matrix}4≤m≤n \\ θ∈X_{m} \end{matrix}} H_{θ}^{3^{n−m}+1} ∏_{\begin{matrix}4≤m<n \\ θ∈Y_{m} \end{matrix}} H_{θ}^{3^{n−m}−1} ∏_{θ∈X_{n+1}} H_{θ}^{2}.

= (α + λ)β^{3^{n−2}+1}γ^{3^{n−1}−1}(δ − λ)^{3^{n−2}−1} ∏_{\begin{matrix}3≤m≤n \\ θ∈X_{m} \end{matrix}} H_{θ}^{3^{n−m}+1} ∏_{\begin{matrix}3≤m<n \\ θ∈Y_{m} \end{matrix}} H_{θ}^{3^{n−m}−1} ∏_{θ∈X_{n+1}} H_{θ}^{2}

as claimed.

Thus, according to the previous proposition, the spectrum of Q_{n} is a collection of 4 lines and (2^{n−1} − 1) + (2^{n−3} − 1) hyperbolæ H_{θ} with θ ∈ X_{3} ⊔ ⋯ ⊔ X_{n+1} ⊔ Y_{3} ⊔ ⋯ ⊔ Y_{n−1}. The spectrum of Δ_{n} is obtained by solving |Q_{n}(1, μ)| = 0, as given in the following proposition.

Proposition 4.16. Let π_{±} : [−4, 5] → [−2, 4] be defined by π_{±}(θ) = 1 ± \sqrt{5 − θ}. Then

spec Δ_{0} = {4};
spec Δ_{1} = {1, 4};

spec Δ_{n} = {−2, 1, 4} ∪ ⋃_{3≤m≤n+1} π_{±}(X_{m}) ∪ ⋃_{3≤m≤n−1} π_{±}(Y_{m}) (n ≥ 2).

Proof. Solving H_{θ}(1, μ) = 0 gives μ = π_{±}(θ). The result then follows from the factorization of |Q_{n}| as a product of H_{θ}’s given by Lemma 4.15.

Corollary 4.17. The spectrum of π for the group \overline{Γ} is the closure of the set

\{ \begin{matrix}4 & (μ = 0) \\ −2 & (μ = \frac{1}{3}) \\ 1 & (μ = \frac{2}{9}) \\ 1 ± \sqrt{\frac{9±3}{2}} & (μ = \frac{2}{27}) \\ 1 ± \sqrt{\frac{9±\sqrt{45±4·3}}{2}} & (μ = \frac{2}{3^{4}} ) \\ 1 ± \sqrt{\frac{9±\sqrt{45±4\sqrt{45±4·3}}}{2}} & (μ = \frac{2}{3^{5}} ) \\ … \end{matrix} \} .

It is a Cantor set of null Lebesgue measure that is symmetrical about 1. The empiric spectral measure is concentrated on the above algebraic numbers and has the values indicated as μ.

μ  λ
Figure 8. The spectrum of Q_{n}(λ, μ) for \overline{Γ} and \overline{\overline{Γ}}

4.5. The Group \overline{\overline{Γ}}. Although \overline{Γ} and \overline{\overline{Γ}} greatly differ in structure—the former is virtually torsion-free while the latter is torsion—their representations π_{n} have the same spectrum:

Proposition 4.18. The spectrum of \overline{\overline{Γ}} is the same as that of \overline{Γ}; that is, a Cantor set symmetrical about 1 and spanning from −2 to 4.

Proof. It suffices to note that for all n we have r_{n} + r_{n}^{−1} = t_{n} + t_{n}^{−1}; this follows by induction on n.

5. Schreier Graphs

Recall from Section 3 the definition of a Schreier graph. In the general setting of a group G acting level-transitively on a tree Σ^{∗}, and a subgroup P defined as the stabilizer of an infinite path, the quotient space G/P is naturally identified with an orbit, i.e. a countable subset, of Σ^{ℕ}. For the finite quotients G_{n}, the space G_{n}/P_{n} is identified with Σ^{n}. We set G_{n} denote the Schreier graph associated to this homogeneous space. Due to the fractal (or recursive) nature of the five examples we study, there are simple local rules producing G_{n+1} from G_{n}, the limit of this

Figure 9. The Cantor-Set spectrum of Δ_{n} for \overline{Γ} and \overline{\overline{Γ}}

process being the Schreier graph of G/P. We describe these rules for our examples: G, G̃, Γ, \overline{Γ}, \overline{\overline{Γ}}.

5.1. S(G, P, S). We describe the graphs G_{n} = S(G_{n}, P_{n}, S). They will be with edges labeled by S (and not oriented, because all s ∈ S are involutions) and vertices labeled by Σ^{n}, where Σ = {0, 1}.

First, it is clear that G_{0} is a graph on one vertex, labeled by the empty sequence ∅, and four loops at this vertex, labeled by a, b, c, d. Next, G_{1} has two vertices, labeled by 0 and 1; an edge labeled a between them; and three loops at 0 and 1 labeled by b, c, d.

Now given G_{n}, for some n ≥ 1, perform on it the following transformation: replace the edge-labels b by d, d by c, c by b; replace the vertex-labels σ by 1σ; and replace all edges labeled by a connecting σ and τ by: edges from 1σ to 0σ and from 1τ to 0τ, labeled a; two edges from 0σ to 0τ labeled b and c; and loops at 0σ and 0τ labeled d. We claim the resulting graph is G_{n+1}.

To prove the claim, it suffices to check that the letters on the edge-labels act as described on the vertex-labels. If b(σ) = τ, then d(1σ) = 1τ, and similarly for c and d; this explains the cyclic permutation of the labels b, c, d. The other substitutions are verified similarly.

As an illustration, here are G_{2} and G_{3} for G:

a ^{...........................................................................................................................} ^{...........................................................................................................................} b, c  a 10 b, c, d  00 d  01 d  11 b, c, d

a ^{...........................................................................................................................} ^{...........................................................................................................................} b, d  a ^{...........................................................................................................................} ^{...........................................................................................................................} b, c  a ^{...........................................................................................................................} ^{...........................................................................................................................} b, d  a 110 b, c, d  010 c  000 c  100 d  101 d  001 c  011 c  111 b, c, d

The graphs G_{2} and G_{3} for G̃ are similar:

a  b  a 10 b, c, d  00 c, d  01 c, d  11 b, c, d

a  d  a  b  a  d  a 110 b, c, d  010 b, c  000 b, c  100 c, d  101 c, d  001 b, c  011 b, c  111 b, c, d

5.2. S(Γ, P, S). Recall that for Γ we take Σ = {0, 1, 2}. Let us write G_{n} = S(Γ, P_{n}, S). First, G_{0} has one vertex, labeled by the empty sequence ∅, and four loops, labeled a, a^{−1}, t, t^{−1}. Next, G_{1} has three vertices, labeled 0, 1, 2, cyclically connected by a triangle labeled a, a^{−1}, and with two loops at each vertex, labeled t, t^{−1}. In the pictures only geometrical edges, in pairs {a, a^{−1}} and {t, t^{−1}}, are represented.

Now given G_{n}, for some n ≥ 1, perform on it the following transformation: replace the vertex-labels σ by 2σ; replace all triangles labeled by a, a^{−1} connecting ρ, σ, τ by: three triangles labeled by a, a^{−1} connecting respectively 0ρ, 1ρ, 2ρ and 0σ, 1σ, 2σ and 0τ, 1τ, 2τ; a triangle labeled by t, t^{−1} connecting 0ρ, 0σ, 0τ; and loops labeled by t, t^{−1} at 1ρ, 1σ, 1τ. We claim the resulting graph is G_{n+1}.

As above, it suffices to check that the letters on the edge-labels act as described on the vertex-labels. If a(ρ) = σ and t(ρ) = τ, then t(0ρ) = 0σ, t(1ρ) = 1ρ and t(2σ) = 2τ. The verification for a edges is even simpler.

5.3. Substitutional graphs. The three Schreier graphs presented in the previous subsection are special cases of substitutional graphs, which we define below.

Substitutional graphs were introduced in the late 70’s to describe growth of multicellular organisms. They bear a strong similarity to L-systems [RS80], as was noted by Mikhael Gromov [Gro84]. Another notion of graph substitution has been studied by [Pre98], where he had the same convergence preoccupations as us.

Let us make a conventions in this section: all graphs G = (V (G), E(G)) shall be labeled, i.e. endowed with a map E(G) → C for a fixed set C of colours, and pointed, i.e. shall have a distinguished vertex ∗ ∈ V (G). A graph embedding G′ ↪ G is just an injective map E(G′) → E(G) preserving the adjacency operations.

Definition 5.1. A substitutional rule is a tuple (U, R_{1}, …, R_{n}), where U is a finite d-regular edge-labeled graph, called the axiom, and each R_{i} is a rule of the form X_{i} → Y_{i}, where X_{i} and Y_{i} are finite edge-labeled graphs. The graphs X_{i} are required to have no common edge. Furthermore, there is a inclusion, written ι_{i}, of the Figure 10. The Schreier Graph of Γ_{6}. The edges represent the generators s and a.

vertices of X_{i} in the vertices of Y_{i}; the degree of ι_{i}(x) is the same as the degree of x for all x ∈ V (X_{i}), and all vertices of Y_{i} not in the image of ι_{i} have degree d.

Given a substitutional rule, one sets G_{0} = U and constructs iteratively G_{n+1} from G_{n} by listing all embeddings of all X_{i} in G_{n} (they are disjoint), and replacing them by the corresponding Y_{i}. If the base point ∗ of G_{n} is in a graph X_{i}, the base point of G_{n+1} will be ι_{i}(∗).

Note that this expansion operation preserves the degree, so G_{n} is a d-regular finite graph for all n. We are interested in fixed points of this iterative process.

For any R ∈ ℕ, consider the balls B_{n}(∗, R) of radius R at the base point ∗ in G_{n}. Since there is only a finite number of rules, there is an infinite sequence n_{0} < n_{1} < … such that the balls B_{n_{i}}(∗, R) ⊆ G_{n_{i}} are all isomorphic. We consider G, a limit graph in the sense of [GŻ97] (the limit exists), and call it a substitutional graph.

Note that in case some rule X_{i} → Y_{i} does not satisfy X_{i} ⊂ Y_{i}, there may be more than one limit graph — this is the case in the following example (where there are in fact three limit graphs, according to whether the next-to-rightmost edge is b, c or b, d or c, d).

Theorem 5.2. The following four substitutional rules describe the Schreier graph of G:

[figure: a; σ; τ; b; σ; τ; c; σ; τ; d; σ; τ; a; ^{...............................................................} ^{...............................................................}; b, c; a; d; d; 1σ; 0σ; 0τ; 1τ; d; 1σ; 1τ; b; 1σ; 1τ; c; 1σ; 1τ; axiom; b, c, d; a; 0; 1]

where the vertex inclusions are given by σ ↦ 1σ and τ ↦ 1τ. The base point is the vertex 111 . . ..

Proof. Consider the Schreier graph G_{n} associated to the action of G on Σ^{n}, the n-th level of the tree T_{Σ}. The vertex set of G_{n} is Σ^{n}, and its edges are described by the action of G. Note first that the axiom is G_{0}.

We construct G_{n+1} from G_{n}. Split Σ^{n+1} as 0Σ^{n} ⊔1Σ^{n}. By virtue of the definition of ϕ given in (2), the b, c, d-edges within 1Σ^{n} are in bijection to the c, d, b-edges in G_{n}, while the b, c-edges within 0Σ^{n} are in bijection with the a-edges in G_{n}, and there are d-loops at all σ ∈ 0Σ^{n}. Moreover there are “parallel edges” labeled a between 0σ and 1σ for all σ ∈ Σ^{n}.

Now consider any b, c, d-edge in G_{n}, say between σ and τ. In G_{n+1}, it gives rise to a d, b, c-edge between 1σ and 1τ.

Consider then an a-edge in G_{n} between σ and τ. In G_{n+1}, it gives rise to the following subgraph: an a-edge from 1σ to 0σ; two edges, labeled b and c, from 0σ to 0τ; an a-edge from 0τ to 1τ; and two loops, labeled d at 0σ and 0τ. This is precisely the substitutional rule for a, completing the proof.

We omit the similar proof of the following result:

Theorem 5.3. The following four substitutional rules describe the Schreier graph of \overline{G}:

[figure: a; σ; τ; b̃; σ; τ; c̃; σ; τ; d̃; σ; τ; a; b̃; a; c̃, d̃; c̃, d̃; 1σ; 0σ; 0τ; 1τ; d̃; 1σ; 1τ; b̃; 1σ; 1τ; c̃; 1σ; 1τ; axiom; b̃, c̃, d̃; a; 0; 1]

where the vertex inclusions are given by σ ↦ 1σ and τ ↦ 1τ. The base point is the vertex 111 . . ..

Theorem 5.4. The substitutional rules producing the Schreier graphs of Γ and \overline{Γ} are given below. Remember that the Schreier graphs of \overline{Γ} and \overline{\overline{Γ}} are isomorphic:

Γ :  a a  a^{ρ}  ^{σ}^{τ}  \overline{}a a a^{2ρ} ^{1ρ} ^{0ρ}  a a a^{1σ} ^{0σ} ^{2σ} a a a^{0τ} ^{2τ}  ^{1τ} s  s s  axiom a a a^{2} s ^{1}  s^{0} s

\overline{Γ}, \overline{\overline{Γ}} :  a a  a^{ρ}  ^{σ}^{τ}  \overline{}a a a^{2ρ} ^{1ρ} ^{0ρ}  a a a^{1σ} ^{0σ} ^{2σ} a a a^{0τ}  ^{2τ} ^{1τ} t  t t  axiom a a a^{2} t ^{1}  t^{0} t

where the vertex inclusions are given by ρ ↦ 2ρ, σ ↦ 2σ and τ ↦ 2τ. The base point is the vertex 222 . . ..

Proof. We prove the claim for Γ only, as the same reasoning applies for \overline{Γ}. Consider the Schreier graph G_{n} associated to the action of G on Σ^{n}, the n-th level of the tree T_{Σ}. The vertex set of G_{n} is Σ^{n}, and its edges are described by the action of G. Note first that the axiom is G_{0}.

We construct G_{n+1} from G_{n}. Split Σ^{n+1} as 0Σ^{n} ⊔ 1Σ^{n} ⊔ 2Σ^{n}. By virtue of the definition of ϕ given in (3), the s-edges within 2Σ^{n} are in bijection to the s-edges in G_{n}, while the s-edges within 0Σ^{n} are in bijection with the a-edges in G_{n}, and there are s-loops at every σ ∈ 1Σ^{n}. Moreover there are “parallel triangles” labeled a between 0σ, 1σ and 2σ for all σ ∈ Σ^{n}.

Now consider any s-edge in G_{n}, say between σ and τ. In G_{n+1}, it remains an s-edge, but now between 2σ and 2τ.

Consider then an a-edge in G_{n} between σ and τ. In G_{n+1}, it gives rise to the following subgraph: an a-triangle between 0σ, 1σ and 2σ; an s-edge between 0σ and 0τ; s-loops at 1σ and 1τ; and an a-triangle between 0τ, 1τ and 2τ. Actually the a-edges form triangles so these subgraphs overlap at the a-triangles and s-loops. This justifies the substitutional rule for a-triangles, completing the proof.

By Proposition 2.11, the limit graphs have asymptotically polynomial growth of degree log_{2}(3).

Note that there are maps π_{n} : V (G_{n+1}) → V (G_{n}) that locally (i.e. in each copy of some right-hand rule Y_{i}) are the inverse of the embedding ι_{i}. In case these π_{n} are graph morphisms, and one can consider the projective system {G_{n}, π_{n}}, and its inverse limit Ĝ = \underleftarrow{lim} G_{n}, which is a profinite graph [RZ99]. We devote our attention to the discrete graph G = \underrightarrow{lim} G_{n}.

The growth series of G can often be described as an infinite product. We give such an expression for the graph in Figure 10, making use of the fact that G “looks like a tree” (even though it is amenable).

Consider the finite graphs G_{n}; recall that G_{n} has 3^{n} vertices. Let D_{n} be the diameter of G_{n} (maximal distance between two vertices), and let γ_{n} = ∑_{i∈ℕ} γ_{n}(i)X^{i} be the growth series of G_{n} (here γ_{n}(i) denotes the number of vertices in G_{n} at distance i from the base point ∗).

The construction rule for G implies that G_{n+1} can be constructed as follows: take three copies of G_{n}, and in each of them mark a vertex V at distance D_{n} from ∗. At each V delete the loop labeled s, and connect the three copies by a triangle labeled s at the three V ’s. It then follows that D_{n+1} = 2D_{n}+1, and γ_{n+1} = (1+2X^{D_{n}+1})γ_{n}. Using the initial values γ_{0} = 1 and D_{0} = 0, we obtain by induction

D_{n} = 2^{n} − 1, γ_{n} = ∏_{i=0}^{n−1}(1 + 2X^{2^{i}}).

We also have shown that the ball of radius 2^{n} around ∗ contains 3^{n} points, so the growth of G is at least n^{log_{2}(3)}. But Proposition 2.11 shows that it is also an upper bound, and we conclude:

Proposition 5.5. Γ is an amenable 4-regular graph whose growth function is transcendental, and admits the product decomposition

γ(X) = ∏_{i∈ℕ}(1 + 2X^{2^{i}}).

It is planar, and has polynomial growth of degree log_{2}(3).

Any graph is a metric space when one identifies each edge with a disjoint copy of an interval [0, L] for some L > 0. We turn G_{n} in a diameter-1 metric space by giving to each edge in G_{n} the length L = diam(G_{n})^{−1}. The family {G_{n}} then converges, in the following sense:

Let A, B be closed subsets of the metric space (X, d). For any ϵ, let A_{ϵ} = {x ∈ X| d(x, A) ≤ ϵ}, and define the Hausdorff distance

d_{X}(A, B) = inf{ϵ| A ⊆ B_{ϵ}, B ⊆ A_{ϵ}}.

This defines a metric on closed subsets of X. For general metric spaces (A, d) and (B, d), define their Gromov-Hausdorff distance

d^{GH}(A, B) = inf_{X,i,j} d_{X}(i(A), j(B)),

where i and j are isometric embeddings of A and B in a metric space X.

We may now rephrase the considerations above as follows: the sequence {G_{n}} is convergent in the Gromov-Hausdorff metric. The limit set G_{∞} is a compact metric space.

The limit spaces are then: for G and G̃, the limit G_{∞} is the interval [0, 1] (in accordance with its linear growth, see Proposition 2.11). The limit spaces for Γ, \overline{Γ} and \overline{\overline{Γ}} are fractal sets of dimension log_{2}(3).

When the present work was completed Stanislav Smirnov informed us about the article [Mal95] which has some connection to our paper. A substitutional tree T is constructed in [Mal95], and the spectrum of the Markov operator on T is of the form K ⊔ P, where K is the Julia set of some quadratic map and P is countable. The approximation arguments used in [Mal95] are different from ours and does not use any amenability assumption (indeed, the graphs constructed there have eigenvalues with compactly supported eigenvectors).

An essential difference is that the graph in [Mal95] is not regular and therefore is not a Schreier graph of a group.

6. Concluding Remarks and Problems

Let us draw here some conclusions and formulate a few questions. We hope that our methods will prove useful in the investigation of spectral properties of the Laplace operator Δ for other groups acting on rooted trees. By computing the spectrum of the Hecke type operator of a quasi-regular representation ρ_{G/P} we obtained a subset of the spectrum of Δ; namely, spec(ρ_{G/P}) ⊆ spec(ρ_{G}) as soon as P is amenable. Moreover, in one case (that of G̃) we obtained spec(Δ) using the bipartitivity of G̃’s Cayley graph. More research must be done in the nonamenable case, in particular

Question 1. Under which conditions (besides amenability) does one have spec(ρ_{G/P}) ⊆ spec(ρ_{G})? When does one have spec(ρ_{G/P}) = spec(ρ_{G})?

We also hope that the methods in this article can be useful to find residually finite examples of nonamenable groups without free subgroups (all known examples are non-residually-finite). The non-amenability of the group considered could be proven by showing that 1 is an isolated point in the spectrum of the associated dynamical system.

Question 2. Is there a finitely generated subgroup G of Aut(T ) with no nonabelian free subgroup and such that 1 ∉ spec(ρ_{G/P})?

Examples of groups G with 1 ∉ spec(ρ_{G/P}) are also interesting because they provide sequences of expanding graphs [Lub94], namely the Schreier graphs S(G, P_{n}, S). In some cases these graphs can be Ramanujan graphs. We formulate the following question with Andrzej Żuk:

Question 3. Are there groups G < Aut(T ), generated by a finite set S of finite automata, such that the sequence of graphs S(G, P_{n}, S) is (i) a sequence of expanders; (ii) a sequence of Ramanujan graphs?

The problem of factoring the resolvent of operators of Hecke type is related to the decomposition of ρ_{G/P_{n}} in irreducible representations. It can be shown that any finite-dimensional irreducible representation of G is a subrepresentation in a tensor product of sufficiently many copies of ρ_{G/P_{n}} (in other words, the representation ring R(G) is generated by the irreducible subrepresentations of ρ_{G/P_{n}}). We therefore hope that our methods will extend the knowledge on the irreducible representations of G.

We constructed a virtually torsion-free group, Γ, with totally disconnected spectrum spec(ρ_{Γ/P}). To answer in the negative to the Baum-Connes conjecture, as well as to the Kadison-Kaplansky conjecture [Val89], it would suffice to construct a torsion-free group with a gap in the spectrum of its Laplace operator. Therefore one should delete the “virtually” and replace ρ_{Γ/P} by ρ_{Γ} in order to improve our results.

Question 4. Is there a torsion-free group G < Aut(T ) with totally disconnected spectrum spec(ρ_{G})? Or with a gap in its spectrum?

7. Acknowledgments

Both authors wish to thank heartily Pierre de la Harpe for his constant availability and interest. Viviane Baladi, Marc Burger, Vaughan Jones, Volodymyr Nekrashevych, Gilles Robert, Alain Valette and Andrzej Żuk contributed by generous discussions and input.

References

[Bar88] Michael Barnsley, Fractals everywhere, Academic Press Inc., Boston, MA, 1988.

[Bar99] Laurent Bartholdi, A class of groups acting on rooted trees, in progress, 1999.

[Bau93] Gilbert Baumslag, Topics in combinatorial group theory, Lectures in Mathematics, ETH Zürich, Birkhäuser Verlag, Basel, 1993.

[BG98] Laurent Bartholdi and Rostislav I. Grigorchuk, On parabolic subgroups and quasiregular representations of some fractal groups, to appear, 1998.

[BH97] Marc Burger and Pierre de la Harpe, Constructing irreducible representations of discrete groups, Proc. Indian Acad. Sci. Math. Sci. 107 (1997), no. 3, 223–235.

[Bra84] Wilfried Brauer, Automatentheorie, B. G. Teubner, Stuttgart, 1984, Eine Einführung in die Theorie endlicher Automaten. [An introduction to the theory of finite automata].

[BS82] Jean Béllissard and B. Simon, Cantor spectrum for the almost Mathieu equation, J. Funct. Anal. 48 (1982), no. 3, 408–419.

[BVŻ97] Cédric Béguin, Alain Valette, and Andrzej Żuk, On the spectrum of a random walk on the discrete Heisenberg group and the norm of Harper’s operator, J. Geom. Phys. 21 (1997), no. 4, 337–356.

[CDS79] Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, Pure and Applied Mathematics, Academic Press, 1979.

[CGH99] Tullio G. Ceccherini-Silberstein, Rostislav I. Grigorchuk, and Pierre de la Harpe, Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces, Proc. Steklov Inst. Math. 224 (1999), 57–95.

[CHMM98] Alan L. Carey, Keith C. Hannabuss, Varghese Mathai, and Paul J. McCann, Quantum Hall effect on the hyperbolic plane, Comm. Math. Phys. 190 (1998), no. 3, 629–673.

[CMS98] Tullio G. Ceccherini-Silberstein, Antonio Machì, and Fabio Scarabotti, Un’introduzione al gruppo di grigorchuk, to appear, 1998.

[Con94] Alain Connes, Noncommutative geometry, Academic Press, San Diego, CA., 1994.

[Dix77] Jacques Dixmier, C^{∗}-algebras, North-Holland Mathematical Library, vol. 15, North Holland, Amsterdam, 1977, Translated from the French by Francis Jellett.

[dMvS93] Welington de Melo and Sebastian van Strien, One-dimensional dynamics, Springer-Verlag, Berlin, 1993.

[ECH^{+}92] David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups, Jones and Bartlett Publishers, 1992.

[Eil74] Samuel Eilenberg, Automata, languages, and machines, vol. A, Academic Press, 1974.

[Far98] Michael Farber, Geometry of growth: approximation theorems for L^{2} invariants, Math. Ann. 311 (1998), no. 2, 335–375.

[FG91] Jacek Fabrykowski and Narain Gupta, On groups with sub-exponential growth functions. II, J. Indian Math. Soc. (N.S.) 56 (1991), no. 1-4, 217–228.

[Føl57] Erling Følner, Note on groups with and without full Banach mean value, Math. Scand.

5 (1957), 5–11.

[GC71] Ferenc Gécseg and Béla Csákány, Algebraic theory of automata, Akademiami Kiado, Budapest, 1971.

[Glu61] Victor M. Gluškov, Abstract theory of automata, Uspehi Mat. Nauk 16 (1961), no. 5 (101), 3–62.

[Gri80] Rostislav I. Grigorchuk, On Burnside’s problem on periodic groups, Funktsional. Anal. i Prilozhen. 14 (1980), no. 1, 53–54, english translation: Functional Anal. Appl. 14 (1980), 41–43.

[Gri83] Rostislav I. Grigorchuk, On the Milnor problem of group growth, Dokl. Akad. Nauk SSSR 271 (1983), no. 1, 30–33.

[Gri84] Rostislav I. Grigorchuk, 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, english translation: Math. USSR-Izv. 25 (1985), no. 2, 259–300.

[Gri85] Rostislav I. Grigorchuk, Degrees of growth of p-groups and torsion-free groups, Mat. Sb. (N.S.) 126(168) (1985), no. 2, 194–214, 286.

[Gri98] Rostislav I. Grigorchuk, Just infinite branched groups, Horizons in Profinite Groups (Marcus P. F. du Sautoy and Dan Segal, eds.), Birkhaüser (Basel), to appear (1998).

[Gro84] Mikhael Gromov, Infinite groups as geometric objects, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Warsaw, 1983) (Warsaw), PWN, 1984, pp. 385–392.

[GS83a] Narain Gupta and Said Sidki, On the Burnside problem for periodic groups, Math. Z. 182 (1983), 385–388.

[GS83b] Narain Gupta and Said Sidki, Some infinite p-groups, Algebra i Logika 22 (1983), no. 5, 584–589.

[GWW92] Carolyn Gordon, David L. Webb, and Scott Wolpert, One cannot hear the shape of a drum, Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 1, 134–138.

[GŻ97] Rostislav I. Grigorchuk and Andrzej Żuk, On the asymptotic spectrum of random walks on infinite families of graphs, Proceedings of the Conference “Random Walks and Discrete Potential Theory” (Cortona) (M. Picardello and W. Woess, eds.), Symposia Mathematica (Cambridge University Press), 22–28 June 1997, (to appear), pp. 134–150.

[Har] Pierre de la Harpe, Topics in geometric group theory, University of Chicago Press, to

appear; preprint at http://www.unige.ch/math/biblio/preprint/pp98.html.

[HK97] Nigel Higson and Gennadi G. Kasparov, Operator K-theory for groups which act properly and isometrically on Hilbert space, Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 131–142 (electronic).

[Hoř63] Jiří Hořejš, ��������������� ������������ ��������� ���������� (= trans-

formations, defined by finite automata), Problemy Kibernet. 9 (1963), 23–26.

[HRV93a] Pierre de la Harpe, A. Guyan Robertson, and Alain Valette, On the spectrum of the sum of generators for a finitely generated group, Israel J. Math. 81 (1993), no. 1–2, 65–96.

[HRV93b] Pierre de la Harpe, A. Guyan Robertson, and Alain Valette, On the spectrum of the sum of generators of a finitely generated group. II, Colloq. Math. 65 (1993), no. 1, 87–102.

[Kać96] Mark Kać, Can one hear the shape of a drum?, Amer. Math. Monthly 73 (1996),

no. 4, 1–23.

[Kaž65] David A. Každan, Uniform distribution on a plane, Trudy Moskov. Mat. Obšč. 14

(1965), 299–305.

[Kes59] Harry Kesten, Symmetric random walks on groups, Trans. Amer. Math. Soc. 92 (1959), 336–354.

[Li96] Wo Li, Number theory with applications, World Scientific, 1996.

[Lub94] Alexander Lubotzky, Discrete groups, expanding graphs and invariant measures, Birkhäuser Verlag, Basel, 1994.

[Lub95] Alexander Lubotzky, Cayley graphs: Eigenvalues, expanders and random walks, Surveys in combinatorics, 1995 (Stirling) (Cambridge), Cambridge Univ. Press, Cambridge, 1995, pp. 155–189.

[Lüc94] Wolfgang Lück, Approximating L^{2}-invariants by their finite-dimensional analogues,

Geom. Funct. Anal. 4 (1994), no. 4, 455–481.

[Lys85] Igor G. Lysionok, A system of defining relations for the Grigorchuk group, Mat. Zametki 38 (1985), 503–511.

[Mac76] George W. Mackey, The theory of unitary group representations, University of Chicago Press, Chicago, Ill., 1976, Based on notes by James M. G. Fell and David B. Lowdenslager of lectures given at the University of Chicago, Chicago, Ill., 1955, Chicago Lectures in Mathematics.

[Mal95] Leonid Malozemov, Random walk and chaos of the spectrum. Solvable model, Chaos Solitons Fractals 5 (1995), no. 6, 895–907.

[Mos81] Jürgen Moser, An example of a Schroedinger equation with almost periodic potential and nowhere dense spectrum, Comment. Math. Helv. 56 (1981), no. 2, 198–224.

[MV98] Florian Martin and Alain Valette, Markov operators on the solvable Baumslag-Solitar groups, to appear, 1998.

[Nov97] Sergueĭ P. Novikov, The Schrödinger operator on graphs, and topology, Uspekhi Mat. Nauk 52 (1997), no. 6(318), 177–178.

[NS99] Volodymyr V. Nekrashevych and Vitaliĭ I. Sushchansky, On confinal dynamics of rooted tree automorphisms, preprint, 1999.

[Pre98] Joseph P. Previte, Graph substitutions, Ergodic Theory Dynam. Systems 18 (1998), no. 3, 661–685.

[RS80] Grzegorz Rozenberg and Arto Salomaa, The mathematical theory of L systems, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1980.

[RZ99] Luis Ribes and Pavel Zalesskiĭ, Pro-p trees and applications, Birkhaüser, Basel, 1999, to appear in Horizons in Profinite Groups (Dan Segal ed.).

[Ser95] Jean-Pierre Serre, Cours d’arithmétique, quatrième ed., PUF, 1995.

[Ser97] Jean-Pierre Serre, Répartition asymptotique des valeurs propres de l’opérateur de Hecke T_{p}, J. Amer. Math. Soc. 10 (1997), no. 1, 75–102.

[Sid87a] Said Sidki, On a 2-generated infinite 3-group: subgroups and automorphisms, J. Algebra 110 (1987), no. 1, 24–55.

[Sid87b] Said Sidki, On a 2-generated infinite 3-group: the presentation problem, J. Algebra 110 (1987), no. 1, 13–23.

[Val89] Alain Valette, The conjecture of idempotents: A survey of the C^{∗}-algebraic approach, Bull. Soc. Math. Belg. Sér. A (1989), no. 3, 485–521.

[vN29] John von Neumann, Zur allgemeinen Theorie des Masses, Fund. Math. 13 (1929), 73–116 and 333, = Collected works, vol. I, pages 599–643.

[Woe94] Wolfgang Woess, Random walks on infinite graphs and groups — a survey on selected topics, Bull. London Math. Soc. 26 (1994), 1–60.

E-mail address: Laurent.Bartholdi@math.unige.ch    grigorch@mi.ras.ru

Section de Mathématiques Université de Genève CP 240, 1211 Genève 24 Switzerland Steklov Institute of Mathematics Gubkina 8 Moscow 117966 Russia