1% This file was created automatically from groups.msk. 2% DO NOT EDIT! 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 4\Chapter{Properties and operations with groups and semigroups} 5 6In this chapter we present the functionality applicable to groups and semigroups. 7 8%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 9\Section{Creation of groups and semigroups} 10 11\>AutomatonGroup( <string>[, <bind_vars>] ) O 12\>AutomatonGroup( <list>[, <names>, <bind_vars>] ) O 13\>AutomatonGroup( <automaton>[, <bind_vars>] ) O 14 15Creates the self-similar group generated by the finite automaton, described by <string> 16or <list>, or by the argument <automaton>. 17 18The argument <string> is a conventional notation of the form 19`name1=(name11,name12,...,name1d)perm1, name2=...' 20where each `name\*' is a name of a state or `1', and each `perm\*' is a 21permutation written in {\GAP} notation. Trivial permutations may be 22omitted. This function ignores whitespace, and states may be separated 23by commas or semicolons. 24 25The argument <list> is a list consisting of $n$ entries corresponding to $n$ states of an automaton. 26Each entry is of the form $[a_1,\.\.\.,a_d,p]$, 27where $d \geq 2$ is the size of the alphabet the group acts on, $a_i$ are `IsInt' in 28$\{1,\ldots,n\}$ and 29represent the sections of the corresponding state at all vertices of the first level of the tree; 30and $p$ from `SymmetricGroup(<d>)' describes the action of the corresponding state on the 31alphabet. 32 33The optional argument <names> must be a list of names of generators of the group, corresponding to the 34states of the automaton. 35These names are used to display elements of the resulting group. 36 37If the optional argument <bind_vars> is `false' the names of generators of the group are not assigned 38to the global variables. The default value is `true'. One can use 39`AssignGeneratorVariables' function to assign these names later, if they were not assigned 40when the group was created. 41 42\beginexample 43gap> AutomatonGroup("a=(a,b), b=(a, b)(1,2)"); 44< a, b > 45gap> AutomatonGroup("a=(b,a,1)(2,3), b=(1,a,b)(1,2,3)"); 46< a, b > 47gap> A := MealyAutomaton("a=(b,1)(1,2), b=(a,1)"); 48<automaton> 49gap> G := AutomatonGroup(A); 50< a, b > 51\endexample 52 53In the second form of this operation the definition of the first group 54looks like 55\beginexample 56gap> AutomatonGroup([ [ 1, 2, ()], [ 1, 2, (1,2) ] ], [ "a", "b" ]); 57< a, b > 58\endexample 59 60 61\>AutomatonSemigroup( <string>[, <bind_vars>] ) O 62\>AutomatonSemigroup( <list>[, <names>, <bind_vars>] ) O 63\>AutomatonSemigroup( <automaton>[, <bind_vars>] ) O 64 65Creates the semigroup generated by the finite automaton, described by <string> 66or <list>, or by the argument <automaton>. 67 68The argument <string> is a conventional notation of the form 69`name1=(name11,name12,...,name1d)trans1, name2=...' 70where each `name\*' is a name of a state or `1', and each `trans\*' is either a 71permutation written in {\GAP} notation, or a list defining a transformation 72of the alphabet via `Transformation(trans\*)'. Trivial permutations may be 73omitted. This function ignores whitespace, and states may be separated 74by commas or semicolons. 75 76The argument <list> is a list consisting of $n$ entries corresponding to $n$ states of the automaton. 77Each entry is of the form $[a_1,...,a_d,p]$, 78where $d \geq 2$ is the size of the alphabet the group acts on, $a_i$ are `IsInt' in 79$\{1,\ldots,n\}$ and 80represent the sections of the corresponding state at all vertices of the first level of the tree; 81and $p$ is a transformation of the alphabet describing the action of the corresponding 82state on the alphabet. 83 84The optional arguments <names> and <bind_vars> have the same meaning as in `AutomatonGroup' (see "AutomatonGroup"). 85 86\beginexample 87gap> AutomatonSemigroup("a=(a, b)[2,2], b=(a,b)(1,2)"); 88< a, b > 89gap> AutomatonSemigroup("a=(b,a,1)[1,1,3], b=(1,a,b)(1,2,3)"); 90< 1, a, b > 91gap> A := MealyAutomaton("f0=(f0,f0)(1,2), f1=(f1,f0)[2,2]"); 92<automaton> 93gap> G := AutomatonSemigroup(A); 94< f0, f1 > 95\endexample 96In the second form of this operation the definition of the second semigroup 97looks like 98\beginexample 99gap> AutomatonSemigroup([ [1,2,Transformation([2,2])], [ 1,2,(1,2)] ], ["a","b"]); 100< a, b > 101\endexample 102 103 104 105\>SelfSimilarGroup( <string>[, <bind_vars>] ) O 106\>SelfSimilarGroup( <list>[, <names>, <bind_vars>] ) O 107\>SelfSimilarGroup( <automaton>[, <bind_vars>] ) O 108 109Creates the self-similar group generated by the wreath recursion, described by <string> 110or <list>, or given by the argument <automaton>. 111 112The argument <string> is a conventional notation of the form 113`name1=(word11,word12,...,word1d)perm1, name2=...' 114where each `name\*' is a name of a state, `word\*' is an associative word 115over the alphabet consisting of all `name\*', and each `perm\*' is a 116permutation written in {\GAP} notation. Trivial permutations may be 117omitted. This function ignores whitespace, and states may be separated 118by commas or semicolons. 119 120The argument <list> is a list consisting of $n$ entries corresponding to $n$ generators of the group. 121Each entry is of the form $[a_1,\.\.\.,a_d,p]$, 122where $d \geq 2$ is the size of the alphabet the group acts on, $a_i$ are lists 123acceptable by `AssocWordByLetterRep' (e.g. if the names of generators are `x', `y' and `z', 124then `[1, 1, -2, -2, 1, 3]' will produce `x^2*y^-2*x*z') 125representing the sections of the corresponding generator at all vertices of the first level of the tree; 126and $p$ from `SymmetricGroup(<d>)' describes the action of the corresponding generator on the 127alphabet. 128 129The optional argument <names> must be a list of names of generators of the group. 130These names are used to display the elements of the resulting group. 131 132If the optional argument <bind_vars> is `false' the names of generators of the group are not assigned 133to the global variables. The default value is `true'. One can use 134`AssignGeneratorVariables' function to assign these names later, if they were not assigned 135when the group was created. 136 137\beginexample 138gap> SelfSimilarGroup("a=(a*b, b^-1), b=(1, b^2*a)(1,2)"); 139< a, b > 140gap> SelfSimilarGroup("a=(b,a,a^-1)(2,3), b=(1,a*b,b)(1,2,3)"); 141< a, b > 142gap> A := MealyAutomaton("f0=(f0,f0)(1,2),f1=(f1,f0)"); 143<automaton> 144gap> SelfSimilarGroup(A); 145< f0, f1 > 146\endexample 147In the second form of this operation the definition of the first group 148looks like 149\beginexample 150gap> SelfSimilarGroup([[ [1,2], [-2], ()], [ [], [2,2,1], (1,2) ]], ["a","b"]); 151< a, b > 152\endexample 153 154 155\>SelfSimilarSemigroup( <string>[, <bind_vars>] ) O 156\>SelfSimilarSemigroup( <list>[, <names>, <bind_vars>] ) O 157\>SelfSimilarSemigroup( <automaton>[, <bind_vars>] ) O 158 159Creates the semigroup generated by the wreath recursion, described by <string> 160or <list>, or given by the argument <automaton>. Note, that on the contrary to 161`AutomatonSemigroup' ("AutomatonSemigroup") in some cases the defined semigroup 162may not be self-similar, since the sections of generators may include inverses of 163generators or trivial homomorphisms, not included in the semigroup generated by the 164generators. If one needs to have self-similarity it is always possible to include the 165necessary sections in the generating set. 166 167The argument <string> is a conventional notation of the form 168`name1=(word11,word12,...,word1d)trans1, name2=...' 169where each `name\*' is a name of a state, `word\*' is an associative word 170over the alphabet consisting of all `name\*', and each `trans\*' is either a 171permutation written in {\GAP} notation, or a list defining a transformation 172of the alphabet via `Transformation(trans\*)'. Trivial permutations may be 173omitted. This function ignores whitespace, and states may be separated 174by commas or semicolons. 175 176The argument <list> is a list consisting of $n$ entries corresponding to $n$ generators of the semigroup. 177Each entry is of the form $[a_1,\.\.\.,a_d,p]$, 178where $d \geq 2$ is the size of the alphabet the semigroup acts on, $a_i$ are lists 179acceptable by `AssocWordByLetterRep' (e.g. if the names of generators are `x', `y' and `z', 180then `[1, 1, 2, 3]' will produce `x^2*y*z') 181representing the sections of the corresponding generator at all vertices of the first level of the tree; 182and $p$ is a transformation of the alphabet describing the action of the corresponding 183generator. 184 185The optional arguments <names> and <bind_vars> have the same meaning as in `SelfSimilarGroup' (see "SelfSimilarGroup"). 186 187\beginexample 188gap> SelfSimilarSemigroup("a=(a*b,b)[1,1], b=(a,b^2*a)(1,2)"); 189< a, b > 190gap> SelfSimilarSemigroup("a=(b,a,a^3)(2,3), b=(1,a*b,b^-1)(1,2,3)"); 191< a, b > 192gap> A := MealyAutomaton("f0=(f0,f0)(1,2), f1=(f1,f0)[2,2]"); 193<automaton> 194gap> SelfSimilarSemigroup(A); 195< f0, f1 > 196\endexample 197In the second form of this operation the definition of the first semigroup 198looks like 199\beginexample 200gap> SelfSimilarSemigroup([[[1,2], [2], ()], [[1], [2,2,1], (1,2)]],["a","b"]); 201< a, b > 202\endexample 203 204 205 206\>IsTreeAutomorphismGroup( <G> ) C 207 208The category of groups of tree automorphisms. 209 210 211\>IsAutomGroup( <G> ) C 212 213The category of groups generated by finite invertible initial automata 214(elements from category `IsAutom'). 215 216 217\>IsAutomatonGroup( <G> ) P 218 219is `true' if <G> is created using the command `AutomatonGroup' ("AutomatonGroup") 220or if the generators of <G> coincide with the generators of the corresponding family, and `false' otherwise. 221To test whether <G> is self-similar use `IsSelfSimilar' ("IsSelfSimilar") command. 222 223 224\>IsSelfSimGroup( <G> ) C 225 226The category of groups whose generators are defined using wreath recursion 227(elements from category `IsSelfSim'). These groups need not be self-similar. 228 229 230\>IsSelfSimilarGroup( <G> ) P 231 232is `true' if <G> is created using the command `SelfSimilarGroup' ("SelfSimilarGroup") 233or if the generators of <G> coincide with the generators of the corresponding family, and `false' otherwise. 234To test whether <G> is self-similar use `IsSelfSimilar' ("IsSelfSimilar") command. 235 236 237 238 239%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 240\Section{Basic properties of groups and semigroups} 241 242\>TopDegreeOfTree( <obj> ) A 243 244Returns the degree of the tree on the first level, i.e. the number of vertices 245adjacent to the root vertex. 246 247 248\>DegreeOfTree( <obj> ) A 249 250This is a synonym for TopDegreeOfTree~("TopDegreeOfTree") for the case of 251a regular tree. It is an error to call this method for an object which acts 252on a non-regular tree. 253 254 255\>IsFractal( <G> ) P 256 257Returns whether the group <G> is fractal (also called as <self-replicating>). In other 258words, if <G> acts transitively on the first level and for any vertex $v$ of the tree 259the projection of the stabilizer of $v$ in <G> 260on this vertex coincides with the whole group <G>. 261\beginexample 262gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 263< a, b, c, d > 264gap> IsFractal(Grigorchuk_Group); 265true 266\endexample 267 268 269\>IsFractalByWords( <G> ) P 270 271Computes the generators of stabilizers of vertices of the first level 272and their projections on these vertices. Returns `true' if the preimages of these 273projections in the free group under the canonical epimorphism generate the whole free 274group for each stabilizer, and the <G> acts transitively on the first level. 275This is sufficient but not necessary condition for <G> to be fractal. See also 276`IsFractal' ("IsFractal"). 277 278 279\>IsSphericallyTransitive( <G> )!{ for tree homomorphism (semi)group} P 280 281Returns whether the group <G> is spherically transitive (see~"Short math background"). 282\beginexample 283gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 284< a, b, c, d > 285gap> IsSphericallyTransitive(Grigorchuk_Group); 286true 287\endexample 288 289 290\>ContainsSphericallyTransitiveElement( <G> ) A 291 292For a self-similar group <G> acting on a binary tree returns `true' if <G> contains 293an element acting spherically transitively on the levels of the tree and `false' 294otherwise. See also `SphericallyTransitiveElement' ("SphericallyTransitiveElement"). 295\beginexample 296gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 297< u, v > 298gap> ContainsSphericallyTransitiveElement(Basilica); 299true 300gap> G := SelfSimilarGroup("a=(a^-1*b^-1,1)(1,2), b=(b^-1,a*b)"); 301< a, b > 302gap> ContainsSphericallyTransitiveElement(G); 303false 304\endexample 305 306 307\>IsTransitiveOnLevel( <G>, <lev> )!{ for tree homomorphism (semi)group} O 308 309Returns whether the group (semigroup) <G> acts transitively on level <lev>. 310 311\beginexample 312gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 313< a, b, c, d > 314gap> IsTransitiveOnLevel(Group([a,b]),3); 315true 316gap> IsTransitiveOnLevel(Group([a,b]),4); 317false 318\endexample 319 320 321\>IsSelfSimilar( <G> ) P 322 323Returns whether the group or semigroup <G> is self-similar (see "Short math background"). 324 325 326\>IsContracting( <G> ) A 327 328Given a self-similar group <G> tries to compute whether it is contracting or not. 329Only a partial method is implemented (since there is no general algorithm so far). 330First it tries to find the nucleus up to size 50 using `FindNucleus'(<G>,50) (see~"FindNucleus"), then 331it tries to find evidence that the group is noncontracting using 332`IsNoncontracting'(<G>,10,10) (see~"IsNoncontracting"). If the answer was not found one can try to use 333`FindNucleus' and `IsNoncontracting' with bigger parameters. Also one can use 334`SetInfoLevel(InfoAutomGrp, 3)' for more information to be displayed. 335 336\beginexample 337gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 338< u, v > 339gap> IsContracting(Basilica); 340true 341gap> IsContracting(AutomatonGroup("a=(c,a)(1,2), b=(c,b), c=(b,a)")); 342false 343\endexample 344 345 346\>IsNoncontracting( <G>[, <max_len>, <depth>] ) F 347 348Tries to show that the group <G> is not contracting. 349Enumerates the elements of the group <G> up to length <max_len> 350until it finds an element which has a section <g> of infinite order, such that 351`OrderUsingSections'(<g>, <depth>) (see "OrderUsingSections") 352returns `infinity' and such that <g> stabilizes some vertex and has itself as a 353section at this vertex. See also `IsContracting'~("IsContracting"). 354 355If <max_len> and <depth> are omitted they are assumed to be `infinity' and 10, respectively. 356 357If `InfoLevel' of `InfoAutomGrp' is greater than 358or equal to 3 (one can set it by `SetInfoLevel( InfoAutomGrp, 3)'), then the proof 359is printed. 360 361\beginexample 362gap> G := AutomatonGroup("a=(b,a)(1,2), b=(c,b), c=(c,a)"); 363< a, b, c > 364gap> IsNoncontracting(G); 365true 366gap> H := AutomatonGroup("a=(c,b)(1,2), b=(b,a), c=(a,a)"); 367< a, b, c > 368gap> SetInfoLevel(InfoAutomGrp, 3); 369gap> IsNoncontracting(H); 370#I There are 37 elements of length up to 2 371#I There are 187 elements of length up to 3 372#I a^2*c^-1*b^-1 is obtained from (a^2*c^-1*b^-1)^2 373 by taking sections and cyclic reductions at vertex [ 1, 1 ] 374#I a^2*c^-1*b^-1 has b*c*a^-2 as a section at vertex [ 2 ] 375true 376\endexample 377 378 379\>IsGeneratedByAutomatonOfPolynomialGrowth( <G> ) P 380 381For a group <G> generated by all states of a finite automaton (see "IsAutomatonGroup") 382determines whether this automaton has polynomial growth in terms of Sidki~\cite{Sid00}. 383 384See also operations `IsGeneratedByBoundedAutomaton' ("IsGeneratedByBoundedAutomaton") and 385`PolynomialDegreeOfGrowthOfUnderlyingAutomaton' ("PolynomialDegreeOfGrowthOfUnderlyingAutomaton"). 386\beginexample 387gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 388< u, v > 389gap> IsGeneratedByAutomatonOfPolynomialGrowth(Basilica); 390true 391gap> D := AutomatonGroup( "a=(a,b)(1,2), b=(b,a)" ); 392< a, b > 393gap> IsGeneratedByAutomatonOfPolynomialGrowth(D); 394false 395\endexample 396 397 398\>IsGeneratedByBoundedAutomaton( <G> ) P 399 400For a group <G> generated by all states of a finite automaton (see "IsAutomatonGroup") 401determines whether this automaton is bounded in terms of Sidki~\cite{Sid00}. 402 403See also `IsGeneratedByAutomatonOfPolynomialGrowth' ("IsGeneratedByAutomatonOfPolynomialGrowth") 404and `PolynomialDegreeOfGrowthOfUnderlyingAutomaton' ("PolynomialDegreeOfGrowthOfUnderlyingAutomaton"). 405\beginexample 406gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 407< u, v > 408gap> IsGeneratedByBoundedAutomaton(Basilica); 409true 410gap> C := AutomatonGroup("a=(a,b)(1,2), b=(b,c), c=(c,1)(1,2)"); 411< a, b, c > 412gap> IsGeneratedByBoundedAutomaton(C); 413false 414\endexample 415 416 417\>PolynomialDegreeOfGrowthOfUnderlyingAutomaton( <G> ) A 418 419For a group <G> generated by all states of a finite automaton (see "IsAutomatonGroup") 420of polynomial growth in terms of Sidki~\cite{Sid00} determines the degree of 421polynomial growth of this automaton. This degree is 0 if and only if the automaton is bounded. 422If the growth of automaton is exponential returns `fail'. 423 424See also `IsGeneratedByAutomatonOfPolynomialGrowth' ("IsGeneratedByAutomatonOfPolynomialGrowth") 425and `IsGeneratedByBoundedAutomaton' ("IsGeneratedByBoundedAutomaton"). 426\beginexample 427gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 428< u, v > 429gap> PolynomialDegreeOfGrowthOfUnderlyingAutomaton(Basilica); 4300 431gap> C := AutomatonGroup("a=(a,b)(1,2), b=(b,c), c=(c,1)(1,2)"); 432< a, b, c > 433gap> PolynomialDegreeOfGrowthOfUnderlyingAutomaton(C); 4342 435\endexample 436 437 438\>IsOfSubexponentialGrowth( <G>[, <len>, <depth>] ) O 439 440Tries to check whether the growth function of a self-similar group <G> is subexponential. 441The main part of the algorithm works as follows. It looks at all words of length up to <len> 442and if for some length $l$ for each word of this length $l$ the sum of the lengths of 443all its sections at level <depth> is less then $l$, returns `true'. The default values of 444<len> and <depth> are 10 and 6 respectively. Setting `SetInfoLevel(InfoAtomGrp, 3)' will make it 445print for each length the words that are not contracted. It also sometimes helps to use 446`AG_UseRewritingSystem' (see "AG_UseRewritingSystem"). 447 448\beginexample 449gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 450< a, b, c, d > 451gap> AG_UseRewritingSystem(Grigorchuk_Group); 452gap> IsOfSubexponentialGrowth(Grigorchuk_Group,10,6); 453true 454\endexample 455 456 457\>IsAmenable( <G> ) P 458 459In certain cases (for groups generated by bounded automata~\cite{BKNV05}, 460some virtually abelian groups or finite groups) returns `true' if <G> is 461amenable. 462 463\beginexample 464gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 465< a, b, c, d > 466gap> IsAmenable(Grigorchuk_Group); 467true 468\endexample 469 470 471\>UnderlyingAutomaton( <G> ) A 472 473For a group (or semigroup) <G> returns an automaton generating a 474self-similar group (or semigroup) containing <G>. 475\beginexample 476gap> GS := AutomatonSemigroup("x=(x,y)[1,1], y=(y,y)(1,2)"); 477< x, y > 478gap> A := UnderlyingAutomaton(GS); 479<automaton> 480gap> Display(A); 481a1 = (a1, a2)[ 1, 1 ], a2 = (a2, a2)[ 2, 1 ] 482\endexample 483For a subgroup of Basilica group we get the automaton generating Basilica group. 484\beginexample 485gap> H := Group([u*v^-1,v^2]); 486< u*v^-1, v^2 > 487gap> Display(UnderlyingAutomaton(H)); 488a1 = (a1, a1), a2 = (a3, a1)(1,2), a3 = (a2, a1) 489\endexample 490 491 492\>AutomatonList( <G> )!{ for tree homomorphism (semi)group} AM 493 494Returns an `AutomatonList' of `UnderlyingAutomaton'(<G>) (see "UnderlyingAutomaton"). 495\beginexample 496gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 497< u, v > 498gap> AutomatonList(Basilica); 499[ [ 2, 5, (1,2) ], [ 1, 5, () ], [ 5, 4, (1,2) ], [ 3, 5, () ], [ 5, 5, () ] ] 500\endexample 501 502 503\>RecurList( <G> )!{ for tree homomorphism (semi)group} AM 504 505Returns an internal representation of the wreath recursion of the 506self-similar group (semigroup) containing <G>. 507\beginexample 508gap> R := SelfSimilarGroup("a=(a^-1*b,b^-1*a)(1,2), b=(a^-1,b^-1)"); 509< a, b > 510gap> RecurList(R); 511[ [ [ -1, 2 ], [ -2, 1 ], (1,2) ], [ [ -1 ], [ -2 ], () ], 512 [ [ -1, 2 ], [ -2, 1 ], (1,2) ], [ [ 1 ], [ 2 ], () ] ] 513\endexample 514 515 516 517 518%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 519\Section{Operations with groups and semigroups} 520 521\>PermGroupOnLevel( <G>, <k> ) O 522 523Returns the group of permutations induced by the action of the group <G> at the <k>-th 524level. 525\beginexample 526gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 527< u, v > 528gap> PermGroupOnLevel(Basilica, 4); 529Group([ (1,11,3,9)(2,12,4,10)(5,13)(6,14)(7,15)(8,16), (1,6,2,5)(3,7)(4,8) ]) 530gap> H := PermGroupOnLevel(Group([u,v^2]),4); 531Group([ (1,11,3,9)(2,12,4,10)(5,13)(6,14)(7,15)(8,16), (1,2)(5,6) ]) 532gap> Size(H); 53364 534\endexample 535 536 537\>TransformationSemigroupOnLevel( <G>, <k> ) O 538 539Returns the semigroup of transformations induced by the action of the semigroup <G> at the <k>-th 540level. 541\beginexample 542gap> S := AutomatonSemigroup("y=(1,u)[1,1],u=(y,u)(1,2)"); 543< 1, y, u > 544gap> T := TransformationSemigroupOnLevel(S,3); 545<transformation monoid on 8 pts with 2 generators> 546gap> Size(T); 54711 548\endexample 549 550 551\>StabilizerOfLevel( <G>, <k> ) O 552 553Returns the stabilizer of the <k>-th level. 554\beginexample 555gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 556< u, v > 557gap> StabilizerOfLevel(Basilica, 2); 558< u^2, v^2, u*v^2*u^-1, v*u^2*v^-1, u*v*u^2*v^-1*u^-1, (v*u)^2*(v^-1*u^-1)^2, v*u*\ 559v^2*u^-1*v^-1, (u*v)^2*u*v^-1*u^-1*v^-1, (u*v)^2*v*u^-1*v^-1*u^-1 > 560\endexample 561 562 563\>StabilizerOfFirstLevel( <G> ) A 564 565Returns the stabilizer of the first level, see also~"StabilizerOfLevel". 566\beginexample 567gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 568< u, v > 569gap> StabilizerOfFirstLevel(Basilica); 570< v, u^2, u*v*u^-1 > 571\endexample 572 573 574\>StabilizerOfVertex( <G>, <v> ) O 575 576Returns the stabilizer of the vertex <v>. Here <v> can be a list representing a 577vertex, or a positive integer representing a vertex at the first level. 578\beginexample 579gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 580< u, v > 581gap> StabilizerOfVertex(Basilica, [1,2,1]); 582< u^2, u*v*u^-1, v^2, v*u*v*u^-1*v^-1, v*u^-1*v*u*v^-1, v*u^4*v^-1, v*u^2*v^2*u^-2\ 583*v^-1, (v*u^2)^2*v^-1*u^-2*v^-1, v*u*(u*v)^2*u^-1*v^-1*u^-2*v^-1 > 584\endexample 585 586 587\>FixesLevel( <obj>, <lev> ) O 588 589Returns whether <obj> fixes level <lev>, i.e. fixes every vertex at the level 590<lev>. 591 592 593\>FixesVertex( <obj>, <v> ) O 594 595Returns whether <obj> fixes the vertex <v>. The vertex <v> may be given as a list, or as 596a positive integer, in which case it denotes the <v>-th vertex at the first 597level. 598 599 600\>Projection( <G>, <v> ) O 601\>ProjectionNC( <G>, <v> ) O 602 603Returns the projection of the group <G> at the vertex <v>. The group <G> must fix the 604vertex <v>, otherwise `Error'() will be called. The operation `ProjectionNC' does the 605same thing, except it does not check whether <G> fixes the vertex <v>. 606\beginexample 607gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 608< u, v > 609gap> Projection(StabilizerOfVertex(Basilica, [1,2,1]), [1,2,1]); 610< u, v > 611\endexample 612 613 614\>ProjStab( <G>, <v> ) O 615 616Returns the projection of the stabilizer of <v> at itself. It is a shortcut for 617`Projection'(`StabilizerOfVertex'(G, v), v) (see "Projection", 618"StabilizerOfVertex"). 619\beginexample 620gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 621< u, v > 622gap> ProjStab(Basilica, [1,2,1]); 623< u, v > 624\endexample 625 626 627\>FindGroupRelations( <G>[, <max_len>, <max_num_rels>] ) O 628\>FindGroupRelations( <subs_words>[, <names>, <max_len>, <max_num_rels>] ) O 629 630Finds group relations between the generators of the group <G> 631or in the group generated by <subs_words>. Stops after investigating all words 632of length up to <max_len> elements or when it finds <max_num_rels> 633relations. The optional argument <names> is a list of names of generators of the same length 634as <subs_words>. If this argument is given the relations are given in terms of these names. 635Otherwise they are given in terms of the elements of the group generated by <subs_words>. 636If <max_len> or <max_num_rels> are not specified, they are assumed to be `infinity'. 637Note that if the rewring system (see "AG_UseRewritingSystem") for group <G> is used, then this operation 638returns relations not contained in the rewriting system rules (see "AG_RewritingSystemRules"). 639This operation can be applied to any group, not only to a group generated by automata. 640\beginexample 641gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 642< u, v > 643gap> FindGroupRelations(Basilica, 6); 644v*u*v*u^-1*v^-1*u*v^-1*u^-1 645v*u^2*v^-1*u^2*v*u^-2*v^-1*u^-2 646v^2*u*v^2*u^-1*v^-2*u*v^-2*u^-1 647[ v*u*v*u^-1*v^-1*u*v^-1*u^-1, v*u^2*v^-1*u^2*v*u^-2*v^-1*u^-2, 648 v^2*u*v^2*u^-1*v^-2*u*v^-2*u^-1 ] 649gap> FindGroupRelations([u*v^-1, v*u], ["x", "y"], 5); 650y*x^2*y*x^-1*y^-2*x^-1 651[ y*x^2*y*x^-1*y^-2*x^-1 ] 652gap> FindGroupRelations([u*v^-1, v*u], 5); 653u^-2*v*u^-2*v^-1*u^2*v*u^2*v^-1 654[ u^-2*v*u^-2*v^-1*u^2*v*u^2*v^-1 ] 655gap> FindGroupRelations([(1,2)(3,4), (1,2,3)], ["x", "y"]); 656x^2 657y^-3 658(y^-1*x)^3 659[ x^2, y^-3, (y^-1*x)^3 ] 660\endexample 661 662 663\>FindSemigroupRelations( <G>[, <max_len>, <max_num_rels>] ) O 664\>FindSemigroupRelations( <subs_words>[, <names>, <max_len>, <max_num_rels>] ) O 665 666Finds semigroup relations between the generators of the group or semigroup <G>, 667or in the semigroup generated by <subs_words>. The arguments have the same meaning 668as in `FindGroupRelations'~("FindGroupRelations"). It returns a list of pairs of equal words. 669In order to make the list of relations shorter 670it also tries to remove relations that can 671be derived from the known ones. Note, that by default the trivial automorphism is 672not included in every semigroup. So if one needs to find relations of the form 673$w=1$ one has to define <G> as a monoid or to include the trivial automorphism 674into <subs_words> (for instance, as `One(g)' for any element `g' acting on the same 675tree). 676This operation can be applied for any semigroup, not only for a semigroup generated by automata. 677\beginexample 678gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 679< u, v > 680gap> FindSemigroupRelations([u*v^-1, v*u], ["x", "y"], 6); 681y*x^2*y=x*y^2*x 682y*x^3*y^2=x^2*y^3*x 683y^2*x^3*y=x*y^3*x^2 684[ [ y*x^2*y, x*y^2*x ], [ y*x^3*y^2, x^2*y^3*x ], [ y^2*x^3*y, x*y^3*x^2 ] ] 685gap> FindSemigroupRelations([u*v^-1, v*u],6); 686v*u^2*v^-1*u^2 = u^2*v*u^2*v^-1 687v*u*(u*v^-1)^2*u^2*v*u = u*v^-1*u*(u*v)^2*u^2*v^-1 688(v*u)^2*(u*v^-1)^2*u^2 = u*(u*v)^2*u*(u*v^-1)^2 689[ [ v*u^2*v^-1*u^2, u^2*v*u^2*v^-1 ], 690 [ v*u*(u*v^-1)^2*u^2*v*u, u*v^-1*u*(u*v)^2*u^2*v^-1 ], 691 [ (v*u)^2*(u*v^-1)^2*u^2, u*(u*v)^2*u*(u*v^-1)^2 ] ] 692gap> x := Transformation([1,1,2]);; 693gap> y := Transformation([2,2,3]);; 694gap> FindSemigroupRelations([x,y],["x","y"]); 695y*x=x 696y^2=y 697x^3=x^2 698x^2*y=x*y 699[ [ y*x, x ], [ y^2, y ], [ x^3, x^2 ], [ x^2*y, x*y ] ] 700\endexample 701 702 703 704 705\>Iterator( <G>[, <max_len>] ) M 706 707Provides a possibility to loop over elements of a group (semigroup, monoid) 708generated by automata. If <max_len> is given, it stops after enumerating all elements 709of length up to <max_len>. 710\beginexample 711gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 712< a, b, c, d > 713gap> iter := Iterator(Grigorchuk_Group, 5); 714<iterator> 715gap> l:=[];; 716gap> for g in iter do 717> if Order(g)=16 then Add(l,g); fi; 718> od; 719gap> l; 720[ b*a, a*b, d*a*c, c*a*d, d*a*c*a, d*a*b*a, c*a*d*a, b*a*d*a, a*d*a*c, 721 a*d*a*b, a*c*a*d, a*b*a*d, c*a*c*a*b, c*a*b*a*b, b*a*c*a*c, b*a*b*a*c, 722 a*d*a*c*a, a*c*a*d*a ] 723\endexample 724 725\>FindElement( <G>, <func>, <val>, <max_len> ) O 726\>FindElements( <G>, <func>, <val>, <max_len> ) O 727 728The first function enumerates elements of the group (semigroup, monoid) <G> until it finds 729an element $g$ of length at most <max_len>, for which <func>($g$)=<val>. Returns $g$ if 730such an element was found and `fail' otherwise. 731 732The second function enumerates elements of the group (semigroup, monoid) of length at most <max_len> 733and returns the list of elements $g$, for which <func>($g$)=<val>. 734 735These functions are based on `Iterator' operation (see "Iterator"), so can be applied in 736more general settings whenever \GAP\ knows how to solve word problem in the group. 737The following example illustrates how to find an element of order 16 in 738Grigorchuk group and the list of all such elements of length at most 5. 739\beginexample 740gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 741< a, b, c, d > 742gap> FindElement(Grigorchuk_Group, Order, 16, 5); 743a*b 744gap> FindElements(Grigorchuk_Group,Order,16,5); 745[ a*b, b*a, c*a*d, d*a*c, a*b*a*d, a*c*a*d, a*d*a*b, a*d*a*c, b*a*d*a, c*a*d*a, 746 d*a*b*a, d*a*c*a, a*c*a*d*a, a*d*a*c*a, (b*a)^2*c, b*(a*c)^2, c*(a*b)^2, 747 (c*a)^2*b ] 748\endexample 749 750 751\>FindElementOfInfiniteOrder( <G>, <max_len>, <depth> ) O 752\>FindElementsOfInfiniteOrder( <G>, <max_len>, <depth> ) O 753 754The first function enumerates elements of the group <G> up to length <max_len> 755until it finds an element $g$ of infinite order, such that 756`OrderUsingSections'($g$,<depth>) (see "OrderUsingSections") is `infinity'. 757In other words all sections of every element up to depth <depth> are 758investigated. In case if the element belongs to the group generated by bounded 759automaton (see "IsGeneratedByBoundedAutomaton") one can set <depth> to be `infinity'. 760 761The second function returns the list of all such elements up to length <max_len>. 762 763\beginexample 764gap> G := AutomatonGroup("a=(1,1)(1,2), b=(a,c), c=(b,1)"); 765< a, b, c > 766gap> FindElementOfInfiniteOrder(G, 5, 10); 767a*b*c 768\endexample 769 770 771\>SphericallyTransitiveElement( <G> ) A 772 773For a self-similar group <G> acting on a binary tree returns 774an element of <G> acting spherically transitively on the levels of the tree if 775such an element exists and `fail' 776otherwise. See also `ContainsSphericallyTransitiveElement' 777("ContainsSphericallyTransitiveElement"). 778\beginexample 779gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 780< u, v > 781gap> SphericallyTransitiveElement(Basilica); 782u*v 783gap> G := SelfSimilarGroup("a=(a^-1*b^-1,1)(1,2), b=(b^-1,a*b)"); 784< a, b > 785gap> SphericallyTransitiveElement(G); 786fail 787\endexample 788 789 790\>Growth( <G>, <max_len> ) O 791 792Returns a list of the first values of the growth function of a group 793(semigroup, monoid) <G>. 794If <G> is a monoid it computes the growth function at $\{0,1,\ldots,<max_len>\}$, 795and for a semigroup without identity at $\{1,\ldots,<max_len>\}$. 796\beginexample 797gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 798< a, b, c, d > 799gap> Growth(Grigorchuk_Group, 7); 800There are 11 elements of length up to 2 801There are 23 elements of length up to 3 802There are 40 elements of length up to 4 803There are 68 elements of length up to 5 804There are 108 elements of length up to 6 805There are 176 elements of length up to 7 806[ 1, 5, 11, 23, 40, 68, 108, 176 ] 807gap> H := AutomatonSemigroup("a=(a,b)[1,1], b=(b,a)(1,2)"); 808< a, b > 809gap> Growth(H,6); 810[ 2, 6, 14, 30, 62, 126 ] 811\endexample 812 813 814\>ListOfElements( <G>, <max_len> ) O 815 816Returns the list of all different elements of a group (semigroup, monoid) 817<G> up to length <max_len>. 818\beginexample 819gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 820< a, b, c, d > 821gap> ListOfElements(Grigorchuk_Group, 3); 822[ 1, a, b, c, d, a*b, a*c, a*d, b*a, c*a, d*a, a*b*a, a*c*a, a*d*a, b*a*b, 823 b*a*c, b*a*d, c*a*b, c*a*c, c*a*d, d*a*b, d*a*c, d*a*d ] 824\endexample 825 826 827\>FindNucleus( <G>[, <max_nucl>, <print_info>] ) O 828 829Given a self-similar group <G> it tries to find its nucleus. If <G> 830is not contracting it will loop forever. When it finds the nucleus it returns 831the triple [`GroupNucleus'(<G>), `GeneratingSetWithNucleus'(<G>), 832`GeneratingSetWithNucleusAutom'(<G>)] (see "GroupNucleus", "GeneratingSetWithNucleus", 833"GeneratingSetWithNucleusAutom"). 834 835If <max_nucl> is given it stops after finding <max_nucl> elements that need to be in 836the nucleus and returns `fail' if the nucleus was not found. 837 838An optional argument <print_info> is a boolean telling whether to print results of 839intermediate computations. The default value is `true'. 840 841Use `IsNoncontracting'~(see "IsNoncontracting") to try to show that <G> is 842noncontracting. 843 844\beginexample 845gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 846< u, v > 847gap> FindNucleus(Basilica); 848Trying generating set with 5 elements 849Elements added:[ u^-1*v, v^-1*u ] 850Trying generating set with 7 elements 851[ [ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ], 852 [ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ], <automaton> ] 853\endexample 854 855 856\>LevelOfFaithfulAction( <G> ) A 857\>LevelOfFaithfulAction( <G>, <max_lev> ) A 858 859For a given finite self-similar group <G> determines the smallest level of 860the tree, where <G> acts faithfully, i.e. the stabilizer of this level in <G> 861is trivial. The idea here is that for a self-similar group all nontrivial level 862stabilizers are different. If <max_lev> is given it finds only first <max_lev> 863quotients by stabilizers and if all of them have different size it returns `fail'. 864If <G> is infinite and <max_lev> is not specified it will loop forever. 865 866See also `IsomorphismPermGroup' ("IsomorphismPermGroup"). 867\beginexample 868gap> H := SelfSimilarGroup("a=(a,a)(1,2), b=(a,a), c=(b,a)(1,2)"); 869< a, b, c > 870gap> LevelOfFaithfulAction(H); 8713 872gap> Size(H); 87316 874gap> Adding_Machine := AutomatonGroup("a=(1,a)(1,2)"); 875< a > 876gap> LevelOfFaithfulAction(Adding_Machine, 10); 877fail 878\endexample 879 880 881\>IsomorphismPermGroup( <G> ) O 882\>IsomorphismPermGroup( <G>, <max_lev> ) O 883 884For a given finite group <G> generated by initial automata or by elements defined by 885wreath recursion 886computes an isomorphism from <G> into a finite permutational group. 887If <G> is not known to be self-similar (see "IsSelfSimilar") the isomorphism is based on the 888regular representation, which works generally much slower. If <G> is self-similar 889there is a level of the tree (see "LevelOfFaithfulAction"), where <G> acts faithfully. 890The corresponding representation is returned in this case. If <max_lev> is given 891it finds only the first <max_lev> quotients by stabilizers and if all of them have 892different size it returns `fail'. 893If <G> is infinite and <max_lev> is not specified it will loop forever. 894 895For example, consider a subgroup $\langle a, b\rangle$ of Grigorchuk group. 896\beginexample 897gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 898< a, b, c, d > 899gap> f := IsomorphismPermGroup(Group(a, b)); 900MappingByFunction( < a, b >, Group( 901[ (1,2)(3,5)(4,6)(7,9)(8,10)(11,13)(12,14)(15,17)(16,18)(19,21)(20,22)(23, 902 25)(24,26)(27,29)(28,30)(31,32), (1,3)(2,4)(5,7)(6,8)(9,11)(10,12)(13, 903 15)(14,16)(17,19)(18,20)(21,23)(22,24)(25,27)(26,28)(29,31)(30,32) 904 ]), function( g ) ... end, function( b ) ... end ) 905gap> Size(Image(f)); 90632 907gap> H := SelfSimilarGroup("a=(a*b,1)(1,2), b=(1,b*a^-1)(1,2), c=(b, a*b)"); 908< a, b, c > 909gap> f1 := IsomorphismPermGroup(H); 910MappingByFunction( < a, b, c >, Group([ (1,3)(2,4), (1,3)(2,4), (1,2) 911 ]), function( g ) ... end, function( b ) ... end ) 912gap> Size(Image(f1)); 9138 914gap> PreImagesRepresentative(f1, (1,3,2,4)); 915a*c 916gap> (a*c)^f1; 917(1,3,2,4) 918\endexample 919 920 921\>Random( <G> ) O 922 923Returns a random element of a group (semigroup) <G>. The operation is based 924on the generator of random elements in free groups and semigroups. 925 926\beginexample 927gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 928< u, v > 929gap> Random( Basilica ); 930v*u^-3 931\endexample 932 933 934\>MarkovOperator( <G>, <lev>, <weights> ) O 935 936Computes the matrix of the Markov operator related to the (semi)group <G> on the <lev>-th level 937of the tree. If <G> is a group generated by $g_1,g_2,\ldots,g_n$, then the Markov operator 938is defined as $(`PermOnLevelAsMatrix'(g_1)+\cdots+`PermOnLevelAsMatrix'(g_n)+ 939`PermOnLevelAsMatrix'(g_1^{-1})+\cdots+`PermOnLevelAsMatrix'(g_n^{-1}))/(2*n)$. 940If <S> is a semigroup generated by $s_1,s_2,\ldots,s_n$, then the Markov operator 941is defined similarly with `PermOnLevelAsMatrix' being replaced with `TransformationOnLevelAsMatrix'. 942If the list of <weights> is given, uses its entries as coefficients of operators correspondings to 943the generators of a group or semigroup. In the case of a group, the length of <weights> must be twice 944as big as the number of generators of <G>. The list <weights> may consist either of numbers or of strings 945representing the names of indeterminates. 946See also 947`PermOnLevelAsMatrix' ("PermOnLevelAsMatrix") and `TransformationOnLevelAsMatrix' ("TransformationOnLevelAsMatrix"). 948\beginexample 949gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)"); 950< p, q > 951gap> MarkovOperator(L, 3); 952[ [ 0, 0, 1/4, 1/4, 0, 1/4, 0, 1/4 ], [ 0, 0, 1/4, 1/4, 1/4, 0, 1/4, 0 ], 953 [ 1/4, 1/4, 0, 0, 1/4, 0, 1/4, 0 ], [ 1/4, 1/4, 0, 0, 0, 1/4, 0, 1/4 ], 954 [ 0, 1/4, 1/4, 0, 0, 1/2, 0, 0 ], [ 1/4, 0, 0, 1/4, 1/2, 0, 0, 0 ], 955 [ 0, 1/4, 1/4, 0, 0, 0, 1/2, 0 ], [ 1/4, 0, 0, 1/4, 0, 0, 0, 1/2 ] ] 956gap> MarkovOperator(L,3,["a","b","c","d"]); 957[ [ 0, 0, d, b, 0, c, 0, a ], [ 0, 0, b, d, c, 0, a, 0 ], 958 [ b, d, 0, 0, a, 0, c, 0 ], [ d, b, 0, 0, 0, a, 0, c ], 959 [ 0, a, c, 0, 0, b+d, 0, 0 ], [ a, 0, 0, c, b+d, 0, 0, 0 ], 960 [ 0, c, a, 0, 0, 0, b+d, 0 ], [ c, 0, 0, a, 0, 0, 0, b+d ] ] 961\endexample 962In the case of semigroups we have: 963\beginexample 964gap> S := AutomatonSemigroup("c=(c,d)[1,1],d=(c,c)(1,2)"); 965< c, d > 966gap> MarkovOperator(S,3,["w1","w2"]); 967[ [ w1, 0, 0, 0, w2, 0, 0, 0 ], [ w1, 0, 0, 0, w2, 0, 0, 0 ], 968 [ 0, w1, 0, 0, 0, w2, 0, 0 ], [ w1, 0, 0, 0, w2, 0, 0, 0 ], 969 [ w2, 0, w1, 0, 0, 0, 0, 0 ], [ w2, 0, w1, 0, 0, 0, 0, 0 ], 970 [ w1, w2, 0, 0, 0, 0, 0, 0 ], [ w1+w2, 0, 0, 0, 0, 0, 0, 0 ] ] 971gap> MarkovOperator(S,3,[1/3,2/3]); 972[ [ 1/3, 0, 0, 0, 2/3, 0, 0, 0 ], [ 1/3, 0, 0, 0, 2/3, 0, 0, 0 ], 973 [ 0, 1/3, 0, 0, 0, 2/3, 0, 0 ], [ 1/3, 0, 0, 0, 2/3, 0, 0, 0 ], 974 [ 2/3, 0, 1/3, 0, 0, 0, 0, 0 ], [ 2/3, 0, 1/3, 0, 0, 0, 0, 0 ], 975 [ 1/3, 2/3, 0, 0, 0, 0, 0, 0 ], [ 1, 0, 0, 0, 0, 0, 0, 0 ] ] 976\endexample 977 978 979\>MihailovaSystem( <G> ) AM 980 981In the case when <G> is an automaton fractal group acting on a binary 982tree, computes the generating set for the first level stabilizer in G 983such that the sections of these generators at the first level, 984viewed as elements of $F_r\times F_r$, are in Mihailova normal form. 985See~\cite{GSESS} for details. 986 987\beginexample 988gap> G := AutomatonGroup("a=(b,c)(1,2),b=(a,c),c=(a,a)"); 989< a, b, c > 990gap> M := MihailovaSystem(G); 991[ c^-1*b, c^-1*b^-1*c*a^-1*b*c*b^-1*a, a^-1*b*c*b^-1*a, a*c^-1*b^-1*a*c, 992 c^-1*a^-1*b*c*a ] 993gap> for g in M do 994> Print(g,"=",Decompose(g),"\n"); 995> od; 996c^-1*b=(1, a^-1*c) 997c^-1*b^-1*c*a^-1*b*c*b^-1*a=(1, a^-1*c^-1*a*b^-1*a*b) 998a^-1*b*c*b^-1*a=(a, b^-1*a*b) 999a*c^-1*b^-1*a*c=(b, c*a^-2*b*a) 1000c^-1*a^-1*b*c*a=(c, a^-1*b^-1*a^2*b) 1001\endexample 1002 1003 1004 1005 1006 1007\>AbelImage( <obj> ) A 1008 1009Returns image of <obj> in the canonical projection onto the abelianization of 1010the full group of tree automorphisms, represented as a subgroup of the additive 1011group of rational functions. 1012 1013 1014\>DiagonalPower( <fam>[, <k>] ) O 1015 1016For a given automaton group <G> acting on alphabet $X$ and corresponding family 1017<fam> of automata one can consider the action of $<G>^<k>$ on $X^<k>$ defined by 1018$(x_1,x_2,\ldots, x_k)^{(g_1,g_2,\ldots,g_k)}=(x_1^{g_1},x_2^{g_2},\ldots,x_k^{g_k})$. 1019This function constructs a self-similar group, which encodes this action. If 1020<k> is not given it is assumed to be $2$. 1021\beginexample 1022gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 1023< u, v > 1024gap> S := DiagonalPower(UnderlyingAutomFamily(Basilica)); 1025< uu, uv, u1, vu, vv, v1, 1u, 1v > 1026gap> Decompose(uu); 1027(vv, v1, 1v, 1)(1,4)(2,3) 1028\endexample 1029 1030 1031\>MultAutomAlphabet( <fam> ) O 1032 1033 1034 1035\>UnderlyingAutomFamily( <G> ) A 1036 1037Returns the family to which the elements of <G> belong. 1038 1039 1040 1041%Declaration{UnderlyingFreeGroup} 1042%Declaration{UnderlyingFreeSubgroup} 1043%Declaration{UnderlyingFreeGenerators} 1044%Declaration{TrivialSubgroup} 1045 1046 1047%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1048\Section{Self-similar groups and semigroups defined by the wreath recursion} 1049 1050\>IsFiniteState( <G> )!{ for tree homomorphism (semi)group} P 1051 1052For a group or semigroup of homomorphisms of the tree defined using a 1053wreath recursion, returns `true' if all 1054generators can be represented as finite automata (have finitely many different 1055sections). 1056It will never stop if the free reduction of words is not sufficient to establish 1057the finite-state property or if the group is not finite-state. 1058In case <G> is a finite-state group it automatically computes the attributes 1059`UnderlyingAutomatonGroup'(<G>) ("UnderlyingAutomatonGroup"), 1060`IsomorphicAutomGroup'(<G>) ("IsomorphicAutomGroup") and 1061`MonomorphismToAutomatonGroup'(<G>) ("MonomorphismToAutomatonGroup"). 1062For a finite-state semigroup it computes the corresponding attributes 1063`UnderlyingAutomatonSemigroup'(<G>) ("UnderlyingAutomatonSemigroup"), 1064`IsomorphicAutomSemigroup'(<G>) ("IsomorphicAutomSemigroup") and 1065`MonomorphismToAutomatonSemigroup'(<G>) ("MonomorphismToAutomatonSemigroup"). 1066\beginexample 1067gap> W := SelfSimilarGroup("x=(x^-1,y)(1,2), y=(z^-1,1)(1,2), z=(1,x*y)"); 1068< x, y, z > 1069gap> IsFiniteState(W); 1070true 1071gap> Size(GeneratorsOfGroup(UnderlyingAutomatonGroup(W))); 107250 1073\endexample 1074 1075\>IsomorphicAutomGroup( <G> ) AM 1076 1077In case <G> is finite-state tries to compute a group generated by automata, isomorphic to <G>, 1078which is a subgroup of `UnderlyingAutomatonGroup'(<G>) (see "UnderlyingAutomatonGroup"). 1079The natural isomorphism between <G> and `IsomorphicAutomGroup'(<G>) is stored in the 1080attribute `MonomorphismToAutomatonGroup'(<G>) ("MonomorphismToAutomatonGroup"). 1081In some cases it may be useful to check if <G> is finite. 1082\beginexample 1083gap> R := SelfSimilarGroup("a=(a^-1*b,b^-1*a)(1,2), b=(a^-1,b^-1)"); 1084< a, b > 1085gap> UR := UnderlyingAutomatonGroup(R); 1086< a1, a2, a4, a5 > 1087gap> IR := IsomorphicAutomGroup(R); 1088< a1, a5 > 1089gap> hom := MonomorphismToAutomatonGroup(R); 1090MappingByFunction( < a, b >, < a1, a5 >, function( a ) ... end, function( b ) \ 1091... end ) 1092gap> (a*b)^hom; 1093a1*a5 1094gap> PreImagesRepresentative(hom, last); 1095a*b 1096gap> List(GeneratorsOfGroup(UR), x -> PreImagesRepresentative(hom, x)); 1097[ a, a^-1*b, b^-1*a, b ] 1098\endexample 1099 1100All these operations work also for the subgroups of groups generated by `SelfSimilarGroup'. 1101("SelfSimilarGroup"). 1102\beginexample 1103gap> T := Group([b*a, a*b]); 1104< b*a, a*b > 1105gap> IT := IsomorphicAutomGroup(T); 1106< a1, a4 > 1107\endexample 1108Note, that different groups have different `UnderlyingAutomGroup' attributes. For example, 1109the generator `a1' of group `IT' above is different from the generator `a1' of group `IR'. 1110 1111 1112\>IsomorphicAutomSemigroup( <G> ) AM 1113 1114In case <G> is finite-state returns a semigroup generated by automata, isomorphic to <G>, 1115which is a subsemigroup of `UnderlyingAutomatonSemigroup'(<G>) (see "UnderlyingAutomatonSemigroup"). 1116The natural isomorphism between <G> and `IsomorphicAutomSemigroup'(<G>) is stored in the 1117attribute `MonomorphismToAutomatonSemigroup'(<G>) ("MonomorphismToAutomatonSemigroup"). 1118\beginexample 1119gap> R := SelfSimilarSemigroup("a=(1,1)[1,1], b=(a*c,1)(1,2), c=(1,a*b)"); 1120< a, b, c > 1121gap> UR := UnderlyingAutomatonSemigroup(R); 1122< 1, a1, a3, a5, a6 > 1123gap> IR := IsomorphicAutomSemigroup(R); 1124< a1, a3, a5 > 1125gap> hom := MonomorphismToAutomatonSemigroup(R); 1126MappingByFunction( < a, b, c >, < a1, a3, a5 >, function( a ) ... end, functio\ 1127n( b ) ... end ) 1128gap> (a*b)^hom; 1129a1*a3 1130gap> PreImagesRepresentative(hom, last); 1131a*b 1132gap> List(GeneratorsOfSemigroup(UR), x -> PreImagesRepresentative(hom, x)); 1133[ 1, a, b, c, a*b ] 1134\endexample 1135 1136All these operations work also for the subsemigroups of semigroups generated by 1137`SelfSimilarSemigroup' ("SelfSimilarSemigroup"). 1138\beginexample 1139gap> T := Semigroup([a*b, b^2]); 1140< a*b, b^2 > 1141gap> IT := IsomorphicAutomSemigroup(T); 1142< a1, a4 > 1143\endexample 1144Note, that different semigroups have different `UnderlyingAutomSemigroup' attributes. For example, 1145the generator `a1' of semigroup `IT' above is different from the generator `a1' of semigroup `IR'. 1146 1147 1148 1149\>UnderlyingAutomatonGroup( <G> ) AM 1150 1151In case <G> is finite-state returns a self-similar closure of <G> as a group 1152generated by automaton. 1153The natural monomorphism from <G> and `UnderlyingAutomatonGroup'(<G>) is stored in the 1154attribute `MonomorphismToAutomatonGroup'(<G>) ("MonomorphismToAutomatonGroup"). If 1155<G> is created by `SelfSimilarGroup' (see "SelfSimilarGroup"), then the self-similar closure 1156of <G> coincides with <G>, so one can use `MonomorphismToAutomatonGroup'(<G>) to 1157get preimages of elements of `UnderlyingAutomatonGroup'(<G>) in <G>. See the example for 1158`IsomorphicAutomGroup' ("IsomorphicAutomGroup"). 1159 1160 1161\>UnderlyingAutomatonSemigroup( <G> ) AM 1162 1163In case <G> is finite-state returns a self-similar closure of <G> as a semigroup 1164generated by automaton. 1165The natural monomorphism from <G> and `UnderlyingAutomatonSemigroup'(<G>) is stored in the 1166attribute `MonomorphismToAutomatonSemigroup'(<G>) ("MonomorphismToAutomatonSemigroup"). If 1167<G> is created by `SelfSimilarSemigroup' (see "SelfSimilarSemigroup"), then the self-similar closure 1168of <G> coincides with <G>, so one can use `MonomorphismToAutomatonSemigroup'(<G>) to 1169get preimages of elements of `UnderlyingAutomatonSemigroup'(<G>) in <G>. See the example for 1170`IsomorphicAutomSemigroup' ("IsomorphicAutomSemigroup"). 1171 1172 1173 1174\>MonomorphismToAutomatonGroup( <G> ) AM 1175 1176In case <G> is finite-state returns a monomorphism from <G> into `UnderlyingAutomatonGroup'(<G>) 1177(see "UnderlyingAutomatonGroup"). If <G> is created by `SelfSimilarGroup' (see "SelfSimilarGroup"), 1178then one can use `MonomorphismToAutomatonGroup'(<G>) to 1179get preimages of elements of `UnderlyingAutomatonGroup'(<G>) in <G>. See the example for 1180`IsomorphicAutomGroup' ("IsomorphicAutomGroup"). 1181 1182 1183\>MonomorphismToAutomatonSemigroup( <G> ) AM 1184 1185In case <G> is finite-state returns a monomorphism from <G> into `UnderlyingAutomatonSemigroup'(<G>) 1186(see "UnderlyingAutomatonSemigroup"). If <G> is created by `SelfSimilarSemigroup' 1187(see "SelfSimilarSemigroup"), 1188then one can use `MonomorphismToAutomatonSemigroup'(<G>) to 1189get preimages of elements of `UnderlyingAutomatonSemigroup'(<G>) in <G>. See the example for 1190`IsomorphicAutomSemigroup' ("IsomorphicAutomSemigroup"). 1191 1192 1193 1194 1195 1196%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1197\Section{Contracting groups} 1198 1199\>GroupNucleus( <G> ) AM 1200 1201Tries to compute the <nucleus> (see the definition in "Short math background") of 1202a self-similar group <G>. Note that this set need not contain the original 1203generators of <G>. It uses `FindNucleus' (see "FindNucleus") 1204operation and behaves accordingly: if the group is not contracting it will loop 1205forever. See also `GeneratingSetWithNucleus' ("GeneratingSetWithNucleus"). 1206 1207\beginexample 1208gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 1209< u, v > 1210gap> GroupNucleus(Basilica); 1211[ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ] 1212\endexample 1213 1214 1215\>GeneratingSetWithNucleus( <G> ) AM 1216 1217Tries to compute the generating set of a self-similar group <G> that includes 1218the original generators and the <nucleus> (see "Short math background") of <G>. 1219It uses `FindNucleus' operation 1220and behaves accordingly: if the group is not contracting 1221it will loop forever (modulo memory constraints, of course). 1222See also `GroupNucleus' ("GroupNucleus"). 1223 1224\beginexample 1225gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 1226< u, v > 1227gap> GeneratingSetWithNucleus(Basilica); 1228[ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ] 1229\endexample 1230 1231 1232\>GeneratingSetWithNucleusAutom( <G> ) AM 1233 1234Computes the automaton of the generating set that includes the nucleus of a contracting group <G>. 1235See also `GeneratingSetWithNucleus' ("GeneratingSetWithNucleus"). 1236\beginexample 1237gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 1238< u, v > 1239gap> B_autom := GeneratingSetWithNucleusAutom(Basilica); 1240<automaton> 1241gap> Display(B_autom); 1242a1 = (a1, a1), a2 = (a3, a1)(1,2), a3 = (a2, a1), a4 = (a1, a5) 1243(1,2), a5 = (a4, a1), a6 = (a1, a7)(1,2), a7 = (a6, a1)(1,2) 1244\endexample 1245 1246 1247\>ContractingLevel( <G> ) AM 1248 1249Given a contracting group <G> with generating set $N$ that includes the nucleus, stored in 1250`GeneratingSetWithNucleus'(<G>) (see "GeneratingSetWithNucleus") computes the 1251minimal level $n$, such that for every vertex $v$ of the $n$-th 1252level and all $g, h \in N$ the section $gh|_v \in N$. 1253 1254In the case if it is not known whether <G> is contracting, it first tries to compute 1255the nucleus. If <G> happens to be noncontracting, it will loop forever. One can 1256also use `IsNoncontracting' (see "IsNoncontracting") or `FindNucleus' (see 1257"FindNucleus") directly. 1258\beginexample 1259gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 1260< a, b, c, d > 1261gap> ContractingLevel(Grigorchuk_Group); 12621 1263gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 1264< u, v > 1265gap> ContractingLevel(Basilica); 12662 1267\endexample 1268 1269 1270\>ContractingTable( <G> ) AM 1271 1272Given a contracting group <G> with a generating set $N$ of size $k$ that includes the nucleus, stored in 1273`GeneratingSetWithNucleus'(<G>)~(see "GeneratingSetWithNucleus") 1274computes the $k\times k$ table, whose 1275[i][j]-th entry contains decomposition of $N$[i]$N$[j] on 1276the `ContractingLevel'(<G>) level~(see "ContractingLevel"). By construction the sections of 1277$N$[i]$N$[j] on this level belong to $N$. This table is used in the 1278algorithm solving the word problem in polynomial time. 1279 1280In the case if it is not known whether <G> is contracting it first tries to compute 1281the nucleus. If <G> happens to be noncontracting, it will loop forever. One can 1282also use `IsNoncontracting' (see "IsNoncontracting") or `FindNucleus' (see 1283"FindNucleus") directly. 1284\beginexample 1285gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 1286< a, b, c, d > 1287gap> ContractingTable(Grigorchuk_Group); 1288[ [ (1, 1), (1, 1)(1,2), (a, c), (a, d), (1, b) ], 1289 [ (1, 1)(1,2), (1, 1), (c, a)(1,2), (d, a)(1,2), (b, 1)(1,2) ], 1290 [ (a, c), (a, c)(1,2), (1, 1), (1, b), (a, d) ], 1291 [ (a, d), (a, d)(1,2), (1, b), (1, 1), (a, c) ], 1292 [ (1, b), (1, b)(1,2), (a, d), (a, c), (1, 1) ] ] 1293\endexample 1294 1295 1296\>UseContraction( <G> ) O 1297\>DoNotUseContraction( <G> ) O 1298 1299For a contracting automaton group <G> these two operations determine whether to 1300use the algorithm 1301of polynomial complexity solving the word problem in the group. By default 1302it is set to <true> as soon as the nucleus of the group was computed. Sometimes 1303when the nucleus is very big, the standard algorithm of exponential complexity 1304is faster for short words, but this heavily depends on the group. Therefore 1305the decision on which algorithm to use is left to the user. To use the 1306exponential algorithm one can use the second operation `DoNotUseContraction'(<G>). 1307 1308Note also then in order to use the polynomial time algorithm the `ContractingTable(G)' 1309(see "ContractingTable") has to be computed first, which takes some time when the 1310nucleus is big. This attribute is computed automatically when the word problem is solved 1311for the first time. This sometimes causes some delay. 1312 1313Below we provide an example which shows that both methods can be of use. 1314\testexamplefalse 1315\beginexample 1316gap> G := AutomatonGroup("a=(b,b)(1,2), b=(c,a), c=(a,a)"); 1317< a, b, c > 1318gap> IsContracting(G); 1319true 1320gap> Size(GroupNucleus(G)); 132141 1322gap> ContractingLevel(G); 13236 1324gap> ContractingTable(G);; time; 13254719 1326gap> v := a*b*a*b^2*c*b*c*b^-1*a^-1*b^-1*a^-1;; 1327gap> w := b*c*a*b*a*b*c^-1*b^-2*a^-1*b^-1*a^-1;; 1328gap> UseContraction(G);; 1329gap> IsOne(Comm(v,w)); time; 1330true 1331110 1332gap> FindGroupRelations(G, 9);; time; 1333a^2 1334b^2 1335c^2 1336(b*a*b*c*a)^2 1337(b*(c*a)^2)^2 1338(b*c*b*a*(b*c)^2*a)^2 1339(b*(c*b*c*a)^2)^2 134011578 1341gap> DoNotUseContraction(G);; 1342gap> IsOne(Comm(v,w)); time; 1343true 1344922 1345gap> FindGroupRelations(G, 9);; time; 1346a^2 1347b^2 1348c^2 1349(b*a*b*c*a)^2 1350(b*(c*a)^2)^2 1351(b*c*b*a*(b*c)^2*a)^2 1352(b*(c*b*c*a)^2)^2 135323719 1354\endexample 1355 1356 1357 1358 1359%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1360\Section{Rewriting Systems} 1361 1362It is possible to use basic relators in all computations performed 1363in a self-similar group. 1364 1365\>AG_UseRewritingSystem( <G>[, <setting>] ) O 1366 1367Tells whether computations in the group <G> should use a rewriting system. 1368<setting> defaults to `true' if omitted. This function initially only 1369tries to find involutions in <G>. See `AG_AddRelators' ("AG_AddRelators") 1370and `AG_UpdateRewritingSystem' ("AG_UpdateRewritingSystem") for the ways 1371to add more relators. 1372 1373\beginexample 1374gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 1375< a, b, c, d > 1376gap> Comm(a*b, b*a); 1377b^-1*a^-2*b^-1*a*b^2*a 1378gap> AG_UseRewritingSystem(G); 1379gap> Comm(a*b, b*a); 13801 1381gap> AG_UseRewritingSystem(G, false); 1382gap> Comm(a*b, b*a); 1383b^-1*a^-2*b^-1*a*b^2*a 1384\endexample 1385 1386 1387\>AG_AddRelators( <G>, <relators> ) O 1388 1389Adds relators from the list <relators> to the rewriting system used in 1390<G>. 1391 1392\beginexample 1393gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 1394< a, b, c, d > 1395gap> AG_UseRewritingSystem(G); 1396gap> b*c; 1397b*c 1398gap> AG_AddRelators(G, [b*c*d]); 1399gap> b*c; 1400d 1401\endexample 1402 1403In some cases it's hard to find relations directly from the wreath 1404recursion of a self-similar group (at least, there is no general agorithm). 1405This function provides possibility to add relators manually. After that 1406one can use `AG_UpdateRewritingSystem' (see "AG_UpdateRewritingSystem") 1407and `AG_UseRewritingSystem' (see "AG_UseRewritingSystem") to use these 1408relators in computations. In the example below we consider a finite group 1409$H$, in which $a=b$, but the standard algorithm is unable to solve the 1410word problem. There are two solutions for that. One can manually add a 1411relator, or one can ask if the group is finite (which does not stop 1412generally if the group is infinite). 1413\beginexample 1414gap> H := SelfSimilarGroup("a=(a*b,1)(1,2), b=(1,b*a^-1)(1,2), c=(b, a*b)"); 1415< a, b, c > 1416gap> AG_AddRelators(H, [a*b^-1]); 1417gap> AG_UseRewritingSystem(H); 1418gap> Order(a*c); 14194 1420\endexample 1421 1422 1423\>AG_UpdateRewritingSystem( <G>, <maxlen> ) O 1424 1425Tries to find new relators of length up to <maxlen> and adds them into 1426the rewriting system. It can also be used after introducing new relators 1427via `AG_AddRelators' (see "AG_AddRelators"). 1428 1429\beginexample 1430gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 1431< a, b, c, d > 1432gap> AG_UseRewritingSystem(G); 1433gap> b*c; 1434b*c 1435gap> AG_UpdateRewritingSystem(G, 3); 1436gap> b*c; 1437d 1438\endexample 1439 1440 1441\>AG_RewritingSystemRules( <G> ) O 1442 1443Returns the list of rules used in the rewriting system of group <G>. 1444\beginexample 1445gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 1446< a, b, c, d > 1447gap> AG_UseRewritingSystem(G); 1448gap> AG_RewritingSystemRules(G); 1449[ [ a^2, <identity ...> ], [ b^2, <identity ...> ], [ c^2, <identity ...> ], 1450 [ d^2, <identity ...> ], [ A, a ], [ B, b ], [ C, c ], [ D, d ] ] 1451\endexample 1452 1453 1454 1455 1456 1457%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1458