<?xml version="1.0" encoding="ISO-8859-1"?>
<!-- $Id: fr.xml,v 1.42 2008/12/02 12:04:31 gap Exp $ -->
<!DOCTYPE Book SYSTEM "gapdoc.dtd"
[ <!ENTITY see '<Alt Only="LaTeX">$\to$</Alt><Alt Not="LaTeX">--&tgt;</Alt>'>]>
<Book Name="FR">
<TitlePage>
<Title>Functionally recursive groups</Title>
<Subtitle>Self-similar groups</Subtitle>
<Version>Version <#Include Label="Version"></Version>
<TitleComment>
Groups generated by automata or satisfying functional recursions
</TitleComment>
<Author>Laurent Bartholdi
<Email><Alt Only="HTML">laurent dot bartholdi at gmail dot com</Alt>
<Alt Not="HTML">laurent.bartholdi@gmail.com</Alt></Email>
<Homepage>http://www.uni-math.gwdg.de/laurent/</Homepage>
</Author>
<Date>$Date: 2008/12/02 12:04:31 $</Date>
<Address>
Mathematisches Institut, Bunsenstraße 3-5, D-37073 Göttingen<Br/>D-37073 Göttingen<Br/>Germany
</Address>
<Abstract>
This document describes the package <Package>FR</Package>, which
implements in &GAP; the basic objects of Mealy machines and
functional recursions; and handles groups that they generate.
<Alt Only="HTML">
<P/>
The computer algebra system &GAP; is available at
<URL>http://gap-system.org</URL>.
<P/>
This documentation for <Package>FR</Package> is available at
<URL>http://www.uni-math.gwdg.de/laurent/FR/manual.pdf</URL> in PDF
format, and may be accessed online at
<URL>http://www.uni-math.gwdg.de/laurent/FR/</URL>.
<P/>
The latest source of the package may be downloaded as
<URL>http://www.uni-math.gwdg.de/laurent/FR/fr.tar.gz</URL> (tar, gzipped) and
<URL>http://www.uni-math.gwdg.de/laurent/FR/fr.zoo</URL> (zoo).
</Alt>
<P/>
Groups defined by a recursive action on a rooted tree can
be defined in &GAP; via their recursion. Various algorithms are
implemented to manipulate these groups and their elements.
<P/>
For comments or questions on <Package>FR</Package> please contact
the author; this package is still under development.
</Abstract>
<Copyright>©right; 2006-2008 by Laurent Bartholdi
</Copyright>
<Acknowledgements>Part of this work is supported by the "Swiss
National Fund for Scientific Research"
</Acknowledgements>
<Colophon>
This project started in the mid-1990s, when, as a PhD student I did
many calculations with groups generated by automata, and realized
the similarities between all calculations; it quickly became clear
that these calculations could be done much better by a computer than
by a human.
<P/> The first routines I wrote constructed finite representations
of the groups considered, so as to get insight from fast
calculations within &GAP;. The results then had to be proved correct
within the infinite group under consideration, and this often
involved guessing appropriate words in the infinite group with a
given image in the finite quotient.
<P/> Around 2000, I had developed quite a few routines, which I
assembled in a &GAP; package, that dealt directly with infinite
groups. This package was primitive at its core, but was extended
with various routines as they became useful.
<P/> I decided in late 2005 to start a new package from scratch,
that would encorporate as much functionality as possible in a
uniform manner; that would handle semigroups as well as groups; that
could be easily extended; and with a complete, understandable
documentation. I hope I am not too far from these objectives.
</Colophon>
</TitlePage>
<TableOfContents/>
<Body>
<Chapter><Heading>Licensing</Heading>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or any
later version.
<P/> This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
<P/> You should have received a copy of the GNU General Public
License along with this program, in the file COPYING. If not, see
<URL>http://www.gnu.org/licenses/</URL>.
</Chapter>
<Chapter Label="frpackage"><Heading>FR package</Heading>
<Section Label="mathintro"><Heading>A brief mathematical introduction</Heading>
This chapter assumes that you have no familiarity with groups
generated by automata. If you do, and wish to see their usage within
&GAP; through a sample session, please skip to Section <Ref
Label="frintro"/>. For a more thourough introduction on self-similar
groups see <Cite Key="MR2091700"/> or <Cite Key="MR2035113"/>.
<P/>
We shall here be interested in groups <M>G</M> defined by their action
on a regular rooted tree. Let <M>X</M> be a finite set; and let
<M>X^*</M> denote the set of words (free monoid) over <M>X</M>. Then
<M>X^*</M> naturally has the structure of a regular rooted tree: the
root is the empty word, and vertex <M>v \in X^*</M> is connected to
vertex <M>vx</M> for all choices of <M>x \in X</M>. Each vertex except
the root therefore has <M>\#X+1</M> neighbours.
<P/> Let <M>W</M> denote the automorphism group of the graph
<M>X^*</M>. Given <M>a \in W</M>, we may restrict its action to
<M>X \subset X^*</M>, and obtain a permutation <M>\pi_a</M> on
<M>X</M>, called the <E>activity</E> of <M>a</M>. We may also obtain,
for all <M>x\in X</M>, a tree automorphism <M>a_x \in W</M>, called
the <E>state of <M>a</M> at <M>x</M></E>, by the formula
<Display>(v){a_x} = w \quad\textrm{if}\quad (xv)a = x^{\pi_a}w.</Display>
The data <M>(a_x,\pi_a)</M> determine uniquely the automorphism
<M>a</M>, and any choice of <M>a_x</M> and <M>\pi_a</M> defines a tree
isometry. We therefore have a group isomorphism
<Display>\phi: W \to W\wr \mathop{Sym}(X),</Display>
called the <E>Wreath recursion</E>. The image of <M>\phi</M> is the
permutational wreath product <M>W^X \rtimes \mathop{Sym}(X)</M>.
<P/> The state <M>a_x</M> should be interpreted as the restriction of
the action of <M>a</M> on the subtree <M>xX^*</M>; the automorphism
<M>a</M> is defined by acting first on each of the subtrees of the
form <M>xX^*</M> by its respective state, and then permuting these
subtrees according to <M>\pi_a</M>. The wreath recursion can be
iterated on the states of <M>a</M>, to define states <M>a_v</M> for
any <M>v \in X^*</M>.
<P/> The automorphism <M>a \in W</M> may be represented by a graph, as
follows. There is one vertex for each state <M>a_v</M> of <M>a</M>,
labeled <M>\pi_{a_v}</M>; and for each <M>x \in X</M> there is one
edge from state <M>a_v</M> to state <M>a_{vx}</M>, labeled
<M>x</M>. This graph is nothing but a quotient of the regular rooted
tree <M>X^*</M>, where vertices <M>v</M> and <M>w</M> are identified
if <M>a_v=a_w</M>. Again, this graph, with a choice of initial vertex,
determines uniquely the automorphism <M>a</M>. It is called the
<E>Mealy machine</E> associated with <M>a</M>.
<P/> Of particular interest are <E>finite-state automorphisms</E>:
these are automorphisms whose Mealy machine has finitely many
states. The product and inverse of finite-state automorphisms is again
finite-state.
<P/> A subgroup <M>G \le W</M> is <E>self-similar</E> if <M>G^\phi
\subset G\wr\mathop{Sym}(X)</M>. This is equivalent to asking,
for every <M>a \in G</M>, that all of its states <M>a_x</M> also
belong to <M>G</M>.
<P/> The following important properties have also been considered. A
subgroup <M>G \le W</M> is <E>level-transitive</E> if its action is
transitive on all the <M>G</M>-subsets <M>X^n</M>. It is <E>weakly
branched</E> if it is level-transitive, and for every <M>v\in X^*</M>
there is a non-trivial <M>a_v\in G</M> that fixes <M>X^* \setminus
vX^*</M>. It is <E>branched</E> if furthermore for each <M>n \in \mathbb
N</M> the group generated by all such <M>a_v</M> for all <M>v</M> of
length <M>n</M> has finite index in <M>G</M>.
<P/> A self-similar finitely generated group <M>G \le </M> is
<E>contracting</E> if there are constants <M>K,n \in \mathbb N</M> and
<M>\lambda<1</M> such that
<M>|a_v|\le\lambda|a|+K</M> for all <M>a\in G</M> and <M>v\in X^n</M>;
here <M>|a|</M> denotes the minimal number of generators needed to
express <M>a</M>. It then follows that there exists a finite set
<M>N\subset G</M> such that for all <M>a\in G</M>, all but finitely
many of the states of
<M>a</M> belong to <M>N</M>. The minimal such <M>N</M> is called the
<E>nucleus</E> of <M>G</M>. Since the states of elements of the
nucleus are again in the nucleus, we see that the nucleus is naturally
a Mealy machine. By considering all elements of <M>W</M> obtained from
this Mealy machine by choosing all possible initial states, we obtain
a generating set for <M>G</M> made of all states of a single machine;
this is the <E>group generated</E> by the machine.
<P/> In this package, we are mainly interested in self-similar groups
of finite-state automorphisms. The reason is historical: Aleshin <Cite
Key="MR713968"/>, and later Grigorchuk <Cite Key="MR565099"/> and
Gupta and Sidki <Cite Key="MR696534"/> constructed peculiar examples
of groups using self-similar finite-state automorphisms. All these
groups can be defined by drawing a small machine (at most five
vertices) and considering the group that they generate.
<P/> We assumed for simplicity that the elements <M>a</M> were
invertible. Actually, in the definition of Mealy machines it makes
sense to accept arbitrary maps, and not necessarily bijections of
<M>X</M> as a label at each vertex. One may in this way define
peculiar semigroups.
</Section>
<Section Label="frintro"><Heading>An example session</Heading>
This is a brief introduction describing some of the simpler features
of the <Package>FR</Package> package. It assumes you have some
familiarity with the theory of groups defined by automata; if not,
a brief mathematical introduction may be found in Section <Ref
Label="mathintro"/>. We show here and comment a typical use of the
package.
<P/> The package is installed by unpacking the archive in the
<File>pkg/</File> directory of your &GAP; installation. It can also be
placed in a local directory, which must be added to the load-path by
invoking <C>gap</C> with the <C>-l</C> option.
<Example><![CDATA[
gap> LoadPackage("fr");
----------------------------------------------------------------
Loading FR 0.857142p5 (Functionally recursive and automata groups)
by Laurent Bartholdi (http://www.uni-math.gwdg.de/laurent)
----------------------------------------------------------------
true
]]></Example>
Many FR groups are predefined by <Package>FR</Package>, see Chapter <Ref
Label="frexamples"/>. We consider here the <E>Basilica group</E>,
considered in <Cite Key="MR1902367"/> and <Cite Key="MR2176547"/>.
<P/> We may start by defining a group: it has two generators <M>a</M>
and <M>b</M>, satisfying the specified recursions.
<Example><![CDATA[
gap> B := FRGroup("a=<1,b>(1,2)","b=<1,a>":IsFRElement);
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> AssignGeneratorVariables(B);
#I Assigned the global variables [ a, b ]
]]></Example>
We have just created the group <M>B=\langle a,b\rangle</M>.
<P/> Note that this group is predefined as <C>BasilicaGroup</C>. We now
compute the decompositions of the generators:
<Example><![CDATA[
gap> DecompositionOfFRElement(a); DecompositionOfFRElement(b);
[ [ <2|identity ...>, <2|b> ], (1,2) ]
[ [ <2|identity ...>, <2|a> ], () ]
]]></Example>
Elements are described as words in the generators; they are printed as
<C><![CDATA[<2|a>]]></C>, where the <M>2</M> reminds of the degree of
the tree on which <M>a</M> acts.
<P/> The optional argument <Ref Filt="IsFRElement"/> tells
<Package>FR</Package> to store elements in this way. This
representation is always possible, but it is usually inefficient for
calculations. The argument <Ref Filt="IsMealyElement"/> forces
<Package>FR</Package> to use a more efficient representation, which in
some cases may take an infinite time to set up. With no extra
argument, <Package>FR</Package> does what it thinks is best.
<P/> Elements act on sequences over <M>\{1,2\}</M>. The action is
computed in the standard manner:
<Example><![CDATA[
gap> 1^a; [1]^a; [1,1]^a;
2
[ 2 ]
[ 2, 1 ]
]]></Example>
Periodic sequences are also implemented in <Package>FR</Package>; they
are constructed by giving the period and preperiod. The period is
printed by preceding it with a "/":
<Example><![CDATA[
gap> v := PeriodicList([1],[2]);
[ 1, / 2 ]
gap> v^a; v^(a^2);
[/ 2 ]
[/ 1, 2 ]
gap> last{[1..10]};
[ 1, 2, 1, 2, 1, 2, 1, 2, 1, 2 ]
]]></Example>
<P/> Most computations are much more efficient if <M>B</M>'s elements
are converted to <E>Mealy representation</E>,
<Example><![CDATA[
gap> Bm := Image(IsomorphismMealyGroup(B));
<self-similar group over [ 1 .. 2 ] with 2 generators>
gap> a := Bm.1; b := Bm.2;
<Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>
<Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>
]]></Example>
This could have been done automatically by specifying
<C>:IsMealyElement</C> as an option in the call to <C>FRGroup</C>.
<P/> The group <M>B</M> is torsion-free, and its elements are bounded
automata. Although torsion-freeness is difficult to check for
<Package>FR</Package>, it can be checked on individual elements:
<Example><![CDATA[
gap> IsBoundedFRSemigroup(Bm);
true
gap> Order(a); Order(b);
infinity
infinity
gap> g := PseudoRandom(B);; Length(InitialState(g));
4679
gap> Order(g); time;
infinity
2599
]]></Example>
<P/> The group <M>B</M> is weakly branched; more precisely, the
derived subgroup <M>B'</M> contains <M>B' \times B'</M>. To prove
that, it suffices to check <M>[a,b] \times 1\in B'</M> and
<M>1 \times [a,b]\in B'</M>. These elements are constructed using
<Ref Oper="VertexElement"/>:
<Example><![CDATA[
gap> c := Comm(a,b);
<Mealy element on alphabet [ 1, 2 ] with 9 states, initial state 1>
gap> K := NormalClosure(Bm,Group(c));
<self-similar group over [ 1 .. 2 ] with 3 generators>
gap> VertexElement(1,c) in K; VertexElement(1,c) in K;
true
true
gap> DecompositionOfFRElement(VertexElement(1,c)=[[c,One(Bm)],()];
true
gap> VertexElement(2,c)=Comm(b,a^2);
true
]]></Example>
Note that we had to guess the form of the element
<C>VertexElement(2,c)</C> above. This could have been found out by
&GAP; using <Ref Func="ShortGroupWordInSet"/>.
<P/> We may also check the relations <M>[b^p,(b^p)^{a^p}]=1</M> and
<M>[a^{2p},(a^{2p})^{b^p}]</M> for <M>p</M> any power of <M>2</M>:
<Example><![CDATA[
gap> ForAll([0..10],i->IsOne(Comm(b^(2^i),(b^(2^i))^((a^(2^i)))))); time;
true
1361
]]></Example>
Since the group <M>B</M> is bounded, it is contracting. We compute
its nucleus:
<Example><![CDATA[
gap> NucleusOfFRSemigroup(B);
[ <2|identity ...>, <2|b>, <2|b^-1>, <2|a>, <2|a^-1>, <2|b^-1*a>, <2|a^-1*b> ]
]]></Example>
We then compute the Mealy machine with stateset this nucleus, and draw
it graphically (this requires the external programs
<Package>graphviz</Package> and <Package>imagemagick</Package>):
<Example><![CDATA[
gap> N := NucleusMachine(B);
<Mealy machine on alphabet [ 1, 2 ] with 7 states>
gap> Draw(N);
]]></Example>
We may also draw powers of the dual automaton: these are
approximations to the Schreier graph of <M>B</M>. However, we also
construct a smaller Mealy machine with states only <M>a</M> and
<M>b</M>, which give better images:
<Example><![CDATA[
gap> Draw(DualMachine(N)^3);
gap> M := AsMealyMachine(FRMachine(a))[1];
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> Draw(DualMachine(M)^4);
]]></Example>
These Schreier graphs are orbits of the group; they can be displayed
as follows:
<Example><![CDATA[
gap> WordGrowth(B:point:=[1,1,1,1],draw);
]]></Example>
More properties of <M>B</M> can be checked, or experimented with, on
its finite quotients obtained by truncating the tree on which <M>B</M>
acts at a given length. <C>PermGroup(B,n)</C> constructs a permutation
group which is the natural quotient of <M>B</M> acting on <M>2^n</M>
points:
<Example><![CDATA[
gap> G := PermGroup(B,7);
<permutation group with 2 generators>
gap> Size(G); LogInt(last,2);
309485009821345068724781056
88
]]></Example>
We may "guess" the structure of the Lie algebra of <M>B</M> by
examining the ranks of the successive quotients along its Jennings
series:
<Example><![CDATA[
gap> J := JenningsLieAlgebra(G); time;
<Lie algebra of dimension 88 over GF(2)>
18035
gap> List([1..15],i->Dimension(Grading(J).hom_components(i)));
[ 2, 3, 1, 4, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 ]
]]></Example>
The "<M>4</M>" in position <M>8</M> of that list should really be a
"<M>5</M>"; computations on finite quotients of <M>B</M> usually give
lower bounds for invariants of <M>B</M>. In that case, we guess that
the ranks behave like a "ruler" function, i.e. that the rank of the
homogeneous component of degree <M>i</M> is <M>2+\nu_2(i)</M> if
<M>i</M> is a power of <M>2</M> and is <M>1+\nu_2(i)</M> otherwise;
here <M>\nu_2(i)</M> is the number of times <M>2</M> divides <M>i</M>.
</Section>
</Chapter>
<Chapter Label="frmachines"><Heading>Functionally recursive machines</Heading>
At the core of this package are <E>functionally recursive
machines</E>. The internals of machine will be described later, but
each machine <M>M</M> has an associated
<E>alphabet</E> <M>X</M>, a <E>set of states</E> <M>Q</M>, and a
<E>transition function</E> <M>\phi:Q \times X \to X \times Q</M>. An
<E>element</E>, as we will see in Section <Ref
Label="frelements"/>, is given by a machine and an initial state
<M>q\in Q</M>.
<P/> The element <M>(M,q)</M> defines a transformation on the set
<M>X^*</M> of strings (finite or infinite) over the alphabet <M>X</M>,
as follows: the empty string is always fixed. Given a string
<M>x_1x_2\dots x_n</M> with <M>n\ge0</M>, compute
<M>\phi(q,x_1)=(y_1,r)</M>; then compute the action of <M>(M,r)</M> on
the string <M>x_2\dots x_n</M>, and call the result <M>y_2\dots
y_n</M>. Then the action of <M>(M,q)</M> on <M>x_1x_2\dots x_n</M>
yields <M>y_1y_2\dots y_n</M>.
<P/> This can be understood more formally as follows. The transition
function <M>\phi</M> induces a map <M>\phi^n:Q\times X^n \to X^n
\times Q</M>, defined by successively applying <M>\phi</M> to move the
<M>Q</M> from the left to the right. Similarly, <M>\phi</M> can be
extended to a map <M>Q^m\times X^n \to X^n \times Q^m</M>.
<P/> We see that the action on finite strings preserves their length,
and also preserves prefixes: if <M>(M,q)</M> maps <M>x_1\dots x_n</M> to
<M>y_1\dots y_m</M>, then necessarily <M>m=n</M>; and if <M>k<n</M>
then <M>T</M> maps <M>x_1\dots x_k</M> to
<M>y_1\dots y_k</M>.
<P/> The strings over the alphabet <M>X</M> can be naturally organised
into a rooted tree. The root represents the empty string, and the
strings <M>x_1\dots x_n</M> and <M>x_1\dots x_{n+1}</M> are connected
by an edge, for all <M>x_i\in X</M>.
<Section Label="frmachine-types"><Heading>Types of machines</Heading>
Machines must be accessible to computation; therefore it is reasonable
to assume that their alphabet <M>X</M> is finite.
<P/> If the stateset <M>Q</M> is also finite, the machine is called a
<E>Mealy machine</E>, and its transition function <M>\phi</M> can be
stored as a table.
<P/> More general machines are obtained if one allows the stateset
<M>Q</M> to be a free group/semigroup/monoid generated by a finite set
<M>S</M>, and the transition function <M>\phi</M> to be specified on
<M>S\times X</M>. Its values are then extended naturally by
composition.
<P/> Machines store their transitions (second coordinate of
<M>\phi</M>), and their output,
(first coordinate of <M>\phi</M>) in a matrix indexed by state and letter.
In particular, <C>PermList(output[state])</C> gives the action on the first
level.
<P/> Because of the way &GAP; handles permutations and
transformations, a permutation is never equal to a transformation,
even though both can answer <K>true</K> to <M>IsOne</M>. Therefore,
<Package>FR</Package> introduces a new type of transformation, which can
be equal to a permutation, and which is actually represented as a
permutation is it is invertible. Like permutations, the new transformations
do not have a fixed degree. They are created by <C>Trans(list)</C>.
</Section>
<Section Label="frmachine-products"><Heading>Products of machines</Heading>
Machines can be combined in different manners. If two machines act on
the same alphabet, then their <E>sum</E> and <E>product</E> are
defined as machines acting again on the same alphabet; the statesets
are the free products (which is also their sum, in the category of
semigroups) of the respective statesets. The sum or product of
machines has a stateset of highest possible category, i.e. is a group
unless some argument is a monoid, and a monoid unless some argument is
a semigroup. The transition and output functions are the union of the
respective functions of their arguments.
<P/> If a non-empty collection of machines have same stateset, then
their <E>tensor sum</E> and <E>tensor product</E> are machines again
with same stateset; the alphabets on which the machines act are the
disjoint union, respectively cartesian product, of the arguments'
alphabets. The transition and output functions are again the union or
composition of the respective functions of their arguments.
<P/> The <E>direct sum</E> and <E>direct product</E> of a collection
of machines are always defined. Its stateset is generated by the
union of the arguments' statesets, as for a sum or a product; its
alphabet is the disjoint union, respectively cartesian product of its
arguments' alphabets, as for a tensor sum or product. The transition
and output functions are again the union of the respective functions
of their arguments.
</Section>
<Section><Heading>Creators for <C>FRMachine</C>s</Heading>
<#Include Label="FRMachine">
<#Include Label="AsGroupFRMachine">
<#Include Label="ChangeFRMachineBasis">
</Section>
<Section><Heading>Attributes for <C>FRMachine</C>s</Heading>
<#Include Label="StateSet">
<#Include Label="Output/machine">
</Section>
<Section><Heading>Operations for <C>FRMachine</C>s</Heading>
<#Include Label="StructuralGroup">
<#Include Label="+">
<#Include Label="SubFRMachine">
<#Include Label="FR-Minimized">
</Section>
</Chapter>
<Chapter Label="frelements"><Heading>Functionally recursive elements</Heading>
A <E>functionally recursive element</E> is given by a functionally recursive
machine and an initial state <M>q</M>. Many functions for FR
machines, which accept a state as an argument, apply to FR
elements. In that case, no state is passed to the function.
<P/> The main function of FR elements is to serve as
group/monoid/semigroup elements: they can be multiplied and divided,
and they act naturally on sequences. They can also be tested for
equality, and can be sorted.
<P/> FR elements are stored as free group/monoid/semigroup words. They
are printed as <C><n|w></C>, where <C>n</C> is the degree of their
alphabet.
<P/> Equality of FR elements is tested as follows. Given FR elements
<M>(m,q)</M> and <M>(m,r)</M>, we set up a "rewriting system" for
<M>m</M>, which records a purported set of relations among states of
<M>m</M>. We start by an empty rewriting system, and we always ensure
that the rewriting system is reduced and shortlex-reducing. Then, to
compare <M>q</M> and <M>r</M>, we first compare their activities. If
they differ, the elements are distinct. Otherwise, we reduce <M>q</M>
and <M>r</M> using the rewriting system. If the resulting words are
graphically equal, then they are equal. Otherwise, we add the rule
<M>q\to r</M> or <M>r\to q</M> to the rewriting system, and proceed
recursively to compare coordinatewise the states of these reduced
words. As a bonus, we keep the rewriting system to speed up future
comparisons.
<P/> Efficient comparison requires lookup in sorted lists, aka "Sets".
Given two FR elements <M>x</M> and <M>y</M>, we declare that <M>x<y</M>
if, for the shortlex-first sequence <M>l</M> such
that <C>Output(Transition(x,l))</C> and <C>Output(Transition(y,l))</C>
differ, the former is less than the latter (compared as lists).
In fact, a single internal function compares <M>x</M> and <M>y</M> and
returns <M>-1,0,1</M> depending on whether <M>x<y</M> or <M>x=y</M>
or <M>x>y</M>. It traverses, in breadth first fashion, the alphabet
sequences, and stops either when provably <M>x=y</M> or if different
outputs appear.
<Section><Heading>Creators for <C>FRElement</C>s</Heading>
<#Include Label="FRElement">
<#Include Label="AsGroupFRElement">
</Section>
<Section><Heading>Operations and Attributes for <C>FRElement</C>s</Heading>
<#Include Label="Output/element">
<#Include Label="States">
<#Include Label="InitialState">
<#Include Label="^">
</Section>
</Chapter>
<Chapter Label="mealy"><Heading>Mealy machines and elements</Heading>
<E>Mealy machines</E> form a special class of FR machines. They have
as stateset a finite set, as opposed to a free group/monoid/semigroup. All
commands available for FR machines are also available for Mealy
machines, but the latter have added functionality.
<P/> There are currently two types of Mealy machines; one has as
stateset an interval of integers of the form <C>[1..m]</C> and as
alphabet a set of integers; the other has an arbitrary domain as
stateset and alphabet. Almost no functionality is implemented for the
latter type, but there is a function converting it to the former type
(see <Ref Attr="AsMealyMachine" Label="FR machine"/>).
<P/> The internal representation of a Mealy machine of the first kind
is quite different from that of FR machines. The alphabet is assumed
to be an interval <C>[1..n]</C>, and the stateset is assumed to be an interval
<C>[1..m]</C>. The transitions are stored as a <M>m \times n</M>
matrix, and the outputs are stored in a list of length <M>m</M>,
consisting of permutations or transformations.
<P/> Mealy machines have additional properties, in particular they can
act on periodic sequences (see <Ref Oper="PeriodicList"/>). For
example, the periodic sequence <C>PeriodicList([1],[1,2])</C>
describes the infinite ray <C>[1,1,2,1,2,..]</C> in the tree. In
principle, Mealy machines could act on sequences accepted by an
automaton, although this is not yet implemented.
<P/> Mealy elements are Mealy machines with an initial state. For
efficiency reasons, Mealy elements are always minimized, and their
states are ordered in a canonical top-down, left-to-right order of
traversal of the tree. In particular, their initial state is always 1.
In this implementation, multiplication of Mealy
elements is slower than multiplication of group FR elements, while
comparison of Mealy elements is faster than comparison of group FR
elements. In practise, it is better to work with Mealy elements as
often as possible.
<P/> Products of Mealy machines behave in the same way as products of
general FR machines, see <Ref Label="frmachine-products"/>. The only
difference is that now the sum and products of statesets are distinct;
the sum of statesets being their disjoint union, and their product
being their cartesian product.
<Section><Heading>Creators for <C>MealyMachine</C>s and <C>MealyElement</C>s</Heading>
<#Include Label="MealyMachine">
<#Include Label="AllMealyMachines">
</Section>
<Section><Heading>Operations and Attributes for <C>MealyMachine</C>s and <C>MealyElement</C>s</Heading>
<#Include Label="Draw">
<#Include Label="MM-Minimized">
<#Include Label="DualMachine">
<#Include Label="StateGrowth">
<#Include Label="Signatures">
<#Include Label="AsMealyMachine">
<#Include Label="ConfinalityClasses">
<#Include Label="LimitMachine">
<#Include Label="GuessMealyElement">
</Section>
</Chapter>
<Chapter Label="vector"><Heading>Linear machines and elements</Heading>
<E>Linear</E> machines are a special class of FR machines, in which
the stateset <M>Q</M> and the alphabet <M>X</M> are vector spaces over
a field <M>\Bbbk</M>, and the transition map <M>\phi: Q\otimes X\to
X\otimes Q</M> is a linear map; furthermore, there is a functional
<M>\pi:Q\to\Bbbk</M> called the <E>output</E>.
<P/>As before, a choice of initial state <M>q\in Q</M> induces a
linear map <M>q:T(X)\to T(X)</M>, where <M>T(X)=\bigoplus X^{\otimes
n}</M> is the tensor algebra generated by <M>X</M>. This map is
defined as follows: given <M>x=x_1\otimes\dots\otimes x_n\in T(X)</M>,
rewrite <M>q\otimes x</M> as a sum of expressions of
the form <M>y\otimes r</M> with <M>y\in T(X)</M> and <M>r\in Q</M>;
then <M>q</M>, by definition, maps <M>x</M> to the sum of the
<M>\pi(r)y</M>.
<P/> There are two sorts of linear machines: <E>vector machines</E>,
for which the state space is a finite-dimensional vector space over a
field; and <E>algebra machines</E>, for which the state space is a
free algebra in a finite set of variables.
<P/> In a vector machine, the transition and output maps are stored as
a matrix and a vector respectively. Minimization algorithms are
implemented, as for Mealy machines.
<P/> In an algebra machine, the transition and output maps are stored
as words in the algebra. These machines are natural extensions of
group/monoid/semigroup machines.
<P/> Linear elements are given by a linear machine and an initial
state. They can be added and multiplied, and act on the tensor algebra
of the alphabet, admitting natural representations as matrices.
<Section><Heading>Methods and operations for <C>LinearFRMachine</C>s and <C>LinearFRElement</C>s</Heading>
<#Include Label="VectorMachine">
<#Include Label="AlgebraMachine">
<#Include Label="Transitions">
<#Include Label="AsLinearMachine">
</Section>
</Chapter>
<Chapter Label="group"><Heading>Self-similar groups, monoids and semigroups</Heading>
Self-similar groups, monoids and semigroups (below <E>FR
semigroups</E>) are simply groups, monoids and semigroups whose
elements are FR machines. They naturally act on the alphabet of their
elements, and on sequences over that alphabet.
<P/> Most non-trivial calculations in FR groups are performed as
follows: &GAP; searches through words of short length in the
generating set of a FR group to find a solution to a group-theoretic
question, and at the same time searches through the finite quotients
to prove the inexistence of a solution. Usually the calculation ends
with the answer <K>maybe</K>, which means that no definite answer,
neither positive nor negative, could be found; however, the cases
where the calculation actually terminates have been most useful.
<P/> The maximal length of words to consider in the search is
controlled by the variable <C>FR&uscore;SEARCH.radius</C> (initially 10),
and the maximal depth of the tree in which to search is controlled by
the variable <C>FR&uscore;SEARCH.depth</C> (initially 6). These limits can be
modified in any function call using &GAP;'s options mechanism, e.g. in
<C>Index(G,H:FRdepth:=5,FRradius:=5)</C>.
<Section><Heading>Creators for FR semigroups</Heading>
The most straightforward creation method for FR groups is
<C>Group()</C>, applied with FR elements as arguments. There are
shortcuts to this somewhat tedious method:
<#Include Label="FRGroup">
<#Include Label="SCGroup">
<#Include Label="FullSCGroup">
<#Include Label="IsomorphismFRGroup">
<#Include Label="FRGroupByVirtualEndomorphism">
<#Include Label="Products">
</Section>
<Section><Heading>Operations for FR semigroups</Heading>
<#Include Label="PermGroup">
<#Include Label="StabilizerImage">
<#Include Label="IsStateClosed">
<#Include Label="IsFinitary">
<#Include Label="IsContracting">
<#Include Label="IsBranched">
<#Include Label="VertexTransformations">
<#Include Label="VirtualEndomorphism">
<#Include Label="EpimorphismFromFpGroup">
</Section>
<Section><Heading>Properties for infinite groups</Heading>
<#Include Label="IsTorsionGroup">
</Section>
</Chapter>
<Chapter Label="algebras"><Heading>Algebras</Heading>
Self-similar algebras and algebras with one (below <E>FR
algebras</E>) are simply algebras [with one] whose
elements are linear FR machines. They naturally act on the alphabet of their
elements, which is a vector space.
<P/> Elements may be added, subtracted and multiplied. They can be
vector or algebra linear elements; the vector elements are in general
preferable, for efficiency reasons.
<P/> Finite-dimensional approximations of self-similar algebras can be
computed; they are given as matrix algebras.
<Section><Heading>Creators for FR algebras</Heading>
The most straightforward creation method for FR algebras is
<C>Algebra()</C>, applied with linear FR elements as arguments. There are
shortcuts to this somewhat tedious method:
<#Include Label="FRAlgebra">
<#Include Label="SCAlgebra">
</Section>
<Section><Heading>Operations for FR algebras</Heading>
<#Include Label="MatrixQuotient">
<#Include Label="ThinnedAlgebra">
<#Include Label="Nillity">
</Section>
</Chapter>
<Chapter Label="img"><Heading>Iterated monodromy groups</Heading>
Iterated monodromy machines are a special class of group FR machines
(see Section <Ref Label="frmachines"/>) with attribute <Ref
Oper="IMGRelator"/>. This attribute records a cyclic ordering of the
generators of the machine whose product is trivial.
<P/> The interpretation is the following: the machine encodes a
<E>Thurston map</E>, i.e. a post-critically finite topological
branched self-covering of the sphere <M>S^2</M>. Generators of the
machine correspond to loops in the fundamental group of the sphere
(punctured at post-critical points), that circle once
counter-clockwise around a post-critical point. For more details on
the connection between self-similar groups and Thurston maps, see
<Cite Key="MR2162164"/>.
<P/> IMG FR elements are a bit different from group FR elements: while
we said a group FR element is trivial if and only if its action on
sequences is trivial, we say that an IMG FR element <M>g</M> is
trivial if there exists an integer <M>N</M> such that unfolding
<M>N</M> times the recursion for <M>g</M> yields only trivial states
(as elements of the underlying free group).
<Section><Heading>Creators and operations for IMG FR machines</Heading>
<#Include Label="IMGFRMachine">
<#Include Label="DBRationalIMGGroup">
</Section>
<Section><Heading>Spiders</Heading>
<#Include Label="Spiders">
</Section>
</Chapter>
<Chapter Label="frexamples"><Heading>Examples</Heading>
<Package>FR</Package> predefines a large collection of machines and
groups. The groups are, whenever possible, defined as state closures
of corresponding Mealy machines.
<Section><Heading>Examples of groups</Heading>
<#Include Label="FiniteDepthBinaryGroup">
<#Include Label="BinaryKneadingGroup">
<#Include Label="AddingMachine">
<#Include Label="MixerMachine">
<#Include Label="SunicMachine">
<#Include Label="GrigorchukGroup">
<#Include Label="BrunnerSidkiVieiraMachine">
<#Include Label="AleshinMachine">
<#Include Label="GuptaSidkiMachines">
<#Include Label="GammaPQ">
<#Include Label="OtherGroups">
<#Include Label="FRAffineGroup">
</Section>
<Section><Heading>Examples of semigroups</Heading>
<#Include Label="I2Machine">
</Section>
<Section><Heading>Examples of algebras</Heading>
<#Include Label="PSZAlgebra">
</Section>
<Section Label="bacher"><Heading>Bacher's determinant identities</Heading>
In his paper <Cite Key="bacher"/>, Roland Bacher exhibits striking
formulas for determinants of matrices obtained from binomial
coefficients.
<P/> The general construction is as follows: let <M>P</M> be an
infinite matrix, and let <M>P(n)</M> be its upper <M>n\times n</M>
corner. To evaluate <M>\det P(n)</M>, decompose <M>P=LDR</M> where
<M>L,D,R</M> are respectively lower triangular, diagonal, and upper
triangular, with 1's on the diagonals of <M>L</M> and <M>R</M>. Then
that determinant is the product of the first <M>n</M> entries of
<M>D</M>.
<P/> Bacher considers some natural examples of matrices arising from
binomial coefficients, and notes that the matrix <M>P</M> is the limit
of a convergent vector element (see <Ref Oper="IsConvergent"/>). He
also notes that the decomposition <M>P=LDR</M> may be achieved within
vector elements.
<P/> As a first example, consider the <M>n\times n</M> matrix
<M>P(n)</M> with coefficients <M>P_{s,t}={s+t \choose s}\pmod
2</M>. Here and below, indices start at 0. Let also <M>ds(n)</M>
denote the digit-sum of the integer
<M>n</M>. Then
<Display>\det(P(n))=\cases{
(-1)^{n/2} & if $n$ is even,\cr
(-1)^{(n-1)/2+ds((n-1)/2)} & if $n$ is odd.}
</Display>
For the proof, note that <M>P</M> is a convergent infinite matrix; it
may be presented as a self-similar linear element by
<C>FRAlgebra("P=[[P,P],[P,0]]")</C>. It then suffices to construct an
LR decomposition of <M>P</M> within FR vector elements, following
Bacher:
<Example><![CDATA[
gap> AssignGeneratorVariables(FRAlgebra(Rationals,
"P=[[P,P],[P,0]]","L=[[L,0],[L,L]]","D=[[D,0],[0,-D]]"));
gap> L*D*TransposedFRElement(L)=P;
true
]]></Example>
and to analyse the elements of the diagonal matrix <M>D</M>.
<P/> For a more complicated example, let <M>v_2</M> denote 2-valuation
of a rational, and construct the <M>n\times n</M> matrix <M>V(n)</M>
with coefficients <M>V_{s,t}=i^{v_2({s+t \choose s})}</M>. Then
<Display>\det(V(n))=\det(P(n))\prod_{k=1}^{n-1}(1-f(k)i),</Display>
where <M>f(k)</M> is the regular paper-folding sequence defined by
<M>f(2^n)=1</M> and <M>f(2^n+a)=-f(2^n-a)</M> for <M>1\le a<2^n</M>.
<P/> This is again proved by noticing that <M>V</M> is a corner in a
self-similar element, namely
<Example><![CDATA[
gap> AssignGeneratorVariables(FRAlgebra(GaussianRationals,
"V1=[[V1,V2],[V2,E(4)*V1]]",
"V2=[[V1,-E(4)*V1+(1+E(4))*V2],[-E(4)*V1+(1+E(4))*V2,-V1]]"));
gap> Activity(V1,3)=
List([0..7],s->List([0..7],t->E(4)^ValuationInt(Binomial(s+t,s),2)));
true
]]></Example>
The LR decomposition of <M>V=V1</M> can be checked as follows:
<Example><![CDATA[
gap> AssignGeneratorVariables(FRAlgebra(GaussianRationals,
"L1=[[L1,0],[L3,L4]]",
"L2=[[0,-E(4)*L2],[-L1+L3,-E(4)*L2-E(4)*L4]]:0",
"L3=[[L1,L2],[-E(4)*L1+(1+E(4))*L3,L2+(1+E(4))*L4]]",
"L4=[[L1,0],[(1-E(4))*L1+E(4)*L3,L4]]",
"D1=[[D1,0],[0,D2]]",
"D2=[[D3,0],[0,2*D1-D2+2*D3]]:-1+E(4)",
"D3=[[D3,0],[0,-D2]]:-1+E(4)"));
gap> L1*D1*TransposedFRElement(L1)=V1;
true
]]></Example>
The LR decomposition can also, in favourable situations, be discovered
by <Package>FR</Package> through the command <Ref
Oper="LDUDecompositionFRElement"/>. This approach will be followed below.
<P/> For the next example, consider "Beeblebrox reduction"
<M>\beta(4k\pm1)=\pm1,\beta(2k)=0</M>, and construct the <M>n\times
n</M> matrix <M>Z(n)</M> (named after Zaphod Beeblebrox) with
coefficients
<M>Z_{s,t}=\beta({s+t \choose s})</M>. Then
<Display>\det(Z(n))=\prod_{k=1}^{n-1}g(k),</Display>
where <M>g(\sum
a_i2^i)=(-1)^{a_0}3^{\#\{i:a_i=a_{i+1}=1\}-\#\{i:a_i\neq
a_{i+1}=1\}}</M> with all <M>a_i\in\{0,1\}</M>.
<P/> This is again proved by noticing that <M>Z</M> is a corner in a
self-similar element, namely
<Example><![CDATA[
gap> beta := n->Jacobi(-1,n)*(n mod 2);;
gap> Zaphod := GuessVectorElement(List([0..7],i->List([0..7],j->beta(Binomial(i+j,j)))));
<Linear element on alphabet Rationals^2 with 3-dimensional stateset>
gap> Display(Zaphod);
Rationals | 1 | 2 |
-----------+----------+----------+
1 | 1 0 0 | 0 1 0 |
| 1 0 0 | 0 1 0 |
| 1 0 0 | 0 -1 0 |
-----------+----------+----------+
2 | 0 0 1 | 0 0 0 |
| 0 0 -1 | 0 0 0 |
| 0 0 1 | 0 0 0 |
-----------+----------+----------+
Output: 1 1 1
Initial state: 1 0 0
gap> LDUDecompositionFRElement(guessZ);
[ <Linear element on alphabet Rationals^2 with 4-dimensional stateset>,
<Linear element on alphabet Rationals^2 with 2-dimensional stateset>,
<Linear element on alphabet Rationals^2 with 4-dimensional stateset> ]
gap> Display(last[2]);
Rationals | 1 | 2 |
-----------+---------+---------+
1 | 1 0 | 0 0 |
| 3 0 | 0 0 |
-----------+---------+---------+
2 | 0 0 | 0 1 |
| 0 0 | 0 1/3 |
-----------+---------+---------+
Output: 1 -1
Initial state: 1 0
]]></Example>
and now the recursion read on this diagonal self-similar matrix gives
immediately Bacher's recursion for <M>\det(Z(n))</M>.
<P/> Bacher notes that the group generated by
<M>a=L_1,b=L_2/2,c=L_3,d=L_4</M> in the last example may be of
interest. A quick check produces the following relations (slightly
rewritten):
<Example><![CDATA[
gap> AssignGeneratorVariables(FRAlgebra(Rationals,
"a=[[a,0],[c,d]]","b=[[-1/3*a,2*b],[1/3*c,d]]",
"c=[[a,2*b],[c,d]]","d=[[a,0],[1/3*c,d]]"));
gap> g := Group(List([a,b,c,d], x->Activity(x,3)));
<matrix group with 4 generators>
gap> FindShortGroupRelations(g,10);
[ b*d^-1*c*a^-1,
c*a^-1*c*a^-1,
c*a*d^-1*a^-1*d^2*a^-1*b^-1,
c*a*d^-1*c^-1*b*d*a^-1*b^-1,
c*d*a^-2*d*a*d^-1*b^-1,
c*a^2*d^-1*a^-2*d*a*d*a^-2*b^-1,
d^2*a*d^-2*b^-1*c*a*d*a^-3,
c*d*a*d^-2*a^-1*d*a*d*a^-2*b^-1 ]
]]></Example>
Consider next the "triangular Beeblebrox matrix" with
entries <M>L_{s,t}=\beta({s \choose t})</M>. The recurrence is now
given by
<Example><![CDATA[
gap> A := FRAlgebra(Rationals,
"L1=[[L1,0],[L2,L3]]",
"L2=[[L1,0],[L2,-L3]]",
"L3=[[L1,0],[-L2,L3]]");
<self-similar algebra on alphabet Rationals^2 with 3 generators>
]]></Example>
and it is striking that <M>A</M> is a graded algebra, with
<M>L_1,L_2,L_3</M> homogeneous of degree 1, and each homogeneous
component is 3-dimensional; all of <M>L_1,L_2,L_3</M> are invertible
(with inverses have degree <M>-1</M>), and generate a group that
admits a faithful <M>3\times 3</M> linear representation.
As a final example, Bacher considers the "Jacobi character"
<M>\chi(8&ZZ;\pm1)=1,\chi(8&ZZ;\pm3)=-1,\chi(2&ZZ;)=0</M>, and the
associated matrix <M>J_{s,t}=\chi({s+t \choose s})</M>. He gives an
easily-computed, but complicated formula for <M>\det(J(n))</M>. We can
recover this formula, as before, by "guessing" an LR decomposition for
<M>J</M>, which is self-similar and convergent:
<Example><![CDATA[
gap> chi := function(x)
if x mod 8 in [1,7] then return 1;
elif x mod 8 in [3,5] then return -1;
else return 0; fi;
end;;
gap> m := List([0..63],i->List([0..63],j->chi(Binomial(i+j,j))));;
gap> J := GuessVectorElement(m,2);
<Linear element on alphabet Rationals^2 with 9-dimensional stateset>
gap> LDUDecompositionFRElement(J);
[ <Linear element on alphabet Rationals^2 with 20-dimensional stateset>,
<Linear element on alphabet Rationals^2 with 4-dimensional stateset>,
<Linear element on alphabet Rationals^2 with 20-dimensional stateset> ]
gap> time;
26869
gap> Display(last2[2]);
Rationals | 1 | 2 |
-----------+-----------------+-----------------+
1 | 1 0 0 0 | 0 0 0 0 |
| 0 0 1 0 | 0 0 0 0 |
| 3 0 0 0 | 0 0 0 0 |
| 0 0 3 0 | 0 0 0 0 |
-----------+-----------------+-----------------+
2 | 0 0 0 0 | 0 1 0 0 |
| 0 0 0 0 | 0 0 0 1 |
| 0 0 0 0 | 0 1/3 0 0 |
| 0 0 0 0 | 0 0 0 1/3 |
-----------+-----------------+-----------------+
Output: 1 -1 3 -1/3
Initial state: 1 0 0 0
]]></Example>
</Section>
<Section Label="vhgroups"><Heading>VH groups</Heading>
[!!! introduction to do]
<#Include Label="VHGroup">
</Section>
</Chapter>
<Chapter><Heading>FR implementation details</Heading>
<Package>FR</Package> creates new categories for the various objects
considered in the package. The first category is <C>FRObject</C>; all
objects are in this category, and have an <C>Alphabet</C> method.
<P/> There are two categories below: <C>FRMachine</C> and
<C>FRElement</C>. An <C>FRMachine</C> must have a <C>StateSet</C>, and
methods for <C>Output</C> and a <C>Transition</C>. An <C>FRElement</C>
must have an underlying <C>FRMachine</C> and <C>InitialState</C>, and
<C>Output</C> and a <C>Transition</C> that use the initial state.
<P/> A self-similar group is simply a collections category of FR
elements which is also a group.
<Section><Heading>The family of FR objects</Heading> All FR objects
have an associated <Ref Attr="AlphabetOfFRObject"/>.
<#Include Label="FRMFamily">
<#Include Label="FREFamily">
<#Include Label="AlphabetOfFRObject">
<ManSection>
<Meth Name="AsPermutation" Arg="o" Label="FR object"/>
<Description>
This method takes as argument an FR object <A>o</A>: machine, element, or
group, and produces an equivalent object whose outputs are
permutations. In particular, it converts Mealy machines from
domain representation to int representation.
<P/> If this is not possible, the method returns <K>fail</K>.
</Description>
</ManSection>
<ManSection>
<Meth Name="AsTransformation" Arg="o" Label="FR object"/>
<Description>
This method takes as argument an FR object <A>o</A>: machine, element, or
group, and produces an equivalent object whose outputs are
transformations. In particular, it converts Mealy machines from
domain representation to int representation.
<P/> Since transformations can never be inverted by &GAP;, even
when they are invertible, this function returns a monoid when
applied to a full SC group.
</Description>
</ManSection>
</Section>
<Section><Heading>Filters for <C>FRObject</C>s</Heading>
<#Include Label="IsGroupFRMachine">
<#Include Label="IsFRMachineStdRep">
<#Include Label="IsMealyMachine">
<#Include Label="IsMealyMachineIntRep">
<#Include Label="IsVectorFRMachineRep">
<#Include Label="IsAlgebraFRMachineRep">
<#Include Label="IsLinearFRMachine">
<#Include Label="IsFRElement">
<#Include Label="IsFRObject">
<#Include Label="IsInvertible">
<#Include Label="IsFRGroup">
<#Include Label="IsFRAlgebra">
</Section>
<Section><Heading>Some of the algorithms implemented</Heading>
Few calculations with infinite groups can be guaranteed to terminate
--- and especially to terminate within reasonable time. This section
describes some of the algorithms implemented in <Package>FR</Package>.
<#Include Label="FRMachineRWS">
<Subsection><Heading>Order of FR elements</Heading>
<P/> The order of an FR element <C>e</C> is computed as follows: the
tree is traversed recursively, filling it as follows. For each cycle
of <C>e</C> on the first level, the product of the states on that
cycle are computed. The method continues recursively with that product,
remembering the order of the cycle. Once a state reappears in the
traversal, <Package>FR</Package> determines if one instance of the
state is in the subtree of the other, and if so whether the top one
was raised to a non-trivial power to yield the second one as a
state. If this happens, then <C>e</C> has infinite order. Otherwise,
the least common multiple of the powers that appeared in the traversal
is returned.
<P/> This method is guaranteed to succeed if <C>e</C> is a bounded
element. To improve chances of success, <Package>FR</Package> first
computes whether <C>e</C> acts by vertex transformations belonging to
an abelian group; and if so, if <C>e</C> is conjugate to an adding
machine. In that case too, <C>e</C> has infinite order.
</Subsection>
<Subsection><Heading>Membership in semigroups</Heading>
The following algorithm is used to determine whether a Mealy element
belongs to a self-similar group. The corresponding problem of
membership of an FR element in a state-closed self-similar group can
be much simpler, because an FR element has an associated FR machine,
all of whose states belong to the group.
<P/> Assume the group is given by generators. <Package>FR</Package>
attempts to express the given Mealy element as a product of
generators. At the same time, it constructs epimorphisms to finite
groups. It is hoped that one of these two processes will stop.
<P/> This amounts, in fact, to the following. Consider a group
<M>G</M> acting on a tree. It has a natural, profinite closure
<M>\overline G</M>. The algorithm then attempts either to write an
element <M>x</M> as a product of generators of <A>G</A>, or to show
that <M>x</M> does not belong to <M>\overline G</M>.
<P/> There are groups <M>G</M> such that <M>\overline G\setminus G</M>
contains Mealy machines. For these, the above algorithm will not
terminate.
<P/> An additional refinement is implemented for bounded groups (see
<Ref Prop="IsBoundedFRSemigroup"/>). The <Ref Attr="Germs"/>
of an element are computed, and compared to the germs of elements in
the group.
<P/> Finally, for a group that possesses self-similar data (see
Section <Ref Label="preimages"/>), very fast methods are implemented
to recognize and express an FR element as a product of generators.
</Subsection>
<Subsection><Heading>Order of groups</Heading>
<P/> The order of an FR group is computed as follows: if all
generators are finitary, then enumeration will succeed in computing
the order. If the action of the group is primitive, and it comes from
a bireversible automaton, then the Thompson-Wielandt theorem is tested
against. This theorem states that, in our context (a group acting on a
rooted tree, coming from a larger group acting transitively), if the
group is finite then the stabilizer of a sphere of radius 2 is a
<M>p</M>-group; see <Cite Key="MR1839488" Where="Proposition 2.1.1"/>.
Then, <Package>FR</Package> attempts to find whether the group is
level-transitive (in which case it would be infinite). Finally, it
attempts to enumerate the group's elements, testing at the same time
whether these elements have infinite order.
<P/> Needless to say, none except the first few steps are guaranteed
to succeed.
</Subsection>
<Subsection Label="preimages"><Heading>Images and preimages of some groups in
f.p. and l.p. groups</Heading>
Contracting, branched groups admit finite L-presentations (see <Cite
Key="MR2009317"/>), that is, presentations by finitely many
generators, relators and endomorphisms; the (usual) relators are the
images of the given relators under iteration by all endomorphisms.
<P/> Using the package <Package>NQL</Package>, it is possible to
construct infinite nilpotent quotients of self-similar groups, and
perform fast computations in them.
<P/> It is possible to construct, algorithmically, such an L-presentation
from a self-similar groups; however, this algorithm has not been
implemented yet, mainly because efficiency issues would make it usable
only in very few cases.
<P/> For groups with an isomorphism to an L-presented group
(constructed by <Ref Oper="IsomorphismLpGroup"/>), a fast method
expresses group elements as words in the L-presented group's
generators. It proceeds recursively on the decomposition of the
element, mapping elements that are expressible by short words over
the nucleus (usually length 1; length 3 is needed for the
<Ref Var="BrunnerSidkiVieiraGroup"/>) to their value in the
L-presented group, and using the presentation's endomorphism to
construct words with appropriate decompositions.
<P/> In particular, the algorithm will stop, returning <K>fail</K>,
if during the recursion it reaches an element <M>x</M> such that
<M>x</M> is a state of <M>x</M> but <M>x</M> does not belong to the
nucleus.
</Subsection>
<Subsection Label="sorting"><Heading>Comparison of FR, Mealy, vector,
and algebra elements</Heading>
FR and Mealy elements can be compared quite efficiently, as long as
they are distinct. The algorithm runs as follows: let the two
elements be <M>x</M> and <M>y</M>. Considering both in turn,
<Package>FR</Package> constructs the first entries of minimal Mealy
elements expressing <M>x</M> and <M>y</M>; as soon as an output entry
is distinct for <M>x</M> and for <M>y</M>, the status of
<M>x<y</M> is determined; and similarly for transition entries.
Finally, if either of <M>x</M> or <M>y</M> is finite-state and the
entries were identical up to that step, then the element with
smallest stateset is considered smaller.
<P/> In this way, FR and Mealy elements can efficiently be
compared. For Mealy elements, it suffices to follow their internal
data; while for FR elements, this amounts to constructing Mealy
elements approximating them to a sufficient precision so that they
can be compared as such.
<P/> The algorithm first tries to test its arguments for equality;
this test is not guaranteed to succeed.
<P/> A similar algorithm applies for linear elements. Here, one
constructs vector element approximations; and compares, for
ever-increasing values of <M>i</M>, first the output vectors of
basis state <M>i</M>; then the transitions from state <M>i</M> to
state <M>j</M>, for all <M>j\in\{1,\dots,i\}</M>; then the
transitions from state <M>j</M> to state <M>i</M> for all
<M>j\in\{1,\dots,i-1\}</M>.
</Subsection>
<Subsection><Heading>Inverses of linear elements</Heading>
It is probably difficult to compute the inverse of a
vector element. The following approach is used: to compute the inverse
of <M>x</M>, large (scalar) matrix approximations of <M>x</M> are
computed; they are inverted using linear algebra; a vector element
representing this inverse is guessed; and the guess is checked. As
long as that check fails, larger approximations are computed.
<P/> Needless to say, this method need not succeed; for there are
vector elements that are invertible, but whose inverse is not a vector
element. A good test example appears in <Cite Key="bacher"/>: consider
the infinite matrix with 1's on the diagonal, and <M>\omega</M> below
the diagonal. This element admits an inverse if and only if
<M>\omega</M> is a root of unity. The complexity of the inverse grows
as the degree of <M>\omega</M> grows. Here is an illustation:
<Example><![CDATA[
gap> bacher := function(n)
local f;
f := CyclotomicField(n);
return VectorElement(f,One(f)*[[[[1,0],[0,0]],
[[0,0],[0,1]]],[[[0,1],[0,0]],[[1,0],[0,0]]]],[One(f),E(n)],[One(f),Zero(f)]);
end;;
gap> Inverse(bacher(3));
<Linear element on alphabet CF(3)^2 with 4-dimensional stateset>
6 gap> Inverse(bacher(5));
<Linear element on alphabet CF(5)^2 with 6-dimensional stateset>
]]></Example>
<Table Align="r|cccccccccc">
<Caption>Dimension of states of inverse</Caption>
<Row>
<Item><M>n</M></Item>
<Item>1</Item><Item>2</Item><Item>3</Item><Item>4</Item><Item>5</Item>
<Item>6</Item><Item>7</Item><Item>8</Item><Item>9</Item><Item>10</Item>
</Row>
<Row>
<Item>dimension</Item>
<Item></Item><Item>2</Item><Item>4</Item><Item>4</Item><Item>6</Item>
<Item>3</Item><Item>5</Item><Item>5</Item><Item>8</Item><Item>5</Item>
</Row>
<HorLine/>
<Row>
<Item><M>n</M></Item>
<Item>11</Item><Item>12</Item><Item>13</Item><Item>14</Item><Item>15</Item>
<Item>16</Item><Item>17</Item><Item>18</Item><Item>19</Item><Item>20</Item>
</Row>
<Row>
<Item>dimension</Item>
<Item>?</Item><Item>5</Item><Item>?</Item><Item>4</Item><Item>6</Item>
<Item>6</Item><Item>?</Item><Item>7</Item><Item>?</Item><Item>7</Item>
</Row>
<HorLine/>
<Row>
<Item><M>n</M></Item>
<Item>22</Item><Item>24</Item><Item>26</Item><Item>28</Item><Item>30</Item>
<Item>32</Item><Item>34</Item><Item>36</Item><Item>38</Item><Item>40</Item>
</Row>
<Row>
<Item>dimension</Item>
<Item>?</Item><Item>6</Item><Item>?</Item><Item>6</Item><Item>?</Item>
<Item>7</Item><Item>?</Item><Item>?</Item><Item>?</Item><Item>?</Item>
</Row>
</Table>
</Subsection>
</Section>
</Chapter>
<Chapter><Heading>Miscellanea</Heading>
<Section><Heading>Helpers</Heading>
<#Include Label="Maybe">
<#Include Label="TensorSum">
<#Include Label="PeriodicLists">
<#Include Label="WordGrowth">
<#Include Label="ShortMonoidRelations">
<#Include Label="Braids">
<#Include Label="Helpers">
<#Include Label="FIFOs">
<#Include Label="LowerCentralSeries">
<#Include Label="Trans">
</Section>
<Section><Heading>User settings</Heading>
<ManSection>
<InfoClass Name="InfoFR"/>
<Description>
This is an <K>Info</K> class for the package <Package>FR</Package>.
The command <C>SetInfoLevel(InfoFR,1);</C> switches on the printing of
some information during the computations of certain
<Package>FR</Package> functions; in particular all automatic
conversions between FR machines and Mealy machines.
<P/> The command <C>SetInfoLevel(InfoFR,2);</C> requests a little
more information, and in particular prints intermediate results in
potentially long calculations such as <Ref Attr="NucleusOfFRSemigroup"/>.
<P/> The command <C>SetInfoLevel(InfoFR,3);</C> ensures that
<Package>FR</Package> will print information every few seconds or
so. This is useful to gain confidence that the program is not
stuck due to a programming bug by the author of
<Package>FR</Package>.
</Description>
</ManSection>
<#Include Label="FR_SEARCH">
</Section>
</Chapter>
</Body>
<Bibliography Databases="frbib.xml"/>
<TheIndex/>
</Book>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
1557
