#############################################################################
##
#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