The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata

Let Zn be a cubical lattice in the Euclidean space Rn. The generalized dihedral group Dih(Zn) is a topologically discrete group of isometries of Zn generated by translations and reflections in all points from Zn. We study this group as a group generated by a (2n+2)-state time-varying automaton o...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
1. Verfasser:	Woryna, A.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Інститут прикладної математики і механіки НАН України 2008
Schriftenreihe:	Algebra and Discrete Mathematics
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/153364
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:	The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata / A. Woryna // Algebra and Discrete Mathematics. — 2008. — Vol. 7, № 3. — С. 98–101. — Бібліогр.: 8 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-153364
record_format	dspace
spelling	irk-123456789-1533642019-06-15T01:26:23Z The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata Woryna, A. Let Zn be a cubical lattice in the Euclidean space Rn. The generalized dihedral group Dih(Zn) is a topologically discrete group of isometries of Zn generated by translations and reflections in all points from Zn. We study this group as a group generated by a (2n+2)-state time-varying automaton over the changing alphabet. The corresponding action on the set of words is described. 2008 Article The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata / A. Woryna // Algebra and Discrete Mathematics. — 2008. — Vol. 7, № 3. — С. 98–101. — Бібліогр.: 8 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 20E22, 20E08, 20F65. http://dspace.nbuv.gov.ua/handle/123456789/153364 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	Let Zn be a cubical lattice in the Euclidean space Rn. The generalized dihedral group Dih(Zn) is a topologically discrete group of isometries of Zn generated by translations and reflections in all points from Zn. We study this group as a group generated by a (2n+2)-state time-varying automaton over the changing alphabet. The corresponding action on the set of words is described.
format	Article
author	Woryna, A.
spellingShingle	Woryna, A. The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata Algebra and Discrete Mathematics
author_facet	Woryna, A.
author_sort	Woryna, A.
title	The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata
title_short	The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata
title_full	The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata
title_fullStr	The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata
title_full_unstemmed	The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata
title_sort	generalized dihedral groups dih(zn) as groups generated by time-varying automata
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2008
url	http://dspace.nbuv.gov.ua/handle/123456789/153364
citation_txt	The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata / A. Woryna // Algebra and Discrete Mathematics. — 2008. — Vol. 7, № 3. — С. 98–101. — Бібліогр.: 8 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT worynaa thegeneralizeddihedralgroupsdihznasgroupsgeneratedbytimevaryingautomata AT worynaa generalizeddihedralgroupsdihznasgroupsgeneratedbytimevaryingautomata
first_indexed	2025-07-14T04:35:32Z
last_indexed	2025-07-14T04:35:32Z
_version_	1837595605337112576
fulltext	Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 3. (2008). pp. 98 – 111 c© Journal “Algebra and Discrete Mathematics” The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata Adam Woryna Communicated by V. I. Sushchansky Abstract. Let Z n be a cubical lattice in the Euclidean space R n. The generalized dihedral group Dih(Zn) is a topologically discrete group of isometries of Z n generated by translations and reflections in all points from Z n. We study this group as a group generated by a (2n + 2)-state time-varying automaton over the changing alphabet. The corresponding action on the set of words is described. Introduction For any abelian group A the generalized dihedral group Dih(A) is defined as a semidirect product of A and Z2 with Z2 acting on A by inverting elements, i.e. Dih(A) = A⋊φ Z2, with φ(0) the identity and φ(1) inversion. If A is cyclic, then Dih(A) is called a dihedral group. The subgroup of Dih(A) of elements (a, 0) is a normal subgroup of index 2, isomorphic to A, while the elements (a, 1) are all their own inverse. This property in fact characterizes generalized dihedral groups, in the sense that if a group G has a subgroup N of index 2 such that all elements of the complement G−N are of order two, then N is abelian and G ≃ Dih(N). Let Z n be a free abelian group of rank n. We may look on it as a cubical lattice in the Euclidean space R n. The corresponding generalized 2000 Mathematics Subject Classification: 20E22, 20E08, 20F65. Key words and phrases: generalized dihedral groups, time-varying automaton, group generated by time-varying automaton. Jo u rn al A lg eb ra D is cr et e M at h .A. Woryna 99 dihedral group Dih(Zn) is a topologically discrete group of isometries of Z n generated by translations and reflections in all points from Z n. In case n = 1 this is the isometry group of Z, which is called the infinite dihedral group and is isomorphic to the free product of two cyclic groups of order two. For n = 2 it is a type of the so-called wallpaper group - the mathematical concept to classify repetitive designs on two-dimensional surfaces. For n = 3 this is the so-called space group of a crystal. Our new look on the group Dih(Zn) is via the time-varying automata theory. Namely, we realize this group as a group defined by a (2n + 2)-state time-varying automaton over the changing alphabet. 1. Time-varying automata and groups generated by them Let N0 = {0, 1, 2, . . .} be a set of nonnegative integers. A changing al- phabet is an infinite sequence X = (Xt)t∈N0 , where Xt are nonempty, finite sets (sets of letters). A word over the changing alphabet X is a finite sequence x0x1 . . . xl, where xi ∈ Xi for i = 0, 1, . . . , l. We denote by X∗ the set of all words (including the empty word ∅). By \|w\| we denote the length of the word w ∈ X∗. The set of words of the length t we denote by X(t). For any t ∈ N0 we also consider the set X(t) of finite sequences in which the i-th letter (i = 1, 2, . . .) belongs to the set Xt+i−1. In particular X(0) = X∗. Definition 1. A time-varying Mealy automaton is a quintuple A = (Q,X, Y, ϕ, ψ), where: 1. Q = (Qt)t∈N0 is a sequence of sets of inside states, 2. X = (Xt)t∈N0 is a changing input alphabet, 3. Y = (Yt)t∈N0 is a changing output alphabet, 4. ϕ = (ϕt)t∈N0 is a sequence of transitions functions of the form ϕt : Qt ×Xt → Qt+1, 5. ψ = (ψt)t∈N0 is a sequence of output functions of the form ψt : Qt ×Xt → Yt. Jo u rn al A lg eb ra D is cr et e M at h .100 The generalized dihedral groups. . . We say that an automaton A is finite if the set S = ⋃ t∈N0 Qt of all its inside states is finite. If \|S\| = n, we say that A is an n-state automaton. It is convenient to present a time-varying Mealy automaton as a la- belled, directed, locally finite graph with vertices corresponding to the inside states of the automaton. For every t ∈ N0 and every letter x ∈ Xt an arrow labelled by x starts from every state q ∈ Qt to the state ϕt(q, x). Each vertex q ∈ Qt is labelled by the corresponding state function σt,q : Xt → Yt, σt,q(x) = ψt(q, x). (1) To make the graph of the automaton clear, the sets of vertices Vt and Vt′ corresponding to the sets Qt and Qt′ respectively, are disjoint whenever t 6= t′ (in particular, different vertices may correspond to the same inside state). Moreover, we will substitute a large number of arrows connecting two fixed states and having the same direction for a one multi- arrow labelled by suitable letters and if the labelling of such a multi-arrow is obvious we will omit this labelling. For instance Figure 1 presents a 2-state time-varying automaton in which Qt = {0, 1}, Xt = Yt = {0, 1, . . . , t + 1} and the state functions σt,0 = σt and σt,1 = 1 are respectively a cyclical permutation (0, 1, . . . , t+ 1) and the identity permutation of the set Xt. s 0 s 3s 2 s 1 1 32 1 1 1 1 Figure 1: an example of a 2-state time-varying automaton A time-varying automaton may be interpreted as a machine, which being at a moment t ∈ N0 in a state q ∈ Qt and reading on the input tape a letter x ∈ Xt, goes to the state ϕt(q, x), types on the output tape the letter ψt(q, x), moves both tapes to the next position and then proceeds further to the next moment t+ 1. The automaton A with a fixed initial state q ∈ Q0 is called the initial automaton and is denoted by Aq. The above interpretation defines a Jo u rn al A lg eb ra D is cr et e M at h .A. Woryna 101 natural action of Aq on the words. Namely, the initial automaton Aq defines a function fA q : X∗ → Y ∗ as follows: fA q (x0x1...xl) = ψ0(q0, x0)ψ1(q1, x1)...ψl(ql, xl), where the sequence q0, q1, . . . , ql of inside states is defined recursively: q0 = q, qi = ϕi−1(qi−1, xi−1) for i = 1, 2, . . . , l. (2) This action may be extended in a natural way on the set Xω of infinite words over X. The function fA q is called the automaton function defined by Aq. The image of a word w = x0x1 . . . xl under a map fA q can be easily found using the graph of the automaton. One must find a directed path starting in a vertex q ∈ Q0 and with consecutive labels x0, x1, . . . , xl. Such a path will be unique. If σ0, σ1, . . . , σl are the labels of consecutive vertices in this path, then the word fA q (w) is equal to σ0(x0)σ1(x1) . . . σl(xl). In the set of words over a changing alphabet we consider for any k ∈ N0 the equivalence relation ∼k as follows: w ∼k v if and only if w and v have a common prefix of the length k. Let X and Y be changing alphabets and let f be a function of the form f : X∗ → Y ∗. If f preserves the relation ∼k for any k, then we say that f preserves beginnings of the words. If \|f(w)\| = \|w\| for any w ∈ X∗, then we say that f preserves lengths of the words. Theorem 1. [7] The function f : X∗ → Y ∗ is an automaton function (defined by some initial automaton Aq) if and only if it preserves begin- nings and lengths of the words. Definition 2. Let f : X∗ → Y ∗ be an automaton function and let w ∈ X∗ be a word of the length \|w\| = n. The function fw : X(n) → Y(n) defined by the equality f(wv) = f(w)fw(v) is called a remainder of f on the word w or simply a w-remainder of f . Definition 3. Let A = (Q,X, Y, ϕ, ψ) be a time-varying Mealy automa- ton. For any t0 ∈ N0 the automaton A\|t0 = (Q′, X ′, Y ′, ϕ′, ψ′) defined as follows Q′ t = Qt0+t, X ′ t = Xt0+t, Y ′ t = Yt0+t, ϕ′ t = ϕt0+t, ψ′ t = ψt0+t, is called a t0-remainder of A. Jo u rn al A lg eb ra D is cr et e M at h .102 The generalized dihedral groups. . . If f = fA q is defined by the initial automaton Aq and w = x0x1 . . . xl, then the w-remainder fw is an automaton function generated by the initial automaton Bql , where B = A\|l is an l-remainder of A and the initial state ql is defined by (2). Definition 4. An automaton A in which input and output alphabets co- incide and every its state function σt,q : Xt → Xt is a permutation of Xt is called a permutational automaton. If A is a permutational automaton, then for every q ∈ Q0 the trans- formation fA q : X∗ → X∗ is a permutation of X∗. The set SA(X) of automaton functions defined by all initial automata over a common input and output alphabet X forms a monoid with the identity function as the neutral element. The subset GA(X) of functions generated by permutational automata is a group of invertible elements in SA(X). The group GA(X) is an example of residually finite group (see [8]). Definition 5. Let A = (Q,X,X,ϕ, ψ) be a time-varying permutational automaton. The group of the form G(A) = 〈fA q : q ∈ Q0〉 is called the group generated by automaton A. For any permutational automaton A the group G(A) is residually finite, as a subgroup of GA(X). It turns out that groups of this form include the class of finitely generated residually finite groups. Theorem 2. [8] For any n-generated residually finite group G there is an n-state time-varying automaton A such that G ∼= G(A). 2. The embedding into the permutational wreath product In this section we describe a close realtion between time-varying automata groups and permutational wreath products. Let K and H be finitely generated groups such that H is a permutation group of a finite set L. We define the permutational wreath product K ≀L H as a semidirect product (K ×K × . . .×K ︸︷︷︸ \|L\| ) ⋊H, where H acts on the direct product by permuting the factors. Let G be any subgroup of GA(X). For any i ∈ N0 we define the group Gi = 〈 fw : f ∈ G, w ∈ X(i) 〉 , Jo u rn al A lg eb ra D is cr et e M at h .A. Woryna 103 which is a group generated by remainders fw of functions f ∈ G on all words w ∈ X∗ of the length \|w\| = i. In particular G0 = G. Proposition 1. For any f, g ∈ SA(X) and any word w ∈ X∗ we have (fg)w = fwgf(w). (3) If g ∈ GA(X), then ( g−1 ) w = ( gg−1(w) )−1 . (4) Proof. For any u ∈ X(\|w\|) we have (fg)(wu) = (fg)(w)(fg)w(u). On the other hand (fg)(wu) = g(f(wu)) = g(f(w)fw(u)) = = g(f(w))gf(w)(fw(u)) = (fg)(w)(fwgf(w))(u), what gives (3) from the previous equality. The formula (4) follows by substitution of f for g−1 in (3). Proposition 2. Let us put the letters of the set Xi into the sequence x0, x1, . . . , xm−1. Then the mapping Ψ(g) = (gx0 , gx1 , . . . , gxm−1)σg (5) defines the embedding of the group Gi into the permutational wreath prod- uct Gi+1 ≀Xi S(Xi), where the permutation σg ∈ S(Xi) is defined by σg(x) = g(x). Proof. The equalities g(xu) = σg(x)gx(u), x ∈ Xi, u ∈ X(i+1) imply that Ψ is one-to-one. Next, by Proposition 1 we have: Ψ(fg) = ((fg)x0 , . . . , (fg)xm−1)σfg = = (fx0gσf (x0), . . . , fxm−1gσf (xm−1)) σfσg = = (fx0 , fx1 , . . . , fxm−1)σf (gx0 , gx1 , . . . , gxm−1)σg = Ψ(f)Ψ(g). Hence Ψ is a homomorphism. We will rewrite (5) in the form g = [gx0 , gx1 , . . . , gxm−1 ]σg and call this the decomposition of g. In case σg = 1 (the identity permu- tation) we will write g = [gx0 , gx1 , . . . , gxm−1 ]. Jo u rn al A lg eb ra D is cr et e M at h .104 The generalized dihedral groups. . . 3. Dih(Zn) as a time-varying automaton group Let m0 = 2,m1,m2, . . . be an infinite sequence of positive even numbers and let a1, a2, . . . , ak be a sequence of positive odd numbers such that sup i { mi ai 1 + ai 2 + . . .+ ai k } = ∞. (6) Lemma 1. Let r1, r2, . . . , rk be integers such that the congruence ai 1r1 + ai 2r2 + . . .+ ai krk ≡ 0 (mod mi) holds for any i ∈ N0. Then r1 = r2 = . . . = rk = 0. Proof. There are integers qi, such that ai 1r1+. . .+ai krk = qimi for i ∈ N0. Let us denote c = max{\|r1\|, . . . , \|rk\|}. For any i ∈ N0 we have \|qimi\| = \|ai 1r1 + . . .+ ai krk\| ≤ c(ai 1 + . . .+ ai k). We show that qi = 0 for infinitely many i ∈ N0. Otherwise, there is i0 ∈ N0 such that qi 6= 0 for all i ≥ i0. Then c ≥ \|qimi\| ai 1 + . . .+ ai k ≥ mi ai 1 + . . .+ ai k for all i ≥ i0, what is contrary to the assumption (6). Let i1 < i2 < . . . be an infinite sequence for which qij = 0, j ∈ N0. Thus (r1, . . . , rk) is a solution of the homogeneous system of linear equations a ij 1 x1 + . . .+ a ij k xk = 0, j = 1, . . . , k. The matrix of this system is a generalized Vandermonde k×k matrix. It is known that its determinant is always positive. Hence all ri are equal to zero. We define a 2k-state time-varying, permutational automaton A in which (in point 4 below x±m y denotes an arithmetical operation mod- ulo m): 1. Qt = {a1,−a1, a2,−a2, . . . , ak,−ak}, 2. Xt = {0, 1, . . . ,mt − 1}, 3. ϕt(±ai, x) = ai · (−1)x, 4. ψt(±ai, x) = x±mt a t i. Jo u rn al A lg eb ra D is cr et e M at h .A. Woryna 105 We are going to show that the group G(A) generated by the automaton A is isomorphic to the generalized dihedral group Dih(Zk−1). The graph of A is a disjoint sum of k graphs of the form depicted in the Figure 2, each one defining a 2-state time-varying automaton with the set {−ai, ai} of its inside states (the labelling σt constitutes a cyclical permutation (0, 1, . . . ,mt − 1) of the set Xt). Directly from the above s 0 s 0 s 1 -a s 2 -a s 2 a s 3 a s 3 -a s 1 a 1, 3, ..., -1m1 1, 3, ..., -1m2 0, 2, ..., -2m20, 2, ..., -2m10 1 2 3 32 i i i i i i Figure 2: the fragment of A corresponding to the states ±ai ∈ Q0 graph we see that fA ai = fA −ai for i = 1, 2 . . . , k, and hence G(A) = 〈fA a1 , fA a2 , . . . , fA ak 〉. To simplify, we denote fi = fA ai for i = 1, 2, . . . , k. For any i ∈ {1, 2, . . . , k} and any j ∈ N0 we also denote by fi,j the remainder of fi on a zero-word 00 . . . 0 of the length j. In particular fi = fi,0. Proposition 3. The decomposition of fε i,j, ε ∈ {−1, 1} is as follows fε i,j = [fi,j+1, f −1 i,j+1, fi,j+1, f −1 i,j+1, . . . , fi,j+1, f −1 i,j+1]σ εa j i j . In particular f2 i = 1 for i = 1, 2, . . . , k. Proof. Let us denote by f−i,j the remainder of fi on the word 11 . . . 1 of the length j. Directly from the graph of A we have fi,j = [fi,j+1, f − i,j+1, fi,j+1, f − i,j+1, . . . , fi,j+1, f − i,j+1]σ a j i j , f−i,j = [fi,j+1, f − i,j+1, fi,j+1, f − i,j+1, . . . , fi,j+1, f − i,j+1]σ −a j i j . As ai is an odd number, we obtain: fi,jf − i,j = f−i,jfi,j = [fi,j+1f − i,j+1, f − i,j+1fi,j+1, fi,j+1f − i,j+1, . . . , f − i,j+1fi,j+1]. Jo u rn al A lg eb ra D is cr et e M at h .106 The generalized dihedral groups. . . Hence f−i,jfi,j = fi,jf − i,j = 1 and in consequence f−i,j = f−1 i,j . In particular f2 i = f2 i,0 = [fi,1, f −1 i,1 ]σ0[fi,1, f −1 i,1 ]σ0 = [fi,1f −1 i,1 , f −1 i,1 fi,1] = 1. Since all the generators fi are of order two, every element g ∈ G(A) is of the form g = fν1fν2 . . . fνr for some ν1, ν2, . . . , νr ∈ {1, 2, . . . , k} and νj+1 6= νj for j = 1, . . . , r − 1. Proposition 4. Let gw be a remainder of g on the word w ∈ X(i). Then gw = { fν1,if −1 ν2,i . . . f (−1)r−1 νr,i , if x even, f−1 ν1,ifν2,i . . . f (−1)r νr,i , if x odd, where x is the last letter of w. Proof. By Proposition 1 we may write gw = (fν1fν2 . . . fνr)w = (fν1)w1(fν2)w2 . . . (fνr)wr , where (fνj )wj (j = 1, . . . , r) is a remainder of fνj on the word wj = fν1fν2 . . . fνj−1(w) ∈ X(i). From the graph of A and by Proposition 3, the remainder of any generator ft = fA at on an arbitrary word v ∈ X(i) is equal to fε t,i for some ε ∈ {−1, 1}. In consequence gw = fε1 ν1,if ε2 ν2,i . . . f εr νr,i for some ε1, ε2, . . . , εr ∈ {−1, 1}. Let w′ ∈ X∗ be a prefix of w of the length \|w\| − 1 = i− 1. Then gw′ = f ε′1 ν1,i−1f ε′2 ν2,i−1 . . . f ε′r νr,i−1 for some ε′1, ε ′ 2, . . . , ε ′ r ∈ {−1, 1}. By Proposition 1 the element f εj νj ,i is equal to (f ε′j νj ,i−1)x′ - the remainder of f ε′j νj ,i−1 on a one-letter word x′, where x′ = f ε′1 ν1,i−1f ε′2 ν2,i−1 . . . f ε′j−1 νj−1,i−1(x) = x+mi−1 (ε′1a i−1 ν1 + . . .+ ε′j−1a i−1 νj−1 ). Since mi−1 is even and aν1 , . . . , aνj−1 are all odd, the parity of the letter x′ depends only on j and x in the following way: for x even the letter x′ is even only for j odd, and for x odd the letter x′ is even only for j even. Now, it suffices to see that by Proposition 3 the remainder (f ε′j νj ,i−1)x′ is equal to fνj ,i for x′ even, or to f−1 νj ,i for x′ odd. Jo u rn al A lg eb ra D is cr et e M at h .A. Woryna 107 Let g ∈ G(A) be represented by a group-word fν1fν2 . . . fνr (7) (now, we do not assume that νj+1 6= νj). With the group-word (7) we associate the sequence of integers r1, r2, . . . , rk in which ri = r−i − r+i and r+i (r−i ) denotes the number of occurrences of the generator fi in even (odd) positions in (7). Remark 1. Removing in (7) any subword of the form fjfj does not change the value of any ri. Proposition 5. Any word w = x0x1 . . . xt ∈ X∗ is mapped by g on the word g(w) = y0y1 . . . yt ∈ X∗, where yi = xi +mi (−1)xi−1 ( ai 1r1 + ai 2r2 + . . .+ ai krk ) for i = 0, 1, . . . , t (we assume x−1 = 0). Proof. By Remark 1 we may assume that νj+1 6= νj for j = 1, . . . , r − 1. Now, the thesis follows by the equality yi = gx0x1...xi−1(xi) and by Proposition 4. Let r be the length of the group-word (7). In case r even the number of all the symbols in even positions in (7) is equal to the number of all the symbols in odd positions, and in case r odd these numbers differ by one. Hence the sum ε = r1 + r2 + . . .+ rk is equal to (r)2 - the remainder of r modulo 2. Theorem 3. The mapping Ψ(g) = (r1, r2, . . . , rk−1) ε defines the isomorphism between the groups G(A) and Dih(Zk−1). Proof. First we show that Ψ is a well-defined, one-to-one mapping from G(A) to Dih(Zk−1). Let g = fν1 . . . fνr and g′ = fµ1 . . . fµs be any elements of G(A). Let r1, . . . , rk, ε = r1 + . . .+ rk, r′1, . . . , r ′ k, ε′ = r′1 + . . .+ r′k Jo u rn al A lg eb ra D is cr et e M at h .108 The generalized dihedral groups. . . be sequences corresponding to the group-words fν1 . . . fνr and fµ1 . . . fµs respectively. By Proposition 5 we have: g = g′ if and only if xi +mi (−1)xi−1(ai 1r1 + . . .+ ai krk) = xi +mi (−1)xi−1(ai 1r ′ 1 + . . .+ ai kr ′ k) for any xi−1 ∈ Xi−1, xi ∈ Xi and any i ∈ N0. This condition is equivalent to the congruences: ai 1(r1 − r′1) + . . .+ ai k(rk − r′k) ≡ 0 (mod mi) for any i ∈ N0. By Lemma 1 this is equivalent to the equalities: ri = r′i for i = 1, 2, . . . , k. In particular ε = ε′. As a result we have: g = g′ if and only if Ψ(g) = Ψ(g′). To show Ψ is a homomorphism, let us denote Ψ(gg′) = (R1, . . . , Rk−1)ε ′′. Since gg′ = fν1 . . . fνrfµ1 . . . fµs , we have: ε′′ = (r + s)2 = (r)2 +2 (s)2 = ε+2 ε ′. If ε = 0, then r is even. Thus for any i ∈ {1, 2, . . . , k − 1} the position of any symbol fi in the group-word fµ1 . . . fµs has the same parity as in the group-word fν1 . . . fνrfµ1 . . . fµs . In consequence R+ i = r+i + r′i + and R− i = r−i + r′i −. Thus for i = 1, 2, . . . , k − 1 we have in this case Ri = R− i −R+ i = (r−i − r+i ) + (r′i − − r′i + ) = ri + r′i. If ε = 1, then r is odd and the positions of any fi in group-words fµ1 . . . fµs and fν1 . . . fνrfµ1 . . . fµs are of different parity. In consequence R+ i = r+i + r′i − and R− i = r−i + r′i +. Thus for i = 1, 2, . . . , k − 1 we have in this case Ri = R− i −R+ i = (r−i − r+i ) − (r′i − − r′i + ) = ri − r′i. Hence Ψ(gg′) = Ψ(g)Ψ(g′). Tho show Ψ is onto we take any sequence of integers r1, r2, . . . , rk with the sum ε = r1 + r2 + . . . + rk ∈ {0, 1}. Then there is a group-word fν1fν2 . . . fνr in the symbols f1, f2, . . . , fk for which: (i) r = \|r1\| + \|r2\| + . . .+ \|rk\|, (ii) the symbol fi (i = 1, 2, . . . , k) occurs \|ri\| times in this word, (iii) if ri > 0 (ri < 0), then each fi occurs in the odd (even) position. Then Ψ(g) = (r1, r2, . . . , rk−1) ε for the element g = fν1fν2 . . . fνr . Jo u rn al A lg eb ra D is cr et e M at h .A. Woryna 109 Corollary 1. Let \|\|g\|\| be the length of the shortest presentation of any g ∈ G(A) as a product of generators f1, . . . , fk. If Ψ(g) = (r1, r2, . . . , rk−1)ε, then \|\|g\|\| = \|r1\| + \|r2\| + . . .+ \|rk−1\| + \|r1 + r2 . . .+ rk−1 − ε\|. Proof. Any group-word fν1fν2 . . . fνr satisfying the conditions (i)-(iii) in the proof of Theorem 3 constitutes the shortest representative of g. Using Theorem 3 one may derive the following algorithms solving the word problem (WP) and the conjugacy problem (CP) in G(A). ALGORITHMS: Let fν1 . . . fνr and fµ1 . . . fµs be any group-words in f1, . . . , fk. Calculate their sequences: r1, . . . , rk, ε and r′1, . . . , r ′ k, ε ′. Then (WP) the group-words define the same element if and only if ri = r′i for i = 1, . . . , k, (CP) the group-words define the conjugate elements if and only if ε = 0 and ri = −r′i for i = 1, . . . , k, or if ε = 1 and ri ≡ r′i (mod 2) for i = 1, . . . , k. 4. The action on the set of words With the group G = G(A) we associate the following subgroups: 1. StG(w) = {g ∈ G : g(w) = w} - the stabilizer of the word w ∈ X∗, 2. StG(n) = ⋂ w∈X(n) StG(w)- the stabilizer of the n-th level, which is the intersection of the stabilizers of the words of the length n, 3. Pu - the stabilizer of an infinite word u ∈ Xω (the so called parabolic subgroup). Theorem 4. Let n ∈ N, w ∈ X(n) and u ∈ Xω. Then StG(w) = StG(n) ≃ Z k−1 and the parabolic subgroup Pu is a trivial group. Jo u rn al A lg eb ra D is cr et e M at h .110 The generalized dihedral groups. . . Proof. Let Ψ(g) = (r1, . . . , rk−1)ε. By proposition 5 we have g ∈ StG(w) if and only if g ∈ StG(n) if and only if ε = 0 and (ai 1 − ai k)r1 + (ai 2 − ai k)r2 + . . .+ (ai k−1 − ai k)rk−1 ≡ 0 (mod mi) for 0 < i < n. Thus in case n = 1 we have: g ∈ StG(w) if and only if g ∈ StG(n) if and only if ε = 0. Hence StG(w) = StG(1) ≃ Z k−1 in this case. Thus for n ≥ 1 the stabilizer StG(w) = StG(n) < StG(1) is isomorphic with a free abelian group of rank l ≤ k−1. On the other hand, if each ri is divisible by the product m1m2 . . .mn−1, then the element g with Ψ(g) = (r1, . . . , rk−1)0 is an element of the stabilizer StG(n). In consequence StG(n) contains Z k−1 as a subgroup. Thus StG(n) must be isomorphic with Z k−1. The triviality of any parabolic subgroup is a direct consequence of Lemma 1. Let w = x0x1 . . . xt ∈ X∗ be any word over the changing alphabet X, and let Orb(w) = {g(w) : g ∈ G} be its orbit. From Proposition 5 and Theorem 3 we see that the word v = y0y1 . . . yt ∈ X∗ belongs to Orb(w) if and only if there are integers r1, r2, . . . , rk−1, ε with ε ∈ {0, 1} such that yi = xi +mi (−1)xi−1εai k +mi (−1)xi−1 k−1∑ j=1 (ai j − ai k)rj (8) for i = 0, 1, . . . , t. Since, all mi are even and all ai are odd, this implies: yi − y0 ≡ xi − x0 (mod 2) for i = 0, 1, . . . t. In particular the action of the group G(A) on the set X∗ is not spherically transitive. By adding some additional assumption on mi, we may obtain a nice description of this action. Theorem 5. Let p1 < p2 < p3 < . . . be a sequence of odd primes such that pi > i(ai 1 + . . .+ai k) and let mi = 2pi for i = 1, 2 . . . . Then the words w = x0x1 . . . xt and v = y0y1 . . . yt belong to the same orbit if and only if yi − y0 ≡ xi − x0 (mod 2) (9) for i = 0, 1, . . . , t. In particular [G : StG(t+ 1)] = m0m1 . . .mt/2 t for t = 0, 1, 2, . . . . Jo u rn al A lg eb ra D is cr et e M at h .A. Woryna 111 Proof. The equalities pi > i(ai 1 + . . .+ ai k) assure that the condition (6) holds. Thus, it suffices to prove, that if w and v satisfy (9), then there is a sequence r1, r2, . . . , rk−1, ε with ε ∈ {0, 1} which satisfies (8). Let us denote: ε = (y0−x0)2 and zi = (yi−xi) · (−1)xi−1 −εai k, bi = (ai 1−a i k)/2 for i = 0, 1, . . . , t. Then all zi are even, and for i = 1, 2, . . . , t the numbers bi and pi are coprime. Using the Chinese Remainder Theorem we can find an integer r such that zi/2 ≡ rbi (mod pi) for i = 1, 2, . . . , t. Then the sequence r1, r2, . . . , rk−1, ε in which r1 = r and r2 = . . . = rk−1 = 0 satisfies (8). As a consequence we obtain [G : StG(t+ 1)] = [G : StG(w)] = \|Orb(w)\| = m0m1 . . .mt/2 t. References [1] L. Bartholdi, R. I. Grigorchuk, V. Nekrashevych. From fractal groups to fractal sets. Fractal in Graz 2001. Analysis-Dynamics-Geometry-Stochastics (P. Grabner and W. Woess, eds.), Trends in Mathematics, vol. 19, Birkhäuser, 2003, pp. 25–118. [2] R. I. Grigorchuk, V. V. Nekrashevich, V. I. Sushchanskii. Automata, Dynamical Systems and Groups. Proseedings of Steklov Institute of Mathematics, 231:128-203, 2000. [3] R. I. Grigorchuk, A. Їuk. Advanced Course on Automata Groups. Notes of the Course, Centre de Recerca Matematica Bellaterra (Spain), July 2004. [4] D. E. Joyce: http://www.clarku.edu/ djoyce/wallpaper [5] V. I. Sushchansky. Group of Automatic Permutations. Dopovidi NAN Ukrainy, N6:47-51, 1998 (in Ukrainian). [6] V. I. Sushchansky. Group of Finite Automatic Permutations. Dopovidi NAN Ukrainy, N2:48-52, 1999 (in Ukrainian). [7] A. Woryna. On the transformations given by the Mealy time varying automata. Zesz. Nauk. Pol. Њl., Seria: Automatyka 138(1581):201-215, 2003 (in Polish). [8] A. Woryna. On permutation groups generated by time-varying Mealy automata. Publ. Math. Debrecen, vol. 67/1-2 (2005), 115-130. Contact information Adam Woryna Institute of Mathematics, Silesian Univer- sity of Technology, 44-100 Gliwice E-Mail: Adam.Woryna@polsl.pl Received by the editors: 23.09.2006 and in final form 14.10.2008.

The generalized dihedral groups Dih(Zn) as groups generated by time-varying automata

Institution

Ähnliche Einträge