Based on Steve Linton's talk at the Second CoDiMa Training School in Computational Discrete Mathematics (ICMS, Edinburgh, 17-21 October 2016, https://www.codima.ac.uk/school2016/)
Motivating problem: find an element of $S_9$ which is NOT an involution
Filtered(Elements(SymmetricGroup(9)), x-> x*x <> ())[1];
(7,8,9)
Filtered(Elements(SymmetricGroup(10)), x-> x*x <> ())[1];
(8,9,10)
n:=15
and you quickly run out of memory: $15!$ is roughly $1.3 \times 10^{12}$n:=9;; Filtered( Elements(SymmetricGroup(n) ),
x-> x*x <> () )[1];
First(Elements(SymmetricGroup(9)), x-> x*x <> ());
(7,8,9)
Enumerator
returns a list of elements of a domainEnumeratorSorted
— but only if you need it# Do not remove the 2nd semicolon below yet
# See https://github.com/gap-packages/JupyterKernel/issues/72
e := Enumerator(SymmetricGroup(99));;
Length(e);
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000
e[10^100];
(2,60,99,55,54,65,7,16,18,32,70,15,5,37,43,97,19,31,66,30,90,17,29,85,28,67,27,62,26,34,52,59)(3,44,73,47,95,45,51,68,50,86,49,83,40,36,81,35,93,12,76,11,75,10,46,9,96,8,53,42,41,22,78,21,38,20,24,63,23,48,39,56,4,6,58,14,80,13,25,33)
See also EnumeratorOfTuples
and EnumeratorOfCombinations
(both documented) and EnumeratorOfCartesianProduct
(currently undocumented)
IsDoneIterator
and NextIterator
operationsn := 9;; i := Iterator(SymmetricGroup(n));;
while not IsDoneIterator(i) do
x := NextIterator(i);
if x*x <> () then
break;
fi;
od;
x;
(7,9,8)
Or more concisely, thanks to some built-in magic:
n := 9;;
for x in SymmetricGroup(n) do
if x*x <> () then
break;
fi;
od;
x;
(7,9,8)
Or even shorter:
n := 9;; First(SymmetricGroup(n), x->x*x <> ());
(7,9,8)
g := SL(10,3);
SL(10,3)
repeat
x := PseudoRandom(g);
until Order(x) = (3^10-1)/2;
x;
[ [ 0*Z(3), Z(3)^0, Z(3), Z(3), Z(3)^0, Z(3)^0, 0*Z(3), Z(3)^0, Z(3), Z(3)^0 ], [ Z(3), Z(3), Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3), Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), Z(3), 0*Z(3), Z(3), 0*Z(3), Z(3), Z(3) ], [ Z(3), 0*Z(3), Z(3), Z(3)^0, Z(3)^0, Z(3), Z(3)^0, Z(3), Z(3)^0, 0*Z(3) ], [ Z(3)^0, Z(3)^0, Z(3)^0, Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3) ], [ Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3), 0*Z(3), Z(3)^0, Z(3), 0*Z(3), Z(3)^0 ], [ Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3), Z(3)^0, 0*Z(3), 0*Z(3), Z(3), Z(3)^0 ], [ Z(3)^0, Z(3)^0, Z(3), Z(3), Z(3)^0, Z(3), 0*Z(3), Z(3), Z(3), Z(3) ], [ Z(3)^0, Z(3)^0, 0*Z(3), Z(3), Z(3)^0, Z(3), Z(3), Z(3), Z(3), Z(3)^0 ], [ 0*Z(3), Z(3), 0*Z(3), Z(3), Z(3), Z(3)^0, Z(3), Z(3), Z(3)^0, Z(3) ] ]
Display(x);
. 1 2 2 1 1 . 1 2 1 2 2 2 1 . 1 1 2 1 . . 1 . . 2 . 2 . 2 2 2 . 2 1 1 2 1 2 1 . 1 1 1 2 . . . . . 2 2 1 . 1 2 . 1 2 . 1 2 1 1 1 2 1 . . 2 1 1 1 2 2 1 2 . 2 2 2 1 1 . 2 1 2 2 2 2 1 . 2 . 2 2 1 2 2 1 2
n := 9;;
Representative(First(ConjugacyClasses(SymmetricGroup(n)),
c->Representative(c)^2 <> ()));
(1,2,3)
First(SymmetricGroup(11),
x-> OnTuples([1,2,3,4,5],x) = [1,3,5,7,9] and
Order(x) = 7);
(2,3,5,9,4,7,11)
[1,2,3,4,5]
to [1,3,5,7,9]
lie in a coset of a sequence stabilizerg := SymmetricGroup(12);; s := Stabilizer(g,[1,2,3,4,5],OnTuples);;
r := RepresentativeAction(g,[1,2,3,4,5],[1,3,5,7,9],OnTuples);
(2,3,5,9,4,7)
First(s,x->Order(x*r) = 7)*r;
(2,3,5,9,12,4,7)
IsOne(x*x) and not IsOne(x)
ConjugacyClasses
)NormalSubgroups
MaximalSubgroups
will return all subgroups. You are likely to want ony MaximalSubgroupClassReps
Conjecture: $U_3(3)$ cannot be generated by three involutions
g := PSU(3,3);
<permutation group of size 6048 with 2 generators>
IteratorOfTuples
to run through all 216G ...IteratorOfCombinations
to run through 36G of unordered triplesinvs := Filtered(g, x -> IsOne(x*x) and not IsOne(x));;
Length(invs);
63
iter := IteratorOfCombinations(invs,3);; ct := 0;;
while not IsDoneIterator(iter) do
x := NextIterator(iter);
if Subgroup(g,x) = g then
break;
fi;
ct := ct+1;
od;
ct;
39711
Binomial(63,3);
39711
Binomial(63,3)
to Binomial(62,2)
g:=PSU(3,3);;
F:=FreeGroup(3);
<group with 3 generators>
F:=F/[F.1^2,F.2^2,F.3^2];
<group with 3 generators>
GQuotients(F,g);
[ ]
F:=FreeGroup(2);
<group with 2 generators>
F:=F/[F.1^2,F.2^6];
<group with 2 generators>
qs:=GQuotients(F,g);
[ [ f1, f2 ] -> [ (2,4)(5,9)(6,7)(8,10)(11,21)(12,22)(13,20)(14,24)(15,28)(16,27)(17,25)(18,26)(19,23)(38,60)(39,64)(40,59)(41,61)(42,63)(43,58)(44,57)(45,56)(46,62)(47,73)(48,68)(49,69)(50,72)(51,71)(52,65)(53,67)(54,66)(55,70)(74,89)(75,88)(76,90)(77,83)(78,84)(79,87)(80,86)(81,91)(82,85), (1,43,21,15,26,58)(2,91,73)(3,22,89,24,66,25)(4,33)(5,47,13,87,36,12)(6,57,45,78,76,83)(7,17,29,69,16,81)(8,10,77,60,42,50)(9,72,52,51,56,44)(11,48,80,18,67,88)(19,64,46)(20,74,23,54,27,32)(30,59,40,85,86,75)(31,90,62,39,65,34)(35,53,68,70,61,41)(37,82,55)(38,63)(49,84)(71,79) ], [ f1, f2 ] -> [ (2,5)(3,10)(4,6)(7,9)(11,85)(12,83)(13,84)(14,91)(15,86)(16,89)(17,90)(18,88)(19,87)(20,54)(21,53)(22,52)(23,49)(24,47)(25,50)(26,55)(27,51)(28,48)(29,46)(30,41)(31,42)(32,45)(33,44)(34,38)(35,40)(36,39)(37,43)(65,77)(66,78)(67,82)(68,80)(69,79)(70,75)(71,74)(72,76)(73,81), (1,43,21,15,26,58)(2,91,73)(3,22,89,24,66,25)(4,33)(5,47,13,87,36,12)(6,57,45,78,76,83)(7,17,29,69,16,81)(8,10,77,60,42,50)(9,72,52,51,56,44)(11,48,80,18,67,88)(19,64,46)(20,74,23,54,27,32)(30,59,40,85,86,75)(31,90,62,39,65,34)(35,53,68,70,61,41)(37,82,55)(38,63)(49,84)(71,79) ] ]
Length(qs);
2
AllHomomorphisms
, AutomorphismGroup
, IsomorphicSubgroups
f := FreeGroup("a","b");
<group with 2 generators>
AssignGeneratorVariables(f);
#I Assigned the global variables [ a, b ]
g := f/[a^2,b^3,(a*b)^7, Comm(a,b)^8];
<group with 2 generators>
Sum(Elements(g), Order);
66655
x := Random(g);
<object>
Print(x);
(b*a^-1*b^-1*a^-1)^3*b*a^-1*b^-1*(a^-1*b^-1*(a^-1*b^-1*a^-1*b)^3*a^-1*b^-1*a^-\ 1)^2*b^-1*a^-1*(a^-1*b^-1)^2*a^-1
g := f/[a^2,b^3,(a*b)^7, Comm(a,b)^8];
<group with 2 generators>
phi := IsomorphismPermGroup(g);
<object>
Print(phi);
GroupHomomorphismByImages( Group( [ a, b ] ), Group( [ ( 1, 2)( 3, 5)( 4, 6)( 7,11)( 8,12)( 9,13)(10,14)(16,20)(17,21)(18,22) (19,23)(25,29)(26,27)(28,30)(31,34)(32,35)(33,36)(37,41)(38,42)(39,43) (40,44)(45,50)(46,51)(48,52)(49,53)(54,56), ( 2, 3, 4)( 5, 7, 8)( 6, 9,10)(11,15,14)(12,16,17)(13,18,19)(20,24,23) (21,25,26)(22,27,28)(29,31,32)(30,33,34)(35,37,38)(36,39,40)(41,45,46) (42,47,43)(44,48,49)(50,53,54)(51,55,52) ] ), [ a, b ], [ ( 1, 2)( 3, 5)( 4, 6)( 7,11)( 8,12)( 9,13)(10,14)(16,20)(17,21)(18,22) (19,23)(25,29)(26,27)(28,30)(31,34)(32,35)(33,36)(37,41)(38,42)(39,43) (40,44)(45,50)(46,51)(48,52)(49,53)(54,56), ( 2, 3, 4)( 5, 7, 8)( 6, 9,10)(11,15,14)(12,16,17)(13,18,19)(20,24,23) (21,25,26)(22,27,28)(29,31,32)(30,33,34)(35,37,38)(36,39,40)(41,45,46) (42,47,43)(44,48,49)(50,53,54)(51,55,52) ] )
h := ImagesSource(phi);
<permutation group of size 10752 with 2 generators>
Sum(Elements(h), Order);
66655
x := Random(h);
(1,9,31)(2,5,39)(3,27,20)(4,35,55)(6,21,25)(7,37,30)(8,24,51)(11,41,47)(12,28,46)(13,43,38)(14,18,22)(15,53,17)(16,40,23)(19,54,45)(26,56,44)(29,49,32)(33,52,36)(34,42,50)
y := PreImagesRepresentative(phi,x);
<object>
Print(y);
b^-1*a^-1*b*((a^-1*b^-1*a^-1*b)^3*a^-1*b^-1)^2*a^-1*(b^-1*(a*b)^2*a)^2*(b^-1*a\ )^2*b
Other Isomorphism Constructors
Isomorphism[Special]PcGroup
IsomorphismFpGroup
SmallerDegreePermRep
?NiceMonomorphism
or ?NiceObject
Source
and Range
(domain and codomain)ImagesSource
and PreImagesRange
may be what you wantImage
specialised to ImageElm
and ImagesSet
PreImagesRepresentative
gives just ONE preimageInverseGeneralMapping
CompositionMapping
g:=Group((1,2,3,4),(1,2),(5,6,7));
Group([ (1,2,3,4), (1,2), (5,6,7) ])
iso:=IsomorphismPcGroup(g);
<object>
h:=Image(iso);
<group of size 72 with 5 generators>
z:=Centre(h);
<group with 1 generators>
SetCentre(g,PreImage(iso,z));
cl:=ConjugacyClasses(h);
[ <object>, <object>, <object>, <object>, <object>, <object>, <object>, <object>, <object>, <object>, <object>, <object>, <object>, <object>, <object> ]
ncl:=[];
[ ]
for c in cl do
nc:=ConjugacyClass(g,PreImage(iso,Representative(c)));
SetSize(nc,Size(c));
SetStabilizerOfExternalSet(nc, PreImage(iso,StabilizerOfExternalSet(c)));
Add(ncl,nc);
od;
List(ncl,Size);
[ 1, 1, 6, 8, 3, 1, 6, 8, 3, 6, 6, 8, 3, 6, 6 ]
SetConjugacyClasses(g,ncl);
g := Group((1,2),(3,4),(5,6),(7,8),(9,10,11),(11,12,13));
Group([ (1,2), (3,4), (5,6), (7,8), (9,10,11), (11,12,13) ])
Number(g, x-> Order(x) mod 2 = 1); Size(g);
45
960
Orbits(g,MovedPoints(g));
[ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ], [ 7, 8 ], [ 9, 10, 11, 12, 13 ] ]
phi := ActionHomomorphism(g,[1..8]);
<object>
Print(phi);
<action homomorphism>
h := ImagesSource(phi);
Group([ (1,2), (3,4), (5,6), (7,8) ])
odds := Filtered(h, x->Order(x) mod 2 = 1);
[ () ]
p := PreImagesSet(phi,odds);
[ (), (11,12,13), (11,13,12), (10,11)(12,13), (10,11,12), (10,11,13), (10,12,11), (10,12,13), (10,12)(11,13), (10,13,11), (10,13,12), (10,13)(11,12), (9,10)(12,13), (9,10)(11,12), (9,10)(11,13), (9,10,11), (9,10,11,12,13), (9,10,11,13,12), (9,10,12,13,11), (9,10,12), (9,10,12,11,13), (9,10,13,12,11), (9,10,13), (9,10,13,11,12), (9,11,10), (9,11,12,13,10), (9,11,13,12,10), (9,11)(12,13), (9,11,12), (9,11,13), (9,11)(10,12), (9,11,10,12,13), (9,11,13,10,12), (9,11)(10,13), (9,11,10,13,12), (9,11,12,10,13), (9,12,13,11,10), (9,12,10), (9,12,11,13,10), (9,12,11), (9,12,13), (9,12)(11,13), (9,12,13,10,11), (9,12)(10,11), (9,12,10,11,13), (9,12,10,13,11), (9,12,11,10,13), (9,12)(10,13), (9,13,12,11,10), (9,13,10), (9,13,11,12,10), (9,13,11), (9,13,12), (9,13)(11,12), (9,13,12,10,11), (9,13)(10,11), (9,13,10,11,12), (9,13,10,12,11), (9,13,11,10,12), (9,13)(10,12) ]
Length(p); Number(p, x->Order(x) mod 2 = 1);
60
45
GroupHomorphismByImages
(by giving images of generators)GroupHomorphismByImagesNC
if you are sure you are right)ActionHomorphism
is usually goodIsomorphismXXXGroup
Avoid long lists of mutable objects
cvec
ConvertToVectorRep(v, q)
and ConvertToMatrixRep(m,q)
convert in placecvec
has its own functionsBosma & van der Poorten: Computational Algebra and Number Theory, 1995, Springer)