% generated by GAPDoc2LaTeX from XML source (Frank Luebeck)
\documentclass[a4paper,11pt]{report}
\usepackage{a4wide}
\sloppy
\pagestyle{myheadings}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage{makeidx}
\makeindex
\usepackage{color}
\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%% strange name because of pdflatex bug:
\definecolor{Chapter }{rgb}{0.0,0.0,1.0}
\usepackage{fancyvrb}
\usepackage{pslatex}
\usepackage[pdftex=true,
a4paper=true,bookmarks=false,pdftitle={Written with GAPDoc},
pdfcreator={LaTeX with hyperref package / GAPDoc},
colorlinks=true,backref=page,breaklinks=true,linkcolor=RoyalBlue,
citecolor=RoyalGreen,filecolor=RoyalRed,
urlcolor=RoyalRed,pagecolor=RoyalBlue]{hyperref}
% write page numbers to a .pnr log file for online help
\newwrite\pagenrlog
\immediate\openout\pagenrlog =\jobname.pnr
\immediate\write\pagenrlog{PAGENRS := [}
\newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}}
%% were never documented, give conflicts with some additional packages
\newcommand{\GAP}{\textsf{GAP}}
\begin{document}
\logpage{[ 0, 0, 0 ]}
\begin{titlepage}
\begin{center}{\Huge \textbf{\textsf{IdRel}\mbox{}}}\\[1cm]
\hypersetup{pdftitle=\textsf{IdRel}}
\markright{\scriptsize \mbox{}\hfill \textsf{IdRel} \hfill\mbox{}}
{\Large \textbf{A package for Identities among Relators\mbox{}}}\\[1cm]
{Version 2.05\mbox{}}\\[1cm]
{November 2008\mbox{}}\\[1cm]
\mbox{}\\[2cm]
{\large \textbf{ Anne Heyworth \mbox{}}}\\
{\large \textbf{ Chris Wensley \mbox{}}}\\
\hypersetup{pdfauthor= Anne Heyworth ; Chris Wensley }
\end{center}\vfill
\mbox{}\\
{\mbox{}\\
\small \noindent \textbf{ Anne Heyworth } --- Email: \href{mailto://anne.heyworth@googlemail.com} {\texttt{anne.heyworth@googlemail.com}}}\\
{\mbox{}\\
\small \noindent \textbf{ Chris Wensley } --- Email: \href{mailto://c.d.wensley@bangor.ac.uk} {\texttt{c.d.wensley@bangor.ac.uk}}\\
--- Homepage: \href{http://www.bangor.ac.uk/~mas023/} {\texttt{http://www.bangor.ac.uk/\texttt{\symbol{126}}mas023/}}\\
--- Address: \begin{minipage}[t]{8cm}\noindent
School of Computer Science, Bangor University,\\
Dean Street, Bangor, Gwynedd, LL57 1UT, U.K. \end{minipage}
}\\
\end{titlepage}
\newpage\setcounter{page}{2}
{\small
\section*{Abstract}
\logpage{[ 0, 0, 1 ]}
The \textsf{IdRel} package was originally implemented in 1999, using the \textsf{GAP} 3 language, when the first author was studying for a Ph.D. in Bangor.
This package is designed to compute a minimal set of generators for the module
of the identities among relators of a group presentation. It does this using
\begin{itemize}
\item rewriting and logged rewriting: a self-contained implementation of the
Knuth-Bendix process using the monoid presentation associated to the group
presentation;
\item monoid polynomials: an implementation of the monoid ring;
\item module polynomials: an implementation of the right module over this monoid
generated by the relators.
\item Y-sequences: used as a \emph{rewriting} way of representing elements of a free crossed module (products of conjugates
of group relators and inverse relators).
\end{itemize}
Bug reports, suggestions and comments are, of course, welcome. Please contact
the second author at \href{mailto://c.d.wensley@bangor.ac.uk} {\texttt{c.d.wensley@bangor.ac.uk}}. \mbox{}}\\[1cm]
{\small
\section*{Copyright}
\logpage{[ 0, 0, 2 ]}
{\copyright} 2005-2008 Anne Heyworth and Chris Wensley
\mbox{}}\\[1cm]
{\small
\section*{Acknowledgements}
\logpage{[ 0, 0, 3 ]}
This \textsf{idrel} package is released under the GNU General Public License (GPL). This file is
part of \textsf{idrel}, though as documentation it is released under the GNU Free Documentation
License (see \href{http://www.gnu.org/licenses/licenses.html#FDL} {\texttt{http://www.gnu.org/licenses/licenses.html\#FDL}}).
\textsf{idrel} is free software; you can redistribute it and/or modify it under the terms of
the GNU General Public License as published by the Free Software Foundation;
either version 2 of the License, or (at your option) any later version.
\textsf{idrel} is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with \textsf{idrel}; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite
330, Boston, MA 02111-1307 USA.
For more details, see \href{http://www.fsf.org/licenses/gpl.html} {\texttt{http://www.fsf.org/licenses/gpl.html}}.
This documentation was prepared with the \textsf{GAPDoc} package of Frank L\texttt{\symbol{92}}"ubeck and Max
Neunh\texttt{\symbol{92}}"offer. \mbox{}}\\[1cm]
\newpage
\def\contentsname{Contents\logpage{[ 0, 0, 4 ]}}
\tableofcontents
\newpage
\chapter{\textcolor{Chapter }{Introduction}}\label{intro}
\logpage{[ 1, 0, 0 ]}
\hyperdef{L}{X7DFB63A97E67C0A1}{}
{
This manual describes the \textsf{IdRel} (version 2.05) \textsf{GAP} package 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 \cite{BrHu}, Brown and Razak Salleh \cite{BrSa} and is surveyed in \cite{anne-thesis}.
\textsf{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 \emph{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 \textsf{GAP}4, and requires no compilation.
The package is loaded into \textsf{GAP} with the \texttt{LoadPackage} command, and on-line help is available in the usual way.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> LoadPackage( "idrel" );
gap> ?idrel
\end{Verbatim}
A pdf version of the \textsf{IdRel} manual is available in the \texttt{doc} directory of the home directory of \textsf{IdRel}. The information parameter \texttt{InfoIdRel} has default value \texttt{0}. When raised to a higher value, additional information is printed out. \textsf{IdRel} was originally developed in 1999 using \textsf{GAP}3, partially supported by a University of Wales Research Assistantship for the
first author, Anne Heyworth.
If you use \textsf{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 \cite{HeWe1} and \cite{anne-thesis}.
The new version (2.05) was required in November 2008 because the Mathematics
website at Bangor moved to a different network, and the \textsf{IdRel} pages moved with it. }
\chapter{\textcolor{Chapter }{Rewriting Systems}}\label{chap-rws}
\logpage{[ 2, 0, 0 ]}
\hyperdef{L}{X7CA8FCFD81AA1890}{}
{
This chapter describes functions to construct rewriting systems for finitely
presented groups which store rewriting information. The main example used is a
presentation of the quaternion group \texttt{q8} with generators $a,b$ and relators $[a^4, b^4, abab^{-1}, a^2b^2]$.
\section{\textcolor{Chapter }{Identity Y-sequences}}\logpage{[ 2, 1, 0 ]}
\hyperdef{L}{X7C9AE9BC78CCBFAA}{}
{
A typical input for \textsf{IdRel} is an fp-group presentation. This requires a free group \texttt{F} on a set of generators and a set of relators \texttt{R} (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 \texttt{F}. A Y-sequence is evaluated in \texttt{F} 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 \texttt{F}. 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 \textsf{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 \texttt{s3} with generators $a,b$ and relators $[a^3 , b^2, (ab)^2]$. In the listing below, \texttt{s3{\textunderscore}M1} is the first monoid generator for \texttt{s3}, \texttt{s3{\textunderscore}R2} is the second relator, while \texttt{s3{\textunderscore}Y4} is the fourth Y-sequence for \texttt{s3}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> F := FreeGroup( 2 );;
gap> a := F.l;; b:= F.2;;
gap> rels3 := [ a^3 , b^2, a*b*a*b];
[ fl^3 , f2^2, fl*f2*fl*f2]
gap> s3 := F/rels3;
<fp group on the generators [ fl, f2 ]>
gap> SetName( s3, "s3" );
gap> idy3 := IdentityYSequences( s3 );;
gap> Length( idy3 );
18
gap> Y4 := idy3[4];
[ [ s3_R1^-1, f1^-1 ], [ s3_R1, <identity ...> ] ]
gap> Y6 := idy3[6];
[ [ s3_R3^-1, f1^-1 ], [ s3_R1, <identity ...> ], [ s3_R3^-1, f1 ],
[ s3_R2, f1^-1*f2^-1 ], [ s3_R1, f2^-1 ], [ s3_R3^-1, f1*f2^-1 ],
[ s3_R2, <identity ...> ], [ s3_R2, f1^-1 ] ]
gap> Y7 := idy3[7];
[ [ s3_R3^-1, f1*f2^-1 ], [ s3_R2, <identity ...> ], [ s3_R3, <identity ...> ],
[ s3_R2^-1, <identity ...> ] ]
gap> Y8 := idy3[8];
[ [ s3_R2^-1, f2^-1 ], [ s3_R2, <identity ...> ] ]
\end{Verbatim}
Of the $18$ Y-sequences formed, $6$ are empty, and \texttt{Y4} is the \emph{root identity} \texttt{((a\texttt{\symbol{94}}3)\texttt{\symbol{94}}-1)\texttt{\symbol{94}}(a\texttt{\symbol{94}}-1).(a\texttt{\symbol{94}}3)}. If we write $r=a^3, s=b^2, t=(ab)^2$ then \texttt{Y4} is \texttt{(r\texttt{\symbol{94}}-1)\texttt{\symbol{94}}(a\texttt{\symbol{94}}-1).r}. Similarly, \texttt{Y8} is the second root identity \texttt{(s\texttt{\symbol{94}}-1)\texttt{\symbol{94}}(b\texttt{\symbol{94}}-1).s}, while \texttt{Y7} is the third root identity \texttt{(t\texttt{\symbol{94}}-1)\texttt{\symbol{94}}(ab\texttt{\symbol{94}}-1).t}. The identity \texttt{Y6}, which is not a root identity, is obtained by walking around the Schreier
diagram of the presentation, which is a somewhat truncated triangular prism,
taking the appropriate conjugate of each face in turn: \texttt{ Y6=(t\texttt{\symbol{94}}-1)\texttt{\symbol{94}}(a\texttt{\symbol{94}}-1).r.(t\texttt{\symbol{94}}-1)\texttt{\symbol{94}}a.s\texttt{\symbol{94}}(a\texttt{\symbol{94}}-1b\texttt{\symbol{94}}-1).r\texttt{\symbol{94}}(b\texttt{\symbol{94}}-1).(t\texttt{\symbol{94}}-1)\texttt{\symbol{94}}(ab\texttt{\symbol{94}}-1).s.s\texttt{\symbol{94}}(a\texttt{\symbol{94}}-1) }. These four identities generate the module of identities for \texttt{s3}.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> idrels3 := IdentitiesAmongRelators( s3 );;
gap> Display( idrels3[1] );
[ ( s3_Y4*( s3_M2*s3_M1), s3_R1*( s3_M1 - <identity ...>) ),
( s3_Y8*( s3_M2*s3_M1), s3_R2*( s3_M2 - <identity ...>) ),
( s3_Y7*( s3_M2*s3_M1), s3_R3*( s3_M2 - s3_M1) ),
( s3_Y6*( -s3_M2*s3_M1), s3_R1*( -s3_M2*s3_M1 - s3_M1) + s3_R2*( -s3_M1*s3_M\
2 - s3_M1 - <identity ...>) + s3_R3*( s3_M3 + s3_M2 + <identity ...>) )
]
\end{Verbatim}
}
\section{\textcolor{Chapter }{Monoid Presentations of FpGroups}}\logpage{[ 2, 2, 0 ]}
\hyperdef{L}{X7875619E84157FC1}{}
{
\subsection{\textcolor{Chapter }{FreeRelatorGroup}}
\logpage{[ 2, 2, 1 ]}\nobreak
\hyperdef{L}{X868422B878B0C380}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FreeRelatorGroup({\slshape grp})\index{FreeRelatorGroup@\texttt{FreeRelatorGroup}}
\label{FreeRelatorGroup}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FreeRelatorHomomorphism({\slshape grp})\index{FreeRelatorHomomorphism@\texttt{FreeRelatorHomomorphism}}
\label{FreeRelatorHomomorphism}
}\hfill{\scriptsize (attribute)}}\\
The function \texttt{FreeRelatorGroup} returns a free group on the set of relators of the given fp-group \texttt{G}. If \texttt{HasName(G)} is \texttt{true} then a name is automatically assigned to the free group.
The function \texttt{FreeRelatorHomomorphism} returns the group homomorphism from the free group on the relators to the free
group on the generators of \texttt{G}, mapping each generator to the corresponding word.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> F := FreeGroup( 2 );;
gap> a := F.1;; b:= F.2;;
gap> rels := [ a^4, b^4, a*b*a*b^-1, a^2*b^2];;
gap> q8 := F/rels;;
gap> SetName( q8, "q8" );
gap> frq8 := FreeRelatorGroup( q8 );
q8_R
gap> GeneratorsOfGroup( frq8 );
[ q8_R1, q8_R2, q8_R3, q8_R4]
gap> frhomq8 := FreeRelatorHomomorphism( q8 );
[ q8_R1, q8_R2, q8_R3, q8_R4] -> [ f1^4, f2^4, f1*f2*f1*f2^-1, f1^2*f2^2]
\end{Verbatim}
\subsection{\textcolor{Chapter }{MonoidPresentationFpGroup}}
\logpage{[ 2, 2, 2 ]}\nobreak
\hyperdef{L}{X7CBE13927DFF4446}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MonoidPresentationFpGroup({\slshape grp})\index{MonoidPresentationFpGroup@\texttt{MonoidPresentationFpGroup}}
\label{MonoidPresentationFpGroup}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FreeGroupOfPresentation({\slshape mon})\index{FreeGroupOfPresentation@\texttt{FreeGroupOfPresentation}}
\label{FreeGroupOfPresentation}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GroupRelatorsOfPresentation({\slshape mon})\index{GroupRelatorsOfPresentation@\texttt{GroupRelatorsOfPresentation}}
\label{GroupRelatorsOfPresentation}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InverseRelatorsOfPresentation({\slshape mon})\index{InverseRelatorsOfPresentation@\texttt{InverseRelatorsOfPresentation}}
\label{InverseRelatorsOfPresentation}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{HomomorphismOfPresentation({\slshape mon})\index{HomomorphismOfPresentation@\texttt{HomomorphismOfPresentation}}
\label{HomomorphismOfPresentation}
}\hfill{\scriptsize (attribute)}}\\
A monoid presentation for a finitely presented group \texttt{G} has two monoid generators $g^+,g^-$ for each group generator $g$. The relators of the monoid presentation comprise the group relators, and
relators $g^+g^-$ specifying the inverses. The function \texttt{MonoidPresentationFpGroup} returns the monoid presentation derived in this way from an fp-presentation.
(Note: this function should always be followed by a double semicolon -- \texttt{MonoidPresentationFpGroup(G);;} -- because an error occurs in attempting to display the results on the screen:
the \texttt{ElementsFamily} needs to be fixed.)
The function \texttt{FreeGroupOfPresentation} returns the free group on the monoid generators.
The function \texttt{GroupRelatorsOfPresentation} returns those relators of the monoid which correspond to the relators of the
group. All negative powers in the group relators are converted to positive
powers of the $g^-$.
The function \texttt{InverseRelatorsOfPresentation} returns relators which specify the inverse pairs of the monoid generators.
The function \texttt{HomomorphismOfPresentation} returns the homomorphism from the free group of the monoid presentation to the
free group of the group presentation.
In the example below, the four monoid generators $a^+, b^+, a^-, b^-$ are named \texttt{q8\texttt{\symbol{92}}{\textunderscore}M1,
q8\texttt{\symbol{92}}{\textunderscore}M2,
q8\texttt{\symbol{92}}{\textunderscore}M3,
q8\texttt{\symbol{92}}{\textunderscore}M4}.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> mon := MonoidPresentationFpgroup( q8 );;
gap> fgmon := FreeGroupOfPresentation( mon);
<free group on the generators [ q8_Ml, q8_M2, q8_M3, q8_M4]>
gap> genfgmon := GeneratorsOfGroup( fgmon);
[ q8_Ml, q8_M2, q8_M3, q8_M4]
gap> gprels := GroupRelatorsOfPresentation( mon );
[ q8_Ml^4, q8_M2^4, q8_Ml*q8_M2*q8_Ml*q8_M4, q8_Ml^2*q8_M2^2]
gap> invrels := InverseRelatorsOfPresentation( mon);
[ q8_Ml*q8_M3, q8_M2*q8_M4, q8_M3*q8_Ml, q8_M4*q8_M2]
gap> hompres := HomomorphismOfPresentation( mon );
[ q8_Ml, q8_M2, q8_M3, q8_M4] -> [ fl, f2, fl^-l, f2^-1 ]
\end{Verbatim}
}
\section{\textcolor{Chapter }{Rewriting systems for FpGroups}}\logpage{[ 2, 3, 0 ]}
\hyperdef{L}{X7A1F10597D8FC9A9}{}
{
These functions duplicate the standard Knuth Bendix functions which are
available in the \textsf{GAP} library. There are two reasons for this: (1) these functions were first
written before the standard functions were available; (2) we require logged
versions of the functions, and these are most conveniently extended versions
of the non-logged code.
\subsection{\textcolor{Chapter }{RewritingSystemFpGroup}}
\logpage{[ 2, 3, 1 ]}\nobreak
\hyperdef{L}{X858ECE3E807C7363}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RewritingSystemFpGroup({\slshape grp})\index{RewritingSystemFpGroup@\texttt{RewritingSystemFpGroup}}
\label{RewritingSystemFpGroup}
}\hfill{\scriptsize (attribute)}}\\
This function attempts to return a complete rewrite system for the group \texttt{G} obtained from the monoid presentation \texttt{mon}, with a length-lexicographical ordering on the words in \texttt{fgmon}, by applying Knuth-Bendix completion. Such a rewrite system can be obtained
for all finite groups. The rewrite rules are (partially) ordered, starting
with the inverse relators, followed by the rules which reduce the word length
the most.
In our \texttt{q8} example there are 16 rewrite rules.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> rws := RewritingSystemFpGroup( q8 );
[ [q8_Ml*q8_M3, <identity ...>], [ q8_M2*q8_M4, <identity ...> ],
[q8_M3*q8_Ml, <identity ...>], [ q8_M4*q8_M2, <identity ...> ],
[q8_M1^2*q8_M4, q8_M2], [q8_Ml^2*q8_M2, q8_M4], [ q8_Ml^3, q8_M3 ],
[ q8_M4^2, q8_Ml^2], [ q8_M4*q8_M3, q8_Ml*q8_M4],
[ q8_M4*q8_Ml, q8_Ml*q8_M2], [q8_M3*q8_M4, q8_Ml*q8_M2],
[ q8_M3^2, q8_Ml^2], [q8_M3*q8_M2, q8_Ml*q8_M4],
[ q8_M2*q8_M3, q8_Ml*q8_M2], [q8_M2^2, q8_Ml^2],
[ q8_M2*q8_Ml, q8_Ml*q8_M4] ]
\end{Verbatim}
The functions called by \texttt{RewritingSystemFpGroup} are as follows.
\subsection{\textcolor{Chapter }{OnePassReduceWord}}
\logpage{[ 2, 3, 2 ]}\nobreak
\hyperdef{L}{X83BD6C0A80D88C2C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OnePassReduceWord({\slshape word, rules})\index{OnePassReduceWord@\texttt{OnePassReduceWord}}
\label{OnePassReduceWord}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ReduceWordKB({\slshape word, rules})\index{ReduceWordKB@\texttt{ReduceWordKB}}
\label{ReduceWordKB}
}\hfill{\scriptsize (operation)}}\\
Assuming that \texttt{word} is an element of a free monoid and \texttt{rules} is a list of ordered pairs of such words, the function \texttt{OnePassReduceWord} searches the list of rules until it finds that the left-hand side of a \texttt{rule} is a \texttt{subword} of \texttt{word}, whereupon it replaces that \texttt{subword} with the right-hand side of the matching rule. The search is continued from
the next \texttt{rule} in \texttt{rules}, but using the new \texttt{word}. When the end of \texttt{rules} is reached, one pass is considered to have been made and the reduced \texttt{word} is returned. If no matches are found then the original \texttt{word} is returned.
The function \texttt{ReduceWordKB} repeatedly applies the function \texttt{OnePassReduceWord} until the \texttt{word} remaining contains no left-hand side of a \texttt{rule} as a \texttt{subword}. If \texttt{rules} is a complete rewrite system, then the irreducible \texttt{word} that is returned is unique, otherwise the order of the rules in \texttt{rules} will determine which irreducible word is returned. In the example we see that $b^9a^9$ reduces to $ba$, and we shall see later that this is not a normal form.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> monrels := Concatenation( gprels, invrels );
[ q8_Ml^4, q8_M2^4, q8_Ml*q8_M2*q8_Ml*q8_M4, q8_Ml^2*q8_M2^2, q8_Ml*q8_M3,
q8_M2*q8_M4, q8_M3*q8_Ml, q8_M4*q8_M2]
gap> id := One( monrels[l] );;
gap> r0 := List( monrels, r -> [ r, id ] );
[ [ q8_Ml^4, <identity ...> ], [ q8_M2^4, <identity. ..> ],
[ q8_Ml*q8_M2*q8_Ml*q8_M4, <identity ...> ],
[ q8_Ml^2*q8_M2^2, <identity. ..>], [ q8_Ml*q8_M3, <identity ...> ],
[ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity. ..>],
[ q8_M4*q8_M2, <identity ...> ] ]
gap> ap := genfgmon[l];; bp := genfgmon[2];; ## p for plus
gap> am := genfgmon[3];; bm := genfgmon[4];; ## m for minus
gap> w0 := bp^9 * ap^9;
q8_M2^9*q8_M1^9
gap> w1 := OnePassReduceWord( w0, r0 );
q8_M2^5*q8_M1^5
gap> w2 := ReduceWordKB( w0, r0 );
q8_M2*q8_M1
\end{Verbatim}
\subsection{\textcolor{Chapter }{OnePassKB}}
\logpage{[ 2, 3, 3 ]}\nobreak
\hyperdef{L}{X7F0CD1EB7C220D40}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OnePassKB({\slshape rules})\index{OnePassKB@\texttt{OnePassKB}}
\label{OnePassKB}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RewriteReduce({\slshape rules})\index{RewriteReduce@\texttt{RewriteReduce}}
\label{RewriteReduce}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{KnuthBendix({\slshape rules})\index{KnuthBendix@\texttt{KnuthBendix}}
\label{KnuthBendix}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ShorterRule({\slshape rule1, rule2})\index{ShorterRule@\texttt{ShorterRule}}
\label{ShorterRule}
}\hfill{\scriptsize (operation)}}\\
The function \texttt{OnePassKB} implements the main loop of the Knuth-Bendix completion algorithm. Rules are
compared with each other; all critical pairs are calculated; and the
irreducible critical pairs are orientated with respect to the
length-lexicographical ordering and added to the rewrite system.
The function \texttt{RewriteReduce} will remove unnecessary rules from a rewrite system. A rule is deemed to be
unnecessary if it is implied by the other rules, i.e. if both sides can be
reduced to the same thing by the remaining rules.
The function \texttt{KnuthBendix} implements the Knuth-Bendix algorithm, attempting to complete a rewrite system
with respect to a length-lexicographic ordering. It calls first \texttt{OnePassKB}, which adds rules, and then (for efficiency) \texttt{RewriteReduce} which removes any unnecessary ones. This procedure is repeated until \texttt{OnePassKB} adds no more rules. It will not always terminate, but for many examples (all
finite groups) it will be successful. The rewrite system returned is complete,
that is: it will rewrite any given word in the free monoid to a unique
irreducible; there is one irreducible for each element of the quotient monoid;
and any two elements of the free monoid which are in the same class will
rewrite to the same irreducible.
The function \texttt{ShorterRule} gives an ordering on rules. Rules $(g_lg_2,id)$ that identify two generators (or one generator with the inverse of another)
come first in the ordering. Otherwise one precedes another if it reduces the
length of a word by a greater amount.
One pass of this procedure for our \texttt{q8} example adds 13 relators to the original 8, and these 21 are then reduced to
9. A second pass and reduction gives a list of 16 rules which forms a complete
rewrite system for the group.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> r1 := OnePassKB( r0 );
[ [ q8_Ml^4, <identity ...> ], [ q8_M2^4, <identity ...> ],
[ q8_Ml*q8_M2*q8_Ml*q8_M4, <identity ...> ],
[ q8_Ml^2*q8_M2^2, <identity. ..> ], [ q8_Ml*q8_M3, <identity ...> ],
[ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity ...> ],
[ q8_M4*q8_M2, <identity ...> ], [ q8_M2*q8_Ml*q8_M4, q8_Ml^3],
[ q8_Ml*q8_M2^2, q8_Ml^3 ], [ q8_M2^2, q8_Ml^2 ], [q8_Ml^3, q8_M3 ],
[ q8_M2^3, q8_M4 ], [ q8_Ml*q8_M2*q8_Ml, q8_M2],
[ q8_M2^3, q8_Ml^2*q8_M2], [ q8_M2^2, q8_Ml^2 ], [q8_Ml^2*q8_M2, q8_M4 ],
[ q8_Ml^3, q8_M3 ], [ q8_M2*q8_Ml*q8_M4, q8_M3 ], [q8_Ml*q8_M2^2, q8_M3 ],
[ q8_M2^3, q8_M4 ] ]
gap> r1 := RewriteReduce( r1 );
[ [ q8_Ml*q8_M3, <identity ...> ], [ q8_M2^2, q8_Ml^2 ],
[ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity ...> ],
[ q8_M4*q8_M2, <identity ...> ], [ q8_Ml^3, q8_M3 ],
[ q8_Ml^2*q8_M2, q8_M4 ], [ q8_Ml*q8_M2*q8_Ml, q8_M2 ],
[ q8_M2*q8_Ml*q8_M4, q8_M3 ] ]
gap> r2 := KnuthBendix( r1 );
[ [ q8_Ml*q8_M3, <identity ...> ], [ q8_M2*q8_Ml, q8_Ml*q8_M4 ],
[ q8_M2^2, q8_Ml^2], [ q8_M2*q8_M3, q8_Ml*q8_M2 ],
[ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity ...> ],
[ q8_M3*q8_M2, q8_Ml*q8_M4 ], [ q8_M3^2, q8_Ml^2 ],
[ q8_M3*q8_M4, q8_Ml*q8_M2 ], [ q8_M4*q8_Ml, q8_Ml*q8_M2 ],
[ q8_M4*q8_M2, <identity ...> ], [ q8_M4*q8_M3, q8_Ml*q8_M4 ],
[ q8_M4^2, q8_Ml^2], [ q8_Ml^3, q8_M3 ], [q8_Ml^2*q8_M2, q8_M4 ],
[ q8_Ml^2*q8_M4, q8_M2 ] ]
gap> w2 := ReduceWordKB( w0, r2 );
q8_M1*q8_M4
\end{Verbatim}
}
\section{\textcolor{Chapter }{Enumerating elements}}\logpage{[ 2, 4, 0 ]}
\hyperdef{L}{X83CBF2BE8478A728}{}
{
\subsection{\textcolor{Chapter }{ElementsOfMonoidPresentation}}
\logpage{[ 2, 4, 1 ]}\nobreak
\hyperdef{L}{X7EDA50068207339D}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ElementsOfMonoidPresentation({\slshape mon})\index{ElementsOfMonoidPresentation@\texttt{ElementsOfMonoidPresentation}}
\label{ElementsOfMonoidPresentation}
}\hfill{\scriptsize (attribute)}}\\
The function \texttt{ElementsOfMonoidPresentation} returns a list of normal forms for the elements of the group given by the
monoid presentation \texttt{mon}. The normal forms are the least elements in each equivalence class (with
respect to length-lex order). When \texttt{rules} is a complete rewrite system for \texttt{G} the list returned is a set of normal forms for the group elements.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> elq8 := Elements( q8 );
[ <identity .. .>, fl, f2, fl^2, fl*f2, fl^3*f2, fl^3, fl^2*f2 ]
gap> elmonq8 := ElementsOfMonoidPresentation( monq8 );
[ <identity. ..>, q8_Ml, q8_M2, q8_M3, q8_M4, q8_Ml^2, q8_Ml*q8_M2,
q8_Ml*q8_M4 ]
\end{Verbatim}
}
}
\chapter{\textcolor{Chapter }{Logged Rewriting Systems}}\label{chap-logrws}
\logpage{[ 3, 0, 0 ]}
\hyperdef{L}{X7B8D727485966AF8}{}
{
A logged rewrite system is associated with a group presentation. Each logged
rewrite rule contains, in addition to the standard rewrite rule, a record or
log component which express the rule in terms of the original relators of the
group. Here a logged rewrite rule is represented by a triple \texttt{[ u, [L1,L2,..,Lk], v]}, where \texttt{[u,v]} is a rewrite rule and $L_i = [n_i,w_i]$ where $n_i$ is a group relator and $w_i$ is a word. These three components obey the identity $u = n_1^{w_1} \ldots n_k^{w_k} v$.
Rules of the form $g^+g^-$ are relevant to the monoid presentation, but not to the group presentation, so
are not included in the logging.
\section{\textcolor{Chapter }{Logged Knuth-Bendix Completion}}\logpage{[ 3, 1, 0 ]}
\hyperdef{L}{X797732E87F1FE197}{}
{
The functions in this section are the logged versions of those in the previous
chapter.
\subsection{\textcolor{Chapter }{LoggedOnePassKB}}
\logpage{[ 3, 1, 1 ]}\nobreak
\hyperdef{L}{X80075D5180A8F1A5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LoggedOnePassKB({\slshape loggedrules})\index{LoggedOnePassKB@\texttt{LoggedOnePassKB}}
\label{LoggedOnePassKB}
}\hfill{\scriptsize (operation)}}\\
Given a logged rewrite system, this function finds all the rules that would be
added to complete the rewrite system in \texttt{OnePassKB}, and also the logs which relate the new rules to the originals. The result of
applying this function to loggedrules is to add new logged rules to the system
without changing the monoid it defines.
In the example, we first convert the presentation for \texttt{q8} into an initial set of logged rules, and then apply one pass of Knuth-Bendix.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> l0 := ListWithIdenticalEntries( 8, 0 );;
gap> for j in [1..8] do
r := r0[j];
if ( j<5 ) then
l0[j] := [ r[1], [ [j,id] ], r[2] ];
else
l0[j] := [ r[1], [ ], r[2] ];
fi;
od;
gap> l0;
[ [ q8_M1^4, [ [ 1, <identity ...>] ], <identity. ..> ],
[ q8_M2^4, [ [ 2, <identity ...>] ], <identity ...> ],
[ q8_M1*q8_M2*q8_M1*q8_M4, [ [ 3, <identity ...> ] ], <identity ...> ],
[ q8_M1^2*q8_M2^2, [ [ 4, <identity ...> ] ], <identity ...> ],
[ q8_M1*q8_M3, [ ], <identity ...> ], [ q8_M2*q8_M4, [ ], <identity ...> ],
[ q8_M3*q8_M1, [ ], <identity ...> ], [ q8_M4*q8_M2, [ ], <identity ...> ] ]
gap> l1 := LoggedOnePassKB( l0 );;
gap> Length( l1 );
\end{Verbatim}
\subsection{\textcolor{Chapter }{LoggedKnuthBendix}}
\logpage{[ 3, 1, 2 ]}\nobreak
\hyperdef{L}{X87D1E3A578AAAFCB}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LoggedKnuthBendix({\slshape loggedrules})\index{LoggedKnuthBendix@\texttt{LoggedKnuthBendix}}
\label{LoggedKnuthBendix}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LoggedRewriteReduce({\slshape loggedrules})\index{LoggedRewriteReduce@\texttt{LoggedRewriteReduce}}
\label{LoggedRewriteReduce}
}\hfill{\scriptsize (operation)}}\\
The function \texttt{LoggedRewriteReduce} removes unnecessary rules from a logged rewrite system. It works on the same
principle as \texttt{RewriteReduce}.
The function \texttt{LoggedKnuthBendix} repeatedly applies \texttt{LoggedOnePassKB} and \texttt{LoggedRewriteReduce} until no new rules are added and no unnecessary ones are included. The output
is a reduced complete logged rewrite system.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> l1 := LoggedRewriteReduce( l1 );
[ [ q8_M1*q8_M3, [ ], <identity ...> ],
[ q8_M2^2, [ [ -4, <identity ...> ], [ 2, q8_M1^-2 ] ], q8_M1^2 ],
[ q8_M2*q8_M4, [ ], <identity ...> ], [ q8_M3*q8_M1, [ ], <identity ...> ],
[ q8_M4*q8_M2, [ ], <identity ...> ],
[ q8_M1^3, [ [ 1, <identity. ..> ] ], q8_M3 ],
[ q8_M1^2*q8_M2, [ [ 4, <identity. ..> ] ], q8_M4 ],
[ q8_M1*q8_M2*q8_M1, [ [ 3, <identity ...> ] ], q8_M2 ],
[ q8_M2*q8_M1*q8_M4, [ [ 3, q8_M3^-1 ] ], q8_M3] ]
gap> l2 := LoggedKnuthBendix( l1 );
[ [ q8_M1*q8_M3, [ ], <identity ...> ],
[ q8_M2*q8_M1, [ [ 3, q8_M3^-1 ], [-1, <identity. ..> ], [ 4, q8_M1^-1 ] ],
q8_M1*q8_M4 ],
[ q8_M2^2, [ [ -4, <identity ...> ], [2, q8_M1^-2] ], q8_M1^2 ],
[ q8_M2*q8_M3, [ [ -3, <identity ...> ] ], q8_M1*q8_M2 ],
[ q8_M2*q8_M4, [ ], <identity ...> ], [ q8_M3*q8_M1, [ ], <identity ...> ],
[ q8_M3*q8_M2, [ [ -1, <identity ...>], [4, q8_M1^-1 ] ], q8_M1*q8_M4 ],
[ q8_M3^2, [ [ -1, <identity ...>] ], q8_M1^2 ],
[ q8_M3*q8_M4, [ [ -1, <identity ...>], [ -2, q8_M1^-2],
[ 4, <identity ...> ], [ 3, q8_M3^-1*q8_M2^-1 ],
[ -3, <identity. ..> ] ], q8_M1*q8_M2 ],
[ q8_M4*q8_M1, [ [ -4, <identity ...> ], [ 3, q8_M1^-1 ] ], q8_M1*q8_M2 ],
[ q8_M4*q8_M2, [ ], <identity ...> ],
[ q8_M4*q8_M3, [ [ -3, q8_M3^-1*q8_M4^-1] ], q8_M1*q8_M4 ],
[ q8_M4^2, [ [ -4, <identity. ..> ] ], q8_M1^2 ],
[ q8_M1^3, [ [ 1, <identity ...> ] ], q8_M3 ],
[ q8_M1^2*q8_M2, [ [4, <identity. ..> ] ], q8_M4 ],
[ q8_M1^2*q8_M4, [ [ -4, q8_M1^-2], [ 1, <identity ...> ] ], q8_M2 ] ]
\end{Verbatim}
}
\section{\textcolor{Chapter }{Logged reduction of a word}}\logpage{[ 3, 2, 0 ]}
\hyperdef{L}{X831A93087918AA5D}{}
{
\subsection{\textcolor{Chapter }{LoggedReduceWordKB}}
\logpage{[ 3, 2, 1 ]}\nobreak
\hyperdef{L}{X7C5094AF784A8BA7}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LoggedReduceWordKB({\slshape word, loggedrules})\index{LoggedReduceWordKB@\texttt{LoggedReduceWordKB}}
\label{LoggedReduceWordKB}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LoggedOnePassReduceWord({\slshape word, loggedrules})\index{LoggedOnePassReduceWord@\texttt{LoggedOnePassReduceWord}}
\label{LoggedOnePassReduceWord}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ShorterLoggedRule({\slshape logrule1, logrule2})\index{ShorterLoggedRule@\texttt{ShorterLoggedRule}}
\label{ShorterLoggedRule}
}\hfill{\scriptsize (operation)}}\\
Given a word and a logged rewrite system, the function \texttt{LoggedOnePassReduceWord} makes one reduction of the word (as in \texttt{OnePassReduceWord}) and records this, using the log part of the rule used and the position in
the original word of the replaced part.
The function \texttt{LoggedReduceWordKB} repeatedly applies \texttt{OnePassLoggedReduceWord} until the word can no longer be reduced. Each step of the reduction is logged,
showing how the original word can be expressed in terms of the original
relators and the irreducible word. When \texttt{loggedrules} is complete the reduced word is a unique normal form for that group element.
The log of the reduction depends on the order in which the rules are applied.
The function \texttt{ShorterLoggedrule} decides whether one logged rule is better than another, using the same
criteria as \texttt{ShorterRule}. In the example we perform logged reductions of \texttt{w0} corresponding to the ordinary reductions performed in the previous chapter.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> w0;
q8_M2^9*q8_M1^9
gap> lw1 := LoggedOnePassReduceWord( w0, l0 );
[ [ [ 1, q8_M2^-9 ], [ 2, <identity ...> ] ], q8_M2^5*q8_M1^5 ]
gap> lw2 := LoggedReduceWordKB( w0, l0 );
[ [ [ 1, q8_M2^-9 ], [ 2, <identity ...> ], [ 1, q8_M2^-5 ],
[ 2, <identity ...> ] ], q8_M2*q8_M1 ]
gap> lw2 := LoggedReduceWordKB( w0, l2 );
[ [ [ 3, q8_M3^-1*q8_M2^-8 ], [ -1, q8_M2^-8 ], [ 4, q8_M1^-1*q8_M2^-8 ],
[ -4, <identity ...> ], [ 2, q8_M1^-2 ],
[ -4, q8_M1^-1*q8_M2^-6*q8_M1^-2 ], [ 3, q8_M1^-2*q8_M2^-6*q8_M1^-2 ],
[ 1, q8_M2^-1*q8_M1^-2*q8_M2^-6*q8_M1^-2 ], [ 4, <identity ...> ],
[ 3, q8_M3^-1*q8_M2^-4*q8_M4^-1 ], [ -1, q8_M2^-4*q8_M4^-1 ],
[ 4, q8_M1^-1*q8_M2^-4*q8_M4^-1 ], [ -4, q8_M4^-1 ],
[ 2, q8_M1^-2*q8_M4^-1 ],
[ -3, q8_M1^-1*q8_M4^-1*q8_M1^-1*q8_M2^-2*q8_M1^-2*q8_M4^-1 ],
[ -4, <identity ...> ], [ 3, q8_M1^-1 ],
[ 1, q8_M2^-1*q8_M1^-2*q8_M4^-1*q8_M1^-1*q8_M2^-2*q8_M1^-1*q8_M2^
-1*q8_M1^-1 ],
[ 4, q8_M4^-1*q8_M1^-1*q8_M2^-2*q8_M1^-1*q8_M2^-1*q8_M1^-1 ],
[ 3, q8_M3^-1*q8_M1^-1 ], [ -1, q8_M1^-1 ], [ 4, q8_M1^-2 ],
[ -4, q8_M4^-1*q8_M1^-2 ], [ 2, q8_M1^-2*q8_M4^-1*q8_M1^-2 ],
[ -4, q8_M1^-2 ], [ 3, q8_M1^-3 ], [ -4, q8_M1^-2*q8_M2^-1*q8_M1^-3 ],
[ 1, <identity ...> ], [ 3, q8_M3^-2 ], [ -1, q8_M3^-1 ],
[ 4, q8_M1^-1*q8_M3^-1 ], [ -4, <identity ...> ], [ 3, q8_M1^-1 ],
[ 3, q8_M3^-1*q8_M1^-1 ], [ -1, q8_M1^-1 ], [ 4, q8_M1^-2 ],
[ -4, q8_M1^-2 ], [ 3, q8_M1^-3 ], [ 1, <identity ...> ],
[ -1, <identity ...> ], [ 4, q8_M1^-1 ] ], q8_M1*q8_M4 ]
\end{Verbatim}
\subsection{\textcolor{Chapter }{LoggedRewritingSystemFpGroup}}
\logpage{[ 3, 2, 2 ]}\nobreak
\hyperdef{L}{X8652CEEF7802DA46}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LoggedRewritingSystemFpGroup({\slshape loggedrules})\index{LoggedRewritingSystemFpGroup@\texttt{LoggedRewritingSystemFpGroup}}
\label{LoggedRewritingSystemFpGroup}
}\hfill{\scriptsize (attribute)}}\\
Given a group presentation, the function \texttt{LoggedRewritingSystemFpGroup} determines a logged rewrite system based on the relators. The initial logged
rewrite system associated with a group presentation consists of two types of
rule. These are logged versions of the two types of rule in the monoid
presentation. For each relator \texttt{rel} of the group there is a logged rule \texttt{[ rel, [ [ 1, rel] ], id]}. For each inverse relator there is a logged rule \texttt{[gen*inv, [], id ]}. It then attempts a completion of the logged rewrite system. The rules in the
final system are partially ordered by the function \texttt{ShorterLoggedRule}.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> LoggedRewritingSystemFpGroup( q8 );
[ [ q8_M4*q8_M2, [ ], <identity ...> ], [ q8_M3*q8_Ml, [ ], <identity ...> ],
[ q8_M2*q8_M4, [ ], <identity ...> ],
[ q8_Ml*q8_M3, [ ], <identity ...> ],
[ q8_Ml^2*q8_M4, [ [ -8, q8_Ml^-2 ], [ 5, <identity ...> ] ], q8_M2 ],
[ q8_Ml^2*q8_M2, [ [ 8, <identity ...> ] ], q8_M4 ],
[ q8_Ml^3, [ [ 5, <identity ...> ] ], q8_M3 ],
[ q8_M4^2, [ [ -8, <identity ...> ] ], q8_Ml^2 ],
[ q8_M4*q8_M3, [ [ -7, q8_M3^-1*q8_M4^-1 ] ], q8_Ml*q8_M4 ],
[ q8_M4*q8_Ml, [ [ -8, <identity. ..> ], [ 7, q8_Ml^-1 ] ], q8_Ml*q8_M2 ],
[ q8_M3*q8_M4,
[ [ -5, <identity ...>], [ -6, q8_Ml^-2 ], [ 8, <identity ...> ],
[ 7, q8_M3^-1*q8_M2^-1 ], [ -7, <identity. ..> ] ], q8_Ml*q8_M2 ],
[ q8_M3^2, [ [ -5, <identity ...>] ], q8_Ml^2 ],
[ q8_M3*q8_M2, [ [ -5, <identity. ..> ], [ 8, q8_Ml^-1 ] ], q8_Ml*q8_M4 ],
[ q8_M2*q8_M3, [ [ -7, <identity ...> ] ], q8_M1*q8_M2 ],
[ q8_M2^2, [ [ -a, <identity ...> ], [ 6, q8_M1^-2 ] ], q8_M1^2 ],
[ q8_M2*q8_M1, [ [ 7, q8_M3^-1 ], [ -5, <identity ...> ], [ a, q8_M1^-1 ] ],
q8_M1*q8_M4 ] ]
\end{Verbatim}
}
}
\chapter{\textcolor{Chapter }{Monoid Polynomials}}\label{chap-monpoly}
\logpage{[ 4, 0, 0 ]}
\hyperdef{L}{X83B25026816C87CE}{}
{
This chapter describes functions to compute with elements of a free
noncommutative algebra. The elements of the algebra are sums of rational
multiples of words in a free monoid. These are called \emph{monoid polynomials}, and are stored as lists of pairs \texttt{[coefficient, word]}.
\section{\textcolor{Chapter }{Construction of monoid polynomials}}\logpage{[ 4, 1, 0 ]}
\hyperdef{L}{X7E8CE44085FE959D}{}
{
\subsection{\textcolor{Chapter }{MonoidPolyFromCoeffsWords}}
\logpage{[ 4, 1, 1 ]}\nobreak
\hyperdef{L}{X7DE231F282DB8660}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MonoidPolyFromCoeffsWords({\slshape coeffs, words})\index{MonoidPolyFromCoeffsWords@\texttt{MonoidPolyFromCoeffsWords}}
\label{MonoidPolyFromCoeffsWords}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MonoidPoly({\slshape terms})\index{MonoidPoly@\texttt{MonoidPoly}}
\label{MonoidPoly}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ZeroMonoidPoly({\slshape F})\index{ZeroMonoidPoly@\texttt{ZeroMonoidPoly}}
\label{ZeroMonoidPoly}
}\hfill{\scriptsize (operation)}}\\
There are two ways to input a monoid polynomial: by listing the coefficients
and then the words; or by listing the terms as a list of pairs \texttt{[coefficient, word]}. If a word occurs more than once in the input list, the coefficients will be
added so that the terms of the monoid polynomial recorded do not contain any
duplicates. The zero monoid polynomial is the polynomial with no terms.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> rels := RelatorsOfFpGroup( q8 );
[ f1^4, f2^4, f1*f2*f1*f2^-1, f1^2*f2^2 ]
gap> freeq8 := FreeGroupOfFpGroup( q8 );;
gap> gens := GeneratorsOfGroup( freeq8 );;
gap> famfree := ElementsFamily( FamilyObj( freeq8 ) );;
gap> famfree!.monoidPolyFam := MonoidPolyFam;;
gap> cg := [6,7];;
gap> pg := MonoidPolyFromCoeffsWords( cg, gens );;
gap> Display( pg );
7*f2 + 6*f1
gap> cr := [3,4,-5,-2];;
gap> pr := MonoidPolyFromCoeffsWords( cr, rels );;
gap> Display( pr );
4*f2^4 - 5*f1*f2*f1*f2^-1 - 2*f1^2*f2^2 + 3*f1^4
gap> Display( ZeroMonoidPoly( freeq8 ) );
zero monpoly
\end{Verbatim}
}
\section{\textcolor{Chapter }{Components of a polynomial}}\logpage{[ 4, 2, 0 ]}
\hyperdef{L}{X84B1F4CC79983A94}{}
{
\subsection{\textcolor{Chapter }{Terms}}
\logpage{[ 4, 2, 1 ]}\nobreak
\hyperdef{L}{X832D20E8813FBE5D}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Terms({\slshape poly})\index{Terms@\texttt{Terms}}
\label{Terms}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Coeffs({\slshape poly})\index{Coeffs@\texttt{Coeffs}}
\label{Coeffs}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Words({\slshape poly})\index{Words@\texttt{Words}}
\label{Words}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LeadTerm({\slshape poly})\index{LeadTerm@\texttt{LeadTerm}}
\label{LeadTerm}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LeadCoeffMonoidPoly({\slshape poly})\index{LeadCoeffMonoidPoly@\texttt{LeadCoeffMonoidPoly}}
\label{LeadCoeffMonoidPoly}
}\hfill{\scriptsize (attribute)}}\\
The function \texttt{Terms} returns the terms of a polynomial as a list of pairs of the form \texttt{[word, coefficient]}. The function \texttt{Coeffs} returns the coefficients of a polynomial as a list, and the function \texttt{Words} returns the words of a polynomial as a list. The function \texttt{LeadTerm} returns the term of the polynomial whose word component is the largest with
respect to the length-lexicographical ordering. The function \texttt{LeadCoeffMonoidPoly} returns the coefficient of the leading term of a polynomial.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> Coeffs( pr );
[ 4, -5, -2, 3 ]
gap> Terms( pr );
[ [ 4, f2^4 ], [ -5, f1*f2*f1*f2^-1 ], [ -2, f1^2*f2^2 ], [ 3, f1^4 ] ]
gap> Words( pr );
[ f2^4, f1*f2*f1*f2^-1, f1^2*f2^2, f1^4 ]
gap> LeadTerm( pr );
[ 4, f2^4]
gap> LeadCoeffMonoidPoly( pr );
4
\end{Verbatim}
\subsection{\textcolor{Chapter }{Monic}}
\logpage{[ 4, 2, 2 ]}\nobreak
\hyperdef{L}{X85C78946877C1FF5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Monic({\slshape poly})\index{Monic@\texttt{Monic}}
\label{Monic}
}\hfill{\scriptsize (operation)}}\\
A monoid polynomial is called \emph{monic} if the coefficient of its leading polynomial is one. The function \texttt{Monic} converts a polynomial into a monic polynomial by dividing all the coefficients
by the leading coefficient.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> mpr := Monic( pr );;
gap> Display( mpr );
f2^4 - 5/4*f1*f2*f1*f2^-1 - 1/2*f1^2*f2^2 + 3/4*f1^4
\end{Verbatim}
\subsection{\textcolor{Chapter }{AddTermMonoidPoly}}
\logpage{[ 4, 2, 3 ]}\nobreak
\hyperdef{L}{X82E04F1086DAAA43}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AddTermMonoidPoly({\slshape poly, coeff, word})\index{AddTermMonoidPoly@\texttt{AddTermMonoidPoly}}
\label{AddTermMonoidPoly}
}\hfill{\scriptsize (operation)}}\\
The function \texttt{AddTermMonoidPoly} adds a new term, given by its coeffiecient and word, to an existing
polynomial.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> w := gens[1]^gens[2];
f2^-1*f1*f2
gap> cw := 3/4;;
gap> wpg:= AddTermMonoidPoly( pg, cw, w);;
gap> Display( wpg );
3/4*f2^-1*f1*f2 + 7*f2 + 6*f1
\end{Verbatim}
}
\section{\textcolor{Chapter }{Monoid Polynomial Operations}}\logpage{[ 4, 3, 0 ]}
\hyperdef{L}{X832341AB7A04BA45}{}
{
\index{=,+,* for monoid polynomials} Tests for equality and arithmetic operations are performed in the usual way.
The operation \texttt{poly1 = poly2} returns \texttt{true} if the monoid polynomials have the same terms, and \texttt{false} otherwise. Multiplication of a monoid polynomial (on the left or right) by a
coefficient; the addition or subtraction of two monoid polynomials;
multiplication (on the right) of a monoid polynomial by a word; and
multiplication of two monoid polynomials; are all implemented.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> [ pg = pg, pg = pr ];
[ true, false ]
gap> prcw := pr*cw;;
gap> Display( prcw );
3*f2^4 - 15/4*f1*f2*f1*f2^-1 - 3/2*f1^2*f2^2 + 9/4*f1^4
gap> cwpr := cw*pr;;
gap> Display( cwpr );
3*f2^4 - 15/4*f1*f2*f1*f2^-1 - 3/2*f1^2*f2^2 + 9/4*f1^4
gap> [ pr = prcw, prcw = cwpr ];
[ false, true ]
gap> Display( pg + pr );
4*f2^4 - 5*f1*f2*f1*f2^-1 - 2*f1^2*f2^2 + 3*f1^4 + 7*f2 + 6*f1
gap> Display( pg - pr );
- 4*f2^4 + 5*f1*f2*f1*f2^-1 + 2*f1^2*f2^2 - 3*f1^4 + 7*f2 + 6*f1
gap> Display( pg * w );
6*f1*f2^-1*f1*f2 + 7*f1*f2
gap> Display( pg * pr );
28*f2^5 - 35*f2*f1*f2*f1*f2^-1 - 14*f2*f1^2*f2^2 + 21*f2*f1^4
+ 24*f1*f2^4 - 30*f1^2*f2*f1*f2^-1 - 12*f1^3*f2^2 + 18*f1^5
\end{Verbatim}
\subsection{\textcolor{Chapter }{Length}}
\logpage{[ 4, 3, 1 ]}\nobreak
\hyperdef{L}{X780769238600AFD1}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Length({\slshape poly})\index{Length@\texttt{Length}}
\label{Length}
}\hfill{\scriptsize (attribute)}}\\
This function returns the number of distinct terms in the monoid polynomial.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> Length( pr );
4
\end{Verbatim}
}
The boolean function \texttt{poly1 {\textgreater} poly2} returns \texttt{true} if the first polynomial has more terms than the second. If the polynomials are
the same length it will compare their leading terms. If the leading word of
the first is lengthlexicographically greater than the leading word of the
second, or if the words are equal but the coefficient of the first is greater
than the coefficient of the second then true is returned. If the leading terms
are equal then the next terms are compared in the same way. If all terms are
the same then \texttt{false} is returned.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> [ pr > 3*pr, pr > pg ];
[ false, true ]
\end{Verbatim}
\section{\textcolor{Chapter }{Reduction of a Monoid Polynomial}}\logpage{[ 4, 4, 0 ]}
\hyperdef{L}{X7A80EA5C7AEA68B1}{}
{
\subsection{\textcolor{Chapter }{ReduceMonoidPoly}}
\logpage{[ 4, 4, 1 ]}\nobreak
\hyperdef{L}{X7979DE308676398D}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ReduceMonoidPoly({\slshape poly, rules})\index{ReduceMonoidPoly@\texttt{ReduceMonoidPoly}}
\label{ReduceMonoidPoly}
}\hfill{\scriptsize (operation)}}\\
Recall that the words of a monoid polynomial are elements of a free monoid.
Given a rewrite system (set of rules) on the free monoid the words can be
reduced. This allows us to simulate calculation in monoid rings where the
monid is given by a complete presentation. This function reduces the words of
the polynomial (elements of the free monoid) with respect to the complete
rewrite system. The words of the reduced polynomial are normal forms for the
elements of the monoid presented by that rewite system. The list of rules \texttt{r2} is displayed in section 2.3.3.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> M := genfgmon;;
gap> mp1 := MonoidPolyFromCoeffsWords( [9,-7,5], [M[1]*M[3], M[2]^3, M[4]*M[3]*M[2]] );;
gap> Display( mp1 );
5*q8_M4*q8_M3*q8_M2 - 7*q8_M2^3 + 9*q8_M1*q8_M3
gap> rmp1 := ReduceMonoidPoly( mp1, r2 );;
gap> Display( rmp1 );
- 7*q8_M4 + 5*q8_M1 + 9*<identity ...>
\end{Verbatim}
}
}
\chapter{\textcolor{Chapter }{Module Polynomials}}\label{chap-modpoly}
\logpage{[ 5, 0, 0 ]}
\hyperdef{L}{X7B5CEEDF82747121}{}
{
In this chapter we consider finitely generated modules over the monoid rings
considered previously. We call an element of this module a \emph{module polynomial}, and we describe functions to construct module polynomials and the standard
algebraic operations for such polynomials.
A module polynomial \texttt{modpoly} is recorded as a list of pairs, \texttt{[ gen, monpoly ]}, where \texttt{gen} is a module generator (basis element), and \texttt{monpoly} is a monoid polynomial. The module polynomial is printed as the formal sum of
monoid polynomial multiples of the generators. Note that the monoid
polynomials are the coefficients of the module polynomials and appear to the
right of the generator, as we choose to work with right modules.
The examples we are aiming for are the identities among the relators of a
finitely presented group (see section \textsc{5.4}).
\section{\textcolor{Chapter }{Construction of module polynomials}}\logpage{[ 5, 1, 0 ]}
\hyperdef{L}{X86625AB980F24AA5}{}
{
\subsection{\textcolor{Chapter }{ModulePoly}}
\logpage{[ 5, 1, 1 ]}\nobreak
\hyperdef{L}{X7BEE34B27861ACE5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ModulePoly({\slshape gens, monpolys})\index{ModulePoly@\texttt{ModulePoly}}
\label{ModulePoly}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ModulePoly({\slshape args})\index{ModulePoly@\texttt{ModulePoly}}
\label{ModulePoly}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ZeroModulePoly({\slshape Fgens, Fmon})\index{ZeroModulePoly@\texttt{ZeroModulePoly}}
\label{ZeroModulePoly}
}\hfill{\scriptsize (operation)}}\\
The function \texttt{ModulePoly} returns a module polynomial. The terms of the polynomial maybe input as a list
of generators followed by a list of monoid polynomials or as one list of \texttt{[generator, monoid polynomial]} pairs.
Assuming that \texttt{Fgens} is the free group on the module generators and \texttt{Fmon} is the free group on the monoid generators, the function \texttt{ZeroModulePoly} returns the zero module polynomial, which has no terms, and is an element of
the module.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> frq8 := FreeRelatorGroup( q8 );;
gap> genfrq8 := GeneratorsOfGroup( frq8 );
[ q8_R1, q8_R2, q8_R3, q8_R4 ]
gap> Display( rmp1 );
- 7*q8_M4 + 5*q8_M1 + 9*<identity ...>
gap> mp2 := MonoidPolyFromCoeffsWords( [4,-5], [ M[4], M[1] ] );;
gap> Display( mp2 );
4*q8_M4 - 5*q8_M1
gap> s1 := ModulePoly( [ genfrq8[4], genfrq8[1] ], [ rmp1, mp2 ] );
q8_R1*(4*q8_M4 - 5*q8_M1) + q8_R4*( - 7*q8_M4 + 5*q8_M1 + 9*<identity ...>)
gap> s2 := ModulePoly( [ genfrq8[3], genfrq8[2], genfrq8[1] ],
gap> [ -1*rmp1, 3*mp2, (rmp1+mp2) ] );
q8_R1*( - 3*q8_M4 + 9*<identity ...>) + q8_R2*(12*q8_M4 - 15*q8_M1) + q8_R3*(
7*q8_M4 - 5*q8_M1 - 9*<identity ...>)
gap> zeromp := ZeroModulePoly( frq8, freeq8 );
zero modpoly
\end{Verbatim}
}
\section{\textcolor{Chapter }{Components of a module polynomial}}\logpage{[ 5, 2, 0 ]}
\hyperdef{L}{X83ECC2D5781DE850}{}
{
\subsection{\textcolor{Chapter }{Terms}}
\logpage{[ 5, 2, 1 ]}\nobreak
\hyperdef{L}{X832D20E8813FBE5D}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Terms({\slshape modpoly})\index{Terms@\texttt{Terms}}
\label{Terms}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LeadTerm({\slshape modpoly})\index{LeadTerm@\texttt{LeadTerm}}
\label{LeadTerm}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LeadMonoidPoly({\slshape modpoly})\index{LeadMonoidPoly@\texttt{LeadMonoidPoly}}
\label{LeadMonoidPoly}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{One({\slshape modpoly})\index{One@\texttt{One}}
\label{One}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Length({\slshape modpoly})\index{Length@\texttt{Length}}
\label{Length}
}\hfill{\scriptsize (attribute)}}\\
The first function counts the number of module generators which occur in \texttt{modpoly} (a generator occurs in a polynomial if it has nonzero coefficient). The
function \texttt{One} returns the identity in the free group on the generators.
The function \texttt{Terms} returns the terms of a module polynomial as a list of pairs. In \texttt{LeadTerm}, the generators are ordered, and the term of \texttt{modpoly} with the highest value generator is defined to be the leading term. The monoid
polynomial (coefficient) part of the leading term is returned by the function \texttt{LeadMonoidPoly}.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> [ Length(s1), Length(s2) ];
[ 2, 3 ]
gap> One( s1 );
<identity ...>
gap> Terms( s1 );
[ [ q8_R1, <monpoly> ], [ q8_R4, <monpoly> ] ]
gap> Display( LeadTerm( s1 ) );
[ q8_R4,
- 7*q8_M4 + 5*q8_M1 + 9*<identity ...>
]
gap> Display( LeadTerm( s2 ) );
[ q8_R3,
7*q8_M4 - 5*q8_M1 - 9*<identity ...>
]
gap> Display( LeadMonoidPoly( s1 ) );
- 7*q8_M4 + 5*q8_M1 + 9*<identity ...>
gap> Display( LeadMonoidPoly( s2 ) );
7*q8_M4 - 5*q8_M1 - 9*<identity ...>
\end{Verbatim}
}
\section{\textcolor{Chapter }{Module Polynomial Operations}}\logpage{[ 5, 3, 0 ]}
\hyperdef{L}{X7E57DFF4791C4CAA}{}
{
\index{=,+,* for module polynomials}
\subsection{\textcolor{Chapter }{AddTermModulePoly}}
\logpage{[ 5, 3, 1 ]}\nobreak
\hyperdef{L}{X811C7964873E4062}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AddTermModulePoly({\slshape modpoly, gen, monpoly})\index{AddTermModulePoly@\texttt{AddTermModulePoly}}
\label{AddTermModulePoly}
}\hfill{\scriptsize (operation)}}\\
The function \texttt{AddTermModulePoly} adds a term \texttt{[gen, monpoly]} to a module polynomial \texttt{modpoly}.
Tests for equality and arithmetic operations are performed in the usual way.
Module polynomials may be added or subtracted. A module polynomial can also be
multiplied on the right by a word or by a scalar. The effect of this is to
multiply the monoid polynomial parts of each term by the word or scalar. This
is made clearer in the example.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> mp0 := MonoidPolyFromCoeffsWords( [6], [ M[2] ] );;
gap> Display(mp0);
6*q8_M2
gap> s0 := AddTermModulePoly( s1, genfrq8[3], mp0 );
q8_R1*(4*q8_M4 - 5*q8_M1) + q8_R3*(6*q8_M2) + q8_R4*( - 7*q8_M4 + 5*q8_M1 +
9*<identity ...>)
gap> Display( s1 + s2 );
q8_R1*( q8_M4 - 5*q8_M1 + 9*<identity ...>) + q8_R2*(12*q8_M4 -
15*q8_M1) + q8_R3*(7*q8_M4 - 5*q8_M1 - 9*<identity ...>) + q8_R4*( -
7*q8_M4 + 5*q8_M1 + 9*<identity ...>)
gap> Display( s1 - s0 );
q8_R3*( - 6*q8_M2)
gap> Display( s1 * 1/2 );
q8_R1*(2*q8_M4 - 5/2*q8_M1) + q8_R4*( - 7/2*q8_M4 + 5/2*q8_M1 + 9/
2*<identity ...>)
gap> Display( s1 * M[1] );
q8_R1*(4*q8_M4*q8_M1 - 5*q8_M1^2) + q8_R4*( - 7*q8_M4*q8_M1 + 5*q8_M1^2 +
9*q8_M1)
\end{Verbatim}
}
\section{\textcolor{Chapter }{Identities among relators}}\logpage{[ 5, 4, 0 ]}
\hyperdef{L}{X78038BF07E998E21}{}
{
\subsection{\textcolor{Chapter }{IdentityYSequences}}
\logpage{[ 5, 4, 1 ]}\nobreak
\hyperdef{L}{X78A94CB77B98ACAA}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IdentityYSequences({\slshape grp})\index{IdentityYSequences@\texttt{IdentityYSequences}}
\label{IdentityYSequences}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IdentityModulePolynomials({\slshape grp})\index{IdentityModulePolynomials@\texttt{IdentityModulePolynomials}}
\label{IdentityModulePolynomials}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IdentitiesAmongRelators({\slshape grp})\index{IdentitiesAmongRelators@\texttt{IdentitiesAmongRelators}}
\label{IdentitiesAmongRelators}
}\hfill{\scriptsize (attribute)}}\\
The identities among the relators for a finitely presented group are
constructed as logged module polynomials. The procedure, described in \cite{HeWe1} and based on work in \cite{BrSa}, is to construct a full set of Y-sequences for the group; convert these into
module polynomials (eliminating empty sequences); and then apply
simplification rules (including the primary identity property) to eliminate
obvious duplicates and conjugates.
It is \emph{not} guaranteed that a minimal set of identities is obtained. For \texttt{q8} a set of seven identities is obtained, whereas a minimal set contains only
six. See Example 5.1 of \cite{HeWe1} for further details.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> yseqs := IdentityYSequences( q8 );;
gap> Length( yseqs );
32
gap> polys := IdentityModulePolys( q8 );;
gap> Length( polys );
22
gap> idsq8 := IdentitiesAmongRelators( q8 );;
gap> Length( idsq8 );
2
gap> Length( idsq8[1] );
7
gap> Display( idsq8[1] );
[ ( q8_Y3*( q8_M1*q8_M4), q8_R1*( q8_M1 - <identity ...>) ),
( q8_Y10*( -q8_M1*q8_M4), q8_R2*( q8_M2 - <identity ...>) ),
( q8_Y17*( <identity ...>), q8_R1*( -q8_M3 - q8_M2) + q8_R3*( q8_M1^
2 + q8_M3 + q8_M1 + <identity ...>) ),
( q8_Y31*( q8_M1*q8_M4), q8_R3*( q8_M3 - q8_M2) + q8_R4*( q8_M1 - <identity \
...>) ),
( q8_Y32*( -q8_M1*q8_M4), q8_R2*( -q8_M1^
2) + q8_R3*( -q8_M3 - <identity ...>) + q8_R4*( q8_M2 + <identity ...>) ),
( q8_Y12*( q8_M1*q8_M4), q8_R1*( -q8_M2) + q8_R3*( q8_M1*q8_M2 + q8_M4) + q8\
_R4*( q8_M2 - <identity ...>) ),
( q8_Y16*( -<identity ...>), q8_R1*( -<identity ...>) + q8_R2*( -q8_M1) + q8\
_R4*( q8_M3 + q8_M1) )
]
\end{Verbatim}
\subsection{\textcolor{Chapter }{RootIdentities}}
\logpage{[ 5, 4, 2 ]}\nobreak
\hyperdef{L}{X7BEE0DBB78F9355E}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RootIdentities({\slshape grp})\index{RootIdentities@\texttt{RootIdentities}}
\label{RootIdentities}
}\hfill{\scriptsize (attribute)}}\\
The \emph{root identities} are identities of the form $r^wr^{-1}$ where $r = w^n$ is a relator and $n>1$.
For \texttt{q8} only two of the four relators are proper powers, $q=a^4$ and $r=b^4$, so the root identities are $q^aq^{-1}$ and $r^br^{-1}$. }
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> RootIdentities( q8 );
[ ( q8_Y3*( q8_M1*q8_M4), q8_R1*( q8_M1 - <identity ...>) ),
( q8_Y10*( -q8_M1*q8_M4), q8_R2*( q8_M2 - <identity ...>) ) ]
gap> RootIdentities(s3);
[ ( s3_Y4*( s3_M2*s3_M1), s3_R1*( s3_M1 - <identity ...>) ),
( s3_Y8*( s3_M2*s3_M1), s3_R2*( s3_M2 - <identity ...>) ),
( s3_Y7*( s3_M2*s3_M1), s3_R3*( s3_M2 - s3_M1) ) ]
\end{Verbatim}
}
}
\def\bibname{References\logpage{[ "Bib", 0, 0 ]}
\hyperdef{L}{X7A6F98FD85F02BFE}{}
}
\bibliographystyle{alpha}
\bibliography{manual}
\def\indexname{Index\logpage{[ "Ind", 0, 0 ]}
\hyperdef{L}{X83A0356F839C696F}{}
}
\printindex
\newpage
\immediate\write\pagenrlog{["End"], \arabic{page}];}
\immediate\closeout\pagenrlog
\end{document}
