%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  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
%%