Quelle chap3.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/laguna/doc/chap3.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (LAGUNA) - Chapter 3: The basic theory behind LAGUNA</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap3" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>

<a href="chap3_mj.html">[MathJax on]</a>
<a id="X7D9FCE3A8526ACBE" name="X7D9FCE3A8526ACBE"></a>
<div class="ChapSects"><a href="chap3.html#X7D9FCE3A8526ACBE">3 The basic theory behind LAGUNA</a>
<div class="ContSect"> <a href="chap3.html#X85C2DE1486FB45FD">3.1 Notation and definitions</a>

</div>
<div class="ContSect"> <a href="chap3.html#X7E26AE6C807D7C07">3.2 p-modular group algebras</a>

</div>
<div class="ContSect"> <a href="chap3.html#X7B74767A849D921E">3.3 Polycyclic generating set for V</a>

</div>
<div class="ContSect"> <a href="chap3.html#X7DCB12F48752C17E">3.4 Computing the canonical form</a>

</div>
<div class="ContSect"> <a href="chap3.html#X873F4F068759DF5D">3.5 Computing a power commutator presentation for V</a>

</div>
<div class="ContSect"> <a href="chap3.html#X79183196837B7CC1">3.6 Verifying Lie properties of FG</a>

</div>
</div>

<h3>3 The basic theory behind LAGUNA</h3>

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

<a id="X85C2DE1486FB45FD" name="X85C2DE1486FB45FD"></a>

<h4>3.1 Notation and definitions</h4>

Let G be a group and F a field. Then the group algebra FG consists of the set of formal linear combinations of the form


\sum_{g \in G}\alpha_g g,\qquad \alpha_g \in F


where all but finitely many of the α_g are zero. The group algebra FG is an F-algebra with the obvious operations. Clearly, dim FG=|G|.

The augmentation homomorphism χ : FG → F is defined by


\chi\left(\sum_{g \in G}\alpha_g g\right)=\sum_{g \in G}\alpha_g.


It is easy to see that χ is indeed a homomorphism onto F. The kernel of χ is called the augmentation ideal of FG. The augmentation ideal is denoted A(FG), or simply A when there is no danger of confusion. It follows from the isomorphism theorems that dim A(FG)=dim FG-1=|G|-1. Another way to write the augmentation ideal is


A(FG)=\left\{\sum_{g \in G}\alpha_g g\ |\ \sum_{g \in G}\alpha_g=0\right\}.


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

<a id="X7E26AE6C807D7C07" name="X7E26AE6C807D7C07"></a>

<h4>3.2 p-modular group algebras</h4>

A group algebra FG is said to be p-modular if F is the field of characteristic p, and G is a finite p-group. A lot of information about the structure of p-modular group algebras can be found in <a href="chapBib.html#biBHB">[HB82, Chapter VIII]</a>. In a p-modular group algebra we have that an element u is a unit if and only if χ(u)≠ 0. Hence the normalised unit group V consists of all elements of FG with augmentation 1. In other words V is a coset of the augmentation ideal, namely V=1+A. This also implies that |V|=|A|=|F|^|G|-1, and so V is a finite p-group.

One of the aims of the LAGUNA package is to compute a power-commutator presentation for the normalised unit group in the case when G is a finite p-group and F is a field of p elements. Such a presentation is given by generators y_1, ..., y_|G|-1 and two types of relations: y_i^p=(y_i+1)^α_i,i+1} ⋯ (y_|G|-1)^α_i,|G|-1} for 1 ≤ i ≤ |G|-1, and [y_j,y_i]=(y_j+1)^α_j,i,j+1} ⋯ (y_|G|-1)^α_j,i,|G|-1} for 1 ≤ i < j ≤ |G|-1, where the exponents α_i,k and α_i,j,k are elements of the set {0,...,p-1}. Having such a presentation, it is possible to carry out efficient computations in the finite p-group V; see <a href="chapBib.html#biBSims">[Sim94, Chapter 9]</a>.

<a id="X7B74767A849D921E" name="X7B74767A849D921E"></a>

<h4>3.3 Polycyclic generating set for V</h4>

Let G be a finite p-group and F the field of p elements. Our aim is to construct a power-commutator presentation for V=V(FG). We noted earlier that V=1+A, where A is the augmentation ideal. We use this piece of information and construct a polycyclic generating set for V using a suitable basis for A. Before constructing this generating set, we note that A is a nilpotent ideal in FG. In other words there is some c such that A^c≠ 0 but A^c+1=0. Hence we can consider the following series of ideals in A:


A\rhd A^2\rhd\cdots\rhd A^{c}\rhd A^{c+1}=0.


It is clear that a quotient A^i/A^i+1of this chain has trivial multiplication, that is, such a quotient is a nil-ring. The chain A^i gives rise to a series of normal subgroups in V:


V=1+A\rhd 1+A^2\rhd\cdots\rhd 1+A^c\rhd 1+A^{c+1}=1.


It is easy to see that the chain 1+A^i is central, that is, (1+A^i)/(1+A^i+1)≤ Z((1+A)/(1+A^i+1)).

Now we show how to compute a basis for A^i that gives a polycyclic generating set for 1+A^i. Let


G=G_1 \rhd G_2\rhd\cdots\rhd G_{k}\rhd G_{k+1}=1


be the Jennings series of G. That is, G_i+1=[G_i,G]G_j^p where j is the smallest non-negative integer such that j≥ i/p. For all i≤ k select elements x_i,1,...,x_i,l_i of G_i such that {x_i,1G_i+1,...,x_i,l_iG_i+1} is a minimal generating set for the elementary abelian group G_i/G_i+1. For the Jennings series it may happen that G_i=G_i+1 for some i. In this case we choose an empty generating set for the quotient G_i/G_i+1 and l_i=0. Then the set x_1,1,...,x_1,l_1,...,x_k,1,...,x_k,l_k is said to be a dimension basis for G. The weight of a dimension basis element x_i,j is i.

A non-empty product


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


where 0≤ α_i,j≤ p-1 is said to be standard. Clearly, a standard product is an element of the augmentation ideal A. The weight of the standard product u is


\sum_{i=1}^k i(\alpha_{i,1}+\cdots+\alpha_{i,l_i}).


The total number of standard products is |G|-1 .

Lemma (<a href="chapBib.html#biBHB">[HB82, Theorem VIII.2.6]</a>). For i≤ c, the set S_i of standard products of weight at least i forms a basis for A^i. Moreover, the set 1+S_i={1+s | s ∈ S_i} is a polycyclic generating set for 1+A^i. In particular 1+S_1 is a polycyclic generating set for V.

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

Let x_1,...,x_{|G|-1 denote the standard products where we choose the indices so that the weight of x_i is not larger than the weight of x_i+1 for all i, and set y_i=1+x_i. Then every element v of V can be uniquely written in the form


v=y_1^{\alpha_1}\cdots (y_{|G|-1})^{\alpha_{|G|-1}}, \quad
\alpha_1,\ldots,\alpha_{|G|-1} \in \{0,\ldots,p-1\}.


This expression is called the canonical form of v. We note that by adding a generator of F^* to the set y_1,...,y_|G|-1| we can obtain a polycyclic generating set for the unit group U.

<a id="X7DCB12F48752C17E" name="X7DCB12F48752C17E"></a>

<h4>3.4 Computing the canonical form</h4>

We show how to compute the canonical form of a normalised unit with respect to the polycyclic generating set y_1,...,y_|G|-1. We use the following elementary lemma.

Lemma. Let i≤ c and suppose that w ∈ A^i. Assume that x_s_i,x_s_i+1...,x_r_i are the standard products with weight i and for s_i≤ j≤ r_i set y_j=1+x_j. Then for all α_s_i,...,α_r_i∈{0,...,p-1} we have that


w\equiv \alpha_{s_i}x_{s_i}+\cdots+\alpha_{r_i}x_{r_i}\quad \bmod \quad A^{i+1}


if an only if


1+w\equiv (y_{s_i})^{\alpha_{s_i}}\cdots (y_{r_i})^{\alpha_{r_i}}\quad \bmod
\quad 1+A^{i+1}.


Suppose that w is an element of the augmentation ideal A and 1+w is a normalised unit. Let x_1,...,x_r_1 be the standard products of weight 1, and let y_1,...,y_r_1 be the corresponding elements in the polycyclic generating set. Then using the previous lemma, we find α_1,...,α_r_1 such that


w\equiv \alpha_{1}x_{1}+\cdots+\alpha_{r_1}x_{r_1}\quad \bmod \quad A^{2},


and so


1+w\equiv (y_{1})^{\alpha_{1}}\cdots (y_{r_1})^{\alpha_{r_1}}\quad \bmod
\quad 1+A^{2}.


Now we have that 1+w=(y_1)^α_1}⋯ (y_r_1)^α_r_1}(1+w_2) for some w_2 ∈ A^2. Then suppose that x_s_2,x_s_2+1,...,x_r_2 are the standard products of weight 2. We find α_s_2,...,α_r_2 such that


w_2\equiv \alpha_{s_2}x_{s_2}+\cdots+\alpha_{r_2}x_{r_2}\quad \bmod \quad A^{3}.


Then the lemma above implies that


1+w_2\equiv (y_{s_2})^{\alpha_{s_2}}\cdots (y_{r_2})^{\alpha_{r_2}}\quad \bmod
\quad 1+A^{3}.


Thus 1+w_2=(y_s_2)^α_s_2}⋯ (y_r_2)^α_r_2}(1+w_3) for some w_3 ∈ A^3, and so 1+w=(y_1)^α_1}⋯ (y_r_1)^α_r_1}(y_s_2)^α_s_2}⋯ (y_r_2)^α_r_2}(1+w_3). We repeat this process, and after c steps we obtain the canonical form for the element 1+w.

<a id="X873F4F068759DF5D" name="X873F4F068759DF5D"></a>

<h4>3.5 Computing a power commutator presentation for V</h4>

Using the procedure in the previous section, it is easy to compute a power commutator presentation for the normalized unit group V of a p-modular group algebra over the field of p elements. First we compute the polycyclic generating sequence y_1,...,y_|G|-1 as in Section <a href="chap3.html#X7B74767A849D921E">3.3</a>. Then for each y_i and for each y_j, y_i such that i<j we compute the canonical form for y_i^p and [y_j,y_i] as described in Section <a href="chap3.html#X7DCB12F48752C17E">3.4</a>.

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

<a id="X79183196837B7CC1" name="X79183196837B7CC1"></a>

<h4>3.6 Verifying Lie properties of FG</h4>

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

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality100%

¤ Dauer der Verarbeitung: 0.18 Sekunden ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.