Finite groups as groups of automata with no cycles with exit

Representations of finite groups as automata groups over a binary alphabet are investigated. The subclass of groups of automata with no cycles with exit is studied.

Gespeichert in:

Bibliographische Detailangaben
Datum:	2010
1. Verfasser:	Russyev, A.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Інститут прикладної математики і механіки НАН України 2010
Schriftenreihe:	Algebra and Discrete Mathematics
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/154493
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:	Finite groups as groups of automata with no cycles with exit / A. Russyev // Algebra and Discrete Mathematics. — 2010. — Vol. 9, № 1. — С. 86–102. — Бібліогр.: 8 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-154493
record_format	dspace
spelling	irk-123456789-1544932019-06-16T01:31:16Z Finite groups as groups of automata with no cycles with exit Russyev, A. Representations of finite groups as automata groups over a binary alphabet are investigated. The subclass of groups of automata with no cycles with exit is studied. 2010 Article Finite groups as groups of automata with no cycles with exit / A. Russyev // Algebra and Discrete Mathematics. — 2010. — Vol. 9, № 1. — С. 86–102. — Бібліогр.: 8 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:20E08. http://dspace.nbuv.gov.ua/handle/123456789/154493 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	Representations of finite groups as automata groups over a binary alphabet are investigated. The subclass of groups of automata with no cycles with exit is studied.
format	Article
author	Russyev, A.
spellingShingle	Russyev, A. Finite groups as groups of automata with no cycles with exit Algebra and Discrete Mathematics
author_facet	Russyev, A.
author_sort	Russyev, A.
title	Finite groups as groups of automata with no cycles with exit
title_short	Finite groups as groups of automata with no cycles with exit
title_full	Finite groups as groups of automata with no cycles with exit
title_fullStr	Finite groups as groups of automata with no cycles with exit
title_full_unstemmed	Finite groups as groups of automata with no cycles with exit
title_sort	finite groups as groups of automata with no cycles with exit
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2010
url	http://dspace.nbuv.gov.ua/handle/123456789/154493
citation_txt	Finite groups as groups of automata with no cycles with exit / A. Russyev // Algebra and Discrete Mathematics. — 2010. — Vol. 9, № 1. — С. 86–102. — Бібліогр.: 8 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT russyeva finitegroupsasgroupsofautomatawithnocycleswithexit
first_indexed	2025-07-14T06:34:59Z
last_indexed	2025-07-14T06:34:59Z
_version_	1837603121206919168
fulltext	Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Volume 9 (2010). Number 1. pp. 86 – 102 c© Journal “Algebra and Discrete Mathematics” Finite groups as groups of automata with no cycles with exit Andriy Russyev Communicated by V. I. Sushchansky Dedicated to Professor I.Ya. Subbotin on the occasion of his 60-th birthday Abstract. Representations of finite groups as automata groups over a binary alphabet are investigated. The subclass of groups of automata with no cycles with exit is studied. 1. The class of automata groups contains many interesting and compli- cated groups. Its thorough investigation was started with automata with small number of states. In the case of two states groups of automata over a binary alphabet were completely described in [3]. The great work has been done in the case of 3-state automata over a binary alphabet [2]. Another approach is to investigate representations of some classes of groups as automata groups. Abelian groups generated by automata over a binary alphabet were considered in [5]. Finite automata that generate some finitely presented solvable groups were constructed in [1]. Note interesting examples of finite automata that generate free group of rank 2 ([4]) and free products of finite number of cyclic groups of order 2 ([8]). In this paper we investigate embedding of finite groups in the class of automata groups over a binary alphabet. We study the subclass of groups of automata with no cycles with exit. All groups from this class are finite. We prove that this class is closed under wreath product with some permutation groups and direct powers. It is proved that the action 2000 Mathematics Subject Classification: 20E08. Key words and phrases: automaton, automaton group, finite group, wreath product. Jo u rn al A lg eb ra D is cr et e M at h .A. Russyev 87 of the elements of the group of an automaton with no cycles with exit with n states is uniquely defined by the action on words of length n. This property simplifies calculations in such groups. Some presentations of finite groups by automata with no cycle with exit are obtained. Using GAP system the complete list of groups of automata with no cycles with exit with 2–5 states over a binary alphabet is calculated. 2. Let X be a finite nonempty set. This set is called an alphabet and its elements are called letters. Let us denote by S(X) the symmetric permutation group on alphabet X. An automaton over the alphabet X is a tuple A = 〈X,Q,ϕ, λ〉, where Q denotes the set of states of A, ϕ : Q × X → Q is the tran- sition function and λ : Q×X → X is the output function. A cycle in the automaton A is a sequence of pairwise different states q1, q2, . . . , qn ∈ Q, n ≥ 1, such that there exists a sequence of letters x1, x2, . . . , xn ∈ X which satisfies equalities ϕ(qi, xi) = qi+1, 1 ≤ i < n, and ϕ(qn, xn) = q1. This cycle is called a cycle with exit if there exist i, 1 ≤ i ≤ n, and x ∈ X such that ϕ(qi, x) /∈ {q1, q2, . . . , qn}. In other case this cycle is called a cycle without exit. A state q ∈ Q is cyclic if it belongs to some cycle of the automaton. Consider the set X∗ = ⋃ n≥1X n∪{Λ} of all words over X. The sym- bol Λ denotes the empty word. On this set one can define the operation of concatenation. The set X∗ is a vertex set of a rooted tree TX in which two words are connected by an edge if and only if they are of the form v and vx, where v ∈ X∗, x ∈ X. The empty word Λ is the root of the tree TX . The transition and output functions of the automaton A can be ex- tended to the set Q ×X∗ by the next formulas. For all q ∈ Q, w ∈ X∗ and x ∈ X ϕ(q, wx) = ϕ(ϕ(q, w), x), ϕ(q,Λ) = q, λ(q, wx) = λ(q, w)λ(ϕ(q, w), x), λ(q,Λ) = Λ. Every state q ∈ Q defines an endomorphism fq = λ(q, ·) : X∗ → X∗ of the tree TX . We will usually identify the state q with the endomorphism fq. The automaton A is called invertible if all these maps are automorphisms. Definition 1 ([4, section 1.5.4]). The group of an invertible automaton A = 〈X,Q,ϕ, λ〉 is the group generated by the set {fq : q ∈ Q}. Hereafter all automata are invertible. One can describe the automaton A by labeled directed graph with the set of vertices Q. Each vertex q ∈ Q is labeled by the permutation Jo u rn al A lg eb ra D is cr et e M at h .88 Finite groups as groups of automata λ(q, ·) ∈ S(X). The transition function defines the set of edges. For every pair (q, x) ∈ Q × X there exists an edge with label x from vertex q to vertex ϕ(q, x). Let G be the group generated by an automaton A over an alphabet X. For element g ∈ G and word w ∈ X∗ there exists an automorphism g\|w : X∗ → X∗ such that g(wu) = g(w)g\|w(u) for every u ∈ X∗. This automorphism g\|w is called the restriction of g in w. If all restrictions of g in all words of length m coincide we will also denote them by g\|m. In calculations in the group G it is useful to describe an element g ∈ G by its action on words of length 1 and restrictions in all words of length 1: g = (g\|x1 , g\|x2 , . . . , g\|xn )π, where x1 < x2 < . . . < xn is some ordering of the alphabet X and π = g\|X : X → X is restriction of g on words of length 1. Theorem 1 ([6, theorem 2]). The group of a finite automaton with no cycles with exit is finite. Theorem 2 ([7, theorem 4]). Let A = 〈X,Q,ϕ, λ〉 be an automaton with no cycles with exit over a binary alphabet, \|Q\| = n and G be the group generated by this automaton. Then \|G\| ≤ 22 n−1 . Let P < S(X) be a permutation group, G be a group and N ⊳ G. Consider the subgroup H < GX that contains only elements h : X → G satisfying condition h(x)(h(y))−1 ∈ N for all x, y ∈ X. The subwreath product of the permutation group P with the group G by the normal subgroup N is the semidirect product P ⋉H with the natural action of group P on the subgroup H. Let us denote it by P ≀ N G. If N = G then P ≀ N G ≃ P ≀G. 3. We start with some constructions of automata to produce certain classes of groups. Theorem 3. Let G be a group generated by (finite) automaton (with no cycles with exit) A = 〈X,Q,ϕ, λ〉 over an alphabet X, P < S(X) and for every state q ∈ Q the permutation λ(q, ·) belongs to the group P . Then the group P ≀ G is generated by (finite) automaton (with no cycles with exit) over an alphabet X. Proof. Suppose that the set {p1, p2, . . . , pk} is a generating set of the group P . Let us construct a new automaton P ≀ A = 〈X, Q̃, ϕ̃, λ̃〉 that generates the group P ≀G. Consider the set Q̃ = Q ⊔ {1} ⊔ {p̂i : 1 ≤ i ≤ k} ⊔ (Q×X). Jo u rn al A lg eb ra D is cr et e M at h .A. Russyev 89 The transition and output functions of this automaton are defined on the set Q̃×X as follows. Put ϕ̃\|Q×X = ϕ, λ̃\|Q×X = λ and for x ∈ X ϕ̃(1, x) = 1, λ̃(1, x) = x; ϕ̃(p̂i, x) = 1, λ̃(p̂i, x) = pi(x), 1 ≤ i ≤ k; ϕ̃((q, x0), x) = q, x = x0, ϕ̃((q, x0), x) = 1, x 6= x0, λ̃((q, x0), x) = x, (q, x0) ∈ Q×X. Consider the map ψ : P ≀G→ AutTX defined by [p; g1, g2, . . . , gn] 7→ (g1, g2, . . . , gn)p, where p ∈ P and g1, g2, . . . , gn ∈ G. It is a monomorphism. The elements ψ−1(fp̂i) = [pi; 1, 1, . . . , 1], 1 ≤ i ≤ k, and ψ−1(f(q,x)) = [1; 1, . . . , fq, . . . , 1], q ∈ Q, x ∈ X, are generators of the group P ≀G. Therefore, the elements fp̂i , 1 ≤ i ≤ k, and f(q,x), q ∈ Q, x ∈ X are generators of the group ψ(P ≀G) ≃ P ≀G. If the group P acts transitively on the set X then for every state q ∈ Q only one state (q, x) is required for some x ∈ X. For every state q ∈ Q we have ψ−1(fq) = [λ(q, ·); fϕ(q,x), x ∈ X] ∈ P ≀G, since λ(q, ·) ∈ P . Thus, fq ∈ ψ(P ≀G) and the automaton P ≀A generates the group P ≀G. If the automaton A is finite or does not contain cycles with exit then the constructed one has the same property. Further we give alternative proof of the proposition 2.9.3 from [4] that shows that the class of groups of automata with no cycles with exit is closed under direct powers too and describe construction of an automaton that generates direct power explicitly. Theorem 4. Let G be a group generated by (finite) automaton (with no cycles with exit) over an alphabet X. Then for every positive integer n the group ⊕n i=1G is generated by (finite) automaton (with no cycles with exit) over an alphabet X. Jo u rn al A lg eb ra D is cr et e M at h .90 Finite groups as groups of automata Proof. Suppose that the automaton A = 〈X,Q,ϕ, λ〉 generates the group G. Let us construct a new automaton A[n] that generates ⊕n i=1G. We denote by Mn the set {0, 1, . . . , n − 1}. Consider the automaton A[n] = 〈X,Q ×Mn, ϕn, λn〉 with the transition and output functions for q ∈ Q and x ∈ X defined by equalities ϕn((q, k), x) = (q, k − 1), k 6= 0, λn((q, k), x) = x, k 6= 0, ϕn((q, 0), x) = (ϕ(q, x), n− 1), λn((q, 0), x) = λ(q, x). To prove that A[n] generates the group ⊕n i=1G let us extend functions ϕn and λn to the set (Q×Mn)×X∗. Then ϕn((q, k), x1x2 . . . xn) = (ϕ(q, xk+1), k), λn((q, k), x1x2 . . . xn) = x1 . . . xkλ(q, xk+1)xk+2 . . . xn and f(q,k)(x1x2 . . . xnu) = x1 . . . xkλ(q, xk+1)xk+2 . . . xnf(ϕ(q,xk+1),k)(u). The set {f(q,k) : q ∈ Q, k ∈ Mn} is a generating set of the group of the automaton A[n]. Consider a word x1x2 . . . xnxn+1 . . . xmn ∈ Xmn, m ≥ 1. For every k ∈ Mn all elements of the set {f(q,k) : q ∈ Q} preserve letters in po- sitions l satisfying condition l − 1 6= k (mod n). Transformation of the subword xk+1xn+k+1 . . . x(m−1)n+k+1 by f(q,k) coincide with the action of fq on words of length m. Therefore, the set {f(q,k) : q ∈ Q} generates the group G for every k ∈Mn. Let us prove that f(q1,k1) and f(q2,k2) commute for k1 6= k2. It is enough to consider the case k1 < k2. We will prove by induction on m that for u ∈ Xmn the equality f(q1,k1)(f(q2,k2)(u)) = f(q2,k2)(f(q1,k1)(u)) (1) holds. The case m = 0 is trivial. For any letters x1, x2, . . . , xn ∈ X and any word u ∈ Xmn be induction hypothesis we have f(q1,k1)(f(q2,k2)(x1x2 . . . xnu)) = = f(q1,k1)(x1 . . . xk2λ(q2, xk2+1)xk2+2 . . . xnf(ϕ(q2,xk2+1),k2)(u) = = x1 . . . xk1λ(q1, xk1+1)xk1+2 . . . xk2λ(q2, xk2+1) xk2+2 . . . xnf(ϕ(q1,xk1+1),k1)(f(ϕ(q2,xk2+1),k2)(u)) = = f(q2,k2)(x1 . . . xk1λ(q1, xk1+1)xk1+2 . . . xnf(ϕ(q1,xk1+1),k1)(u) = Jo u rn al A lg eb ra D is cr et e M at h .A. Russyev 91 = f(q2,k2)(f(q1,k1)(x1x2 . . . xnu)). Therefore, equality (1) holds for any word u ∈ X(m+1)n. Thus, the automaton A[n] generates ⊕n i=1G. If the automaton A is finite or does not contain cycles with exit then the constructed one has the same property. Corollary 1. Let G be a group generated by (finite) automaton (with no cycles with exit) over a binary alphabet. Then Z2 ≀ G and ⊕n i=1G are generated by (finite) automata (with no cycles with exit) over a binary alphabet. In general case the fact that the groups G1 and G2 are generated by automata over an alphabet X does not imply that the group G1 × G2 is generated by an automaton over the same alphabet X. For example there is no automaton over a binary alphabet that generates the group Z ⊕ Z2 ([5, proposition 3.4]), but the groups Z and Z2 are generated by automata over a binary alphabet. If one does not require that the alphabet is the same then it is easy to construct an automaton that generates the group G1 × G2. We assume that automata generating G1 and G2 are defined over alphabets X1 and X2 respectively and X1 ∩X2 = ∅. The automaton generating the group G1 ×G2 is constructed over X1 ∪X2. It contains two disjoint parts: the first acts on X1 as automaton for G1 and trivially on X2 and the second acts on X2 as automaton for G2 and trivially on X1. 4. Here we show how to distinguish elements of the group of automata that have no cycles with exit. Lemma 1. Let A be an n-state automaton with no cycles with exit and G be the group generated by the automaton A. Suppose that all states of A are cyclic. If elements w1, w2 ∈ G act equally on words of length n, then w1 = w2. Proof. Let us denote by k the number of cycles in the automaton A and prove the statement of the lemma by induction on k. It is true for k = 1, since wi(uu ′) = wi(u)wi(u ′), i = 1, 2, for all words u ∈ Xn, u′ ∈ X∗. Suppose that statement is true for automata with k−1 cycles. Let us choose a cycle C in the automaton A. Generators of the group G pairwise commute as all restrictions in words of length 1 coincide for every state. Therefore, elements w1 and w2 can be written in the form wi = uiw ′ i, i = 1, 2, where u1 and u2 contain all multipliers defined by states of the cycle C. The product u−1 1 u2w ′−1 1 w′ 2 acts trivially on words of length n. Hence, elements u−1 2 u1 and w′−1 1 w′ 2 act equally on words of length n. Let Jo u rn al A lg eb ra D is cr et e M at h .92 Finite groups as groups of automata us denote by m the length of the cycle C. Then (u−1 1 u2) ∣ ∣ m = u−1 1 u2. On words of length n−m the equality (w′−1 1 w′ 2) ∣ ∣ m = (u−1 2 u1) ∣ ∣ m = u−1 2 u1 = w′−1 1 w′ 2 holds. Elements (w′−1 1 w′ 2) ∣ ∣ m and w′−1 1 w′ 2 belong to the group generated by an automaton with k − 1 cycles. Therefore, by induction hypothesis, we have (w′−1 1 w′ 2) ∣ ∣ m = w′−1 1 w′ 2 and (u−1 1 u2w ′−1 1 w′ 2) ∣ ∣ m = (u−1 1 u2) ∣ ∣ m (w′−1 1 w′ 2) ∣ ∣ m = u−1 1 u2w ′−1 1 w′ 2. As the product u−1 1 u2w ′−1 1 w′ 2 acts trivially on words of length m, the previous equality implies w−1 1 w2 = u−1 1 u2w ′−1 1 w′ 2 = 1. Theorem 5. Let A be an n-state automaton with no cycles with exit and G be the group generated by the automaton A. If elements w1, w2 ∈ G act equally on words of length n, then w1 = w2. Proof. Let us choose the smallest m ≥ 0 such that for all words v ∈ Xm elements w1 ∣ ∣ v and w2 ∣ ∣ v are products of generators defined by cyclic states of the automaton A or their inverses. Let v ∈ Xm be arbitrary word. It follows from conditions of the theorem that w1 ∣ ∣ v = w2 ∣ ∣ v on words of length n −m. Number of cyclic states of the automaton A is less than n −m. Therefore, lemma 1 implies w1 ∣ ∣ v = w2 ∣ ∣ v . Elements w1 and w2 act equally on first m letters. Hence, w1 = w2. 5. Let us describe some series of groups generated by automata with no cycles with exit over a binary alphabet. Proposition 1. The group of the automaton shown in figure 1 is iso- morphic to the group ⊕n i=1 Z2 ⊕ (Z2 ≀ Z2), n ≥ 1. '&%$ !"#e 0,1 // b1 '&%$ !"#e b2 · · · // '&%$ !"#e 0,1 // bn '&%$ !"#σ 0,1ee c '&%$ !"#e 0 OO 1 44jjjjjjjjjjjjjjjjjjjjjjjjjj a Figure 1 Proof. The generators of the group satisfy the equalities a2 = c2 = 1, b2i = 1, bibj = bjbi, bic = cbi, 1 ≤ i, j ≤ n. Jo u rn al A lg eb ra D is cr et e M at h .A. Russyev 93 Therefore equalities abi = (b1, c)(bi+1, bi+1) = (bi+1, bi+1)(b1, c) = bia, 1 ≤ i < n and abn = (b1, c)(c, c) = (c, c)(b1, c) = bna hold. So, for the group of the automaton we get 〈a, c, bi, 1 ≤ i ≤ n〉 ≃ 〈bi, 1 ≤ i ≤ n〉 ⊕ 〈a, c〉 ≃ n ⊕ i=1 Z2 ⊕ 〈a, c〉, since the generators {bi, 1 ≤ i ≤ n} pairwise commute and their orders are equal to 2. Let us find the order of the product ac = (b1, c)(c, c)σ = (b1c, 1)σ: (ac)2 = (b1c, 1)σ(b1c, 1)σ = (b1c, b1c); (ac)4 = (b1c, b1c)(b1c, b1c) = (b1cb1c, b1cb1c) = (1, 1) = 1. This implies that 〈a, c〉 ≃ Z2 ≀ Z2. Proposition 2. The group of the automaton shown in figure 2 is iso- morphic to the group K4 ≀ Z2. '&%$ !"#e 0,1ee '&%$ !"#e 0,1 //d '&%$ !"#e 0 77oooooooo 1 ''OOOOOOOO a '&%$ !"#σ 0,1ee c Figure 2 Proof. The generators of the group satisfy the equalities a2 = c2 = d2 = 1, (ca)4 = ((c, c)σ(1, c))4 = ((1, c)σ(1, c)σ)2 = (c, c)2 = 1, (ad)4 = ((1, c)(a, a))4 = (a4, (ca)4) = 1, (ada · c)2 = ((1, c)(a, a)(1, c)(c, c)σ)2 = ((ac, ca)σ)2 = 1. Since (ada)2 = 1, we get 〈c, ada〉 ≃ K4 and 〈a, c, d〉 ≃ 〈c, ada, a〉 ≃ 〈c, ada〉⋉ 〈a, cac, dad, cdadc〉. The action of the generators c, ada on the set {a, cac, dad, cdadc} is shown on the diagram. a oo c // KS ada �� cacKS ada �� dad oo c // cdadc Jo u rn al A lg eb ra D is cr et e M at h .94 Finite groups as groups of automata The equalities (ac)4 = (ad)4 = 1 imply that the generator a commutes with the generators cac and dad. Since (a · cdadc)2 = (a · c · adada · c)2 = (a · ada · c · da · c)2 = = (dac)4 = ((ac, a)σ)4 = ((ac, a)(a, ac))2 = = (aca, c)2 = 1, the generators a and cdadc commute and the generators cac and dad commute as well. It remains to check that the generator cdadc commutes with the generators cac and dad: (cac · cdadc)2 = (cadadc)2 = c(ad)4c = 1; (dad · cdadc)2 = (dadc)4 = (adada · c)4 = = (ad · c · ada)4 = ad(ca)4da = 1. Thus 〈a, c, d〉 ≃ K4 ≀ Z2 ≃ 〈a, b, c \| a2, b2, c2, (ab)4, (ac)4, (bc)2, (abc)4〉, where b = ada. Proposition 3. The group of the automaton shown in figure 3 is iso- morphic to the group ⊕n i=1 Z2 ⊕ (K4 ≀ Z2), n ≥ 1. '&%$ !"#e 0,1 // b1 '&%$ !"#e b2 · · · // '&%$ !"#e 0,1 // bn '&%$ !"#σ 0,1ee c '&%$ !"#e 0,1 //d '&%$ !"#e 0 OO 1 44jjjjjjjjjjjjjjjjjjjjjjjjjj a Figure 3 Proof. One can obtain this automaton from the automaton shown in figure 1 by adding the state d. Therefore we have a2 = c2 = d2 = 1, b2i = 1, abi = bia, cbi = bic, bibj = bjbi, 1 ≤ i, j ≤ n, (ac)4 = 1. It follows that dbi = (a, a)(bi+1, bi+1) = (bi+1, bi+1)(a, a) = bid, 1 ≤ i < n, and for the group of the automaton we get 〈a, c, d, bi, 1 ≤ i ≤ n〉 ≃ 〈bi, 1 ≤ i < n〉 ⊕ 〈a, c, d, bn〉 ≃ ≃ n−1 ⊕ i=1 Z2 ⊕ 〈a, c, d, bn〉. Jo u rn al A lg eb ra D is cr et e M at h .A. Russyev 95 Let as show that bn(ac) 2 commutes with a, c and d: a · bn(ac) 2 = bna(ac) 2 = bn(ac) 2 · a, c · bn(ac) 2 = bnc(ac) 2 = bn(ac) 2 · c, d · bn(ac) 2 = (a, a)(c, c)(b1c, b1c) = (a, a)(b1, b1) = (b1, b1)(a, a) = (c, c)(b1c, b1c)(a, a) = bn(ac) 2 · d, which implies 〈a, c, d, bn〉 ≃ 〈bn(ac) 2〉 ⊕ 〈a, c, d〉 ≃ Z2 ⊕ 〈a, c, d〉. It remains to prove that 〈a, c, d〉 ≃ K4 ≀ Z2. Since (ab1) 2 = (ac)4 = 1, we have (ada · c) = (b1, c)(a, a)(b1, c)(c, c)σ = (ac, ca)σ, (ada · c)2 = (ac, ca)σ(ac, ca)σ = (ac, ca)(ca, ac) = 1, (ad)4 = ((b1, c)(a, a)) 4 = ((b1a) 4, (ca)4) = 1. As c2 = (ada)2 = 1, we get 〈c, ada〉 ≃ K4 and 〈a, c, d〉 ≃ 〈c, ada, a〉 ≃ 〈c, ada〉⋉ 〈a, cac, dad, cdadc〉. The action of the generators c, ada on the set {a, cac, dad, cdadc} is shown on the diagram. a oo c // KS ada �� cacKS ada �� dad oo c // cdadc The equalities (ac)4 = (ad)4 = 1 imply that the generator a commutes with the generators cac and dad. Since (a · cdadc)2 = (a · c · adada · c)2 = (a · ada · c · da · c)2 = = (dac)4 = ((ab1c, a)σ) 4 = ((ab1c, a)(a, ab1c)) 2 = = (ab1ca, b1c) 2 = 1, the generators a and cdadc commute and the generators cac and dad commute as well. The proof that the generator cdadc commutes with the generators cac and dad is the same as in the proof of the proposition 2. Thus 〈a, c, d〉 ≃ K4 ≀ Z2. Jo u rn al A lg eb ra D is cr et e M at h .96 Finite groups as groups of automata Proposition 4. The group of the automaton shown in figure 4 is iso- morphic to the group Z2 ⊕ ≀ n i=1 Z2, n ≥ 1 '&%$ !"#e 0 // 1 77 an '&%$ !"#e 1 55 an−1 · · · // '&%$ !"#e 0,1 // a1 '&%$ !"#σ 0,1ee a0 Figure 4 Proof. The generators of the group satisfy the equalities a2i = (ai−1, a0)(ai−1, a0) = (a2i−1, a 2 0) for i > 0 and a20 = (a20, a 2 0) which implies a2i = 1, 0 ≤ i ≤ n. Let us choose another set of generators in the group G of the automata G = 〈ai, 0 ≤ i ≤ n〉 ≃ 〈a0, aiai−1, 1 ≤ i ≤ n〉. Consider the subgroup H = 〈aiai−1, 1 ≤ i ≤ n〉. For its generators we get aiai−1 = (ai−1, a0)(ai−2, a0) = (ai−1ai−2, 1), (aiai−1) 2 = ((ai−1ai−2) 2, 1), i > 1; a1a0 = (a0, a0)(a0, a0)σ = (1, 1)σ, (a1a0) 2 = 1. Thus H = 〈aiai−1, 1 ≤ i ≤ n〉 ≃ n ≀ i=1 Z2. Let us show that the generator a0 can be replaced by another one that commutes with all generators of the subgroup H. For a word w = ai1ai2 . . . aik we denote by r(w) the word ai1+1ai2+1 . . . aik+1. Consider the sequence w0 = a1, wi = r(wi−1)a0r(wi−1)a0a1, 1 ≤ i ≤ n− 1. All words of this sequence contain odd number of letters. We will identify them with the corresponding products in the group G. So, we have w0 = (a0, a0), wi = (wi−1, wi−1), 1 ≤ i ≤ n− 1. Let us prove by induction on i that wi−1 commutes with all elements aj , 0 ≤ j ≤ i. Case i = 1 is trivial. The equalities Jo u rn al A lg eb ra D is cr et e M at h .A. Russyev 97 wia0 = (wi−1, wi−1)(a0, a0)σ = = (wi−1a0, wi−1a0)σ = (a0wi−1, a0wi−1)σ = = (a0, a0)σ(wi−1, wi−1) = a0wi are equivalent to the equality wi−1a0 = a0wi−1 which implies from the induction hypothesis. For 1 ≤ j ≤ i+ 1 by induction hypothesis we get wiaj = (wi−1, wi−1)(aj−1, a0) = = (wi−1aj−1, wi−1a0) = (aj−1wi−1, a0wi−1) = = (aj−1, a0)(wi−1, wi−1) = ajwi. Hence wn−1 commutes with all elements ai, 0 ≤ i ≤ n, and, consequently, with all generators aiai−1, 1 ≤ i ≤ n, of the subgroup H. Let us prove that the generator a0 can be replaced by the generator wn−1. A product of even number of elements ai, 0 ≤ i ≤ n, belongs to the subgroup H, since aiaj = aiai−1 · ai−1ai−2 · · · aj+1aj and ajai = (aiaj) −1 for i > j. The element a0wn−1 is the product of even number of elements ai, 0 ≤ i ≤ n, and, consequently, belongs to the subgroup H. Hence the ele- ment a0 can be represented as a product of wn−1 and the generators of the subgroup H. Thus G ≃ 〈wn−1, aiai−1, 1 ≤ i ≤ n〉 ≃ ≃ 〈wn−1〉 ⊕ 〈aiai−1, 1 ≤ i ≤ n〉 ≃ Z2 ⊕ n ≀ i=1 Z2, since the order of the element wn−1 is equal to 2. Proposition 5. The group of the automaton shown in figure 5 is iso- morphic to the group Z2 ≀〈a,b,bc〉〈a, b, c \| a 2, b2, c2, (ab)2, (ac)2, (bc)4〉. '&%$ !"#e 0,1 �� '&%$ !"#σ 0,1 �� c '&%$ !"#σ 0,1 __? ? ? ? ? ? ? ? a '&%$ !"#e 0 OO 1 // d '&%$ !"#e 0 __? ? ? ? ? ? ? ? 1 OO b Figure 5 Jo u rn al A lg eb ra D is cr et e M at h .98 Finite groups as groups of automata Proof. Consider the subgroup H = 〈a, b, c〉. It is obvious that a2 = b2 = c2 = 1 and ac = ca. Let us prove that ac and b commute: ac · b = σ(c, c)σ(a, c) = (c, c)(a, c) = (ca, 1), b · ac = (a, c)σ(c, c)σ = (a, c)(c, c) = (ac, 1) = (ca, 1). Hence H ≃ 〈ac〉 ⊕ 〈b, c〉 ≃ Z2 ⊕ 〈b, c〉. It remains to calculate the order of the product bc. bc = (a, c)(c, c)σ = (ac, 1)σ, (bc)2 = (ac, 1)σ(ac, 1)σ = (ac, ac), (bc)4 = (ac, ac)(ac, ac) = (1, 1) = 1. Thus, H ≃ Z2 ⊕ D4. For the group G = 〈a, b, c, d〉 of the automaton we have G < Z2 ≀H. Elements of the group G can be represented by tables [π;h1, h2], where π ∈ Z2 and h1, h2 ∈ H. Every element of the group G is a product of elements from the list d = (1, b), cdc = (c, c)σ(1, b)(c, c)σ = (c, c)(b, 1)(c, c) = (cbc, 1), ada = σ(1, b)σ = (b, 1), acdca = σ(cbc, 1)σ = (1, cbc), bca = (a, c)(c, c)σσ = (ac, 1), cba = (c, c)σ(a, c)σ = (1, ca) = (1, ac) and the element amcn, 0 ≤ m,n ≤ 1. All elements from the list above generate subgroup N×N , N = 〈ac〉⊕〈b〉⊕〈cbc〉 ≃ Z 3 2. The parameter m allows to choose any element π ∈ Z2. It does not change elements h1 and h2. The parameter n allows to choose any pair of elements h1, h2 from coset N or from coset Nc. Thus, G ≃ Z2 ≀〈ā,b,bc〉〈ā, b, c \| ā 2, b2, c2, (āb)2, (āc)2, (bc)4〉, where ā = ac. Proposition 6. The group of the automaton shown in figure 6 is isomor- phic to the group Z2 ≀〈c,ca,cab〉〈a, b, c \| a 2, b2, c2, (ab)4, (ac)4, (bc)2, (abc)4〉. '&%$ !"#e 0,1ee '&%$ !"#e 0,1 //g '&%$ !"#e 0,1 // d '&%$ !"#e 0 77oooooooo 1 ''OOOOOOOO a '&%$ !"#σ 0,1ee c Figure 6 Jo u rn al A lg eb ra D is cr et e M at h .A. Russyev 99 Proof. One can get this automaton from the automaton shown in figure 2 by adding the state g. In proposition 2 we prove that a2 = c2 = d2 = (ac)4 = 1 and H = 〈a, c, d〉 ≃ 〈a, b, c \| a2, b2, c2, (ab)4, (ac)4, (bc)2, (abc)4〉 ≃ K4 ≀ Z2, where b = ada. For the group G = 〈a, c, d, g〉 of the automaton we have aca = (1, c)(c, c)σ(1, c) = (c, 1)(c, 1)σ = σ, aca · a · aca = σ(1, c)σ = (c, 1), aca · d · aca = σ(a, a)σ = (a, a) = d, aca · g · aca = σ(d, d)σ = (d, d) = g. Hence G ≃ 〈aca〉 ⋉ 〈a, a′, d, g〉, where a′ = acaca. One can assume that elements a, a′, d, g belong to the group H×H, and aca acts by permuting components. Consider the subgroup H̄ = 〈a, a′, d, g〉 < H × H. Let us denote by N the normal closure of the set {c} in the group H. Restrictions in words of length 1 of every generator a, a′, d, g belong to the same coset of the subgroup N . Therefore components of every element of the group H̄ belong to the same coset of the subgroup N . Let us prove that H̄ contains all such elements. Using generators a, d, g one can construct a pair with any element of the group H in the second component. In the first component one can put any element from the coset of the subgroupN with second component as representative, since normal closure of the element a′ in the group 〈a′, d, g〉 is equal to N × {1}. Thus, we get G ≃ Z2 ≀N H. It remains to calculate the subgroup N : dcd = (a, a)(c, c)σ(a, a) = (aca, aca)σ, dacad = (a, a)σ(a, a) = σ = aca, adcda = (1, c)(aca, aca)σ(1, c) = (acac, caca)σ = = (acac, acac)σ = (aca, aca)(c, c)σ = dcd · aca · c, cdcdc = (c, c)σ(aca, aca)σ(c, c)σ = (cacac, cacac)σ = = (aca, aca)σ = dcd. Hence N = 〈c, aca, dcd〉 = 〈c, aca, bacab〉 = 〈c〉 ⊕ 〈aca〉 ⊕ 〈dcd〉 ≃ Z 3 2. 6. The class of groups of automata with no cycles with exit even over a binary alphabet is very large. So, the following questions arise. What groups are there in this class? If a group G is in this class then what is the minimal number of states in an automaton that generates G? Jo u rn al A lg eb ra D is cr et e M at h .100 Finite groups as groups of automata '&%$ !"#σ 0,1ee Figure 7 '&%$ !"#σ 0,1 // '&%$ !"#e 0,1ee Figure 8 Using construction from the proof of the theorem 4 one can obtain from the automaton shown in figure 7 an automaton with n states that generates the group ⊕n i=1 Z2. But a minimal generating system of this group contains n elements. Thus, the minimal number of states in an automaton that generates the group ⊕n i=1 Z2 is equal to n. The construction from the proof of the theorem 3 applied to the au- tomaton shown in figure 8 produces an automaton with n+1 states that generates the group ≀ n i=1 Z2. This group has 22 n−1 elements. By theo- rem 2 the group of an automaton with no cycles with exit with n states has at most 22 n−1 elements. But 22 n−1 < 22 n−1 for n ≥ 2. Thus, the minimal number of states in an automaton with no cycles with exit that generates the group ≀ n i=1 Z2, n ≥ 2, is equal to n+ 1. Group 2 states 3 states 4 states Z2 2 25 642 Z2 ⊕ Z2 2 35 838 Z2 ≀ Z2 — 16 720 Z2 ⊕ Z2 ⊕ Z2 — 10 294 Z2 ⊕ (Z2 ≀ Z2) — 16 880 Z2 ⊕ Z2 ⊕ Z2 ⊕ Z2 — — 66 Z2 ⊕ Z2 ⊕ (Z2 ≀ Z2) — — 200 K4 ≀ Z2 — — 80 Z2 ≀ (Z2 ≀ Z2) — — 320 Z2 ⊕ (K4 ≀ Z2) — — 80 Z2 ⊕ (Z2 ≀ (Z2 ≀ Z2)) — — 320 Total 4 102 4440 Table 1. List of the groups of automata with no cycles with exit. The number of states in the automata shown in figures 1 and 3 is equal to the minimal number of generators of the groups generated by them. For the groups of the automata shown in figures 2 and 4 the theorem 2 implies that the number of states is minimal. All groups mentioned above are the complete list of the groups of Jo u rn al A lg eb ra D is cr et e M at h .A. Russyev 101 automata with no cycles with exit with the number of states less or equal to 4. This was checked by the GAP system; results are shown in the table 1. The table 2 contains the complete list of groups of automata with no cycles with exit with 5 states. Is was found by the GAP system too. The groups are marked with a star if the estimation of the number of states in an automaton by theorem 2 is not precise. The following notation is used in the table: G1 = 〈a, b, c \| a2, b2, c2, (ab)2, (ac)2, (bc)4〉 ≃ Z2 ⊕ (Z2 ≀ Z2), G2 = 〈a, b, c \| a2, b2, c2, (ab)4, (ac)4, (bc)2, (abc)4〉 ≃ K4 ≀ Z2, G3 = 〈a, b, c \| a2, b2, c2, (ab)4, (ac)4, (bc)4, (acbc)2〉 ≃ Z2 ≀ (Z2 ≀ Z2). Number of direct factors Z2 Group 0 1 2 3 4 5 {1} — 31436 37926 9850 2796∗ 492∗ D4 37352 47576 14616 2376∗ — — Z2 ≀K4 5040∗ 3600∗ — — — — K4 ≀ Z2 6000 6120 600∗ — — — D4 ⊕ D4 840∗ 600∗ — — — — Z2 ≀ (Z2 ≀ Z2) 32640 33360 3600 — — — Z2 ≀〈a,b,bc〉G1 2688∗ 1920 — — — — Z2 ≀〈a,bc〉G1 2352∗ 1680 — — — — Z2 ≀〈c,ca,cab〉G2 480 480 — — — — Z2 ≀〈b,c,ba,ca〉G2 1920 1920 — — — — Z2 ≀〈ab,c〉G2 960 960 — — — — Z2 ≀〈b,c,ba,ca〉G3 1920 1920 — — — — Z2 ≀ (Z2 ≀ (Z2 ≀ Z2)) 11520 11520 — — — — Table 2. List of the groups of automata with no cycles with exit with 5 states. We consider automata with no cycles with exit over the binary alpha- bet X = {0, 1} with the set of states Q = {1, 2, . . . , n} such that there exists k, 1 ≤ k ≤ n−1, and for q ∈ Q the equality λ(q, ·) = 1 holds if and only if q ≤ k. The tables show the number of automata that generate the specified group. Jo u rn al A lg eb ra D is cr et e M at h .102 Finite groups as groups of automata References [1] L. Bartholdi, Z. Šunić, Some solvable automaton groups, Contemporary Mathe- matics 394, 2006, 11–29. [2] I. Bondarenko, R. Grigorchuk, R. Kravchenko, Y. Muntyan, V. Nekrashevych, D. Savchuk, Z. Šunić, On classification of groups generated by 3-state automata over a 2-letter alphabet, Algebra and Discrete Mathematics, 1 (2008) 1–163. [3] R. I. Grigorchuk, V. V. Nekrashevich, V. I. Sushchanskiy, Automata, dynamical systems, and groups, Tr. Mat. Inst. Steklova, 231 (Din. Sist., Avtom. i Beskon. Gruppy):134–214, 2000. [4] V. V. Nekrashevych, Self-similar groups, volume 117 of Mathematical Surveys and Monographs, American Mathematical Society, Providence, RI, 2005. [5] V. Nekrashevych, S. Sidki, Automorphisms of the binary tree: state closed sub- groups and dynamics of 1/2-endomorphisms, Groups: Topological, Combinatorial and Arithmetic Aspects (T. W. Müller, ed.), LMS Lecture Notes Series, vol. 311, 2004, pp. 375–404. [6] A. V. Russyev, On finite and Abelian groups generated by finite automata, Matem- atychni Studii, 24 (2005) 139–146 (in Ukrainian). [7] A. V. Russyev, Groups of automata with no cycles with exit, Dop. NAS Ukraine, 2(2010) 28-32 (in Ukrainian). [8] D. Savchuk, Ya. Vorobets, Automata generating free products of groups of order 2, http://arxiv.org/abs/0806.4801. Contact information A. Russyev Department of Mechanics and Mathematics Kyiv National Taras Shevchenko University Volodymyrska, 60 Kyiv 01033 E-Mail: russev@mail.univ.kiev.ua Received by the editors: 22.09.2009 and in final form 18.05.2010.

Finite groups as groups of automata with no cycles with exit

Institution

Ähnliche Einträge