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