|
#############################################################################
##
#W selfsimgroup.gi automgrp package Yevgen Muntyan
#W Dmytro Savchuk
##
#Y Copyright (C) 2003 - 2018 Yevgen Muntyan, Dmytro Savchuk
##
###############################################################################
##
#M SelfSimilarGroup(<list>)
##
InstallMethod(SelfSimilarGroup, "for [IsList]", [IsList],
function(list)
return SelfSimilarGroup(list, false);
end);
###############################################################################
##
#M SelfSimilarGroup(<list>, <bind_vars>)
##
InstallMethod(SelfSimilarGroup, "for [IsList, IsBool]", [IsList, IsBool],
function(list, bind_vars)
if not AG_IsCorrectRecurList(list, true) then
Error("in SelfSimilarGroup(IsList, IsBool):\n",
" given list is not a correct list representing self-similar group\n");
fi;
return GroupOfSelfSimFamily(SelfSimFamily(list, bind_vars));
end);
###############################################################################
##
#M SelfSimilarGroup(<list>, <names>)
##
InstallMethod(SelfSimilarGroup, "for [IsList, IsList]", [IsList, IsList],
function(list, names)
return SelfSimilarGroup(list, names, AG_Globals.bind_vars_autom_family);
end);
###############################################################################
##
#M SelfSimilarGroup(<list>, <names>, <bind_vars>)
##
InstallMethod(SelfSimilarGroup,
"for [IsList, IsList, IsBool]", [IsList, IsList, IsBool],
function(list, names, bind_vars)
if not AG_IsCorrectRecurList(list, true) then
Error("error in SelfSimilarGroup(IsList, IsList, IsBool):\n",
" given list is not a correct list representing self-similar group\n");
fi;
return GroupOfSelfSimFamily(SelfSimFamily(list, names, bind_vars));
end);
###############################################################################
##
#M SelfSimilarGroup(<string>)
#M SelfSimilarGroup(<string>, <bind_vars>)
##
InstallMethod(SelfSimilarGroup, "for [IsString]", [IsString],
function(string)
return SelfSimilarGroup(string, AG_Globals.bind_vars_autom_family);
end);
InstallMethod(SelfSimilarGroup, "for [IsString, IsBool]", [IsString, IsBool],
function(string, bind_vars)
local s;
s := AG_ParseAutomatonStringFR(string);
return SelfSimilarGroup(s[2], s[1], bind_vars);
end);
###############################################################################
##
#M SelfSimilarGroup(<A>)
#M SelfSimilarGroup(<A>, <bind_vars>)
##
InstallMethod(SelfSimilarGroup, "for [IsMealyAutomaton]", [IsMealyAutomaton],
function(A)
if not IsInvertible(A) then
Error("Automaton <A> is not invertible");
fi;
return SelfSimilarGroup(AutomatonList(A), A!.states);
end);
InstallMethod(SelfSimilarGroup, "for [IsMealyAutomaton, IsBool]", [IsMealyAutomaton, IsBool],
function(A, bind_vars)
if not IsInvertible(A) then
Error("Automaton <A> is not invertible");
fi;
return SelfSimilarGroup(AutomatonList(A), A!.states, bind_vars);
end);
###############################################################################
##
#M GroupOfSelfSimFamily(<G>)
##
InstallMethod(GroupOfSelfSimFamily, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
return GroupOfSelfSimFamily(UnderlyingSelfSimFamily(G));
end);
###############################################################################
##
#M IsGroupOfSelfSimFamily(<G>)
##
InstallMethod(IsGroupOfSelfSimFamily, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
return G = GroupOfSelfSimFamily(G);
end);
###############################################################################
##
#M UseSubsetRelation(<G>)
##
InstallMethod(UseSubsetRelation,
"for [IsSelfSimGroup, IsSelfSimGroup]",
[IsSelfSimGroup, IsSelfSimGroup],
function(super, sub)
## the full group is self similar, so if <super> is smaller than the full
## group then sub is smaller either
if HasIsGroupOfSelfSimFamily(super) then
if not IsGroupOfSelfSimFamily(super) then
SetIsGroupOfSelfSimFamily(sub, false); fi; fi;
TryNextMethod();
end);
###############################################################################
##
#M __AG_SubgroupOnLevel(<G>, <gens>, <level>)
##
InstallMethod(__AG_SubgroupOnLevel, [IsSelfSimGroup,
IsList and IsTreeAutomorphismCollection,
IsPosInt],
function(G, gens, level)
local overgroup;
if IsEmpty(gens) or (Length(gens) = 1 and IsOne(gens[1])) then
return TrivialSubgroup(G);
fi;
if HasIsGroupOfSelfSimFamily(G) and IsGroupOfSelfSimFamily(G) then
overgroup := G;
else
overgroup := GroupOfSelfSimFamily(UnderlyingSelfSimFamily(G));
fi;
return SubgroupNC(overgroup, gens);
end);
InstallOtherMethod(__AG_SubgroupOnLevel, [IsSelfSimGroup, IsList and IsEmpty, IsPosInt],
function(G, gens, level)
return TrivialSubgroup(G);
end);
InstallMethod(__AG_SubgroupOnLevel, [IsTreeAutomorphismGroup,
IsList and IsSelfSimCollection,
IsPosInt],
function(G, gens, level)
local overgroup;
overgroup := GroupOfSelfSimFamily(FamilyObj(gens[1]));
if Length(gens) = 1 and IsOne(gens[1]) then
return TrivialSubgroup(overgroup);
fi;
return SubgroupNC(overgroup, gens);
end);
InstallMethod(__AG_SimplifyGroupGenerators, "for [IsList and IsInvertibleSelfSimCollection]",
[IsList and IsInvertibleSelfSimCollection],
function(gens)
local words, fam;
if IsEmpty(gens) then
return [];
fi;
fam := FamilyObj(gens[1]);
words := FreeGeneratorsOfGroup(Group(List(gens, a -> a!.word)));
if fam!.use_rws and not IsEmpty(words) then
words := AG_ReducedForm(fam!.rws, words);
if IsEmpty(words) then
return [];
fi;
words := FreeGeneratorsOfGroup(Group(words));
fi;
return List(words, w -> SelfSim(w, fam));
end);
###############################################################################
##
#M PrintObj(<G>)
##
InstallMethod(PrintObj, "for [IsSelfSimilarGroup]",
[IsSelfSimilarGroup],
function(G)
Print("SelfSimilarGroup(\"", String(G), "\")");
end);
###############################################################################
##
#M Display(<G>)
##
InstallMethod(Display, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
local i, gens, printone;
printone := function(a)
Print(a, " = ", Decompose(a));
end;
gens := GeneratorsOfGroup(G);
if gens = [] then Print("< >"); fi;
if Length(gens) = 1 then
Print("< "); printone(gens[1]); Print(" >");
else
Print("< "); printone(gens[1]); Print(", \n");
for i in [2..Length(gens)-1] do
Print(" "); printone(gens[i]); Print(", \n");
od;
Print(" "); printone(gens[Length(gens)]); Print(" >");
fi;
end);
#############################################################################
##
#M String(<G>)
##
InstallMethod(String, "for [IsSelfSimGroup]", [IsSelfSimGroup],
function(G)
local i, gens, formatone, s;
formatone := function(a)
return Concatenation(String(a), " = ", String(Decompose(a)));
end;
gens := GeneratorsOfGroup(G);
s := "";
for i in [1..Length(gens)] do
Append(s, formatone(gens[i]));
if i <> Length(gens) then
Append(s, ", ");
fi;
od;
return s;
end);
###############################################################################
##
#M ViewObj(<G>)
##
InstallMethod(ViewObj, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
local i, gens;
gens := List(GeneratorsOfGroup(G), g -> Word(g));
if gens = [] then Print("< >"); fi;
Print("< ");
for i in [1..Length(gens)-1] do
if IsOne(gens[i]) then
Print(AG_Globals.identity_symbol, ", ");
else
Print(gens[i], ", ");
fi;
od;
if IsOne(gens[Length(gens)]) then
Print(AG_Globals.identity_symbol, " >");
else
Print(gens[Length(gens)], " >");
fi;
end);
###############################################################################
##
#M IsFractalByWords(G)
##
InstallMethod(IsFractalByWords, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function (G)
local freegens, stab, i, sym, f;
sym := GroupWithGenerators(List(GeneratorsOfGroup(G), g -> Perm(g)));
if not IsTransitive(sym, [1..DegreeOfTree(G)]) then
Info(InfoAutomGrp, 1, "group is not transitive on first level");
return false;
fi;
f := GroupWithGenerators(List(GeneratorsOfGroup(G), g -> Word(g)));
stab := StabilizerOfFirstLevel(G);
stab := List(GeneratorsOfGroup(stab), a -> StatesWords(a));
for i in [1..DegreeOfTree(G)] do
if f <> GroupWithGenerators(List(stab, s -> s[i])) then
return false;
fi;
od;
return true;
end);
###############################################################################
##
#M Size(G)
##
InstallMethod(Size, "for [IsSelfSimGroup]", [IsSelfSimGroup],
function (G)
local f;
if IsTrivial(G) then
Info(InfoAutomGrp, 3, "Size(G): 1, G is trivial");
return 1;
fi;
if CanEasilyTestSphericalTransitivity(G) and IsSphericallyTransitive(G) then
Info(InfoAutomGrp, 3, "Size(G): infinity, G is spherically transitive");
return infinity;
fi;
if IsFractalByWords(G) then
Info(InfoAutomGrp, 3, "Size(G): infinity, G is fractal by words");
return infinity;
fi;
if HasIsFractal(G) and IsFractal(G) then
Info(InfoAutomGrp, 3, "Size(G): infinity, G is fractal");
return infinity;
fi;
if IsSelfSimilarGroup(G) and LevelOfFaithfulAction(G, 8)<>fail then
return Size(G);
fi;
f := FindElementOfInfiniteOrder(G, 10, 10);
if HasSize(G) or f <> fail then
return Size(G);
fi;
Info(InfoAutomGrp, 1, "You can try to use IsomorphismPermGroup(<G>) or\n",
" FindElementOfInfiniteOrder( <G>, <length>, <depth> ) with bigger bounds");
TryNextMethod();
end);
InstallOtherMethod(LevelOfFaithfulAction, "for [IsSelfSimGroup and IsSelfSimilar, IsCyclotomic]",
[IsSelfSimGroup and IsSelfSimilar, IsCyclotomic],
function(G, max_lev)
local s, s_next, lev;
if HasIsFinite(G) and not IsFinite(G) then return fail; fi;
if HasLevelOfFaithfulAction(G) then return LevelOfFaithfulAction(G); fi;
lev := 0; s := 1; s_next := Size(PermGroupOnLevel(G, 1));
while s<s_next and lev<max_lev do
lev := lev+1;
s := s_next;
s_next := Size(PermGroupOnLevel(G, lev+1));
od;
if s=s_next then
SetSize(G, s);
SetLevelOfFaithfulAction(G, lev);
return lev;
else
return fail;
fi;
end);
InstallMethod(LevelOfFaithfulAction, "for [IsSelfSimGroup and IsSelfSimilar]",
[IsSelfSimGroup and IsSelfSimilar],
function(G)
return LevelOfFaithfulAction(G, infinity);
end);
################################################################################
##
#O IsomorphismPermGroup (<G>)
#O IsomorphismPermGroup (<G>, <max_lev>)
##
## For a given finite group <G> generated by initial automata or by elements defined by
## wreath recursion
## computes an isomorphism from <G> into a finite permutational group.
## If <G> is not known to be self-similar (see "IsSelfSimilar") the isomorphism is based on the
## regular representation, which works generally much slower. If <G> is self-similar
## there is a level of the tree (see "LevelOfFaithfulAction"), where <G> acts faithfully.
## The corresponding representation is returned in this case. If <max_lev> is given
## it finds only the first <max_lev> quotients by stabilizers and if all of them have
## different size it returns `fail'.
## If <G> is infinite and <max_lev> is not specified it will loop forever.
##
## For example, consider a subgroup $\langle a, b\rangle$ of Grigorchuk group.
## \beginexample
## gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
## < a, b, c, d >
## gap> f := IsomorphismPermGroup(Group(a, b));
## MappingByFunction( < a, b >, Group(
## [ (1,2)(3,5)(4,6)(7,9)(8,10)(11,13)(12,14)(15,17)(16,18)(19,21)(20,22)(23,
## 25)(24,26)(27,29)(28,30)(31,32), (1,3)(2,4)(5,7)(6,8)(9,11)(10,12)(13,
## 15)(14,16)(17,19)(18,20)(21,23)(22,24)(25,27)(26,28)(29,31)(30,32)
## ]), function( g ) ... end, function( b ) ... end )
## gap> Size(Image(f));
## 32
## gap> H := SelfSimilarGroup("a=(a*b,1)(1,2), b=(1,b*a^-1)(1,2), c=(b, a*b)");
## < a, b, c >
## gap> f1 := IsomorphismPermGroup(H);
## MappingByFunction( < a, b, c >, Group([ (1,3)(2,4), (1,3)(2,4), (1,2)
## ]), function( g ) ... end, function( b ) ... end )
## gap> Size(Image(f1));
## 8
## gap> PreImagesRepresentative(f1, (1,3,2,4));
## a*c
## gap> (a*c)^f1;
## (1,3,2,4)
## \endexample
##
InstallOtherMethod(IsomorphismPermGroup, "for [IsSelfSimilarGroup, IsCyclotomic]",
[IsSelfSimGroup and IsSelfSimilar, IsCyclotomic],
function (G, n)
local H, lev;
lev := LevelOfFaithfulAction(G, n);
if lev <> fail then
H := PermGroupOnLevel(G, LevelOfFaithfulAction(G));
return AG_GroupHomomorphismByImagesNC(G, H, GeneratorsOfGroup(G), GeneratorsOfGroup(H));
fi;
return fail;
end);
###############################################################################
##
#M IsSphericallyTransitive(G)
##
InstallMethod(IsSphericallyTransitive, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function (G)
local x, rat_gens, abel_hom, lev;
if IsFractalByWords(G) then
Info(InfoAutomGrp, 3, "IsSphericallyTransitive(G): true");
Info(InfoAutomGrp, 3, " G is fractal");
return true;
fi;
if IsTrivial(G) then
Info(InfoAutomGrp, 3, "IsSphericallyTransitive(G): false");
Info(InfoAutomGrp, 3, " G is trivial: G = ", G);
return false;
fi;
if HasIsFinite(G) and IsFinite(G) then
Info(InfoAutomGrp, 3, "IsSphericallyTransitive(G): false");
Info(InfoAutomGrp, 3, " IsFinite(G): G = ", G);
return false;
fi;
if DegreeOfTree(G) = 2 and TestSelfSimilarity(G) and IsSelfSimilar(G) then
if HasIsFinite(G) and IsFinite(G)=false then
Info(InfoAutomGrp, 3, "IsSphericallyTransitive(G): true");
Info(InfoAutomGrp, 3, " <G> is infinite self-similar acting on binary tree");
return true;
fi;
if PermGroupOnLevel(G, 2)=Group((1, 4, 2, 3)) then
Info(InfoAutomGrp, 3, "IsSphericallyTransitive(G): true");
Info(InfoAutomGrp, 3, " any element which acts transitively on the first level acts spherically transitively");
return true;
fi;
fi;
for lev in [1..8] do
if not IsTransitiveOnLevel(G,lev) then
Info(InfoAutomGrp, 3, "IsSphericallyTransitive(G): false");
Info(InfoAutomGrp, 3, " the group does not act transitively on level ", lev);
return false;
fi;
od;
TryNextMethod();
end);
###############################################################################
##
#M DiagonalPower(<G>, <n>)
##
InstallOtherMethod( DiagonalPower,
"for [IsSelfSimGroup and IsGroupOfSelfSimFamily, IsPosInt]",
[IsSelfSimGroup and IsGroupOfSelfSimFamily, IsPosInt],
function(G, n)
return DiagonalPower(UnderlyingSelfSimFamily(G), n);
end);
###############################################################################
##
#M MultAutomAlphabet(<G>, <n>)
##
InstallOtherMethod( MultAutomAlphabet,
"for [IsSelfSimGroup and IsGroupOfSelfSimFamily, IsPosInt]",
[IsSelfSimGroup and IsGroupOfSelfSimFamily, IsPosInt],
function(G, n)
return MultAutomAlphabet(UnderlyingSelfSimFamily(G), n);
end);
###############################################################################
##
#M \= (<G>, <H>)
##
InstallMethod(\=, "for [IsSelfSimGroup, IsSelfSimGroup]",
IsIdenticalObj, [IsSelfSimGroup, IsSelfSimGroup],
function(G, H)
local fgens1, fgens2, fam;
if HasIsGroupOfSelfSimFamily(G) and HasIsGroupOfSelfSimFamily(H) then
if IsGroupOfSelfSimFamily(G) <> IsGroupOfSelfSimFamily(H) then
Info(InfoAutomGrp, 3, "G = H: false, exactly one is GroupOfSelfSimFamily");
return false;
fi;
if IsGroupOfSelfSimFamily(G) then
Info(InfoAutomGrp, 3, "G = H: true, both are GroupOfSelfSimFamily");
return true;
fi;
fi;
fgens1 := List(GeneratorsOfGroup(G), g -> Word(g));
fgens2 := List(GeneratorsOfGroup(H), g -> Word(g));
fam := UnderlyingSelfSimFamily(G);
if fam!.rws <> fail then
fgens1 := AG_ReducedForm(fam!.rws, fgens1);
fgens2 := AG_ReducedForm(fam!.rws, fgens2);
fi;
if GroupWithGenerators(fgens1) = GroupWithGenerators(fgens2) then
Info(InfoAutomGrp, 3, "G = H: true, by subgroups of free group");
return true;
fi;
TryNextMethod();
end);
###############################################################################
##
#M IsSubset (<G>, <H>)
##
InstallMethod(IsSubset, "for [IsSelfSimGroup, IsSelfSimGroup]",
IsIdenticalObj, [IsSelfSimGroup, IsSelfSimGroup],
function(G, H)
local h, fam, fgens1, fgens2;
if HasIsGroupOfSelfSimFamily(G) and IsGroupOfSelfSimFamily(G) then
Info(InfoAutomGrp, 3, "IsSubgroup(G, H): true");
Info(InfoAutomGrp, 3, " G is GroupOfSelfSimFamily");
return true;
fi;
fgens1 := List(GeneratorsOfGroup(G), g -> Word(g));
fgens2 := List(GeneratorsOfGroup(H), g -> Word(g));
fam := UnderlyingSelfSimFamily(G);
if fam!.rws <> fail then
fgens1 := AG_ReducedForm(fam!.rws, fgens1);
fgens2 := AG_ReducedForm(fam!.rws, fgens2);
fi;
if IsSubgroup(GroupWithGenerators(fgens1), GroupWithGenerators(fgens2)) then
Info(InfoAutomGrp, 3, "IsSubgroup(G, H): true");
Info(InfoAutomGrp, 3, " by subgroups of free group");
return true;
fi;
TryNextMethod();
end);
###############################################################################
##
#M <g> in <G>
##
InstallMethod(\in, "for [IsSelfSim, IsSelfSimGroup]",
[IsSelfSim, IsSelfSimGroup],
function(g, G)
local fam, fgens, w;
if HasIsGroupOfSelfSimFamily(G) and IsGroupOfSelfSimFamily(G) then
return true;
fi;
fgens := List(GeneratorsOfGroup(G), g -> Word(g));
w := Word(g);
fam := UnderlyingSelfSimFamily(G);
if fam!.rws <> fail then
fgens := AG_ReducedForm(fam!.rws, fgens);
w := AG_ReducedForm(fam!.rws, w);
fi;
if w in GroupWithGenerators(fgens) then
Info(InfoAutomGrp, 3, "g in G: true");
Info(InfoAutomGrp, 3, " by elements of free group");
Info(InfoAutomGrp, 3, " g = ", g, "; G = ", G);
return true;
fi;
TryNextMethod();
end);
###############################################################################
##
#O Random(<G>)
##
## Returns a random element of a group (semigroup) <G>. The operation is based
## on the generator of random elements in free groups and semigroups.
##
## \beginexample
## gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
## < u, v >
## gap> Random( Basilica );
## v*u^-3
## \endexample
##
InstallMethodWithRandomSource(Random, "for a random source and [IsSelfSimGroup]",
[IsRandomSource, IsSelfSimGroup],
function(rs, G)
local F, gens, pi;
if IsTrivial(G) then
return One(G);
elif IsSelfSimilarGroup(G) then
return SelfSim(Random(rs, UnderlyingFreeGroup(G)), UnderlyingSelfSimFamily(G));
else
gens := GeneratorsOfGroup(G);
F := FreeGroup(Length(gens));
pi := GroupHomomorphismByImagesNC(F, G, GeneratorsOfGroup(F), gens);
return Random(rs, F)^pi;
fi;
end);
###############################################################################
##
#M UnderlyingFreeSubgroup(<G>)
##
InstallMethod(UnderlyingFreeSubgroup, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
local f;
if HasIsGroupOfSelfSimFamily(G) and IsGroupOfSelfSimFamily(G) then
return UnderlyingFreeGroup(G);
fi;
f := Subgroup(UnderlyingFreeGroup(G), UnderlyingFreeGenerators(G));
if f = UnderlyingFreeGroup(G) then
SetIsGroupOfSelfSimFamily(G, true);
fi;
return f;
end);
###############################################################################
##
#M UnderlyingFreeGenerators(<G>)
##
InstallMethod(UnderlyingFreeGenerators, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
return List(GeneratorsOfGroup(G), g -> Word(g));
end);
###############################################################################
##
#M TrivialSubmagmaWithOne(<G>)
##
InstallMethod(TrivialSubmagmaWithOne, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
return Subgroup(G, [One(G)]);
end);
###############################################################################
##
#M IsSelfSimilarGroup(<G>)
##
## Returns `true' if generators of <G> coincide with generators of the family
InstallImmediateMethod(IsSelfSimilarGroup, IsSelfSimGroup, 0,
function(G)
local fam;
fam := UnderlyingSelfSimFamily(G);
return fam!.numstates = 0 or
GeneratorsOfGroup(G) = fam!.recurgens{[1..fam!.numstates]};
end);
###############################################################################
##
#M RecurList(<G>)
##
InstallMethod(RecurList, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
if IsSelfSimilarGroup(G) then
return RecurList(GroupOfSelfSimFamily(UnderlyingSelfSimFamily(G)));
else
Error("Group <G> is not necessarily self-similar");
fi;
end);
###############################################################################
##
#M IsSelfSimilar(<G>)
##
InstallMethod(IsSelfSimilar, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
local g, i, res;
res := true;
for g in GeneratorsOfGroup(G) do
for i in [1..UnderlyingSelfSimFamily(G)!.deg] do
res := Section(g, i) in G;
if res = fail then
TryNextMethod();
elif not res then
return false;
fi;
od;
od;
return true;
end);
###############################################################################
##
#M UnderlyingSelfSimFamily(<G>)
##
InstallMethod(UnderlyingSelfSimFamily, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
return FamilyObj(GeneratorsOfGroup(G)[1]);
end);
###############################################################################
##
#M IsFiniteState(<G>)
##
InstallMethod(IsFiniteState, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
local states, MealyAutomatonLocal, aut_list, gens, images, H, g, hom_function, \
inv_hom_function, hom, free_groups_hom, inv_free_groups_hom, inv_hom, \
gens_in_freegrp, images_in_freegrp, preimages_in_freegrp, F, pi, pi_bar, \
preimage_in_freegrp, MealyAutomatonLocalFinite;
# if we do not know much, we compare just words in free group
MealyAutomatonLocal := function(g)
local cur_state;
if g!.word in states then return Position(states, g!.word); fi;
Add(states, g!.word);
cur_state := Length(states);
aut_list[cur_state] := List([1..g!.deg], x -> MealyAutomatonLocal(Section(g, x)));
Add(aut_list[cur_state], g!.perm);
return cur_state;
end;
# if we do know that the groups is finite, we compare actual elements of the group
MealyAutomatonLocalFinite := function(g)
local cur_state;
if g in states then return Position(states, g); fi;
Add(states, g);
cur_state := Length(states);
aut_list[cur_state] := List([1..g!.deg], x -> MealyAutomatonLocalFinite(Section(g, x)));
Add(aut_list[cur_state], g!.perm);
return cur_state;
end;
if IsTrivial(G) then return true; fi;
states := [];
aut_list := [];
gens := GeneratorsOfGroup(G);
images := [];
if HasIsFinite(G) and IsFinite(G) then
for g in gens do
Add(images, MealyAutomatonLocalFinite(g));
od;
states := List(states, Word);
else
for g in gens do
Add(images, MealyAutomatonLocal(g));
od;
fi;
H := AutomatonGroup(aut_list);
if IsTrivial(H) then
SetIsTrivial( G, true);
return true;
fi;
images := UnderlyingAutomFamily(H)!.oldstates{images};
SetIsomorphicAutomGroup(G, GroupWithGenerators(UnderlyingAutomFamily(H)!.automgens{images}));
SetUnderlyingAutomatonGroup(G, H);
# preimages of generators of G in UnderlyingFreeGroup(G)
gens_in_freegrp := List(GeneratorsOfGroup(G), Word);
# preimages of generators of a subgroup of H isomorphic to G in UnderlyingFreeGroup(H)
images_in_freegrp := List(UnderlyingAutomFamily(H)!.automgens{images}, Word);
preimage_in_freegrp := function(x)
local w;
w := LetterRepAssocWord(x!.word)[1];
if w > 0 then
return states[ Position( UnderlyingAutomFamily(H)!.oldstates, w)];
else
return states[ Position( UnderlyingAutomFamily(H)!.oldstates, -w+UnderlyingAutomFamily(H)!.numstates)];
fi;
end;
# preimages of generators of H in UnderlyingFreeGroup(G)
# preimages_in_freegrp := List([1..Length(GeneratorsOfGroup(H))], x->states[Position(UnderlyingAutomFamily(H)!.oldstates, x)]);
preimages_in_freegrp := List(GeneratorsOfGroup(H), x -> preimage_in_freegrp(x));
if IsSelfSimilarGroup(G) then
free_groups_hom :=
GroupHomomorphismByImagesNC( Group(gens_in_freegrp), UnderlyingFreeGroup(H),
gens_in_freegrp, images_in_freegrp );
inv_free_groups_hom :=
GroupHomomorphismByImagesNC( UnderlyingFreeGroup(H), UnderlyingFreeGroup(G),
UnderlyingFreeGenerators(H), preimages_in_freegrp );
hom_function := function(a)
return Autom(Image(free_groups_hom, a!.word), UnderlyingAutomFamily(H));
end;
inv_hom_function := function(b)
return SelfSim(Image(inv_free_groups_hom, b!.word), UnderlyingSelfSimFamily(G));
end;
hom := GroupHomomorphismByFunction(G, GroupWithGenerators(UnderlyingAutomFamily(H)!.automgens{images}), hom_function, inv_hom_function);
SetMonomorphismToAutomatonGroup(G, hom);
else
F := FreeGroup(Length(GeneratorsOfGroup(G)));
# pi
# F ------> G ----> UnderlyingFreeGroup(H)
# -------------->
# pi_bar
pi := GroupHomomorphismByImages(F, Group(gens_in_freegrp),
GeneratorsOfGroup(F), gens_in_freegrp);
pi_bar := GroupHomomorphismByImages(F, UnderlyingFreeGroup(H),
GeneratorsOfGroup(F), images_in_freegrp);
hom_function := function(g)
return Autom(Image(pi_bar, PreImagesRepresentative(pi, g!.word)), UnderlyingAutomFamily(H));
end;
inv_hom_function := function(b)
return SelfSim(Image(pi, PreImagesRepresentative(pi_bar, b!.word)), UnderlyingSelfSimFamily(G));
end;
hom := GroupHomomorphismByFunction(G, GroupWithGenerators(UnderlyingAutomFamily(H)!.automgens{images}), hom_function, inv_hom_function);
SetMonomorphismToAutomatonGroup(G, hom);
fi;
return true;
end);
###############################################################################
##
#M IsomorphicAutomGroup( <G> )
##
InstallMethod(IsomorphicAutomGroup, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
if IsFiniteState(G) then return IsomorphicAutomGroup(G); fi;
end);
###############################################################################
##
#M UnderlyingAutomatonGroup( <G> )
##
InstallMethod(UnderlyingAutomatonGroup, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
if IsFiniteState(G) then return UnderlyingAutomatonGroup(G); fi;
end);
###############################################################################
##
#M MonomorphismToAutomatonGroup( <G> )
##
InstallMethod(MonomorphismToAutomatonGroup, "for [IsSelfSimGroup]",
[IsSelfSimGroup],
function(G)
if IsFiniteState(G) then return MonomorphismToAutomatonGroup(G); fi;
end);
###############################################################################
##
#M IsContracting( <G> )
##
InstallMethod(IsContracting, "for [IsSelfSimilarGroup]",
[IsSelfSimilarGroup],
function(G)
local res;
if not IsFiniteState(G) then
# every contracting self-similar group is finite-state
return false;
fi;
res := IsContracting(GroupOfAutomFamily(UnderlyingAutomFamily(UnderlyingAutomatonGroup(G))));
UnderlyingSelfSimFamily(G)!.use_contraction := true;
UnderlyingAutomFamily(UnderlyingAutomatonGroup(G))!.use_contraction := true;
return res;
end);
###############################################################################
##
#M GroupNucleus( <G> )
##
InstallMethod(GroupNucleus, "for [IsSelfSimilarGroup]",
[IsSelfSimilarGroup],
function(G)
local H;
if not IsFiniteState(G) then
# every contracting self-similar group is finite-state
Error("Group <G> is not finite-state");
fi;
if not IsContracting(G) then
Error("Group <G> is not contracting");
fi;
H := GroupOfAutomFamily( UnderlyingAutomFamily( UnderlyingAutomatonGroup(G)));
return List( GroupNucleus(H), x -> PreImagesRepresentative( MonomorphismToAutomatonGroup(G), x));
end);
###############################################################################
##
#M UseContraction( <G> )
##
InstallMethod(UseContraction, "for [IsSelfSimGroup]", true,
[IsSelfSimGroup],
function(G)
if not IsSelfSimilarGroup(G) then
Print("Error in UseContraction(<G>): The method is implemented only for IsSelfSimilarGroup\n");
return fail;
fi;
if not HasIsContracting(G) then
Print("Error in UseContraction(<G>): It is not known whether the group <G> is contracting\n");
return fail;
elif not IsContracting(G) then
Print("Error in UseContraction(<G>): The group <G> is not contracting");
return fail;
fi;
# IsContracting returns either true or false or an error (it can not return fail)
UnderlyingSelfSimFamily(G)!.use_contraction := true;
UnderlyingAutomFamily( UnderlyingAutomatonGroup(G))!.use_contraction := true;
return true;
end);
###############################################################################
##
#M DoNotUseContraction( <G> )
##
InstallMethod(DoNotUseContraction, "for [IsSelfSimGroup]", true,
[IsSelfSimGroup],
function(G)
UnderlyingAutomFamily(G)!.use_contraction := false;
if HasUnderlyingAutomatonGroup(G) then
UnderlyingAutomFamily( UnderlyingAutomatonGroup(G))!.use_contraction := false;
fi;
return true;
end);
###############################################################################
##
#M FindNucleus( <G> )
##
InstallMethod(FindNucleus, "for [IsSelfSimilarGroup, IsCyclotomic]",
[IsSelfSimilarGroup, IsCyclotomic],
function(G, max_nucl)
local H, nuclH, nuclG;
if not IsFiniteState(G) then
# every contracting self-similar group is finite-state
Error("Group <G> is not finite-state");
fi;
if HasIsContracting(G) and not IsContracting(G) then
Error("Group <G> is not contracting");
fi;
H := GroupOfAutomFamily( UnderlyingAutomFamily( UnderlyingAutomatonGroup( G )));
if HasIsContracting(H) and not IsContracting(H) then
Error("Group <G> is not contracting");
fi;
nuclH := FindNucleus(H, max_nucl);
if nuclH=fail then return fail; fi;
nuclG := [];
Add(nuclG, List( GeneratingSetWithNucleus(H), x -> PreImagesRepresentative( MonomorphismToAutomatonGroup( G ), x )));
Add(nuclG, List( GroupNucleus(H), x -> PreImagesRepresentative( MonomorphismToAutomatonGroup( G ), x )));
Add(nuclG, GeneratingSetWithNucleusAutom(H));
SetGroupNucleus(G, nuclG[1]);
SetGeneratingSetWithNucleus(G, nuclG[2]);
SetGeneratingSetWithNucleusAutom(G, nuclG[3]);
SetContractingLevel(G, ContractingLevel(H));
return nuclG;
end);
InstallMethod(FindNucleus, "for [IsSelfSimilarGroup]", true,
[IsSelfSimilarGroup],
function(G)
return FindNucleus(G, infinity);
end);
InstallMethod(GeneratingSetWithNucleus, "for [IsSelfSimilarGroup]", true,
[IsSelfSimilarGroup],
function(G)
if IsContracting(G) then return GeneratingSetWithNucleus(G); fi;
end);
InstallMethod(GeneratingSetWithNucleusAutom, "for [IsSelfSimilarGroup]", true,
[IsSelfSimilarGroup],
function(G)
if IsContracting(G) then return GeneratingSetWithNucleusAutom(G); fi;
end);
#E
[ Dauer der Verarbeitung: 0.59 Sekunden
(vorverarbeitet)
]
|
