Post-critically finite self-similar groups

Post-critically finite self-similar groups

We describe in terms of automata theory the automatic actions with post-critically finite limit space. We prove that these actions are precisely the actions by bounded automata and that any self-similar action by bounded automata is contracting.

Gespeichert in:
Bibliographische Detailangaben
Datum:2003
Hauptverfasser: Bondarenko, E., Nekrashevych, V.
Format: Artikel
Sprache:English
Veröffentlicht: Інститут прикладної математики і механіки НАН України 2003
Schriftenreihe:Algebra and Discrete Mathematics
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/155721
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Post-critically finite self-similar groups / E. Bondarenko, V. Nekrashevych // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 4. — С. 21–32. — Бібліогр.: 19 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-155721
record_format dspace
spelling irk-123456789-1557212019-06-18T01:28:32Z Post-critically finite self-similar groups Bondarenko, E. Nekrashevych, V. We describe in terms of automata theory the automatic actions with post-critically finite limit space. We prove that these actions are precisely the actions by bounded automata and that any self-similar action by bounded automata is contracting. 2003 Article Post-critically finite self-similar groups / E. Bondarenko, V. Nekrashevych // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 4. — С. 21–32. — Бібліогр.: 19 назв. — англ. 1726-3255 http://dspace.nbuv.gov.ua/handle/123456789/155721 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language English
description We describe in terms of automata theory the automatic actions with post-critically finite limit space. We prove that these actions are precisely the actions by bounded automata and that any self-similar action by bounded automata is contracting.
format Article
author Bondarenko, E.
Nekrashevych, V.
spellingShingle Bondarenko, E.
Nekrashevych, V.
Post-critically finite self-similar groups
Algebra and Discrete Mathematics
author_facet Bondarenko, E.
Nekrashevych, V.
author_sort Bondarenko, E.
title Post-critically finite self-similar groups
title_short Post-critically finite self-similar groups
title_full Post-critically finite self-similar groups
title_fullStr Post-critically finite self-similar groups
title_full_unstemmed Post-critically finite self-similar groups
title_sort post-critically finite self-similar groups
publisher Інститут прикладної математики і механіки НАН України
publishDate 2003
url http://dspace.nbuv.gov.ua/handle/123456789/155721
citation_txt Post-critically finite self-similar groups / E. Bondarenko, V. Nekrashevych // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 4. — С. 21–32. — Бібліогр.: 19 назв. — англ.
series Algebra and Discrete Mathematics
work_keys_str_mv AT bondarenkoe postcriticallyfiniteselfsimilargroups
AT nekrashevychv postcriticallyfiniteselfsimilargroups
first_indexed 2025-07-14T07:56:52Z
last_indexed 2025-07-14T07:56:52Z
_version_ 1837608272188669952
fulltext Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 4. (2003). pp. 21 – 32 c© Journal “Algebra and Discrete Mathematics” Post-critically finite self-similar groups E. Bondarenko, V. Nekrashevych Communicated by V. V. Kirichenko Dedicated to R. I. Grigorchuk on the occasion of his 50th birthday Abstract. We describe in terms of automata theory the auto- matic actions with post-critically finite limit space. We prove that these actions are precisely the actions by bounded automata and that any self-similar action by bounded automata is contracting. 1. Introduction The aim of this paper is to show a connection between two notions, which have appeared in rather different fields of mathematics. One is the notion of a post-critically finite self-similar set (other related terms are: “nested fractal” or “finitely ramified fractal”). It appeared during the study of harmonic functions and Brownian motion on fractals. The class of post- critically finite fractals is a convenient setup for such studies. See the papers [1, 10, 3, 17] for the definition of a post-critically finite self-similar sets and for applications of this notion to harmonic analysis on fractals. The second notion appeared during the study of groups generated by finite automata (or, equivalently, groups acting on rooted trees). Many interesting examples of such groups where found (like the Grigorchuk group [7], groups defined by Aleshin [13], Sushchansky [18], Gupta-Sidki groups [14] and many others), and these particular examples where gen- eralized to different classes of groups acting on rooted trees: branch groups [4], self-similar (state closed) groups [15, 5], GGS-groups [2], AT groups [8, 9], spinal groups [12]. The second author acknowledges the support of Swiss National Science Foundation and Alexander von Huboldt Foundation Jo u rn al A lg eb ra D is cr et e M at h .22 Post-critically finite self-similar groups S. Sidki has defined in his work [16] a series of subgroups of the group of finite automata, using the notions of activity growth and circuit struc- ture. In particular, he has defined the notion of a bounded automaton. The set of all automorphisms of the regular rooted tree, which are defined by bounded automata is a group. It is interesting that most of the known interesting examples of groups acting on rooted trees (in particular, all the above mentioned examples) are subgroups of the group of bounded automata. Also every finitely automatic GGS-group, AT-group or spinal group is a subgroup of the group of bounded automata. We prove in our paper that a self-similar (state closed) group is a subgroup of the group of all bounded automata if and only if its limit space is a post-critically finite self-similar space. The limit space of a self-similar group was defined in [11] (see also [15]). This establishes the mentioned above connection between the harmonic analysis on fractals and group theory. The structure of the paper is the following. Section “Self-similar groups” is a review of the basic definitions of the theory of self-similar groups of automata. We define the notions of self-similar groups, au- tomata, Moore diagrams, contracting groups, nucleus of a contracting group and establish notations. Third section “Limit spaces” gives the definition and the basic prop- erties of the limit space of a contracting self-similar group as a quotient of the space of infinite sequences. We also discuss the notion of tiles of a limit space (the images of the cylindric sets of the space of sequences). The main results of the section “Post-critically finite limit space” are Corollary 4.2, giving a criterion when the limit space of a self-similar group action is post-critically finite and Proposition 4.3, stating that a post-critically finite limit space is 1-dimensional. The last section “Automata with bounded cyclic structure” is the main part of the article. We prove Theorem 5.3, which says that every self- similar subgroup of the group B of bounded automata is contracting and that a contracting group has a post-critically finite limit space if and only if it is a subgroup of B. 2. Self-similar groups We review in this section the basic definitions and theorems concerning self-similar groups. For a more detailed account, see [15]. Let X be a finite set, which will be called alphabet. By X∗ we denote the set of all finite words x1x2 . . . xn over the alphabet X, including the empty word ∅. Jo u rn al A lg eb ra D is cr et e M at h .E. Bondarenko, V. Nekrashevych 23 Definition 2.1. A faithful action of a group G on the set X∗ is self- similar (or state closed) if for every g ∈ G and for every x ∈ X there exist h ∈ G and y ∈ X such that g(xw) = yh(w) for all w ∈ X∗. We will write formally g · x = y · h, (1) if for every w ∈ X∗ we have g(xw) = yh(w). If one identifies every letter x ∈ X with the map w 7→ xw : X∗ −→ X∗, then equation (1) will become a correct equality of two transformations. The notion of a self-similar action is closely related with the notion of an automaton. Definition 2.2. An automaton A over the alphabet X is a tuple 〈Q, π, λ〉, where Q is a set (the set of internal states of the automaton), and π : Q × X −→ Q and λ : Q × X −→ Q are maps (the transition and the output functions, respectively). An automaton is finite if its set of states Q is finite. A subset Q′ ⊂ Q is called sub-automaton if for all q ∈ Q′ and x ∈ X we have π(q, x) ∈ Q′. If Q′ is a sub-automaton, then we identify it with the automaton 〈Q′, π|Q′×X , λ|Q′×X〉. For every state q ∈ Q and x ∈ X we also write formally q · x = y · p, (2) where y = λ(q, x) and p = π(q, x). We will also often use in our paper another notation for the functions π and λ: π(q, x) = q|x, λ(q, x) = q(x). The transition and output functions are naturally extended to func- tions π : Q × X∗ −→ Q and λ : Q × X∗ −→ X∗ by the formulae: π(q, xv) = π (π(q, x), v) , λ(q, xv) = λ(q, x)λ (π(q, x), v) , or, in the other notation: q|xv = q|x|v, q(xv) = q(x)q|x(v). We also put q|∅ = q, q(∅) = ∅. Jo u rn al A lg eb ra D is cr et e M at h .24 Post-critically finite self-similar groups Hence we get for every state q a map v 7→ q(v), defining the action of the state q on the words. It is easy to see that we have q1q2|v = q1|q2(v)g2|v, q(vw) = q(v)q|v(w) for all q, q1, q2 ∈ Q and v, w ∈ X∗. Here q1q2 is the product of transfor- mations q1 and q2, i.e., q1q2(w) = q1 (q2(w)). The above definitions imply the following description of self-similar actions in terms of automata theory. Proposition 2.1. A faithful action of a group G on the set X∗ is self- similar if and only if there exists an automaton with the set of states G such that the action of the states of the automaton on X∗ coincides with the original action of G. The automaton from Proposition 2.1 is called complete automaton of the action. It is convenient to represent automata by their Moore diagrams. If A = 〈Q, π, λ〉 is an automaton, then its Moore diagram is a directed graph with the set of vertices Q in which we have for every pair x ∈ X, q ∈ Q an arrow from q ∈ Q into π(q, x) labelled by the pair of letters (x; λ(q, x)). Let q ∈ Q be a state and let v ∈ X∗ be a word. In order to find the image q(v) of the word v under the action of the state q one needs to find a path in the Moore diagram, which starts at the state q with the consecu- tive labels of the form (x1; y1), (x2; y2), . . . (xn; yn), where x1x2 . . . xn = v, then q(v) = y1y2 . . . yn. Definition 2.3. We say that an automaton A = 〈Q, π, λ〉 has finite nucleus if there exists its finite sub-automaton N ⊂ Q such that for every q ∈ A there exists n ∈ N such that q|v ∈ N for all v ∈ X∗ such that |v| ≥ n. A self-similar action of a group G on X∗ is said to be contracting if its full automaton has a finite nucleus. In general, if A is an automaton, then its nucleus is the set N = ⋃ q∈Q ⋂ n∈N {q|v : v ∈ X∗, |v| ≥ n} . For more on contracting actions, see the papers [15, 6]. 3. Limit spaces One of important properties of contracting actions is there strong relation to Dynamical Systems, exhibited in the following notion of limit space. Jo u rn al A lg eb ra D is cr et e M at h .E. Bondarenko, V. Nekrashevych 25 Denote by X−ω the set of all infinite to the left sequences of the form . . . x2x1, where xi are letters of the alphabet X. We introduce on the set X−ω the topology of the infinite power of the discrete set X. Then the space X−ω is a compact totally disconnected metrizable topological space without isolated points. Thus it is homeomorphic to the Cantor space. Definition 3.1. Let (G, X∗) be a contracting group action over the al- phabet X. We say that two points . . . x2x1, . . . y2y1 ∈ X−ω are asymptot- ically equivalent (with respect to the action of the group G) if there exists a bounded sequence {gk}k≥1 of group elements such that for every k ∈ N we have gk(xk . . . x1) = yk . . . y1. Here a sequence {gk}k≥1 is said to be bounded if the set of its values is finite. It is easy to see that the defined relation is an equivalence. The quotient of the space X−ω by the asymptotic equivalence relation is called the limit space of the action and is denoted JG. We have the following properties of the limit space (see [11]). Theorem 3.1. The asymptotic equivalence relation is closed and has finite equivalence classes. The limit space JG is metrizable and finite- dimensional. The shift σ : . . . x2x1 7→ . . . x3x2 induces a continuous surjective map s : JG −→ JG. We will also use the following description of the asymptotic equiva- lence relation (for the proof see [11]). Proposition 3.2. Two sequences . . . x2x1, . . . ay2y1 ∈ X−ω are asymp- totically equivalent if and only if there exists a sequence g1, g2, . . . of el- ements of the nucleus such that gi · xi = yi · gi−1, i.e., if there exists a left-infinite path . . . e2, e1 in the Moore diagram of the nucleus such that the edge ei is labelled by (xi; yi). A left-infinite path in a directed graph is a sequence . . . e2, e1 of its arrows such that beginning of ei is equal to the end of ei+1. The end of the last edge e1 is called the end of the left-infinite path. The dynamical system (JG, s) has a special Markov partition coming from the its presentation as a shift-invariant quotient. Definition 3.2. For every finite word v ∈ X∗ the respective tile Tv is the image of the cylindrical set X−ωv in the limit space JG. We say that Tv is a tile of the level number |v|. Jo u rn al A lg eb ra D is cr et e M at h .26 Post-critically finite self-similar groups We have the following obvious properties of the tiles. 1. Every tile Tv is a compact set. 2. s (Tvx) = Tv. 3. Tv = ∪x∈XTxv. In particular, the image of a tile Tv of nth level under the shift map s is a union of d tiles Tu of the nth level, i.e., that the tiles of one level for a Markov partition of the dynamical system (JG, T). Actually, a usual definition of a Markov partition requires that two tiles do not overlap, i.e., that they do not have common interior points. We have the following criterion (for a proof see also [11]). We say that a self-similar action satisfies the open set condition if for every g ∈ G there exists v ∈ X∗ such that g|v = 1. Theorem 3.3. If a contracting action of a group G on X∗ satisfies the open set condition then for every n ≥ 0 and for every v ∈ Xn the boundary of the tile Tv is equal to the set ∂Tv = ⋃ u∈Xn,u 6=v Tu ∩ Tv, and the tiles of one level have disjoint interiors. If the action does not satisfy the open set condition, then there exists n ∈ N and a tile of nth level, which is covered by other tiles of nth level. 4. Post-critically finite limit spaces Following [1], we adopt the following definition. Definition 4.1. We say that a contracting action (G, X∗), has a post- critically finite (p.c.f.) limit space if intersection of every two different tiles of one level is finite. We obtain directly from Theorem 3.3 that a contracting action has a p.c.f. limit space if and only if it satisfies the open set condition and the boundary of every tile is finite. The following is an easy corollary of Theorem 3.3 and Proposition 3.2. Proposition 4.1. The image of a sequence . . . xn+1xn . . . x1 ∈ X−ω be- longs to the boundary of the tile Txn...x1 if and only if there exists a se- quence {gk} of elements of the nucleus such that gk+1 ·xk+1 = xk · gk and gn(xn . . . x1) 6= xn . . . x1. Jo u rn al A lg eb ra D is cr et e M at h .E. Bondarenko, V. Nekrashevych 27 This gives us an alternative way of defining p.c.f. limit spaces. Corollary 4.2. A contracting action (G, X∗) has a p.c.f. limit space if and only if there exists only a finite number of left-infinite paths in the Moore diagram of its nucleus which end in a non-trivial state. Proof. We say that a sequence . . . x2x1 ∈ X−ω is read on a left-infinite path . . . e2e1, if the label of the edge ei is (xi; yi) for some yi ∈ X. If the path . . . e2e1 passes through the states . . . g2g1g0 (here gi is the beginning and gi−1 is the end of the edge ei), then the state gn−1 is uniquely defined by gn and xn, since gn−1 = gn|xn . Consequently, any given sequence . . . x2x1 is read not more than on |N | left-infinite paths of the nucleus N . In particular, every asymptotic equivalence class on X−ω has not more than |N | elements. For every non-trivial state g ∈ N denote by Bg be the set of sequences, which are read on the left-infinite paths of the nucleus, which end in g. Suppose that there is infinitely many left-infinite paths in the nucleus ending in a nontrivial state. Then there exists a state g ∈ N \ {1} for which the set Bg is infinite. Since the state g is non-trivial, there exists a word v ∈ X∗ such that g(v) 6= v. Then for every . . . x2x1 ∈ Bg, there exists a sequence . . . y2y1 such that . . . x2x1v is asymptotically equivalent to . . . y2y1g(v). Hence, every point of JG represented by a sequence from Bgv belongs both to Tv and to Tg(v). This show that the intersection Tv ∩ Tg(v) is infinite, since the asymptotic equivalence classes are finite. On the other hand, Proposition 4.1 shows, that if the sequence . . . x2x1v, represents a point of the intersection Tv∩Tu for u ∈ X |v|, u 6= v, then the sequence . . . x2x1 is read on some path of the nucleus, which ends in a non-trivial state. Therefore, if the intersection Tv ∩ Tu is infinite, then the set of left-infinite paths in the nucleus is infinite. Proposition 4.3. If the limit space of a contracting action is post-critically finite, then its topological dimension is ≤ 1. Proof. We have to prove that every point ζ ∈ JG has a basis of neighbor- hoods with 0-dimensional boundaries. Let Tn(ζ) be the union of the tiles of nth level, containing ζ. It is easy to see that {Tn(ζ) : n ∈ N} is a base of neighborhoods of ζ. 5. Automata with bounded cyclic structure We take Corollary 4.2 as a justification of the following definition. Jo u rn al A lg eb ra D is cr et e M at h .28 Post-critically finite self-similar groups Definition 5.1. A self-similar contracting group is said to be post-criti- cally finite (p.c.f. for short) if there exists only a finite number of inverse paths in the nucleus ending at a non-trivial state. A more precise description of the structure of the nucleus of a p.c.f. group is given in the next proposition. Recall, that an automatic transformation q of X∗ is said to be finitary (see [19]) if there exists n ∈ N such that q|v = 1 for all v ∈ Xn (then q(x1 . . . xm) = q(x1 . . . xn)xn+1 . . . xm). The minimal number n is called depth of q. The set of all finitary automatic transformations of X∗ is a locally finite group. If G is a finite subgroup of the group of finitary transforma- tions, then the depth of G is the greatest depth of its elements. If we have a subset A of the vertex set of a graph Γ, then we consider it to be a subgraph of Γ, taking all the edges, which start and end at the vertices of A. We say that a directed graph is a simple cycle if its vertices g1, g2, . . . , gn and edges e1, e2, . . . , en can be indexed so that ei starts at gi and ends at gi+1 (here all gi and all ei are pairwise different and gn+1 = g1). Proposition 5.1. Let N be the nucleus of a p.c.f. group, and let N0 be the subgraph of finitary elements of N and N1 = N \ N0. Then N1 is a disjoint union of simple cycles. Proof. The set N0 is obviously a sub-automaton, i.e., for every g ∈ N0 and x ∈ X we have g|x ∈ N0. It follows then from the definition of a nucleus that every vertex of the graph N1 has an incoming arrow. This means that every vertex of the graph N1 is an end of a left-infinite path. On the other hand, there exists for every g ∈ N1 at least one x ∈ X such that g|x ∈ N1, since all elements of N1 are not finitary. Thus, every vertex of N1 has an outgoing arrow and is a beginning of a right-infinite path. Let g be an arbitrary vertex of the graph N1. We have a left-infinite path γ− ending in g. Suppose that we have a (pre-)periodic right-infinite path γ+ starting at g, i.e., a path of the form γ+ = qppp . . . = qpω, were q is a finite path, p is a finite simple cycle and the set of edges of the paths p and q are disjoint. Note that there always exists a (pre-)periodic path beginning at g. If q is not empty, then we get an infinite set of different left-infinite paths in the graph N1: {γ−qpn}n∈N, what contradicts to the post-critical finiteness of the action. Hence the pre-period q is empty. In particular, every element of N1 belongs to a finite cycle, i.e., for every g ∈ N1 there exists v ∈ X∗ such that g|v = g. Jo u rn al A lg eb ra D is cr et e M at h .E. Bondarenko, V. Nekrashevych 29 Suppose now that there exist two different letters x, y ∈ X such that g|x and g|y belong to N1. The element g|x belongs to a finite cycle px in N1. The cycle px must contain the element g, otherwise we get a strictly pre-periodic path starting at g. Similarly, there exists a cycle py , which contains g and g|y. The cycles px and py are different and intersect in the vertex g. Hence we get an infinite set of left-infinite paths in N1 of the form . . . p3p2p1, where pi are either px or py (seen as paths starting at g) in an arbitrary way. Hence, for every g ∈ N1 there exists only one letter x ∈ X such that g|x ∈ N1. This (together with the condition that every vertex of N1 has an incoming edge) implies that N1 is a disjoint union of simple cycles. The following notion was defined and studied by Said Sidki in [16]. Definition 5.2. We say that an automatic transformation q is bounded if the sequence θ(k, q) is bounded, where θ(k, q) is the number of words v ∈ Xk such that q|v acts non-trivially on the first level X1 of the tree X∗. The following proposition is proved in [16] (Corollary 14). Proposition 5.2. An automatic transformation is bounded if and only if it is defined by a finite automaton in which every two non-trivial cycles are disjoint and not connected by a directed path. Here a cycle is trivial if its only vertex is the trivial state. In particu- lar, every finitary transformation is bounded, since it has no non-trivial cycles. Theorem 5.3. The set B of all bounded automorphisms of the tree X∗ is a group. A finitely generated self-similar automorphism group G of the tree X∗ has a p.c.f. limit space if and only if it is a subgroup of B. In particular, every finitely generated self-similar subgroup of B is contracting. Proof. The fact that B is a group, is proved in [16]. We have also proved that the nucleus of every p.c.f. group G is a subset of B. This implies that G is a subgroup of B. In the other direction, suppose that we have a self-similar finitely generated subgroup G ≤ B. Then G is generated by a finite automaton S whose all non-trivial cycles are disjoint. Let S0 be the subautomaton of all finitary tranformations, and let S2 = S \ S0. Then all non-trivial cycles belong to S2. Let S1 be the union of all these cycles. Let g ∈ S1 and v ∈ X∗ be arbitrary. Then either g|v belongs to the same cycle as g, or g|v /∈ S1, since no two different cycles of S1 can be Jo u rn al A lg eb ra D is cr et e M at h .30 Post-critically finite self-similar groups connected by a directed path. If g|v /∈ S1, then all states g|vu of g|v do not belong to S1. But this is possible only when g|v ∈ S0. Therefore, there exists m ∈ N such that for every g ∈ S and every v ∈ Xm either g|v ∈ S0, or g|v ∈ S1. Then the group G1 = 〈G|Xm〉 is also self-similar and is generated by a subset of the set S0∪S1. The group G is contracting if and only if G1 is contracting. Their nuclei will coincide. Therefore, if we prove our theorem for G1, then it will follow for G, so we assume that S2 = S1. Let n1 be the least common multiple of the lengths of cycles in S1. Then for every u ∈ Xn1 and s ∈ S1 we have either s|u ∈ S0 or s|u = s. Moreover, it follows from the conditions of the theorem that the word u ∈ Xn1 such that s|u = s is unique for every s ∈ S1. Let N1 be the set of all elements h ∈ G \ 1 such that there exists one word u(h) ∈ Xn1 such that h|u(h) = h and for all the other words u ∈ Xn1 the restriction h|u belongs to 〈S0〉. It is easy to see that the set N1 is finite (every its element h is uniquely defined by the permutation it induces on Xn1 and its restrictions in the words u ∈ Xn1 , note also that the group 〈S0〉 is finite). Let us denote by l1(g) the minimal number of elements of S1 ∪ S−1 1 in a decomposition of g into a product of elements of S ∪ S−1. Let us prove that there exists for every g ∈ G a number k such that for every v ∈ Xn1k the restriction g|v belongs to N1∪{S0}. We will prove this by induction on l1(g). If l1(g) = 1, then g = h1sh2, where h1, h2 ∈ 〈S0〉 and s ∈ S1. The elements h1, h2 are finitary, thus there exists k such that for every v ∈ Xn1k the restriction hi|v is trivial. Then we have h1sh2|v = s|h2(v), thus g|v is either equal to s ∈ N1 or belongs to S0 ∪ S−1 0 . Thus the claim is proved for the case l1(g) = 1. Suppose that the claim is proved for all elements g ∈ G such that l1(g) < m. Let g = s1s2 . . . sk, where si ∈ S ∪ S−1. For every u ∈ Xn1 the restriction si|u is equal either to si or belongs to S0. Consequently, either g|u = g for one u and g|u ∈ 〈S0〉 for all the other u ∈ Xn1 , or l1(g|u) < l1(g) for every u ∈ Xn1 . In the first case we have g ∈ N1 and in the second we apply the induction hypothesis, and the claim is proved. Consequently, the group G is contracting with the nucleus equal to a subset of the set {g|v : g ∈ N1, v ∈ X∗, |v| < n1}. Note that any restriction g|v of an element of N1 either belongs to N1 or is finitary. Let us prove that the limit space of the group G is p.c.f.. Suppose that we have a left-infinite path in the nucleus of the group. Let . . . h3, h2, h1 be the elements of the nucleus N it passes through and let the letters Jo u rn al A lg eb ra D is cr et e M at h .E. Bondarenko, V. Nekrashevych 31 . . . , x3, x2, x1 be the letters labeling its edges. In other words, we have hn = hn+1|xn for every n ≥ 1. The number of possibilities for hn is finite, thus it follows from the arguments above that every element hi belongs to N1∪〈S0〉. The elements of 〈S0〉 can belong only to the ending of the sequence hi of the length not greater than the depth of the group 〈S0〉. The rest of the sequences hi and xi is periodic with period n1. Hence, there exists only a finite number of possibilities for such a sequence, and the limit space of the group is p.c.f. Corollary 5.4. The word problem is solvable in polynomial time for every finitely generated subgroup of B. Proof. The word problem in every finitely generated contracting group is solvable in polynomial time (see [6]). References [1] Jun Kigami. Analysis on fractals, volume 143 of Cambridge Tracts in Mathemat- ics. Cambridge University Press, 2001. [2] G. Baumslag. Topics in combinatorial group theory. Lectures in Mathematics, ETH Zürich. Birkhäuser Verlag, Basel, 1993. [3] Tom Lindstrøm. Brownian motion on nested fractals. Mem. Am. Math. Soc., 420:128 p., 1990. [4] Rostislav I. Grigorchuk. Just infinite branch groups. In Aner Shalev, Marcus P. F. du Sautoy, and Dan Segal, editors, New horizons in pro-p groups, volume 184 of Progress in Mathematics, pages 121–179. Birkhäuser Verlag, Basel, etc., 2000. [5] Said N. Sidki. Regular Trees and their Automorphisms, volume 56 of Monografias de Matematica. IMPA, Rio de Janeiro, 1998. [6] Volodymyr V. Nekrashevych. Virtual endomorphisms of groups. Algebra and Discrete Mathematics, 1(1):96–136, 2002. [7] Rostislav I. Grigorchuk. On Burnside’s problem on periodic groups. Funtional Anal. Appl., 14(1):41–43, 1980. [8] Yurĭı I. Merzlyakov. Infinite finitely generated periodic groups. Dokl. Akad. Nauk SSSR, 268(4):803–805, 1983. [9] A. V. Rozhkov. Finiteness conditions in automorphism groups of trees. PhD thesis, Cheliabinsk, 1996. Habilitation thesis. [10] Jun Kigami. Laplacians on self-similar sets — analysis on fractals. Transl., Ser. 2, Am. Math. Soc. 161, 75-93 (1994); translation from Sugaku 44, No.1, 13-28 (1992), 1992. [11] Volodymyr V. Nekrashevych. Limit spaces of self-similar group actions. preprint, Geneva University, available at http://www.unige.ch/math/biblio/preprint/2002/limit.ps, 2002. Jo u rn al A lg eb ra D is cr et e M at h .32 Post-critically finite self-similar groups [12] Laurent Bartholdi, Rostislav I. Grigorchuk, and Zoran Šuniḱ. Branch groups. preprint. [13] S. V. Aleshin. Finite automata and the Burnside problem for periodic groups. Mat. Zametki, 11:319–328, 1972. (in Russian). [14] Narain D. Gupta and Said N. Sidki. On the Burnside problem for periodic groups. Math. Z., 182:385–388, 1983. [15] L. Bartholdi, R. Grigorchuk, and V. Nekrashevych. From fractal groups to fractal sets. In Peter Grabner and Wolfgang Woess, editors, Fractals in Graz 2001. Analysis – Dynamics – Geometry – Stochastics, pages 25–118. Birkhäuser Verlag. Basel. Boston. Berlin., 2003. [16] Said N. Sidki. Automorphisms of one-rooted trees: growth, circuit structure and acyclicity. J. of Mathematical Sciences (New York), 100(1):1925–1943, 2000. [17] C. Sabot. Existence and uniqueness of diffusions of finitely ramified self-similar fractals. Ann. Sci. Éc. Norm. Supér., IV. Sér., 30(5):605–673, 1997. [18] Vitalĭı I. Sushchansky. Periodic permutation p-groups and the unrestricted Burn- side problem. DAN SSSR., 247(3):557–562, 1979. (in Russian). [19] Rostislav I. Grigorchuk, Volodymyr V. Nekrashevich, and Vitalĭı I. Sushchanskii. Automata, dynamical systems and groups. Proceedings of the Steklov Institute of Mathematics, 231:128–203, 2000. Contact information V. Nekrashevych Kyiv Taras Shevchenko University Mechanics and Mathematics Faculty Algebra Department Volodymyrska, 60 Kyiv, Ukraine, 01033 E-Mail: nazaruk@ukrpack.net

Ähnliche Einträge