| Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/lib/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 18.9.2025 mit Größe 103 kB |
|
SSL grpprmcs.gi Sprache: unbekannt |
|
|
#############################################################################
## ## This file is part of GAP, a system for computational discrete algebra. ## This file's authors include Ákos Seress. ## ## Copyright of GAP belongs to its developers, whose names are too numerous ## to list here. Please refer to the COPYRIGHT file for details. ## ## SPDX-License-Identifier: GPL-2.0-or-later ## ############################################################################# ## #F GInverses( <S> ) . . . . . . . . . . . . . . . . . . . . . . . . . local ## ## <S> must be a stabilizer chain. ## ## `GInverses' changes `<S>.generators' ! ## BindGlobal( "GInverses", function( S ) local inverses, set, i; set := Set( S.translabels ); RemoveSet( set, 1 ); S.generators := S.labels{ set }; inverses := [ ]; for i in [ 1 .. Length( S.generators ) ] do inverses[ i ] := S.generators[ i ] ^ -1; od; if IsBound( S.stabilizer ) then Append( S.generators, S.stabilizer.generators ); fi; return inverses; end ); ############################################################################# ## #F DisplayCompositionSeries( <S> ) . . . . . . . . . . . . display function ## InstallGlobalFunction( DisplayCompositionSeries, function( S ) local f, i,s; # ok, we accept groups too if IsGroup( S ) then S := CompositionSeries( S ); fi; # if we know the composition series, we know orders of groups, so we may # enforce their computation before calling GroupString to display them. Perform( S, Size ); Print( GroupString( S[1], "G" ), "\n" ); for i in [2..Length(S)] do f:=Image(NaturalHomomorphismByNormalSubgroup(S[i-1],S[i])); s:=IsomorphismTypeInfoFiniteSimpleGroup(f); if IsBound(s.shortname) then s:=s.shortname; else s:=s.name; fi; Print( " | ",s,"\n"); if i < Length(S) then Print( GroupString( S[i], "S" ), "\n" ); else Print( GroupString( S[i], "1" ), "\n" ); fi; od; end ); ############################################################################# ## #M CompositionSeries( <G> ) . . . . composition series of permutation group ## ## `CompositionSeriesPermGroup' returns the composition series of <G> as a ## list. ## ## The subgroups in this list have a slightly modified ## `NaturalHomomorphismByNormalSubgroup' method, ## which notices if you compute the factor group of one subgroup by the next ## and return the factor group as a primitive permutation group in this ## case (which is also computed by the function below). The factor groups ## remember the natural homomorphism since the images of the generators of ## the subgroup are known and the natural homomorphism can thus be written ## as `GroupHomomorphismByImages'. ## ## The program works for permutation groups of degree < 2^20 = 1048576. ## For higher degrees `IsSimple' and `CasesCSPG' must be extended with ## longer lists of primitive groups from extensions in Kantor's tables ## (see JSC. 12(1991), pp. 517-526). It may also be necessary to modify ## `FindNormalCSPG'. ## ## A general reference for the algorithm is: ## Beals-Seress, 24th Symp. on Theory of Computing 1992. ## InstallMethod( CompositionSeries, "for a permutation group", true, [ IsPermGroup ], 0, function( Gr ) local pcgs, normals, # first component of output; normals[i] contains # generators for i^th subgroup in comp. series factors, # second component of output; factors[i] contains # the action of generators in normals[i] factorsize, # third component of output; factorsize[i] is the # size of the i^th factor group homlist, # list of homomorphisms applied to input group auxiliary, # if auxiliary[j] is bounded, it contains # a subg. which must be added to kernel of homlist[j] index, # variable recording how many elements of normals are # computed workgroup, # the subnormal factor group we currently work with workgrouporbit, lastpt, # degree of workgroup tchom, # transitive constituent homomorphism applied to # intransitive workgroup bhom, # block homomorphism applied to imprimitive workgroup fahom, # factor homomorphism to store bl, # block system in workgroup D, # derived subgroup of workgroup top, # index of D in workgroup lenhomlist, # length of homlist i, s, t, # fac, # factor group as permutation group list; # output of CompositionSeries # Solvable groups first. pcgs := Pcgs( Gr ); if pcgs <> fail then list := ShallowCopy( PcSeries( pcgs ) ); s := list[ 1 ]; for i in [ 2 .. Length( list ) ] do t := AsSubgroup( s, list[ i ] ); fac := CyclicGroup( IsPermGroup, RelativeOrders( pcgs )[ i - 1 ] ); fahom:=GroupHomomorphismByImagesNC( s, fac, pcgs{ [ i - 1 .. Length( pcgs ) ] }, Concatenation( GeneratorsOfGroup( fac ), List( [ i .. Length( pcgs ) ], k -> One( fac ) ) ) ); Setter( NaturalHomomorphismByNormalSubgroupInParent )( t,fahom); AddNaturalHomomorphismsPool(s,t,fahom); list[ i ] := t; s := t; od; return list; fi; # initialize output and work arrays normals := []; factors := []; factorsize := []; auxiliary := []; homlist := []; index := 1; workgroup := Gr; # workgroup is always a factor group of the input Gr such that a # composition series for Gr/workgroup is already computed. # Try to get a factor group of workgroup while (Size(workgroup) > 1) or (Length(homlist) > 0) do #Print(List(normals,Length)," ",Size(workgroup),"\n"); if Size(workgroup) > 1 then lastpt := LargestMovedPoint(workgroup); # if workgroup is not transitive workgrouporbit:= StabChainMutable( workgroup ).orbit; if Length(workgrouporbit) < lastpt then tchom := ActionHomomorphism(workgroup,workgrouporbit,"surjective"); Add(homlist,tchom); workgroup := Image(tchom,workgroup); else bl := MaximalBlocks(workgroup,[1..lastpt]); # if workgroup is not primitive if Length(bl) > 1 then bhom:=ActionHomomorphism(workgroup,bl,OnSets,"surjective"); workgroup := Image(bhom,workgroup); Add(homlist,bhom); else D := DerivedSubgroup(workgroup); top := Size(workgroup)/Size(D); # if workgroup is not perfect if top > 1 then # fill up workgroup/D by cyclic factors index := NonPerfectCSPG(homlist,normals,factors, auxiliary,factorsize,top,index,D,workgroup); workgroup := D; # otherwise chop off simple factor group from top of # workgroup else workgroup := PerfectCSPG(homlist,normals,factors, auxiliary,factorsize,index,workgroup); index := index+1; fi; # nonperfect-perfect fi; # primitive-imprimitive fi; # transitive-intransitive # if the workgroup was trivial else lenhomlist := Length(homlist); # pull back natural homs PullBackNaturalHomomorphismsPool(homlist[lenhomlist]); workgroup := KernelOfMultiplicativeGeneralMapping( homlist[lenhomlist] ); # if auxiliary[lenhmlist] is bounded, it is faster to augment it # by generators of the kernel of `homlist[lenhomlist]' if IsBound(auxiliary[lenhomlist]) then workgroup := auxiliary[lenhomlist]; workgroup := ClosureGroup( workgroup, GeneratorsOfGroup( KernelOfMultiplicativeGeneralMapping( homlist[lenhomlist] ) ) ); fi; Unbind(auxiliary[lenhomlist]); Unbind(homlist[lenhomlist]); fi; # workgroup is nontrivial-trivial od; # loop over the subgroups #s := SubgroupNC( Gr, normals[1] ); #SetSize( s, Size( Gr ) ); s:=Gr; list := [ s ]; for i in [2..Length(normals)] do t := SubgroupNC( s, normals[i] ); SetSize( t, Size( s ) / factorsize[i-1] ); fac := GroupByGenerators( factors[i-1] ); SetSize( fac, factorsize[i-1] ); SetIsSimpleGroup( fac, true ); fahom:=GroupHomomorphismByImagesNC( s, fac, normals[i-1], factors[i-1] ); #if IsIdenticalObj(Parent(t),s) then # Setter( NaturalHomomorphismByNormalSubgroupInParent )( t,fahom); #fi; AddNaturalHomomorphismsPool(s, t,fahom); Add( list, t ); s := t; od; t := TrivialSubgroup( s ); Assert(1,Size( s )=factorsize[Length(normals)]); fac := GroupByGenerators( factors[Length(normals)] ); SetSize( fac, factorsize[Length(normals)] ); SetIsSimpleGroup( fac, true ); fahom:=GroupHomomorphismByImagesNC( s, fac, Last(normals), factors[Length(normals)] ); if IsIdenticalObj(Parent(t),s) then Setter( NaturalHomomorphismByNormalSubgroupInParent )( t,fahom); fi; AddNaturalHomomorphismsPool(s, t,fahom); Add( list, t ); # return output return list; end ); ############################################################################# ## #F NonPerfectCSPG() . . . . . . . . non perfect case of composition series ## ## When <workgroup> is not perfect, it fills up the factor group of the ## commutator subgroup with cyclic factors. ## Output is the first index in normals which remains undefined ## InstallGlobalFunction( NonPerfectCSPG, function( homlist, normals, factors, auxiliary, factorsize, top, index, D, workgroup ) local listlength, # number of cyclic factors to add to factors indexup, # loop variable for adding the cyclic factors oldworkup, # loop subgroups between workup, # workgroup and derived subgrp order, # index of oldworkup in workup orderlist, # prime factors of order g, p, # generators of workup, oldworkup h, # a power of g i; # loop variables # number of primes in factor <workgroup> / <derived subgroup> listlength := Length(Factors(Integers,top)); indexup := index+listlength; oldworkup := D; # starting with the derived subgroup, add generators g of workgroup # each addition produces a cyclic factor group on top of previous; # appropriate powers of g will divide the cyclic factor group into # factors of prime length for g in StabChainMutable( workgroup ).generators do if not (g in oldworkup) then # check for error in random computation of derived subgroup Assert(1, ForAll ( StabChainMutable( oldworkup ).generators, x->(x^g in oldworkup) )); workup := ClosureGroup(oldworkup, g); order := Size(workup)/Size(oldworkup); orderlist := Factors(Integers,order); for i in [1..Length(orderlist)] do # h is the power of g which adds prime length factors h := g^Product([i+1..Length(orderlist)],x->orderlist[x]); # construct entries in factors, normals factors[indexup -1] := []; normals[indexup -1] := []; for p in StabChainMutable( oldworkup ).generators do # p acts trivially in factor group Add(factors[indexup -1],()); # preimage of p is a generator in normals Add(normals[indexup -1],PullbackCSPG(p,homlist)); od; # workgroup is a factor group of original input; # kernel of homomorphism must be added to gens in normals PullbackKernelCSPG(homlist,normals,factors, auxiliary,indexup-1); # add preimage of h to generator list Add(normals[indexup-1],PullbackCSPG(h,homlist)); # add a prime length cycle to factor group action Add(factors[indexup-1], PermList(Concatenation([2..orderlist[i]],[1]))); # size of factor group is a prime factorsize[indexup-1] := orderlist[i]; indexup := indexup -1; od; oldworkup := workup; fi; od; return index+listlength; end ); ############################################################################# ## #F PerfectCSPG() . . . . . . . . . . . . prefect case of composition series ## ## Computes maximal normal subgroup of perfect primitive group K and adds ## its factor group to factors. ## Output is the maximal normal subgroup NN. In case NN=1 (i.e. K simple), ## the kernel of homomorphism which produced K is returned ## InstallGlobalFunction( PerfectCSPG, function( homlist, normals, factors, auxiliary, factorsize, index, K ) local whichcase, # var indicating to which case of the O'Nan-Scott # theorem K belongs. When Size(K) and degree do not # determine the case without ambiguity, whichcase # has value as in case of unique nonregular # minimal normal subgroup N, # normal subgroup of K prime, # prime dividing order of degree of K stab2, # stabilizer of first two base points in K kerelement, # element of normal subgroup ker2, # conjugate of kerelement H, # normalizer, and then centralizer of stab2 L, # set of moved points of stab2 op, # operation of H on N tchom, # restriction of H to L g, # generator of subgroups lenhomlist, # length of homlist kernel, # output ready, # boolean variable indicating whether normal subgroup # was found chainK, list; while not IsSimpleGroup(K) do whichcase := CasesCSPG(K); # becomes true if we find proper normal subgroup by first method ready := false; # whichcase[1] is true in nonregular minimal normal subgroup case if whichcase[1]=1 then N := FindNormalCSPG(K, whichcase); # check size of result to terminate fast in ambiguous cases if 1 < Size(N) and Size(N) < Size(K) then # K is a factor group with N in the kernel K := NinKernelCSPG(K,N,homlist,auxiliary); SetDerivedSubgroup( K, K ); #T better set that K is perfect? ready := true; fi; fi; # apply regular normal subgroup with nontrivial centralizer method if not ready then chainK:= StabChainMutable( K ); stab2 := Stabilizer(K,[ chainK.orbit[1], chainK.stabilizer.orbit[1]], OnTuples); if IsTrivial(stab2) then prime := Factors(Integers,whichcase[2])[1]; N:=Group(One(K)); repeat kerelement:=Random(K); if NrMovedPoints(kerelement)=LargestMovedPoint(K) and IsOne(kerelement^prime) then ker2:=kerelement^Random(K); if Comm(kerelement,ker2)=One(K) then N := NormalClosure(K, SubgroupNC(K,[kerelement])); fi; fi; until Size(N)=whichcase[2]; else list := NormalizerStabCSPG(K); H := list[1]; chainK := list[2]; if whichcase[1] = 2 then stab2 := Stabilizer( K, [ chainK.orbit[1], chainK.stabilizer.orbit[1] ], OnTuples); H := CentralizerNormalCSPG( H, stab2 ); else L := Orbit( H, StabChainMutable( H ).orbit[1] ); tchom := ActionHomomorphism(H,L,"surjective"); op := Image( tchom ); H := PreImage(tchom,PCore(op,Factors(Integers,whichcase[2])[1])); H := Centre(H); SetIsAbelian( H, true ); fi; N := FindRegularNormalCSPG(K,H,whichcase); fi; K := NinKernelCSPG(K,N,homlist,auxiliary); SetDerivedSubgroup( K, K ); #T better set that K is perfect? fi; od; # add next entry to the CompositionSeries output lists factors[index] := []; normals[index] := []; factorsize[index] := Size(K); for g in StabChainMutable( K ).generators do Add(factors[index],g); # store generators for image Add(normals[index],PullbackCSPG(g,homlist)); od; # add generators for kernel to normals PullbackKernelCSPG(homlist,normals,factors,auxiliary,index); lenhomlist := Length(homlist); # determine output of routine if lenhomlist > 0 then kernel := KernelOfMultiplicativeGeneralMapping(homlist[lenhomlist]); if IsBound(auxiliary[lenhomlist]) then kernel := auxiliary[lenhomlist]; # faster to add this way kernel := ClosureGroup( kernel, KernelOfMultiplicativeGeneralMapping(homlist[lenhomlist]) ); fi; Unbind(homlist[lenhomlist]); Unbind(auxiliary[lenhomlist]); # case when we found last factor of original group else kernel := GroupByGenerators( [], () ); fi; return kernel; end ); ############################################################################# ## #F CasesCSPG() . . . . . . . . . . . . determine case of O'Nan Scott theorem ## ## Input: primitive, perfect, nonsimple group G. ## CasesCSPG determines whether there is a normal subgroup with ## nontrivial centralizer (output[1] := 2 or 3) or decomposes the ## degree of G into the form output[2]^output[3], output[1] := 1 (case ## of nonregular minimal normal subgroup). ## There are some ambiguous cases, (e.g. degree=2^15) when Size(G) ## and degree do not determine which case G belongs to. In these cases, ## the output is as in case of nonregular minimal normal subgroup. ## This computation duplicates some of what is done in IsSimple. ## InstallGlobalFunction( CasesCSPG, function(G) local degree, # degree of G g, # order of G primes, # list of primes in prime decomposition of degree output, # output of routine n,m,o,p, # loop variables tab1, # table of orders of primitive groups tab2, # table of orders of perfect transitive groups base; # prime occurring in order of outer automorphism # group of some group in tab1 g := Size(G); degree := LargestMovedPoint(G); if degree>2^20 then # see comment before the composition series method Error("degree too big"); fi; output := []; # case of two regular normal subgroups if Size(G)=degree^2 then output[1] := 2; output[2] := degree; return output; fi; # degree is not prime power primes := Factors(Integers,degree); if primes[1] < Last(primes) then output[1] := 1; # only case when index of primitive group in socle is not 2*prime if Length(primes)=15 then output[2] := 12; output[3] := 5; else output[2] := primes[1]*Last(primes); output[3] := Length(primes)/2; fi; return output; # in case of prime power degree, we have to determine the possible # orders of G with nonabelian socle. See IsSimple for identification # of groups in tab1,tab2 else tab1 := [ ,,,,[60],,[168,2520],[168,20160],[504,181440],, [660,7920,19958400],,[5616,3113510400]]; tab2 := [ ,,,,[60],[60,360],[168,2520],[168,1344,20160]]; for n in [5,7,8,9,11,13] do for m in [5..8] do for o in [1..Length(tab1[n])] do for p in [1..Length(tab2[m])] do if tab1[n][o]=504 then base := 3; else base := 2; fi; if degree=n^m and g mod (tab1[n][o]^m*tab2[m][p]) = 0 and (tab1[n][o]^m*tab2[m][p]*base^m) mod g = 0 then output[1] := 1; output[2] := n; output[3] := m; return output; fi; od; od; od; od; # if the order of G did not satisfy any of the nonabelian socle # possibilities, output the abelian socle message output[1] := 3; output[2] := degree; return output; fi; end ); ############################################################################# ## #F FindNormalCSPG() . . . . . . . . . . . . . find a proper normal subgroup ## ## given perfect, primitive G with unique nonregular minimal normal ## subgroup, the routine returns a proper normal subgroup of G ## InstallGlobalFunction( FindNormalCSPG, function ( G, whichcase ) local n, # degree of G i, # loop variable stabgroup, # stabilizer subgroup of first point orbits, # list of orbits of stabgroup where, # index of shortest orbit in orbits len, # length of shortest orbit tchom, # trans. constituent homom. of stabgroup # to shortest orbit bl, # blocks in action of stabgroup on shortest orbit bhom, # block homomorphism for the action on bl K, # homomorph image of stabgroup at tchom, bhom kernel, # kernel of bhom N; # output; normal subgroup of G # whichcase[1]=1 if G has no normal subgroup with nontrivial # centralizer or we cannot determine this fact from Size(G) n := LargestMovedPoint(G); stabgroup := Stabilizer(G, StabChainMutable( G ).orbit[1],OnPoints); orbits := OrbitsDomain(stabgroup,[1..n]); # find shortest orbit of stabgroup len := n; where := 1; for i in [1..Length(orbits)] do if (1<Length(orbits[i])) and (Length(orbits[i])< len) then where := i; len := Length(orbits[i]); fi; od; # check arith. conditions in order to terminate fast in ambiguous cases if len mod whichcase[3] = 0 and len <= whichcase[3]*(whichcase[2]-1) then # take action of stabgroup on shortest orbit tchom := ActionHomomorphism(stabgroup,orbits[where],"surjective"); K := Image(tchom,stabgroup); bl := MaximalBlocks(K,[1..len]); # take action on blocks if Length(bl) > 1 then bhom := ActionHomomorphism(K,bl,OnSets,"surjective"); K := Image(bhom,K); kernel := KernelOfMultiplicativeGeneralMapping( CompositionMapping(bhom,tchom)); N := NormalClosure(G,kernel); # another check for ambiguous cases if Size(N) < Size(G) then return N; fi; fi; fi; # in ambiguous case, return trivial subgroup N := TrivialSubgroup( Parent(G) ); return N; end ); ############################################################################# ## #F FindRegularNormalCSPG() . . . . . . . . . . find a proper normal subgroup ## ## given perfect, primitive G with regular minimal normal ## subgroup(s), the routine returns one ## InstallGlobalFunction( FindRegularNormalCSPG, function ( G, H, whichcase ) local core, # p-core of H cosetrep, # a cosetrep of H.stabilizer candidates, # list of perms; one element is in regular normal sbgrp ready, # boolean to exit loop i, # loop variable N, # regular normal subgroup, output chain; # case of abelian normal subgroup if whichcase[1] <> 2 then core := PCore( H, Factors(Integers, whichcase[2])[1] ); chain:=StabChainOp(core,rec(base:=BaseOfGroup(G),reduced:=false)); cosetrep := chain.transversal[chain.orbit[2]]; candidates := AsList(Stabilizer(core,BaseOfGroup(G)[1]))*cosetrep; ready := false; i:= 0; while not ready do i := i+1; N := NormalClosure(G, SubgroupNC(G, [candidates[i]]) ); if Size(N) = whichcase[2] then ready := true; fi; od; # case of two simple regular normal subgroups else chain := StabChainOp(H, rec(base := BaseOfGroup(G), reduced := false) ); cosetrep := chain.transversal[chain.orbit[2]]; candidates := cosetrep*AsList(Stabilizer(H,BaseOfGroup(G)[1])); ready := false; i:= 0; while not ready do i := i+1; N := NormalClosure(G, SubgroupNC(G, [candidates[i]]) ); if Size(N) = whichcase[2] then ready := true; fi; od; fi; return N; end ); ############################################################################# ## #F NinKernelCSPG() . . . . . find homomorphism that contains N in the kernel ## ## Given a normal subgroup N of G, creates a subgroup H such that the ## homomorphism to the action on cosets of H contains N in the kernel. ## Actually, only the image of a subgroup is computed, and we store ## N in auxiliary to remember that N should be added to kernel of ## homomorphism. ## Output is the image at homomorphism ## InstallGlobalFunction( NinKernelCSPG, function ( G, N, homlist, auxiliary ) local i,j, # loop variables base, # base of G stab, # stabilizer of first two base points H,HOld, # subgroups of G G1,H1, # stabilizer chains of G, HOld block, # set of cosets of G1[i]; G1[i] is represented on # images of block newrep, # blocks of imprimitivity in bhom, # block hom. and tchom; # transisitive const. hom. applied to G1[i] j := Length(homlist)+1; auxiliary[j] := N; # find smallest subgroup of G in stabilizer chain which, together with N, # generates G G1:=StabChainMutable(G); base := BaseStabChain(G1); G1 := ListStabChain( G1 ); i := Length(base)+1; # first try the stabilizer of first two points if Size(N) = LargestMovedPoint(G) then stab := AsSubgroup(Parent(G),Stabilizer(G,[base[1],base[2]],OnTuples)); H := ClosureGroup ( stab, GeneratorsOfGroup( N ), rec(size:=Size(N)*Size(stab)) ); else H := ClosureGroup( N, G1[3].generators ); fi; if Size(H) < Size(G) then HOld := H; i := 2; else # if did not work, start from bottom of stabilizer chain H := N; repeat HOld := H; i := i-1; H := ClosureGroup( H, G1[i].generators ); until Size(H) = Size(G); fi; # represent G1[i] on cosets of H1[i] := G1[i+1]N \cap G1[i] H1 := ListStabChain( StabChainOp( HOld, rec( base := base, reduced := false ) ) ); # G1[i] will be represented on images of block block := Set( H1[i].orbit ); G := Stabilizer(G,List([1 .. i-1], x->base[x]),OnTuples); # now G is the previous G1[i] # find primitive action on images of block newrep := MaximalBlocks( G, StabChainMutable( G ).orbit, block ); if Length(newrep) > 1 then bhom := ActionHomomorphism(G,newrep,OnSets,"surjective"); Add(homlist,bhom); G := Image(bhom,G); else tchom:=ActionHomomorphism(G, StabChainMutable( G ).orbit,"surjective"); Add(homlist,tchom); G := Image(tchom,G); fi; return G; end ); ############################################################################# ## #F RegularNinKernelCSPG() . . . . action of G on H and on maximal subgroup ## ## H is transitive and contains the stabilizer of the first two ## base points; we want to find the action of G on cosets of H, and ## then the action of G on cosets of a maximal subgroup K containing H ## reference: Beals-Seress Lemma 4.3. ## InstallGlobalFunction( RegularNinKernelCSPG, function ( G, H, homlist ) local i,j,k, # loop variables base, # base of G chainG, # stabilizer chain of `G' chainH, # stabilizer chain of `H' H1, # stabilizer chain of G,H x,y, # first two base points of G stabgroup, # stabilizer of x in G chainstabgroup, Ginverses, # list of inverses of generators of G hgens, # list of generators of H Hinverses, # list of inverses of generators of H stabgens, # list of generators of stabgroup stabinverses, # list of inverses of generators of stabgroup block, # orbit of y in H_x orbits, # images of block in G_x=stabgroup a, # cardinality of orbits b, # cardinality of block reprlist, # for z in stabgroup.orbit, reprlist[z] tells which # element of orbits z belongs to reps, # for representatives z of sets in orbits, reps # contains the cosetrep carrying z to y in stabgroup # (as a word in generators of stabgroup) inversereps,# the inverses of words in reps # (as words in stabinverses) images, # list containing the images of generators of G, # acting on cosets of H (there are $a$ cosets, # represented by the elements of orbits) v, # point of permutation domain tau, # the cosetrep of H carrying v to x # (as a word in H.gen's) tauinverse, # the inverse of tau (as a word in Hinverses) word, # list of permutations coding a cosetrep of H K, # the factor group of G generated by images newrep, # block system from cosets of K c, # cardinality of newrep d, # size of one block newimages, # list containing the action of generators of G, on # newrep hom; # the homomorphism G->K chainG:= StabChainMutable( G ); base := BaseStabChain(chainG); H1 := ListStabChain( StabChainOp( H, rec( base := base, reduced := false ) ) ); block := Set( H1[2].orbit ); x := chainG.orbit[1]; stabgroup := Stabilizer( G, x, OnPoints ); orbits := Orbit(stabgroup,block,OnSets); chainstabgroup:= StabChainMutable( stabgroup ); y := chainstabgroup.orbit[1]; a := Length(orbits); b := Length(block); reprlist := []; for i in [1..a] do for k in [1..b] do reprlist[orbits[i][k]] := i; od; od; Ginverses := GInverses( chainG ); chainH:= StabChainMutable( H ); Hinverses := GInverses( chainH ); hgens := chainH.generators; stabinverses := GInverses( chainstabgroup ); stabgens := chainstabgroup.generators; reps := []; inversereps := []; for i in [1..a] do reps[i] := CosetRepAsWord( y, orbits[i][1], chainstabgroup.transversal ); inversereps[i] := InverseAsWord(reps[i],stabgens,stabinverses); od; # construct action of G-generators on cosets of H. Each coset of H has a # representative in orbits; to find the image of an H coset # at multiplication by G.generators[i], take element of H coset such that # the product with G.generators[i] fixes x. Then the image of the coset # can be read from the position in orbits (cf. Lemma 4.3) images := []; for i in [1..Length( chainG.generators )] do images[i] := []; for j in [1..a] do v := ImageInWord(x^Ginverses[i],reps[j]); tau := CosetRepAsWord( x, v, chainH.transversal ); tauinverse := InverseAsWord(tau,hgens,Hinverses); word := Concatenation(tauinverse,inversereps[j], [ chainG.generators[i] ]); images[i][j] := reprlist[ImageInWord(y,word)]; od; images[i] := PermList(images[i]); od; K := GroupByGenerators(images,()); # check whether new representation is primitive. If not, construct action # on maximal block system newrep := MaximalBlocks(K,[1..a]); if Length(newrep) > 1 then c := Length(newrep); d := Length(newrep[1]); reprlist := []; for i in [1..c] do for k in [1..d] do reprlist[newrep[i][k]] := i; od; od; newimages := []; for i in [1..Length( chainG.generators )] do newimages[i] := []; for k in [1..c] do newimages[i][k] := reprlist[newrep[k][1]^images[i]]; od; newimages[i] := PermList(newimages[i]); od; K := GroupByGenerators(newimages,()); hom := GroupHomomorphismByImagesNC( G, K, chainG.generators, newimages ); else hom := GroupHomomorphismByImagesNC( G, K, chainG.generators, images ); fi; j := Length(homlist)+1; homlist[j] := hom; K := Image(homlist[j],G); SetDerivedSubgroup( K, K ); #T better set that K is perfect? return K; end ); ############################################################################# ## #F NormalizerStabCSPG( <G> ) . . . . . . . normalizer of 2 point stabilizer ## ## Given a primitive, perfect group <G> which has a regular normal subgroup ## with nontrivial centralizer, ## the output is a list of length two, the first entry being N_G(G_{xy}) ## and the second entry being a stabilizer chain of <G>. ## InstallGlobalFunction( NormalizerStabCSPG, function(G) local n, # degree of G chainG, # stabilizer chain of `G' chainstab, # stabilizer chain of a point stabilizer in `G' orbits, # orbits of stabgroup len, # minimal length of stabgroup orbits where, # index of minimal length orbit i, # loop variable chainstab2, # chain of stabilizer of first two base points in G x,y, # first two base points normalizer, # output group N_G(G_{xy}) L, # fixed points of stabgroup2 yL, # intersection of L and y-orbit in stabgroup orbity, # orbit of y in normalizer_x; # eventually, orbity must be yL orbitx, # orbit of x in normalizer; # eventually, orbitx must be L u,v, # points in permutation domain tau,sigma,p,# cosetreps of G, stabgroup Ltau; # image of L under tau n := LargestMovedPoint(G); chainG:= StabChainMutable( G ); chainstab := chainG.stabilizer; # If necessary, make base change to achieve that second base point is # in smallest orbit of stabilizer. orbits := OrbitsPerms( chainstab.generators, [1..n] ); len := n; where := 1; for i in [1..Length(orbits)] do if (1<Length(orbits[i])) and (Length(orbits[i])< len) then where := i; len := Length(orbits[i]); fi; od; if Length( chainstab.orbit ) > len then chainG:= StabChainOp( G, [ chainG.orbit[1], orbits[where][1] ] ); chainstab:= chainG.stabilizer; fi; x := chainG.orbit[1]; y := chainstab.orbit[1]; chainstab2 := chainstab.stabilizer; # compute normalizer. Method: Beals-Seress, Lemma 7.1 L := Difference( [1..n], MovedPoints( chainstab2.generators ) ); yL := Intersection( L, chainstab.orbit ); # initialize normalizer to G_{xy} normalizer := rec( generators := ShallowCopy( chainstab2.generators) ); orbity := OrbitPerms(normalizer.generators,y); while Length(orbity) < Length(yL) do v := Difference(yL,orbity)[1]; p := Product( CosetRepAsWord( y, v, chainstab.transversal ) ); Add(normalizer.generators,p); orbity := OrbitPerms(normalizer.generators,y); od; normalizer.stabChain2 := EmptyStabChain( [ ], (), y ); AddGeneratorsExtendSchreierTree(normalizer.stabChain2,normalizer.generators); normalizer.stabChain2.stabilizer:= chainstab2; orbitx := OrbitPerms(normalizer.generators,x); while Length(orbitx) < Length(L) do v := Difference(L,orbitx)[1]; tau := Product( CosetRepAsWord( x, v, chainG.transversal ) ); Ltau := OnSets(L,tau); u := Intersection( Ltau, chainstab.orbit )[1]; sigma := Product( CosetRepAsWord( y, u, chainstab.transversal ) ); Add(normalizer.generators,tau*sigma); orbitx := OrbitPerms(normalizer.generators,x); od; normalizer.stabChain := EmptyStabChain( [ ], (), x ); AddGeneratorsExtendSchreierTree(normalizer.stabChain,normalizer.generators); normalizer.stabChain.stabilizer:=normalizer.stabChain2; normalizer := GroupStabChain( Parent( G ), normalizer.stabChain, true ); return [normalizer, chainG]; end ); ############################################################################# ## #F TransStabCSPG() . . . embed a 2 point stabilizer in a transitive subgroup ## ## given a subgroup H of G which contains G_{xy}, the stabilizer of the ## first two points in G, and a theoretical guarantee that there is a ## proper transitive subgroup K containing H, the routine finds such K ## InstallGlobalFunction( TransStabCSPG, function(G,H) local n, # degree of G chainG, # stabilizer chain of `G' chainH, # stabilizer chain of `H' x,y, # first two points of the base of G stabgroup, # stabilizer of x in G chainstabgroup, hstabgroup, # stabilizer of x in H chainhstabgroup, u,v, # indices of points in G.orbit, stabgroup.orbit g, # list of permutations whose product is # (semi)random element of G notinH, # boolean; true if g is not in H word, # list of permutations whose product is # (semi)random element of <H,g> len, # length of word hword, # list of permutations giving random element of H tau,sigma, # lists of permutations whose tau1,sigma1,# products are coset representatives i,j,k, # loop variables K; # K=<H,g> #Print(Size(G),",",Size(H)); n := LargestMovedPoint(G); chainG:= StabChainMutable( G ); x := chainG.orbit[1]; stabgroup := Stabilizer(G,x,OnPoints); chainstabgroup := StabChainMutable( stabgroup ); y := chainstabgroup.orbit[1]; hstabgroup := Stabilizer(H,x,OnPoints); chainhstabgroup:= StabChainMutable( hstabgroup ); chainH:= StabChainMutable( H ); ExtendStabChain( chainH, BaseStabChain(chainG) ); ExtendStabChain( chainhstabgroup, BaseStabChain( chainstabgroup ) ); # try to embed H into bigger subgroups; stop when result is transitive repeat # Print("brum"); # first, take random element of G\H repeat v := Random(1, Length( chainG.orbit )); g := CosetRepAsWord( x, chainG.orbit[v], chainG.transversal ); u := Random(1, Length( chainstabgroup.orbit )); Append(g,CosetRepAsWord( y, chainstabgroup.orbit[u], chainstabgroup.transversal )); notinH := false; v := ImageInWord(x,g); if not IsBound( chainH.transversal[v] ) then notinH := true; else u := ImageInWord(y,g); u := ImageInWord( u, CosetRepAsWord( x, v, chainH.transversal ) ); if not IsBound( chainhstabgroup.transversal[u] ) then notinH := true; fi; fi; until notinH; for i in [1..n] do # construct semirandom element of <H,g> word := []; for j in [1..5] do len := Length(word); for k in [1..Length(g)] do word[len+k] := g[k]; od; len := Length(word); hword := RandomElmAsWord(H); for k in [1..Length(hword)] do word[len+k] := hword[k]; od; od; # check whether word is in H; # if not, then let g=cosetrep of word in G_{xy} v := ImageInWord(x,word); tau := CosetRepAsWord( x, v, chainH.transversal ); if tau = [] then tau1 := CosetRepAsWord( x, v, chainG.transversal ); u := ImageInWord(y,word); u := ImageInWord(u,tau1); sigma1 := CosetRepAsWord( y, u, chainstabgroup.transversal ); g := Concatenation(tau1,sigma1); else u := ImageInWord(y,word); u := ImageInWord(u,tau); sigma := CosetRepAsWord( y, u, chainhstabgroup.transversal ); if sigma = [] then tau1 := CosetRepAsWord( x, v, chainG.transversal ); u := ImageInWord(y,word); u := ImageInWord(u,tau1); sigma1 := CosetRepAsWord( y, u, chainstabgroup.transversal ); g := Concatenation(tau1,sigma1); fi; fi; od; # check whether H,g generate a proper subgroup of G K := ClosureGroup(H,Product(g)); if 1 < Size(G)/Size(K) then H := K; chainH:= StabChainMutable( H ); #Print(Size(H)); hstabgroup := Stabilizer(H,x,OnPoints); chainhstabgroup:= StabChainMutable( hstabgroup ); ExtendStabChain( chainhstabgroup, BaseStabChain(chainstabgroup) ); ExtendStabChain( chainH, BaseStabChain(chainG) ); fi; until Length( chainH.orbit ) = n; return H; end ); ############################################################################# ## #F PullbackKernelCSPG() . . . . . . . . . . . . . . . pull back the kernels ## InstallGlobalFunction( PullbackKernelCSPG, function( homlist, normals, factors, auxiliary, index ) local lenhomlist, # length of homlist i, j, # loop variables gens, # list of generators in kernels # of homomorphisms in homlist k, # kernel kg, # kernel generators g; # a member of gens # for each kernel, compute preimages of the kernel generators in the # input group add these to generators of the current subnormal subgroup # in the composition series lenhomlist := Length(homlist); for i in [1..lenhomlist] do k:=KernelOfMultiplicativeGeneralMapping(homlist[i]); kg:=GeneratorsOfGroup(k); if IsBound(auxiliary[i]) then gens := Union( GeneratorsOfGroup( k ), StabChainMutable( auxiliary[i] ).generators); if Length(gens)>6 then g:=Group(gens,()); if IsSubset(auxiliary[i],k) then SetSize(g,Size(auxiliary[i])); else StabChainOptions(g).limit:=Size(k)*Size(auxiliary[i]); fi; gens:=SmallGeneratingSet(g); fi; else if Length(kg)>5 then gens:=SmallGeneratingSet(k); else gens := kg; fi; fi; for g in gens do for j in [1..i-1] do g := PreImagesRepresentative(homlist[i-j],g); od; Add(normals[index],g); Add(factors[index],()); od; od; end ); ############################################################################# ## #F PullbackCSPG() . . . . . . . . . . . . . . . . . . . . . . . . pull back ## InstallGlobalFunction( PullbackCSPG, function(p,homlist) local i, # loop variable lenhomlist; # length of homlist # compute a preimage of the permutation p in the input group lenhomlist := Length(homlist); for i in [1..lenhomlist] do p := PreImagesRepresentative(homlist[lenhomlist+1-i],p); od; return p; end ); ############################################################################# ## #F CosetRepAsWord() . . . . . . . . . write a coset representative as word ## ## returns the cosetrep carrying y to the base point x as a word in the ## generators. If y is not in the orbit of x, returns [] ## InstallGlobalFunction( CosetRepAsWord, function(x,y,transversal) local word, # list of permutations point; # element of permutation domain word := []; if IsBound(transversal[y]) then point := y; repeat word[Length(word)+1] := transversal[point]; point := point^transversal[point]; until point = x; fi; return word; end ); ############################################################################# ## #F ImageInWord() . . . image of a point under a permutation written as word ## ## computes the image of x when the list of permutations word is applied ## InstallGlobalFunction( ImageInWord, function(x,word) local i, # loop variable value; # element of permutation domain value := x; for i in [1..Length(word)] do value := value^word[i]; od; return value; end ); ############################################################################# ## #F SiftAsWord( <chain>, <perm> ) . . . . sift a permutation written as word ## ## given a list <perm> of permutations and a stabilizer chain <chain> for ## the group $G$, the routine computes the residue at the sifting of perm ## through the SGS of $G$. ## The output is a list of length 2: the first component is the siftee, ## as a word, the second component is 0 if perm in $G$, and i if the siftee ## on the i^th level could not be computed. ## #T <perm> is changed! ## InstallGlobalFunction( SiftAsWord, function( chain, perm ) local i, # loop variable y, # element of permutation domain word, # the list collecting the siftee of perm len, # length of word coset, # word representing a coset in a stabilizer index, # the level where the siftee cannot be computed stb; # the stabilizer group we currently work with # perm must be a list of permutations itself! stb := chain; word := perm; index := 0; while IsBound(stb.stabilizer) do index:=index+1; y:=ImageInWord(stb.orbit[1],word); if IsBound(stb.transversal[y]) then coset := CosetRepAsWord(stb.orbit[1],y,stb.transversal); len := Length(word); for i in [1..Length(coset)] do word[len+i] := coset[i]; od; stb:=stb.stabilizer; else return([word,index]); fi; od; index := 0; return [word,index]; end ); ############################################################################# ## #F InverseAsWord() . . . . . . . . . . invert a permutation written as word ## ## given a list of permutations "list", the inverses of these permutations ## in inverselist, and a list of permutations "word" with elements from ## list, returns the inverse of word as a list of inverses from inverselist ## InstallGlobalFunction( InverseAsWord, function(word,list,inverselist) local i, # loop variable p, # position inverse; # the inverse of word if word = [ () ] then return word; fi; inverse := []; for i in [1..Length(word)] do # identity tests are cheaper if the degree gets bigger. p:=PositionProperty(list,j->IsIdenticalObj(j,word[Length(word)+1-i])); if p=fail then # this is very unlikely to happen. p:=Position(list,word[Length(word)+1-i]); fi; inverse[i] := inverselist[p]; od; return inverse; end ); ############################################################################# ## #F RandomElmAsWord( <chain> ) . . . . . . . random element written as word ## ## given an stabilizer chain <chain> for the group $G$, returns a uniformly ## distributed random element of $G$, ## as a word in the strong generators ## InstallGlobalFunction( RandomElmAsWord, function( chain ) local i, # loop variable word, # the random element len, # length of word stb, # the stabilizer group we currently work with v, # index of random element of stb.orbit coset; # word representing a coset word:=[]; stb:= chain; while IsBound(stb.stabilizer) do v := Random(1,Length(stb.orbit)); coset := CosetRepAsWord(stb.orbit[1],stb.orbit[v],stb.transversal); len := Length(word); for i in [1..Length(coset)] do word[len+i] := coset[i]; od; stb:=stb.stabilizer; od; return word; end ); ############################################################################# ## #M PCore() . . . . . . . . . . . . . . . . . . p core of a permutation group ## ## O_p(G), the p-core of G, is the maximal normal p-subgroup ## Output of routine: the subgroup O_p(workgroup) ## reference: Luks-Seress ## InstallMethod( PCoreOp, "for a permutation group, and a positive integer", true, [ IsPermGroup, IsPosInt ], 0, function(workgroup,p) local n, # degree of workgroup G, # a factor group of workgroup list, # the record workgroup.compositionSeries normals, # gens for the subgroups in the composition series factorsize, # the sizes of factor groups in composition series index, # loop variable running through the indices of # subgroups in the composition series primes, # list of primes in the factorization of numbers ppart, # p-part of Size(G) homlist, # list of homomorphisms applied to workgroup lenhomlist, # length of homlist K, N, # subnormal subgroups of G from composition series g, # generator of K C, # centralizer of N in K D, # the p-part of C order, # order of a generator of C H, # first solvable, then also # abelian normal p-subgroup of G series, # the derived series of H; H becomes abelian when it # is redefined as last nontrivial term of series actionlist, # record of G action on transitive # constituent pieces of H Ggens, # generators of stab. chain of `G' i, j, # loop variables image, # list of images of generators of G # acting on pieces of H GG, # the image of G at this action hom, # the homomorphism from G to GG pgenlist; # list of generators for the p-core # handle trivial cases if not IsPrime(p) then return TrivialSubgroup(workgroup); fi; if IsTrivial(workgroup) then return TrivialSubgroup(workgroup); fi; if Size(workgroup) mod p <> 0 then # p does not divide Size(workgroup) return TrivialSubgroup(workgroup); fi; #handle nilpotent case directly if IsNilpotentGroup( workgroup ) then # compute the p-part of generators of workgroup primes := Collected( Factors( Size(workgroup) ) ); ppart := p^primes[PositionProperty( primes, x->x[1]=p )][2]; pgenlist := []; for g in StabChainMutable( workgroup ).generators do Add( pgenlist, g^( Size(workgroup)/( ppart ) ) ); od; D := SubgroupNC( workgroup, pgenlist ); if ppart > 1 then SetIsPGroup( D, true ); SetPrimePGroup( D, p ); SetSylowSubgroup( workgroup, p, D ); SetHallSubgroup( workgroup, [p], D ); fi; return D; fi; n := LargestMovedPoint(workgroup); G := workgroup; list := CompositionSeries(G); # normals := Copy(list[1]); # factorsize := list[3]; normals := List( [1..Length(list)-1], i->ShallowCopy(StabChainMutable(list[i]).generators)); factorsize := List([1..Length(list)-1],i->Size(list[i])/Size(list[i+1])); Add(normals, [()]); homlist := []; index := Length(factorsize); # try to find smallest subgroup in composition series with nontrivial # p-core. The normal closure of this p-core is a solvable normal # p-subgroup of G; taking commutator subgroups, find abelian normal # p-subgroup of G. # represent G acting on transitive constituent pieces of abelian normal # p-subgroup; kernel is abelian p-group. Take image at this action, and # repeat while index > 0 do if factorsize[index] <> p then index := index-1; else N := SubgroupNC(Parent(G),normals[index+1]); # define K := SubGroup(Parent(G),normals[index]); # N has trivial p-core; check whether K has nontrivial one # K=N is possible when we work in homomorphic images of original if ForAll(normals[index], x -> x in N) then index := index-1; else K := ClosureGroup( N,normals[index], rec( size:=p*Size(N) ) ); C := CentralizerNormalCSPG(K,N); # O_p(K) is cyclic or trivial; it must show up in C # C is always abelian; check whether it has p-part D := []; C:= GeneratorsOfGroup( C ); for i in [1..Length( C )] do order := Order(C[i]); if order mod p = 0 then D[i] := C[i]^(order/p); else D[i] := (); fi; od; # redefine C as the p-core of C C := SubgroupNC(Parent(K),D); if IsTrivial(C) then index := index-1; else H := NormalClosure(G,C); series := DerivedSeriesOfGroup(H); H := series[Length(series)-1]; # at that moment, H is abelian normal in G # define new action of G with H in the kernel actionlist := ActionAbelianCSPG(H,n); Ggens:= StabChainMutable( G ).generators; image:= List( Ggens, g -> ImageOnAbelianCSPG( g, actionlist ) ); # take homomorphic image of G GG := GroupByGenerators(image,()); hom:=GroupHomomorphismByImagesNC(G,GG,Ggens,image); Add(homlist,hom); #force makemapping SetSize(GG,Size(G)/Size( KernelOfMultiplicativeGeneralMapping( hom ))); # find new action of subgroups in composition series for i in [1..index] do for j in [1..Length(normals[i])] do normals[i][j] := # ImageOnAbelianCSPG(normals[i][j],actionlist); Image(hom,normals[i][j]); od; od; G := GG; index := index-1; fi; # IsTrivial(C) fi; # K = N fi; # factorsize[index] <> p od; # create output; # the p-core is the kernel of homomorphisms applied to workgroup lenhomlist := Length(homlist); if lenhomlist = 0 then pgenlist := [()]; else pgenlist := []; for i in [1..lenhomlist] do for g in GeneratorsOfGroup( KernelOfMultiplicativeGeneralMapping( homlist[i] ) ) do for j in [1..i-1] do g := PreImagesRepresentative(homlist[i-j],g); od; Add(pgenlist,g); od; od; fi; D := SubgroupNC(workgroup,pgenlist); if not ForAll(pgenlist,IsOne) then SetIsPGroup( D, true ); SetPrimePGroup( D, p ); fi; return D; end ); ############################################################################# ## #M SolvableRadical( <G> ) . . . . . solvable radical of a permutation group ## ## the radical is the maximal solvable normal subgroup ## output of routine: the subgroup radical of workgroup ## reference: Luks-Seress ## InstallMethod( SolvableRadical, "for a permutation group", [ IsPermGroup ], function(workgroup) local n, # degree of workgroup G, # a factor group of workgroup list, # the record workgroup.compositionSeries normals, # gens for the subgroups in the composition series factorsize, # the sizes of factor groups in composition series index, # loop variable running through the indices of # subgroups in the composition series primes, # list of primes in the factorization of numbers homlist, # list of homomorphisms applied to workgroup lenhomlist, # length of homlist K, N, # subnormal subgroups of G from composition series g, # generator of K C, # centralizer of N in K H, # first solvable, # then also abelian normal subgroup of G series, # the derived series of H; H becomes abelian when it # is redefined as last nontrivial term of series actionlist, # record of G action on transitive # constituent pieces of H Ggens, # generators of stab. chain of `G' i, j, # loop variables image, # list of images of generators of G # acting on pieces of H GG, # the image of G at this action hom, # the homomorphism from G to GG map, # natural homomorphism for radical. solvable, # list of generators for the radical o, # orbits of G b, # blocks TryReduction;# function to test whether a hom. can reduce if IsTrivial(workgroup) then return TrivialSubgroup(workgroup); fi; if IsSolvableGroup(workgroup) then return workgroup; fi; n := LargestMovedPoint(workgroup); G := workgroup; # if the degree is big, try to reduce it in a first step if n>1000 then TryReduction:=function(hom) local s,f,k,map; s:=Size(G)/Size(Image(hom)); # kernel size # is the kernel solvable? If yes we can go to the image f:=Collected(Factors(s)); # at most 2 primes or all primes to power 1 -> Solvable if Length(f)<3 or ForAll(f,i->i[2]=1) then Info(InfoGroup,1,"solvable kernel size ",f); # OK, transfer result back k:=SolvableRadical(Image(hom)); solvable:=PreImage(hom,k); map:=hom*NaturalHomomorphismByNormalSubgroup(Image(hom),k); SetKernelOfMultiplicativeGeneralMapping(map,solvable); AddNaturalHomomorphismsPool(G,solvable,map); return solvable; fi; return fail; end; # try orbits o:=ShallowCopy(Orbits(G,MovedPoints(G))); if Length(o)>1 then SortBy(o, Length); for i in o do Info(InfoGroup,1,"trying orbit length ",Length(o)); hom:=ActionHomomorphism(G,i,"surjective"); K:=TryReduction(hom); if K<>fail then return K; fi; od; fi; # try blocks on orbits for i in o do b:=Blocks(G,i); if Length(b)>1 then Info(InfoGroup,1,"trying blocks length ",Length(b)); hom:=ActionHomomorphism(G,b,OnSets,"surjective"); K:=TryReduction(hom); if K<>fail then return K; fi; fi; od; fi; list := CompositionSeries(G); # normals := Copy(list[1]); # factorsize := list[3]; #was: #normals := List( [1..Length(list)-1], # i->ShallowCopy(StabChainMutable(list[i]).generators)); # but not all subgroups in the comp.ser have their own stabchain. normals:=[]; for i in [1..Length(list)-1] do if HasStabChainMutable(list[i]) then normals[i]:=ShallowCopy(StabChainMutable(list[i]).generators); else normals[i]:=ShallowCopy(GeneratorsOfGroup(list[i])); fi; od; factorsize := List([1..Length(list)-1],i->Size(list[i])/Size(list[i+1])); Add(normals, [()]); homlist := []; index := Length(factorsize); # try to find smallest subgroup in composition series with nontrivial # radical. The normal closure of this radical is a solvable normal # subgroup of G; taking commutator subgroups, find abelian normal # subgroup of G. # represent G acting on transitive constituent pieces of abelian normal # subgroup; kernel is abelian normal. # Take image at this action, and repeat while index > 0 do primes := Factors(Integers,factorsize[index]); # if the factor group is not cyclic, no chance for nontrivial radical if Length(primes) > 1 then index := index-1; else N := SubgroupNC(Parent(G),normals[index+1]); # define K := SubGroup(Parent(G),normals[index]); # N has trivial radical; check whether K has nontrivial one # K=N is possible when we work in homomorphic images of original if ForAll(normals[index], x -> x in N) then index := index-1; else K := ClosureGroup( N,normals[index], rec( size:=factorsize[index]*Size(N) ) ); Size(K); C := CentralizerNormalCSPG(K,N); # radical of K is cyclic or trivial; it has to show up in C if IsTrivial(C) then index := index-1; else H := NormalClosure(G,C); series := DerivedSeriesOfGroup(H); H := series[Length(series)-1]; # at that moment, H is abelian normal in G # define new action of G with H in the kernel actionlist := ActionAbelianCSPG(H,n); --> -------------------- --> maximum size reached --> -------------------- [ Verzeichnis aufwärts0.58unsichere Verbindung Übersetzung europäischer Sprachen durch Browser ] |
2026-03-28