%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% primitive.tex IRREDSOL documentation Burkhard Hoefling %% %% @(#)$Id: primitive.tex,v 1.4 2005/07/06 10:08:23 gap Exp $ %% %% Copyright (C) 2003-2005 by Burkhard Hoefling, %% Institut fuer Geometrie, Algebra und Diskrete Mathematik %% Technische Universitaet Braunschweig, Germany %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Chapter{Primitive solvable groups} A finite group <G> is called {\it primitive} if it has a maximal subgroup <M> with trivial core; the group acts faithfully and primitively on the cosets of such a maximal subgroup. Now assume that <G> is primitive and solvable. Then there exists a unique conjugacy class of such maximal subgroups; the index of <M> in <G> is called the degree of <G>. Moreover, $<M>$ complements the socle <N> of $<G>$. THe socle <N> coincides with the Fitting subgroup of <G>; it is the unique minimal normal subgroup <N> of~<G>. Therefore, the index of <M> in <G> is a prime power, $p^n$, say. Regarding <N> as a $\F_p$-vector space, <M> acts as an irreducible subgroup of $GL(n,p)$ on <N>. Conversely, if <M> is an irreducible solvable subgroup of $GL(n,p)$, and $V = \F_p^n$, then the split extension of $V$ by <M> is a primitive solvable group. This establishes a well known bijection between the isomorphism types (or, equivalently, the $Sym(p^n)$-conjugacy classes) of primitive solvable groups of degree $<p>^<n>$ and the conjugacy classes of irreducible solvable subgroups of $GL(n, p)$. The {\IRREDSOL} package provides functions for translating between primitive solvable groups and irreducible solvable matrix groups, which are described in Section~"Translating between irreducible solvable matrix groups and primitive solvable groups". Moreover, there are functions for finding primitive solvable groups with given properties, see Section~"Finding primitive pc groups with given properties" and "Finding primitive solvable permutation groups with given properties". %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Translating between irreducible solvable matrix groups and primitive solvable groups} \>PrimitivePcGroupIrreducibleMatrixGroup(<G>) F \>PrimitivePcGroupIrreducibleMatrixGroupNC(<G>) F For a given irreducible solvable matrix group <G> over a prime field, this function returns a primitive pc group <H> which is the split extension of <G> with its natural underlying vector space~<V>. The `NC' version does not check whether <G> is over a prime field, or whether <G> is irreducible. The group <H> has an attribute `Socle' (see "ref:Socle" in the {\GAP} reference manual, corresponding to~<V>. If the package {\CRISP} is loaded, then the attribute `SocleComplement' (see "crisp:SocleComplement" in the {\CRISP} manual) is set to a subgroup of <H> isomorphic with <G>. \beginexample gap> PrimitivePcGroupIrreducibleMatrixGroup ( > IrreducibleSolvableMatrixGroup (4,2,2,3)); <pc group of size 160 with 6 generators> \endexample \>`PrimitivePermutationGroupIrreducibleMatrixGroup(<G>)'% {PrimitivePermutationGroupIrreducibleMatrixGroup}% @{`PrimitivePermutationGroup\\Irreducible\\MatrixGroup'} F \>`PrimitivePermutationGroupIrreducibleMatrixGroupNC(<G>)'% {PrimitivePermutationGroupIrreducibleMatrixGroupNC}% @{`PrimitivePermutationGroup\\Irreducible\\MatrixGroupNC'} F For a given irreducible solvable matrix group <G> over a prime field, this function returns a primitive permutation group~<H>, representing the affine action of <G> on its natural vector space~<V>. The `NC' version does not check whether <G> is over a prime field, or whether <G> is irreducible. The group <H> has an attribute `Socle' (see "ref:Socle" in the {\GAP} reference manual, corresponding to~<V>. If the package {\CRISP} is loaded, then the attribute `SocleComplement' (see "crisp:SocleComplement" in the {\CRISP} manual) is set to a subgroup of <H> isomorphic with <G>. \beginexample gap> PrimitivePermutationGroupIrreducibleMatrixGroup ( > IrreducibleSolvableMatrixGroup (4,2,2,3)); <permutation group of size 160 with 6 generators> \endexample \>`IrreducibleMatrixGroupPrimitiveSolvableGroup(<G>)'% {IrreducibleMatrixGroupPrimitiveSolvableGroup}% @{`IrreducibleMatrixGroup\\Primitive\\SolvableGroup'} F \>`IrreducibleMatrixGroupPrimitiveSolvableGroupNC(<G>)'% {IrreducibleMatrixGroupPrimitiveSolvableGroupNC}% @{`IrreducibleMatrixGroup\\Primitive\\SolvableGroupNC'} F For a given primitive solvable group <G>, this function returns a matrix group obtained from the conjugation action of <G> on its unique minimal normal subgroup <N>, regarded as a vector space over $\F_p$, where $p$ is the exponent of <N>. The $\F_p$-basis of <N> is chosen arbitrarily, so that the matrix group returned is unique only up to conjugacy in the relevant $GL(n, p)$. The NC version does not check whether <G> is primitive and solvable. \beginexample gap> IrreducibleMatrixGroupPrimitiveSolvableGroup (SymmetricGroup (4)); Group([ <an immutable 2x2 matrix over GF2>, <an immutable 2x2 matrix over GF2> , <an immutable 2x2 matrix over GF2>, <an immutable 2x2 matrix over GF2> ]) \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Finding primitive pc groups with given properties} \>AllPrimitivePcGroups(<func_1>, <arg_1>, <func_2>, <arg_2>, \dots) F This function returns a list of all primitive solvable pc groups <G> in the {\IRREDSOL} library for which the return value of $<func_i>(G)$ lies in <arg_i>. The arguments <func_1>, <func_2>, \dots, must be {\GAP} functions which take a pc group as their only argument and return a value, and <arg_1>, <arg_2>, \dots, must be lists. If <arg_i> is not a list, <arg_i> is replaced by the list `[<arg_i>]'. One of the functions must be `Degree' or one of its equivalents, see below. The following functions <func_i> are handled particularly efficiently. \beginlist \item{--} `Degree', `NrMovedPoints', `LargestMovedPoint' \item{--} `Order', `Size' \endlist Note that there is also a function `IteratorPrimitivePcGroups' (see "IteratorPrimitivePcGroups") which allows one to run through the list produced by `AllPrimitivePcGroups' without having to store all the groups in the list simultaneously. \beginexample gap> AllPrimitivePcGroups (Degree, [1..255], Order, [168]); [ <pc group of size 168 with 5 generators> ] \endexample \>OnePrimitivePcGroup(<func_1>, <arg_1>, <func_2>, <arg_2>, \dots) F This function returns one primitive solvable pc group <G> in the {\IRREDSOL} library for which the return value of $<func_i>(G)$ lies in <arg_i>, or `fail' if no such group exists. The arguments <func_1>, <func_2>, \dots, must be {\GAP} functions which take a pc group as their only argument and return a value, and <arg_1>, <arg_2>, \dots, must be lists. If <arg_i> is not a list, <arg_i> is replaced by the list `[<arg_i>]'. One of the functions must be `Degree' or one of its, equivalents, `NrMovedPoints' or `LargestMovedPoint'. For a list of functions which are handled particularly efficiently, see "AllPrimitivePcGroups". \beginexample gap> OnePrimitivePcGroup (Degree, [256], Order, [256*255]); <pc group of size 65280 with 11 generators> \endexample \>IteratorPrimitivePcGroups(<func_1>, <arg_1>, <func_2>, <arg_2>, \dots) F This function returns an iterator which runs through the list of all primitive solvable pc groups <G> in the {\IRREDSOL} library such that $<func_i>(G)$ lies in <arg_i>. The arguments <func_1>, <func_2>, \dots, must be {\GAP} functions taking a pc group as their only argument and returning a value, and <arg_1>, <arg_2>, \dots, must be lists. If <arg_i> is not a list, <arg_i> is replaced by the list `[<arg_i>]'. One of the functions must be `Degree' or one of its, equivalents, `NrMovedPoints' or `LargestMovedPoint'. For a list of functions which are handled particularly efficiently, see "AllPrimitivePcGroups". Using `IteratorPrimitivePcGroups'(<func_1>, <arg_1>, <func_2>, <arg_2>, \dots)) is functionally equivalent to `Iterator'(`AllPrimitivePcGroups'(<func_1>, <arg_1>, <func_2>, <arg_2>, \dots)) (see "ref:Iterators" in the {\GAP} reference manual for details) but does not compute all relevant pc groups at the same time. This may save some memory. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Finding primitive solvable permutation groups with given properties} \>AllPrimitiveSolvablePermutationGroups(<func_1>, <arg_1>, <func_2>, <arg_2>, \dots) F This function returns a list of all primitive solvable permutation groups <G> corresponding to irreducible matrix groups in the {\IRREDSOL} library for which the return value of $<func_i>(G)$ lies in <arg_i>. The arguments <func_1>, <func_2>, \dots, must be {\GAP} functions which take a permutation group as their only argument and return a value, and <arg_1>, <arg_2>, \dots, must be lists. If <arg_i> is not a list, <arg_i> is replaced by the list `[<arg_i>]'. One of the functions must be `Degree' or one of its equivalents, see below. The following functions <func_i> are handled particularly efficiently. \beginlist \item{--} `Degree', `NrMovedPoints', `LargestMovedPoint' \item{--} `Order', `Size' \endlist Note that there is also a function `IteratorPrimitivePermutationGroups' (see "IteratorPrimitivePermutationGroups") which allows one to run through the list produced by `AllPrimitivePcGroups' without having to store all of the groups simultaneously. \beginexample gap> AllPrimitiveSolvablePermutationGroups (Degree, [1..100], Order, [72]); [ Group([ (1,4,7)(2,5,8)(3,6,9), (1,2,3)(4,5,6)(7,8,9), (2,4)(3,7)(6,8), (2,3)(5,6)(8,9), (4,7)(5,8)(6,9) ]), Group([ (1,4,7)(2,5,8)(3,6,9), (1,2,3)(4,5,6)(7,8,9), (2,5,3,9)(4,8,7,6), (2,7,3,4)(5,8,9,6), (2,3)(4,7)(5,9)(6,8) ]), Group([ (1,4,7)(2,5,8)(3,6,9), (1,2,3)(4,5,6)(7,8,9), (2,5,6,7,3,9,8,4) ]) ] gap> List (last, IdGroup); [ [ 72, 40 ], [ 72, 41 ], [ 72, 39 ] ] \endexample \>OnePrimitiveSolvablePermutationGroup(<func_1>, <arg_1>, <func_2>, <arg_2>, \dots) F This function returns one primitive solvable permutation group <G> corresponding to irreducible matrix groups in the {\IRREDSOL} library for which the return value of $<func_i>(G)$ lies in <arg_i>, or `fail' if no such group exists. The arguments <func_1>, <func_2>, \dots, must be {\GAP} functions which take a permutation group as their only argument and return a value, and <arg_1>, <arg_2>, \dots, must be lists. If <arg_i> is not a list, <arg_i> is replaced by the list `[<arg_i>]'. One of the functions must be `Degree' or one of its, equivalents, `NrMovedPoints' or `LargestMovedPoint'. For a list of functions which are handled particularly efficiently, see "AllPrimitiveSolvablePermutationGroups". \beginexample gap> OnePrimitiveSolvablePermutationGroup (Degree, [1..100], Size, [123321]); fail \endexample \>IteratorPrimitivePermutationGroups(<func_1>, <arg_1>, <func_2>, <arg_2>, \dots) F This function returns an iterator which runs through the list of all primitive solvable groups <G> in the {\IRREDSOL} library such that $<func_i>(G)$ lies in <arg_i>. The arguments <func_1>, <func_2>, \dots, must be {\GAP} functions taking a pc group as their only argument and returning a value, and <arg_1>, <arg_2>, \dots, must be lists. If <arg_i> is not a list, <arg_i> is replaced by the list `[<arg_i>]'. One of the functions must be `Degree' or one of its, equivalents, `NrMovedPoints' or `LargestMovedPoint'. For a list of functions which are handled particularly efficiently, see "AllPrimitiveSolvablePermutationGroups". Using `IteratorPrimitiveSolvablePermutationGroups'(<func_1>, <arg_1>, <func_2>, <arg_2>, \dots)) is functionally equivalent to `Iterator'(`AllPrimitiveSolvablePermutationGroups'(<func_1>, <arg_1>, <func_2>, <arg_2>, \dots)) (see "ref:Iterators" in the {\GAP} reference manual for details) but does not compute all relevant pc groups at the same time. This may save some memory. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Recognizing primitive solvable groups} \>IdPrimitiveSolvableGroup(<G>) F \>IdPrimitiveSolvableGroupNC(<G>) F returns the id of the primitive solvable group <G>. This is the same as the id of `IrreducibleMatrixGroupPrimitiveSolvableGroup(<G>)', see "IrreducibleMatrixGroupPrimitiveSolvableGroup" and "IdIrreducibleSolvableMatrixGroup". Note that two primitive solvable groups are isomorphic if, and only if, their ids returned by `IdPrimitivePcGroup' are the same. The NC version does not check whether <G> is primitive and solvable. \beginexample gap> G := PrimitivePcGroupIrreducibleMatrixGroup (\ > IrreducibleSolvableMatrixGroup (6,2,3,3)); <pc group of size 8064 with 10 generators> gap> IdPrimitiveSolvableGroup (G); [ 6, 2, 3, 3 ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E %%