%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Computing with nilpotent linear groups}

\atindex{Nilmat package}{@Nilmat package}

This chapter contains the main functions of this package for computing
with nilpotent matrix groups.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Preliminaries}

We first describe some of the basic functions used in
\package{Nilmat} for nilpotency testing of a group $G$ input by a
finite generating set of matrices.

\> JordanSplitting( <G> ) A

For a subgroup $G$ of $GL(n,\F)$, $\F=GF(q)$ or $\Q$, returns a list
of two groups $[S,U]$, where $S$ is the semisimple part of $G$ (the
group generated by the semisimple parts of the generators of $G$),
and $U$ is the unipotent part of $G$ (the group generated by the
unipotent parts of the generators of $G$). If $G$ is nilpotent, then
$G \cong S \times U$, the group $S$ is completely reducible and $U$
is unipotent. This attribute relies on the {\GAP} attribute
`JordanDecomposition'.

\> IsUnipotentMatGroup( <G> ) P

For a subgroup $G$ of $GL(n,\F)$, $\F=GF(q)$ or $\Q$, returns `true'
if <G> is unipotent (i.e. conjugate to a group of upper unitriangular
matrices) and `false' otherwise.

\> ClassLimit( <n> , <F> ) F

returns an upper bound on the nilpotency class of nilpotent
subgroups of $GL(n,\F)$, $\F=GF(q)$ or $\Q$.

\> AbelianNormalSeries( <G>, <l> ) F

Here $G\< GL(n,q)$ and <l> is a positive integer. If <G> is nilpotent
of class at most <l> and the order of <G> is coprime to the
characteristic of $GF(q)$, then this function determines a normal
series with abelian factors for <G>. Otherwise, the function may
still return such a series or it may return `fail'. The function is
based on recursively selecting non-central elements from the second
centers of terms in the abelian series.

\> PiPrimarySplitting( <G> ) A

For a subgroup $G$ of $GL(n,q)$, this function returns a list of
two subgroups $[B,C]$ with $G = BC$. If $G$ is nilpotent, then
$G \cong B \times C$, the group $C$ is the product of all Sylow
$p$-subgroups with $p>n$ and $B$ is the product of all other
Sylow subgroups of $G$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Testing nilpotency}

The following is one of the main functions of the \package{Nilmat}
package.

\> IsNilpotentMatGroup( <G> ) F

For a subgroup $G$ of $GL(n,\F)$, $\F=GF(q)$ or $\Q$, returns
`true' if <G> is nilpotent and `false' otherwise. This function is
also installed as method for the property `IsNilpotentGroup'.

We include a brief description of the algorithm behind this function.
Let $X$ be a generating set of the given group <G>. The first stage
of testing nilpotency of $G$ is reduction to the semisimple part $S$
of $G$. The procedure for reducing to the semisimple case is based on
the \package{Nilmat} functions `JordanSplitting' and `IsUnipotentGroup'
described in the previous section. In the following, we assume that
all elements of $X$ are semisimple matrices.

If $\F=GF(q)$, then we apply the function `PiPrimarySplitting' to
the group $S$ and thus reduce to a smaller group $B$. Next, we
attempt to compute an abelian normal series for $B$ using the
function `AbelianNormalSeries'. If no such series exists, then $G$
is not nilpotent. If such a series exists, then we use it to
construct the Sylow subgroups of $B$ and check that they commute
pairwise. For details on this method, see \cite{DF06}.

If $\F=\Q$, then we first use a reduction mod $p$ for a suitable
prime $p$ and check that the image of $G$ under the corresponding
congruence homomorphism is nilpotent using the finite field method
above. If so, then we construct the kernel of the congruence
homomorphism and test whether this is central in $G$. We refer to
\cite{DF07} for details. Note that the construction of the
congruence homomorphism and its kernel is based on the methods of
the Package \package{Polenta}; see also \cite{AE05} for
background.

The nilpotency testing functions of the package \package{Nilmat}
have advantages over the standard {\GAP} methods for
`IsNilpotentGroup'. When $\F$ is finite, the \package{Nilmat}
functions have better runtimes for all input groups we tested.
When $\F$ is infinite, the standard {\GAP} functions frequently do
not terminate at all in sensible time; on the other hand, the
\package{Nilmat} functions always terminate, with comparatively
small runtimes (see the examples in Chapter 3).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Finiteness, Sylow subgroups, testing complete reducibility}

The function `IsNilpotentMatGroup' determines various structural
properties of the given group as by-products. The functions in
this section have been designed to exploit these by-products.

\> IsFiniteNilpotentMatGroup( <G> ) F

For a nilpotent subgroup $G$ of $GL(n,\Q)$, returns `true' if $G$
is finite and `false' otherwise. Note that the function assumes
that $G$ is nilpotent and may return an incorrect result if not.
The function exploits the by-products of the nilpotency testing
functions in \package{Nilmat} and hence runs particularly fast
(and usually faster than the standard {\GAP} method for testing
finiteness) if they have been used to check nilpotency. This
function is also installed as method for the property `IsFinite'.

\> SylowSubgroupsOfNilpotentFFMatGroup( <G> ) F

For a nilpotent subgroup $G$ of $GL(n,\F)$, $\F=GF(q)$, returns
the list of all Sylow subgroups. The advantage of this function over
the {\GAP} function `SylowSubgroup' is that the former function
returns all Sylow subgroups of $G$ without first computing all prime
divisors of the order of $G$. This function is installed as method
for `SylowSystem' for nilpotent matrix groups.

\> SizeOfNilpotentMatGroup( <G> ) F

For a finite nilpotent subgroup $G$ of $GL(n,\F)$, $\F=GF(q)$ or $\Q$, this
function returns the order of $G$. The function is based on by-products of
the nilpotency testing in \package{Nilmat}. Again, in some situations it is
more efficient than the similar default {\GAP} function; see the examples
in Chapter 3.

\> IsCompletelyReducibleNilpotentMatGroup( <G> ) F

For a nilpotent subgroup $G$ of $GL(n,\F)$, $\F=GF(q)$ or $\Q$, returns
`true' if $G$ is completely reducible and `false' otherwise.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{A library of primitive nilpotent groups}

Another main part of \package{Nilmat} is a library of nilpotent
primitive matrix groups over finite fields.

\> NilpotentPrimitiveMatGroups( <n> , <p> , <l> ) F

returns a complete and irredundant list $L$ of the conjugacy class
representatives of the nilpotent primitive subgroups of $GL(n,p^l)$.
The list $L$ contains non-abelian (i.e. non-cyclic) subgroups only
if $n=2m$, $m$ is odd, and $p^l \equiv 3$ mod $4$. Every non-abelian
group in $L$ is given by three generators. Note that the groups in
$L$ know their orders i.e. the attribute `Size' has been set for these
groups.

\> SizesOfNilpotentPrimitiveMatGroups( <n> , <p> , <l> ) F

returns the list of orders of groups in the list $L$ output by
`NilpotentPrimitiveMatGroups( <n> , <p> , <l> )'.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Further examples of nilpotent matrix groups}

In this section we describe various functions designed to produce
interesting examples of nilpotent matrix groups.

\>  MaximalAbsolutelyIrreducibleNilpotentMatGroup( <n> , <p> , <l>) F

constructs the unique (up to conjugacy) maximal absolutely
irreducible nilpotent subgroup of $GL(n,p^l)$ if such a group
exists. Note that such a group exists if and only if each prime
divisor of $n$ divides $p^l-1$. Otherwise the function returns
`fail'.

\> MonomialNilpotentMatGroup( <n> ) F

constructs an example of a finite nilpotent monomial subgroup of $GL(n,\Q)$.

\> ReducibleNilpotentMatGroup( <m>, <k>, [<p>, <l>] ) F

constructs an example of a reducible but not completely reducible
nilpotent subgroup of $GL(mk, \F)$, where $\F = \Q$ if there are
two arguments given and $\F = GF(p^l)$ if there are four arguments
given.