<!-- $Id: theory.xml,v 1.11 2005/04/19 21:32:53 alexk Exp $ -->
<Chapter Label="Theory">
<Heading>The basic theory behind &LAGUNA;</Heading>    

In this chapter we describe the theory that is behind the algorithms used by
&LAGUNA;. 

<Section Label="TheoryFirst">
<Heading>Notation and definitions</Heading>

<Index>group algebra</Index>
Let <M>G</M> be a group and <M>F</M> a field. Then the <E>group algebra</E> 
<M>FG</M> consists of the set of formal linear combinations of the form 
<Display> 
\sum_{g \in G}\alpha_g g,\qquad \alpha_g \in F
</Display>
where all but finitely many of the <M>\alpha_g</M> are zero. The group algebra
<M>FG</M> is an <M>F</M>-algebra with the obvious operations. 
Clearly, <M>\dim FG=|G|</M>.<P/>

<Index>augmentation homomorphism</Index>
<Index>augmentation ideal</Index>
The <E>augmentation homomorphism</E> <M> \chi : FG \rightarrow F</M> 
is defined by
<Display>
\chi\left(\sum_{g \in G}\alpha_g g\right)=\sum_{g \in G}\alpha_g.
</Display>
It is easy to see that <M>\chi</M> is indeed a homomorphism onto <M>F</M>. The
kernel of <M>\chi</M> is called the <E>augmentation ideal</E> of <M>FG</M>. The
augmentation ideal is denoted <M>A(FG)</M>, or simply <M>A</M> when there is no
danger of confusion. It
follows from the isomorphism theorems that <M>\dim A(FG)=\dim
FG-1=|G|-1</M>. Another way to write the augmentation ideal is
<Display>
A(FG)=\left\{\sum_{g \in G}\alpha_g g\ |\ \sum_{g \in G}\alpha_g=0\right\}.
</Display><P/>

<Index>unit</Index>
<Index>unit group</Index>
<Index>normalised unit</Index>
<Index>normalised unit group</Index>
An invertible
element of <M>FG</M> is said to be a  <E>unit</E>. 
Clearly the elements of <M>G</M>
and the non-zero elements of <M>F</M> are units. The set of units in <M>FG</M>
is a group with respect to the  multiplication of <M>FG</M>. The <E>unit group</E>
of <M>FG</M> is denoted <M>U(FG)</M> or simply <M>U</M> when there is no risk
of confusion. A unit <M>u</M> is said to be <E>normalised</E> if
<M>\chi(u)=1</M>. The set of normalised units forms a subgroup of the unit
group, and is referred to as the <E>normalised unit group</E>. The normalised unit
group of <M>FG</M> is denoted <M>V(FG)</M>, or simply <M>V</M>. It is easy to
prove that <M>U(FG) = F^* \times V(FG)</M> where <M>F^*</M> denotes the
multiplicative group of <M>F</M>.

</Section>

<!-- ********************************************************* -->

<Section Label="TheorySecond">
<Heading><M>p</M>-modular group algebras</Heading>

<Index Key="p-modular group algebra"><M>p</M>-modular group algebra</Index>
A group algebra <M>FG</M> is said to be <M>p</M>-modular if <M>F</M> is the
field of characteristic <M>p</M>, and <M>G</M> is a finite
<M>p</M>-group. A lot of information about the structure of <M>p</M>-modular
group algebras can be found in <Cite Key="HB" Where="Chapter VIII"/>.
In a  <M>p</M>-modular group algebra we have that an element
<M>u</M> is a unit if and only if <M>\chi(u)\neq 0</M>. Hence the normalised
unit group <M>V</M> consists of all elements of <M>FG</M> with augmentation
<M>1</M>. In other words <M>V</M> is a coset of the augmentation ideal, namely
<M>V=1+A</M>. This also implies that <M>|V|=|A|=|F|^{|G|-1}</M>, and so <M>V</M>
is a finite <M>p</M>-group.
<P/>

<Index>power-commutator presentation</Index>
One of the aims of the &LAGUNA; package is to compute a power-commutator
presentation for the normalised unit group in the case when <M>G</M>
is a finite <M>p</M>-group and <M>F</M> is
a field of <M>p</M> elements. Such a presentation is given by
generators <M>y_1, \ldots, y_{|G|-1} </M> and two types of relations: 
<M>y_i^p=(y_{i+1})^{\alpha_{i,i+1}} \cdots (y_{|G|-1})^{\alpha_{i,|G|-1}}</M>
for <M> 1 \leq i \leq |G|-1 </M>, and 
<M> [y_j,y_i]=(y_{j+1})^{\alpha_{j,i,j+1}} \cdots
              (y_{|G|-1})^{\alpha_{j,i,|G|-1}} </M>
for <M> 1 \leq i&tlt;j \leq |G|-1</M>,
where the exponents <M>\alpha_{i,k}</M> and <M>\alpha_{i,j,k}</M> are
elements of the set <M>\{0,\ldots,p-1\}</M>. Having such a presentation, it 
is possible to carry out efficient computations in the finite <M>p</M>-group
<M>V</M>; see <Cite Key="Sims" Where="Chapter 9"/>.

</Section>

<!-- ********************************************************* -->

<Section Label="TheoryThird">
<Heading>Polycyclic generating set for <M>V</M></Heading>

Let <M>G</M> be a finite <M>p</M>-group and <M>F</M> the field of
<M>p</M> elements. Our aim is to construct a
power-commutator presentation for <M>V=V(FG)</M>. We noted earlier that
<M>V=1+A</M>, where <M>A</M> is the augmentation ideal. We use this piece of
information and construct a polycyclic generating set for <M>V</M> using a
suitable basis for <M>A</M>. Before constructing this generating set, we note
that <M>A</M> is a nilpotent ideal in <M>FG</M>. In other words there is some
<M>c</M> such that <M>A^c\neq 0</M> but <M>A^{c+1}=0</M>. 
Hence we can consider the following series
of ideals in <M>A</M>:
<Display>
A\rhd A^2\rhd\cdots\rhd A^{c}\rhd A^{c+1}=0.
</Display>
It is clear that a quotient <M>A^i/A^{i+1}</M>of this chain has trivial
multiplication, that is, such a quotient is a nil-ring. The chain <M>A^i</M> 
gives rise to a series of normal subgroups in <M>V</M>:
<Display>
V=1+A\rhd 1+A^2\rhd\cdots\rhd 1+A^c\rhd 1+A^{c+1}=1.
</Display>
It is easy to see that the chain <M>1+A^i</M> is central, that is,
<M>(1+A^i)/(1+A^{i+1})\leq Z((1+A)/(1+A^{i+1}))</M>. 
<P/>

<Index>Jennings series</Index>
<Index>dimension basis</Index>
<Index>weight, of dimension basis element</Index>
Now we show how to compute a basis for <M>A^i</M> that gives a polycyclic
generating set for <M>1+A^i</M>.
Let 
<Display>
G=G_1 \rhd G_2\rhd\cdots\rhd G_{k}\rhd G_{k+1}=1
</Display>
be the <E>Jennings series</E> of <M>G</M>. That is, <M>G_{i+1}=[G_i,G]G_{j^p}</M> where
<M>j</M> is the smallest non-negative integer such that <M>j\geq i/p</M>. For
all <M>i\leq k</M>  
select elements <M>x_{i,1},\ldots,x_{i,l_i}</M> of <M>G_i</M>
such that <M>\{x_{i,1}G_{i+1},\ldots,x_{i,l_i}G_{i+1}\}</M> is a minimal
generating set for the elementary abelian group <M>G_i/G_{i+1}</M>. For the
Jennings series it may happen that <M>G_i=G_{i+1}</M>  for some <M>i</M>. In
this case we choose an empty generating set for the quotient <M>G_i/G_{i+1}</M>
 and <M>l_i=0</M>.
Then the
set <M>x_{1,1},\ldots,x_{1,l_1},\ldots,x_{k,1},\ldots,x_{k,l_k}</M>  is said to
be a <E>dimension basis</E> for <M>G</M>. The <E>weight</E> of a dimension basis
element <M>x_{i,j}</M> is <M>i</M>.<P/>

<Index>standard product</Index>
A non-empty product 
<Display>
u=(x_{1,1}-1)^{\alpha_{1,1}}\cdots(x_{1,l_1}-1)^{\alpha_{1,l_1}}\cdots
(x_{k,1}-1)^{\alpha_{k,1}}\cdots(x_{k,l_k}-1)^{\alpha_{k,l_k}}
</Display>
where <M>0\leq \alpha_{i,j}\leq p-1</M> is said to be <E>standard</E>.
Clearly, a standard product is an element of the augmentation ideal
<M>A</M>. The weight of the standard product <M>u</M> is
<Display>
\sum_{i=1}^k i(\alpha_{i,1}+\cdots+\alpha_{i,l_i}).
</Display>
The total number of standard products is <M>|G|-1</M>
.


<P/>

<B>Lemma (</B><Cite Key="HB" Where="Theorem VIII.2.6"/><B>).</B> 
For <M>i\leq c</M>, the set <M>S_i</M> 
of standard products of weight at least <M>i</M>  forms a basis for
<M>A^i</M>. Moreover, the set <M>1+S_i=\{1+s\ |\ s \in S_i\}</M>  is a
polycyclic generating set for <M>1+A^i</M>. In particular <M>1+S_1</M> is a
polycyclic generating set for <M>V</M>.
<P/>

A basis for <M>A</M> consisting of the standard products is referred to as a
<E>weighted basis</E>. Note that a weighted basis is a basis for the
augmentation ideal, and not for the whole group algebra.<P/>

Let <M>x_1,\ldots,x_{{|G|}-1}</M> denote the standard products where we choose
the indices so that the weight of <M>x_i</M> is not larger than the weight of
<M>x_{i+1}</M>  for all <M>i</M>, and set <M>y_i=1+x_i</M>. Then every element
<M>v</M> of <M>V</M>  can be uniquely written in the form
<Display>
v=y_1^{\alpha_1}\cdots (y_{|G|-1})^{\alpha_{|G|-1}}, \quad
\alpha_1,\ldots,\alpha_{|G|-1} \in \{0,\ldots,p-1\}.
</Display>
This expression is called the <E>canonical form</E> of <M>v</M>.

We note that by adding a generator of <M>F^*</M> to the set
<M>y_1,\ldots,y_{|G|-1|}</M> we can obtain a polycyclic generating set for the unit group
<M>U</M>.

</Section>

<!-- ********************************************************* -->

<Section Label="TheoryFourth">
<Heading>Computing the canonical form</Heading>

We show how to compute the canonical form of
a normalised unit with respect to the polycyclic generating set
<M>y_1,\ldots,y_{|G|-1}</M>. We use the following elementary lemma.
<P/>

<B>Lemma.</B> Let <M>i\leq c</M> and suppose that
<M>w \in A^i</M>. Assume that <M>x_{s_i},x_{s_i+1}\ldots,x_{r_i}</M> are the
standard products with weight <M>i</M> and  for <M>s_i\leq j\leq r_i</M> set
<M>y_j=1+x_j</M>. Then for all
<M>\alpha_{s_i},\ldots,\alpha_{r_i}\in\{0,\ldots,p-1\}</M> we have that
<Display>
w\equiv \alpha_{s_i}x_{s_i}+\cdots+\alpha_{r_i}x_{r_i}\quad \bmod \quad A^{i+1}
</Display>
if an only if
<Display>
1+w\equiv (y_{s_i})^{\alpha_{s_i}}\cdots (y_{r_i})^{\alpha_{r_i}}\quad \bmod
\quad 1+A^{i+1}.
</Display>

<P/>

Suppose that <M>w</M> is an element of the augmentation ideal <M>A</M> and
<M>1+w</M> is a normalised unit. Let <M>x_1,\ldots,x_{r_1}</M> be the standard
products of weight 1, and let <M>y_1,\ldots,y_{r_1}</M> be the corresponding
elements in the polycyclic generating set. Then using the previous lemma, we find
<M>\alpha_1,\ldots,\alpha_{r_1}</M> such that
<Display>
w\equiv \alpha_{1}x_{1}+\cdots+\alpha_{r_1}x_{r_1}\quad \bmod \quad A^{2},
</Display>
and so 
<Display>
1+w\equiv (y_{1})^{\alpha_{1}}\cdots (y_{r_1})^{\alpha_{r_1}}\quad \bmod
\quad 1+A^{2}.
</Display>
Now we have that <M>1+w=(y_{1})^{\alpha_{1}}\cdots
(y_{r_1})^{\alpha_{r_1}}(1+w_2)</M> for some <M>w_2 \in A^2</M>. Then suppose
that  <M>x_{s_2},x_{s_2+1},\ldots,x_{r_2}</M> are the standard products of
weight 2. We find
<M>\alpha_{s_2},\ldots,\alpha_{r_2}</M> such that
<Display>
w_2\equiv \alpha_{s_2}x_{s_2}+\cdots+\alpha_{r_2}x_{r_2}\quad \bmod \quad A^{3}.
</Display>
Then the lemma above implies that
<Display>
1+w_2\equiv (y_{s_2})^{\alpha_{s_2}}\cdots (y_{r_2})^{\alpha_{r_2}}\quad \bmod
\quad 1+A^{3}.
</Display>
Thus <M>1+w_2=(y_{s_2})^{\alpha_{s_2}}\cdots (y_{r_2})^{\alpha_{r_2}}(1+w_3)</M> for
some <M>w_3 \in A^3</M>, and so <M>1+w=(y_{1})^{\alpha_{1}}\cdots
(y_{r_1})^{\alpha_{r_1}}(y_{s_2})^{\alpha_{s_2}}\cdots
(y_{r_2})^{\alpha_{r_2}}(1+w_3)</M>. We repeat this process, and after <M>c</M>
steps we obtain the canonical form for the element <M>1+w</M>.

</Section>

<!-- ********************************************************* -->

<Section Label="TheoryFifth">
<Heading>Computing a power commutator presentation for <M>V</M></Heading>

Using the procedure in the previous section, it is easy to compute a power
commutator presentation for the normalized unit group <M>V</M> of a
<M>p</M>-modular group algebra over the field of <M>p</M> elements. 
First we compute the polycyclic generating
sequence <M>y_1,\ldots,y_{|G|-1}</M> as in Section 
<Ref Sect="TheoryThird"/>. Then for
each <M>y_i</M> and for each <M>y_j,\ y_i</M> such that <M>i&tlt;j</M>
we compute the canonical form for <M>y_i^p</M> and <M>[y_j,y_i]</M>
as described in Section <Ref Sect="TheoryFourth"/>. <P/>

Once a power-commutator 
presentation for <M>V</M> is constructed, it is easy to
obtain a polycyclic presentation for the unit group <M>U</M> by adding an extra
central generator <M>y</M> 
corresponding to a generator of the cyclic group <M>F^*</M> and enforcing that
<M>y^{p-1}=1</M>.
</Section>

<!-- ********************************************************* -->

<Section Label="TheorySixth">
<Heading>Verifying Lie properties of <M>FG</M></Heading>

If <M>FG</M> is a group algebra then  one can consider the Lie bracket
operation defined by <M>[a,b]=ab-ba</M>. Then it is well-known that
<M>FG</M> with respect to the scalar multiplication, the addition, and
the bracket operation becomes a Lie algebra over <M>F</M>. This Lie
algebra is also denoted <M>FG</M>. Some Lie properties of such Lie
algebras can be computed very efficiently. In particular, it can be verified whether the Lie 
algebra <M>FG</M> is nilpotent, soluble, metabelian,
centre-by-metabelian.  Fast algorithms that achieve these goals are
described in <Cite Key="LR86"/>,  <Cite Key="PPS73"/>, and <Cite
Key="Ros00"/>.

</Section>
</Chapter>