Quelle chap1_mj.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/idrel/doc/chap1_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 (IdRel) - Chapter 1: Introduction</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="chap1" 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="chap5_mj.html">5</a> <a href="chap6_mj.html">6</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="chap0_mj.html">[Previous Chapter]</a> <a href="chap2_mj.html">[Next Chapter]</a> </div>

<a href="chap1.html">[MathJax off]</a>
<a id="X7DFB63A97E67C0A1" name="X7DFB63A97E67C0A1"></a>
<div class="ChapSects"><a href="chap1_mj.html#X7DFB63A97E67C0A1">1 Introduction</a>
<div class="ContSect"> <a href="chap1_mj.html#X80F39D77788BD099">1.1 An illustrative example</a>

</div>
</div>

<h3>1 Introduction</h3>

This manual describes the IdRel package for GAP 4.7 for computing the identities among relators of a group presentation using rewriting, logged rewriting, monoid polynomials, module polynomials and \(Y\)-sequences.

The theoretical background for these computations is contained in Brown and Huebschumann <a href="chapBib_mj.html#biBBrHu">[BH82]</a>, Brown and Razak Salleh <a href="chapBib_mj.html#biBBrSa">[BRS99]</a> and is surveyed in the first author's thesis [Hey99].

IdRel is primarily designed for the computation of a minimal set of generators for the module of identities among relators. It also contains functions which compute logged rewrite systems for group presentations (and complete them where possible); functions for operations involving elements of monoid rings; and functions for operations with elements of right modules over monoid rings. The \(Y\)-sequences are used as a rewriting way of representing elements of a free crossed module (products of conjugates of group relators and inverse relators). The package is written entirely in GAP4, and requires no compilation.

The package is loaded into GAP with the <code class="code">LoadPackage</code> command, and on-line help is available in the usual way.

<div class="example"><pre>

gap> LoadPackage( "idrel" ); 
gap> ?idrel

</pre></div>

A pdf version of the IdRel manual is available in the <code class="file">doc</code> directory of the home directory of IdRel. The information parameter <code class="code">InfoIdRel</code> has default value <code class="code">0</code>. When raised to a higher value, additional information is printed out. IdRel was originally developed in 1999 using GAP3, partially supported by a University of Wales Research Assistantship for the first author, Anne Heyworth.

If you use IdRel to solve a problem then please send a short email to the second author, to whom bug reports, suggestions and other comments should also be sent. You may reference the package by mentioning <a href="chapBib_mj.html#biBHeWe1">[HW03]</a> and <a href="chapBib_mj.html#biBanne-thesis">[Hey99]</a>.

The package may be obtained as a compressed tar file <code class="file">idrel-version.number.tar.gz</code> by ftp from one of the following sites:

<ul>
<li>the IdRel GitHub site: <a href="https://github.com/gap-packages.github.io/idrel/">https://github.com/gap-packages.github.io/idrel/</a>.

</li>
<li>any GAP archive, e.g. <a href="https://www.gap-system.org/Packages/packages.html">https://www.gap-system.org/Packages/packages.html</a>;

</li>
</ul>
The package also has a GitHub repository at: <a href="https://github.com/gap-packages/idrel/">https://github.com/gap-packages/idrel/</a> where issues can be raised.

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

<h4>1.1 An illustrative example</h4>

A typical input for IdRel is an fp-group presentation. This requires a free group <code class="code">F</code> on a set of generators and a set of relators <code class="code">R</code> (words in the free group). The module of identities among relators for this presentation has as its elements the Peiffer equivalence classes of all products of conjugates of relators which represent the identity in the free group.

In this package the identities among relators are represented by Y-sequences, which are lists \([[r_1, u_1],\ldots,[r_k,u_k]]\) where \(r_1,\ldots,r_k\) are the group relators or their inverses, and \(u_1,\ldots,u_k\) are words in the free group <code class="code">F</code>. A Y-sequence is evaluated in <code class="code">F</code> as the product \((u_1^{-1}r_1u_1)\ldots(u_k^{-1}r_ku_k)\) and is an identity Y-sequence if it evaluates to the identity in <code class="code">F</code>. An identity Y-sequence represents an identity among the relators of the group presentation. The main function of the package is to produce a set of Y-sequences which generate the module of identites among relators, and further, that this set be minimal in the sense that every element in it is needed to generate the module.

Before starting on the main example, we consider a simpler example illustrating the use of IdRel. All the functions used are described in detail in this manual. We compute a reduced set of identities among relators for the presentation of the symmetric group <code class="code">s3 = F/[f^3,g^2,(fg)^2]</code>. In the listings below, <code class="code">s3_Ri</code> is the <code class="code">i</code>-th relator for <code class="code">s3</code>, and <code class="code">f1,f2</code> are the generators \(f,g\) of \(F\).

<div class="example"><pre>

gap> F := FreeGroup( 2 );; 
gap> f := F.1;; g := F.2;; 
gap> rels3 := [ f^3, g^2, f*g*f*g ]; 
[ f1^3, f2^2, (f1*f2)^2 ]
gap> s3 := F/rels3; 
<fp group on the generators [ f1, f2 ]>
gap> SetName( s3, "s3" );; 
gap> IdentitiesAmongRelators( s3 );
[ [ [ -1, <identity ...> ], [ 1, s3_M1 ] ],
 [ [ -2, <identity ...> ], [ 2, s3_M2 ] ],
 [ [ -3, <identity ...> ], [ 3, s3_M1*s3_M2 ] ],
 [ [ 1, <identity ...> ], [ -3, s3_M1 ], [ 2, s3_M3*s3_M4 ], [ 1, s3_M4 ],
 [ -3, <identity ...> ], [ 2, s3_M3*s3_M4*s3_M3 ], [ 2, s3_M3 ],
 [ -3, s3_M3 ] ],
 [ [ 1, <identity ...> ], [ -3, s3_M2 ], [ 2, s3_M3*s3_M4*s3_M3*s3_M2 ],
 [ 2, s3_M3*s3_M2 ], [ 1, s3_M2 ], [ -3, <identity ...> ], [ 2, s3_M3 ],
 [ -3, s3_M3 ] ] ]

</pre></div>

If we write \(\rho=f^3\), \(\sigma=g^2\), \(\tau=(fg)^2\) then the first identity becomes \(\rho^{-1} \rho^{f}\). Similarly, the second and third identities are the root identities \(\sigma^{-1} \sigma^{g}\) and \(\tau^{-1} \tau^{fg}\). The fourth identity, which is not a root identity, is obtained by walking around the Schreier diagram of the presentation, a somewhat truncated triangular prism. Taking the appropriate conjugate of each face in turn, we get:

\[
\rho\ (\tau^{-1})^f\ \sigma^{f^{-1}g^{-1}}\ \rho^{g^{-1}}\ (\tau^{-1})\
\sigma^{f^{-1}g^{-1}f^{-1}}\ \sigma^{f^{-1}}\ (\tau^{-1})^{f^{-1}}\, .
\]

The fifth identity is equivalent to the fourth, as we shall show in section <a href="chap6_mj.html#X79EE179E7AD81F44">6.2</a>.

In order to form the module of identities for <code class="code">s3</code> the identities are transformed into module polynomials. The first is \(y_1 = \rho(f-1)\). The second and third are \(y_2 = \sigma(g-1)\) and \(y_3 = \tau(fg-1)\), while the fourth is \(\rho(1+g^{-1}f) + \sigma(1+f^{-1}g^{-1}+f^{-1}g^{-1}f) - \tau(1++f+f^2)\). Note that, in the fourth polynomial, the conjugators are converted to their normal forms in <code class="code">s3</code>, namely \(f^2=f^{-1},\ f^{-1}g^{-1}f=fg,\ g^{-1}f=gf\) and \(fg^{-1}f=g\). Generators for this module are returned by the operation <code class="code">IdentityYSequences</code>.

<div class="example"><pre>

gap> idyseq3 := IdentityYSequences( s3 ); 
[ ( s3_Y1*( -s3_M1), s3_R1*( s3_M1 - <identity ...>) ),
 ( s3_Y2*( <identity ...>), s3_R2*( s3_M2 - <identity ...>) ),
 ( s3_Y3*( s3_M1), s3_R3*( s3_M2 - s3_M1) ),
 ( s3_Y9*( -<identity ...>), s3_R1*( -s3_M2*s3_M1 - s3_M1) + s3_R2*( -s3_M1*s\
3_M2 - s3_M1 - <identity ...>) + s3_R3*( s3_M3 + s3_M2 + <identity ...>) ) ]

</pre></div>

Further examples are given in chapter <a href="chap6_mj.html#X78038BF07E998E21">6</a>.

An extensive revision has been released with version 2.44. This has concentrated in the area of log sequences, adding many of the functions described in sections <a href="chap6_mj.html#X79EE179E7AD81F44">6.2</a> and <a href="chap6_mj.html#X82CE16C9788F883A">6.3</a>.

Work on revising Y-sequences is needed, but must wait for later versions.

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap0_mj.html">[Previous Chapter]</a> <a href="chap2_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="chap5_mj.html">5</a> <a href="chap6_mj.html">6</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>

quality100%

¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤

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.