% This file was created automatically from groups.msk. % DO NOT EDIT! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Chapter{Properties and operations with groups and semigroups} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Creation of groups and semigroups} \>AutomatonGroup( <string>[, <bind_vars>] ) O \>AutomatonGroup( <list>[, <names>, <bind_vars>] ) O \>AutomatonGroup( <automaton>[, <bind_vars>] ) O Creates the self-similar group generated by the finite automaton, described by <string> or <list>, or by the argument <automaton>. The argument <string> is a conventional notation of the form `name1=(name11,name12,...,name1d)perm1, name2=...' where each `name\*' is a name of a state or `1', and each `perm\*' is a permutation written in {\GAP} notation. Trivial permutations may be omitted. This function ignores whitespace, and states may be separated by commas or semicolons. The argument <list> is a list consisting of $n$ entries corresponding to $n$ states of an automaton. Each entry is of the form $[a_1,\.\.\.,a_d,p]$, where $d \geq 2$ is the size of the alphabet the group acts on, $a_i$ are `IsInt' in $\{1,\ldots,n\}$ and represent the sections of the corresponding state at all vertices of the first level of the tree; and $p$ from `SymmetricGroup(<d>)' describes the action of the corresponding state on the alphabet. The optional argument <names> must be a list of names of generators of the group, corresponding to the states of the automaton. These names are used to display elements of the resulting group. If the optional argument <bind_vars> is `false' the names of generators of the group are not assigned to the global variables. The default value is `true'. One can use `AssignGeneratorVariables' function to assign these names later, if they were not assigned when the group was created. \beginexample gap> AutomatonGroup("a=(a,b), b=(a, b)(1,2)"); < a, b > gap> AutomatonGroup("a=(b,a,1)(2,3), b=(1,a,b)(1,2,3)"); < a, b > gap> A := MealyAutomaton("a=(b,1)(1,2), b=(a,1)"); <automaton> gap> G := AutomatonGroup(A); < a, b > \endexample In the second form of this operation the definition of the first group looks like \beginexample gap> AutomatonGroup([ [ 1, 2, ()], [ 1, 2, (1,2) ] ], [ "a", "b" ]); < a, b > \endexample The <bind_vars> argument works as follows \beginexample gap> AutomatonGroup("t = (1, t)(1,2)", false);; gap> t; Variable: 't' must have a value gap> AutomatonGroup("t = (1, t)(1,2)", true);; gap> t; t \endexample \>AutomatonSemigroup( <string>[, <bind_vars>] ) O \>AutomatonSemigroup( <list>[, <names>, <bind_vars>] ) O \>AutomatonSemigroup( <automaton>[, <bind_vars>] ) O Creates the semigroup generated by the finite automaton, described by <string> or <list>, or by the argument <automaton>. The argument <string> is a conventional notation of the form `name1=(name11,name12,...,name1d)trans1, name2=...' where each `name\*' is a name of a state or `1', and each `trans\*' is either a permutation written in {\GAP} notation, or a list defining a transformation of the alphabet via `Transformation(trans\*)'. Trivial permutations may be omitted. This function ignores whitespace, and states may be separated by commas or semicolons. The argument <list> is a list consisting of $n$ entries corresponding to $n$ states of the automaton. Each entry is of the form $[a_1,...,a_d,p]$, where $d \geq 2$ is the size of the alphabet the group acts on, $a_i$ are `IsInt' in $\{1,\ldots,n\}$ and represent the sections of the corresponding state at all vertices of the first level of the tree; and $p$ is a transformation of the alphabet describing the action of the corresponding state on the alphabet. The optional arguments <names> and <bind_vars> have the same meaning as in `AutomatonGroup' (see "AutomatonGroup"). \beginexample gap> AutomatonSemigroup("a=(a, b)[2,2], b=(a,b)(1,2)"); < a, b > gap> AutomatonSemigroup("a=(b,a,1)[1,1,3], b=(1,a,b)(1,2,3)"); < 1, a, b > gap> A := MealyAutomaton("f0=(f0,f0)(1,2), f1=(f1,f0)[2,2]"); <automaton> gap> G := AutomatonSemigroup(A); < f0, f1 > \endexample In the second form of this operation the definition of the second semigroup looks like \beginexample gap> AutomatonSemigroup([ [1,2,Transformation([2,2])], [ 1,2,(1,2)] ], ["a","b"]); < a, b > \endexample \>SelfSimilarGroup( <string>[, <bind_vars>] ) O \>SelfSimilarGroup( <list>[, <names>, <bind_vars>] ) O \>SelfSimilarGroup( <automaton>[, <bind_vars>] ) O Creates the self-similar group generated by the wreath recursion, described by <string> or <list>, or given by the argument <automaton>. The argument <string> is a conventional notation of the form `name1=(word11,word12,...,word1d)perm1, name2=...' where each `name\*' is a name of a state, `word\*' is an associative word over the alphabet consisting of all `name\*', and each `perm\*' is a permutation written in {\GAP} notation. Trivial permutations may be omitted. This function ignores whitespace, and states may be separated by commas or semicolons. The argument <list> is a list consisting of $n$ entries corresponding to $n$ generators of the group. Each entry is of the form $[a_1,\.\.\.,a_d,p]$, where $d \geq 2$ is the size of the alphabet the group acts on, $a_i$ are lists acceptable by `AssocWordByLetterRep' (e.g. if the names of generators are `x', `y' and `z', then `[1, 1, -2, -2, 1, 3]' will produce `x^2*y^-2*x*z') representing the sections of the corresponding generator at all vertices of the first level of the tree; and $p$ from `SymmetricGroup(<d>)' describes the action of the corresponding generator on the alphabet. The optional argument <names> must be a list of names of generators of the group. These names are used to display the elements of the resulting group. If the optional argument <bind_vars> is `false' the names of generators of the group are not assigned to the global variables. The default value is `true'. One can use `AssignGeneratorVariables' function to assign these names later, if they were not assigned when the group was created. \beginexample gap> SelfSimilarGroup("a=(a*b, b^-1), b=(1, b^2*a)(1,2)"); < a, b > gap> SelfSimilarGroup("a=(b,a,a^-1)(2,3), b=(1,a*b,b)(1,2,3)"); < a, b > gap> A := MealyAutomaton("f0=(f0,f0)(1,2),f1=(f1,f0)"); <automaton> gap> SelfSimilarGroup(A); < f0, f1 > \endexample In the second form of this operation the definition of the first group looks like \beginexample gap> SelfSimilarGroup([[ [1,2], [-2], ()], [ [], [2,2,1], (1,2) ]], ["a","b"]); < a, b > \endexample The <bind_vars> argument works as follows \beginexample gap> SelfSimilarGroup("t = (t^2, t)(1,2)", false);; gap> t; Variable: 't' must have a value gap> SelfSimilarGroup("t = (t^2, t)(1,2)", true);; gap> t; t \endexample \>SelfSimilarSemigroup( <string>[, <bind_vars>] ) O \>SelfSimilarSemigroup( <list>[, <names>, <bind_vars>] ) O \>SelfSimilarSemigroup( <automaton>[, <bind_vars>] ) O Creates the semigroup generated by the wreath recursion, described by <string> or <list>, or given by the argument <automaton>. Note, that on the contrary to `AutomatonSemigroup' ("AutomatonSemigroup") in some cases the defined semigroup may not be self-similar, since the sections of generators may include inverses of generators or trivial homomorphisms, not included in the semigroup generated by the generators. If one needs to have self-similarity it is always possible to include the necessary sections in the generating set. The argument <string> is a conventional notation of the form `name1=(word11,word12,...,word1d)trans1, name2=...' where each `name\*' is a name of a state, `word\*' is an associative word over the alphabet consisting of all `name\*', and each `trans\*' is either a permutation written in {\GAP} notation, or a list defining a transformation of the alphabet via `Transformation(trans\*)'. Trivial permutations may be omitted. This function ignores whitespace, and states may be separated by commas or semicolons. The argument <list> is a list consisting of $n$ entries corresponding to $n$ generators of the semigroup. Each entry is of the form $[a_1,\.\.\.,a_d,p]$, where $d \geq 2$ is the size of the alphabet the semigroup acts on, $a_i$ are lists acceptable by `AssocWordByLetterRep' (e.g. if the names of generators are `x', `y' and `z', then `[1, 1, 2, 3]' will produce `x^2*y*z') representing the sections of the corresponding generator at all vertices of the first level of the tree; and $p$ is a transformation of the alphabet describing the action of the corresponding generator. The optional arguments <names> and <bind_vars> have the same meaning as in `SelfSimilarGroup' (see "SelfSimilarGroup"). \beginexample gap> SelfSimilarSemigroup("a=(a*b,b)[1,1], b=(a,b^2*a)(1,2)"); < a, b > gap> SelfSimilarSemigroup("a=(b,a,a^3)(2,3), b=(1,a*b,b^-1)(1,2,3)"); < a, b > gap> A := MealyAutomaton("f0=(f0,f0)(1,2), f1=(f1,f0)[2,2]"); <automaton> gap> SelfSimilarSemigroup(A); < f0, f1 > \endexample In the second form of this operation the definition of the first semigroup looks like \beginexample gap> SelfSimilarSemigroup([[[1,2], [2], ()], [[1], [2,2,1], (1,2)]],["a","b"]); < a, b > \endexample The <bind_vars> argument works as follows \beginexample gap> SelfSimilarSemigroup("t = (t^2, t)(1,2)", false);; gap> t; Variable: 't' must have a value gap> SelfSimilarSemigroup("t = (t^2, t)(1,2)", true);; gap> t; t \endexample \>IsTreeAutomorphismGroup( <G> ) C The category of groups of tree automorphisms. \>IsAutomGroup( <G> ) C The category of groups generated by finite invertible initial automata (elements from category `IsAutom'). \>IsAutomatonGroup( <G> ) P is `true' if <G> is created using the command `AutomatonGroup' ("AutomatonGroup") or if the generators of <G> coincide with the generators of the corresponding family, and `false' otherwise. To test whether <G> is self-similar use `IsSelfSimilar' ("IsSelfSimilar") command. \>IsSelfSimGroup( <G> ) C The category of groups whose generators are defined using wreath recursion (elements from category `IsSelfSim'). These groups need not be self-similar. \>IsSelfSimilarGroup( <G> ) P is `true' if <G> is created using the command `SelfSimilarGroup' ("SelfSimilarGroup") or if the generators of <G> coincide with the generators of the corresponding family, and `false' otherwise. To test whether <G> is self-similar use `IsSelfSimilar' ("IsSelfSimilar") command. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Basic properties of groups and semigroups} \>TopDegreeOfTree( <obj> ) A Returns the degree of the tree on the first level, i.e. the number of vertices adjacent to the root vertex. \>DegreeOfTree( <obj> ) A This is a synonym for TopDegreeOfTree~("TopDegreeOfTree") for the case of a regular tree. It is an error to call this method for an object which acts on a non-regular tree. \>IsFractal( <G> ) P Returns whether the group <G> is fractal (also called as <self-replicating>). In other words, if <G> acts transitively on the first level and for any vertex $v$ of the tree the projection of the stabilizer of $v$ in <G> on this vertex coincides with the whole group <G>. \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> IsFractal(GrigorchukGroup); true \endexample \>IsFractalByWords( <G> ) P Computes the generators of stabilizers of vertices of the first level and their projections on these vertices. Returns `true' if the preimages of these projections in the free group under the canonical epimorphism generate the whole free group for each stabilizer, and the <G> acts transitively on the first level. This is sufficient but not necessary condition for <G> to be fractal. See also `IsFractal' ("IsFractal"). \>`IsSphericallyTransitive( <G> )'{IsSphericallyTransitive![treehomsg]}@{`IsSphericallyTransitive'!`[treehomsg]'} P Returns whether the group <G> is spherically transitive (see~"Short math background"). \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> IsSphericallyTransitive(GrigorchukGroup); true \endexample \>ContainsSphericallyTransitiveElement( <G> ) A For a self-similar group <G> acting on a binary tree returns `true' if <G> contains an element acting spherically transitively on the levels of the tree and `false' otherwise. See also `SphericallyTransitiveElement' ("SphericallyTransitiveElement"). \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> ContainsSphericallyTransitiveElement(Basilica); true gap> G := SelfSimilarGroup("a=(a^-1*b^-1,1)(1,2), b=(b^-1,a*b)"); < a, b > gap> ContainsSphericallyTransitiveElement(G); false \endexample \>`IsTransitiveOnLevel( <G>, <lev> )'{IsTransitiveOnLevel![treehomsg]}@{`IsTransitiveOnLevel'!`[treehomsg]'} O Returns whether the group (semigroup) <G> acts transitively on level <lev>. \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> IsTransitiveOnLevel(Group([a,b]),3); true gap> IsTransitiveOnLevel(Group([a,b]),4); false \endexample \>IsSelfSimilar( <G> ) P Returns whether the group or semigroup <G> is self-similar (see "Short math background"). \>IsContracting( <G> ) A Given a self-similar group <G> tries to compute whether it is contracting or not. Only a partial method is implemented (since there is no general algorithm so far). First it tries to find the nucleus up to size 50 using `FindNucleus'(<G>,50) (see~"FindNucleus"), then it tries to find evidence that the group is noncontracting using `IsNoncontracting'(<G>,10,10) (see~"IsNoncontracting"). If the answer was not found one can try to use `FindNucleus' and `IsNoncontracting' with bigger parameters. Also one can use `SetInfoLevel(InfoAutomGrp, 3)' for more information to be displayed. \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> IsContracting(Basilica); true gap> IsContracting(AutomatonGroup("a=(c,a)(1,2), b=(c,b), c=(b,a)")); false \endexample \>IsNoncontracting( <G>[, <max_len>, <depth>] ) F Tries to show that the group <G> is not contracting. Enumerates the elements of the group <G> up to length <max_len> until it finds an element which has a section <g> of infinite order, such that `OrderUsingSections'(<g>, <depth>) (see "OrderUsingSections") returns `infinity' and such that <g> stabilizes some vertex and has itself as a section at this vertex. See also `IsContracting'~("IsContracting"). If <max_len> and <depth> are omitted they are assumed to be `infinity' and 10, respectively. If `InfoLevel' of `InfoAutomGrp' is greater than or equal to 3 (one can set it by `SetInfoLevel( InfoAutomGrp, 3)'), then the proof is printed. \beginexample gap> G := AutomatonGroup("a=(b,a)(1,2), b=(c,b), c=(c,a)"); < a, b, c > gap> IsNoncontracting(G); true gap> H := AutomatonGroup("a=(c,b)(1,2), b=(b,a), c=(a,a)"); < a, b, c > gap> SetInfoLevel(InfoAutomGrp, 3); gap> IsNoncontracting(H); #I There are 37 elements of length up to 2 #I There are 187 elements of length up to 3 #I a^2*c^-1*b^-1 is obtained from (a^2*c^-1*b^-1)^2 by taking sections and cyclic reductions at vertex [ 1, 1 ] #I a^2*c^-1*b^-1 has b*c*a^-2 as a section at vertex [ 2 ] true \endexample \>IsGeneratedByAutomatonOfPolynomialGrowth( <G> ) P For a group <G> generated by all states of a finite automaton (see "IsAutomatonGroup") determines whether this automaton has polynomial growth in terms of Sidki~\cite{Sid00}. See also operations `IsGeneratedByBoundedAutomaton' ("IsGeneratedByBoundedAutomaton") and `PolynomialDegreeOfGrowthOfUnderlyingAutomaton' ("PolynomialDegreeOfGrowthOfUnderlyingAutomaton"). \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> IsGeneratedByAutomatonOfPolynomialGrowth(Basilica); true gap> D := AutomatonGroup( "a=(a,b)(1,2), b=(b,a)" ); < a, b > gap> IsGeneratedByAutomatonOfPolynomialGrowth(D); false \endexample \>IsGeneratedByBoundedAutomaton( <G> ) P For a group <G> generated by all states of a finite automaton (see "IsAutomatonGroup") determines whether this automaton is bounded in terms of Sidki~\cite{Sid00}. See also `IsGeneratedByAutomatonOfPolynomialGrowth' ("IsGeneratedByAutomatonOfPolynomialGrowth") and `PolynomialDegreeOfGrowthOfUnderlyingAutomaton' ("PolynomialDegreeOfGrowthOfUnderlyingAutomaton"). \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> IsGeneratedByBoundedAutomaton(Basilica); true gap> C := AutomatonGroup("a=(a,b)(1,2), b=(b,c), c=(c,1)(1,2)"); < a, b, c > gap> IsGeneratedByBoundedAutomaton(C); false \endexample \>PolynomialDegreeOfGrowthOfUnderlyingAutomaton( <G> ) A For a group <G> generated by all states of a finite automaton (see "IsAutomatonGroup") of polynomial growth in terms of Sidki~\cite{Sid00} determines the degree of polynomial growth of this automaton. This degree is 0 if and only if the automaton is bounded. If the growth of automaton is exponential returns `fail'. See also `IsGeneratedByAutomatonOfPolynomialGrowth' ("IsGeneratedByAutomatonOfPolynomialGrowth") and `IsGeneratedByBoundedAutomaton' ("IsGeneratedByBoundedAutomaton"). \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> PolynomialDegreeOfGrowthOfUnderlyingAutomaton(Basilica); 0 gap> C := AutomatonGroup("a=(a,b)(1,2), b=(b,c), c=(c,1)(1,2)"); < a, b, c > gap> PolynomialDegreeOfGrowthOfUnderlyingAutomaton(C); 2 \endexample \>IsOfSubexponentialGrowth( <G>[, <len>, <depth>] ) O Tries to check whether the growth function of a self-similar group <G> is subexponential. The main part of the algorithm works as follows. It looks at all words of length up to <len> and if for some length $l$ for each word of this length $l$ the sum of the lengths of all its sections at level <depth> is less then $l$, returns `true'. The default values of <len> and <depth> are 10 and 6 respectively. Setting `SetInfoLevel(InfoAtomGrp, 3)' will make it print for each length the words that are not contracted. It also sometimes helps to use `AG_UseRewritingSystem' (see "AG_UseRewritingSystem"). \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> UseAGRewritingSystem(GrigorchukGroup); true gap> IsOfSubexponentialGrowth(GrigorchukGroup,10,6); true \endexample \>IsAmenable( <G> ) P In certain cases (for groups generated by bounded automata~\cite{BKNV05}, some virtually abelian groups or finite groups) returns `true' if <G> is amenable. \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> IsAmenable(GrigorchukGroup); true \endexample \>UnderlyingAutomaton( <G> ) A For a group (or semigroup) <G> returns an automaton generating a self-similar group (or semigroup) containing <G>. \beginexample gap> GS := AutomatonSemigroup("x=(x,y)[1,1], y=(y,y)(1,2)"); < x, y > gap> A := UnderlyingAutomaton(GS); <automaton> gap> Print(A); a1 = (a1, a2)[ 1, 1 ], a2 = (a2, a2)[ 2, 1 ] \endexample For a subgroup of Basilica group we get the automaton generating Basilica group. \beginexample gap> H := Group([u*v^-1,v^2]); < u*v^-1, v^2 > gap> Print(UnderlyingAutomaton(H)); a1 = (a1, a1), a2 = (a3, a1)(1,2), a3 = (a2, a1) \endexample \>`AutomatonList( <G> )'{AutomatonList![automsg]}@{`AutomatonList'!`[automsg]'} AM Returns an `AutomatonList' of `UnderlyingAutomaton'(<G>) (see "UnderlyingAutomaton"). \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> AutomatonList(Basilica); [ [ 2, 5, (1,2) ], [ 1, 5, () ], [ 5, 4, (1,2) ], [ 3, 5, () ], [ 5, 5, () ] ] \endexample \>`RecurList( <G> )'{RecurList![selfsimsg]}@{`RecurList'!`[selfsimsg]'} AM Returns an internal representation of the wreath recursion of the self-similar group (semigroup) containing <G>. \beginexample gap> R := SelfSimilarGroup("a=(a^-1*b,b^-1*a)(1,2), b=(a^-1,b^-1)"); < a, b > gap> RecurList(R); [ [ [ -1, 2 ], [ -2, 1 ], (1,2) ], [ [ -1 ], [ -2 ], () ], [ [ -1, 2 ], [ -2, 1 ], (1,2) ], [ [ 1 ], [ 2 ], () ] ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations with groups and semigroups} \>PermGroupOnLevel( <G>, <k> ) O Returns the group of permutations induced by the action of the group <G> at the <k>-th level. \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> PermGroupOnLevel(Basilica, 4); Group([ (1,11,3,9)(2,12,4,10)(5,13)(6,14)(7,15)(8,16), (1,6,2,5)(3,7)(4,8) ]) gap> H := PermGroupOnLevel(Group([u,v^2]),4); Group([ (1,11,3,9)(2,12,4,10)(5,13)(6,14)(7,15)(8,16), (1,2)(5,6) ]) gap> Size(H); 64 \endexample \>TransformationSemigroupOnLevel( <G>, <k> ) O Returns the semigroup of transformations induced by the action of the semigroup <G> at the <k>-th level. \beginexample gap> S:=AutomatonSemigroup("y=(1,u)[1,1],u=(y,u)(1,2)"); < 1, y, u > gap> T:=TransformationSemigroupOnLevel(S,3); <semigroup with 3 generators> gap> Size(T); 11 \endexample \>StabilizerOfLevel( <G>, <k> ) O Returns the stabilizer of the <k>-th level. \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> StabilizerOfLevel(Basilica, 2); < u*v^2*u^-1, u*v*u*v^2*u^-1*v^-1*u^-1, v^2, v*u^2*v^-1, u*v*u^2*v^-1*u^-1, u^ 2, v*u*v*u*v^-1*u^-1*v^-1*u^-1 > \endexample \>StabilizerOfFirstLevel( <G> ) A Returns the stabilizer of the first level, see also~"StabilizerOfLevel". \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> StabilizerOfFirstLevel(Basilica); < u^2, u*v*u^-1, v > \endexample \>StabilizerOfVertex( <G>, <v> ) O Returns the stabilizer of the vertex <v>. Here <v> can be a list representing a vertex, or a positive integer representing a vertex at the first level. \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> StabilizerOfVertex(Basilica, [1,2,1]); < v*u^4*v^-1, v*u^2*v^2*u^-2*v^-1, v^2, u^2, v*u^2*v*u^2*v^-1*u^-2*v^ -1, u*v*u^-1, v*u^-1*v*u*v^-1, v*u^2*v*u*v*u^-1*v^-1*u^-2*v^-1 > \endexample \>FixesLevel( <obj>, <lev> ) O Returns whether <obj> fixes level <lev>, i.e. fixes every vertex at the level <lev>. \>FixesVertex( <obj>, <v> ) O Returns whether <obj> fixes the vertex <v>. The vertex <v> may be given as a list, or as a positive integer, in which case it denotes the <v>-th vertex at the first level. \>Projection( <G>, <v> ) O \>ProjectionNC( <G>, <v> ) O Returns the projection of the group <G> at the vertex <v>. The group <G> must fix the vertex <v>, otherwise `Error'() will be called. The operation `ProjectionNC' does the same thing, except it does not check whether <G> fixes the vertex <v>. \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> Projection(StabilizerOfVertex(Basilica, [1,2,1]), [1,2,1]); < v, u > \endexample \>ProjStab( <G>, <v> ) O Returns the projection of the stabilizer of <v> at itself. It is a shortcut for `Projection'(`StabilizerOfVertex'(G, v), v) (see "Projection", "StabilizerOfVertex"). \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> ProjStab(Basilica, [1,2,1]); < v, u > \endexample \>FindGroupRelations( <G>[, <max_len>, <max_num_rels>] ) O \>FindGroupRelations( <subs_words>[, <names>, <max_len>, <max_num_rels>] ) O Finds group relations between the generators of the group <G> or in the group generated by <subs_words>. Stops after investigating all words of length up to <max_len> elements or when it finds <max_num_rels> relations. The optional argument <names> is a list of names of generators of the same length as <subs_words>. If this argument is given the relations are given in terms of these names. Otherwise they are given in terms of the elements of the group generated by <subs_words>. If <max_len> or <max_num_rels> are not specified, they are assumed to be `infinity'. Note that if the rewring system (see "AG_UseRewritingSystem") for group <G> is used, then this operation returns relations not contained in the rewriting system rules (see "AG_RewritingSystemRules"). This operation can be applied to any group, not only to a group generated by automata. \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> FindGroupRelations(Basilica, 6); 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 v^2*u*v^2*u^-1*v^-2*u*v^-2*u^-1 [ 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, v^2*u*v^2*u^-1*v^-2*u*v^-2*u^-1 ] gap> FindGroupRelations([u*v^-1, v*u], ["x", "y"], 5); y*x^2*y*x^-1*y^-2*x^-1 [ y*x^2*y*x^-1*y^-2*x^-1 ] gap> FindGroupRelations([u*v^-1, v*u], 5); u^-2*v*u^-2*v^-1*u^2*v*u^2*v^-1 [ u^-2*v*u^-2*v^-1*u^2*v*u^2*v^-1 ] gap> FindGroupRelations([(1,2)(3,4), (1,2,3)], ["x", "y"]); x^2 y^-3 y^-1*x*y^-1*x*y^-1*x [ x^2, y^-3, y^-1*x*y^-1*x*y^-1*x ] \endexample \>FindSemigroupRelations( <G>[, <max_len>, <max_num_rels>] ) O \>FindSemigroupRelations( <subs_words>[, <names>, <max_len>, <max_num_rels>] ) O Finds semigroup relations between the generators of the group or semigroup <G>, or in the semigroup generated by <subs_words>. The arguments have the same meaning as in `FindGroupRelations'~("FindGroupRelations"). It returns a list of pairs of equal words. In order to make the list of relations shorter it also tries to remove relations that can be derived from the known ones. Note, that by default the trivial automorphism is not included in every semigroup. So if one needs to find relations of the form $w=1$ one has to define <G> as a monoid or to include the trivial automorphism into <subs_words> (for instance, as `One(g)' for any element `g' acting on the same tree). This operation can be applied for any semigroup, not only for a semigroup generated by automata. \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> FindSemigroupRelations([u*v^-1, v*u], ["x", "y"], 6); 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 [ [ 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 ] ] gap> FindSemigroupRelations([u*v^-1, v*u],6); v*u^2*v^-1*u^2=u^2*v*u^2*v^-1 v*u^2*v^-1*u*v^-1*u^2*v*u=u*v^-1*u^2*v*u*v*u^2*v^-1 v*u*v*u^2*v^-1*u*v^-1*u^2=u^2*v*u*v*u^2*v^-1*u*v^-1 [ [ v*u^2*v^-1*u^2, u^2*v*u^2*v^-1 ], [ v*u^2*v^-1*u*v^-1*u^2*v*u, u*v^-1*u^2*v*u*v*u^2*v^-1 ], [ v*u*v*u^2*v^-1*u*v^-1*u^2, u^2*v*u*v*u^2*v^-1*u*v^-1 ] ] gap> x := Transformation([1,1,2]);; gap> y := Transformation([2,2,3]);; gap> FindSemigroupRelations([x,y],["x","y"]); y*x=x y^2=y x^3=x^2 x^2*y=x*y [ [ y*x, x ], [ y^2, y ], [ x^3, x^2 ], [ x^2*y, x*y ] ] \endexample \>Iterator( <G>[, <max_len>] ) M Provides a possibility to loop over elements of a group (semigroup, monoid) generated by automata. If <max_len> is given stops after enumerating all elements of length up to <max_len>. \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> iter := Iterator(GrigorchukGroup, 5); <iterator> gap> l:=[];; gap> for g in iter do > if Order(g)=16 then Add(l,g); fi; > od; gap> l; [ 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, 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, a*d*a*c*a, a*c*a*d*a ] \endexample \>FindElement( <G>, <func>, <val>, <max_len> ) O \>FindElements( <G>, <func>, <val>, <max_len> ) O The first function enumerates elements of the group (semigroup, monoid) <G> until it finds an element $g$ of length at most <max_len>, for which <func>($g$)=<val>. Returns $g$ if such an element was found and `fail' otherwise. The second function enumerates elements of the group (semigroup, monoid) of length at most <max_len> and returns the list of elements $g$, for which <func>($g$)=<val>. These functions are based on `Iterator' operation (see "Iterator"), so can be applied in more general settings whenever \GAP\ knows how to solve word problem in the group. The following example illustrates how to find an element of order 16 in Grigorchuk group and the list of all such elements of length at most 5. \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> FindElement(GrigorchukGroup, Order, 16, 5); a*b gap> FindElements(GrigorchukGroup,Order,16,5); [ 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, d*a*b*a, d*a*c*a, a*c*a*d*a, a*d*a*c*a, b*a*b*a*c, b*a*c*a*c, c*a*b*a*b, c*a*c*a*b ] \endexample \>FindElementOfInfiniteOrder( <G>, <max_len>, <depth> ) O \>FindElementsOfInfiniteOrder( <G>, <max_len>, <depth> ) O The first function enumerates elements of the group <G> up to length <max_len> until it finds an element $g$ of infinite order, such that `OrderUsingSections'($g$,<depth>) (see "OrderUsingSections") is `infinity'. In other words all sections of every element up to depth <depth> are investigated. In case if the element belongs to the group generated by bounded automaton (see "IsGeneratedByBoundedAutomaton") one can set <depth> to be `infinity'. The second function returns the list of all such elements up to length <max_len>. \beginexample gap> G := AutomatonGroup("a=(1,1)(1,2), b=(a,c), c=(b,1)"); < a, b, c > gap> FindElementOfInfiniteOrder(G, 5, 10); a*b*c \endexample \>SphericallyTransitiveElement( <G> ) A For a self-similar group <G> acting on a binary tree returns an element of <G> acting spherically transitively on the levels of the tree if such an element exists and `fail' otherwise. See also `ContainsSphericallyTransitiveElement' ("ContainsSphericallyTransitiveElement"). \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> SphericallyTransitiveElement(Basilica); u*v gap> G := SelfSimilarGroup("a=(a^-1*b^-1,1)(1,2), b=(b^-1,a*b)"); < a, b > gap> SphericallyTransitiveElement(G); fail \endexample \>Growth( <G>, <max_len> ) O Returns a list of the first values of the growth function of a group (semigroup, monoid) <G>. If <G> is a monoid it computes the growth function at $\{0,1,\ldots,<max_len>\}$, and for a semigroup without identity at $\{1,\ldots,<max_len>\}$. \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> Growth(GrigorchukGroup, 7); There are 11 elements of length up to 2 There are 23 elements of length up to 3 There are 40 elements of length up to 4 There are 68 elements of length up to 5 There are 108 elements of length up to 6 There are 176 elements of length up to 7 [ 1, 5, 11, 23, 40, 68, 108, 176 ] gap> H := AutomatonSemigroup("a=(a,b)[1,1], b=(b,a)(1,2)"); < a, b > gap> Growth(H,6); [ 2, 6, 14, 30, 62, 126 ] \endexample \>ListOfElements( <G>, <max_len> ) O Returns the list of all different elements of a group (semigroup, monoid) <G> up to length <max_len>. \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> ListOfElements(GrigorchukGroup, 3); [ 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, b*a*c, b*a*d, c*a*b, c*a*c, c*a*d, d*a*b, d*a*c, d*a*d ] \endexample \>FindNucleus( <G>[, <max_nucl>, <print_info>] ) O Given a self-similar group <G> it tries to find its nucleus. If the group is not contracting it will loop forever. When it finds the nucleus it returns the triple [`GroupNucleus'(<G>), `GeneratingSetWithNucleus'(<G>), `GeneratingSetWithNucleusAutom'(<G>)] (see "GroupNucleus", "GeneratingSetWithNucleus", "GeneratingSetWithNucleusAutom"). If <max_nucl> is given it stops after finding <max_nucl> elements that need to be in the nucleus and returns `fail' if the nucleus was not found. An optional argument <print_info> is a boolean telling whether to print results of intermediate computations. The default value is `true'. Use `IsNoncontracting'~(see "IsNoncontracting") to try to show that <G> is noncontracting. \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> FindNucleus(Basilica); Trying generating set with 5 elements Elements added:[ u^-1*v, v^-1*u ] Trying generating set with 7 elements [ [ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ], [ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ], <automaton> ] \endexample \>LevelOfFaithfulAction( <G> ) A \>LevelOfFaithfulAction( <G>, <max_lev> ) A For a given finite self-similar group <G> determines the smallest level of the tree, where <G> acts faithfully, i.e. the stabilizer of this level in <G> is trivial. The idea here is that for a self-similar group all nontrivial level stabilizers are different. If <max_lev> is given it finds only first <max_lev> quotients by stabilizers and if all of them have different size it returns `fail'. If <G> is infinite and <max_lev> is not specified it will loop forever. See also `IsomorphismPermGroup' ("IsomorphismPermGroup"). \beginexample gap> H := SelfSimilarGroup("a=(a,a)(1,2), b=(a,a), c=(b,a)(1,2)"); < a, b, c > gap> LevelOfFaithfulAction(H); 3 gap> Size(H); 16 gap> LevelOfFaithfulAction(AddingMachine, 10); fail \endexample \>IsomorphismPermGroup( <G> ) O \>IsomorphismPermGroup( <G>, <max_lev> ) O For a given finite group <G> generated by initial automata or by elements defined by wreath recursion computes an isomorphism from <G> into a finite permutational group. If <G> is not known to be self-similar (see "IsSelfSimilar") the isomorphism is based on the regular representation, which works generally much slower. If <G> is self-similar there is a level of the tree (see "LevelOfFaithfulAction"), where <G> acts faithfully. The corresponding representation is returned in this case. If <max_lev> is given it finds only the first <max_lev> quotients by stabilizers and if all of them have different size it returns `fail'. If <G> is infinite and <max_lev> is not specified it will loop forever. For example, consider a subgroup $\langle a, b\rangle$ of Grigorchuk group. \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> f := IsomorphismPermGroup(Group(a, b)); MappingByFunction( < a, b >, Group( [ (1,2)(3,5)(4,6)(7,9)(8,10)(11,13)(12,14)(15,17)(16,18)(19,21)(20,22)(23, 25)(24,26)(27,29)(28,30)(31,32), (1,3)(2,4)(5,7)(6,8)(9,11)(10,12)(13, 15)(14,16)(17,19)(18,20)(21,23)(22,24)(25,27)(26,28)(29,31)(30,32) ]), function( g ) ... end, function( b ) ... end ) gap> Size(Image(f)); 32 gap> H := SelfSimilarGroup("a=(a*b,1)(1,2), b=(1,b*a^-1)(1,2), c=(b, a*b)"); < a, b, c > gap> f1 := IsomorphismPermGroup(H); MappingByFunction( < a, b, c >, Group([ (1,3)(2,4), (1,3)(2,4), (1,2) ]), function( g ) ... end, function( b ) ... end ) gap> Size(Image(f1)); 8 gap> PreImagesRepresentative(f1, (1,3,2,4)); a*c gap> (a*c)^f1; (1,3,2,4) \endexample \>Random( <G> ) O Returns a random element of a group (semigroup) <G>. The operation is based on the generator of random elements in free groups and semigroups. \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> Random( Basilica ); v*u^-3 \endexample \>MarkovOperator( <G>, <lev> ) F Computes the matrix of the Markov operator related to the group <G> on the <lev>-th level of the tree. If the group <G> is generated by $g_1,g_2,\ldots,g_n$ then the Markov operator is defined as $(`PermOnLevelAsMatrix'(g_1)+\cdots+`PermOnLevelAsMatrix'(g_d)+ `PermOnLevelAsMatrix'(g_1^{-1})+\cdots+`PermOnLevelAsMatrix'(g_d^{-1}))/(2*d)$. See also `PermOnLevelAsMatrix' ("PermOnLevelAsMatrix"). \beginexample gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)"); < p, q > gap> MarkovOperator(L, 3); [ [ 0, 0, 1/4, 1/4, 0, 1/4, 0, 1/4 ], [ 0, 0, 1/4, 1/4, 1/4, 0, 1/4, 0 ], [ 1/4, 1/4, 0, 0, 1/4, 0, 1/4, 0 ], [ 1/4, 1/4, 0, 0, 0, 1/4, 0, 1/4 ], [ 0, 1/4, 1/4, 0, 0, 1/2, 0, 0 ], [ 1/4, 0, 0, 1/4, 1/2, 0, 0, 0 ], [ 0, 1/4, 1/4, 0, 0, 0, 1/2, 0 ], [ 1/4, 0, 0, 1/4, 0, 0, 0, 1/2 ] ] \endexample \>AbelImage( <obj> ) A Returns image of <obj> in the canonical projection onto the abelianization of the full group of tree automorphisms, represented as a subgroup of the additive group of rational functions. \>DiagonalPower( <fam>[, <k>] ) O For a given automaton group <G> acting on alphabet $X$ and corresponding family <fam> of automata one can consider the action of $<G>^<k>$ on $X^<k>$ defined by $(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})$. This function constructs a self-similar group, which encodes this action. If <k> is not given it is assumed to be $2$. \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> S := DiagonalPower(UnderlyingAutomFamily(Basilica)); < uu, uv, u1, vu, vv, v1, 1u, 1v > gap> Decompose(uu); (vv, v1, 1v, 1)(1,4)(2,3) \endexample \>MultAutomAlphabet( <fam> ) O \>UnderlyingAutomFamily( <G> ) A Returns the family to which the elements of <G> belong. %Declaration{UnderlyingFreeGroup} %Declaration{UnderlyingFreeSubgroup} %Declaration{UnderlyingFreeGenerators} %Declaration{IndexInFreeGroup} %Declaration{ApplyNielsen} %Declaration{MihailovaSystem} %Declaration{TrivialSubgroup} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Self-similar groups and semigroups defined by wreath recursion} \>`IsFiniteState( <G> )'{IsFiniteState![selfsimsg]}@{`IsFiniteState'!`[selfsimsg]'} P For a group or semigroup of homomorphisms of the tree defined using a wreath recursion, returns `true' if all generators can be represented as finite automata (have finitely many different sections). It will never stop if the free reduction of words is not sufficient to establish the finite-state property or if the group is not finite-state. In case <G> is a finite-state group it automatically computes the attributes `UnderlyingAutomatonGroup'(<G>) ("UnderlyingAutomatonGroup"), `IsomorphicAutomGroup'(<G>) ("IsomorphicAutomGroup") and `MonomorphismToAutomatonGroup'(<G>) ("MonomorphismToAutomatonGroup"). For a finite-state semigroup it computes the corresponding attributes `UnderlyingAutomatonSemigroup'(<G>) ("UnderlyingAutomatonSemigroup"), `IsomorphicAutomSemigroup'(<G>) ("IsomorphicAutomSemigroup") and `MonomorphismToAutomatonSemigroup'(<G>) ("MonomorphismToAutomatonSemigroup"). \beginexample gap> W:=SelfSimilarGroup("x=(x^-1,y)(1,2), y=(z^-1,1)(1,2), z=(1,x*y)"); < x, y, z > gap> IsFiniteState(W); true gap> Size(GeneratorsOfGroup(UnderlyingAutomatonGroup(W))); 50 \endexample \>IsomorphicAutomGroup( <G> ) AM In case <G> is finite-state tries to compute a group generated by automata, isomorphic to <G>, which is a subgroup of `UnderlyingAutomatonGroup'(<G>) (see "UnderlyingAutomatonGroup"). The natural isomorphism between <G> and `IsomorphicAutomGroup'(<G>) is stored in the attribute `MonomorphismToAutomatonGroup'(<G>) ("MonomorphismToAutomatonGroup"). In some cases it may be useful to check if <G> is finite. \beginexample gap> R := SelfSimilarGroup("a=(a^-1*b,b^-1*a)(1,2), b=(a^-1,b^-1)"); < a, b > gap> UR := UnderlyingAutomatonGroup(R); < a1, a2, a4, a5 > gap> IR := IsomorphicAutomGroup(R); < a1, a5 > gap> hom := MonomorphismToAutomatonGroup(R); MappingByFunction( < a, b >, < a1, a5 >, function( a ) ... end, function( b ) \ ... end ) gap> (a*b)^hom; a1*a5 gap> PreImagesRepresentative(hom, last); a*b gap> List(GeneratorsOfGroup(UR), x -> PreImagesRepresentative(hom, x)); [ a, a^-1*b, b^-1*a, b ] \endexample All these operations work also for the subgroups of groups generated by `SelfSimilarGroup'. ("SelfSimilarGroup"). \beginexample gap> T := Group([b*a, a*b]); < b*a, a*b > gap> IT := IsomorphicAutomGroup(T); < a1, a4 > \endexample Note, that different groups have different `UnderlyingAutomGroup' attributes. For example, the generator `a1' of group `IT' above is different from the generator `a1' of group `IR'. \>IsomorphicAutomSemigroup( <G> ) AM In case <G> is finite-state returns a semigroup generated by automata, isomorphic to <G>, which is a subsemigroup of `UnderlyingAutomatonSemigroup'(<G>) (see "UnderlyingAutomatonSemigroup"). The natural isomorphism between <G> and `IsomorphicAutomSemigroup'(<G>) is stored in the attribute `MonomorphismToAutomatonSemigroup'(<G>) ("MonomorphismToAutomatonSemigroup"). \beginexample gap> R := SelfSimilarSemigroup("a=(1,1)[1,1], b=(a*c,1)(1,2), c=(1,a*b)"); < a, b, c > gap> UR := UnderlyingAutomatonSemigroup(R); < 1, a1, a3, a5, a6 > gap> IR := IsomorphicAutomSemigroup(R); < a1, a3, a5 > gap> hom := MonomorphismToAutomatonSemigroup(R); MappingByFunction( < a, b, c >, < a1, a3, a5 >, function( a ) ... end, functio\ n( b ) ... end ) gap> (a*b)^hom; a1*a3 gap> PreImagesRepresentative(hom, last); a*b gap> List(GeneratorsOfSemigroup(UR), x -> PreImagesRepresentative(hom, x)); [ 1, a, b, c, a*b ] \endexample All these operations work also for the subsemigroups of semigroups generated by `SelfSimilarSemigroup' ("SelfSimilarSemigroup"). \beginexample gap> T := Semigroup([a*b, b^2]); < a*b, b^2 > gap> IT := IsomorphicAutomSemigroup(T); < a1, a4 > \endexample Note, that different semigroups have different `UnderlyingAutomSemigroup' attributes. For example, the generator `a1' of semigroup `IT' above is different from the generator `a1' of semigroup `IR'. \>UnderlyingAutomatonGroup( <G> ) AM In case <G> is finite-state returns a self-similar closure of <G> as a group generated by automaton. The natural monomorphism from <G> and `UnderlyingAutomatonGroup'(<G>) is stored in the attribute `MonomorphismToAutomatonGroup'(<G>) ("MonomorphismToAutomatonGroup"). If <G> is created by `SelfSimilarGroup' (see "SelfSimilarGroup"), then the self-similar closure of <G> coincides with <G>, so one can use `MonomorphismToAutomatonGroup'(<G>) to get preimages of elements of `UnderlyingAutomatonGroup'(<G>) in <G>. See the example for `IsomorphicAutomGroup' ("IsomorphicAutomGroup"). \>UnderlyingAutomatonSemigroup( <G> ) AM In case <G> is finite-state returns a self-similar closure of <G> as a semigroup generated by automaton. The natural monomorphism from <G> and `UnderlyingAutomatonSemigroup'(<G>) is stored in the attribute `MonomorphismToAutomatonSemigroup'(<G>) ("MonomorphismToAutomatonSemigroup"). If <G> is created by `SelfSimilarSemigroup' (see "SelfSimilarSemigroup"), then the self-similar closure of <G> coincides with <G>, so one can use `MonomorphismToAutomatonSemigroup'(<G>) to get preimages of elements of `UnderlyingAutomatonSemigroup'(<G>) in <G>. See the example for `IsomorphicAutomSemigroup' ("IsomorphicAutomSemigroup"). \>MonomorphismToAutomatonGroup( <G> ) AM In case <G> is finite-state returns a monomorphism from <G> into `UnderlyingAutomatonGroup'(<G>) (see "UnderlyingAutomatonGroup"). If <G> is created by `SelfSimilarGroup' (see "SelfSimilarGroup"), then one can use `MonomorphismToAutomatonGroup'(<G>) to get preimages of elements of `UnderlyingAutomatonGroup'(<G>) in <G>. See the example for `IsomorphicAutomGroup' ("IsomorphicAutomGroup"). \>MonomorphismToAutomatonSemigroup( <G> ) AM In case <G> is finite-state returns a monomorphism from <G> into `UnderlyingAutomatonSemigroup'(<G>) (see "UnderlyingAutomatonSemigroup"). If <G> is created by `SelfSimilarSemigroup' (see "SelfSimilarSemigroup"), then one can use `MonomorphismToAutomatonSemigroup'(<G>) to get preimages of elements of `UnderlyingAutomatonSemigroup'(<G>) in <G>. See the example for `IsomorphicAutomSemigroup' ("IsomorphicAutomSemigroup"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Contracting groups} \>GroupNucleus( <G> ) AM Tries to compute the <nucleus> (see the definition in "Short math background") of a self-similar group <G>. Note that this set need not contain the original generators of <G>. It uses `FindNucleus' (see "FindNucleus") operation and behaves accordingly: if the group is not contracting it will loop forever. See also `GeneratingSetWithNucleus' ("GeneratingSetWithNucleus"). \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> GroupNucleus(Basilica); [ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ] \endexample \>GeneratingSetWithNucleus( <G> ) AM Tries to compute the generating set of a self-similar group <G> that includes the original generators and the <nucleus> (see "Short math background") of <G>. It uses `FindNucleus' operation and behaves accordingly: if the group is not contracting it will loop forever (modulo memory constraints, of course). See also `GroupNucleus' ("GroupNucleus"). \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> GeneratingSetWithNucleus(Basilica); [ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ] \endexample \>GeneratingSetWithNucleusAutom( <G> ) AM Computes the automaton of the generating set that includes the nucleus of the contracting group <G>. See also `GeneratingSetWithNucleus' ("GeneratingSetWithNucleus"). \beginexample gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> B_autom := GeneratingSetWithNucleusAutom(Basilica); <automaton> gap> Print(B_autom); a1 = (a1, a1), a2 = (a3, a1)(1,2), a3 = (a2, a1), a4 = (a1, a5) (1,2), a5 = (a4, a1), a6 = (a1, a7)(1,2), a7 = (a6, a1)(1,2) \endexample \>ContractingLevel( <G> ) AM Given a contracting group <G> with generating set $N$ that includes the nucleus, stored in `GeneratingSetWithNucleus'(<G>) (see "GeneratingSetWithNucleus") computes the minimal level $n$, such that for every vertex $v$ of the $n$-th level and all $g, h \in N$ the section $gh|_v \in N$. In case if it is not known whether <G> is contracting it first tries to compute the nucleus. If <G> happens to be noncontracting, it will loop forever. One can also use `IsNoncontracting' (see "IsNoncontracting") or `FindNucleus' (see "FindNucleus") directly. \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> ContractingLevel(GrigorchukGroup); 1 gap> ContractingLevel(Basilica); 2 \endexample \>ContractingTable( <G> ) AM Given a contracting group <G> with generating set $N$ of size $k$ that includes the nucleus, stored in `GeneratingSetWithNucleus'(<G>)~(see "GeneratingSetWithNucleus") computes the $k\times k$ table, whose [i][j]-th entry contains decomposition of $N$[i]$N$[j] on the `ContractingLevel'(<G>) level~(see "ContractingLevel"). By construction the sections of $N$[i]$N$[j] on this level belong to $N$. This table is used in the algorithm solving the word problem in polynomial time. In case if it is not known whether <G> is contracting it first tries to compute the nucleus. If <G> happens to be noncontracting, it will loop forever. One can also use `IsNoncontracting' (see "IsNoncontracting") or `FindNucleus' (see "FindNucleus") directly. \beginexample gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> ContractingTable(GrigorchukGroup); [ [ (1, 1), (1, 1)(1,2), (a, c), (a, d), (1, b) ], [ (1, 1)(1,2), (1, 1), (c, a)(1,2), (d, a)(1,2), (b, 1)(1,2) ], [ (a, c), (a, c)(1,2), (1, 1), (1, b), (a, d) ], [ (a, d), (a, d)(1,2), (1, b), (1, 1), (a, c) ], [ (1, b), (1, b)(1,2), (a, d), (a, c), (1, 1) ] ] \endexample \>UseContraction( <G> ) O \>DoNotUseContraction( <G> ) O For a contracting automaton group <G> these two operations determine whether to use the algorithm of polynomial complexity solving the word problem in the group. By default it is set to <true> as soon as the nucleus of the group was computed. Sometimes when the nucleus is very big, the standard algorithm of exponential complexity is faster for short words, but this heavily depends on the group. Therefore the decision on which algorithm to use is left to the user. To use the exponential algorithm one can use the second operation `DoNotUseContraction'(<G>). Note also then in order to use the polynomial time algorithm the `ContractingTable(G)' (see "ContractingTable") has to be computed first, which takes some time when the nucleus is big. This attribute is computed automatically when the word problem is solved for the first time. This sometimes causes some delay. Below we provide an example which shows that both methods can be of use. %notest \beginexample gap> G := AutomatonGroup("a=(b,b)(1,2), b=(c,a), c=(a,a)"); < a, b, c > gap> IsContracting(G); true gap> Size(GroupNucleus(G)); 41 gap> ContractingLevel(G); 6 gap> ContractingTable(G);; time; 11336 gap> v := a*b*a*b^2*c*b*c*b^-1*a^-1*b^-1*a^-1;; gap> w := b*c*a*b*a*b*c^-1*b^-2*a^-1*b^-1*a^-1;; gap> UseContraction(G);; gap> IsOne(Comm(v,w)); time; true 251 gap> FindGroupRelations(G, 5);; time; a^2 b^2 c^2 b*a*b*c*a*b*a*b*c*a b*c*a*c*a*b*c*a*c*a 881 gap> DoNotUseContraction(G);; gap> IsOne(Comm(v,w)); time; true 3855 gap> FindGroupRelations(G, 5);; time; a^2 b^2 c^2 b*a*b*c*a*b*a*b*c*a b*c*a*c*a*b*c*a*c*a 451 \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Rewriting Systems} It is possible to use basic relators in all computations performed in a self-similar group. \>AG_UseRewritingSystem( <G>[, <setting>] ) O Tells whether computations in the group <G> should use a rewriting system. <setting> defaults to `true' if omitted. This function initially only tries to find involutions in <G>. See `AG_AddRelators' ("AG_AddRelators") and `AG_UpdateRewritingSystem' ("AG_UpdateRewritingSystem") for the ways to add more relators. \beginexample gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> Comm(a*b, b*a); b^-1*a^-2*b^-1*a*b^2*a gap> AG_UseRewritingSystem(G); gap> Comm(a*b, b*a); 1 gap> AG_UseRewritingSystem(G, false); gap> Comm(a*b, b*a); b^-1*a^-2*b^-1*a*b^2*a \endexample \>AG_AddRelators( <G>, <relators> ) O Adds relators from the list <relators> to the rewriting system used in <G>. \beginexample gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> AG_UseRewritingSystem(G); gap> b*c; b*c gap> AG_AddRelators(G, [b*c*d]); gap> b*c; d \endexample In some cases it's hard to find relations directly from the wreath recursion of a self-similar group (at least, there is no general agorithm). This function provides possibility to add relators manually. After that one can use `AG_UpdateRewritingSystem' (see "AG_UpdateRewritingSystem") and `AG_UseRewritingSystem' (see "AG_UseRewritingSystem") to use these relators in computations. In the example below we consider a finite group $H$, in which $a=b$, but the standard algorithm is unable to solve the word problem. There are two solutions for that. One can manually add a relator, or one can ask if the group is finite (which does not stop generally if the group is infinite). \beginexample gap> H := SelfSimilarGroup("a=(a*b,1)(1,2), b=(1,b*a^-1)(1,2), c=(b, a*b)"); < a, b, c > gap> AG_AddRelators(H, [a*b^-1]); gap> AG_UseRewritingSystem(H); gap> Order(a*c); 4 \endexample \>AG_UpdateRewritingSystem( <G>, <maxlen> ) O Tries to find new relators of length up to <maxlen> and adds them into the rewriting system. It can also be used after introducing new relators via `AG_AddRelators' (see "AG_AddRelators"). \beginexample gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> AG_UseRewritingSystem(G); gap> b*c; b*c gap> AG_UpdateRewritingSystem(G, 3); gap> b*c; d \endexample \>AG_RewritingSystemRules( <G> ) O Returns the list of rules used in the rewriting system of group <G>. \beginexample gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> AG_UseRewritingSystem(G); gap> AG_RewritingSystemRules(G); [ [ a^2, <identity ...> ], [ b^2, <identity ...> ], [ c^2, <identity ...> ], [ d^2, <identity ...> ], [ a^-1, a ], [ b^-1, b ], [ c^-1, c ], [ d^-1, d ] ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%