#############################################################################
##
#W AutGrp.gi FGA package Christian Sievers
##
## Methods for automorphism groups of free groups
##
#Y 2003 - 2012
##
#############################################################################
##
#M AutomorphismGroup( <group> )
##
InstallMethod( AutomorphismGroup,
"for free groups",
[ CanComputeWithInverseAutomaton ],
function( G )
local n, aut;
n := RankOfFreeGroup( G );
if n = 0 then
aut := AsGroup( [ IdentityMapping ( G ) ] );
elif n = 1 then
aut := Group( FreeGroupAutomorphismsGeneratorO( G ) );
SetSize( aut, 2 );
elif n = 2 then
aut := Group( FreeGroupAutomorphismsGeneratorO( G ),
FreeGroupAutomorphismsGeneratorP( G ),
FreeGroupAutomorphismsGeneratorU( G ) );
elif n = 3 then
aut := Group( FreeGroupAutomorphismsGeneratorS( G ),
FreeGroupAutomorphismsGeneratorT( G ),
FreeGroupAutomorphismsGeneratorU( G ) );
elif IsEvenInt( n ) then
aut := Group( FreeGroupAutomorphismsGeneratorQ( G ),
FreeGroupAutomorphismsGeneratorR( G ) );
else # n > 3, odd
aut := Group( FreeGroupAutomorphismsGeneratorS( G ),
FreeGroupAutomorphismsGeneratorR( G ) );
fi;
SetIsFinite( aut, n <= 1 );
SetFilterObj( aut, IsAutomorphismGroupOfFreeGroup );
return aut;
end );
#############################################################################
##
#M \in( <hom>, <autgrp> )
##
## tests whether <hom> is in <autgrp>.
##
## Code contributed by Max Horn.
InstallMethod( \in,
"for automorphism groups of free groups",
[ IsGroupGeneralMapping, IsAutomorphismGroupOfFreeGroup ],
function( hom, aut )
local G;
G := AutomorphismDomain( aut );
return Source( hom ) = G and Range( hom ) = G and IsBijective( hom );
end );
#############################################################################
##
#M IsomorphismFpGroup( <group> )
##
## returns an isomorphism from an automorphism group of a free group
## to a finitely presented group.
##
## The presentation follows Bernhard Neumann (see ../doc/manual.bib)
## Numbers in the comments refer to the equation numbers in that paper.
##
InstallMethod( IsomorphismFpGroup,
"for automorphism groups of free groups",
[ IsAutomorphismGroupOfFreeGroup ],
function( aut )
local n, f, fp, O, P, U, S, T, Q, R, rels, moreRels,
o, p, u, s, t, q, r, iso, isoinv;
n := RankOfFreeGroup( AutomorphismDomain ( aut ));
if n = 0 then
fp := FreeGroup( 0 );
iso := aut -> One( fp );
elif n = 1 then
f := FreeGroup( "O" );
O := f.1;
rels := [ O^2 ]; # 6a
fp := f / rels;
o := fp.1;
iso := aut -> o ^ (Order(aut) - 1);
elif n = 2 then
f := FreeGroup( "O", "P", "U" );
O := f.1; P := f.2; U := f.3;
rels := [ P^2 # 5a
, O^2 # 6a
, (O*P)^4 # 8a
, Comm( U, O*U*O ) # 7e
, (P*O*P*U)^2 # 7i
, (U*P*O)^3 # 8b
];
fp := f / rels;
o := fp.1; p := fp.2; u := fp.3;
iso := FGA_CurryAutToPQOU( p, p, o, u); # Q=P
elif n = 3 then
f := FreeGroup( "S", "T", "U" );
S := f.1; T := f.2; U := f.3;
rels := [ (S^5*T^-1)^2 # 19a
, T^-1*S*T^2*S^8*T^-1*S*T^2*S^-4 # 19b
, (S^4*T^-1*S*T^-1)^2 # 19c
, T^4 # 19d
, Comm( U, S^2*T^-1*S*T^-1*S^2 ) # 19e
, Comm( U, S^-2*T^-1*S*T^-1*U*S^-2*T^-1*S*T^-1) # 19f
# wrong: Comm( U, S^2*T^-1*S*T*S*T^-1*U*T*S^-1*T^-1*S^-1*T*S^2 ) # 19g
, Comm( U, S^-2*T^-1*S*T*S*T^-1*U*
T*S^-1*T^-1*S^-1*T*S^2 ) # 19g corrected
, Comm( U, T^-1*S*T^2*U*T^-1*S*T^2 ) # 19h
, S^-2*T^-1*S*T^2*S^2*U*S^2*T^-1*S*T^2*S^2*
U*S^-2*U*S^2*U^-1*S^-2*U^-1 # 19i
, (S^-2*T^-1*S*T*U)^2 # 19j
, (U*T)^3 # 19k
];
fp := f / rels;
s := fp.1; t := fp.2; u := fp.3;
iso := FGA_CurryAutToPQOU( t*s^3*(s*t^-1)^2 # 16c
, s^4 # 16a
, s^3*(s*t^-1)^2 # 16b
, u
);
elif IsEvenInt(n) then
f := FreeGroup( "Q", "R" );
Q := f.1; R := f.2;
rels := [ (R^3*(Q*R^3)^(n-1))^2 # 22a
, (Q*R^3)^(2*(n-1)) # 22d
, Q^n # 22e
, Comm( (Q*R^3)^(n-1),
Q^-1*R^3*(Q*R^3)^(n-1)*Q ) # 22f
, Comm( Q^-2*R^4*Q^2*R^-3,
Q*R^-3*Q^-1*R^-3*Q ) # 22h
, Comm( R^4, (Q*R^3)^(n-1) ) # 22j
, Comm( R^4, Q^-2*R^4*Q^2 ) # 22k
, Comm( Q^-2*R^4*Q^2*R^-3,
(Q*R^3)^(n-1)*Q^-2*R^4*Q^2*R^-3*(Q*R^3)^(n-1) ) # 22l
, Comm( Q^-2*R^4*Q^2*R^-3,
R^-3*Q^-1*Q^-2*R^4*Q^2*R^-3*Q*R^3 ) # 22m
, Comm( Q^-2*R^4*Q^2*R^-3,
R^-3*Q^-1*R^-3*(Q*R^3)^n*Q^-2*R^4*
Q^2*R^-3*(Q*R^3)^-n*R^3*Q*R^3 ) # 22n
, (Q*R^3)^-n*Q^-2*R^4*Q^2*R^-3*(Q*R^3)^n*
Q^-3*R^4*Q^2*R^-3*Q^-1*R^4*Q^2*R^-3*
Q^-1*R^3*Q^-2*R^-4*Q^3*R^3*Q^-2*R^-4*Q^2 # 22o
, (R^3*(Q*R^3)^(n-1)*Q^-2*R^4*Q^2)^2 # 22p
, R^12 # 22q
];
# finally the relations 22c:
moreRels := List( [ 2 .. n/2 ],
i -> Comm( R^3*(Q*R^3)^(n-1),
Q^-i*R^3*(Q*R^3)^(n-1)*Q^i ) );
fp := f / Concatenation(rels, moreRels);
q := fp.1; r := fp.2;
iso := FGA_CurryAutToPQOU( r^3*(q*r^3)^(n-1) # 21b
, q
, (q*r^3)^(n-1) # 21a
, q^-2*r^4*q^2*r^-3 # 21c
);
else # n > 3, odd
f := FreeGroup( "S", "R" );
S := f.1; R := f.2;
rels := [ (R^3*S^n*(S*R^-3)^(n-1))^2 # 25a
, (S^(n+1)*R^3*S^n*(S*R^-3)^(n-1))^(n-1)*
S^((-n)*(n-1)) # 25b
, ((S^n)*(S*R^-3)^(n-1))^2 # 25d
, Comm( S^n*(S*R^-3)^(n-1),
S^-(n+1)*R^3*S^n*
(S*R^-3)^(n-1)*S^(n+1) ) # 25e
, Comm( S^-2*R^4*S^2*R^3,
S*R^-3*S^(n-1)*R^-3*S ) # 25f
, Comm( R^4, S^n*(S*R^-3)^(n-1) ) # 25g
, Comm( R^4, S^-2*R^4*S^2 ) # 25h
, Comm( S^-2*R^4*S^2*R^-3,
S^n*(S*R^-3)^(n-1)*S^-2*R^4*S^2*
R^-3*S^n*(S*R^-3)^(n-1) ) # 25i
, Comm( S^-2*R^4*S^2*R^-3,
R^-3*S^-(n+1)*S^-2*R^4*S^2*
R^-3*S^(n+1)*R^3 ) # 25j
# wrong: , Comm( S^-2*R^4*S^2*R^-3,
# R^-3*S^-1*R^-3*S*R^3*S^n*
# (S*R^-3)^(n-1)*S^-2*R^4*S^2*R^3*
# (S*R^-3)^(n-1)*S^n*R^-3*S^-1*
# R^3*S*R^3 ) # 25k
, Comm( S^-2*R^4*S^2*R^-3,
R^-3*S^-1*R^-3*S*R^3*S^n*
(S*R^-3)^(n-1)*S^-2*R^4*S^2*R^-3*
(S*R^-3)^(n-1)*S^n*R^-3*S^-1*
R^3*S*R^3 ) # 25k corrected
, R^3*(S*R^-3)^(n-1)*S^-3*R^4*S^2*R^-3*S*
R^3*(S*R^-3)^(n-1)*S^(n-3)*R^4*S^2*R^-3*
S^(n-1)*R^4*S^2*R^-3*S^(n-1)*R^3*S^-2*
R^-4*S^(n+3)*R^3*S^-2*R^-4*S^2 # 25l
, (R^3*(S*R^-3)^(n-1)*S^(n-2)*R^4*S^2)^2 # 25m
, R^12 # 22q
] ;
# and finally the relations 25c:
moreRels := List( [ 2 .. (n-1)/2 ],
i -> Comm( R^3*S^n*(S*R^-3)^(n-1),
S^(-i*(n+1))*R^3*S^n*
(S*R^-3)^(n-1)*S^(i*(n+1)) ) );
fp := f / Concatenation( rels, moreRels );
s := fp.1; r := fp.2;
iso := FGA_CurryAutToPQOU( r^3*s^n*(s*r^-3)^(n-1) # 24c
, s^(n+1) # 24a
, s^n*(s*r^-3)^(n-1) # 24b
, s^(-2*(n+1))*r^4*s^(2*(n+1))*r^-3 # 24d
);
fi;
isoinv := GroupHomomorphismByImagesNC( fp, aut,
GeneratorsOfGroup( fp ),
GeneratorsOfGroup( aut ) );
return GroupHomomorphismByFunction( aut, fp, iso,
x -> x ^ isoinv );
end );
#############################################################################
##
#F FreeGroupEndomorphismByImages( <group>, <images> )
##
## returns the endomorphism of <group> that maps the generators of <group>
## to <images>.
##
InstallGlobalFunction( FreeGroupEndomorphismByImages,
function(g,l)
return GroupHomomorphismByImages(g,g,FreeGeneratorsOfGroup(g),l);
end );
#############################################################################
##
#F FreeGroupAutomorphismsGeneratorO( <group> )
#F FreeGroupAutomorphismsGeneratorP( <group> )
#F FreeGroupAutomorphismsGeneratorU( <group> )
#F FreeGroupAutomorphismsGeneratorS( <group> )
#F FreeGroupAutomorphismsGeneratorT( <group> )
#F FreeGroupAutomorphismsGeneratorQ( <group> )
#F FreeGroupAutomorphismsGeneratorR( <group> )
##
## These functions return the automorphism of <group> which maps the
## generators [<x1>, <x2>, ..., <xn>] to
## O : [<x1>^-1 , <x2>, ..., <xn> ] (n>=1)
## P : [<x2> , <x1>, <x3>, ..., <xn> ] (n>=2)
## U : [<x1><x2>, <x2>, <x3>, ..., <xn> ] (n>=2)
## S : [<x2>^-1, <x3>^-1, ..., <xn>^-1, <x1>^-1 ] (n>=1)
## T : [<x2> , <x1>^-1, <x3>, ..., <xn>] (n>=2)
## Q : [<x2>, <x3>, ..., <xn>, <x1> ] (n>=2)
## R : [<x2>^-1, <x1>, <x3>, <x4>, ...,
## <x{n-2}>, <xn><x{n-1}>^-1, <x{n-1}>^-1] (n>=4)
##
InstallGlobalFunction( FreeGroupAutomorphismsGeneratorO,
function( g )
local imgs;
FGA_CheckRank( g, 1 );
imgs := ShallowCopy( FreeGeneratorsOfGroup( g ) );
imgs[1] := imgs[1]^-1;
return FreeGroupEndomorphismByImages( g, imgs );
end );
InstallGlobalFunction( FreeGroupAutomorphismsGeneratorP,
function( g )
local imgs;
FGA_CheckRank( g, 2 );
imgs := ShallowCopy( FreeGeneratorsOfGroup( g ) );
imgs{[1,2]} := [ imgs[2], imgs[1] ];
return FreeGroupEndomorphismByImages( g, imgs );
end );
InstallGlobalFunction( FreeGroupAutomorphismsGeneratorU,
function( g )
local imgs;
imgs := ShallowCopy( FreeGeneratorsOfGroup( g ) );
FGA_CheckRank( g, 2 );
imgs[1] := imgs[1] * imgs[2];
return FreeGroupEndomorphismByImages( g, imgs );
end );
InstallGlobalFunction( FreeGroupAutomorphismsGeneratorS,
function( g )
local imgs;
FGA_CheckRank( g, 1 );
imgs := FreeGeneratorsOfGroup(g){[2..Rank(g)]};
Add( imgs, FreeGeneratorsOfGroup(g)[1] );
return FreeGroupEndomorphismByImages( g, List(imgs, g -> g^-1) );
end );
InstallGlobalFunction( FreeGroupAutomorphismsGeneratorT,
function( g )
local imgs;
FGA_CheckRank( g, 2 );
imgs := ShallowCopy( FreeGeneratorsOfGroup( g ) );
imgs{[1..2]} := [ imgs[2], imgs[1]^-1 ];
return FreeGroupEndomorphismByImages( g, imgs );
end );
InstallGlobalFunction( FreeGroupAutomorphismsGeneratorQ,
function( g )
local imgs;
FGA_CheckRank( g, 2 ); # we could allow 1
imgs := FreeGeneratorsOfGroup(g){[2..Rank(g)]};
Add( imgs, FreeGeneratorsOfGroup(g)[1] );
return FreeGroupEndomorphismByImages( g, imgs );
end );
InstallGlobalFunction( FreeGroupAutomorphismsGeneratorR,
function( g )
local imgs, n;
FGA_CheckRank( g, 4 );
n := RankOfFreeGroup( g );
imgs := ShallowCopy( FreeGeneratorsOfGroup( g ) );
imgs{[1,2,n-1,n]} := [ imgs[2]^-1, imgs[1],
imgs[n]*imgs[n-1]^-1, imgs[n-1]^-1 ];
return FreeGroupEndomorphismByImages( g, imgs );
end );
#############################################################################
##
#F FGA_CheckRank( <group>, <minrank> )
##
## Checks whether <group> has rank at least <minrank>, and signals an
## error otherwise (helper function for FreeGroupAutomorphismsGenerator*)
##
InstallGlobalFunction( FGA_CheckRank,
function( g, r )
if RankOfFreeGroup( g ) < r then
Error( "the rank of the group should be at least ", r );
fi;
return;
end );
#############################################################################
##
#E
