elements.tex

% This file was created automatically from elements.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Properties and operations with group and semigroup elements}

In this chapter we present the functionality applicable to elements of groups and semigroups.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Creation of tree automorphisms and homomorphisms}

\>TreeAutomorphism( <states>, <perm> ) O

Constructs the tree automorphism with states on the first level given by the
argument <states> and acting
on the first level as the permutation <perm>. The <states> must
belong to the same family.
\beginexample
gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> r := TreeAutomorphism([p, q, p, q^2],(1,2)(3,4));
(p, q, p, q^2)(1,2)(3,4)
gap> t := TreeAutomorphism([q, 1, p*q, q],(1,2));
(q, 1, p*q, q)(1,2)
gap> r*t;
(p, q^2, p*q, q^2*p*q)(3,4)
\endexample


\>TreeHomomorphism( <states>, <tr> ) O

Constructs an homomorphism with states <states> and acting
on the first level with transformation <tr>. The <states> 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


\>Representative( <word>, <fam> ) O
\>Representative( <word>, <a> ) O

Given an associative word <word> constructs the tree homomorphism from the family
<fam>, or to which homomorphism <a> 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);
<free group on the generators [ p, q ]>
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);
<free group on the generators [ x, y ]>
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


%Declaration{AutomFamily}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Properties and attributes of tree automorphisms and homomorphisms}

\>`IsSphericallyTransitive( <a> )'{IsSphericallyTransitive}!{[treehom]} P

Returns whether the action of <a> is spherically transitive (see "Short math background").


\>`IsTransitiveOnLevel( <a>, <lev> )'{IsTransitiveOnLevel}!{[treehom]} O

Returns whether <a> acts transitively on level <lev> of the tree.



\>IsOne( <a> ) O

Returns whether an automorphism <a> acts trivially on the tree. For contracting groups see also
`UseContraction' ("UseContraction") and `IsOneContr' ("IsOneContr").
\beginexample
gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> IsOne(q*p^-1*q*p^-1);
true
\endexample

\>IsOneContr( <a> ) F

Returns `true' if <a> is trivial automorphism and `false' otherwise. Works for
contracting groups only. Uses polynomial time algorithm.




\>Order( <a> ) O

Computes the order of an automorphism <a>. In some cases it does not stop. Works always (modulo memory
restrictions) for groups generated by bounded automata.

If `InfoLevel' of `InfoAutomGrp' is greater than or equal to 3 (one can set it by
`SetInfoLevel( InfoAutomGrp, 3)') and the element has infinite order, then the proof of this fact
is printed.

\beginexample
gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> Order(p*q^-1);
2
gap> SetInfoLevel( InfoAutomGrp, 3);
gap> Order( u^35*v^-12*u^2*v^-3 );
#I  (u^35*v^-12*u^2*v^-3)^68719476736 has conjugate of u^2*v^-3*u^35*v^
-12 as a section at vertex [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
infinity
\endexample

\>OrderUsingSections( <a>[, <max_depth>] ) O

Tries to compute the order of the element <a> by looking at its sections
of depth up to <max_depth>-th level.
If <max_depth> is omitted it is assumed to be `infinity', but then it may not stop. Also note,
that if <max_depth> is not given, it searches the tree in depth first and may be trapped
in some infinite ray, while specifying finite <max_depth> may produce a result by looking at
a section not in that ray.
For bounded automata it will always produce a result.

If `InfoLevel' of `InfoAutomGrp' is greater than
or equal to 3 (one can set it by `SetInfoLevel( InfoAutomGrp, 3)')
and the element has infinite order, then the proof of this fact is printed.

\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> OrderUsingSections( a*b*a*c*b );
16
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> SetInfoLevel( InfoAutomGrp, 3);
gap> OrderUsingSections( u^23*v^-2*u^3*v^15, 10 );
#I  v^13*u^15 acts transitively on levels and is obtained from (u^23*v^-2*u^3*v^15)^1
    by taking sections and cyclic reductions at vertex [ 1 ]
infinity
gap> G := AutomatonGroup("a=(c,a)(1,2), b=(b,c), c=(b,a)");
< a, b, c >
gap> OrderUsingSections(b,10);
#I  b*c*a^2*b^2*c*a acts transitively on levels and is obtained from (b)^8
    by taking sections and cyclic reductions at vertex
[ 2, 2, 1, 1, 1, 1, 2, 2, 1, 1 ]
infinity
\endexample


\>Perm( <a>[, <lev>] ) O

Returns the permutation induced by the tree automorphism <a> on the level <lev>
(or first level if <lev> is not given). See also
`TransformationOnLevel'~("TransformationOnLevel").


\>PermOnLevel( <a>, <k> ) O

Does the same thing as `Perm'~("Perm").


\>PermOnLevelAsMatrix( <g>, <lev> ) F

Computes the action of the element <g> of a group on the <lev>-th level as a permutational matrix, in
which the i-th row contains 1 at the position i^<g>.
\beginexample
gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> PermOnLevel(p*q,2);
(1,4)(2,3)
gap> PermOnLevelAsMatrix(p*q, 2);
[ [ 0, 0, 0, 1 ], [ 0, 0, 1, 0 ], [ 0, 1, 0, 0 ], [ 1, 0, 0, 0 ] ]
\endexample


\>TransformationOnLevel( <a>, <lev> ) O
\>TransformationOnFirstLevel( <a> ) O

The first function returns the transformation induced by the tree homomorphism
<a> on the level <lev>. See also `PermOnLevel'~("PermOnLevel").

If the transformation is invertible then it returns a permutation, and
`Transformation' otherwise.

`TransformationOnFirstLevel'(<a>) is equivalent to
`TransformationOnLevel'(<a>, `1').


\>TransformationOnLevelAsMatrix( <g>, <lev> ) F

Computes the action of the element <g> on the <lev>-th level as a permutational matrix, in
which the i-th row contains 1 at the position i^<g>.
\beginexample
gap> L := AutomatonSemigroup("p=(p,q)(1,2), q=(p,q)[1,1]");
< p, q >
gap> TransformationOnLevel(p*q,2);
Transformation( [ 1, 1, 2, 2 ] )
gap> TransformationOnLevelAsMatrix(p*q,2);
[ [ 1, 0, 0, 0 ], [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 1, 0, 0 ] ]
\endexample


\>Word( <a> ) O

Returns <a> as an associative word (an element of the underlying free group) in
the generators of the self-similar group (semigroup) to which <a> 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




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Operations with tree automorphisms and homomorphisms}

The multiplication of tree homomorphisms is defined in the standard way

\>`<a> \* <b>'{product}!{for tree homomorphisms}

The following operations allow computation of the actions of tree
homomorphisms on letters and vertices

\>`<letter> ^ <a>'{action}!{of tree homomorphism on letter}
\>`<vertex> ^ <a>'{action}!{of tree homomorphism on vertex}

\beginexample
gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> 1^p;
2
gap> [1, 2, 2, 1, 2, 1]^(p*q^2);
[ 2, 1, 2, 2, 1, 2 ]
\endexample


The operations below describe how to work with sections of tree homomorphisms.

\>`Section( <a>, <v> )'{Section}!{[treehom]} O

Returns the section of the automorphism (homomorphism) <a> at the vertex <v>.
The vertex <v> 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


\>Sections( <a> [, <lev>] ) O

Returns the list of sections of <a> at the <lev>-th level. If <lev> 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


\>Decompose( <a>[, <k>] ) O

Returns the decomposition of the tree homomorphism <a> on the <k>-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 <a> at the <k>-th level, and $\sigma$ is the
transformation of the <k>-th level. If <k> 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







\>`<a> in <G>'{in}

Returns whether the automorphism <a> belongs to the group <G>. In some cases it does not stop.
\beginexample
gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> H := Group([p^2, q^2]);
< p^2, q^2 >
gap> p in H;
false
\endexample



\>OrbitOfVertex( <ver>, <g>[, <n>] ) O

Returns the list of vertices in the orbit of the vertex <ver> under the
action of the semigroup generated by the automorphism <g>.
If <n> is specified, it returns only the first <n> elements of the orbit.
Vertices are defined either as lists with entries from $\{1,\ldots,d\}$, or as
strings containing characters $1,\ldots,d$, where $d$
is the degree of the tree.
\beginexample
gap> T := AutomatonGroup("t=(1,t)(1,2)");
< t >
gap> OrbitOfVertex([1,1,1], t);
[ [ 1, 1, 1 ], [ 2, 1, 1 ], [ 1, 2, 1 ], [ 2, 2, 1 ], [ 1, 1, 2 ],
  [ 2, 1, 2 ], [ 1, 2, 2 ], [ 2, 2, 2 ] ]
gap> OrbitOfVertex("11111111111", t, 6);
[ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ], [ 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
  [ 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 ], [ 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
  [ 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1 ], [ 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1 ] ]
\endexample


\>PrintOrbitOfVertex( <ver>, <g>[, <n>] ) O

Prints the orbit of the vertex <ver> under the action of the semigroup generated by
<g>. Each vertex is printed as a string containing characters $1,\ldots,d$, where $d$
is the degree of the tree. In case of binary tree the symbols `` '' and ```x'''
are used to represent `1' and `2'.
If <n> is specified only the first <n> elements of the orbit are printed.
Vertices are defined either as lists with entries from $\{1,\ldots,d\}$, or as
strings. See also `OrbitOfVertex' ("OrbitOfVertex").
\beginexample
gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> PrintOrbitOfVertex("2222222222222222222222222222222", p*q^-2, 6);
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
 x x x x x x x x x x x x x x x
x  xx  xx  xx  xx  xx  xx  xx
   x   x   x   x   x   x   x
xxx    xxxx    xxxx    xxxx
 x     x x     x x     x x
gap> H := AutomatonGroup("t=(s,1,1)(1,2,3), s=(t,s,t)(1,2)");
< t, s >
gap> PrintOrbitOfVertex([1,2,1], s^2);
121
132
123
131
122
133
\endexample


\>PermActionOnLevel( <perm>, <big_lev>, <sm_lev>, <deg> ) F

Given a permutation <perm> on the <big_lev>-th level of the tree of degree
<deg> returns the permutation induced by <perm> on a smaller level
<sm_lev>.
\beginexample
gap> PermActionOnLevel((1,4,2,3), 2, 1, 2);
(1,2)
gap> PermActionOnLevel((1,13,5,9,3,15,7,11)(2,14,6,10,4,16,8,12), 4, 2, 2);
(1,4,2,3)
\endexample




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Elements of groups and semigroups defined by wreath recursion}

\>`IsFiniteState( <a> )'{IsFiniteState}!{[selfsim]} P

Returns `true' if <a> has 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 <a> is not finite-state (has
infinitely many different sections).

See also `AllSections' ("AllSections") for the list of all sections and
`MealyAutomaton' ("MealyAutomaton"), which allows to construct
a Mealy automaton whose states are the sections of <a> and which
encodes its action on the tree.
\beginexample
gap> D := SelfSimilarGroup("x=(1,y)(1,2), y=(z^-1,1)(1,2), z=(1,x*y)");
< x, y, z >
gap> IsFiniteState(x*y^-1);
true
\endexample


\>AllSections( <a> ) A

Returns the list of all sections of <a> 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 <a> 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 <a> is a element of
of a (semi)group generated by finite automaton, it will always return the list of
all distinct sections of <a>.
\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



See also operation `MealyAutomaton' ("MealyAutomaton"), which allows to construct
a Mealy automaton whose states are the sections of given tree homomorphism and which
encodes its action on the tree.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Elements of contracting groups}

\>AutomPortrait( <a> ) F
\>AutomPortraitBoundary( <a> ) F
\>AutomPortraitDepth( <a> ) F

Constructs the portrait of an element <a> of a
contracting group $G$. The portrait of <a> is defined recursively as follows.
For $g$ in the nucleus of $G$ the portrait is just $[g]$. For any other
element $g=(g_1,g_2,\ldots,g_d)\sigma$ the portrait of $g$ is
$[\sigma, `AutomPortrait'(g_1),\ldots, `AutomPortrait'(g_d)]$, where $d$ is
the degree of the tree. This structure describes a finite tree whose inner vertices
are labelled by permutations from $S_d$ and the leaves are labelled by
elements from the nucleus. The contraction in $G$ guarantees that the
portrait of any element is finite.

The portraits may be considered as ``normal forms''
of the elements of $G$, since different elements have different portraits.

One also can be interested only in the boundary of a portrait, which consists
of all leaves of the portrait. This boundary can be described by an ordered set of
pairs $[level_i, g_i]$, $i=1,\ldots,r$ representing the leaves of the tree ordered from left
to right (where $level_i$ and $g_i$ are the level and the label of the $i$-th leaf
correspondingly, $r$ is the number of leaves). The operation `AutomPortraitBoundary'(<a>)
computes this boundary.

`AutomPortraitDepth'( <a> ) returns the depth of the portrait, i.e. the minimal
level such that all sections of <a> at this level belong to the nucleus of $G$.

\beginexample
gap> Basilica := AutomatonGroup("u=(v,1)(1,2), v=(u,1)");
< u, v >
gap> AutomPortrait(u^3*v^-2*u);
[ (), [ (), [ (), [ v ], [ v ] ], [ 1 ] ],
  [ (), [ (), [ v ], [ u^-1*v ] ], [ v^-1 ] ] ]
gap> AutomPortrait(u^3*v^-2*u^3);
[ (), [ (), [ (1,2), [ (), [ (), [ v ], [ v ] ], [ 1 ] ], [ v ] ], [ 1 ] ],
  [ (), [ (1,2), [ (), [ (), [ v ], [ v ] ], [ 1 ] ], [ u^-1*v ] ], [ v^-1 ]
     ] ]
gap> AutomPortraitBoundary(u^3*v^-2*u^3);
[ [ 5, v ], [ 5, v ], [ 4, 1 ], [ 3, v ], [ 2, 1 ], [ 5, v ], [ 5, v ],
  [ 4, 1 ], [ 3, u^-1*v ], [ 2, v^-1 ] ]
gap> AutomPortraitDepth(u^3*v^-2*u^3);
5
\endexample




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%