1############################################################################# 2## 3#W treeautgrp.gd automgrp package Yevgen Muntyan 4#W Dmytro Savchuk 5## 6#Y Copyright (C) 2003 - 2018 Yevgen Muntyan, Dmytro Savchuk 7## 8 9 10############################################################################### 11## 12#C IsTreeAutomorphismGroup( <G> ) 13## 14## The category of groups of tree automorphisms. 15## 16DeclareSynonym("IsTreeAutomorphismGroup", IsGroup and IsTreeAutomorphismCollection); 17InstallTrueMethod(IsActingOnTree, IsTreeAutomorphismGroup); 18 19 20############################################################################### 21## 22#O TreeAutomorphismGroup( <G>, <S> ) 23## 24## Constructs wreath product of tree automorphisms group <G> and permutation 25## group <S>. 26## 27DeclareOperation("TreeAutomorphismGroup", [IsTreeAutomorphismGroup, IsPermGroup]); 28 29 30############################################################################### 31## 32#P IsFractal( <G> ) 33## 34## Returns whether the group <G> is fractal (also called as <self-replicating>). In other 35## words, if <G> acts transitively on the first level and for any vertex $v$ of the tree 36## the projection of the stabilizer of $v$ in <G> 37## on this vertex coincides with the whole group <G>. 38## \beginexample 39## gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); 40## < a, b, c, d > 41## gap> IsFractal(Grigorchuk_Group); 42## true 43## \endexample 44## 45DeclareProperty("IsFractal", IsTreeAutomorphismGroup); 46 47 48############################################################################# 49## 50#P IsFractalByWords( <G> ) 51## 52## Computes the generators of stabilizers of vertices of the first level 53## and their projections on these vertices. Returns `true' if the preimages of these 54## projections in the free group under the canonical epimorphism generate the whole free 55## group for each stabilizer, and the <G> acts transitively on the first level. 56## This is sufficient but not necessary condition for <G> to be fractal. See also 57## `IsFractal' ("IsFractal"). 58## 59DeclareProperty("IsFractalByWords", IsTreeAutomorphismGroup); 60InstallTrueMethod(IsFractal, IsFractalByWords); 61 62 63############################################################################### 64## 65#A LevelOfFaithfulAction( <G> ) 66#A LevelOfFaithfulAction( <G>, <max_lev> ) 67## 68## For a given finite self-similar group <G> determines the smallest level of 69## the tree, where <G> acts faithfully, i.e. the stabilizer of this level in <G> 70## is trivial. The idea here is that for a self-similar group all nontrivial level 71## stabilizers are different. If <max_lev> is given it finds only first <max_lev> 72## quotients by stabilizers and if all of them have different size it returns `fail'. 73## If <G> is infinite and <max_lev> is not specified it will loop forever. 74## 75## See also `IsomorphismPermGroup' ("IsomorphismPermGroup"). 76## \beginexample 77## gap> H := SelfSimilarGroup("a=(a,a)(1,2), b=(a,a), c=(b,a)(1,2)"); 78## < a, b, c > 79## gap> LevelOfFaithfulAction(H); 80## 3 81## gap> Size(H); 82## 16 83## gap> Adding_Machine := AutomatonGroup("a=(1,a)(1,2)"); 84## < a > 85## gap> LevelOfFaithfulAction(Adding_Machine, 10); 86## fail 87## \endexample 88## 89DeclareAttribute("LevelOfFaithfulAction", IsTreeAutomorphismGroup and IsSelfSimilar); 90 91 92################################################################################ 93## 94#A IsContracting( <G> ) 95## 96## Given a self-similar group <G> tries to compute whether it is contracting or not. 97## Only a partial method is implemented (since there is no general algorithm so far). 98## First it tries to find the nucleus up to size 50 using `FindNucleus'(<G>,50) (see~"FindNucleus"), then 99## it tries to find evidence that the group is noncontracting using 100## `IsNoncontracting'(<G>,10,10) (see~"IsNoncontracting"). If the answer was not found one can try to use 101## `FindNucleus' and `IsNoncontracting' with bigger parameters. Also one can use 102## `SetInfoLevel(InfoAutomGrp, 3)' for more information to be displayed. 103## 104## \beginexample 105## gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 106## < u, v > 107## gap> IsContracting(Basilica); 108## true 109## gap> IsContracting(AutomatonGroup("a=(c,a)(1,2), b=(c,b), c=(b,a)")); 110## false 111## \endexample 112## 113DeclareProperty("IsContracting", IsTreeAutomorphismGroup); 114 115 116############################################################################### 117## 118#A StabilizerOfFirstLevel( <G> ) 119## 120## Returns the stabilizer of the first level, see also~"StabilizerOfLevel". 121## \beginexample 122## gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 123## < u, v > 124## gap> StabilizerOfFirstLevel(Basilica); 125## < v, u^2, u*v*u^-1 > 126## \endexample 127## 128DeclareAttribute("StabilizerOfFirstLevel", IsTreeAutomorphismGroup); 129 130############################################################################### 131## 132#O StabilizerOfLevel( <G>, <k> ) 133## 134## Returns the stabilizer of the <k>-th level. 135## \beginexample 136## gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 137## < u, v > 138## gap> StabilizerOfLevel(Basilica, 2); 139## < 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*\ 140## v^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 > 141## \endexample 142## 143KeyDependentOperation("StabilizerOfLevel", IsTreeAutomorphismGroup, IsPosInt, ReturnTrue); 144 145############################################################################### 146## 147#O StabilizerOfVertex( <G>, <v> ) 148## 149## Returns the stabilizer of the vertex <v>. Here <v> can be a list representing a 150## vertex, or a positive integer representing a vertex at the first level. 151## \beginexample 152## gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 153## < u, v > 154## gap> StabilizerOfVertex(Basilica, [1,2,1]); 155## < 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\ 156## *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 > 157## \endexample 158## 159DeclareOperation("StabilizerOfVertex", [IsTreeAutomorphismGroup, IsObject]); 160 161 162############################################################################### 163## 164#O Projection( <G>, <v> ) 165#O ProjectionNC( <G>, <v> ) 166## 167## Returns the projection of the group <G> at the vertex <v>. The group <G> must fix the 168## vertex <v>, otherwise `Error'() will be called. The operation `ProjectionNC' does the 169## same thing, except it does not check whether <G> fixes the vertex <v>. 170## \beginexample 171## gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 172## < u, v > 173## gap> Projection(StabilizerOfVertex(Basilica, [1,2,1]), [1,2,1]); 174## < u, v > 175## \endexample 176## 177KeyDependentOperation("Projection", IsTreeAutomorphismGroup, IsPosInt, ReturnTrue); 178DeclareOperation("Projection", [IsTreeAutomorphismGroup, IsList]); 179DeclareOperation("ProjectionNC", [IsTreeAutomorphismGroup, IsObject]); 180 181############################################################################### 182## 183#O ProjStab (<G>, <v>) 184## 185## Returns the projection of the stabilizer of <v> at itself. It is a shortcut for 186## `Projection'(`StabilizerOfVertex'(G, v), v) (see "Projection", 187## "StabilizerOfVertex"). 188## \beginexample 189## gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 190## < u, v > 191## gap> ProjStab(Basilica, [1,2,1]); 192## < u, v > 193## \endexample 194## 195DeclareOperation("ProjStab", [IsTreeAutomorphismGroup, IsObject]); 196 197 198DeclareOperation("__AG_SubgroupOnLevel", [IsTreeAutomorphismGroup, 199 IsTreeHomomorphismCollection, 200 IsPosInt]); 201DeclareOperation("__AG_SimplifyGroupGenerators", [IsObject]); 202 203 204############################################################################### 205## 206#O PermGroupOnLevel (<G>, <k>) 207## 208## Returns the group of permutations induced by the action of the group <G> at the <k>-th 209## level. 210## \beginexample 211## gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 212## < u, v > 213## gap> PermGroupOnLevel(Basilica, 4); 214## 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) ]) 215## gap> H := PermGroupOnLevel(Group([u,v^2]),4); 216## Group([ (1,11,3,9)(2,12,4,10)(5,13)(6,14)(7,15)(8,16), (1,2)(5,6) ]) 217## gap> Size(H); 218## 64 219## \endexample 220## 221KeyDependentOperation("PermGroupOnLevel", IsTreeAutomorphismGroup, IsPosInt, ReturnTrue); 222 223 224############################################################################### 225## 226#A ContainsSphericallyTransitiveElement( <G> ) 227## 228## For a self-similar group <G> acting on a binary tree returns `true' if <G> contains 229## an element acting spherically transitively on the levels of the tree and `false' 230## otherwise. See also `SphericallyTransitiveElement' ("SphericallyTransitiveElement"). 231## \beginexample 232## gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 233## < u, v > 234## gap> ContainsSphericallyTransitiveElement(Basilica); 235## true 236## gap> G := SelfSimilarGroup("a=(a^-1*b^-1,1)(1,2), b=(b^-1,a*b)"); 237## < a, b > 238## gap> ContainsSphericallyTransitiveElement(G); 239## false 240## \endexample 241## 242DeclareAttribute("ContainsSphericallyTransitiveElement", IsTreeAutomorphismGroup); 243 244 245############################################################################### 246## 247#A SphericallyTransitiveElement( <G> ) 248## 249## For a self-similar group <G> acting on a binary tree returns 250## an element of <G> acting spherically transitively on the levels of the tree if 251## such an element exists and `fail' 252## otherwise. See also `ContainsSphericallyTransitiveElement' 253## ("ContainsSphericallyTransitiveElement"). 254## \beginexample 255## gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); 256## < u, v > 257## gap> SphericallyTransitiveElement(Basilica); 258## u*v 259## gap> G := SelfSimilarGroup("a=(a^-1*b^-1,1)(1,2), b=(b^-1,a*b)"); 260## < a, b > 261## gap> SphericallyTransitiveElement(G); 262## fail 263## \endexample 264## 265DeclareAttribute("SphericallyTransitiveElement", IsTreeAutomorphismGroup); 266 267 268#E 269