The group of all finite-state automorphisms of a regular rooted tree has a minimal generating set

Abstract

We find some sufficient conditions under which the permutational wreath product of two groups has a minimal (irredundant) generating set. In particular we prove that for a regular rooted tree the group of all automorphisms and the group of all finite-state automorphisms of such a tree satisfy these conditions. Thereby we solve the problem that was stated by B. Csákány and F. Gécseg in 1965.

1 Introduction

We consider the following problem

Problem 1

Do the group of all automorphisms and the group of all finite-state automorphisms of a regular rooted tree have any minimal generating set?

This problem was stated originally by Csákány and Gécseg [6] in terms of automata in 1965. They asked whether the semigroup of all automaton transformations, the semigroup of all finite automaton transformations, the group of all bijective automaton transformations, and the group of all finite bijective automaton transformations over a fixed finite alphabet with at least two elements have a minimal generating set?

The answer for semigroups is negative. This result was obtained independently by Aleshin [1] in 1970 and Dömösi [7] in 1972. The question about groups (i.e. Problem 1) was also formulated in papers of Dömösi. In particular, it appeared in [8, Problem  2.1] and [9, Problem 2.31]. Moreover this problem is mentioned in the papers [2, 16].

Among works related to this problem we mention the result of Andriy Oliynyk from [17]. Namely, it was proven that finite-state wreath product of transformation semigroups is not finitely generated and in some cases doesn’t have a minimal generating set. We also mention papers devoted to the study of generating sets in projective limits of wreath products of groups [3, 4, 14, 18].

We find some sufficient conditions under which the permutational wreath product of a finite group and an infinite group has a minimal generating set (Theorem 2). We also give a several examples of groups and classes of groups satisfying such conditions. In particular we prove that for a regular rooted tree the group of all automorphisms and the group of all finite-state automorphisms of such a tree satisfy these conditions (Theorems 7 and 9). Therefore we obtain the main theorem of the paper.

Theorem 1

The group of all automorphisms and the group of all finite-state automorphisms of a regular rooted tree have minimal generating sets.

Thus Problem 1 is solved positively.

Most results of this paper were announced without proofs in  [12, 13].

2 Minimal generating sets in permutational wreath products

We first recall the notion of the permutational wreath product.

Let (A, X) be a permutation group and let H be a group. Then the permutational wreath product $(A,X)\wr H$ is the semi-direct product $(A,X)\rightthreetimes H^X$, where (A, X) acts on the direct power $H^X$ by the respective permutations of the direct factors.

We will say that a permutation group (A, X) satisfies the condition PS if:

• 1. The group (A, X) is finite and transitive.

• 2. There are subsets $X_1,X_2$ of X and subgroups $A_1,A_2$ of A with the following properties:

  • $(A_1,X)$ and $(A_2,X)$ act transitively on $X_1$ and $X_2$ respectively and act trivially on $X\setminus X_1$ and $X\setminus X_2$ respectively.

  • $X_1$ and $X_2$ do not intersect.

  • $|X_1|\ge 2$, $|X_2|\ge 3$.

  • If $|X_1|= 2$ then there is $a\in A$ satisfying $a(X_1)\cap X_2\ne \emptyset$ and $a(X_1)\nsubseteq X_2$.

We say that a group G satisfies the L-condition, if G is decomposed into permutational wreath product $G= (A,X)\wr H$ and there are a normal subgroup $H_0$ of H and an integer $k>1$ with the following properties:

• 1. The permutation group (A, X) satisfies the condition PS,

• 2. The quotient $H/H_0$ has infinite minimal generating set,

• 3. $|H/H_0|\ge |H_0|$,

• 4. Either $H_0<H'$ or $H'\lneq H_0<H^kH'$, where $H'$ is the commutator subgroup of H and $H^k=\langle \{h^k , h\in H\}\rangle$,

• 5. If $H'\lneq H_0<H^kH'$ then there is a subset C of some minimal generating set of $H/H_0$ such that

  • (a) $|C|=|H/H_0|$,

  • (b) For every coset $c\in C$ there is h in the coset c such that $h^k=e$.

Note that condition 2 of the definition of the L-condition imply that H is infinite.

In this section we prove the following theorem.

Theorem 2

A group with the L-condition has a minimal generating set.

Proof

Proof of Theorem 2

At first we fix some notation.

Let $G= (A,X)\wr H$ and let $H_0$ be a normal subgroup of H. We assume that G,  (A, X), H, and $H_0$ satisfy the conditions of Theorem 2. Let $X=\{ {0}, {1},\ldots , {n}\}$, $X_1=\{ {0}, {1},\ldots , {l_1}\}$, and $X_2=\{ {l_2}, {l_2+1},\ldots , {n}\}$.

The symbol for the identity element is e and the symbol for the trivial group is E.

The group G is a semidirect product of its subgroups A and K, where K is the direct product of $n+1$ copies of H, i.e., $K=\underbrace{H\times \cdots \times H}_{n+1}$. We will also write whole subgroup K as $(\underbrace{H,\ldots ,H}_{n+1})$. The conjugation of $g=(g_0,\ldots ,g_{n})$ by an element of (A, X) is a corresponding permutation of coordinates of the tuple.

Without loss of generality, we will make the following assumptions:

If there exists $a\in A$ such that $a(X_1)\cap X_2\ne \emptyset$ and $a(X_1)\nsubseteq X_2$ then let $d_1\in A$ be such that $d_1( {0})\notin X_2$ and $d_1( {1})= {n}$.

Otherwise, if $a(X_1)\cap X_2\ne \emptyset$ implies that $a(X_1)\subseteq X_2$ for all $a\in A$ then $|X_1|\ge 3$ by the condition PS. In this case let $d_2\in A$ be such that $d_2(0)=n$, $d_2(1)=n-1$, and $d_2(2)=n-2$.

By the L-condition there is a minimal generating set $\bar{F}=\{\bar{f}_i\ |\ i \in {\mathop {\mathcal {I}}\nolimits }\}$ of $H/H_0$, where $\mathop {\mathcal {I}}\nolimits$ denotes a set of indices. Let $\psi : H\rightarrow H/H_0$ be the canonical epimorphism. For every $i\in \mathop {\mathcal {I}}\nolimits$ we fix some element $f_i\in H$ such that $\psi (f_i)=\bar{f_i}$. Denote

$$\begin{aligned} F=\{f_i \ | i\in \mathop {\mathcal {I}}\nolimits \}. \end{aligned}$$

Let $\mathop {\mathcal {I}}\nolimits _1$ and $\mathop {\mathcal {I}}\nolimits _2$ be subsets of $\mathop {\mathcal {I}}\nolimits$ with the following properties:

• $|\mathop {\mathcal {I}}\nolimits _2|=|\mathop {\mathcal {I}}\nolimits |.$

• $\mathop {\mathcal {I}}\nolimits _1=\mathop {\mathcal {I}}\nolimits \setminus \mathop {\mathcal {I}}\nolimits _2$.

Denote

$$\begin{aligned} F^{\mathop {\mathcal {I}}\nolimits _j}=\{f_i \ | i\in \mathop {\mathcal {I}}\nolimits _j\}\ \text {for} \ j=1,2. \end{aligned}$$

In the case of $H'\lneq H_0<H^kH'$ due to condition 5 of the L-condition we can assume that for every $i \in \mathop {\mathcal {I}}\nolimits _2$ the following equality holds: $f_i^k=e$. In the case of $H_0<H'$ we can assume that $\mathop {\mathcal {I}}\nolimits _2=\mathop {\mathcal {I}}\nolimits$.

Since $\bar{F}$ is an infinite set the set of the finite words over $\bar{F}$ has the same cardinality as $\bar{F}$. By the L-condition $|H/H_0|\ge |H_0|.$ It follows that

$$\begin{aligned} |\mathop {\mathcal {I}}\nolimits _2|=|\mathop {\mathcal {I}}\nolimits |=|H/H_0|\ge |H_0|. \end{aligned}$$

Therefore we can fix a surjection $\phi : \mathop {\mathcal {I}}\nolimits _2 \rightarrow H_0$. We also define the set of elements of G:

$$\begin{aligned} S_K=\{q_{i}=(f_i,e,\ldots ,e,\phi (i)) \ | \ i\in \mathop {\mathcal {I}}\nolimits _2\}\cup \{q_{i}=(f_i,e,\ldots ,e) \ | \ i\in \mathop {\mathcal {I}}\nolimits _1\}. \end{aligned}$$

Let us fix a minimal generating set of A: $S_A=\{s_1,s_2,\ldots ,s_r\}$. Let $S =S_K \cup S_A$ and $N=\langle S \rangle$. Note that $A=\langle S_A \rangle$ is contained in N.

Lemma 1

The set S is a minimal generating set of the group N.

Proof

Since G is the semidirect product $A\rightthreetimes K$ and $S_K\subset K$, any element s of $S_A$ cannot be written as an product of elements of $S\setminus \{s\}$ and their inverses.

Further, suppose, contrary to our claim, that the element $q_i$ for some $i\in \mathop {\mathcal {I}}\nolimits$ is a product of elements of $S\setminus \{q_{i}\}$ and their inverses. It is easy to check that this decomposition of $q_i$ can be transformed to the product of the form $q_i=(q_{i_1}^{\epsilon _1})^{a_{1}}\ldots (q_{i_m}^{\epsilon _m})^{a_{m}}$, where $i_1,\ldots , i_m \in \mathop {\mathcal {I}}\nolimits \setminus \{i\}$, $\epsilon _1,\ldots ,\epsilon _m\in \{-1,1\}$ and $a_1,\ldots ,a_m\in A$. Consider the 0-th coordinate of $q_i$. We have that $f_i$ is a product of elements of $F\setminus \{f_i\}$, their inverses and elements of $H_0$. Applying $\psi$ we conclude that $\bar{f}_i$ is a product of elements of $\bar{F}\setminus \{\bar{f}_i\}$ and their inverses. This contradicts the fact that $\bar{F}$ is a minimal generating set of the quotient $H/H_0$.$\square$

We next show that the set S is a generating set of G, i.e., we next show that $N=G$.

Lemma 2

For every $g\in \langle F\rangle$ the elements $u_{n-2}=(e,\ldots ,e,{g},e,g^{-1})$ and $u_{n-1}=(e,\ldots ,e,{g},g^{-1})$ are contained in N.

Proof

The element g can be decomposed into the product of elements of F and their inverses: $g=f_{i_1}^{\epsilon _1}\ldots f_{i_m}^{\epsilon _m}$, where $\epsilon _1,\ldots ,\epsilon _m\in \{-1,1\}$. For every $j\in X_1 \setminus \{0\}$ choose $b_j\in A_1$ such that $b_j( {0})= {j}$. Then

$$\begin{aligned} t_{j}=b_j^{-1}q_{i_1}^{\epsilon _1}\ldots q_{i_m}^{\epsilon _m}b_j (q_{i_1}^{\epsilon _1}\ldots q_{i_m}^{\epsilon _m})^{-1}=(g^{-1},e,\ldots ,e,g,e,\ldots ,e)\in N, \end{aligned}$$

where g is located on the j-th coordinate of the tuple.

We consider all possible cases depending on the group A. We will use here the elements $d_1$ and $d_2$ which were defined at the beginning of the proof of the theorem.

• 1. There is $a\in A$ such that $a(X_1)\cap X_2\ne \emptyset$ and $a(X_1)\nsubseteq X_2$. For every $m \in \{n-2,n-1\}$ choose $c_m\in A_2$ such that $c_m(n)=m$. Then $t_{1}^{d_1}(t_{1}^{d_1c_m})^{-1}=u_m\in N$ for $m=n-2, n-1$.

• 2. For all $a\in A$, the inequality $a(X_1)\cap X_2\ne \emptyset$ implies that $a(X_1)\subseteq X_2$. Then $|X_1|\ge 3$ and elements $u_{n-1}=t_1^{d_2}$ and $u_{n-2}=t_2^{d_2}$ are contained in N.

Lemma 3

The subgroup $(E,\ldots ,E,H')$ of K is contained in N.

Proof

Let $h_1,h_2\in H$. Then there exist $g_j\in \langle F\rangle$, $i_j \in \mathop {\mathcal {I}}\nolimits _2$ for $j=1,2$ such that $h_j=g_j\phi (i_j)$. By the construction, the set S contains elements $q_{i_j}=(f_{i_j},e,\ldots ,e,\phi (i_j))$ for $j=1,2$. Let $a\in A_1$ be such that $a(0)=1$. Then $q_{i_2}^a=(e,f_{i_2},e,\ldots ,e,\phi (i_2))\in N$. By Lemma 2 elements $t_1=(e,\ldots ,e , g_1^{-1} ,e,g_1)$ and $t_2=(e,\ldots ,e , g_2^{-1} ,g_2)$ are contained in N. Therefore $h_1'=t_1q_{i_1}=(f_{i_1},e,\ldots ,e , g_1^{-1} ,e,g_1\phi (i_1))$ and $h_2'=t_2q_{i_2}^a=(e,f_{i_2},e,\ldots ,e , g_2^{-1} ,g_2\phi (i_2))$ are contained in N. Hence $h_1'h_2'{h_1'}^{-1}{h_2'}^{-1}=(e,\ldots ,e , h_1h_2{h_1}^{-1}{h_2}^{-1})\in N$. Thus $(E,\ldots ,E,H')<N$.$\square$

Lemma 4

If $H'\lneq H_0<H^kH'$ then $(E,\ldots ,E,H^k)<N$.

Proof

If $H'\lneq H_0<H^kH'$ then for every $i \in \mathop {\mathcal {I}}\nolimits _2$ the following equality holds: $f_i^k=e$.

Let $h \in H$. Then $h=gh_0$ for some $g\in \langle F\rangle$ and $h_0\in H_0$. Since $H_0>H'$ and $F^{\mathop {\mathcal {I}}\nolimits _1}\cup F^{\mathop {\mathcal {I}}\nolimits _2} = F$ there exist $g_1\in \langle F^{\mathop {\mathcal {I}}\nolimits _1}\rangle$, $g_2\in \langle F^{\mathop {\mathcal {I}}\nolimits _2}\rangle$, and $h_1\in H'$ such that $g=g_1g_2h_1$. Since $H_0>H'$ there exists $i \in \mathop {\mathcal {I}}\nolimits _2$ satisfying $\phi (i)=h_1h_0$. Thus we have $h=g_1g_2\phi (i)$. By the construction, the set S contains the element $q_{i}=(f_{i},e,\ldots ,e,\phi (i))$. By Lemma 2 element $t_2=(e,\ldots ,e , g_2^{-1} ,g_2)$ is contained in N. Let $a\in A$ be such that $a(0)=n$. Note that element $t_1=a^{-1}(g_1,e,\ldots ,e)a=(e,\ldots ,e,g_1)$ is contained in N. Therefore $h'=t_1t_2q_i =(f_{i},e,\ldots ,e , g_2^{-1},g_1g_2\phi (i))$ is contained in N. By the condition of the lemma there is $h_2\in H'$ such that $g_2^p=h_2$. Let $a_1\in A_2$ be such that $a_1(n-1)=n$. Then $(e,\ldots ,e,h_2,e)= a_1^{-1}(e,\ldots ,e,h_2)a_1\in N$ by Lemma 3. Therefore ${h'}^k(e,\ldots ,e,h_2,e)=(e,\ldots ,e , e, h^k)\in N$. Thus $(E,\ldots ,E,H^k)<N$.$\square$

Lemma 5

$N=G$.

Proof

If $H_0<H'$ then $(E,\ldots ,E,H_0)< N$ by Lemma 3. If $H_0>H'$ then the conditions of Lemma 4 hold by condition 5 of the L-condition. Thus in this case $(E,\ldots ,E,H_0)< N$ too. By construction $(F,E,\ldots , E)$ is contained in $\langle S_K, (E,\ldots ,E,H_0) \rangle$. Therefore the set $(F,E,\ldots , E)$ is contained in N. Let $a\in A$ be such that $a(0)=n$. Then $a^{-1}(F,E,\ldots , E)a=(E,\ldots , E,F)\subset N$. Since $\langle F\rangle H_0=H$ we have $(E,\ldots , E,H)<N$. Also by transitivity of (A, X) we obtain $(H,\ldots , H)<N$. It follows that $N=G$.$\square$

Now the assertion of Theorem 2 follows immediately from Lemma 1 and Lemma 5.

3 Applications and examples

We first give natural constructions of groups with property PS.

Proposition 3

The following groups satisfy PS:

• 1. The symmetric group of degree $m\ge 5$.

• 2. The permutational wreath product $(B_1,Y_1)\wr (B_2,Y_2)$, where $(B_1,Y_1)$ and $(B_2,Y_2)$ are finite transitive permutation groups and $|Y_1|\ge 2$, $|Y_2|\ge 3$.

• 3. The permutational wreath product $(B_1,Y_1)\wr (B_2,Y_2)\wr (B_3,Y_3)$, where $(B_i,Y_i)$ is a finite transitive permutation group and $|Y_i|\ge 2$ for $i=1,2,3$.

Now we formulate two corollaries from Theorem 2 which are more applicable.

Proposition 4

Let $G= (A,X)\wr H$ and there is an integer $k>1$ with the following properties:

• 1. (A, X) satisfies PS.

• 2. H is an infinite group.

• 3. $H'>H^k$.

• 4. $|H'|\le |H/H'|$.

Then the group G satisfies the L-condition.

Proof

Due to Theorem 2 we only need to show that $H/H'$ has infinite minimal generating set. By the conditions of the theorem $H/H'$ has exponent k. We conclude from result of [11, Proposition3.7] that an abelian group of a bounded exponent has a minimal generating set, and the proposition follows.$\square$

Proposition 5

Let $G= (A,X)\wr H$ and there is an infinite subgroup M of H with the following properties:

• 1. (A, X) satisfies PS.

• 2. M has exponent 2.

• 3. $|M|=|H|$.

• 4. $M\cap H^2 = E$.

Then the group G satisfies the L-condition.

Proof

Set $H_0=H^2$. Then $H/H_0$ and M have minimal generating sets (Hamel basis) as vector spaces over the field with two elements.

Let I be an index set, and let $B=\{b_i\ | \ i\in I\}$ be a minimal generating set of M. Let also $\psi :H\rightarrow H/H^2$ be the canonical epimorphism. Since $M\cap H^2 = E$ the restriction $\psi$ onto M is a bijection and the set $\psi (B)$ is a minimal generating set of $\langle \psi (B) \rangle$. Since B is infinite we have $|\psi (B)|=|B|=|M|=|H|$. Therefore we have $|H|=|H/H_0|$ and $\psi (B)$ can be complemented to Hamel basis F of the space $H/H_0$. It is also evident that $b_i^2=e$ for every $b_i\in B$. Note that inclusion $H'<H^2$ is always true. Thus the group G satisfies the L-condition.$\square$

Note that we use existence of Hamel basis of a vector space over a field in the proof of Proposition 5. Hence this proof uses the axiom of choise in some cases.

In the next section we will apply Proposition 5 to some groups of automorphisms of rooted trees, and particularly give positive answer to Problem 1.

3.1 Automorphism groups of rooted trees

We first recall necessary definitions related to rooted trees and groups acting on rooted trees. All notions which will be defined in this section are well-known, see for instance [10, 19, 20] for more details.

Let us fix our notation. Let $\mathsf {X}=(\mathsf {X}_1,\mathsf {X}_2,\ldots )$ be a sequence of finite sets $\mathsf {X}_i=\{ {0}, {1},\ldots , {n_i}\}$ (we assume $n_i\ge 1$ for all i). Let $\mathsf {X}^n$ denote the set of all words of the form $x_1x_2\ldots x_n$, where $x_i\in \mathsf {X}_i$ for $i=1,\ldots ,n$. Let $\mathsf {X}^*$ denote the set which consist of the empty word $\emptyset$ and all words of the form $x_1x_2\ldots x_n$, where $n\in \mathbb {N}$ and $x_i\in \mathsf {X}_i$ for $i=1,\ldots ,n$. Let $\mathsf {X}^\omega$ denote the set of all infinite words of the form $x_1x_2\ldots$, where $x_i\in \mathsf {X}_i$. We denote by ${\mathsf {X}}^{(k)}$ the infinite sequence $({\mathsf {X}}_k,{\mathsf {X}}_{k+1},\ldots )$.

We can consider the set of words $\mathsf {X}^*$ as rooted tree $T_{\mathsf {X}}$ which can be defined as follows: a vertex $x_1x_2\ldots x_n$ is adjacent to $x_1x_2\ldots x_{n-1}$, $\emptyset$ is the root. For the rooted tree $T_{\mathsf {X}}$ we also define the vertex subtree $T_v$ ($v\in \mathsf {X}^*$) whose vertices are the words of the form $v\mathsf {X}^*$. We call the set of vertices $\mathsf {X}^n$ the n-th level of $T_{\mathsf {X}}$.

Let $\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$ be the group of all automorphisms of the tree $T_{\mathsf {X}}$. Let $G<\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$. We recall the definitions of some standard subgroups of G:

• The subgroup of all elements of G fixing every vertex of n-th level, denoted by $\mathop {\mathrm {Stab}}\nolimits _G(n)$, is called the stabilizer of the n-th level.

• For every $v\in \mathsf {X}^*$ the subgroup of all elements of G fixing every vertex outside the subtree $T_v$, denoted by $\mathop {\mathsf {rist}}\nolimits _G (v)$, is called the rigid stabilizer of the vertex v.

• The group generated by the set $\bigcup _{v\in \mathsf {X}^n}\mathop {\mathsf {rist}}\nolimits v$, denoted by $\mathop {\mathsf {Rist}}\nolimits _G(n)$, is called the rigid stabilizer of the n th level.

Let $\mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}}$ be the subgroup of $\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$ such that an automorphism g of $T_{\mathsf {X}}$ is in $\mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}}$ if and only if the equality $g(uv)=g(u)v$ is valid for any $u\in \mathsf {X}^k$ and any $v\in \mathsf {X}^*$. Note that $\mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}}$ acts by permutations faithfully on the set $\mathsf {X}^k$. Note also that $\mathop {\mathrm {Stab}}\nolimits _{\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}}(k)=\mathop {\mathsf {Rist}}\nolimits _{\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}}(k)$. Therefore the group $\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$ can be decomposed into semidirect product of its subgroups $\mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}} \rightthreetimes \mathop {\mathsf {Rist}}\nolimits _{\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}}(k)$. It follows that $\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$ is isomorphic to the permutational wreath product $(\mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}},\mathsf {X}^k) \wr \mathop {\mathsf {rist}}\nolimits _{\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}}(v)$, where $v\in \mathsf {X}^k$ and $\mathop {\mathsf {Rist}}\nolimits _{\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}}(k)$ is the base subgroup of this wreath product.

We define subgroup $M_0<\mathop {\mathrm {Aut}}\nolimits T_{{\mathsf {X}}}$ as infinite direct product: $M_0= \prod _{i\ge 0}C_2^{(i)}$, where each $C_2^{(i)}$ is isomorphic to the group of order 2. The action of elements of $M_0$ on the tree $T_{{\mathsf {X}}}$ can be defined in the following way. A nontrivial element of $C_2^{(i)}$ acts as follows $\underbrace{ {0} {0}\ldots {0}}_{i} {10}v \rightarrow \underbrace{{0} {0}\ldots {0}}_{i} {11}v$, $\underbrace{ {0} {0}\ldots {0}}_{i} {11}v \rightarrow \underbrace{{0} {0}\ldots {0}}_{i} {10}v$ for every $v\in \mathsf {X}^{(i+1)}$, and $w\rightarrow w$ for the other words of $\mathsf {X}^*$.

Lemma 6

The intersection $M_0\cap (\mathop {\mathrm {Aut}}\nolimits T_{{\mathsf {X}}})^2$ is trivial.

Proof

For every $g\in \mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$ and $n\ge 0$ we can write $g=g_n(g_{v_1},\ldots ,g_{v_k})$, where $g_n\in \mathop {\mathrm {Aut}}\nolimits _n T_{\mathsf {X}}$, $(g_{v_1},\ldots ,g_{v_k})\in \mathop {\mathsf {Rist}}\nolimits _{\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}}(n)$, and $\{v_1,\ldots , v_k\}=\mathsf {X}^n$. Write $\Pi _n g=\prod _{v\in \mathsf {X}^n}g_v$ for every $n\ge 0$.

It is evident that $\Pi _n g^2$ is an even permutation of $\mathsf {X}_{n+1}$ for every $g\in \mathop {\mathrm {Aut}}\nolimits T_{{\mathsf {X}}}$ and $n\ge 0$. Therefore $\Pi _n h$ is an even permutation of $\mathsf {X}_{n+1}$ for every $h\in (\mathop {\mathrm {Aut}}\nolimits T_{{\mathsf {X}}})^2$ and $n\ge 0$. But for every nontrivial element $g\in M_0$ there is $m\ge 0$ such that $\Pi _m g$ is an odd permutation of $\mathsf {X}_{m+1}$. Thus the intersection $M_0\cap (\mathop {\mathrm {Aut}}\nolimits T_{{\mathsf {X}}})^2$ is trivial.$\square$

Proposition 6

Let G be an infinite automorphism group of $T_{\mathsf {X}}$ and there is a positive integer k with the following properties:

• 1. The group G can be decomposed into a semidirect product of its subgroups $(G\cap \mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}},\mathsf {X}^k)\rightthreetimes \mathop {\mathsf {Rist}}\nolimits _G(k)$ provided the group $(G\cap \mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}},\mathsf {X}^k)$ satisfies PS.

• 2. $|M_0\cap G|=|G|$.

Then the group G satisfies the L-condition.

Proof

Let G be a group and $k\in \mathbb {N}$ be such that all conditions of the statement are satisfied. Let $v=0\ldots 0\in \mathsf {X}^k$. Then G is isomorphic to the permutational wreath product $(G\cap \mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}},\mathsf {X}^k)\wr \mathop {\mathsf {rist}}\nolimits _G(v)$.

Consider the subgroup $M=M_0\cap \mathop {\mathsf {rist}}\nolimits _G(v)$ of the group G. It is obvious that M has exponent 2. Since $M_0\cap G=(M_0 \cap G\cap \mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}}) \times M$ we have $|M|=|M_0\cap G|$. Combining it with the second condition of the statement we obtain $|M|=|G|$. It follows that $|M|=|G|=|\mathop {\mathsf {rist}}\nolimits _G(v)|$. By Lemma 6 we have $M\cap (\mathop {\mathsf {rist}}\nolimits _G(v))^2< M_0\cap (\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}})^2=E$. Thus the group G satisfies the L-condition by Proposition 5, and the statement follows.$\square$

3.1.1 Examples of uncountable groups of automorphisms with the L-condition

We recall the definitions of some classes of automorphisms of $T_{\mathsf {X}}$.

• An automorphism g is called finitary if there is a positive integer n such that the equality $g(uv)=g(u)v$ is valid for every $u\in \mathsf {X}^n$ and every $v\in \mathsf {X}^*$.

• An automorphism g is called weakly finitary if for every $w\in \mathsf {X}^\omega$ there are $n\in \mathbb {N}$, $u\in \mathsf {X}^n$, and $v\in \mathsf {X}^\omega$ such that $w=uv$ and $g(uv)=g(u)v$.

• Two words $w_1,w_2\in \mathsf {X}^\omega$ are called cofinal if there are $n\in \mathbb {N}$, $u_1,u_2\in \mathsf {X}^n$, $v\in \mathsf {X}^\omega$ satisfying $w_1=u_1v$ and $w_2=u_2v$. An automorphism g is called cofinal if it maps cofinal words to cofinal words.

• An automorphism g is called bicofinal if both g and $g^{-1}$ are cofinal.

Denote by $\mathop {\mathrm {Aut}}\nolimits _f T_{\mathsf {X}}$, $\mathop {\mathrm {Aut}}\nolimits _{wf} T_{\mathsf {X}}$, $\mathop {\mathrm {Aut}}\nolimits _{b} T_{\mathsf {X}}$ the sets of all finitary, weakly finitary and bicofinal automorphisms of $T_{\mathsf {X}}$ respectively. All of these sets are groups.

Note that, by definitions, we have the following inclusions:

$$\begin{aligned} \mathop {\mathrm {Aut}}\nolimits _f T_{\mathsf {X}}<\mathop {\mathrm {Aut}}\nolimits _{wf} T_{\mathsf {X}}<\mathop {\mathrm {Aut}}\nolimits _{b} T_{\mathsf {X}}. \end{aligned}$$

For more details on these groups we refer the reader to [15].

Theorem 7

The groups $\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$, $\mathop {\mathrm {Aut}}\nolimits _{wf} T_{\mathsf {X}}$ and $\mathop {\mathrm {Aut}}\nolimits _{b} T_{\mathsf {X}}$ satisfy the L-condition and so have minimal generating sets.

Proof

Let G be one of the above groups. Then G can be decomposed into semidirect product of its subgroups $(\mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}},\mathsf {X}^k)\rightthreetimes \mathop {\mathsf {Rist}}\nolimits _G(k)$ for a positive integer k. The permutation group $(\mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}},\mathsf {X}^k)$ satisfies the condition PS for $k\ge 3$ by Proposition 3. It is clear that $M_0<\mathop {\mathrm {Aut}}\nolimits _{wf} T_{\mathsf {X}}<\mathop {\mathrm {Aut}}\nolimits _{b} T_{\mathsf {X}}<\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$. It follows that G satisfies all conditions of Proposition 6, and the statement follows.$\square$

3.1.2 Examples of countable groups of automorphisms with L-condition

Proposition 8

Let G be a countable automorphism group of the rooted tree $T_{\mathsf {X}}$ with the following properties:

• $\mathop {\mathrm {Aut}}\nolimits _f T_{\mathsf {X}}<G$.

• $\mathop {\mathsf {Rist}}\nolimits _G(k)=\mathop {\mathrm {Stab}}\nolimits _G(k)$ for some integer $k\ge 3$.

Then the group G satisfies the L-condition.

Proof

By the condition of the proposition $M_0\cap G > M_0\cap \mathop {\mathrm {Aut}}\nolimits _f T_{\mathsf {X}}$. Since the intersection $M_0\cap \mathop {\mathrm {Aut}}\nolimits _f T_{\mathsf {X}}$ is countable, $|M_0\cap G | = |G|$. Since $\mathop {\mathrm {Aut}}\nolimits _f T_{\mathsf {X}}<G$, $\mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}}<G$. Therefore G is decomposed into semidirect product $(\mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}},\mathsf {X}^k)\rightthreetimes \mathop {\mathsf {Rist}}\nolimits _G(k)$ of its subgroups. The permutation group $(\mathop {\mathrm {Aut}}\nolimits _k T_{\mathsf {X}},\mathsf {X}^k)$ satisfies condition PS for $k\ge 3$ by Proposition 3. It follows that G satisfies all conditions of Proposition 6, and the statement follows.$\square$

From now we assume that $X_1=X_2=\ldots$. In this case $T_{\mathsf {X}}$ is called regular rooted tree.

A vertex subtree $T_v$ of $T_{\mathsf {X}}$ for every $v\in \mathsf {X}^n$ can be naturally identified with the whole tree $T_{\mathsf {X}}$:

$$\begin{aligned} \pi _v:v x_{n+1} \ldots x_m\mapsto x_{n+1} x_{n+2} \ldots x_m. \end{aligned}$$

Thus for every $g\in \mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$ and $v\in \mathsf {X}^*$ we can define automorphism $g|_v\in \mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$ in the following way: $g|_v(u)=w$ if and only if $g(vu)=g(v)w$ for every $u,w\in \mathsf {X}^*$. We call the automorphism $g|_v\in \mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$ the state of g in v.

An automorphism $g\in \mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$ is a finite-state automorphism if the set of its states is finite. All finite-state automorphisms of the tree $T_{\mathsf {X}}$ form the group $\mathop {\mathrm {FAut}}\nolimits T_{\mathsf {X}}$ of finite-state automorphisms of the tree $T_{\mathsf {X}}$.

Let us define the number $\Theta _n(g)=\#\{v\in \mathsf {X}^n \ |\ g|_v \ne e\}$ for every $g\in \mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$.

The set of all finite-state automorphisms $g\in \mathop {\mathrm {FAut}}\nolimits T_{\mathsf {X}}$ such that the sequence $\Theta _n(g)$ is bounded by a polynomial in n of degree m forms the group $\mathop {\mathrm {Pol}}\nolimits (m)$ of polynomial automorphisms of degree m of the tree $T_{\mathsf {X}}$. The group $\mathop {\mathrm {Pol}}\nolimits (0)$ is also called the group of bounded automorphisms. The group of polynomial automorphisms, denoted by $\mathop {\mathrm {Pol}}\nolimits (\infty )$, is defined to be the union of increasing chain of groups: $\mathop {\mathrm {Pol}}\nolimits (\infty )=\bigcup _{m=0}^{\infty } \mathop {\mathrm {Pol}}\nolimits (m)$.

A subgroup G of $\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$ is self-similar provided $g|_v \in G$ for all $g\in G$ and $v\in \mathsf {X}^*$. The group $\mathop {\mathrm {RAut}}\nolimits T_{\mathsf {X}}$ of functionally recursive automorphisms of $T_{\mathsf {X}}$ can be defined as the union of all finitely generated self-similar subgroups of $\mathop {\mathrm {Aut}}\nolimits T_{\mathsf {X}}$.

We refer the reader to [5, 19, 20] for details concerning groups defined above.

Theorem 9

The groups $\mathop {\mathrm {FAut}}\nolimits T_{\mathsf {X}}$, $\mathop {\mathrm {Pol}}\nolimits (m)$ ($m\ge 0$), $\mathop {\mathrm {Pol}}\nolimits (\infty )$, and $\mathop {\mathrm {RAut}}\nolimits T_{\mathsf {X}}$ satisfy the L-condition and so have minimal generating sets.

Proof

Let G be one of the groups above. It is well known that G is countable group. By definition, the group G contains the group $\mathop {\mathrm {Aut}}\nolimits _f T_{\mathsf {X}}$. Furthermore, we have $\mathop {\mathrm {Stab}}\nolimits _G(k)=\mathop {\mathsf {Rist}}\nolimits _G(k)$ for every positive integer k. It follows that G satisfies the L-condition by Proposition 8, and the theorem follows.$\square$

Finally we obtain the statement of Theorem 1 as an immediate corollary of Theorems 2, 7 and 9.