Quelle group.gd Sprache: unbekannt

#############################################################################
##
#W group.gd Laurent Bartholdi
##
##
#Y Copyright (C) 2006, Laurent Bartholdi
##
#############################################################################
##
## This file declares the (semi)groups of FR and Mealy machines.
##
#############################################################################

#############################################################################
##
#C IsFRGroup . . . . . . . . . . . . . . . . . . . . .all self-similar groups
#C IsFRSemigroup . . . . . . . . . . . . . . . . .all self-similar semigroups
#C IsFRMonoid . . . . . . . . . . . . . . . . . . . .all self-similar monoids
##
## <#GAPDoc Label="IsFRGroup">
## <ManSection>
## <Filt Name="IsFRGroup" Arg="obj"/>
## <Filt Name="IsFRMonoid" Arg="obj"/>
## <Filt Name="IsFRSemigroup" Arg="obj"/>
## <Returns><K>true</K> if <A>obj</A> is a FR group/monoid/semigroup.</Returns>
## <Description>
## These functions accept <E>self-similar groups/monoids/semigroups</E>,
## i.e. groups/monoids/semigroups whose elements are FR elements.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareSynonym("IsFRGroup", IsFRElementCollection and IsGroup);
DeclareSynonym("IsFRSemigroup", IsFRElementCollection and IsSemigroup);
DeclareSynonym("IsFRMonoid", IsFRElementCollection and IsMonoid);
#############################################################################

#############################################################################
##
#A AlphabetOfFRSemigroup . . . . . . . . . . . . . . . . alphabet of the tree
##
DeclareAttribute("AlphabetOfFRSemigroup", IsFRSemigroup);
#############################################################################

#############################################################################
##
#F FRGroup
#F FRSemigroup
#F FRMonoid
##
## <#GAPDoc Label="FRGroup">
## <ManSection>
## <Oper Name="FRGroup" Arg="{definition,}"/>
## <Oper Name="FRMonoid" Arg="{definition,}"/>
## <Oper Name="FRSemigroup" Arg="{definition,}"/>
## <Returns>A new self-similar group/monoid/semigroup.</Returns>
## <Description>
## This function constructs a new FR group/monoid/semigroup,
## generated by group FR elements. It receives as argument any
## number of strings, each of which represents a generator of
## the object to be constructed.
##
## Each <A>definition</A> is of the form <C>"name=projtrans"</C>,
## where each of <C>proj</C> and <C>trans</C> is optional.
## <C>proj</C> is of the form <C><w1,...,wd></C>, where each
## <C>wi</C> is a (possibly empty) word in the <C>name</C>s or is 1.
## <C>trans</C> is either a permutation in disjoint cycle notation,
## or a list, representing the images of a permutation.
##
## The last argument may be one of the filters <C>IsMealyElement</C>,
## <C>IsFRMealyElement</C> or <C>IsFRElement</C>. By default, if each of
## the states of generators is a generator or 1, the elements of the
## created object will be Mealy elements; otherwise, they will be
## FR elements. Specifying such a filter requires them to be in the
## appropriate category; e.g.,
## <C>FRGroup("a=(1,2)",IsFRMealyElement)</C> asks for the resulting group
## to be generated by FR-Mealy elements. The generators must of course be
## finite-state.
## <Example><![CDATA[
## gap> FRGroup("a=(1,2)","b=(1,2,3,4,5)"); Size(last);
## <self-similar group over [ 1 .. 5 ] with 2 generators>
## 120
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(Dinfinity);
## #I Assigned the global variables [ a, b ]
## gap> Order(a); Order(b); Order(a*b);
## 2
## 2
## infinity
## gap> ZZ := FRGroup("t=<,t>[2,1]");
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## tau := FRElement([[[b,1],[1]]],[()],[1]);
## <2|f3>
## gap> IsSubgroup(Dinfinity,ZZ);
## false
## gap> IsSubgroup(Dinfinity^tau,ZZ);
## true
## gap> Index(Dinfinity^tau,ZZ);
## 2
## ]]></Example>
## <Example><![CDATA[
## gap> i4 := FRMonoid("s=(1,2)","f=<s,f>[1,1]");
## <self-similar monoid over [ 1 .. 2 ] with 2 generators>
## gap> f := GeneratorsOfMonoid(i4){[1,2]};;
## gap> for i in [1..10] do Add(f,f[i]*f[i+1]); od;
## gap> f[1]^2=One(m);
## true
## gap> f[2]^3=f[2];
## true
## gap> f[11]*f[10]^2=f[1]*Product(f{[5,7..11]})*f[10];
## true
## gap> f[12]*f[11]^2=f[2]*Product(f{[6,8..12]})*f[11];
## true
## ]]></Example>
## <Example><![CDATA[
## gap> i2 := FRSemigroup("f0=<f0,f0>(1,2)","f1=<f1,f0>[2,2]");
## <self-similar semigroup over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(i2);
## #I Assigned the global variables [ "f0", "f1" ]
## gap> f0^2=One(i2);
## true
## gap> ForAll([0..10],p->(f0*f1)^p*(f1*f0)^p*f1=f1^2*(f0*f1)^p*(f1*f0)^p*f1);
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Attr Name="NewSemigroupFRMachine" Arg="..."/>
## <Attr Name="NewMonoidFRMachine" Arg="..."/>
## <Attr Name="NewGroupFRMachine" Arg="..."/>
## <Returns>A new FR machine, based on string descriptions.</Returns>
## <Description>
## This command constructs a new FR machine, in a format similar to
## <Ref Func="FRGroup"/>; namely, the arguments are strings of the form
## "gen=<word-1,...,word-d>perm"; each <C>word-i</C> is a word in the
## generators; and <C>perm</C> is a transformation,
## either written in disjoint cycle or in images notation.
##
## Except in the semigroup case, <C>word-i</C> is allowed to be the
## empty string; and the "<...>" may be skipped altogether.
## In the group or IMG case, each <C>word-i</C> may also contain inverses.
##
## The following example constructs the "universal Grigorchuk machine".
## <Example><![CDATA[
## gap> m := NewGroupFRMachine("a=(1,2)(3,4)(5,6)","b=<a,b,a,b,,b>",
## "c=<a,c,,c,a,c>","d=<,d,a,d,a,d>");
## gap> <FR machine with alphabet [ 1, 2, 3, 4, 5, 6 ] on Group( [ a, b, c, d ] )>
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("FRGroup");
DeclareGlobalFunction("FRSemigroup");
DeclareGlobalFunction("FRMonoid");
DeclareGlobalFunction("NewSemigroupFRMachine");
DeclareGlobalFunction("NewMonoidFRMachine");
DeclareGlobalFunction("NewGroupFRMachine");
#############################################################################

#############################################################################
##
#O FRGroupByVirtualEndomorphism
##
## <#GAPDoc Label="FRGroupByVirtualEndomorphism">
## <ManSection>
## <Oper Name="FRGroupByVirtualEndomorphism" Arg="hom[,transversal]"/>
## <Returns>A new self-similar group.</Returns>
## <Description>
## This function constructs a new FR group <C>P</C>, generated by group FR
## elements. Its first argument is a virtual endomorphism of a group
## <C>G</C>, i.e. a homomorphism from a subgroup <C>H</C> to <C>G</C>.
## The constructed FR group acts on a tree with alphabet a transversal
## of <C>H</C> in <C>G</C> (represented as <C>[1..d]</C>), and is
## a homomorphic image of <C>G</C>. The stabilizer of the first-level
## vertex corresponding to the trivial coset is the image of <C>H</C>.
## This function is loosely speaking an inverse of
## <Ref Oper="VirtualEndomorphism"/>.
##
## The optional second argument is a transversal of <C>H</C> in
## <C>G</C>, either of type <C>IsRightTransversal</C> or a list.
##
## Furthermore, an option "MealyElement" can be passed to the
## function, as <C>FRGroupByVirtualEndomorphism(f:MealyElement)</C>,
## to require the resulting group to be generated by Mealy elements
## and not FR elements. The call will succeed, of course, only if the
## representation of <C>G</C> is finite-state.
##
## The resulting FR group has an attribute <C>Correspondence(P)</C>
## that records a homomorphism from <C>G</C> to <C>P</C>.
##
## The example below constructs the binary adding machine, and a
## non-standard representation of it.
## <Example><![CDATA[
## gap> G := FreeGroup(1);
## <free group on the generators [ f1 ]>
## gap> f := GroupHomomorphismByImages(Group(G.1^2),G,[G.1^2],[G.1]);
## [ f1^2 ] -> [ f1 ]
## gap> H := FRGroupByVirtualEndomorphism(f);
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## gap> Display(H.1);
## | 1 2
## ----+--------+------+
## x1 | <id>,2 x1,1
## ----+--------+------+
## Initial state: x1
## gap> Correspondence(H);
## [ f1 ] -> [ <2|x1> ]
## gap> H := FRGroupByVirtualEndomorphism(f,[G.1^0,G.1^3]);;
## gap> Display(H.1);
## | 1 2
## ----+---------+--------+
## x1 | x1^-1,2 x1^2,1
## ----+---------+--------+
## Initial state: x1
## gap> H := FRGroupByVirtualEndomorphism(f:MealyElement);
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## gap> Display(H.1);
## | 1 2
## ---+-----+-----+
## a | b,2 a,1
## b | b,1 b,2
## ---+-----+-----+
## Initial state: a
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("FRGroupByVirtualEndomorphism",[IsGroupHomomorphism]);
DeclareOperation("FRGroupByVirtualEndomorphism",[IsGroupHomomorphism,IsList]);
#############################################################################

#############################################################################
##
#O VirtualEndomorphism
##
## <#GAPDoc Label="VirtualEndomorphism">
## <ManSection>
## <Oper Name="VirtualEndomorphism" Arg="g/m,v"/>
## <Returns>The virtual endomorphism at vertex <A>v</A>.</Returns>
## <Description>
## This function returns the homomorphism from <C>Stabilizer(g,v)</C>
## to <A>g</A>, defined by computing the state at <A>v</A>.
## It is loosely speaking an inverse of
## <Ref Oper="FRGroupByVirtualEndomorphism"/>.
##
## The first argument <A>m</A> may also be an FR machine.
## <Example><![CDATA[
## gap> A := SCGroup(MealyMachine([[2,1],[2,2]],[(1,2),()]));
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## gap> f := VirtualEndomorphism(A,1);
## MappingByFunction( <self-similar group over [ 1 .. 2 ] with
## 1 generator>, <self-similar group over [ 1 .. 2 ] with
## 1 generator>, function( g ) ... end )
## gap> ((A.1)^2)^f=A.1;
## true
## gap> B := FRGroupByVirtualEndomorphism(f);
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## gap> A=B;
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("VirtualEndomorphism",[IsFRGroup,IsObject]);
#############################################################################

#############################################################################
##
#O SEARCH@
##
## <#GAPDoc Label="SEARCH@">
## <ManSection>
## <Var Name="SEARCH@"/>
## <Description>
## This variable controls the search mechanism in FR groups. It is
## a record with in particular entries <C>radius</C> and <C>depth</C>.
##
## <C>radius</C> limits the search in FR groups to balls of
## that radius in the generating set. For example, the command
## <C>x in G</C> will initiate a search in <C>G</C> to attempt to express
## <C>x</C> as a reasonably short word in the generators of <C>G</C>.
##
## <C>depth</C> limits the level of the tree on which quotients
## of FR groups should be considered. Again for the command <C>x in G</C>,
## deeper and deeper quotients will be considered, in the hope of finding
## a quotient of <C>G</C> to which <C>x</C> does not belong.
##
## A primitive mechanism is implemented to search alternatively for
## a quotient disproving <C>x in G</C> and a word proving <C>x in G</C>.
##
## When the limits are reached and the search was unsuccessful, an
## interactive <C>Error()</C> is raised, to let the user increase their
## values.
##
## Specific limits can be passed to any command via the options
## <C>FRdepth</C> and <C>FRradius</C>, as for example in
## <C>Size(G:FRdepth:=3,FRradius:=5)</C>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BindGlobal("SEARCH@", rec(depth := 6, volume := 5000));
#############################################################################

#############################################################################
##
#O SCGroup. . . . . . . . . . . . . . . . . . . . . . . . .state-closed group
#O SCSemigroup. . . . . . . . . . . . . . . . . . . . .state-closed semigroup
#O SCMonoid. . . . . . . . . . . . . . . . . . . . . . . .state-closed monoid
##
## <#GAPDoc Label="SCGroup">
## <ManSection>
## <Oper Name="SCGroup" Arg="m"/>
## <Oper Name="SCGroupNC" Arg="m"/>
## <Oper Name="SCMonoid" Arg="m"/>
## <Oper Name="SCMonoidNC" Arg="m"/>
## <Oper Name="SCSemigroup" Arg="m"/>
## <Oper Name="SCSemigroupNC" Arg="m"/>
## <Returns>The state-closed group/monoid/semigroup generated by the machine <A>m</A>.</Returns>
## <Description>
## This function constructs a new FR group/monoid/semigroup <C>g</C>,
## generated by all the states of the FR machine <A>m</A>.
## There is a bijective correspondence between
## <C>GeneratorsOfFRMachine(m)</C> and the generators of <C>g</C>, which
## is accessible via <C>Correspondence(g)</C>
## (See <Ref Attr="Correspondence" Label="FR semigroup"/>); it is a
## homomorphism from the stateset of <A>m</A> to <C>g</C>, or a list
## indicating for each state of
## <A>m</A> a corresponding generator index in the generators of <C>g</C>
## (with negatives for inverses, and 0 for identity).
##
## In the non-<C>NC</C> forms, redundant (equal, trivial
## or mutually inverse) states are removed from the generating set of
## <C>g</C>.
## <Example><![CDATA[
## gap> b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);; g := SCGroupNC(b);
## <self-similar group over [ 1 .. 2 ] with 3 generators>
## gap> Size(g);
## infinity
## gap> IsOne(Comm(g.2,g.2^g.1));
## true
## ]]></Example>
## <Example><![CDATA[
## gap> i4machine := MealyMachine([[3,3],[1,2],[3,3]],[(1,2),[1,1],()]);
## <Mealy machine on alphabet [ 1, 2 ] with 3 states>
## gap> IsInvertible(i4machine);
## false
## gap> i4 := SCMonoidNC(i4machine);
## <self-similar monoid over [ 1 .. 2 ] with 3 generators>
## gap> f := GeneratorsOfMonoid(i4){[1,2]};;
## gap> for i in [1..10] do Add(f,f[i]*f[i+1]); od;
## gap> f[1]^2=One(m);
## true
## gap> f[2]^3=f[2];
## true
## gap> f[11]*f[10]^2=f[1]*Product(f{[5,7..11]})*f[10];
## true
## gap> f[12]*f[11]^2=f[2]*Product(f{[6,8..12]})*f[11];
## true
## ]]></Example>
## <Example><![CDATA[
## gap> i2machine := MealyMachine([[1,1],[2,1]],[(1,2),[2,2]]);
## <Mealy machine on alphabet [ 1, 2 ] with 2 states>
## gap> i2 := SCSemigroupNC(i2machine);
## <self-similar semigroup over [ 1 .. 2 ] with 2 generators>
## gap> f0 := GeneratorsOfSemigroup(i2)[1];; f1 := GeneratorsOfSemigroup(i2)[2];;
## gap> f0^2=One(i2);
## true
## gap> ForAll([0..10],p->(f0*f1)^p*(f1*f0)^p*f1=f1^2*(f0*f1)^p*(f1*f0)^p*f1);
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Attr Name="Correspondence" Arg="g" Label="FR semigroup"/>
## <Returns>A correspondence between the generators of the underlying FR machine of <A>g</A> and <A>g</A>.</Returns>
## <Description>
## If <A>g</A> was created as the state closure of an FR machine <C>m</C>,
## this attribute records the correspondence between <C>m</C> and <A>g</A>.
##
## If <C>m</C> is a group/monoid/semigroup/algebra FR machine, then
## <C>Correspondence(g)</C> is a homomorphism from the stateset of <C>m</C>
## to <A>g</A>.
##
## If <C>m</C> is a Mealy or vector machine, then
## <C>Correspondence(g)</C> is a list, with in position <M>i</M> the
## index in the generating set of <A>g</A> of state number <M>i</M>.
## This index is 0 if there is no corresponding generator because the
## state is trivial, and is negative if there is no corresponding
## generator because the inverse of state number <M>i</M> is a
## generator.
##
## See <Ref Oper="SCGroupNC"/>, <Ref Oper="SCGroup"/>,
## <Ref Oper="SCMonoidNC"/>, <Ref Oper="SCMonoid"/>,
## <Ref Oper="SCSemigroupNC"/>, <Ref Oper="SCSemigroup"/>,
## <Ref Oper="SCAlgebraNC"/>, <Ref Oper="SCAlgebra"/>,
## <Ref Oper="SCAlgebraWithOneNC"/>, and <Ref Oper="SCAlgebraWithOne"/>
## for examples.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("SCGroupNC", [IsFRMachine]);
DeclareOperation("SCMonoidNC", [IsFRMachine]);
DeclareOperation("SCSemigroupNC", [IsFRMachine]);
DeclareOperation("SCGroup", [IsFRMachine]);
DeclareOperation("SCMonoid", [IsFRMachine]);
DeclareOperation("SCSemigroup", [IsFRMachine]);
DeclareAttribute("Correspondence", IsFRSemigroup);
#############################################################################

#############################################################################
##
#O FullSCGroup. . . . . . . . . . . . . . . . . . maximal state-closed group
#O FullSCMonoid. . . . . . . . . . . . . . . . . maximal state-closed monoid
#O FullSCSemigroup. . . . . . . . . . . . . . maximal state-closed semigroup
##
## <#GAPDoc Label="FullSCGroup">
## <ManSection>
## <Func Name="FullSCGroup" Arg="..."/>
## <Func Name="FullSCMonoid" Arg="..."/>
## <Func Name="FullSCSemigroup" Arg="..."/>
## <Returns>A maximal state-closed group/monoid/semigroup on the alphabet <A>a</A>.</Returns>
## <Description>
## This function constructs a new FR group, monoid or semigroup, which
## contains all transformations with given properties of the tree
## with given alphabet.
##
## The arguments can be, in any order: a semigroup, specifying which
## vertex actions are allowed; a set or domain, specifying the alphabet
## of the tree; an integer, specifying the maximal depth of elements;
## and a filter among <Ref Prop="IsFinitaryFRElement"/>,
## <Ref Prop="IsBoundedFRElement"/>,
## <Ref Prop="IsPolynomialGrowthFRElement"/> and
## <Ref Prop="IsFiniteStateFRElement"/>.
##
## This object serves as a container for all
## FR elements with alphabet <A>a</A>. Random elements can be drawn
## from it; they are Mealy elements with a random number of states, and
## with the required properties.
## <Example><![CDATA[
## gap> g := FullSCGroup([1..3]);
## FullSCGroup([ 1 .. 3 ]);
## gap> IsSubgroup(g,GuptaSidkiGroup);
## true
## gap> g := FullSCGroup([1..3],Group((1,2,3)));
## FullSCGroup([ 1 .. 3 ], Group( [ (1,2,3) ] ))
## gap> IsSubgroup(g,GuptaSidkiGroup);
## true
## gap> IsSubgroup(g,GrigorchukGroup);
## false
## gap> Random(g);
## <Mealy element on alphabet [ 1, 2, 3 ] with 2 states, initial state 1>
## gap> Size(FullSCGroup([1,2],3));
## 128
## gap> g := FullSCMonoid([1..2]);
## FullSCMonoid([ 1 .. 2 ])
## gap> IsSubset(g,AsTransformation(FullSCGroup([1..2])));
## true
## gap> IsSubset(g,AsTransformation(GrigorchukGroup));
## true
## gap> g := FullSCSemigroup([1..3]);
## FullSCSemigroup([ 1 .. 3 ])
## gap> h := FullSCSemigroup([1..3],Semigroup(Transformation([1,1,1])));
## FullSCSemigroup([ 1 .. 3 ], Semigroup( [ [ 1, 1, 1 ] ] ))
## gap> Size(h);
## 1
## gap> IsSubset(g,h);
## true
## gap> g=FullSCMonoid([1..3]);
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("FullSCGroup");
DeclareGlobalFunction("FullSCSemigroup");
DeclareGlobalFunction("FullSCMonoid");
DeclareAttribute("FullSCFilter", IsFRSemigroup);
DeclareAttribute("FullSCVertex", IsFRSemigroup);
DeclareProperty("HasFullSCData", IsFRSemigroup);
#############################################################################

#############################################################################
##
#O TopVertexTransformations. . the (semi)group acting at the root of the tree
#O VertexTransformations. . . . . . . . . . . . . at all vertices of the tree
##
## <#GAPDoc Label="VertexTransformations">
## <ManSection>
## <Attr Name="TopVertexTransformations" Arg="g"/>
## <Returns>The transformations at the root under the action of <A>g</A>.</Returns>
## <Description>
## This function returns the permutation group, or the transformation
## group/semigroup/monoid, of all activities of all elements under the
## root vertex of the tree on which <A>g</A> acts.
##
## It is a synonym for <C>PermGroup(g,1)</C> or
## <C>TransformationMonoid(g,1)</C> or <C>TransformationSemigroup(g,1)</C>.
## <Example><![CDATA[
## gap> TopVertexTransformations(GrigorchukGroup);
## Group([ (), (1,2) ])
## gap> IsTransitive(last,AlphabetOfFRSemigroup(GrigorchukGroup));
## true
## gap> TopVertexTransformations(FullSCMonoid([1..3]));
## <monoid with 3 generators>
## gap> Size(last);
## 27
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Attr Name="VertexTransformations" Arg="g" Label="FR semigroup"/>
## <Returns>The transformations at all vertices under the action of <A>g</A>.</Returns>
## <Description>
## This function returns the permutation group, or the transformation
## group/monoid/semigroup, of all activities of all elements under all
## vertices of the tree on which <A>g</A> acts.
##
## This is the smallest group/monoid/semigroup <C>P</C> such that
## <A>g</A> is a subset of <C>FullSCGroup(AlphabetOfFRSemigroup(g),P)</C>
## or <C>FullSCMonoid(AlphabetOfFRSemigroup(g),P)</C> or
## <C>FullSCSemigroup(AlphabetOfFRSemigroup(g),P)</C>.
## <Example><![CDATA[
## gap> VertexTransformations(GuptaSidkiGroup);
## Group([ (), (1,2,3), (1,3,2) ])
## gap> TopVertexTransformations(Group(GuptaSidkiGroup.2));
## Group(())
## gap> VertexTransformations(Group(GuptaSidkiGroup.2));
## Group([ (), (1,2,3), (1,3,2) ])
## ]]></Example>
## </Description>
## </ManSection>
##
## <#/GAPDoc>
##
DeclareAttribute("TopVertexTransformations", IsFRSemigroup);
DeclareAttribute("VertexTransformations", IsFRSemigroup);
#############################################################################

#############################################################################
##
#O PermGroup. . . . . . . . . . . . . . . . . .group acting on truncated tree
#O [Epimorphism]PermGroup
#O [Epimorphism]PcGroup
#O [Epimorphism]TransformationMonoid
#O [Epimorphism]TransformationSemigroup
##
## <#GAPDoc Label="PermGroup">
## <ManSection>
## <Oper Name="PermGroup" Arg="g,l"/>
## <Oper Name="EpimorphismPermGroup" Arg="g,l"/>
## <Returns>[An epimorphism to] the permutation group of <A>g</A>'s action on level <A>l</A>.</Returns>
## <Description>
## The first function returns a permutation group on <M>d^l</M> points, where
## <M>d</M> is the size of <A>g</A>'s alphabet. It has as many generators
## as <A>g</A>, and represents the action of <A>g</A> on the <A>l</A>th
## layer of the tree.
##
## The second function returns a homomorphism from <A>g</A> to
## this permutation group.
## <Example><![CDATA[
## gap> g := FRGroup("a=(1,2)","b=<a,>"); Size(g);
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## 8
## gap> PermGroup(g,2);
## Group([ (1,3)(2,4), (1,2) ])
## gap> PermGroup(g,3);
## Group([ (1,5)(2,6)(3,7)(4,8), (1,3)(2,4) ])
## gap> List([1..6],i->LogInt(Size(PermGroup(GrigorchukGroup,i)),2));
## [ 1, 3, 7, 12, 22, 42 ]
## gap> g := FRGroup("t=<,t>(1,2)"); Size(g);
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## infinity
## gap> pi := EpimorphismPermGroup(g,5);
## MappingByFunction( <self-similar group over [ 1 .. 2 ] with 1 generator,
## of size infinity>, Group([ (1,17,9,25,5,21,13,29,3,19,11,27,7,23,15,31,
## 2,18,10,26,6,22,14,30,4,20,12,28,8,24,16,32) ]), function( w ) ... end )
## gap> Order(g.1);
## infinity
## gap> Order(g.1^pi);
## 32
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Oper Name="PcGroup" Arg="g,l"/>
## <Oper Name="EpimorphismPcGroup" Arg="g,l"/>
## <Returns>[An epimorphism to] the pc group of <A>g</A>'s action on level <A>l</A>.</Returns>
## <Description>
## The first function returns a polycyclic group representing the action
## of <A>g</A> on the <A>l</A>th layer of the tree. It converts the
## permutation group <C>PermGroup(g,l)</C> to a Pc group, in which
## computations are often faster.
##
## The second function returns a homomorphism from <A>g</A> to
## this pc group.
## <Example><![CDATA[
## gap> g := PcGroup(GrigorchukGroup,7); time;
## <pc group with 5 generators>
## 3370
## gap> NormalClosure(g,Group(g.3)); time;
## <pc group with 79 generators>
## 240
## gap> g := PermGroup(GrigorchukGroup,7); time;
## <permutation group with 5 generators>
## 3
## gap> NormalClosure(g,Group(g.3)); time;
## <permutation group with 5 generators>
## 5344
## gap> g := FRGroup("t=<,t>(1,2)"); Size(g);
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## infinity
## gap> pi := EpimorphismPcGroup(g,5);
## MappingByFunction( <self-similar group over [ 1 .. 2 ] with
## 1 generator, of size infinity>, Group([ f1, f2, f3, f4, f5 ]), function( w ) ... end )
## gap> Order(g.1);
## infinity
## gap> Order(g.1^pi);
## 32
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Oper Name="TransformationMonoid" Arg="g,l"/>
## <Oper Name="EpimorphismTransformationMonoid" Arg="g,l"/>
## <Returns>[An epimorphism to] the transformation monoid of <A>g</A>'s action on level <A>l</A>.</Returns>
## <Description>
## The first function returns a transformation monoid on <M>d^l</M> points,
## where <M>d</M> is the size of <A>g</A>'s alphabet. It has as many
## generators as <A>g</A>, and represents the action of <A>g</A> on
## the <A>l</A>th layer of the tree.
##
## The second function returns a homomorphism from <A>g</A> to this
## transformation monoid.
## <Example><![CDATA[
## gap> i4 := SCMonoid(MealyMachine([[3,3],[1,2],[3,3]],[(1,2),[1,1],()]));
## <self-similar monoid over [ 1 .. 2 ] with 3 generators>
## gap> g := TransformationMonoid(i4,6);
## <monoid with 3 generators>
## gap> List([1..6],i->Size(TransformationMonoid(i4,i)));
## [ 4, 14, 50, 170, 570, 1882 ]
## gap> Collected(List(g,RankOfTransformation));
## [ [ 1, 64 ], [ 2, 1280 ], [ 4, 384 ], [ 8, 112 ], [ 16, 32 ], [ 32, 8 ], [ 64, 2 ] ]
## gap> pi := EpimorphismTransformationMonoid(i4,9);
## MappingByFunction( <self-similar monoid over [ 1 .. 2 ] with 3 generators>,
## <monoid with 3 generators>, function( w ) ... end )
## gap> f := GeneratorsOfMonoid(i4){[1,2]};;
## gap> for i in [1..10] do Add(f,f[i]*f[i+1]); od;
## gap> Product(f{[3,5,7,9,11]})=f[11]*f[10];
## false
## gap> Product(f{[3,5,7,9,11]})^pi=(f[11]*f[10])^pi;
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Oper Name="TransformationSemigroup" Arg="g,l"/>
## <Oper Name="EpimorphismTransformationSemigroup" Arg="g,l"/>
## <Returns>[An epimorphism to] the transformation semigroup of <A>g</A>'s action on level <A>l</A>.</Returns>
## <Description>
## The first function returns a transformation semigroup on <M>d^l</M>
## points, where <M>d</M> is the size of <A>g</A>'s alphabet.
## It has as many generators as <A>g</A>, and represents the action
## of <A>g</A> on the <A>l</A>th layer of the tree.
##
## The second function returns a homomorphism from <A>g</A> to this
## transformation semigroup.
## <Example><![CDATA[
## gap> i2 := SCSemigroup(MealyMachine([[1,1],[2,1]],[(1,2),[2,2]]));
## <self-similar semigroup over [ 1 .. 2 ] with 2 generators>
## gap> g := TransformationSemigroup(i2,6);
## <semigroup with 2 generators>
## gap> List([1..6],i->Size(TransformationSemigroup(i2,i)));
## [ 4, 14, 42, 114, 290, 706 ]
## gap> Collected(List(g,RankOfTransformation));
## [ [ 1, 64 ], [ 2, 384 ], [ 4, 160 ], [ 8, 64 ], [ 16, 24 ], [ 32, 8 ], [ 64, 2 ] ]
## gap> f0 := GeneratorsOfSemigroup(i2)[1];; f1 := GeneratorsOfSemigroup(i2)[2];;
## gap> pi := EpimorphismTransformationSemigroup(i2,10);
## MappingByFunction( <self-similar semigroup over [ 1 .. 2 ] with
## 2 generators>, <semigroup with 2 generators>, function( w ) ... end )
## gap> (f1*(f1*f0)^10)=((f1*f0)^10);
## false
## gap> (f1*(f1*f0)^10)^pi=((f1*f0)^10)^pi;
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Oper Name="EpimorphismGermGroup" Arg="g,l"/>
## <Oper Name="EpimorphismGermGroup" Arg="g" Label="EGG0"/>
## <Returns>A homomorphism to a polycyclic group.</Returns>
## <Description>
## This function returns an epimorphism to a polycyclic group, encoding
## the action on the first <A>l</A> levels of the tree and on the germs
## below. If <A>l</A> is omitted, it is assumed to be <M>0</M>.
##
## Since the elements of <A>g</A> are finite automata, they map
## periodic sequences to periodic sequences. The action on the periods,
## and in the immediate vicinity of them, is called the <E>germ action</E>
## of <A>g</A>. This function returns the natural homomorphism from
## <A>g</A> to the wreath product of this germ group with the quotient of
## <A>g</A> acting on the <A>l</A>th layer of the tree.
##
## The germ group, by default, is abelian. If it is finite, this
## function returns a homomorphism to a Pc group; otherwise, a
## homomorphism to a polycyclic group.
##
## The <Ref Var="GrigorchukTwistedTwin"/> is, for now, the only example
## with a hand-coded, non-abelian germ group.
## <Example><![CDATA[
## gap> EpimorphismGermGroup(GrigorchukGroup,0);
## MappingByFunction( GrigorchukGroup, <pc group of size 4 with 2 generators>,
## function( g ) ... end )
## gap> List(GeneratorsOfGroup(GrigorchukGroup),x->x^last);
## [ <identity> of ..., f1, f1*f2, f2 ]
## gap> StructureDescription(Image(last2));
## "C2 x C2"
## gap> g := FRGroup("t=<,t>(1,2)","m=<,m^-1>(1,2)");;
## gap> EpimorphismGermGroup(g,0);
## MappingByFunction( <state-closed, bounded group over [ 1, 2 ] with 2
## generators>, Pcp-group with orders [ 0, 0 ], function( x ) ... end )
## gap> EpimorphismGermGroup(g,1);; Range(last); Image(last2);
## Pcp-group with orders [ 2, 0, 0, 0, 0 ]
## Pcp-group with orders [ 2, 0, 0, 0 ]
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Attr Name="GermData" Arg="group"/>
## <Oper Name="GermValue" Arg="element, data"/>
## <Description>
## The first command computes some data useful to determine the germ
## value of a group element; the second command computes these germ
## values. For more information on germs, see <Ref Oper="Germs"/>.
## <Example><![CDATA[
## gap> data := GermData(GrigorchukGroup);
## rec( endo := [ f1, f2 ] -> [ f1*f2, f1 ], group := <pc group of size 4 with 2 generators>,
## machines := [ ], map := [ <identity> of ..., f2, f1, f1*f2, <identity> of ... ],
## nucleus := [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>, d, c, b, a ],
## nucleusmachine := <Mealy machine on alphabet [ 1 .. 2 ] with 5 states> )
## gap> List(GeneratorsOfGroup(GrigorchukGroup),x->GermValue(x,data));
## [ <identity> of ..., f1*f2, f1, f2 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute("LevelOfEpimorphismFromFRGroup",IsGroupHomomorphism);
DeclareOperation("PermGroup", [IsFRGroup, IsInt]);
DeclareOperation("EpimorphismPermGroup", [IsFRGroup, IsInt]);
DeclareOperation("PcGroup", [IsFRGroup, IsInt]);
DeclareOperation("EpimorphismPcGroup", [IsFRGroup, IsInt]);
DeclareOperation("TransformationMonoid", [IsFRMonoid, IsInt]);
DeclareOperation("EpimorphismTransformationMonoid", [IsFRMonoid, IsInt]);
DeclareOperation("TransformationSemigroup", [IsFRSemigroup, IsInt]);
DeclareOperation("EpimorphismTransformationSemigroup", [IsFRSemigroup, IsInt]);
DeclareOperation("EpimorphismGermGroup",[IsFRGroup, IsInt]);
DeclareOperation("EpimorphismGermGroup",[IsFRGroup]);
#############################################################################

#############################################################################
##
#P IsStateClosed. . . . . . . . . . . . are all states of elements of G in G?
#O StateClosure. . . . . . . . . the smallest state-closed group containing G
#P IsRecurrent. . . . . . . . .do all elements appear under any fixed vertex?
#P IsLevelTransitive. . . . . . is there one orbit at each level of the tree?
##
## <#GAPDoc Label="IsStateClosed">
## <ManSection>
## <Prop Name="IsStateClosed" Arg="g"/>
## <Returns><K>true</K> if all states of elements of <A>g</A> belong to <A>g</A>.</Returns>
## <Description>
## This function tests whether <A>g</A> is a <E>state-closed</E> group,
## i.e. a group such that all states of all elements of <A>g</A> belong
## to <A>g</A>.
##
## The smallest state-closed group containing <A>g</A> is computed
## with <Ref Oper="StateClosure"/>.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(Dinfinity);
## #I Assigned the global variables [ a, b ]
## gap> IsStateClosed(Group(a));
## IsStateClosed(Group(b));
## IsStateClosed(Dinfinity);
## true
## false
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Oper Name="StateClosure" Arg="g"/>
## <Returns>The smallest state-closed group containing <A>g</A>.</Returns>
## <Description>
## This function computes the smallest group containing all states of
## all elements of <A>g</A>, i.e. the smallest group containing <A>g</A>
## and for which <Ref Prop="IsStateClosed"/> returns <K>true</K>.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(Dinfinity);
## #I Assigned the global variables [ a, b ]
## gap> StateStateClosure(Group(a))=Dinfinity; StateClosure(Group(b))=Dinfinity;
## false
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="IsRecurrentFRSemigroup" Arg="g"/>
## <Returns><K>true</K> if <A>g</A> is a recurrent group.</Returns>
## <Description>
## This function returns <K>true</K> if <A>g</A> is a <E>recurrent</E>
## group, i.e. if, for every vertex <C>v</C>, all elements of <A>g</A>
## appear as states at <C>v</C> of elements fixing <C>v</C>.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(Dinfinity);
## #I Assigned the global variables [ a, b ]
## gap> IsRecurrentFRSemigroup(Group(a)); IsRecurrentFRSemigroup(Group(b));
## false
## false
## gap> IsRecurrentFRSemigroup(Dinfinity);
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="IsLevelTransitiveFRGroup" Arg="g"/>
## <Returns><K>true</K> if <A>g</A> is a level-transitive group.</Returns>
## <Description>
## This function returns <K>true</K> if <A>g</A> is a
## <E>level-transitive</E> group, i.e. if the action of <A>g</A> is
## transitive at every level of the tree on which it acts.
##
## This function can be abbreviated as <C>IsLevelTransitive</C>.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(Dinfinity);
## #I Assigned the global variables [ a, b ]
## gap> IsLevelTransitiveFRGroup(Group(a)); IsLevelTransitiveFRGroup(Group(b));
## IsLevelTransitiveFRGroup(Dinfinity);
## false
## false
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="IsInfinitelyTransitive" Arg="g"/>
## <Prop Name="IsLevelTransitiveOnPatterns" Arg="g"/>
## <Returns><K>true</K> if <A>g</A> is infinitely transitive.</Returns>
## <Description>
## This function returns <K>true</K> if <A>g</A> is an
## <E>infinitely transitive</E> group. This means that <A>g</A> is
## the state-closed group of a bireversible Mealy machine (see <Ref
## Prop="IsBireversible"/>), and that
## the action of the set of reduced words of any given length over the
## alphabet (where "reduced" means no successive letters related by
## the involution) is transitive.
##
## Reduced words are defined as follows: if the underlying Mealy
## machine of <A>g</A> has an involution on its alphabet
## (see <Ref Attr="AlphabetInvolution"/>), then reduced words are words
## in which two consecutive letters are not images of each other under
## the involution. If no involution is defined, then all words are
## considered reduced; the command then becomes synonymous to
## <Ref Prop="IsLevelTransitiveFRGroup"/>.
##
## This notion is of fundamental importance for the study of
## lattices in a product of trees; it implies under appropriate
## circumstances that the dual group is free.
## <Example><![CDATA[
## gap> IsInfinitelyTransitive(BabyAleshinGroup);
## true
## gap> IsLevelTransitiveFRGroup(BabyAleshinGroup);
## true
## gap> s := DualMachine(BabyAleshinMachine);
## <Mealy machine on alphabet [ 1 .. 3 ] with 2 states>
## gap> AlphabetInvolution(s); # set attribute
## [ 1, 2, 3 ]
## gap> g := SCGroup(s);
## <state-closed group over [ 1 .. 3 ] with 2 generators>
## gap> IsInfinitelyTransitive(g);
## true
## gap> IsLevelTransitiveFRGroup(g);
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty("IsStateClosed", IsFRSemigroup);
DeclareOperation("StateClosure", [IsFRSemigroup]);
DeclareProperty("IsRecurrentFRSemigroup", IsFRSemigroup);
DeclareProperty("IsLevelTransitiveFRGroup", IsFRSemigroup);
DeclareProperty("IsInfinitelyTransitive", IsFRGroup);
DeclareProperty("IsLevelTransitiveOnPatterns", IsFRGroup);
#############################################################################

#############################################################################
##
#P IsContracting
#A NucleusOfFRSemigroup
#A NucleusMachine
##
## <#GAPDoc Label="IsContracting">
## <ManSection>
## <Prop Name="IsContracting" Arg="g"/>
## <Returns><K>true</K> if <A>g</A> is a contracting semigroup.</Returns>
## <Description>
## This function returns <K>true</K> if <A>g</A> is a <E>contracting</E>
## semigroup, i.e. if there exists a finite subset <C>N</C> of <A>g</A>
## such that the <Ref Oper="LimitStates"/> of every element of <A>g</A>
## belong to <C>N</C>.
##
## The minimal such <C>N</C> can be computed with <Ref Attr="NucleusOfFRSemigroup"/>.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> IsContracting(Dinfinity);
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Attr Name="NucleusOfFRSemigroup" Arg="g"/>
## <Oper Name="Nucleus" Arg="g" Label="FR semigroup"/>
## <Returns>The nucleus of the contracting semigroup <A>g</A>.</Returns>
## <Description>
## This function returns the <E>nucleus</E> of the contracting semigroup
## <A>g</A>, i.e. the smallest subset <C>N</C> of <A>g</A>
## such that the <Ref Oper="LimitStates"/> of every element of <A>g</A>
## belong to <C>N</C>.
##
## This function returns <K>fail</K> if no such <C>N</C> exists.
## Usually, it loops forever without being able to decide whether <C>N</C>
## is finite or infinite. It succeeds precisely when
## <C>IsContracting(g)</C> succeeds.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> NucleusOfFRSemigroup(Dinfinity);
## [ <2|identity ...>, <2|b>, <2|a> ]
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Attr Name="NucleusMachine" Arg="g" Label="FR semigroup"/>
## <Returns>The nucleus machine of the contracting semigroup <A>g</A>.</Returns>
## <Description>
## This function returns the <E>nucleus</E> of the contracting semigroup
## <A>g</A>, see <Ref Attr="NucleusOfFRSemigroup"/>, in the form of a Mealy machine.
##
## Since all states of the nucleus are elements of the nucleus, the
## transition and output function may be restricted to the nucleus,
## defining a Mealy machine. Finitely generated recurrent groups are
## generated by their nucleus machine.
##
## This function returns <K>fail</K> if no such <C>n</C> exists.
## Usually, it loops forever without being able to decide whether <C>n</C>
## is finite or infinite. It succeeds precisely when
## <C>IsContracting(g)</C> succeeds.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> M := NucleusMachine(Dinfinity);
## <Mealy machine on alphabet [ 1, 2 ] with 3 states>
## gap> Display(M);
## | 1 2
## ---+-----+-----+
## a | a,1 a,2
## b | c,1 b,2
## c | a,2 a,1
## ---+-----+-----+
## gap> Dinfinity=SCGroup(M);
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Attr Name="AdjacencyBasesWithOne" Arg="g"/>
## <Attr Name="AdjacencyPoset" Arg="g"/>
## <Returns>The bases, or the poset, of the simplicial model of <A>g</A>.</Returns>
## <Description>
## For these arguments, <A>g</A> can be either the nucleus of an FR
## semigroup, or that semigroup itself, in which case its nucleus is
## first computed.
##
## The first function computes those maximal (for inclusion)
## subsets of the nucleus that are recurrent, namely subsets <C>B</C>
## such that <C>Set(B,x->States(x,v))=B</C> for a string <C>v</C>.
##
## The second function then computes the poset of intersections of
## these bases, and returns it as a binary relation.
##
## For more details on these concepts, see <Cite Key="0810.4936"/>.
## <Example><![CDATA[
## gap> n := NucleusOfFRSemigroup(BasilicaGroup);
## [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>, b,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states> ]
## gap> AdjacencyBasesWithOne(n);
## [ [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states> ],
## [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states> ],
## [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
## <Mealy element on alphabet [ 1 .. 2 ] with 3 states> ] ]
## gap> AdjacencyPoset(n);
## <general mapping: <object> -> <object> >
## gap> Draw(HasseDiagramBinaryRelation(last));
## ]]></Example>
## This produces (in a new window) the following picture:
## <Alt Only="LaTeX"><![CDATA[
## \includegraphics[height=3cm,keepaspectratio=true]{hasse.jpg}
## ]]></Alt>
## <Alt Only="HTML"><![CDATA[
## <img alt="Hasse Diagram" src="hasse.jpg">
## ]]></Alt>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty("IsContracting", IsFRSemigroup);
DeclareAttribute("NucleusOfFRSemigroup", IsFRSemigroup);
DeclareAttribute("NucleusMachine", IsFRSemigroup);
DeclareAttribute("AdjacencyBasesWithOne", IsFRElementCollection);
DeclareAttribute("AdjacencyPoset", IsFRElementCollection);
#############################################################################

#############################################################################
##
#P IsFinitary
#P IsBounded
#P IsFiniteState
##
## <#GAPDoc Label="IsFinitary">
## <ManSection>
## <Prop Name="IsFinitaryFRSemigroup" Arg="g"/>
## <Prop Name="IsWeaklyFinitaryFRSemigroup" Arg="g"/>
## <Prop Name="IsBoundedFRSemigroup" Arg="g"/>
## <Prop Name="IsPolynomialGrowthFRSemigroup" Arg="g"/>
## <Prop Name="IsFiniteStateFRSemigroup" Arg="g"/>
## <Returns><K>true</K> if all elements of <A>g</A> have the required property.</Returns>
## <Description>
## This function returns <K>true</K> if all elements of <A>g</A>
## have the required property, as FR elements; see
## <Ref Prop="IsFinitaryFRElement"/>,
## <Ref Prop="IsWeaklyFinitaryFRElement"/>,
## <Ref Prop="IsBoundedFRElement"/>,
## <Ref Prop="IsPolynomialGrowthFRElement"/> and
## <Ref Prop="IsFiniteStateFRElement"/>.
## <Example><![CDATA[
## gap> G := FRGroup("a=(1,2)","b=<a,b>","c=<c,b>","d=<d,d>(1,2)");
## <self-similar group over [ 1 .. 2 ] with 4 generators>
## gap> L := [Group(G.1),Group(G.1,G.2),Group(G.1,G.2,G.3),G];;
## gap> List(L,IsFinitaryFRSemigroup);
## [ true, false, false, false ]
## gap> List(L,IsBoundedFRSemigroup);
## [ true, true, false, false ]
## gap> List(L,IsPolynomialGrowthFRSemigroup);
## [ true, true, true, false ]
## gap> List(L,IsFiniteStateFRSemigroup);
## [ true, true, true, true ]
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Attr Name="Degree" Arg="g" Label="FR semigroup"/>
## <Attr Name="DegreeOfFRSemigroup" Arg="g"/>
## <Attr Name="Depth" Arg="g" Label="FR semigroup"/>
## <Attr Name="DepthOfFRSemigroup" Arg="g"/>
## <Returns>The maximal degree/depth of elements of <A>g</A>.</Returns>
## <Description>
## This function returns the maximal degree/depth of elements of <A>g</A>;
## see <Ref Attr="Degree" Label="FR element"/> and
## <Ref Attr="Depth" Label="FR element"/>.
## <Example><![CDATA[
## gap> G := FRGroup("a=(1,2)","b=<a,b>","c=<c,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> Degree(Group(G.1)); Degree(Group(G.1,G.2)); Degree(G);
## 0
## 1
## 2
## gap> Depth(Group(G.1)); Depth(Group(G.1,G.2)); Depth(G);
## 1
## infinity
## infinity
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="HasOpenSetConditionFRSemigroup" Arg="g"/>
## <Returns><K>true</K> if <A>g</A> has the open set condition.</Returns>
## <Description>
## This function returns <K>true</K> if all elements of <A>g</A>
## have the <E>open set condition</E>, see
## <Ref Prop="HasOpenSetConditionFRElement"/>.
## <Example><![CDATA[
## gap> HasOpenSetConditionFRSemigroup(GrigorchukGroup);
## false
## gap> HasOpenSetConditionFRSemigroup(BinaryAddingGroup);
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="HasCongruenceProperty" Arg="G"/>
## <Returns><K>true</K> if <A>G</A> has the congruence property.</Returns>
## <Description>
## This function returns <K>true</K> if the transformation
## (semi)group <A>G</A> has the <E>congruence property</E>, namely if
## every homomorphism <M>G\to Q</M> to a finite quotient factors as
## <M>G\to H\to Q</M> via an action of <M>G</M> on a finite set.
##
## This command is not guaranteed to terminate.
## <Example><![CDATA[
## gap> HasCongruenceProperty(GrigorchukGroup);
## true
## gap> HasCongruenceProperty(GrigorchukTwistedTwin);
## ...runs forever...
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty("IsFinitaryFRSemigroup", IsFRSemigroup);
DeclareProperty("IsWeaklyFinitaryFRSemigroup", IsFRSemigroup);
DeclareProperty("IsBoundedFRSemigroup", IsFRSemigroup);
DeclareProperty("IsPolynomialGrowthFRSemigroup", IsFRSemigroup);
DeclareProperty("IsFiniteStateFRSemigroup", IsFRSemigroup);
DeclareAttribute("DegreeOfFRSemigroup", IsFRSemigroup);
DeclareAttribute("DepthOfFRSemigroup", IsFRSemigroup);
DeclareProperty("HasOpenSetConditionFRSemigroup", IsFRSemigroup);
DeclareOperation("Depth", [IsFRSemigroup]);
DeclareAttribute("GermData", IsFRGroup, "mutable");
DeclareOperation("GermValue", [IsFRElement, IsRecord]);
DeclareProperty("HasCongruenceProperty", IsFRGroup);
#############################################################################

#############################################################################
##
#P IsTorsionGroup ...
##
## <#GAPDoc Label="IsTorsionGroup">
## <ManSection>
## <Prop Name="IsTorsionGroup" Arg="g"/>
## <Returns><K>true</K> if <A>g</A> is a torsion group.</Returns>
## <Description>
## This function returns <K>true</K> if <A>g</A> is a torsion group,
## i.e. if every element in <A>g</A> has finite order; and <K>false</K>
## if <A>g</A> contains an element of infinite order.
##
## This method is quite rudimentary, and is not guaranteed to
## terminate. At the minimum, <A>g</A> should be a group in which
## <C>Order()</C> succeeds in computing element orders; e.g. a
## bounded group in Mealy machine format.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>":IsMealyElement);
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> IsTorsionGroup(Dinfinity);
## false
## gap> IsTorsionGroup(GrigorchukGroup); IsTorsionGroup(GuptaSidkiGroup);
## true
## true
## gap> IsTorsionGroup(FabrykowskiGuptaGroup);
## false
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="IsTorsionFreeGroup" Arg="g"/>
## <Returns><K>true</K> if <A>g</A> is a torsion-free group.</Returns>
## <Description>
## This function returns <K>true</K> if <A>g</A> is a torsion-free group,
## i.e. if no element in <A>g</A> has finite order; and <K>false</K>
## if <A>g</A> contains an element of finite order.
##
## This method is quite rudimentary, and is not guaranteed to
## terminate. At the minimum, <A>g</A> should be a group in which
## <C>Order()</C> succeeds in computing element orders; e.g. a
## bounded group in Mealy machine format.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>":IsMealyElement);
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> IsTorsionFreeGroup(Dinfinity);
## false
## gap> IsTorsionFreeGroup(BasilicaGroup);
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="IsAmenableGroup" Arg="g"/>
## <Returns><K>true</K> if <A>g</A> is an amenable group.</Returns>
## <Description>
## Amenable groups, introduced by von Neumann <Cite Key="vneumann"/>,
## are those groups that admit a finitely additive,
## translation-invariant measure.
## <Example><![CDATA[
## gap> IsAmenableGroup(FreeGroup(2));
## false
## gap> IsAmenableGroup(BasilicaGroup);
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="IsVirtuallySimpleGroup" Arg="g"/>
## <Attr Name="LambdaElementVHGroup" Arg="g"/>
## <Returns><K>true</K> if <A>g</A> admits a finite-index simple subgroup.</Returns>
## <Description>
## This function attempts to prove that the VH group <A>g</A> admits a finite-index
## simple subgroup.
##
## It is based on the following test: let <C>D</C> be a direction
## (vertical or horizontal) such that the corresponding action is
## infinitely transitive (see <Ref Prop="IsInfinitelyTransitive"/>). If the corresponding
## subgroup of <A>g</A> contains a non-trivial element <M>\lambda</M> that acts
## trivially in the corresponding action, then every normal subgroup contains
## <M>\lambda</M>. It then remains to check that the normal closure of <M>\lambda</M>
## has finite index. This element <M>\lambda</M> is then stored as the
## attribute <C>LambdaElementVHGroup(g)</C>.
##
## The current implementation is based on results in
## <Cite Key="MR1839488"/> and <Cite Key="MR1839489"/>, and does not
## work for the Rattaggi examples (see <Ref Var="RattaggiGroup"/>).
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="IsResiduallyFinite" Arg="obj"/>
## <Returns><K>true</K> if <A>obj</A> is residually finite.</Returns>
## <Description>
## An object is <E>residually finite</E> if it can be approximated
## arbitrarily well by finite quotients; i.e. if for every
## <M>g\neq h\in X</M> there exists a finite quotient <M>\pi:X\to Q</M>
## such that <M>g^\pi\neq h^\pi</M>.
## <Example><![CDATA[
## gap> IsResiduallyFinite(FreeGroup(2));
## true
## gap> IsResiduallyFinite(BasilicaGroup);
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="IsSQUniversal" Arg="obj"/>
## <Returns><K>true</K> if <A>obj</A> is SQ-universal.</Returns>
## <Description>
## An object <A>obj</A> is <E>SQ-universal</E> if every countable
## object of the same category as <A>obj</A> is a subobject of a
## quotient of <A>obj</A>.
## <Example><![CDATA[
## gap> IsSQUniversal(FreeGroup(2));
## true
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Prop Name="IsJustInfinite" Arg="obj"/>
## <Returns><K>true</K> if <A>obj</A> is just-infinite.</Returns>
## <Description>
## An object <A>obj</A> is <E>just-infinite</E> if <A>obj</A> is
## infinite, but every quotient of <A>obj</A> is finite.
## <Example><![CDATA[
## gap> IsJustInfinite(FreeGroup(2));
## false
## gap> IsJustInfinite(FreeGroup(1));
## true
## gap> IsJustInfinite(GrigorchukGroup); time
## true
## 8284
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty("IsTorsionGroup", IsGroup);
DeclareSynonym("IsTorsionFreeGroup", IsTorsionFree);
DeclareProperty("IsAmenableGroup", IsGroup);
DeclareProperty("IsVirtuallySimpleGroup",IsGroup);
DeclareProperty("IsSQUniversal",IsObject);
DeclareProperty("IsJustInfinite",IsObject);
DeclareProperty("IsResiduallyFinite",IsObject);
#############################################################################

#############################################################################
##
#P IsomorphismFRGroup(G)
#P IsomorphismMealyGroup(G)
##
## <#GAPDoc Label="IsomorphismFRGroup">
## <ManSection>
## <Oper Name="FRMachineFRGroup" Arg="g"/>
## <Oper Name="FRMachineFRMonoid" Arg="g"/>
## <Oper Name="FRMachineFRSemigroup" Arg="g"/>
## <Oper Name="MealyMachineFRGroup" Arg="g"/>
## <Oper Name="MealyMachineFRMonoid" Arg="g"/>
## <Oper Name="MealyMachineFRSemigroup" Arg="g"/>
## <Returns>A machine describing all generators of <A>g</A>.</Returns>
## <Description>
## This function constructs a new group/monoid/semigroup/Mealy FR machine,
## with (at least) one generator per generator of <A>g</A>.
## This is done by adding all machines of all generators of <A>g</A>,
## and minimizing.
##
## In particular, if <A>g</A> is state-closed, then
## <C>SCGroup(FRMachineFRGroup(g))</C> gives a group isomorphic to
## <A>g</A>, and similarly for monoids and semigroups.
## <Example><![CDATA[
## gap> FRMachineFRGroup(GuptaSidkiGroup);
## <FR machine with alphabet [ 1 .. 3 ] on Group( [ f11, f12 ] )>
## gap> Display(last);
## G | 1 2 3
## -----+--------+----------+--------+
## f11 | <id>,2 <id>,3 <id>,1
## f12 | f11,1 f11^-1,2 f12,3
## -----+--------+----------+--------+
## ]]></Example>
## <Example><![CDATA[
## gap> FRMachineFRMonoid(I4Monoid);
## <FR machine with alphabet [ 1 .. 2 ] on Monoid( [ m11, m12 ], ... )>
## gap> Display(last);
## M | 1 2
## -----+--------+--------+
## m11 | <id>,2 <id>,1
## m12 | m11,1 m12,1
## -----+--------+--------+
## ]]></Example>
## <Example><![CDATA[
## gap> FRMachineFRSemigroup(I2Monoid);
## <FR machine with alphabet [ 1 .. 2 ] on Semigroup( [ s11, s12, s1 ] )>
## gap> Display(last);
## S | 1 2
## -----+-------+-------+
## s11 | s11,1 s11,2
## s12 | s12,2 s12,1
## s1 | s1,2 s12,2
## -----+-------+-------+
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Oper Name="IsomorphismFRGroup" Arg="g"/>
## <Oper Name="IsomorphismFRMonoid" Arg="g"/>
## <Oper Name="IsomorphismFRSemigroup" Arg="g"/>
## <Returns>An isomorphism towards a group/monoid/semigroup on a single FR machine.</Returns>
## <Description>
## This function constructs a new FR group/monoid/semigroup, such that
## all elements of the resulting object have the same underlying
## group/monoid/semigroup FR machine.
## <Example><![CDATA[
## gap> phi := IsomorphismFRGroup(GuptaSidkiGroup);
## [ <Mealy element on alphabet [ 1, 2, 3 ] with 2 states, initial state 1>,
## <Mealy element on alphabet [ 1, 2, 3 ] with 4 states, initial state 1> ] ->
## [ <3|identity ...>, <3|f1>, <3|f1^-1>, <3|f2> ]
## gap> Display(GuptaSidkiGroup.2);
## | 1 2 3
## ---+-----+-----+-----+
## a | a,1 a,2 a,3
## b | a,2 a,3 a,1
## c | a,3 a,1 a,2
## d | b,1 c,2 d,3
## ---+-----+-----+-----+
## Initial state: d
## gap> Display(GuptaSidkiGroup.2^phi);
## | 1 2 3
## ----+--------+---------+--------+
## f1 | <id>,2 <id>,3 <id>,1
## f2 | f1,1 f1^-1,2 f2,3
## ----+--------+---------+--------+
## Initial state: f2
## ]]></Example>
## <Example><![CDATA[
## gap> phi := IsomorphismFRSemigroup(I2Monoid);
## MappingByFunction( I2, <self-similar semigroup over [ 1 .. 2 ] with
## 3 generators>, <Operation "AsSemigroupFRElement"> )
## gap> Display(GeneratorsOfSemigroup(I2Monoid)[3]);
## | 1 2
## ---+-----+-----+
## a | a,2 b,2
## b | b,2 b,1
## ---+-----+-----+
## Initial state: a
## gap> Display(GeneratorsOfSemigroup(I2Monoid)[3]^phi);
## S | 1 2
## ----+------+------+
## s1 | s1,2 s2,2
## s2 | s2,2 s2,1
## ----+------+------+
## Initial state: s1
## ]]></Example>
## <Example><![CDATA[
## gap> phi := IsomorphismFRMonoid(I4Monoid);
## MappingByFunction( I4, <self-similar monoid over [ 1 .. 2 ] with
## 2 generators>, <Operation "AsMonoidFRElement"> )
## gap> Display(GeneratorsOfMonoid(I4Monoid)[1]);
## | 1 2
## ---+-----+-----+
## a | b,2 b,1
## b | b,1 b,2
## ---+-----+-----+
## Initial state: a
## gap> Display(GeneratorsOfMonoid(I4Monoid)[1]^phi);
## M | 1 2
## ----+--------+--------+
## m1 | <id>,2 <id>,1
## ----+--------+--------+
## Initial state: m1
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Oper Name="IsomorphismMealyGroup" Arg="g"/>
## <Oper Name="IsomorphismMealyMonoid" Arg="g"/>
## <Oper Name="IsomorphismMealySemigroup" Arg="g"/>
## <Returns>An isomorphism towards a group/monoid/semigroup all of whose elements are Mealy machines.</Returns>
## <Description>
## This function constructs a new FR group/monoid/semigroup, such that
## all elements of the resulting object are Mealy machines.
## <Example><![CDATA[
## gap> G := FRGroup("a=(1,2)","b=<a,b>","c=<c,b>");
## <self-similar group over [ 1 .. 2 ] with 3 generators>
## gap> phi := IsomorphismMealyGroup(G);
## [ <2|a>, <2|b>, <2|c> ] ->
## [ <Mealy element on alphabet [ 1, 2 ] with 2 states, initial state 1>,
## <Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>,
## <Mealy element on alphabet [ 1, 2 ] with 4 states, initial state 1> ]
## gap> Display(G.3);
## | 1 2
## ---+--------+--------+
## a | <id>,2 <id>,1
## b | a,1 b,2
## c | c,1 b,2
## ---+--------+--------+
## Initial state: c
## gap> Display(G.3^phi);
## | 1 2
## ---+-----+-----+
## a | a,1 b,2
## b | c,1 b,2
## c | d,2 d,1
## d | d,1 d,2
## ---+-----+-----+
## Initial state: a
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("FRMachineFRGroup", [IsFRGroup]);
DeclareOperation("FRMachineFRMonoid", [IsFRMonoid]);
DeclareOperation("FRMachineFRSemigroup", [IsFRSemigroup]);
DeclareOperation("MealyMachineFRGroup", [IsFRGroup]);
DeclareOperation("MealyMachineFRMonoid", [IsFRMonoid]);
DeclareOperation("MealyMachineFRSemigroup", [IsFRSemigroup]);
DeclareOperation("IsomorphismFRGroup", [IsFRGroup]);
DeclareOperation("IsomorphismFRMonoid", [IsFRMonoid]);
DeclareOperation("IsomorphismFRSemigroup", [IsFRSemigroup]);
DeclareOperation("IsomorphismMealyGroup", [IsFRGroup]);
DeclareOperation("IsomorphismMealyMonoid", [IsFRMonoid]);
DeclareOperation("IsomorphismMealySemigroup", [IsFRSemigroup]);
#############################################################################

#############################################################################
##
#O StabilizerImage
##
## <#GAPDoc Label="StabilizerImage">
## <ManSection>
## <Oper Name="StabilizerImage" Arg="g,v"/>
## <Returns>The group of all states at <A>v</A> of elements of <A>g</A> fixing <A>v</A>.</Returns>
## <Description>
## This function constructs a new FR group, consisting of all states at
## vertex <A>v</A> (which can be an integer or a list) of the stabilizer
## of <A>v</A> in <A>g</A>.
##
## The result is <A>g</A> itself precisely if <A>g</A> is recurrent
## (see <Ref Prop="IsRecurrentFRSemigroup"/>).
## <Example><![CDATA[
## gap> G := FRGroup("t=<,t>(1,2)","u=<,u^-1>(1,2)","b=<u,t>");
## <self-similar group over [ 1 .. 2 ] with 3 generators>
## gap> Stabilizer(G,1);
## <self-similar group over [ 1 .. 2 ] with 5 generators>
## gap> GeneratorsOfGroup(last);
## [ <2|u*t^-1>, <2|b>, <2|t^2>, <2|t*u>, <2|t*b*t^-1> ]
## gap> StabilizerImage(G,1);
## <self-similar group over [ 1 .. 2 ] with 5 generators>
## gap> GeneratorsOfGroup(last);
## [ <2|identity ...>, <2|u>, <2|t>, <2|u^-1>, <2|t> ]
## ]]></Example>
## </Description>
## </ManSection>
##
## <ManSection>
## <Oper Name="LevelStabilizer" Arg="g,n"/>
## <Returns>The fixator of the <A>n</A>th level of the tree.</Returns>
## <Description>
## This function constructs the normal subgroup of <A>g</A> that fixes
## the <A>n</A>th level of the tree.
## <Example><![CDATA[
## gap> G := FRGroup("t=<,t>(1,2)","a=(1,2)");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> LevelStabilizer(G,2);
## <self-similar group over [ 1 .. 2 ] with 9 generators>
## gap> Index(G,last);
## 8
## gap> IsNormal(G,last2);
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("StabilizerImage", [IsFRSemigroup, IsObject]);
DeclareOperation("LevelStabilizer", [IsFRSemigroup, IsInt]);
#############################################################################

#############################################################################
##
#O TreeWreathProduct
##
## <#GAPDoc Label="Products">
## <ManSection>
## <Oper Name="TreeWreathProduct" Arg="g,h,x0,y0" Label="FR group"/>
## <Returns>The tree-wreath product of groups <A>g,h</A>.</Returns>
## <Description>
## The tree-wreath product of two FR groups is a group generated by
## a copy of <A>g</A> and of <A>h</A>, in such a way that many
## conjugates of <A>g</A> commute.
##
## More formally, assume without loss of generality that all
## generators of <A>g</A> are states of a machine <C>m</C>, and that
## all generators of <A>h</A> are states of a machine <C>n</C>. Then
## the tree-wreath product is generated by the images of generators
## of <A>g,h</A> in <C>TreeWreathProduct(m,n,x0,y0)</C>.
##
## For the operation on FR machines see <Ref
## Oper="TreeWreathProduct" Label="FR machine"/>). It is described
## (with small variations, and in lesser generality) in
## <Cite Key="MR2197828"/>. For example, in
## <Example><![CDATA[
## gap> w := TreeWreathProduct(AddingGroup(2),AddingGroup(2),1,1);
## <recursive group over [ 1 .. 4 ] with 2 generators>
## gap> a := w.1; b := w.2;
## <Mealy element on alphabet [ 1 .. 4 ] with 3 states>
## <Mealy element on alphabet [ 1 .. 4 ] with 2 states>
## gap> Order(a); Order(b);
## infinity
## infinity
## gap> ForAll([-100..100],i->IsOne(Comm(a,a^(b^i))));
## true
## ]]></Example>
## the group <C>w</C> is the wreath product <M>Z\wr Z</M>.
## </Description>
## </ManSection>
##
## <ManSection>
## <Oper Name="WeaklyBranchedEmbedding" Arg="g"/>
## <Returns>A embedding of <A>g</A> in a weakly branched group.</Returns>
## <Description>
## This function constructs a new FR group, on alphabet the square of the
## alphabet of <A>g</A>. It is generated by the canonical copy of
## <A>g</A> and by the tree-wreath product of <A>g</A> with an adding
## machine on the same alphabet as <A>g</A> (see <Ref
## Oper="TreeWreathProduct" Label="FR group"/>). The function returns a
## group homomorphism into this new FR group.
##
## The main result of <Cite Key="MR1995624"/> is that the
## resulting group <M>h</M> is weakly branched. More precisely,
## <M>h'</M> contains <M>|X|^2</M> copies of itself.
## <Code><![CDATA[
## gap> f := WeaklyBranchedEmbedding(BabyAleshinGroup);;
## gap> Range(f);
## <recursive group over [ 1 .. 4 ] with 8 generators>
## ]]></Code>
## constructs a finitely generated branched group containing a free
## subgroup.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("TreeWreathProduct", [IsFRSemigroup, IsFRSemigroup, IsObject, IsObject]);
DeclareOperation("WeaklyBranchedEmbedding", [IsFRSemigroup]);
#############################################################################

--> --------------------

--> maximum size reached

--> --------------------

Quelle group.gd Sprache: unbekannt

[ Dauer der Verarbeitung: 0.15 Sekunden (vorverarbeitet) ]