SSL chap3_mj.html Interaktion und
PortierbarkeitHTML

products/Sources/formale Sprachen/GAP/pkg/laguna/doc/chap3_mj.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>
<script type="text/javascript"
 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<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_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_mj.html">[Next Chapter]</a> </div>

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

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

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

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

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

</div>
<div class="ContSect"> <a href="chap3_mj.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 \(\alpha_g\) are zero. The group algebra \(FG\) is an \(F\)-algebra with the obvious operations. Clearly, \(\dim FG=|G|\).

The augmentation homomorphism \( \chi : FG \rightarrow 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 \(\chi\) is indeed a homomorphism onto \(F\). The kernel of \(\chi\) 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 \(\chi(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^* \times 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_mj.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 \(\chi(u)\neq 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, \ldots, y_{|G|-1} \) and two types of relations: \(y_i^p=(y_{i+1})^{\alpha_{i,i+1}} \cdots (y_{|G|-1})^{\alpha_{i,|G|-1}}\) for \( 1 \leq i \leq |G|-1 \), and \( [y_j,y_i]=(y_{j+1})^{\alpha_{j,i,j+1}} \cdots (y_{|G|-1})^{\alpha_{j,i,|G|-1}} \) for \( 1 \leq i < j \leq |G|-1\), where the exponents \(\alpha_{i,k}\) and \(\alpha_{i,j,k}\) are elements of the set \(\{0,\ldots,p-1\}\). Having such a presentation, it is possible to carry out efficient computations in the finite \(p\)-group \(V\); see <a href="chapBib_mj.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\neq 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+1}\)of 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})\leq 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\geq i/p\). For all \(i\leq k\) select elements \(x_{i,1},\ldots,x_{i,l_i}\) of \(G_i\) such that \(\{x_{i,1}G_{i+1},\ldots,x_{i,l_i}G_{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},\ldots,x_{1,l_1},\ldots,x_{k,1},\ldots,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\leq \alpha_{i,j}\leq 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_mj.html#biBHB">[HB82, Theorem VIII.2.6]</a>). For \(i\leq 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 \in 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,\ldots,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,\ldots,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,\ldots,y_{|G|-1}\). We use the following elementary lemma.

Lemma. Let \(i\leq c\) and suppose that \(w \in A^i\). Assume that \(x_{s_i},x_{s_i+1}\ldots,x_{r_i}\) are the standard products with weight \(i\) and for \(s_i\leq j\leq r_i\) set \(y_j=1+x_j\). Then for all \(\alpha_{s_i},\ldots,\alpha_{r_i}\in\{0,\ldots,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,\ldots,x_{r_1}\) be the standard products of weight 1, and let \(y_1,\ldots,y_{r_1}\) be the corresponding elements in the polycyclic generating set. Then using the previous lemma, we find \(\alpha_1,\ldots,\alpha_{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})^{\alpha_{1}}\cdots (y_{r_1})^{\alpha_{r_1}}(1+w_2)\) for some \(w_2 \in A^2\). Then suppose that \(x_{s_2},x_{s_2+1},\ldots,x_{r_2}\) are the standard products of weight 2. We find \(\alpha_{s_2},\ldots,\alpha_{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})^{\alpha_{s_2}}\cdots (y_{r_2})^{\alpha_{r_2}}(1+w_3)\) for some \(w_3 \in A^3\), and so \(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)\). 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,\ldots,y_{|G|-1}\) as in Section <a href="chap3_mj.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_mj.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_mj.html#biBLR86">[LR86]</a>, <a href="chapBib_mj.html#biBPPS73">[PPS73]</a>, and <a href="chapBib_mj.html#biBRos00">[Ros00]</a>.

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap2_mj.html">[Previous Chapter]</a> <a href="chap4_mj.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

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

Messung V0.5

¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.13Angebot ¤

*Eine klare Vorstellung vom Zielzustand

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 und die Messung sind noch experimentell.

SSL chap3_mj.html Interaktion und PortierbarkeitHTML

¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.13Angebot ¤

Haftungshinweis

Bemerkung:

SSL chap3_mj.html Interaktion und
PortierbarkeitHTML