Integrable and Chaotic Systems Associated with Fractal Groups

Abstract

Fractal groups (also called self-similar groups) is the class of groups discovered by the first author in the 1980s with the purpose of solving some famous problems in mathematics, including the question of raising to von Neumann about non-elementary amenability (in the association with studies around the Banach-Tarski Paradox) and John Milnor’s question on the existence of groups of intermediate growth between polynomial and exponential. Fractal groups arise in various fields of mathematics, including the theory of random walks, holomorphic dynamics, automata theory, operator algebras, etc. They have relations to the theory of chaos, quasi-crystals, fractals, and random Schrödinger operators. One important development is the relation of fractal groups to multi-dimensional dynamics, the theory of joint spectrum of pencil of operators, and the spectral theory of Laplace operator on graphs. This paper gives a quick access to these topics, provides calculation and analysis of multi-dimensional rational maps arising via the Schur complement in some important examples, including the first group of intermediate growth and its overgroup, contains a discussion of the dichotomy “integrable-chaotic” in the considered model, and suggests a possible probabilistic approach to studying the discussed problems.

1. Introduction

Fractal groups are groups acting on self-similar objects in a self-similar way. The term “fractal group” was used for the first time in [1] and then appeared in [2]. Although there is no rigorous definition of a fractal group (like there is no rigorous definition of a fractal set), there is a definition of a self-similar group (see Definition 1). Self-similar groups act by automorphisms on regular rooted trees (like a binary rooted tree shown in Figure 1). Such trees are among the most natural and often used self-similar objects. The properties of self-similar groups and their structure resemble the self-similarity properties of the trees and their boundaries. The nicest examples come from finite Mealy type automata, like automata presented by Figure 2.

Moreover, there are several ways to associate geometric objects of fractal type with a self-similar group. This includes limits of Schreier graphs [1,3,4,5,6], limit spaces and limit solenoids of Nekrashevych [7,8,9,10], quasi-crystals [11], Julia sets [1,12], etc.

Self-similar groups were used to solve several outstanding problems in different areas of mathematics. They provide an elegant contribution to the general Burnside problem [13], to the J. Milnor problem on growth [14,15], to the von Neumann - Day problem on non-elementary amenability [15,16], to the Atiyah problem in $L^2$-Betti numbers [17], etc. Self-similar groups have applications in many areas of mathematics such as dynamical systems, operator algebras, random walks, spectral theory of groups and graphs, geometry and topology, computer science, and many more (see the surveys [2,4,11,18,19,20,21,22] and the monograph [12]).

Multi-dimensional rational maps appear in the study of spectral properties of graphs and unitary representations of groups (including representations of Koopman type). The spectral theory of such objects is closely related to the theory of joint spectrum of a pencil of operators in a Hilbert (or more generally in a Banach) space and is implicitly considered in [1] and explicitly outlined in [23].

There is some mystery regarding how multi-dimensional rational maps appear in the context of self-similar groups. There are basic examples like the first group $\mathcal{G}$ of intermediate growth from [13,14], the groups called “Lamplighter”, “Hanoi”, “Basilica”, Spinal Groups, GGS-groups, etc. The indicated classes of groups produce a large family of such maps, part of which is presented by examples (1)–(2) and (5)–(11).

These maps are very special and quite degenerate as claimed by N. Sibony and M. Lyubich, respectively. Nevertheless, they are interesting and useful, as, on the one hand, they are responsible for the associated spectral problems, on the other hand, they give a lot of material for people working in dynamics, being quite different from the maps that were considered before.

Some of them demonstrate features of integrability, which means that they semiconjugate to lower-dimensional maps, while the others do not seem to have integrability features and their dynamics (at least on an experimental level) demonstrate the chaotic behavior presented, for instance, by Figure 3.

The phenomenon of integrability, discovered in the basic examples including the groups $\mathcal{G}$, Lamplighter, and Hanoi, is thoroughly investigated by M-B. Dang, M. Lyubich and the first author in [24]. For examples of intermediate complexity, the criterion found in [24] based on the fractionality of the dynamical degree shows non-integrability; for instance, this is the case for the Basilica map (9). More complicated cases of maps, like the Basilica map, or higher-dimensional $\mathcal{G}$-maps given by (5) and (6) still wait for their resolution. An interesting phenomenon discovered in [25] is the relation of self-similar groups with quasi-crystals and random Schrödinger operators.

This article surveys and explores the use of self-similar groups in the dynamics of multi-dimensional rational maps and provides a panorama of ideas, methods, and applications of fractal groups.

2. Basic Examples

We begin with several examples of rational maps that arise from fractal groups. Only minimal information is given about each case. The main examples are related to the group $\mathcal{G}$ given by presentation (3), overgroup $\tilde{\mathcal{G}}$ given by matrix recursions (35), and generalized groups ${\mathcal{G}}_{\omega }$ given by (42). We begin with dimension 2 and then consider the higher-dimensional case given by (5), (6). The justification is given in Section 13.

2.1. Grigorchuk Group

Consider two maps

$$F:\left(\begin{array}{c}x\\ y\end{array}\right)\mapsto \left(\begin{array}{c}\frac{2x^2}{4-y^2}\\ y+\frac{x^{2}y}{4-y^2}\end{array}\right),$$

(1)

$$G:\left(\begin{array}{c}x\\ y\end{array}\right)\mapsto \left(\begin{array}{c}\frac{2(4-y^2)}{x^2}\\ -y-\frac{y(4-y^2)}{x^2}\end{array}\right).$$

(2)

They come from the group of intermediate growth, between polynomial and exponential [13,15]

$$\mathcal{G}=〈a,b,c,d|1=a^2=b^2=c^2=d^2=bcd={\sigma }^k\left({\left(ad\right)}^4\right)={\sigma }^k\left({\left(adacac\right)}^4\right),k=0,1,2,\dots 〉,$$

(3)

where

$$\sigma :a\to aca,b\to d,c\to b,d\to c$$

is a substitution. The maps F and G are related by $H\circ F=G$ and $H\circ G=F$, where H is the involutive map (i.e., $H\circ H=id$)

$$H:\left(\begin{array}{c}x\\ y\end{array}\right)\mapsto \left(\begin{array}{c}\frac{4}{x}\\ -\frac{2y}{x}\end{array}\right).$$

(4)

The point of interest is the dynamics of $F,G$ acting on ${\mathbb{R}}^2,{\mathbb{C}}^2$ or their projective counterparts and the dynamics of the subshift $({\Omega }_{\sigma },T)$ generated by the substitution $\sigma$ (which is briefly discussed in the Section 12).

The map F demonstrates features of an integrable map as it has two almost transversal families of horizontal hyperbolas ${\mathcal{F}}_{\theta }=\{(x,y):4+x^2-y^2-4\theta x=0\}$ and vertical hyperbolas ${\mathcal{H}}_{\eta }=\{(x,y):4-x^2+y^2-4\eta y=0\}$, shown in Figure 4. The first family $\left\{{\mathcal{F}}_{\theta }\right\}$ is invariant as a family and $F^{-1}\left({\mathcal{F}}_{\theta }\right)={\mathcal{F}}_{{\theta }_1}\bigsqcup {\mathcal{F}}_{{\theta }_2}$, where ${\theta }_1,{\theta }_2$ are preimages of $\theta$ under the Chebyshev map $\alpha :z\mapsto 2z^2-1$ (also known as the Ulam-von Neumann map), and the family $\left\{{\mathcal{H}}_{\eta }\right\}$ consists of invariant curves.

The map $\pi =\phi \times \psi$, where

$$\begin{array}{cc}\hfill \psi (x,y)=& \frac{4+x^2-y^2}{4x},\hfill \\ \hfill \phi (x,y)=& \frac{4-x^2+y^2}{4y},\hfill \end{array}$$

semiconjugates F to the map $id\times \alpha$ and as the dynamics of $\alpha$ is well understood, some additional arguments lead to;

Theorem 1

(Equidistribution Theorem [24]). Let Γ and S be two irreducible algebraic curves in ${\mathbb{C}}^2$ in coordinates $(\phi ,\psi )$ such that Γ is not a vertical hyperbola while S is not a horizontal hyperbola. Then

$$\frac{1}{2^n}[{\left(F^n\right)}^{\ast }\Gamma \cap S]\stackrel{n\to \infty }{\to }(deg\Gamma )·\left(degS\right)·{\omega }_S,$$

where ${\omega }_S$ is the restriction of the 1-form $\omega =\frac{d\psi }{\pi \sqrt{1-{\psi }^2}}$ to S, $[·]$ is the counting measure, and $F^n$ denotes the n-th iteration of F.

The set $\mathcal{K}$ shown in Figure 5a (we will call this set the “cross”) is of special interest for us as it represents the joint spectrum of several families of operators associated with the element $m(x,y)=-xa+b+c+d-(y+1)1$ of the group algebra $\mathbb{R}\left[\mathcal{G}\right]$ [1,20,26]. It can be foliated by the hyperbolas ${\mathcal{F}}_{\theta },-1\le \theta \le 1$ as shown in Figure 5b (or by hyperbolas ${\mathcal{H}}_{\eta },-1\le \eta \le 1$ shown in Figure 5c). The F-preimages of the border line $x+y=2$ constitutes a dense family of curves for $\mathcal{K}$ (the same is true for G-preimages) and $\mathcal{K}$ is completely invariant set for F or G (i.e., $F^{-1}\left(\mathcal{K}\right)\subset \mathcal{K}$ and $F\left(\mathcal{K}\right)\subset \mathcal{K}$, so $F\left(\mathcal{K}\right)=\mathcal{K}$).

The map F is comprehensively investigated in [24] (its close relative is studied in [27,28] from a different point of view) and serves as a basis for the integrability theory developed there. The map G happens to be more complicated and its study is ongoing.

F and G are low-dimensional relatives of ${\mathbb{C}}^5\to {\mathbb{C}}^5$ maps

$$\tilde{F}:\left(\begin{array}{c}x\\ y\\ z\\ u\\ v\end{array}\right)\mapsto \left(\begin{array}{c}\frac{x^2(y+z)}{(v+u+y+z)(v+u-y-z)}\\ u\\ y\\ z\\ v-\frac{x^2(v+u)}{(v+u+y+z)(v+u-y-z)}\end{array}\right),$$

(5)

$$\tilde{G}:\left(\begin{array}{c}x\\ y\\ z\\ u\\ v\end{array}\right)\mapsto \left(\begin{array}{c}y+z\\ -\frac{x^2(2vyz-u(v^2-u^2+y^2+z^2))}{(v+u+y+z)(v-u+y-z)(v+u-y-z)(v-u-y+z)}\\ -\frac{x^2(2vuz-y(v^2+u^2-y^2+z^2))}{(v+u+y+z)(v-u+y-z)(v+u-y-z)(v-u-y+z)}\\ -\frac{x^2(2vuy-z(v^2+u^2+y^2-z^2))}{(v+u+y+z)(v-u+y-z)(v+u-y-z)(v-u-y+z)}\\ v+u-\frac{x^2(2uyz-v(-v^2+u^2+y^2+z^2))}{(v+u+y+z)(v-u+y-z)(v+u-y-z)(v-u-y+z)}\end{array}\right),$$

(6)

that come from the 5-parametric pencil $xa+yb+zc+ud+v1\in \mathbb{R}\left[\mathcal{G}\right]$ [20]. The way how they were computed is explained in Section 13.

It is known that there is a subset $\Sigma \subset {\mathbb{R}}^5$ which is both $\tilde{F}$ and $\tilde{G}$-invariant, and the sections of which, by the lines parallel to the direction when $y=z=u$ are unions of two intervals (or an interval), while in all other directions it is a Cantor set of the Lebesgue measure zero. This follows from the results of D. Lenz, T Nagnibeda and the first author [25] and is based on the use of the substitutional dynamical system $({\Omega }_{\sigma },T)$ determined by substitution $\sigma$ (see Section 12 and also [11,25,29]).

The integrability criterion found in [24] clarifies the roots of integrability of the maps (7), (8) presented in the next two examples.

2.2. Lamplighter Group

The Lamplighter map

$$\left(\begin{array}{c}x\\ y\end{array}\right)\mapsto \left(\begin{array}{c}{\displaystyle \frac{x^2-y^2-2}{y-x}}\\ {\displaystyle \frac{2}{y-x}}\end{array}\right)$$

(7)

comes from the Lamplighter group $\mathcal{L}={\mathbb{Z}}_2\wr \mathbb{Z}=\left({\oplus }_{\mathbb{Z}}{\mathbb{Z}}_2\right)⋊\mathbb{Z}$ (where, ≀ and ⋊ denote the wreath product and the semidirect product, respectively) realized as a group generated by the automaton in Figure 2b (generation of groups by automata is explained in the next section). It has a family of invariant lines $l_c\equiv x+y=c$, and its restriction to $l_c$ is the Möbius map represented by the matrix

$$\left(\begin{array}{cc}c& -{\displaystyle \frac{c^2}{2}}-1\\ 1& -{\displaystyle \frac{c}{2}}\end{array}\right)\in SL(2,\mathbb{R}).$$

The Lamplighter map was used in [30,31] to describe unusual spectral properties of the Lamplighter group, and to answer the Atiyah question on $L^2$-Betti numbers [17].

2.3. Hanoi Group

The Hanoi map

$$\left(\begin{array}{c}x\\ y\end{array}\right)\mapsto \left(\begin{array}{c}x-{\displaystyle \frac{2(x^2-x-y^2)y^2}{(x-y-1)(x^2+y-y^2-1)}}\\ {\displaystyle \frac{(x+y-1)y^2}{(x-y-1)(x^2+y-y^2-1)}}\end{array}\right)$$

(8)

comes from the Hanoi group ${\mathcal{H}}^{\left(3\right)}$, associated with the Hanoi Towers Game on three pegs [32,33]. It is the group generated by the automaton in Figure 2c. As shown in [33], this map is semiconjugate by $\psi :{\mathbb{R}}^2\to \mathbb{R}$, $\psi (x,y)={\displaystyle \frac{1}{y}}(x^2-1-xy-2y^2)$ to the map $\beta :x\mapsto x^2-x-3$ and has an invariant set $\Sigma$ (the joint spectrum) shown in Figure 6.

The set $\Sigma$ is the closure of the family of hyperbolas $x^2-1-xy-2y^2-\theta y=0$ when ${\displaystyle \theta \in \bigcup _{i=0}^{\infty }{\beta }^{-i}\left(\theta \right)\cup \bigcup _{i=0}^{\infty }{\beta }^{-i}(-2)}$ and the intersection of $\Sigma$ by vertical lines is a union of a countable set of isolated points and a Cantor set to which this set of points accumulates. Theorem 8, stated later, describes the intersection of $\Sigma$ by horizontal line $y=1$.

In [32], higher-dimensional Hanoi groups ${\mathcal{H}}^{\left(n\right)}$, $n\ge 4$ are also introduced (the automaton generating ${\mathcal{H}}^{\left(4\right)}$ is presented by Figure 2d), but unfortunately so far it was not possible to associate any maps with these groups.

2.4. Basilica Group

The Basilica map

$$\left(\begin{array}{c}x\\ y\end{array}\right)\mapsto \left(\begin{array}{c}-2+{\displaystyle \frac{x(x-2)}{y^2}}\\ {\displaystyle \frac{2-x}{y^2}}\end{array}\right)$$

(9)

comes from the Basilica group, introduced in [34,35] as the group generated by the automaton in Figure 2e. The map in (9) is much more complicated than the other 2-dimensional maps described above. The dynamical picture representing points of bounded orbits (a kind of a Julia set) of the Basilica map is presented by Figure 7.

The Basilica group can also be defined as the Iterated Monodromy group $IMG(z^2-1)$ of the polynomial $z^2-1$ [2,12]. It is the first example of amenable but not subexponentially amenable group, as shown in [36]. For spectral properties of this group see [35,37].

2.5. Iterated Monodromy Group of $z^2+i$

The group $IMG(z^2+i)$ is the group generated by the automaton in Figure 2f. The map

$$\left(\begin{array}{c}y\\ z\\ \lambda \end{array}\right)\mapsto \left(\begin{array}{c}{\displaystyle \frac{z}{y}}\\ {\displaystyle \frac{1}{-y^2+z^2-2z\lambda +{\lambda }^2}}\\ {\displaystyle \frac{-\lambda y^2+\lambda z^2-2z{\lambda }^2+{\lambda }^3+z-\lambda }{y(-y^2+z^2-2z\lambda +{\lambda }^2)}}\end{array}\right),$$

(10)

introduced in [38], is responsible for the spectral problem associated with this group. It is conjugate to a simpler map

$$\left(\begin{array}{c}y\\ z\\ \lambda \end{array}\right)\mapsto \left(\begin{array}{c}{\displaystyle \frac{z}{y}}\\ {\displaystyle \frac{\lambda }{y}}(-2+y\lambda )\\ {\displaystyle \frac{1}{\lambda }}(-y-y{\lambda }^2-\lambda )\end{array}\right),$$

(11)

but, basically this is all that is known about this map.

3. Self-Similar Groups

Self-similar groups arise from actions on d-regular rooted trees $T_d$ (for $d\ge 2$), while self-similar (operator) algebras arise from d-similarities $\psi :H\to H^d=H\oplus \dots \oplus H$ on an infinite dimensional Hilbert space H, where $\psi$ is an isomorphism.

Let us begin with the definition of a self-similar group. Let $X=\{x_1,\dots ,x_d\}$ be an alphabet, $X^{\ast }$ be the set of finite words (including the empty word ∅) ordered lexiographically (assuming $x_1<x_2<\dots <x_d$), and let $T_d$ be a d-regular rooted tree with the set of vertices V identified with $X^{\ast }$ and set of edges $E=\{(w,wx)\mid w\in X^{\ast },x\in X\}$. The Figure 1 shows the binary rooted tree when $X=\{0,1\}$. Usually we will omit the index d in $T_d$. The root vertex corresponds to the empty word.

From a geometric point of view, the boundary $\partial T$ of the tree T consists of infinite paths (without back tracking) joining the root vertex with infinity. It can be identified with the set $X^{\mathbb{N}}$ of infinite words (sequences) of symbols from X and equipped with the Tychonoff product topology which makes it homeomorphic to a Cantor set. Let $\mathrm{Aut}T$ be the group of automorphisms of T (i.e., of bijections on V that preserve the tree structure). The cardinality of $\mathrm{Aut}T$ is $2^{{\aleph }_0}$ and this group supplied with a natural topology is a profinite group (i.e., compact totally disconnected topological group, or a projective limit ${\displaystyle \underset{n\to \infty }{lim}\mathrm{Aut}{T}_{\left[n\right]}}$ of group of automorphisms of finite groups $\mathrm{Aut}{T}_{\left[n\right]}$, where $T_{\left[n\right]}$ is the finite subtree of T from the root until the n-th level, for $n=1,2,\dots$).

Symmetric group ${\mathcal{S}}_d$ ($\cong \mathcal{S}\left(X\right))$ of permutations on $\{1,2,\dots ,d\}$ naturally acts on X and on V by $\sigma \left(xw\right)=\sigma \left(x\right)w$, for $w\in V$ and $\sigma \in {\mathcal{S}}_d$. That is, a permutation $\sigma$ permutes vertices of the first level according to its action on X and no further action below first level. For $v\in V$ let $T_v$ be the subtree of T with the root at v.

For each $v\in V$, the subtree $T_v$ is naturally isomorphic to T and the corresponding isomorphisms ${\alpha }_v:T\to T_v$ constitute a canonical system of self-similarities of T. Any automorphism $g\in \mathrm{Aut}T$ can be described by a permutation $\sigma$ showing how g acts on the first level and a d-tuple of automorphisms $g_{x_1},\dots ,g_{x_d}$ of trees $T_{x_1},\dots ,T_{x_d}$ showing how g acts below the first level. As $T\cong T_{x_i}$ this leads to the isomorphism

$$\mathrm{Aut}T\stackrel{\psi }{\cong }\left(\mathrm{Aut}T\times \dots \times \mathrm{Aut}T\right)⋊{\mathcal{S}}_d,$$

(12)

where ⋊ denotes the operation of semidirect product (recall that if N is a normal subgroup in a group G, H is a subgroup in G, $N\cap H=\left\{e\right\}$, and $NH=G$, then $G=N⋊H$). Another interpretation of the isomorphism (12) is

$$\mathrm{Aut}T\cong \mathrm{Aut}T{\wr }_X{\mathcal{S}}_d$$

(13)

where ${\wr }_X$ denotes the permutational wreath product [4,12]. According to (12), for $g\in \mathrm{Aut}T$,

$$\psi \left(g\right)=(g_1,\dots ,g_d)\sigma .$$

(14)

Relations of this sort are called wreath recursions and elements $g_x,x\in X$ are called sections.

If $V_n=X^n=X\times \dots \times X$ denotes the n-th level of the tree, then every $g\in \mathrm{Aut}T$ preserves the level $V_n$, for $n=1,2,\dots$. Thus the maximum possible transitivity of a group $G\le \mathrm{Aut}T$ is the level transitivity.

Definition 1.

A group G acting on a tree $T(=T_d)$ by automorphism is said to be self-similar if for all $g\in G,x\in X$ the section $g_x$ coming from wreath recursion (14) belongs to G after identification of $T_x$ (on which $g_x$ acts) with T using identifications ${\alpha }_x^{-1}:T_x\to T$.

An alternative way to define self-similar groups is via Mealy automata (also known as the transducers or the sequential machines. See [39,40] for more applications of automata).

A non-initial Mealy automaton $\mathcal{A}=〈Q,X,\pi ,\lambda 〉$ consists of a finite alphabet $X=\{x_1,\dots ,x_d\}$, a set Q of states, a transition function $\pi :Q\times X\to Q$, and an output function $\lambda :Q\times X\to X$. Selecting a state $q\in Q$ as initial, produces the initial automaton ${\mathcal{A}}_q$. The functions $\pi$ and $\lambda$ naturally extends to $\pi :Q\times X^{\ast }\to Q$ and $\lambda :Q\times X^{\ast }\to X^{\ast }$ via inductive definitions

$$\begin{array}{cc}\hfill \pi (q,xw)& =\pi \left(\pi \right(q,x),w),\hfill \\ \hfill \lambda (q,xw)& =\lambda (q,x)\lambda \left(\pi \right(q,x),w),\hfill \end{array}$$

for all $w\in X^{\ast }$. Thus the initial automaton ${\mathcal{A}}_q$ determines the maps

$$\begin{array}{cc}\hfill X^n& \to X^n,n=1,2,\dots \hfill \end{array}$$

(15)

$$\begin{array}{cc}\hfill X^{\mathbb{N}}& \to X^{\mathbb{N}}\hfill \end{array}$$

(16)

which we will denote also by ${\mathcal{A}}_q$ (or sometimes even by q). Moreover, ${\mathcal{A}}_q$ induces an endomorphism of the tree $T=T\left(X\right)$ via identification of V with $X^{\ast }$. The automaton $\mathcal{A}$ is said to be finite if $\left|Q\right|<\infty$.

The initial automaton ${\mathcal{A}}_q$ can be schematically viewed as the sequential machine (or the transducer) shown in Figure 8. At the zero moment $n=0$, the automaton ${\mathcal{A}}_q$ is in the initial state $q=q_0$, reads the symbol $x_0$, produces the output $y_0=\lambda (q,x_0)$, and moves to the state $q_1=\pi (q,x_0)$. Then ${\mathcal{A}}_q$ continues to operate with input symbols in the same fashion until reading the last symbol $x_n$.

An automaton of this type is called a synchronous automaton. Asychronous automata can also be defined and used in group theory and coding as explained in [4,41].

An automaton $\mathcal{A}$ is invertible if for any $q\in Q$, the map $\pi (q,·):X\to X$ is a bijection, i.e., $\pi (q,·)$ is an element ${\sigma }_q$ of the symmetric group $\mathcal{S}\left(X\right)$. Invertibility of $\mathcal{A}$ implies that for any $q\in Q$ the initial automaton ${\mathcal{A}}_q$ induces an automorphism of the tree $T=T\left(X\right)$. The compositions ${\mathcal{A}}_q\circ {\mathcal{B}}_s$ of maps ${\mathcal{A}}_q,{\mathcal{B}}_s:X^n\to X^n$, where ${\mathcal{B}}_s=〈S,X,{\pi }^{\prime },{\lambda }^{\prime }〉$ is another automaton over the same alphabet, is the map determined by the automaton ${\mathcal{C}}_{(q,s)}={\mathcal{A}}_q\circ {\mathcal{B}}_s$ with the set of states $Q\times S$ and the transition and output functions determined by $\pi ,{\pi }^{\prime },\lambda ,{\lambda }^{\prime }$ in the obvious way (see Figure 9). If $\mathcal{A}$ is an invertible automaton, then for any $q\in Q$, the inverse map also is determined by an automaton, which will be denoted by ${\mathcal{A}}_q^{-1}$.

The above discussion shows that for each $m=2,3,\dots$, we have a semigroup $\mathcal{FAS}\left(m\right)$ of finite initial automata over the alphabet on m letters. We can also define a group $\mathcal{FAG}\left(m\right)$ of finite invertible initial automata. The group $\mathcal{FAG}\left(m\right)$ naturally embeds in $\mathcal{FAG}(m+1)$. These groups are quite complicated, contain many remarkable subgroups, and depend on m. At the same time in the asynchronous case there is only one (up to isomorphisms) group, introduced in [4], called the group of rational homeomorphisms of a Cantor set. This group, for instance, contains famous R. Thompson’s groups $F,T$ and V. In fact, the elements in $\mathcal{FAS}\left(m\right)$ and $\mathcal{FAG}\left(m\right)$ are classes of equivalence of automata, usually presented by the minimal automaton. The classical algorithm of minimization of automata solves the word problem in $\mathcal{FAS}\left(m\right)$ and $\mathcal{FAG}\left(m\right)$.

A convenient way to present finite automata is by diagrams, of the type shown on Figure 2. The nodes (vertices) of a such diagram correspond to the states of $\mathcal{A}$, each state $q\in Q$ has $\left|X\right|$ outgoing edges of the form shown in Figure 10, indicating that if current state is q and the input symbol is x, then the next state will be s and the output will be y. This way we describe the transition and the output functions simultaneously.

If $\mathcal{A}$ is an invertible automaton, then we define $S\left(\mathcal{A}\right)$ and $G\left(\mathcal{A}\right)$, the semigroup and the group generated by $\mathcal{A}$;

$$S\left(\mathcal{A}\right)={〈{\mathcal{A}}_q\mid q\in Q〉}_{sem.}$$

is the semigroup generated by initial automata ${\mathcal{A}}_q,q\in Q$ and

$$\begin{array}{cc}\hfill G\left(\mathcal{A}\right)& ={〈{\mathcal{A}}_q\mid q\in Q〉}_{gr.}\hfill \\ \hfill & ={〈{\mathcal{A}}_q\cup {\mathcal{A}}_q^{-1}\mid q\in Q〉}_{sem.}\hfill \end{array}$$

is the group generated by ${\mathcal{A}}_q,q\in Q$.

The group $G\left(\mathcal{A}\right)$ acts on $T=T\left(X\right)$ by automorphisms and for each $q\in Q$ the wreath recursion (14) becomes

$${\mathcal{A}}_q=({\mathcal{A}}_{\pi (q_0,x_1)},\dots ,{\mathcal{A}}_{\pi (q,x_d)}){\sigma }_g.$$

Therefore the groups generated by the states of the invertible automaton are self-similar.

The opposite is also true, any self-similar group can be realized as $G\left(\mathcal{A}\right)$ for some invertible automaton, only the automaton could be infinite. Self-similar groups generated by finite automata, called fractal groups (see [2]), constitute an interesting class of groups. Study of fractal groups in many cases leads to study of fractal objects, as explained for instance in [2,12,22].

4. Self-Similar Algebras

The definition of self-similar algebras resembles the definition of self-similar groups. It is based on the important property of infinite dimensional Hilbert space H to be isomorphic to the direct sum of d (for $d\ge 2)$ copies of it. A d-fold similarity of H is an isomorphism

$$\psi :H\to H^d=H\oplus \dots \oplus H.$$

There are many such isomorphisms and they are in a natural bijection with the *-representations of the Cuntz algebra ${\mathcal{O}}_d$ as observed in [20]. The Cuntz algebra is given by the presentation

$${\mathcal{O}}_d\cong 〈a_1,\dots ,a_d\mid a_1{a}_1^{\ast }+\dots +a_d{a}_d^{\ast }=1,a_i^{\ast }{a}_i=1,i=1,\dots ,d〉$$

(17)

by generators and relations that we will call Cuntz relations.

Theorem 2

(Proposition 3.1 from [20]). The relation putting into correspondence to a *-representation $\rho :{\mathcal{O}}_d\to \mathcal{B}\left(H\right)$ of ${\mathcal{O}}_d$ into the $C^{\ast }$-algebra $\mathcal{B}\left(H\right)$ of bounded operators on a separable infinite dimensional Hibert space H, the map ${\tau }_{\rho }=(\rho \left(a_1^{\ast }\right),\dots ,\rho \left(a_d^{\ast }\right))$, where $a_1,\dots ,a_d$ are generators of ${\mathcal{O}}_d$, is a bijection between the set of representations of ${\mathcal{O}}_d$ on H and the set of d-fold self-similarities.

The inverse of this bijection puts into correspondence to a d-similarity $\psi :H\to H^d$ the *-representation of ${\mathcal{O}}_d$ given by $\rho \left(a_k\right)=T_k$, for

$$T_k\left(\xi \right)={\psi }^{-1}(0,\dots ,0,\xi ,0,\dots ,0),$$

(18)

where ξ in the right hand side is at the k-th coordinate of $H^d$.

A natural example of a d-similarity comes from the d-regular rooted tree T and its boundary $\partial T$ supplied by uniform Bernoulli measure $\mu$. That is, $\partial T\cong X^{\mathbb{N}}$, where $X=\{x_1,\dots ,x_d\}$ and $\mu$ is the uniform distribution on X. Then $H=L^2(\partial T,\mu )$ decomposes as

$$\underset{x\in X}{⨁}{L}^2(\partial T_x,{\mu }_x),$$

where $T_x$ is the subtree of T with the root at the vertex x of the first level and ${\mu }_x{=\mu |}_{\partial T_x}$. Then $L^2(\partial T_x,{\mu }_x)\cong L^2(\partial T,\mu )$ via the isomorphism given by the operator $U_x:L^2(\partial T_x,{\mu }_x)\to L^2(\partial T,\mu )$,

$$U_{x}f\left(\xi \right)=\frac{1}{\sqrt{d}}f\left(x\xi \right),\xi \in \partial T_i,x\in X.$$

Another example associated with the self-similar subgroup $G<\mathrm{Aut}T$ would be to consider a countable self-similar subset $W\subset \partial T$, i.e., a subset W such that $W={\bigsqcup }_{x\in X}xW$. Such a set can be obtained by including the orbit $G\xi$, $\xi \in \partial T$ into the set W that is self-similar closure of $G\xi$. Then

$${\ell }^2\left(W\right)=\underset{x\in X}{⨁}{\ell }^2\left(xW\right)$$

and ${\ell }^2\left(xW\right)$ is isomorphic to ${\ell }^2\left(W\right)$ via the isomorphism $U_x:{\ell }^2\left(xW\right)\to {\ell }^2\left(W\right)$ given by

$$U_x\left(f\right)\left(w\right)=f\left(xw\right).$$

Let G be a self-similar group acting on the d-regular tree $T=T\left(X\right)$, $\left|X\right|=d$, and $\psi :H\to H^X$ be a d-fold similarity. The unitary representation $\rho$ of G on H is said to be self-similar with respect to $\psi$ if for all $g\in G$ and for all $x\in X$

$$\rho \left(g\right)T_x=T_y\rho \left(h\right),$$

(19)

where $T_x$ is the operator defined by (18), the element h is the section ${g|}_x$ of g at the vertex x of the first level, and $y=g\left(x\right)$, for each $x\in X$.

The meaning of the relation (19) comes from the wreath recursion (14) and its generalization represented by the relation

$${g\left(xw\right)=g\left(x\right)g|}_x\left(w\right),\forall w\in W.$$

Examples of self-similar representations are the Koopman representation $\kappa$ of G in $L^2(\partial T,\mu )$ (that is, $\left(\kappa \left(g\right)f\right)\left(x\right)=f\left(g^{-1}x\right)$ for $f\in L^2(\partial T,\mu )$) and permutational representations in ${\ell }^2\left(W\right)$ given by the action of G on the self-similar subset $W\subset \partial T$.

The papers [7,20,42] introduce and discuss a number of self-similar operator algebras associated with self-similar groups. They are denoted by ${\mathcal{A}}_{max},{\mathcal{A}}_{min}$ and if ${\mathcal{A}}_{\rho }$ is the algebra obtained by the completion of the group algebra $\mathbb{C}\left[G\right]$ with respect to a self-similar representation $\rho$, then there are natural surjective homomorphisms

$${\mathcal{A}}_{max}\to {\mathcal{A}}_{\rho }\to {\mathcal{A}}_{min}.$$

The definition of ${\mathcal{A}}_{max}$ involves a general theory of Cuntz-Pimsner $C^{\ast }$-algebras, which was developed in [43].

Study of the algebra ${\mathcal{A}}_{\rho }$ is based on the matrix recursions. A matrix recursion on an associative algebra A is a homomorphism

$$\phi :A\to M_d\left(A\right),$$

where $M_d\left(A\right)$ is the algebra of $d\times d$ matrices with entries in A.

Wreath recursions (14) associated with a self-similar representation $\rho$ of a self-similar group G naturally lead to a matrix recursion $\phi$ for the group algebra $\mathbb{C}\left[G\right]$. Define $\phi$ on group elements $g\in G$ by

$$\phi \left(g\right)={\left(A_{y,x}\right)}_{x,y\in X},$$

(20)

where

$$A_{y,x}=\left\{\begin{array}{cc}\rho \left(g{|}_x\right)\hfill & \mathrm{if}g\left(x\right)=y\hfill \\ 0\hfill & \mathrm{otherwise}\hfill \end{array}\right.,$$

(21)

and extended to the group algebra $\mathbb{C}\left[G\right]$ and its closure ${\mathcal{A}}_{\rho }=\overline{\rho \left(\mathbb{C}\right[G\left]\right)}$ linearly.

In terms of the associated representation $\rho$ of the Cuntz algebra we have the relations

$${g|}_x=T_{g\left(x\right)}^{\ast }g{T}_x,$$

where $T_x=\rho \left(a_x\right)$, and $a_x$ are generators of ${\mathcal{O}}_d$ from presentation (17).

Example 1.

In the case of the group $\mathcal{G}=〈a,b,c,d〉$, given by presentation (3), acting on $T_2$ via the automaton in Figure 2a, the recursions for the Koopman representation are,

$$\begin{array}{cccccccc}\hfill a& =\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),\hfill & \hfill b& =\left(\begin{array}{cc}a& 0\\ 0& c\end{array}\right),\hfill & \hfill c& =\left(\begin{array}{cc}a& 0\\ 0& d\end{array}\right),\hfill & \hfill d& =\left(\begin{array}{cc}1& 0\\ 0& b\end{array}\right),\hfill \end{array}$$

(22)

where 1 stands for the identity operator. Here (and henceforth), we abuse the notation and write g in place of $\kappa \left(g\right)$, for any group element g.

Example 2.

In the case of the Basilica group $\mathcal{B}=〈a,b〉$, the recursions for the Koopman representation are,

$$a=\left(\begin{array}{cc}1& 0\\ 0& b\end{array}\right),b=\left(\begin{array}{cc}0& 1\\ a& 0\end{array}\right).$$

The minimal self-similar algebra ${\mathcal{A}}_{min}$ is defined using the algebra generated by permutational representation in ${\ell }^2\left(W\right)$ for an arbitrary self-similar subset $W\subset \partial T$ spanned by the orbit of any G-regular point [20]. A point $\xi \in \partial T$ is G-regular if $g\xi \ne \xi$ or $g\zeta =\zeta$ for all $\zeta \in U_{\xi }$ for some neighborhood $U_{\xi }$ of $\xi$. Points that are not G-regular are called G-singular. In the case of $\mathcal{G}=〈a,b,c,d〉$, $\mathcal{G}$-singular points constitute the orbit $\mathcal{G}\left(1^{\infty }\right)$. The set of G-regular points is co-meager (i.e., an intersection of a countable family of open dense sets). This notion was introduced in [4] and now play an important role in numerous studies.

Another example of a self-similar algebra is ${\mathcal{A}}_{mes}$ generated by Koopman representation $\kappa$ on $L^2(\partial T,\mu )$. The representation $\kappa$ is the sum of finite dimensional representations and ${\mathcal{A}}_{mes}$ is residually finite dimensional [1,18,44]. The algebra ${\mathcal{A}}_{mes}$ has a natural self-similar trace $\tau$, i.e., a trace that satisfies

$$\tau \left(a\right)=\frac{1}{d}\sum _{i=1}^d\tau \left(a_{ii}\right)$$

for $a\in {\mathcal{A}}_{mes}$, where $\phi \left(a\right)={\left(a_{ij}\right)}_{i,j=1}^d$.

This trace was used in [30] to compute the spectral measure associated with the Laplace operator on the Lamplighter group. The range of values of $\tau \left(g\right)$ for $g\in \mathcal{G}$ is $\frac{1}{7}\{\frac{m}{2^n}\mid m,n\in \mathbb{N},0\le m\le 2^n\}$ [19].

A group G is said to be just-infinite if G is infinite and every proper quotient of G is finite. An algebra $\mathcal{C}$ is just-infinite dimensional if it is infinite dimensional but every proper quotient is finite dimensional. Infinite simple groups and infinite dimensional simple $C^{\ast }$-algebras are examples of such objects. Infinite cyclic group $\mathbb{Z}$, infinite dihedral group $D_{\infty }$, and $\mathcal{G}$ are examples of just-infinite groups. There is a natural partition of the class of just-infinite groups into the class of just-infinite branch groups, hereditary just-infinite groups, and near-simple groups [45]. The proof of this result uses a result of J. Wilson from [46]. Roughly speaking, a branch group is a group acting in a branch way on some spherically homogeneous rooted tree $T_{\overline{m}}$, given by a sequence $\overline{m}={\left\{m_n\right\}}_{n=1}^{\infty }$ (where, $m_n\ge 2$ for all n) of integers (the integer $m_n$ is called the branching number for vertices of n-th level). The group $\mathcal{G}$ is an example of a just-infinite branch group and the algebra $\phi \left(\mathbb{C}\right[\mathcal{G}\left]\right)$, which sometimes (following S. Sidki [47]) is called the “thin” algebra, is just-infinite dimensional [48].

Problem 1.

Is the $C^{\ast }$-algebra ${\mathcal{C}}_{\kappa }^{\ast }\left(\mathcal{G}\right)$, generated by Koopman representation of $\mathcal{G}$ in $L^2(\partial T,\mu )$, just-infinite dimensional?

There is also a natural partition of separable just-infinite dimensional $C^{\ast }$-algebras into three subclasses by the structure of its space of primitive ideals which can be of one of the types $Y_n$, $0\le n\le \infty$, where type $Y_0$ means a singleton and corresponds to the case of simple $C^{\ast }$-algebras, the type $Y_n$, $1\le n<\infty$ corresponds to an essential extension of a simple $C^{\ast }$-algebra by a finite dimensional $C^{\ast }$-algebra with n-simple summands, and in the $Y_{\infty }$ case the algebras are residually finite dimensional. If ${\mathcal{C}}_{\kappa }^{\ast }\left(\mathcal{G}\right)$ happens to be just-infinite dimensional, this would be a good addendum to the examples presented in [49], where the above trichotomy for $C^{\ast }$-algebras is proven.

Given G, a self-similar group acting on $T\left(X\right)$, $\left|X\right|=d$, the associated universal Cuntz-Pimsner $C^{\ast }$-algebra ${\mathcal{O}}_G$, denoted as ${\mathcal{A}}_{max}$, is defined as the universal $C^{\ast }$-algebra generated by G and ${\mathcal{O}}_d$ satisfying the following relations:

• Relations of G,
• Cuntz relations (17),
• $g{a}_x=a_{y}h$ for $g,h\in G$ and $x,y\in X$ if $g\left(xw\right)=yh\left(w\right)$ for all $w\in X^{\ast }$ (i.e., if $g\left(x\right)=y$ and ${h=g|}_x$ is a section).

A self-similar group G is said to be contracting if there exists a finite set $\mathcal{N}\subset G$ such that for all $g\in G$, there exists $n_0\in \mathbb{N}$ with ${g|}_w\in \mathcal{N}$ for all words $w\in X^{\ast }$ of length greater than $n_0$. The smallest set $\mathcal{N}$ having this property is called the nucleus. Examples of contracting groups are the adding machine $\alpha$ given by the relation $\psi \left(\alpha \right)=(1,\dots ,1,\alpha )\sigma$, where $\sigma$ is a cyclic permutation of X, group $\mathcal{G}$, Basilica, Hanoi groups, and $IMG(z^2+i)$. The Lamplighter group $\mathcal{L}$ presented by the automaton in Figure 2b as well as the examples given by automata from Figure 2g,h are not contracting.

The contracting property of the group is a tool used to prove subexponentiality of the growth. But not all contracting groups grow subexponentially. For instance, Basilica is contracting but has exponential growth. For a contracting group G with the nucleus $\mathcal{N}$, the Cuntz-Pimsner algebra ${\mathcal{O}}_G$ has the following presentation by generators and relations:

1.

Cuntz relations,

2.

relations ${\displaystyle g=\sum _{x\in X}{a}_{g\left(x\right)}{g|}_x{a}_x^{\ast }}$ for $g\in \mathcal{N}$,

3.

relations $g_1{g}_2{g}_3=1$, when $g_1,g_2,g_3\in \mathcal{N}$ and relations $g{g}^{\ast }=g^{\ast }g=1$ for $g\in \mathcal{N}$ [7].

Thus, for contracting groups, the algebra ${\mathcal{A}}_{\infty }$ is finitely presented.

The nucleus of the group $\mathcal{G}$ is $\mathcal{N}=\{1,a,b,c,d\}$ hence ${\mathcal{A}}_{\infty }\left(\mathcal{G}\right)$ is given by the presentation

$$\begin{array}{cc}\hfill {\mathcal{A}}_{\infty }\left(\mathcal{G}\right)=〈a_0,a_1,a,b,c,d\mid & 1=a_0{a}_0^{\ast }+a_1{a}_1^{\ast }=a_0^{\ast }{a}_0=a_1^{\ast }{a}_1=a{a}^{\ast }=b{b}^{\ast }=c{c}^{\ast }=d{d}^{\ast }=bcd,\hfill \\ \hfill & b=a_{0}a{a}_0^{\ast }+a_{1}c{a}_1^{\ast },c=a_{0}a{a}_0^{\ast }+a_{1}d{a}_1^{\ast },d=a_0{a}_0^{\ast }+a_{1}b{a}_1^{\ast }〉.\hfill \end{array}$$

For contracting level transitive groups with the property that for every element g of the nucleus the interior of the set of fixed points of g is closed, all self-similar completions of $\mathbb{C}\left[G\right]$ are isomorphic, and the isomorphisms ${\mathcal{A}}_{max}\cong {\mathcal{A}}_{mes}\cong {\mathcal{A}}_{min}$ hold. This condition holds for Basilica but does not hold for the group $\mathcal{G}$ and one of the groups $G_{\omega }$, $\omega \in {\{0,1,2\}}^{\mathbb{N}}$ from [15], presented by the sequence ${\left(01\right)}^{\infty }$ (and studied by A. Erschler [50]). In the latter case ${\mathcal{A}}_{max}\ncong {\mathcal{A}}_{min}$. It is unclear at the moment if for $\mathcal{G}$ we have the equality ${\mathcal{A}}_{max}\cong {\mathcal{A}}_{min}$.

Representations and characters of self-similar groups of branch type are considered in [51,52]. On self-similarity, operators, and dynamics see also [53].

5. Joint Spectrum and Operator Systems

Given a set $\{M_1,\dots ,M_k\}$ of bounded operators in a Hilbert (or more generally Banach) space H, one can consider the pencil of operators $M\left(\overline{z}\right)=z_1{M}_1+\dots +z_k{M}_k$ for $\overline{z}=(z_1,\dots ,z_k)\in {\mathbb{C}}^k$, and define the joint (projective) spectrum $\mathrm{JSp}\left(M\left(\overline{z}\right)\right)$ as the set of parameters $\overline{z}\in \mathbb{C}$ for which $M\left(\overline{z}\right)$ is not invertible. Surprisingly, such a simple concept did not attract much attention when the number of non-homogeneous parameters is greater or equal to two, until publication of [23]. Sporadic examples of analysis of the structure of $\mathrm{JSp}$ and in some cases of computations are presented in [1,30,31,32,33,54,55,56,57]. Important examples of pencils come from $C^{\ast }$-algebras associated with self-similar groups that were discussed in the previous section.

Recall that given a unital $C^{\ast }$-algebra $\mathcal{A}$, a closed subspace $\mathcal{S}$ containing the identity element 1 is called an operator system. One can associate to each subspace $\mathcal{M}\subset \mathcal{A}$ an operator system via $\mathcal{S}=\mathcal{M}+{\mathcal{M}}^{\ast }+\mathbb{C}1$. Such systems are important for the study of completely bounded maps [58,59,60].

If $G=〈a_1,\dots ,a_m〉$ is a contracting self-similar group with (finite) nucleus $\mathcal{N}=\{n_1,\dots ,n_k\}$ and ${\mathcal{A}}^{\ast }$ is a self-similar $C^{\ast }$-algebra associated with a self-similar unitary representation $\rho$ of G, then the identity element belongs to $\mathcal{N}$ and a natural operator space and a self-similar pencil of operators are: $\mathcal{S}=span\{\rho \left(n_1\right),\dots ,\rho \left(n_k\right),\rho \left(n_1^{\ast }\right),\dots ,\rho \left(n_k^{\ast }\right)\}\subset \mathcal{A}$ and

$$M\left(\overline{z}\right)=\sum _{i=1}^k(\rho \left(n_i\right)+\rho \left(n_i^{\ast }\right)),$$

respectively. The main examples considered in this article come from the group $\mathcal{G}$ and the overgroup $\tilde{\mathcal{G}}$ that possess the nuclei $\{1,a,b,c,d\}$ and $\{1,a,b,c,d,\tilde{a},\tilde{b},\tilde{c},\tilde{d}\}$, respectively.

6. Graphs of Algebraic Origin and Their Growth

A graph $\Gamma =(V,E)$ consists of a set V of vertices and a set E of edges. The edges are presented by the map $e:V\times V\to {\mathbb{N}}_0$ (here ${\mathbb{N}}_0$ denotes the set of non negative integers), where $e(u,v)$ represents the number of edges connecting the vertex u to the vertex v. If $u=v$, then the edges are loops. So what we call a graph in graph theory usually is called a directed multi-graph or an oriented multi-graph. Depending on the situation, graph can be non-oriented (if the edges are independent of the orientation, i.e., $e(u,v)=e(v,u)$ and edges $(u,v)$ and $(v,u)$ are identified) and labeled (if edges are colored by elements of a certain alphabet). We only consider connected locally finite graphs (the later means that each vertex is incident to a finite number of edges). The degree $d\left(u\right)$ of the vertex u is the number of edges incident to it (where each edge from or to u contributes 1 to the degree and each loop contributes 2 to the degree). A graph is of uniformly bounded degree if there is a constant C such that $d\left(v\right)\le C$ for all $v\in V$, and $\Gamma$ is a regular graph if all vertices have the same degree.

There is a rich source of examples of graphs coming from groups. Namely, given a marked group $(G,A)$ (i.e., a group G with a generating set A, usually we assume that $\left|A\right|<\infty$ and therefore the group is finitely generated), one defines the directed graph $\Gamma ={\Gamma }_l(G,A)$ with $V=G$ and $E=\{(g,ag)\mid a\in A\cup A^{-1}\}$, where g is the origin and $ag$ is the end of the edge $(g,ag)$. This is the left Cayley graph. Similarly, one can define the right Cayley graph ${\Gamma }_r(G,A)$, and there is a natural isomorphism ${\Gamma }_l(G,A)\cong {\Gamma }_r(G,A)$. Left and right Cayley graphs are vertex transitive, i.e., the group $\mathrm{Aut}(\Gamma )$ of automorphisms acts transitively on the set of vertices (right translations by elements of G on $V=G$ induce automorphisms of ${\Gamma }_l(G,A)$). When speaking about Cayley graph, we usually keep in mind the left Cayley graph. Depending on the situation, Cayley graphs are considered as labeled graphs (the edge $e=(g,ag)$ has label a), or unlabeled (if labels do not play a role). Cayley graphs can also be converted into undirected graphs by identification of pairs $(g,ag),(ag,a^{-1}\left(ag\right))=(ag,g)$ of mutually inverse pairs of edges. The examples of Cayley graphs are presented in Figure 11. Non-oriented Cayley graph of $(G,A)$ is d-regular with $d=2|A\setminus A_2|+|A_2|$, where $A_2\subset A$ is the set of generators whose order is two (involutions).

A Schreier graph $\Gamma =\Gamma (G,H,A)$ is determined by a triple $(G,H,A)$, where as before A is a system of generators of G and H is a subgroup of G. In this case $V=\{gH\mid g\in G\}$ is a set of left cosets (for the left version of definition) and $E=\{(gH,agH)\mid g\in G,a\in A\cup A^{-1}\}$. Again, one can consider a right version of the definition, oriented or non-oriented, labeled or unlabeled versions of the Schreier graph [61,62,63].

Cayley graph $\Gamma (G,A)$ is isomorphic to the Schreier graph $\Gamma (G,H,A)$ when $H=\left\{1\right\}$ is the trivial subgroup. Non-oriented Schreier graphs are also d-regular with d given by the same expression as above, but in contrast with Cayley graphs, they may have a trivial group of automorphism. Examples of Schreier graphs are presented in the Figure 12.

We have the following chains of classes of graphs:

$$\begin{array}{c}\left\{\mathrm{locally}\mathrm{finite}\right\}\supset \left\{\begin{array}{c}\mathrm{bounded}\\ \mathrm{degree}\end{array}\right\}\supset \left\{\mathrm{regular}\right\}\supset \left\{\begin{array}{c}\mathrm{vertex}\\ \mathrm{transitive}\end{array}\right\}\supset \left\{\mathrm{Cayley}\right\},\\ \left\{\mathrm{regular}\right\}\supset \left\{\mathrm{Schreier}\right\}\supset \left\{\mathrm{Cayley}\right\}.\end{array}$$

In fact the class of d-regular graphs of even degree $d=2m$ coincides with the class of Schreier graphs of the free group $F_m$ of rank m (for finite graphs this was observed by Cross [64] and for the general case see [65] and Theorem 6.1 in [19]). For an odd degree, the situation is slightly more complicated, but there is clear understanding on which of them are Schreier graphs [66].

Schreier graphs have much more applications in mathematics being able to provide a geometrical-combinatorial representation of many objects and situations. In particular, they are used to approximate fractals, Julia sets, study the dynamics of groups of iterated monodromy, Hanoi Tower Game on d pegs for $d\ge 3$, etc.

Growth function of a graph $\Gamma =(V,E)$ with distinguished vertex $v_0\in V$ is the function

$$\gamma \left(n\right)={\gamma }_{\Gamma ,v_0}\left(n\right)=\#\{v\in V\mid d(v_0,v)\le n\},$$

where $d(u,v)$ is the combinatorial distance given by the length of a shortest path connecting two vertices u and v. Its rate of growth when $n\to \infty$, defines the rate of growth of the graph at infinity (if $\Gamma$ is an infinite graph). It does not depend on the choice of $v_0$ (in case of connected graphs), and is bounded by the exponential function $C{d}^n$ when $\Gamma$ is of uniformly bounded degree $\le d$.

The growth of Schreier graph can be of power function $n^{\alpha }$, $\alpha >0$ type, even with irrational $\alpha$ [1], of the type $a^{{(logn)}^{\alpha }}$ [32], and of many other unusual types of growth.

On the other hand, the growth of a Cayley graph (or what is the same the growth of the corresponding group) is much more restrictive. It is known that if it is of the power type $n^{\alpha }$, then $\alpha$ is a positive integer (in which case the group is said to be of polynomial growth) and the group is virtually nilpotent (i.e., contains nilpotent subgroup of finite index) [67]. The Cayley graphs of virtually solvable groups or of linear groups (i.e., groups presented by matrices over a field) either have polynomial or exponential growth [68,69,70,71]. The question about existence of groups of intermediate growth was raised by J. Milnor [72] and got the answer in [14,15] using the group $\mathcal{G}$.

The Cayley graph of the group of intermediate growth $\mathcal{G}$ is presented by Figure 11c. The group $\mathcal{G}$ is a representative of an uncountable family of groups ${\mathcal{G}}_{\omega }=〈a,b_{\omega },c_{\omega },d_{\omega }〉$, $\omega \in {\{0,1,2\}}^{\mathbb{N}}=\Omega$, mostly consisting of groups of intermediate growth [15] (definition is given by (41) and (42)). Moreover, there are uncountably many of different rates of growth in this family, where by the rate (or degree) of growth of a group G we mean the dilatational equivalence class of ${\gamma }_G\left(n\right)$ (two functions ${\gamma }_1\left(n\right),{\gamma }_2\left(n\right)$ are equivalent, ${\gamma }_1\left(n\right)\sim {\gamma }_2\left(n\right)$, if there is C such that ${\gamma }_1\left(n\right)\le {\gamma }_2\left(Cn\right)$ and ${\gamma }_2\left(n\right)\le {\gamma }_1\left(Cn\right)$). This gives the first family of cardinality $2^{{\aleph }_0}$ of continuum of finitely generated groups with pairwise non quasi-isometric Cayley graphs. As shown in [73,74], for any $ϵ>0$,

$$e^{n^{\beta -ϵ}}\le {\gamma }_{\mathcal{G}}\left(n\right)\le e^{n^{\beta }},$$

where $\beta \approx 0.767$ is $1/{log}_2{\beta }_0$ and ${\beta }_0$ is the (unique) positive root of the polynomial $x^3-x^2-2x-4$. In [75] the group $\mathcal{G}$ is used to show that for each $\delta$ such that $\beta <\delta <1$, there is a group with growth equivalent to $e^{n^{\delta }}$.

Surprisingly, so far there is no example of a group with super-polynomial growth but slower than the growth of $\mathcal{G}$. There is a conjecture [76] that there is a gap in the scale of growth degrees of finitely generated groups between polynomial growth and growth of the partition function $P\left(n\right)\sim e^{\sqrt{n}}$ (i.e., if ${\gamma }_G\left(n\right)\prec e^{\sqrt{n}}$, then G is virtually nilpotent and hence has a polynomial growth). The conjecture has been confirmed to be true for the class of groups approximated by nilpotent groups. More on the gap conjecture for group growth and other asymptotic characteristics of groups see [21,77].

Problem 2.

Is there a finitely generated group with super polynomial growth smaller than the growth of the group $\mathcal{G}$?

7. Space of Groups and Graphs and Approximation

A pair $(G,A)$ where G is a group and $A=\{a_1,\dots ,a_m\}$ is an ordered system of (not necessarily distinct) generators is said to be a marked group. There is a natural topology in the space ${\mathcal{M}}_m$ of m-generated marked groups introduced in [15]. Similarly, there is a natural topology in the space ${\mathcal{M}}_{Sch}^{\ast }\left(m\right)$ of marked Schreier graphs associated with marked triples $(G,H,A)$ (a marked graph is a graph with distinguished vertex viewed as the origin). For every $m\ge 2$, the spaces ${\mathcal{M}}_m$ and ${\mathcal{M}}_{Sch}^{\ast }\left(m\right)$ are totally disconnected compact metrizable spaces whose structure is closely related to various topics of groups theory and dynamics. For instance the closure $\mathcal{X}$ of ${\left\{{\mathcal{G}}_{\omega }\right\}}_{\omega \in \Omega }$ in ${\mathcal{M}}_4$ consists of a Cantor set ${\mathcal{X}}_0$ and a countable set ${\mathcal{X}}_1$ of isolated points accumulating to ${\mathcal{X}}_0$ and consisting of virtually metabelian groups containing a direct product of copies of the Lamplighter group $\mathcal{L}={\mathbb{Z}}_2\wr \mathbb{Z}$ [15,78] as a subgroup of finite index. The closure of ${\left\{{\tilde{\mathcal{G}}}_{\omega }\right\}}_{\omega \in \Omega }$ is described in [79] and has a more complicated structure. More on spaces ${\mathcal{M}}_m$ and ${\mathcal{M}}_{Sch}^{\ast }\left(m\right)$ see [18,80,81].

One of the fundamental questions about these spaces is finding the Cantor-Bendixson rank (for the definition see [82]) characterized by the first ordinal when taking of Cantor-Bendixson derivative does not change the space.

A more general notion than Schreier graph is the notion of orbital graph. Given an action $\alpha$ of marked group $(G,A)$ on the space X, one can build a graph ${\Gamma }_{\alpha }(G,A)$ with the set of vertices $V=X$ and the set of edges $E=\{(x,ax)\mid a\in A\cup A^{-1}\}$. Connected components of this graph are Schreier graphs $\Gamma (G,H_{x_i},A)$, $i\in I$, where $H_{x_i}$ is the stabilizer of point $x_i\in X$ and ${\left\{x_i\right\}}_{i\in I}$ is the set of representatives of orbits. If action is transitive, then orbit graph is a Schreier graph.

Given a level transitive action of marked group $(G,A)$ by automorphisms on a d-regular rooted tree T, one can consider the covering sequence ${\left\{{\Gamma }_n\right\}}_{n=1}^{\infty }$ of graphs where ${\Gamma }_n$ is orbital graph for action on n-th level of the tree and ${\Gamma }_{n+1}$ covers ${\Gamma }_n$. Additionally, for every point $\xi \in \partial T$ (the boundary of T) one can associate a Schreier graph ${\Gamma }_{\xi }=\Gamma (G,H_{\xi },A)$ built on the orbit $G\left(\xi \right)$ of $\xi$ ($H_{\xi }={St}_G\left(\xi \right)$). If $v_n$ is a vertex of level n that belongs to the path representing $\xi$, then

$$({\Gamma }_{\xi },\xi )=\underset{n\to \infty }{lim}({\Gamma }_n,v_n)$$

(23)

(the limit is taken in the topology of the space of marked Schreier graphs). The relation (23) allows an approximation of infinite graphs by finite graphs that leads also to the approximation of their spectra as shortly explained in the next section.

The example of ${\Gamma }_n$ and ${\Gamma }_{\xi }$ associated with the group $(\mathcal{G},\{a,b,c,d\left\}\right)$ is given by Figure 12a,b. In this example ${\Gamma }_{n+1}$ can be obtained from ${\Gamma }_n$ by substitution rule given by Figure 13 that mimics the substitution $\sigma$ used in presentation (3).

Similar property holds for ${\Gamma }_n,{\Gamma }_{\xi }$ associated with the overgroup ${\tilde{\mathcal{G}}}_{\omega }$ and and graphs associated with ${\mathcal{G}}_{\omega }$ and ${\tilde{\mathcal{G}}}_{\omega }$ if instead of a single substitution, to use three substitutions and iterate them accordingly to “oracle” $\omega$.

The correspondence $\partial T\ni \xi \stackrel{\phi }{⟶}({\Gamma }_{\xi },\xi )$ gives a map from $\partial T$ to ${\mathcal{M}}_{Sch}^{\ast }\left(4\right)$ with the image $\phi (\partial T)=\{({\Gamma }_{\xi },\xi )\mid \xi \in \partial T\}$. The set of vertices $V_{\xi }$ of ${\Gamma }_{\xi }$ is the orbit $\mathcal{G}\xi$ and $\mathcal{G}$ acts on $\phi (\partial T)$ by changing the root vertex $({\Gamma }_{\xi },\xi )\stackrel{g}{⟶}({\Gamma }_{\xi },g\xi )$. The graphs $({\Gamma }_{\xi },\xi ),\xi \in \mathcal{G}{1}^{\infty }$ are one-ended and are isolated points in $\phi (\partial T)$ and also in the closure $\overline{\phi (\partial T)}$ in ${\mathcal{M}}_{Sch}^{\ast }\left(4\right)$. Deletion of them from $\overline{\phi (\partial T)}$ gives the set $X=\overline{\phi (\partial T)}\setminus \left\{\mathrm{isolated}\mathrm{points}\right\}$ which is a union of $X_0=\{({\Gamma }_{\xi },\xi )\mid \xi \in \partial T,\xi \notin \mathcal{G}{1}^{\infty }\}$ and the countable set $X_1$ consisting of the limit points of $X_0$ that do not belong to $X_0$. The set $X_1$ consists of pairs $(\Gamma ,v)$, where $\Gamma$ is one of the three graphs given by Figure 14 (where, $(b^{\prime },c^{\prime },d^{\prime })$ is any cyclic permutation of $(b,c,d)$), and v is an arbitrary vertex of $\Gamma$ [5].

Now X also is homeomorphic to a Cantor set, $\mathcal{G}$ acts on X and the action is minimal and uniquely ergodic and the map $X_0\ni ({\Gamma }_{\xi },\xi )⟶\xi \in \partial T$ extends to a continuous factor map

$$\Phi :X\to \partial T$$

which is one-to-one except in a countable set of points, where it is three-to-one [5].

8. Spectra of Groups and Graphs

Let $\Gamma =(V,E)$ be a d-regular (non-oriented) graph. The Markov operator M acts on the Hilbert space ${\ell }^2\left(V\right)$ (which we denote by ${\ell }^2(\Gamma )$) and is defined as

$$\left(Mf\right)\left(x\right)=\frac{1}{d}\sum _{y\sim x}f\left(y\right),$$

where $f\in {\ell }^2(\Gamma )$ and $x\sim y$ is the adjacency relation. The operator $L=I-M$ where I is the identity operator is called the discrete Laplace operator. Operators M and L can be defined also for non-regular graphs as it is done for instance in [83,84]. The Markov operator M is a self-adjoint operator with the norm $\parallel M\parallel \le 1$ and the spectrum $\mathrm{Sp}\left(M\right)\subset [-1,1]$. The name “Markov” comes from the fact that M is the Markov operator associated with the random walk on $\Gamma$ in which a transition $u\to v$ occurs with probability $p=\frac{1}{d}$, if u and v are adjacent vertices. Random walks on graphs are special case of Markov chains.

A graph $\Gamma$ of uniformly bounded degree is called amenable if $1\in \mathrm{Sp}\left(M\right)$ ($\iff \parallel M\parallel =1$). Such definition comes from the analogy with von-Neumann – Bogolyubov theory of amenable groups, i.e., groups with invariant mean [85]. By Kesten’s criterion [86], amenable groups can be characterized as groups for which the spectral radius $r={\overline{lim}}_{n\to \infty }\sqrt[n]{P_{1,1}^{\left(n\right)}}$ is equal to one, where $P_{1,1}^{\left(n\right)}$ is the probability of return to identity element in n steps of the simple random walk on the Cayley graph.

By a spectrum of a graph (or a group), we mean the spectrum of M. A more general concept is used when graph is weighted, in the sense that a weight function $w:E\to \mathbb{R}$ on edges is given and the “weighted Markov” operator $M_w$ is defined in ${\ell }^2(\Gamma )$ as

$$\left(M_{w}f\right)\left(x\right)=\sum _{y\sim x}w(x,y)f\left(y\right).$$

A special case of such situation is given by a marked group $(G,A)$ (i.e., group G together with its generating set A) and symmetric probability distribution $P\left(g\right)$ on $A\cup A^{-1}$: $P\left(a\right)=P\left(a^{-1}\right)$, for all $a\in A$ and ${\sum }_{a\in A}P\left(a\right)=1/2$. Then Markov operator $M_P$ acts as

$$\left(M_{P}f\right)\left(g\right)=\sum _{a\in A\cup A^{-1}}P\left(a\right)f\left(ag\right)$$

and $M_P$ is the operator associated with a random walk on the (left) Cayley graph $\Gamma (G,A)$, where transition $g\to ag$ holds with probability $P\left(a\right)$.

The case of uniform distribution on $A\cup A^{-1}$ (i.e., of a simple random walk) is called isotropic case, while non-uniform distribution corresponds to the anisotropic case.

Basic questions about spectra of infinite graphs are:

• What is the shape (up to homeomorphism) of $\mathrm{Sp}\left(M\right)$?
• What can be said about spectral measures ${\mu }_{\phi }$ associated with functions $\phi \in {\ell }^2(\Gamma )$, in particular, with delta functions ${\delta }_v$, $v\in V$?

As usual in mathematical physics, the gaps in the spectrum, discrete and singular continuous parts of the spectrum are of special interest. Also an important case is when graph $\Gamma$ has a subgroup of the group of automorphisms acting on the set of vertices freely and co-compactly (i.e., with finitely many orbits). The case of vertex transitive graphs and especially of the Cayley graph is of special interest and is related to many topics in abstract harmonic analysis, operator algebras, asymptotic group theory and theory of random walks. Among open problems, let us mention the following.

Problem 3.

Can the spectrum of a Cayley graph of a finitely generated group be a Cantor set? (i.e., homeomorphic to a Cantor set). The problem is open in both isotropic and anisotropic cases.

 

Problem 4.

Can a torsion free group have a gap in spectrum?

If the answer to the last question is affirmative, then this would give a counterexample to the Kadison-Kaplanski conjecture on idempotents.

Spectral theory of graphs of algebraic origin is a part of spectral theory of convolution operators in ${\ell }^2\left(G\right)$ or ${\ell }^2\left(G\right)\oplus \dots \oplus {\ell }^2\left(G\right)$ given by elements of a group algebra $\mathbb{C}\left[G\right]$ or $n\times n$ matrices with entries in $\mathbb{C}\left[G\right]$ and is closely related to many problems on $L^2$-invariants, including $L^2$-Betti numbers, Novikov-Slubin invariants, etc.

The state of art of the above problem is roughly as follows. Spectra of Euclidean grids (lattices $\cong {\mathbb{Z}}^d$, $d\ge 1$) and of their perturbations is a classical subject based on the use of Bloch-Floquet theory, representation theory of abelian groups and classical methods. The main facts include finiteness of the number of gaps in spectrum, band structure of the spectrum, absence of singular continuous spectrum, finiteness (and in many cases) absence of the discrete part in the spectrum [87].

Another important case is trees and tree like graphs, such as, the Cayley graphs of free groups and free product of finite groups. For these groups the use of representation theory is limited but somehow possible, the structure of the spectrum is similar to the case of graphs with co-compact ${\mathbb{Z}}^d$-action, although the methods are quite different, see [86,88,89,90,91,92,93,94,95,96,97].

One more important case constitute graphs associated with classical and non-classical self-similar fractals or self-similar groups [1,98,99]. In particular, in [1] it is shown that

Theorem 3.

Spectrum of the Schreier graph of self-similar group can be a Cantor set or a Cantor set and a countable set of isolated points accumulated to it.

Recall that in Section 7, for a group acting on rooted tree T, we introduced a sequence ${\left\{{\Gamma }_n\right\}}_{n=1}^{\infty }$ of finite graphs and family ${\left\{{\Gamma }_{\xi }\right\}}_{\xi \in \partial T}$ of infinite graphs. In the next result $M_n$ is a Markov operator associated with ${\Gamma }_n$ and $\kappa$ is the Koopman representation.

Theorem 4.

Let G be a group acting on rooted tree T and$\Sigma =\mathrm{Sp}\left(\kappa \right(M\left)\right)$, where$M={\sum }_{a\in A}(a+a^{-1})\in \mathbb{Z}\left[G\right]$. Then,

1. 

$$\Sigma =\overline{{\cup }_{n}sp\left(M_n\right)}.$$

(24)

2. 

If the action is level transitive and G is amenable, then$\mathrm{Sp}\left({\Gamma }_{\xi }\right)$does not depend on the point$\xi \in \partial T$and is equal to Σ.

3. 

The limit

$${\mu }_{\ast }=\underset{n\to \infty }{lim}{\mu }_n$$

(25)

of counting measures

$${\mu }_n=\frac{1}{|{\Gamma }_n|}\sum _{\lambda \in \mathrm{Sp}\left(M_n\right)}{\delta }_{\lambda }$$

(summation is taken with multiplicities) exists. It is called the density of states.

This result is a combination of observations made in [3,100]. In fact, the relation (24) and the fact about the existence of limit hold not only for elements $M={\sum }_{a\in A}(a+a^{-1})$ of the group algebra (i.e., after normalization corresponding to a simple random walk, i.e., isotropic case) but for arbitrary self-adjoint element of the group algebra.

In [26], the following result related to Theorem 4 is proved.

Theorem 5.

Let $(X,\mu )$ be a measure space and a group G act by transformations preserving the class of measure μ (i.e., $g_{\ast }\mu <\mu$ for all $g\in G$). Let $\kappa :G\to U\left(L^2(X,\mu )\right)$ be the Koopman representation: $\kappa \left(g\right)f\left(x\right)=\sqrt{\frac{dg⁎\mu }{d\mu }}f\left(g^{-1}x\right)$ and π be groupoid representation. Then for any $M\in \mathbb{C}\left[G\right]$,

$$\mathrm{Sp}\left(\kappa \left(M\right)\right)\supset \mathrm{Sp}\left({\Gamma }_x\right)=\mathrm{Sp}\left(\pi \left(M\right)\right)$$

(26)

μ-almost surely (${\Gamma }_x$ is the orbital graph on $Gx$) and if the action $(G,X,\mu )$ is amenable (i.e., partition on orbits is hyperfinite) then in (26) we have equality μ-almost surely instead of inclusion.

For definition of groupoid representation, we direct reader to [26]. Amenable actions are discussed in [82,101].

The idea of approximation of groups in the situation of group action was explored by A. Stepin and A. Vershik in the 1970s [102]. Now the corresponding group property is called local embeddability into finite group (LEF). This is a weaker form of the classical residual finiteness of groups. For instance, topological full groups [103] mentioned in Section 12 are LEF.

Approximation of Ising model in infinite residually finite groups by Ising models on finite quotients is suggested in [104]. The Ising model on self-similar Schreier graphs by finite approximations was studied in [105] and the dimer model on these graphs was studied in [106].

A recent result of B. Simanek and R. Grigorchuk [31] shows that,

Theorem 6.

There are Cayley graphs with infinitely many gaps in the spectrum.

It is a direct consequence of the next theorem.

Theorem 7

([31]). Let $\mathcal{L}$ be the lamplighter group ${\mathbb{Z}}_2\wr \mathbb{Z}$. There is a system of generators $\{a,b\}$ of $\mathcal{L}$ such that the convolution operation $M_{\mu }$ in ${\ell }^2\left(\mathcal{L}\right)$ determined by the element $a+a^{-1}+b+b^{-1}+\mu c$ of the group algebra $\mathbb{R}\left[\mathcal{L}\right]$ where $c=b^{-1}a$, $\mu \in \mathbb{R}$ has pure point spectrum. Moreover,

1. 

if $\left|\mu \right|\le 1$, the eigenvalues of $M_{\mu }$ densely pack the interval $[-4-\mu ,4-\mu ]$.

2. 

If $\left|\mu \right|>1$, the eigenvalues of $M_{\mu }$ form a countable set that densely packs the interval $[-4-\mu ,4-\mu ]$ and also has an accumulation point $\mu +{\displaystyle \frac{2}{\mu }}\notin [-4-\mu ,4-\mu ]$.

3. 

The spectral measure ${\nu }_{\mu }$ of the operator $M_{\mu }$ is discrete and is given by

$${\nu }_{\mu }=\frac{1}{4}{\delta }_{\mu }+\sum _{k=2}^{\infty }\left[\frac{1}{2^{k+1}}\sum _{\{s:G_k(s,\mu )=0\}}{\delta }_s\right],$$

where

$$G_k(z,\mu )=2^k\left[U_k\left(\frac{-z-\mu }{4}\right)+\mu U_{k-1}\left(\frac{-z-\mu }{4}\right)\right],$$

$U_k$ is the degree k Chebyshev polynomial of the second kind.

Observe that if $\mu \ge 2$ is an integer, then the spectrum of the Cayley graph of $\mathcal{L}$ built using the system of generators $a,b,c_1,\dots ,c_{\mu }$ with $c_1=\dots =c_{\mu }=c$ coincides with the spectrum of $M_{\mu }$ and hence has infinitely many gaps. This is the first example of a Cayley graph with infinitely many gaps in the spectrum.

In the case when $\mu =0$, this result was obtained by A. Zuk and R. Grigorchuk [30] and used in [17] to answer a question of M. Atiyah and to give a counterexample to a version of the strong Atiyah conjecture known in 2001. This was done by constructing a 7-dimensional closed Reimannian manifold with third $L^2$-Betti number ${\beta }_2^{\left(3\right)}=\frac{1}{3}$. For more on spectra of Lamplighter type groups and their finite approximations see [107,108].

The Schreier spectrum of the Hanoi Tower group ${\mathcal{H}}^{\left(3\right)}$ is a Cantor set and a countable set of isolated points accumulating to it (see Figure 6) as follows from the following result.

Theorem 8

([32]). The n-th level spectrum $\mathrm{Sp}\left(M_n\right)$ ($n\ge 1$), as a set, has $3·2^{n-1}-1$ points and is equal to

$$\left\{3\right\}\cup \bigcup _{i=0}^{n-1}{f}^{-i}\left(0\right)\cup \bigcup _{j=0}^{n-2}{f}^{-j}(-2).$$

The multiplicity of the $2^i$ level n eigenvalues in $f^{-i}\left(0\right)$, $i=0,\dots ,n-1$ is $a_{n-i}$ and the multiplicity of the $2^j$ eigenvalues in $f^{-j}(-2)$, $j=0,\dots ,n-2$ is $b_{n-j}$, where $f\left(x\right)=x^3-x-3$ and $a_i={\displaystyle \frac{3^{i-1}+3}{2}},b_j={\displaystyle \frac{3^{j-1}-1}{2}}$. Moreover, the Schreier spectrum of ${\mathcal{H}}^{\left(3\right)}$ (i.e., $\mathrm{Sp}\left({\Gamma }_x\right),x\in \partial T$) is equal to

$$\overline{\bigcup _{i=0}^{\infty }{f}^{-i}\left(0\right)}.$$

It consists of a set of isolated points ${\Sigma }_0={\bigcup }_{i=0}^{\infty }{f}^{-i}\left(0\right)$ and its set of accumulation points ${\Sigma }_1$. The set ${\Sigma }_1$ is a Cantor set and is the Julia set of the polynomial f. The density of states is discrete and concentrated on the set ${\bigcup }_{i=0}^{\infty }{f}^{-i}\{0,-2\}$. Its mass at each point of $f^{-i}\{0,-2\}$ is $\frac{1}{6·3^i}$, $i\ge 0$.

Grabowski and Virag [109,110] observed that the Lamplighter group has a system of generators such that the spectral measure is purely singular continuous measure. An infinite family of Schreier graphs with a non-trivial singular continuous part of the spectral measure is constructed in [111,112].

9. Schur Complements

Schur complement is a useful tool in linear algebra, networks, differential operators, applied mathematics, etc. [113]

Let H be a Hilbert space (finite or infinite dimensional) decomposed into a direct sum $H=H_1\oplus H_2$, $H_i\ne \left\{0\right\}$, $i=1,2$. Let $M\in \mathcal{B}\left(H\right)$ be a bounded operator and

$$M=\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)$$

be a matrix representation of M by block matrices corresponding to this decomposition. Thus

$$A:H_1\to H_1,B:H_1\to H_2,C:H_2\to H_1,D:H_2\to H_2.$$

Two partially defined maps $S_1:\mathcal{B}\left(H\right)\to \mathcal{B}\left(H_1\right)$ and $S_2:\mathcal{B}\left(H\right)\to \mathcal{B}\left(H_2\right)$ are defined by,

$$\begin{array}{cc}\hfill S_1\left(M\right)& =A-B{D}^{-1}C,\hfill \\ \hfill S_2\left(M\right)& =D-C{A}^{-1}B,\hfill \end{array}$$

for any $M\in \mathcal{B}\left(H\right)$. Note that $S_1\left(M\right)$ is defined when D is invertible, and $S_2\left(M\right)$ is defined when A is invertible. Maps $S_1,S_2$ are said to be the Schur complements and the following fact holds.

Theorem 9

([20]). Suppose D is invertible. Then M is invertible if and only if $S_1\left(M\right)$ is invertible and

$$M^{-1}=\left(\begin{array}{cc}{S}_1^{-1}& -S_1^{-1}B{D}^{-1}\\ -D^{-1}C{S}_1^{-1}& D^{-1}C{S}_1^{-1}B{D}^{-1}+D^{-1}\end{array}\right),$$

where $S_1=S_1\left(M\right)$.

A similar statement holds for $S_2\left(M\right)$. The above expression for $M^{-1}$ is called Frobenius formula. In the case $dimH<\infty$, the determinant $\left|M\right|$ of matrix M satisfies

$$\left|M\right|=|S_1\left(M\right)\left|\right|D|$$

and the latter relation is attributed to Schur.

There is nothing special in decomposition of H into a direct sum of two subspaces. If $H=H_1\oplus \dots \oplus H_d$ and

$$M=\left(\begin{array}{ccc}{\mathcal{M}}_{11}& \dots & M_{1,d}\\ ⋮& \ddots & ⋮\\ M_{d1}& \dots & M_{dd}\end{array}\right)$$

for $M_{ij}:H_i\to H_j$ and $H=H_1\oplus H_1^{\perp }$, where $H_1^{\perp }=H_2\oplus \dots \oplus H_d$, then we are back in the case $d=2$. By change of the order of the summands (putting $H_i$ on the first place) one can define the i-th Schur complement $S_i\left(M\right)$, for each $i=1,\dots ,d$.

If $dimH=\infty$ and $\psi :H\to H^d$ is a d-similarity, then $S_i\left(M\right)={\left(T_i^{\ast }{M}^{-1}{T}_i\right)}^{-1}$, where $T_i=\rho \left(a_i\right)$ is the image of the generator $a_i$ of the Cuntz algebra ${\mathcal{O}}_d$ under the representation $\rho$ associated with $\psi$ (as explained in Section 4). Therefore, for each $d\ge 2$, one can define ${\mathcal{S}}_d^{\ast }$ the semigroup generated by the Schur transformations $S_i$, $1\le i\le d$ with the operation of composition. We will call ${\mathcal{S}}_d^{\ast }$ the Schur semigroup. For a general element of this semigroup, we get the following expression,

$$S_{i_1}\circ \dots \circ S_{i_k}\left(M\right)={\left({(T_{i_k}\dots T_{I_1})}^{\ast }{M}^{-1}(T_{i_k}\dots T_{i_1})\right)}^{-1}$$

(see Corollary 5.4 in [20]).

The Schur semigroup ${\mathcal{S}}_d^{\ast }$ consists of partially defined transformations on the infinite dimensional space $\mathcal{B}\left(H\right)$. There are examples of finite dimensional subspaces $L\subset \mathcal{B}\left(H\right)$ invariant with respect to ${\mathcal{S}}_d^{\ast }$, where the restrictions of Schur complements to L generates a semigroup of rational transformations on L. An example of this sort is the case of 3-dimensional subspace in $\mathcal{B}\left(H\right)$, for $H=L^2(\partial T,\mu )$, where T is the binary tree and $\mu$ is the uniform Bernoulli measure. It comes from the group $\mathcal{G}$ and L, the space generated by three operators $\kappa \left(a\right),\kappa (b+c+d),I$, where $\kappa$ is the Koopman representation and I is the identity operator. If

$$x\kappa \left(a\right)+y\kappa \left(u\right)+zI\in L,$$

where $u=b+c+d$, then in coordinates $x,y,z$, the Schur complements $S_1,S_2$ are given by

$$\begin{array}{cc}\hfill S_1& =2y\pi \left(a\right)+{\displaystyle \frac{x^{2}y}{(z+3y)(z-y)}}\pi \left(u\right)+\left(z+y-{\displaystyle \frac{z+2y}{(z+3y)(z-y)}}\right)I,\hfill \end{array}$$

(27)

$$\begin{array}{cc}\hfill S_2& ={\displaystyle \frac{2x^{2}y}{(z+3y)(z-y)}}\pi \left(a\right)+y\pi \left(u\right)+\left(z-{\displaystyle \frac{x^2(z+y)}{(z+3y)(z-y)}}\right)I,\hfill \end{array}$$

(28)

and the semigroup $〈S_1,S_2〉$ generated by them is isomorphic to the semigroup $〈F,G〉$ generated by maps (1), (2) (as (27), (28) are homogeneous realizations of $F,G$). Study of properties of the semigroups ${\mathcal{S}}_d^{\ast }$ and its restriction on finite dimensional invariant subspaces is a challenging problem.

10. Self-Similar Random Walks Coming from Self-Similar Groups and the Münchhausen Trick

Let G be a self-similar group acting on $T_d$ and $\mu \in \mathcal{M}\left(G\right)$ (where $\mathcal{M}\left(G\right)$ denotes the simplex of probability measures on G) be a probability measure whose support generates G (we call such $\mu$ non-degenerate). Using $\mu$ one can define a (left) random walk that begins at $1\in G$ and transition $g\to h$ holds with probability $\mu \left(h{g}^{-1}\right)$. Study of random walks on groups is a large area initiated by H. Kesten [86] (see [114,115,116,117,118,119,120] for more on random walks on groups and trees). The main topics of study in random walks are: the asymptotic behavior of the return probabilities $P_{1,1}^{\left(n\right)}$ when $n\to \infty$, the rate of escape, the entropy, the Liouville property and the spectral properties of the Markov operator M acting in ${\ell }^2\left(G\right)$ by

$$\left(Mf\right)\left(g\right)=\sum _{h\in G}\mu \left(h\right)f\left(hg\right),$$

as was discussed in Section 8. The case when the measure $\mu$ is symmetric (i.e., $\mu \left(g\right)=\mu \left(g^{-1}\right)$) is of special interest as in this case M is self-adjoint.

A remarkable progress in the theory of random walks on groups was made by L. Bartholdi and B. Virag. They showed that the self-similarity of a group can be converted into a self-similarity of a random walk on the group and used it for proving the amenability of the group. In such a way it was shown that the Basilica is amenable [121]. The idea of Bartholdi and Virag was developed by V. Kaimanovich in terms of entropy and interpreted as a kind of mathematical implementation of the legendary “Münchhausen trick” [122].

Let us briefly describe the idea of the self-similarity of random walks. Recall, that a self-similar group is determined by the Mealy invertible automaton, or equivalently, by the wreath recursion (14) coming from the embedding $\psi :G\to G{\wr }_X{\mathcal{S}}_d$.

If $Y^{\left(n\right)}$ is a random element of G at the moment $n\in \mathbb{N}$ associated with the random walk determined by $\mu$, then

$$\psi \left(Y^{\left(n\right)}\right)=(Y_1^{\left(n\right)},Y_2^{\left(n\right)},\dots ,Y_d^{\left(n\right)}){\sigma }^{\left(n\right)}.$$

(29)

Let $H=H_i=s{t}_G\left(i\right)$ be the stabilizer of $i\in X$. The index $[G:H]\le d$ is finite and hence the random walk hits H with probability 1. Denote by ${\mu }_H$ the distribution on H given by the probability of the first hit:

$${\mu }_H\left(h\right)=\sum _{n=0}^{\infty }{f}_{1,h}^{\left(n\right)}$$

where $f_{1,h}^{\left(n\right)}$ is the probability of hitting H at the element h for the first time at time n.

Now let us construct transformations $K_i$, $i=1,\dots ,d$ on the space of bounded operators $\mathcal{B}\left(H\right)$ in a Hilbert space $H={\ell }^2\left(G\right)$ when a d-similarity $\phi :H\to H^d=H\oplus \dots \oplus H$ is fixed. Let $S_i$ as before be the i-th Schur complement $1\le i\le d$ associated with $\phi$, $J$ be the map in $\mathcal{B}\left(H\right)$, given by $\mathcal{J}\left(A\right)=A+I$ (where, I is the identity operator). We define $K_i=\mathcal{J}{S}_i{\mathcal{J}}^{-1}$, so if

$$M=\left(\begin{array}{cc}A& B\\ C& D\end{array}\right),$$

where A is an operator acting on the first copy of H in $H\oplus \dots \oplus H$, then

$$K_1\left(M\right)=A+B{(I-D)}^{-1}C.$$

In the case when M is the Markov operator of the random walk on G determined by the measure μ, this leads to the analogous map on simplex $\mathcal{M}\left(G\right)$ which we denote by $k_i$. The measure $k_i\left(\mu \right)$ is called the i-th probabilistic Schur complement.

Theorem 10

([20,122]). Let $p_i:H\to G$ be the i-th projection map ${h\mapsto h|}_i$ (where $H=s{t}_G\left(i\right)$ and ${h|}_i$ is the section of h at vertex i of the first level) and let ${\mu }_i$ be the image of ${\mu }_H$ under $p_i$. Then

$${\mu }_i=k_i\left(\mu \right).$$

In the most interesting cases, the group G acts level transitively (in particular, transitively on the first level) and its action of the first level $V_1$ is a free transitive action of some subgroup $R<S_d$, for instance of ${\mathbb{Z}}_d$ (the latter always holds in the case of binary tree as ${\mathcal{S}}_2={\mathbb{Z}}_2$). In this case for each $i\in X$, $H=s{t}_G\left(i\right)=s{t}_G\left(1\right)$ (where $s{t}_G\left(1\right)$ is the stabilizer of the first level of T), there is a random sequence of hitting times $\tau \left(n\right)$ of the subgroup H so that ${\sigma }^{\tau \left(n\right)}=1$ in (29) and

$$\psi \left(Y^{\tau \left(n\right)}\right)=(Y_1^{\tau \left(n\right)},Y_2^{\tau \left(n\right)},\dots ,Y_d^{\tau \left(n\right)}).$$

Moreover, the random process $Z_i^{\left(n\right)}=Y_i^{\tau \left(n\right)}$ is a random walk on G determined by the measure ${\mu }_i$, $1\le i\le d$. We call ${\mu }_i$ the section (or the projection) of $\mu$ at vertex i.

The maps $k_i:\mathcal{M}\left(G\right)\to \mathcal{M}\left(G\right)$ have the property that they enlarge the weight $\mu \left(1\right)$ of the identity element and hence cannot have fixed points. Now let us resolve this difficulty by following [122] (see also [20]). A measure $\mu$ on a self-similar group is said to be self-similar (or self-affine) at position $i,1\le i\le d$ if for some $\alpha >0$

$${\mu }_i=(1-\alpha ){\delta }_e+\alpha \mu ,$$

(30)

where ${\delta }_e$ is the delta mass at the identity element. Observe that $\mu$ is self-similar at position i if and only if it is a fixed point of the map

$${\tilde{k}}_i:\mu \mapsto \frac{k_i\left(\mu \right)-k_i\left(\mu \right)\left(e\right)}{1-k_i\left(\mu \right)\left(e\right)}.$$

(31)

Thus ${\tilde{k}}_i$ is a modification of $k_i$: we delete from the measure $k_i\left(\mu \right)$ the mass at the identity element and normalize. Note that ${\tilde{k}}_i$ is defined everywhere, except ${\delta }_e$. We can extend it by assigning ${\tilde{k}}_i\left({\delta }_e\right)={\delta }_e$, which makes ${\tilde{k}}_i$ a continuous map $\mathcal{M}\left(G\right)\to \mathcal{M}\left(G\right)$ for the weak topology on $\mathcal{M}\left(G\right)$. We are interested in non-degenerate fixed points because of the following theorem:

Theorem 11.

If a self-similar group G has a non-degenerate symmetric self-similar probability measure, then

1. 

[36] the rate of escape

$$\theta =\underset{n\to \infty }{lim}\frac{1}{n}{Y}^{\left(n\right)}=0,$$

2. 

[122] the entropy

$$h=\underset{n\to \infty }{lim}\frac{1}{n}\sum _{g\in G}{\mu }_n\left(g\right)log{\mu }_n\left(g\right)=0$$

(where ${\mu }_n=\mu \ast \dots \ast \mu$ is the n-th convolution of μ determining the distribution of random walk at time n). Hence the group G is amenable in this case.

In Section 14 we provide an example of self-similar measure in the case of the group $\mathcal{G}$.

11. Can One Hear the Shape of a Group?

One of interesting directions of studies in spectral theory of graphs is finding of iso-spectral but not isomorphic graphs. It is inspired by the famous question of M. Kac, “Can you hear the shape of a drum” [123]. It attracted a lot of attention of researchers, and after several preliminary results, starting with the result of J. Milnor [124], the negative answer was given in 1992 by C. Gordon, D. Webb and S. Walpert, who constructed a pair of plane regions that have different shapes but identical eigenvalues [125]. The regions are concave polygons, their construction uses group theoretical result of T. Sunada [126].

In 1993, A. Valete [127] raised the following question; “Can one hear the shape of a group?”, which means “Does the spectrum of the Cayley graph determines it up to isometry?”. The answer is immediate, and is no as the spectra of all grids ${\mathbb{Z}}^d$, $d\ge 1$ are the same, namely the interval $[-1,1]$. Still the question has some interest. The paper [128] shows that the answer is no in a very strong sense.

Theorem 12

([128]).

1. 

Let ${\mathcal{G}}_{\omega }=\langle S_{\omega }\rangle ,\omega \in \Omega ={\{0,1,2\}}^{\mathbb{N}},S_{\omega }=\{a,b_{\omega }{c}_{\omega },d_{\omega }\}$ be a family of groups of intermediate growth between polynomial and exponential. Then for each $\omega \in \Omega$ the spectrum of the Cayley graph ${\Gamma }_{\omega }=\Gamma ({\mathcal{G}}_{\omega },S_{\omega })$ is the union

$$\Sigma =[-\frac{1}{2},0]\cup [\frac{1}{2},1].$$

2. 

Moreover, for each $\omega \in \Omega$ that is not eventually constant sequence the group ${\mathcal{G}}_{\omega }$ has uncountably many covering amenable groups $\tilde{G}=\langle \tilde{S}\rangle$ (i.e., there is a surjective homomorphism $\tilde{G}\twoheadrightarrow {\mathcal{G}}_{\omega }$) generated by $\tilde{S}=\{\tilde{a},\tilde{b},\tilde{c},\tilde{d}\}$ such that the spectrum of the Cayley graphs $\Gamma (\tilde{G},\tilde{S})$ is the same set $\Sigma =[-\frac{1}{2},0]\cup [\frac{1}{2},1]$.

The proof uses the Hulanicki theorem [129] on characterization of amenable groups in terms of weak containment of the trivial representation in the regular representation, and a weak Hulanicki type theorem for covering graphs. More examples of this sort are in [130]. The above theorem is for the isotropic case. In the anisotrophic case by the result of D. Lenz, T. Nagnibeda and first author [11,29], we know only that $\mathrm{Sp}\left(M_P\right)$ contains a Cantor subset of the Lebesgue measure 0, which is a spectrum of a random Schrödinger operator, whose potential is ruled by the substitutional dynamical system generated by the substitution $\sigma$ used in presentation (3).

In the case of a vertex transitive graph, in particular Cayley graph, a natural choice of a spectral measure is the spectral measure $\nu$ associated with delta function ${\delta }_w$ for $w\in V$. The moments of this measure are the probabilities $P_{w,w}^{\left(n\right)}$ of return.

Problem 5.

Does the spectral measure ν determine Cayley graph of an infinite finitely generated group up to isometry?

12. Substitutional and Schreier Dynamical System

Given an alphabet $A=\{a_1,\dots ,a_m\}$ and a substitution $\rho :A\to A^{\ast },\rho \left(a_i\right)=A_i\left(a_{\mu }\right)$, assuming that for some distinguished symbol $a\in A$, a is a prefix of $\rho \left(a\right)$, we can consider the sequence of iterates

$$a⟶\rho \left(a\right)⟶{\rho }^2\left(a\right)⟶\dots ⟶{\rho }^n\left(a\right)⟶\dots ,$$

where application of $\rho$ to a word $W\in A^{\ast }$ means the replacement of each symbol $a_i$ in A by $\rho \left(a_i\right)$. If we denote $W_n={\rho }^n\left(a\right)$, then $W_n$ is a prefix of $W_{n+1},n=1,2,\dots$ and there is a natural limit

$$W_{\infty }=\underset{n\to \infty }{lim}{W}_n.$$

This limit $W_{\infty }$ is an infinite word over A and the words $W_n$ are prefixes of $W_{\infty }$. Also $W_{\infty }$ is a fixed point of $\rho$: $\rho \left(W_{\infty }\right)=W_{\infty }$. Using $W_{\infty }$, we can now define subshifts of the full shifts $(A^{\mathbb{N}},T)$ and $(A^{\mathbb{Z}},T)$ (where T is a shift map in the space of sequences). Let us do this for the bilateral shift.

Let $\mathcal{L}\left(\rho \right)=\{W\in A^{\ast }\mid W\mathrm{is}\mathrm{a}\mathrm{subword}\mathrm{of}{W}_{\infty }\}$. Equivalently, $\mathcal{L}\left(\rho \right)$ consists of words that appear as a subword of some $W_n$ (and hence in all $W_k,k\ge n$).

Now let ${\Omega }_{\rho }$ be the set of sequences $\omega ={\left({\omega }_n\right)}_{n\in \mathbb{Z}}$ that are unions of words from $\mathcal{L}\left(\rho \right)$, where ${\omega }_n\in A$. In other words, $\omega \in {\Omega }_{\rho }$ if and only if for all $m<0$, $n>0$ there exist $M<m$, $N>n$ such that the subword ${\omega }_M\dots {\omega }_N$ of $\omega$ belongs to $\mathcal{L}\left(\rho \right)$. Obviously, ${\Omega }_{\rho }$ is shift invariant closed subset of $A^{\mathbb{Z}}$. The dynamical system $({\Omega }_{\rho },T)$ with the shift map T restricted to ${\Omega }_{\rho }$ is a substitutional dynamical system generated by $\rho$.

The most important case is when such system is minimal, i.e., for each $x\in {\Omega }_{\rho }$ the orbit ${\left\{T^{n}x\right\}}_{n=-\infty }^{\infty }$ is dense in ${\Omega }_{\rho }$. For instance, this is the case when the substitution $\rho$ is primitive, which means that there exists K such that for each $i,j,1\le i,j\le m$ the symbol $a_i$ occur in the word ${\rho }^K\left(a_j\right)$.

By Krylov-Bogolyubov theorem, the system $({\Omega }_{\tau },T)$ has at least one T-invariant probability measure and the invariant ergodic measures (i.e., extreme points of the simplex of T-invariant probability measures) are of special interest. Another important case is when the system $({\Omega }_{\rho },T)$ is uniquely ergodic, i.e., there is only one invariant probability measure (necessarily ergodic).

A subshift $({\Omega }_{\rho },T)$ is called linearly repetitive (LR) if there exists a constant C such that any word $W\in \mathcal{L}\left(\rho \right)$ occurs in any word $U\in \mathcal{L}\left(\rho \right)$ of length $\ge C\left|W\right|$. This is a stronger condition than minimality. The following result goes back to M. Boshernitzan [131] (see also [132]).

Theorem 13.

Let $(\Omega ,T)$ be a linearly repetitive subshift. Then, the subshift is uniquely ergodic.

Here, it is not necessary for the subshift to be generated by a substitution. It is known that subshifts associated with primitive substitutions are linearly repetitive [133,134]. Theorem 1 of [135] shows that linear repetitivity in fact holds for subshifts associated to any substitution provided minimality holds. Unique ergodicity is then a direct consequence of linear repetitivity due to Theorem 13.

The classical example of a substitutional system is the Thue-Morse system determined by the substitution $0⟶01,1⟶10$ over binary alphabet [40].

Following [11,25,29] we consider the substitution $\sigma :a⟶aca,b⟶d,c⟶b,d⟶c$ over alphabet $\{a,b,c,d\}$ and system $({\Omega }_{\sigma },T)$ generated by it. Despite $\sigma$ not being primitive, the system $({\Omega }_{\sigma },T)$ satisfies the linear repetivity property (in fact the same system can be generated by a primitive substitution ${\sigma }^{\prime }:a⟶ac,b⟶ac,c⟶ad,d⟶ab$).

An additional property of the fixed point $\eta ={lim}_{n\to \infty }{\sigma }^n\left(a\right)$ is that it is a Toeplitz sequence. i.e., for each entry ${\eta }_n$ of $\eta ={\left({\eta }_n\right)}_{n=0}^{\infty }$ there is period $p=p\left(n\right)$ such that all entries with indices of the form $n+pk,k=0,1,\dots$ contain the same symbol ${\eta }_n$. In our case the periods have the form $2^l,l\in \mathbb{N}$. More on combinatorial properties of $\eta$ and associated system see [29].

Our interest in the substitution $\sigma$ and the associated subshift comes from following four facts:

• The substitution $\sigma$ appears in the presentation (3) of the group $\mathcal{G}=〈a,b,c,d〉$ of intermediate growth by generators and relations, so it determines the group modulo finite set of relators.
• The system $({\Omega }_{\sigma },T)$ gives a model for a Schreier dynamical system (in terminology of [19]) determined by the action of $\mathcal{G}$ on the boundary $\partial T$ of binary tree.
• The latter property allows us to translate the spectral properties of Schreier graphs ${\Gamma }_x,x\in \partial T$ into the spectral properties of the corresponding random Schrödinger operator and conclude that in anisotropic case the spectrum is a Cantor set of Lebesgue measure zero [11,25].
• The group $\mathcal{G}$ embeds into the topological full group $\left[\right[\sigma \left]\right]$ associated with the subshift $({\Omega }_{\sigma },T)$.

For any minimal action $\alpha$ of a group G on a Cantor set X, one can define a topological full group (TFG in short) $\left[\right[\alpha \left]\right]$ as a group consisting of homeomorphisms $h\in Homeo\left(X\right)$ that locally act as elements of G. If G is the infinite cyclic group generated by a minimal homeomorphism of a Cantor set, the TFG is an invariant of the Cantor minimal system up to the flip conjugacy [136] and its commutator ${\left[\left[\alpha \right]\right]}^{\prime }$ is a simple group. Moreover, ${\left[\left[\alpha \right]\right]}^{\prime }$ is finitely generated if the system is conjugate to a minimal subshift over a finite alphabet. It was conjectured by K. Medynets and the first author, and proved by K. Juschenko and N. Monod [137] that if $G=\mathbb{Z}$, then $\left[\right[\alpha \left]\right]$ is amenable. Thus TFGs are a rich source of non-elementary amenable groups, and satisfy many unusual properties [103,138]. N. Matte Bon observed that $\mathcal{G}$ embeds into $\left[\right[\sigma \left]\right]$, where $\sigma$ is the substitution from (3) [139]. A similar result holds for overgroup $\tilde{\mathcal{G}}$.

Study of substitutional dynamical systems and more generally of aperiodic order is a rich area of mathematics (see [140,141] and references there for instance). A special attention is paid to the classical substitutions like Thue-Morse, Arshon [142], and Rudin-Shapiro substitutions.

Problem 6.

For which primitive substitutions τ, the TFG $\left[\right[\tau \left]\right]$, contains a subgroup of intermediate growth? contains a subgroup of Burnside type (i.e., finitely generated infinite torsion group)? In particular, does the classical substitutions listed above have such properties?

Given a Schreier graph $\Gamma =\Gamma (G,H,A)\in {\mathcal{X}}_m^{\mathrm{Sch}}$, one can consider the action of G on $\left\{\right(\Gamma ,v)\mid v\in V\}$ (i.e., on the set of marked graphs where $(\Gamma ,v)\stackrel{g}{\to }(\Gamma ,gv)$) and extend it to the action on the closure $\overline{\left\{\right(\Gamma ,v)\mid v\in V\}}$ in ${\mathcal{X}}_m^{\mathrm{Sch}}$. This is called in [19] a Schreier dynamical system. Study of such systems is closely related to the study of invariant random subgroups. In important cases, such systems allows to recover the original action $(G,X)$ if $\Gamma ={\Gamma }_x$, $x\in X$ is an orbital graph. In particular, this holds if the action is extremely non-free (i.e., stabilizers $G_x$ of different points $x\in X$ are distinct). The action of $\mathcal{G}$ and any group of branch type is extremely non-free. More on this is in [19].

13. Computation of Schur Maps for $\mathcal{G}$ and $\tilde{\mathcal{G}}$

Recall the matrix recursions between generators of $\mathcal{G}=〈a,b,c,d〉$ (see (22)),

$$\begin{array}{cccccccccc}\hfill 1& =\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),\hfill & \hfill a& =\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),\hfill & \hfill b& =\left(\begin{array}{cc}a& 0\\ 0& c\end{array}\right),\hfill & \hfill c& =\left(\begin{array}{cc}a& 0\\ 0& d\end{array}\right),\hfill & \hfill d& =\left(\begin{array}{cc}1& 0\\ 0& b\end{array}\right).\hfill \end{array}$$

Let $M=xa+yb+zc+ud+v1$ be an element of the group algebra $\mathbb{C}\left[\mathcal{G}\right]$. By using (22), we identify,

$$M=\left(\begin{array}{cc}(y+z)a+(u+v)1& x\\ x& ub+yc+zd+v1\end{array}\right).$$

(32)

First we will calculate the first Schur complement $S_1\left(M\right)$, which is defined when $D=v1+ub+yc+zd$ is invertible. Since the group generated by $\{1,b,c,d\}$ is isomorphic to ${\mathbb{Z}}_2^2$ (via the identification $1,b,c,d$ with $(0,0),(1,0),(0,1),(1,1)$, respectively), by a direct calculation, we obtain that D is invertible if and only if

$$(v+u+y+z)(v-u+y-z)(v+u-y-z)(v-u-y+z)\ne 0,$$

(33)

and if the condition in (33) is satisfied, then $D^{-1}$ is given by,

$$\begin{array}{cc}\hfill D^{-1}=& \frac{1}{4}\left(\frac{1}{v+u+y+z}+\frac{1}{v-u+y-z}+\frac{1}{v+u-y-z}+\frac{1}{v-u-y+z}\right)1\hfill \\ \hfill & +\frac{1}{4}\left(\frac{1}{(v+u+y+z)}-\frac{1}{v-u+y-z}+\frac{1}{v+u-y-z}-\frac{1}{v-u-y+z}\right)b\hfill \\ \hfill & +\frac{1}{4}\left(\frac{1}{(v+u+y+z)}+\frac{1}{v-u+y-z}-\frac{1}{v+u-y-z}-\frac{1}{v-u-y+z}\right)c\hfill \\ \hfill & +\frac{1}{4}\left(\frac{1}{(v+u+y+z)}-\frac{1}{v-u+y-z}-\frac{1}{v+u-y-z}+\frac{1}{v-u-y+z}\right)d.\hfill \end{array}$$

Therefore,

$$\begin{array}{cc}\hfill S_1\left(M\right)=& A-B{D}^{-1}C\hfill \\ \hfill =& (y+z)a+(v+u)1-x^2{D}^{-1}\hfill \\ \hfill =& (y+z)a\hfill \\ \hfill & +\left(v+u-x^2\frac{2uyz-v(-v^2+u^2+y^2+z^2)}{(v+u+y+z)(v-u+y-z)(v+u-y-z)(v-u-y+z)}\right)1\hfill \\ \hfill & -x^2\frac{2vyz-u(v^2-u^2+y^2+z^2)}{(v+u+y+z)(v-u+y-z)(v+u-y-z)(v-u-y+z)}b\hfill \\ \hfill & -x^2\frac{2vuz-y(v^2+u^2-y^2+z^2)}{(v+u+y+z)(v-u+y-z)(v+u-y-z)(v-u-y+z)}c\hfill \\ \hfill & -x^2\frac{2vuy-z(v^2+u^2+y^2-z^2)}{(v+u+y+z)(v-u+y-z)(v+u-y-z)(v-u-y+z)}d.\hfill \end{array}$$

This leads to the map $\tilde{G}:{\mathbb{C}}^5\to {\mathbb{C}}^5$ given in (6).

Now we will calculate the second Schur complement $S_2\left(M\right)$ which is defined when $A=(y+z)a+(u+v)1$ is invertible. Since the group generated by $\{1,a\}$ is isomorphic to ${\mathbb{Z}}_2$ (via the identification $1,a$ with $0,1$, respectively), by a direct calculation, we obtain that A is invertible if and only if

$$(v+u+y+z)(v+u-y-z)\ne 0,$$

(34)

and if the condition in (34) is satisfied, then $A^{-1}$ is given by,

$$\begin{array}{cc}\hfill A^{-1}& =\frac{1}{2}\left(\frac{1}{v+u+y+z}+\frac{1}{v+u-y-z}\right)1+\frac{1}{2}\left(\frac{1}{v+u+y+z}-\frac{1}{v+u-y-z}\right)a\hfill \\ \hfill & =\frac{v+u}{(v+u+y+z)(v+u-y-z)}1-\frac{y+z}{(v+u+y+z)(v+u-y-z)}a.\hfill \end{array}$$

Therefore,

$$\begin{array}{cc}\hfill S_2\left(M\right)=& D-C{A}^{-1}B\hfill \\ \hfill =& v1+ub+yc+zd-x^2{A}^{-1}\hfill \\ \hfill =& \frac{x^2(y+z)}{(v+u+y+z)(v+u-y-z)}a+ub+yc+zd+\left(v-\frac{x^2(v+u)}{(v+u+y+z)(v+u-y-z)}\right)1.\hfill \end{array}$$

This leads to the map $\tilde{F}:{\mathbb{C}}^5\to {\mathbb{C}}^5$ given in (5).

Now consider the case where $y=z=u=1$. Note that $\tilde{F}$ fixes second, third and fourth coordinates and so we may restrict the map to first and fifth coordinates. Therefore we get ${\mathbb{C}}^2\to {\mathbb{C}}^2$ map

$$\tilde{F}:\left(\begin{array}{c}x\\ v\end{array}\right)\mapsto \left(\begin{array}{c}{\displaystyle \frac{2x^2}{(v+3)(v-1)}}\\ v-{\displaystyle \frac{x^2(v+1)}{(v+3)(v-1)}}\end{array}\right).$$

By the change of coordinates $(x,v)\to (-x,-1-y)$, we obtain F given in (1).

Now note that second, third and fourth coordinates of $\tilde{G}$ are the same and are equal to ${\displaystyle \frac{x^2}{(v+3)(v-1)}}$. By re-normalization (i.e., multiplying by $\frac{(v+3)(v-1)}{x^2}$) we obtain a map which fixes second, third and fourth coordinates. So we may restrict the map to first and fifth coordinates and get ${\mathbb{C}}^2\to {\mathbb{C}}^2$ map

$$\tilde{G}:\left(\begin{array}{c}x\\ v\end{array}\right)\mapsto \left(\begin{array}{c}{\displaystyle \frac{2(v+3)(v-1)}{x^2}}\\ -2-v+(v+1){\displaystyle \frac{(v+3)(v-1)}{x^2}}\end{array}\right).$$

By the change of coordinates $(x,v)\to (-x,-1-y)$, we obtain G given in (2).

Now consider the overgroup $\tilde{\mathcal{G}}=〈a,\tilde{b},\tilde{c},\tilde{d}〉\le \mathrm{Aut}\left(T_2\right)$, where $\tilde{b},\tilde{c},\tilde{d}$ satisfy matrix recursions given by (35) and a is a generator of $\mathcal{G}$. We have $b=\tilde{c}\tilde{d}$, $c=\tilde{b}\tilde{d}$, $d=\tilde{b}\tilde{c}$ and hence $\mathcal{G}$ is a subgroup of $\tilde{\mathcal{G}}$. It will be convenient to consider $\tilde{\mathcal{G}}$ as a group generated by eight elements $a,b,c,d,\tilde{a},\tilde{b},\tilde{c},\tilde{d}$, where $\tilde{a}$ satisfies the matrix recursion in (35).

$$\begin{array}{cccccccc}\hfill \tilde{a}& =\left(\begin{array}{cc}a& 0\\ 0& \tilde{a}\end{array}\right),\hfill & \hfill \tilde{b}& =\left(\begin{array}{cc}1& 0\\ 0& \tilde{c}\end{array}\right),\hfill & \hfill \tilde{c}& =\left(\begin{array}{cc}1& 0\\ 0& \tilde{d}\end{array}\right),\hfill & \hfill \tilde{d}& =\left(\begin{array}{cc}a& 0\\ 0& \tilde{b}\end{array}\right).\hfill \end{array}$$

(35)

$\mathcal{G}$ is a subgroup of $\tilde{\mathcal{G}}$ and so $\mathbb{C}\left[\mathcal{G}\right]$ is a subalgebra of $\mathbb{C}\left[\tilde{\mathcal{G}}\right]$. So we can use (22) as the matrix recursions of $1,a,b,c,d$. Let $M=xa+yb+zc+ud+q\tilde{a}+r\tilde{b}+s\tilde{c}+t\tilde{d}+v1$. By using (35) and (22), we obtain the matrix recursion of M as,

$$M=\left(\begin{array}{cc}(y+z+q+t)a+(u+r+s+v)1& x\\ x& ub+yc+zd+q\tilde{a}+t\tilde{b}+r\tilde{c}+s\tilde{d}+v1\end{array}\right).$$

(36)

We can calculate first and second Schur complements $S_1\left(M\right),S_2\left(M\right)$, and the multi-dimensional maps ${\tilde{S}}_1,{\tilde{S}}_2$ associated with them as we did for the case of $\mathcal{G}$. These maps are nine-dimensional and are given by

$${\tilde{S}}_1:\left(\begin{array}{c}x\\ y\\ z\\ u\\ q\\ r\\ s\\ t\\ v\end{array}\right)\mapsto \left(\begin{array}{c}y+z+q+t\\ -\frac{x^2}{8}\left(\frac{1}{{\widehat{D}}_{000}}-\frac{1}{{\widehat{D}}_{100}}+\frac{1}{{\widehat{D}}_{010}}+\frac{1}{{\widehat{D}}_{001}}-\frac{1}{{\widehat{D}}_{110}}-\frac{1}{{\widehat{D}}_{101}}+\frac{1}{{\widehat{D}}_{011}}-\frac{1}{{\widehat{D}}_{111}}\right)\\ -\frac{x^2}{8}\left(\frac{1}{{\widehat{D}}_{000}}+\frac{1}{{\widehat{D}}_{100}}-\frac{1}{{\widehat{D}}_{010}}+\frac{1}{{\widehat{D}}_{001}}-\frac{1}{{\widehat{D}}_{110}}+\frac{1}{{\widehat{D}}_{101}}-\frac{1}{{\widehat{D}}_{011}}-\frac{1}{{\widehat{D}}_{111}}\right)\\ -\frac{x^2}{8}\left(\frac{1}{{\widehat{D}}_{000}}-\frac{1}{{\widehat{D}}_{100}}-\frac{1}{{\widehat{D}}_{010}}+\frac{1}{{\widehat{D}}_{001}}+\frac{1}{{\widehat{D}}_{110}}-\frac{1}{{\widehat{D}}_{101}}-\frac{1}{{\widehat{D}}_{011}}+\frac{1}{{\widehat{D}}_{111}}\right)\\ -\frac{x^2}{8}\left(\frac{1}{{\widehat{D}}_{000}}-\frac{1}{{\widehat{D}}_{100}}-\frac{1}{{\widehat{D}}_{010}}-\frac{1}{{\widehat{D}}_{001}}+\frac{1}{{\widehat{D}}_{110}}+\frac{1}{{\widehat{D}}_{101}}+\frac{1}{{\widehat{D}}_{011}}-\frac{1}{{\widehat{D}}_{111}}\right)\\ -\frac{x^2}{8}\left(\frac{1}{{\widehat{D}}_{000}}+\frac{1}{{\widehat{D}}_{100}}-\frac{1}{{\widehat{D}}_{010}}-\frac{1}{{\widehat{D}}_{001}}-\frac{1}{{\widehat{D}}_{110}}-\frac{1}{{\widehat{D}}_{101}}+\frac{1}{{\widehat{D}}_{011}}+\frac{1}{{\widehat{D}}_{111}}\right)\\ -\frac{x^2}{8}\left(\frac{1}{{\widehat{D}}_{000}}-\frac{1}{{\widehat{D}}_{100}}+\frac{1}{{\widehat{D}}_{010}}-\frac{1}{{\widehat{D}}_{001}}-\frac{1}{{\widehat{D}}_{110}}+\frac{1}{{\widehat{D}}_{101}}-\frac{1}{{\widehat{D}}_{011}}+\frac{1}{{\widehat{D}}_{111}}\right)\\ -\frac{x^2}{8}\left(\frac{1}{{\widehat{D}}_{000}}+\frac{1}{{\widehat{D}}_{100}}+\frac{1}{{\widehat{D}}_{010}}-\frac{1}{{\widehat{D}}_{001}}+\frac{1}{{\widehat{D}}_{110}}-\frac{1}{{\widehat{D}}_{101}}-\frac{1}{{\widehat{D}}_{011}}-\frac{1}{{\widehat{D}}_{111}}\right)\\ \left((u+r+s+v)-\frac{x^2}{8}\left(\frac{1}{{\widehat{D}}_{000}}+\frac{1}{{\widehat{D}}_{100}}+\frac{1}{{\widehat{D}}_{010}}+\frac{1}{{\widehat{D}}_{001}}+\frac{1}{{\widehat{D}}_{110}}+\frac{1}{{\widehat{D}}_{101}}+\frac{1}{{\widehat{D}}_{011}}+\frac{1}{{\widehat{D}}_{111}}\right)\right)\end{array}\right),$$

$${\tilde{S}}_2:\left(\begin{array}{c}x\\ y\\ z\\ u\\ q\\ r\\ s\\ t\\ v\end{array}\right)\mapsto \left(\begin{array}{c}\frac{x^2(y+z+q+t)}{(v+u+r+s+y+z+q+t)(v+u+r+s-y-z-q-t)}\\ u\\ y\\ z\\ q\\ t\\ r\\ s\\ v-\frac{x^2(v+u+r+s)}{(v+u+r+s+y+z+q+t)(v+u+r+s-y-z-q-t)}\end{array}\right),$$

(37)

where

$$\begin{array}{cc}\hfill {\widehat{D}}_{000}& =v+u+y+s+z+r+t+q,\hfill \\ \hfill {\widehat{D}}_{100}& =v-u+y+s-z-r+t-q,\hfill \\ \hfill {\widehat{D}}_{010}& =v+u-y+s-z+r-t-q,\hfill \\ \hfill {\widehat{D}}_{001}& =v+u+y-s+z-r-t-q,\hfill \\ \hfill {\widehat{D}}_{110}& =v-u-y+s+z-r-t+q,\hfill \\ \hfill {\widehat{D}}_{101}& =v-u+y-s-z+r-t+q,\hfill \\ \hfill {\widehat{D}}_{011}& =v+u-y-s-z-r+t+q,\hfill \\ \hfill {\widehat{D}}_{111}& =v-u-y-s+z+r+t-q.\hfill \end{array}$$

(38)

14. Probabilistic Schur Map for $\mathcal{G}$

Recall that maps $k_i\left(\mu \right)$ were defined by (31). Let $M=xa+yb+zc+ud\in \mathbb{C}\left[\mathcal{G}\right]$ be the Markov operator of random walk determined by the measure $\mu =x{\delta }_a+y{\delta }_b+z{\delta }_c+u{\delta }_d$, supported on the generating set of $\mathcal{G}$ (i.e., $x,y,z,u>0$ and $x+y+z+u=1$). By (32), taking $v=0$ gives the matrix recursion,

$$M=\left(\begin{array}{cc}(y+z)a+\left(u\right)1& x\\ x& ub+yc+zd\end{array}\right).$$

(39)

Recall that $K_i=\mathcal{J}{S}_i{\mathcal{J}}^{-1}$ (where $\mathcal{J}$ is the shift map and $S_i$ is the i-th Schur complement) and $k_i$ is the analogous map on the simplex of probability measures $\mathcal{M}\left(G\right)$ (see Theorem 10). Then,

$$k_i\left(\mu \right)=X_i{\delta }_a+Y_i{\delta }_b+Z_i{\delta }_c+U_i{\delta }_d+V_i{\delta }_e$$

for i = 1,2, where

$$\begin{array}{cc}\hfill X_1& =y+z,\hfill \\ \hfill V_1& =u-\frac{x^2(2uyz+u^2+y^2+z^2-1)}{(u+y+z-1)(-u+y-z-1)(u-y-z-1)(-u-y+z-1)},\hfill \\ \hfill Y_1& =\frac{x^2(2yz+u(1-u^2+y^2+z^2))}{(u+y+z-1)(-u+y-z-1)(u-y-z-1)(-u-y+z-1)},\hfill \\ \hfill Z_1& =\frac{x^2(2uz+y(1+u^2-y^2+z^2))}{(u+y+z-1)(-u+y-z-1)(u-y-z-1)(-u-y+z-1)},\hfill \\ \hfill U_1& =\frac{x^2(2uy+z(1+u^2+y^2-z^2))}{(u+y+z-1)(-u+y-z-1)(u-y-z-1)(-u-y+z-1)},\hfill \end{array}$$

(40)

and

$$\begin{array}{cc}\hfill X_2& =\frac{x^2(y+z)}{(1-u-y-z)(1-u+y+z)},\hfill \\ \hfill V_2& =\frac{x^2(1-u)}{(1-u-y-z)(1-u+y+z)},\hfill \\ \hfill Y_2& =u,\hfill \\ \hfill Z_2& =y,\hfill \\ \hfill U_2& =z.\hfill \end{array}$$

We are interested in self-similar measures (i.e., measures that satisfy (30) or, which is the same, fixed points of the map (31)). A direct calculation shows that ${\tilde{k}}_2$ defined by (31) has no fixed points and so $\mu$ is not self-similar at the second coordinate. Therefore we restrict the rest of the section to study the map ${\tilde{k}}_1$.

In order to understand ${\tilde{k}}_1$, we extend it to the map,

$$\begin{array}{cc}\hfill {\widehat{k}}_1:\Delta & \to \Delta \hfill \\ \hfill (x,y,z,u)& \mapsto \left(\frac{X_1}{1-V_1},\frac{Y_1}{1-V_1},\frac{Z_1}{1-V_1},\frac{U_1}{1-V_1}\right),\hfill \end{array}$$

where $\Delta$ is the 3-simplex $\left\{\right(x,y,z,u)\mid x+y+z+u=1,x,y,z,u\ge 0\}$. Note that the vertices (three coordinates are 0), the edges (two coordinates are 0), and the face $x=0$ correspond to degenerate probability measures $\mu$, whereas the faces $y=0$, $z=0$, and $u=0$ correspond to non-degenerate measures in $\mathcal{M}\left(\mathcal{G}\right)$. This is due to the fact that the group $\mathcal{G}$ is in fact 3-generated and removing exactly one of the elements $b,c$ or d form the set $\{a,b,c,d\}$, still generates $\mathcal{G}$. A direct calculation yields the following proposition.

Proposition 1.

Consider the map ${\widehat{k}}_1$ given above. Then;

1. 

All vertices are indeterminacy points.

2. 

The edge $(x,y,0,0)$ maps to the edge $(X,0,Z,0)$, the edge $(x,0,z,0)$ maps to the edge $(X,0,0,U)$, and the edge $(x,0,0,0)$ maps to the vertex $(0,1,0,0)$.

3. 

The face $x=0$ maps to the vertex $(1,0,0,0)$ and the faces $y=0,z=0$ and $u=0$ map to the interior of the 3-simplex Δ. (See Figure 15.)

4. 

Interior of Δ maps to itself.

${\tilde{k}}_1$ has a fixed point $\left(4/7,1/7,1/7,1/7\right)\in \Delta$ and thus

$${\tilde{k}}_1\left(\mu \right)=\left(1-\frac{1}{2}\right){\delta }_e+\frac{1}{2}\mu .$$

Problem 7.

Describe all fixed points of the maps ${\tilde{k}}_1,\widetilde{k_2}:\mathcal{M}\left(\mathcal{G}\right)\to \mathcal{M}\left(\mathcal{G}\right)$.

15. Random Groups $\left\{{\mathcal{G}}_{\mathit{\omega }}\right\}$ and Associated 4–Parametric Family of Maps

Here we will introduce a family of subgroups of $\mathrm{Aut}{T}_2$, $\{{\mathcal{G}}_{\omega }\mid \omega \in \Omega \}$, where $\Omega ={\{0,1,2\}}^{\mathbb{N}}$. Since each element in $\mathrm{Aut}{T}_2$ can be defined by wreath recursions (14), for $\omega ={\omega }_0{\omega }_1\dots \in \Omega$, we define recursively,

$$\begin{array}{cccccc}\hfill b_{\omega }& =(b_{{\omega }_0},b_{T\omega }),\hfill & \hfill c_{\omega }& =(c_{{\omega }_0},c_{T\omega }),\hfill & \hfill d_{\omega }& =(d_{{\omega }_0},d_{T\omega }),\hfill \end{array}$$

(41)

where T is the left shift operator on $\Omega$, $b_0=b_1=c_0=c_2=d_1=d_2=a$, and $b_2=c_1=d_0=1$. Here $a=(1,1)\sigma$ where $\sigma$ is the permutation of the symmetric group ${\mathcal{S}}_2$. Now define

$${\mathcal{G}}_{\omega }=〈a,b_{\omega },c_{\omega },d_{\omega }〉.$$

(42)

By (41) we obtain the recursions for the Koopman representation

$$\begin{array}{cccccccc}\hfill a& =\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),\hfill & \hfill b_{\omega }& =\left(\begin{array}{cc}{b}_{{\omega }_0}& 0\\ 0& b_{T\omega }\end{array}\right),\hfill & \hfill c_{\omega }& =\left(\begin{array}{cc}{c}_{{\omega }_0}& 0\\ 0& c_{T\omega }\end{array}\right),\hfill & \hfill d_{\omega }& =\left(\begin{array}{cc}{d}_{{\omega }_0}& 0\\ 0& d_{T\omega }\end{array}\right).\hfill \end{array}$$

For $M=xa+y{b}_{\omega }+z{c}_{\omega }+u{d}_{\omega }+v1$, an element of the group algebra $\mathbb{C}\left[{\mathcal{G}}_{\omega }\right]$, using above matrix recursions, we identify,

$$M=\left(\begin{array}{cc}y{b}_{{\omega }_0}+z{c}_{{\omega }_0}+u{d}_{{\omega }_0}+v1& x\\ x& y{b}_{T\omega }+z{c}_{T\omega }+u{d}_{T\omega }+v1\end{array}\right).$$

(43)

We are interested in calculating the Schur maps associated with M. Direct calculation shows that the second Schur complement

$$S_2\left(M\right)=\left\{\begin{array}{cc}\frac{x^2(y+z)}{(v+u+y+z)(v+u-y-z)}a+y{b}_{T\omega }+z{c}_{T\omega }+u{d}_{T\omega }+\left(v-\frac{x^2(v+u)}{(v+u+y+z)(v+u-y-z)}\right)1\hfill & ;{\omega }_0=0\hfill \\ \frac{x^2(y+u)}{(v+z+u+y)(v+z-u-y)}a+y{b}_{T\omega }+z{c}_{T\omega }+u{d}_{T\omega }+\left(v-\frac{x^2(v+z)}{(v+z+u+y)(v+z-u-y)}\right)1\hfill & ;{\omega }_0=1\hfill \\ \frac{x^2(z+u)}{(v+y+z+u)(v+y-z-u)}a+y{b}_{T\omega }+z{c}_{T\omega }+u{d}_{T\omega }+\left(v-\frac{x^2(v+y)}{(v+y+z+u)(v+y-z-u)}\right)1\hfill & ;{\omega }_0=2\hfill \end{array}\right..$$

Note that the middle three coefficients under $S_2$ are fixed and so independent of $\omega$ (or ${\omega }_0$). This allows us to reduce the second Schur map into two dimensional maps (i.e., $\mathbb{C}\to \mathbb{C}$) on three parameters $y,z,u$ and symbols $0,1,2$;

$$F_0:\left(\begin{array}{c}x\\ v\end{array}\right)\mapsto \left(\begin{array}{c}{\displaystyle \frac{x^2(y+z)}{(v+u+y+z)(v+u-y-z)}}\\ v-{\displaystyle \frac{x^2(v+u)}{(v+u+y+z)(v+u-y-z)}}\end{array}\right),$$

(44)

$$F_1:\left(\begin{array}{c}x\\ v\end{array}\right)\mapsto \left(\begin{array}{c}{\displaystyle \frac{x^2(y+u)}{(v+z+u+y)(v+z-u-y)}}\\ v-{\displaystyle \frac{x^2(v+z)}{(v+z+u+y)(v+z-u-y)}}\end{array}\right),$$

$$F_2:\left(\begin{array}{c}x\\ v\end{array}\right)\mapsto \left(\begin{array}{c}{\displaystyle \frac{x^2(z+u)}{(v+y+z+u)(v+y-z-u)}}\\ v-{\displaystyle \frac{x^2(v+y)}{(v+y+z+u)(v+y-z-u)}}\end{array}\right).$$

Thus for a given $\omega \in \Omega$, applying the second Schur complement n times is equivalent to taking composition $F_{{\omega }_{n-1}}\circ \dots \circ F_{{\omega }_0}$.

Consider the family of 2-dimensional (i.e., ${\mathbb{C}}^2\to {\mathbb{C}}^2$) 4–parametric maps $\{F_{(\alpha ,\beta ,\gamma ,\delta )}\mid \alpha ,\beta ,\gamma ,\delta \in \mathbb{C}\}$ given by

$$F_{(\alpha ,\beta ,\gamma ,\delta )}:\left(\begin{array}{c}x\\ v\end{array}\right)\mapsto \left(\begin{array}{c}{\displaystyle \frac{\alpha x^2}{(v+\gamma )(v+\delta )}}\\ v-{\displaystyle \frac{(v+\beta )x^2}{(v+\gamma )(v+\delta )}}\end{array}\right).$$

(45)

The maps $F_0,F_1$ and $F_2$ belong to the above family and correspond to the case when $\gamma =\beta +\alpha$ and $\delta =\beta -\alpha$, where $\alpha ,\beta$ are parameters depending on $y,z$ and u, according to (44).

Therefore, $F_0,F_1$ and $F_2$ belong to the 2–parametric family $\left\{F_{(\alpha ,\beta )}\right\}$, where $F_{(\alpha ,\beta )}=F_{(\alpha ,\beta ,\beta +\alpha ,\beta -\alpha )}$. Similar to (44), maps can be written for generalized overgroups ${\tilde{\mathcal{G}}}_{\omega }$. They also fit in the 2–parametric family $\left\{F_{(\alpha ,\beta )}\right\}$.

Dynamical pictures of composition of the above maps for some sequences $\omega \in \Omega$ are shown in Figure 3. The first Schur maps are much more complicated and so we have restricted this discussion to the second Schur map.

16. Random Model and Concluding Remarks

As explained above, the spectral problem associated with groups and their Schreier graphs in many important examples could be converted into study of invariant sets and dynamical properties of multi-dimensional rational maps. Some of these maps, like (1), (2), (7), (8) demonstrate strong integrability features explored in [1,3,32,33]. The roots of their integrability are comprehensively investigated in [24]. The examples given by (5), (6), (9), (10), (11), (37) are much more complicated. They have an invariant set of fractal nature, and computer simulations demonstrate their chaotic behavior, shown by dynamical pictures given by Figure 3 and Figure 7.

The families of groups ${\mathcal{G}}_{\omega },{\tilde{\mathcal{G}}}_{\omega },$$\omega \in \Omega ={\{0,1,2\}}^{\mathbb{N}}$ (and many other similar families can be created) can be viewed as a random group if $\Omega$ is supplied with a shift invariant probability measure (for instance, Bernoulli or more generally Markov measure). The first step in this direction is publication [143] where it is shown that for any ergodic shift invariant probability measure satisfying a mild extra condition (all Bernoulli measures satisfy it), there is a constant $\beta <1$ such that the growth function ${\gamma }_{{\mathcal{G}}_{\omega }}\left(n\right)$ is bounded by $e^{n^{\beta }}$.

More general model would be to supply the space $\mathcal{M}={\bigcup }_{k=1}^{\infty }{\mathcal{M}}_k$ of finitely generated groups or any of its subspaces ${\mathcal{M}}_k$ with a measure $\mu$ (finite, or infinite, invariant or quasi-invariant with respect to any reasonable group or semigroup of transformations of the space) and study the typical properties of groups with respect to $\mu$. The system $({\mathcal{G}}_{\omega },\Omega ,T,\mu )$ (where T denotes the shift) is just one example of this sort. As suggested in [18], it would be wonderful if one could supply the space $\mathcal{M}$ with a measure that is invariant (or at least quasi-invariant) with respect to the group of finitary Nielsen transformations defined over infinite alphabet $\{x_1,x_2,\dots \}$.

Additionally to the randomness of groups, one can associate with each particular group a random family of Schreier graphs, like the family ${\Gamma }_{\xi }$, $\xi \in \partial T$ for a group $G\le \mathrm{Aut}\left(T\right)$ using the uniform Bernoulli measure on the boundary (other choices for $\mu$ are also possible, especially if G is generated by automorphisms of polynomial activity [26,144,145]). Putting all this together, it leads to study of random graphs associated with random groups (or equivalently, of random invariant subgroups in random groups).

Finally, even if we fix a group, say ${\mathcal{G}}_{\omega }$, $\omega \in \Omega$ and a Schreier graph ${\Gamma }_{\omega ,\xi }$, $\xi \in \partial T$, study of spectral properties of this graph is related to the study of iterations $F_{{\omega }_{n-1}}\circ \dots \circ F_{{\omega }_1}\circ F_{{\omega }_0}$ of maps given by (44) as was mentioned above.

Recall a classical construction of skew product in dynamical systems. Given two spaces $(X,\mu ),(Y,\nu )$, the measure $\nu$ preserving transformation $S:Y\to Y$, and for any $y\in Y$ the measure $\mu$ preserving transformation $T_y:X\to X$, under the assumption that the map $X\times Y\to X$, $(x,y)\mapsto T_{y}x$ is measurable, one can consider the map $Q:X\times Y\to X\times Y$, $Q(x,y)=(T_{y}x,Sy)$, which preserves the measure $\mu \times \nu$. Natural conditions imply that Q is ergodic if S and $T_y$, $y\in Y$ are ergodic. If for $k=1,2,\dots$, we put

$$T_y^{\left(k\right)}=T_{S^{k}y}\circ T_{S^{k-1}y}\circ \dots \circ T_{Sy}\circ T_y,$$

then the random ergodic theorem of Halmos–Kakutani [146,147] states that for $f\in L^1(X,\mu )$, $\nu$ almost surely the averages $\frac{1}{n}{\sum }_{k=0}^{n-1}f\left(T_y^{\left(k\right)}x\right)$ converge $\mu$ almost surely to some function $f_y^{\ast }\left(x\right)\in L^1(X,\mu )$. In the simplest case when $Y=\{1,\dots ,m\}$ and $\nu$ is given by a probability vector $(p_1,\dots ,p_m)$, $p_i>0$, $i=1,\dots ,m$, ${\sum }_{i=1}^m{p}_i=1$, we have m transformations $T_1,\dots ,T_m$ of X. The semigroup generated by them typically is a free semigroup and if $T_1,\dots ,T_m$ are invertible in a typical case, the group $〈T_1,\dots ,T_m〉$ is a free group of rank m.

The question of whether the pointwise ergodic theorem of Birkhoff holds for actions of a free group was raised by V. Arnold and A. Krylov [148] and answered affirmatively by the first author in [149]. A similar theorem is proven for the action of a free semigroup [150]. The proofs are based on the use of the skew product when S is the Bernoulli shift on $\mathrm{\Lambda }={\{1,2,\dots ,m\}}^{\mathbb{N}}$ and $\nu$ is a uniform Bernoulli measure on $\mathrm{\Lambda }$. In fact these ergodic theorems hold for stationary measures.

By a different method, a similar result for the free group actions was obtained by A. Nevo and E. Stein [151]. The method from [149,150] was used by A. Bufetov to get ergodic theorems for a large class of hyperbolic groups [152]. Ergodic theorem for action of non-commutative groups became popular [153,154], but the case of semigroup action is harder and not so many results are known, especially in the case of stationary measure.

In fact, the product measure $\mu \times \nu$ in the construction of the skew product is invariant if and only if the measure $\mu$ is $\nu$-stationary, which means the equality

$$\mu ={\int }_Y{\left(T_y\right)}_{\ast }\mu \nu \left(y\right).$$

In the case of $Y=\{1,\dots ,m\}$, $\nu =(p_1,\dots ,p_m)$, it means that

$$\mu =\sum _{i=1}^m{p}_i{\left(T_i\right)}_{\ast }\mu$$

(i.e., the $\nu$-average of images of $\mu$ under transformations $T_1,\dots ,T_m$ is equal to $\mu$). The skew product approach for non-commutative transformations leads to a not well-investigated notion of entropy [155,156]. It would be interesting to compare this approach with the approach of L. Bowen for the definition of entropy of free group action [157,158].

Going back to the transformations $F_0,F_1,F_2$ given by (44), we could try to apply the idea of skew product to them and investigate the random model. Random dynamical model in the context of holomorphic dynamics is successfully considered in [159] where stationary measures also play an important role. Each of these maps (as well as any map from the 2-parametric family $F_{(\alpha ,\beta )}$) is semiconjugate to the Chebyshev map and has families of horizontal and vertical hyperbolas similar to the case of the map F given by Figure 4. But when parameters $y,z,u$ (the coefficients of $b,c,d$) are not equal, even in the case of periodic sequence $\omega ={\left(012\right)}^{\infty }$ (in which case the group ${\mathcal{G}}_{\omega }$ is just our main hero$\mathcal{G}$), the iterations $T_{{\omega }_{n-1}}\circ \dots \circ T_{{\omega }_0}$ demonstrate chaotic dynamics presented by Figure 3a. Still, it is possible that more chaos could appear if additionally, $\omega$ is chaotic itself. Study of these systems and other topics discussed above is challenging and promising.

The notion of amenable group was introduced by J. von Neumann [160] for discrete groups and by N. Bogolyubov [161] for general topological groups. The concept of amenability entered many areas of mathematics [85,162,163,164,165,166,167]. Groups of intermediate growth and topological full groups remarkably extended the knowledge about the class $AG$ of amenable groups [15,16,137]. There are many characterizations of amenability: via existence of left invariant mean (LIM), existence of Fölner sets, Kesten’s probability criterion, hyperfiniteness [82], co-growth [168], etc.

From dynamical point of view, an important approach is due to Bogolyubov [161]; if a topological group G with left invariant mean acts continuously on a compact set X, then there is a G-invariant probability measure $\mu$ on X (this is a far reaching generalization of the famous Krylov-Bogolyubov theorem). In fact, such property characterizes amenability.

Amenability was mentioned in this article several times. We are going to conclude with open questions related to the considered maps $F,G$ and the conjugates $F_{(\alpha ,\beta )}$ of F. Even though invariant measures seem not to play an important role in the study of dynamical properties of multi-dimensional rational maps (where the harmonic measure or measures of maximal entropy like the Mané-Lyubich measure dominate), we could be interested in existence of invariant or stationary measures supported on invariant subsets of maps coming from Schur complements, as it was discussed above. This could include the whole Schur semigroup $S_d^{\ast }$ defined in Section 9, its subsemigroups, or semigroups involving some relatives of these maps (like the map H given by (4)). The concrete questions are:

Problem 8.

1. 

Is the semigroup $〈F,H〉$ amenable from the left or right?

2. 

Is there a probability measure on the cross $\mathcal{K}$, shown by Figure 5a, invariant with respect to the above semigroup?

By the last part of Theorem 4, we know that each horizontal slice of the cross $\mathcal{K}$ possesses a probability measure that is the density of states for the corresponding Markov operator. Integrating it along the vertical direction we get a measure $\nu$ on $\mathcal{K}$ which is somehow related to both maps F and G. Is it related to the semigroup $〈F,G〉$? $〈F,G〉$ is the simplest example of the Schur type semigroup. One can consider other semigroups of interest, for instance, $〈F_0,F_1,F_2〉$ or even semigroup generated by the maps $F_{(\alpha ,\beta )}$ for $\alpha ,\beta \in \mathbb{R}$, and look for invariant or stationary measures.

The example of semigroup $〈F,G〉$ is interesting because of the relations $H\circ F=G$, $H\circ G=F$. By J. Ritt’s result [169], it is known that in the case of the relation of the type $A\circ B=C\circ D$ for maps $A,B,C,D$ given by polynomials in one variable, all its solutions can be described explicitly. In the paper [170], it is proved that for polynomials P and Q, if there exists a point $z_0$ in the complex Riemann sphere $\overline{\mathbb{C}}$ such that the intersection of the forward orbits of $z_0$ with respect to P and Q is an infinite set, then there are natural numbers $n,m$ such that $P^n=Q^m$. The result of C. Cabrera and P. Makienko [171] generalizes this to the rational maps and includes in the statement the amenability properties of the semigroup $〈P,Q〉$.

In the case of maps $F,G$, we know that the semigroup $〈F,G〉$ is rationally semiconjugate to the commutative (and hence amenable) semigroup $\mathbb{N}\times \mathbb{N}$. Whether $〈F,G〉$ is amenable itself is an open question included in the Problem 8.

A very interesting question is the question about the dynamical properties of maps $F_{(\alpha ,\beta ,\gamma ,\delta )}$ given by (45). They are conjugate to the maps of the form

$$F_{(\alpha ,\beta ,\gamma )}:\left(\begin{array}{c}x\\ v\end{array}\right)\mapsto \left(\begin{array}{c}{\displaystyle \frac{\alpha x^2}{{\gamma }^2-v^2}}\\ v+{\displaystyle \frac{(v+\beta )x^2}{{\gamma }^2-v^2}}\end{array}\right)$$

(46)

via

$$S_{(\gamma ,\delta )}:\left(\begin{array}{c}x\\ v\end{array}\right)\mapsto \left(\begin{array}{c}-x\\ -v-{\displaystyle \frac{(\gamma +\delta )}{2}}\end{array}\right),$$

and further simplification seems to be impossible. At the same time, maps $F_{(\alpha ,\beta )}$ are conjugated to F by

$$R_{(\alpha ,\beta )}:\left(\begin{array}{c}x\\ v\end{array}\right)\mapsto \left(\begin{array}{c}-{\displaystyle \frac{2}{\alpha }}x\\ -{\displaystyle \frac{2}{\alpha }}v-{\displaystyle \frac{2}{\alpha }}\beta \end{array}\right).$$

The dynamical picture for those that are outside the 2-parametric family $F_{(\alpha ,\beta )}$ is presented by Figure 16 and is quite different of those dynamical pictures presented by Figure 3.

It is not clear at the moment if the maps presented in (46) describe the joint spectrum of a pencil of operators associated with fractal groups. But the family (46) itself could have interest for multi-dimensional dynamics and deserves to be carefully investigated, including semigroups generated by $F,H,R_{(\alpha ,\beta )},S_{(\gamma ,\delta )}$ in various combinations of the choice of generating set.