############################################################################# ## #W treehom.gd automgrp package Yevgen Muntyan #W Dmytro Savchuk ## automgrp v 1.3.1 ## #Y Copyright (C) 2003 - 2018 Yevgen Muntyan, Dmytro Savchuk ## ############################################################################# ## #C IsTreeHomomorphism ## ## Category of level-preserving rooted tree homomorphisms. ## DeclareCategory("IsTreeHomomorphism", IsActingOnTree and IsMultiplicativeElementWithOne and IsAssociativeElement); DeclareCategoryFamily("IsTreeHomomorphism"); DeclareCategoryCollections("IsTreeHomomorphism"); InstallTrueMethod(IsActingOnTree, IsTreeHomomorphismFamily); InstallTrueMethod(IsActingOnTree, IsTreeHomomorphismCollection); # XXX DeclareAttribute("AutomatonList", IsTreeHomomorphism and IsActingOnRegularTree, "mutable"); ############################################################################### ## #O TreeHomomorphism( , ) ## ## Constructs an homomorphism with states and acting ## on the first level with transformation . The must ## belong to the same family. ## \beginexample ## gap> S := AutomatonSemigroup("a=(a,b)[1,1],b=(b,a)(1,2)"); ## < a, b > ## gap> x := TreeHomomorphism([a,b^2,a,a*b],Transformation([3,1,2,2])); ## (a, b^2, a, a*b)[3,1,2,2] ## gap> y := TreeHomomorphism([a*b,b,b,b^2],Transformation([1,4,2,3])); ## (a*b, b, b, b^2)[1,4,2,3] ## gap> x*y; ## (a*b, b^2*a*b, a*b, a*b^2)[2,1,4,4] ## \endexample ## ## DeclareOperation("TreeHomomorphism", [IsList, IsObject]); ############################################################################### ## #M TreeHomomorphism(, , ..., , ) ## DeclareOperation("TreeHomomorphism", [IsObject, IsObject, IsTransformation]); DeclareOperation("TreeHomomorphism", [IsObject, IsObject, IsObject, IsTransformation]); DeclareOperation("TreeHomomorphism", [IsObject, IsObject, IsObject, IsObject, IsTransformation]); DeclareOperation("TreeHomomorphism", [IsObject, IsObject, IsPerm]); DeclareOperation("TreeHomomorphism", [IsObject, IsObject, IsObject, IsPerm]); DeclareOperation("TreeHomomorphism", [IsObject, IsObject, IsObject, IsObject, IsPerm]); ############################################################################### ## #O TreeHomomorphismFamily( ) ## ## Constructs a family to which all homomorphisms of a tree with spherical ## index belong. It is used internally, objects created with ## `TreeAutomorphism' belong to this family. ## DeclareOperation("TreeHomomorphismFamily", [IsObject]); ############################################################################### ## #O TransformationOnLevel( , ) #O TransformationOnFirstLevel( ) ## ## The first function returns the transformation induced by the tree homomorphism ## on the level . See also `PermOnLevel'~("PermOnLevel"). ## ## If the transformation is invertible then it returns a permutation, and ## `Transformation' otherwise. ## ## `TransformationOnFirstLevel'() is equivalent to ## `TransformationOnLevel'(, `1'). ## KeyDependentOperation("TransformationOnLevel", IsTreeHomomorphism, IsPosInt, ReturnTrue); DeclareAttribute("TransformationOnFirstLevel", IsTreeHomomorphism); ############################################################################### ## #O Perm( [, ] ) ## ## Returns the permutation induced by the tree automorphism on the level ## (or first level if is not given). See also ## `TransformationOnLevel'~("TransformationOnLevel"). ## DeclareOperation("Perm", [IsTreeHomomorphism]); DeclareOperation("Perm", [IsTreeHomomorphism, IsPosInt]); ############################################################################### ## #O PermOnLevel( , ) ## ## Does the same thing as `Perm'~("Perm"). ## KeyDependentOperation("PermOnLevel", IsTreeHomomorphism, IsPosInt, ReturnTrue); ############################################################################### ## #O Section( , ) ## ## Returns the section of the automorphism (homomorphism) at the vertex . ## The vertex can be a list representing the vertex, or a positive integer ## representing a vertex of the first level of the tree. ## \beginexample ## gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)"); ## < p, q > ## gap> Section(p*q*p^2, [1,2,2,1,2,1]); ## p^2*q^2 ## \endexample ## DeclareOperation("Section", [IsTreeHomomorphism, IsList]); DeclareOperation("Section", [IsTreeHomomorphism, IsPosInt]); ############################################################################### ## #O Sections( [, ] ) ## ## Returns the list of sections of at the -th level. If is omitted ## it is assumed to be 1. ## \beginexample ## gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)"); ## < p, q > ## gap> Sections(p*q*p^2); ## [ p*q^2*p, q*p^2*q ] ## \endexample ## DeclareOperation("Sections", [IsTreeHomomorphism]); DeclareOperation("Sections", [IsTreeHomomorphism, IsCyclotomic]); ############################################################################### ## #O Decompose( [, ] ) ## ## Returns the decomposition of the tree homomorphism on the -th level of the tree, i.e. the ## representation of the form $$a = (a_1, a_2, \ldots, a_{d_1\times...\times d_k})\sigma$$ ## where $a_i$ are the sections of at the -th level, and $\sigma$ is the ## transformation of the -th level. If is omitted it is assumed to be 1. ## \beginexample ## gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)"); ## < p, q > ## gap> Decompose(p*q^2); ## (p*q^2, q*p^2)(1,2) ## gap> Decompose(p*q^2,3); ## (p*q^2, q*p^2, p^2*q, q^2*p, p*q*p, q*p*q, p^3, q^3)(1,8,3,5)(2,7,4,6) ## \endexample ## DeclareOperation("Decompose", [IsTreeHomomorphism]); DeclareOperation("Decompose", [IsTreeHomomorphism, IsPosInt]); DeclareOperation("Decompose", [IsTreeHomomorphism, IsInt and IsZero]); ############################################################################### ## #O Representative( , ) #O Representative( , ) ## ## Given an associative word constructs the tree homomorphism from the family ## , or to which homomorphism belongs. This function is useful when ## one needs to make some operations with associative words. See also `Word' ("Word"). ## \beginexample ## gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)"); ## < p, q > ## gap> F := UnderlyingFreeGroup(L); ## ## gap> r := Representative(F.1*F.2^2, p); ## p*q^2 ## gap> Decompose(r); ## (p*q^2, q*p^2)(1,2) ## gap> H := SelfSimilarGroup("x=(x*y,x)(1,2), y=(x^-1,y)"); ## < x, y > ## gap> F := UnderlyingFreeGroup(H); ## ## gap> r := Representative(F.1^-1*F.2, x); ## x^-1*y ## gap> Decompose(r); ## (x^-1*y, y^-1*x^-2)(1,2) ## \endexample ## DeclareOperation("Representative", [IsAssocWord, IsTreeHomomorphism]); DeclareOperation("Representative", [IsAssocWord, IsTreeHomomorphismFamily]); ############################################################################### ## #O Word( ) ## ## Returns as an associative word (an element of the underlying free group) in ## the generators of the self-similar group (semigroup) to which belongs. ## \beginexample ## gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)"); ## < p, q > ## gap> w := Word(p*q^2*p^-1); ## p*q^2*p^-1 ## gap> Length(w); ## 4 ## \endexample ## DeclareOperation("Word", [IsTreeHomomorphism]); DeclareGlobalFunction("AG_TreeHomomorphismCmp"); ############################################################################# ## #P IsSphericallyTransitive ( ) ## ## Returns whether the action of is spherically transitive (see "Short math background"). ## DeclareProperty("IsSphericallyTransitive", IsTreeHomomorphism); # XXX CanEasilyTestSphericalTransitivity isn't really used except for # automorphisms of binary tree DeclareFilter("CanEasilyTestSphericalTransitivity"); InstallTrueMethod(CanEasilyTestSphericalTransitivity, IsSphericallyTransitive); ############################################################################# ## #O IsTransitiveOnLevel ( , ) ## ## Returns whether acts transitively on level of the tree. ## DeclareOperation("IsTransitiveOnLevel", [IsTreeHomomorphism, IsPosInt]); ############################################################################# ### ##O \^ ( , ) ### ### Returns the image of a vertex under the action of a homomorphism . ### DeclareOperation("\^", [IsList, IsTreeHomomorphism]); ###DeclareOperation("\^", [IsPosInt, IsTreeHomomorphism]); ############################################################################### ## #A AllSections( ) ## ## Returns the list of all sections of if there are finitely many of them and ## this fact can be established using free reduction of words in sections. Otherwise ## will never stop. Note, that in the case when is an element of a self-similar ## (semi)group defined by wreath recurion it does not check whether all elements of the list ## are actually different automorphisms (homomorphisms) of the tree. If is a element of ## of a (semi)group generated by finite automaton, it will always return the list of ## all distinct sections of . ## \beginexample ## gap> D := SelfSimilarGroup("x=(1,y)(1,2), y=(z^-1,1)(1,2), z=(1,x*y)"); ## < x, y, z > ## gap> AllSections(x*y^-1); ## [ x*y^-1, z, 1, x*y, y*z^-1, z^-1*y^-1*x^-1, y^-1*x^-1*z*y^-1, z*y^-1*x*y*z, ## y*z^-1*x*y, z^-1*y^-1*x^-1*y*z^-1, x*y*z, y, z^-1, y^-1*x^-1, z*y^-1 ] ## \endexample ## DeclareAttribute("AllSections", IsTreeHomomorphism); #E