%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  algfp.tex                   GAP documentation               Thomas Breuer
%%
%A  @(%)$Id: algfp.tex,v 3.1 1994/06/10 02:38:36 vfelsch Rel $
%%
%Y  Copyright 1990-1993,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
%%
%%  This file contains the documentation of functions dealing with finitely
%%  presented algebras.
%%
%H  $Log: algfp.tex,v $
%H  Revision 3.1  1994/06/10  02:38:36  vfelsch
%H  updated examples
%H
%H  Revision 3.0  1994/05/19  13:57:29  sam
%H  Initial Revision under RCS
%H
%%
\def\MeatAxe{\sf MeatAxe}
\def\VE{\mbox{\rm Vector Enumeration}}
\Chapter{Finitely Presented Algebras}

This chapter contains the description of functions dealing with finitely
presented algebras.
The first section informs about the data structures
(see "More about Finitely Presented Algebras"),
the next sections tell how to construct free and finitely presented algebras
(see "FreeAlgebra", "FpAlgebra"), and what functions can be applied to them
(see "IsFpAlgebra", "Functions for Finitely Presented Algebras", "Operators
for Finitely Presented Algebras", "PrintDefinitionFpAlgebra"),
and the final sections introduce functions for elements of finitely
presented algebras (see "MappedExpression", "Elements of Finitely Presented
Algebras", "ElementAlgebra", "NumberAlgebraElement").

For a detailed description of operations of finitely presented algebras on
modules, see chapter "Vector Enumeration".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{More about Finitely Presented Algebras}

*Free Algebras*

Let $X$ be a finite set, and $F$ a field.
The *free algebra* $A$ on $X$ over $F$ can be regarded as the semigroup ring
of the free monoid on $X$ over $F$.
Addition and multiplication of elements are performed by dealing with
sums of words in abstract generators, with coefficients in $F$.

Free algebras and also their subalgebras in {\GAP} are always *unital*,
that is, for an element $a$ in a subalgebra $A$ of a free algebra always
the element $a^0$ lies in $A$ (see "Algebras and Unital Algebras").
Thus the free algebra on the empty set over a field $F$ is
defined to consist of all elements $f e$ where $f$ is in $F$, and $e$ is
the multiplicative neutral element, corresponding to the empty word.

Free algebras are useful when dealing with other algebras, like matrix
algebras, since they allow to handle expressions in terms of the generators.
This is just a generalization of handling words in abstract generators and
concrete group elements in parallel, as is done for example in 'MappedWord'
(see "MappedWord") or functions that construct images and preimages under
homomorphisms.  This mechanism is also provided for the records representing
matrices in the {\MeatAxe} share library (see chapter "The MeatAxe").

\vspace{3mm}

*Finitely Presented Algebras*

A *finitely presented algebra* is defined as quotient $A / I$ of a free
algebra $A$ by a two-sided ideal $I$ in $A$ that is generated by a finite set
$S$ of elements in $F$.

Thus computations with finitely presented algebras are similar to those
with finitely presented groups.  For example, in general it is impossible to
decide whether two elements of the free algebra $A$ are equal modulo $I$.

For finitely presented groups a permutation representation on the cosets
of a subgroup of finite index can be computed by the Todd-Coxeter coset
enumeration method.  An analogue of this method for finitely presented
algebras is Steve Linton\'s {\VE} method that tries to compute a matrix
representation of the action on a quotient of a free module of the algebra.
This method is available in {\GAP} as a share library (see chapter
"Vector Enumeration", and the references there), and this makes
finitely presented algebra in {\GAP} more than an object one can only use
for the obvious arithmetics with elements of free algebras.

{\GAP} only handles the data structures, all the work in done by
the standalone program.  Thus all functions for finitely presented algebras,
like 'Size', delegate the work to the {\VE} program.

*Note* that (contrary to the situation in finitely presented groups, and
several places in {\VE}) relators are meant to be equal to *zero*, not to
the identity.  Two examples for this.  If 'x\^2 - a.one' is a relator in
the presentation of the algebra 'a', with 'x' a generator, then 'x' is an
involution.  If 'x\^2' is a relator then 'x' is nilpotent.  If the generator
'x' occurs in relators of the form 'x \*\ v - a.one' and 'w \*\ x - a.one',
for 'v' and 'w' elements of the free algebra, then 'x' is known to be
invertible.

The {\VE} package is loaded automatically as soon as it is needed.
You can also load it explicitly using

|    gap> RequirePackage( "ve" ); |

\vspace{3mm}

*Elements of Finitely Presented Algebras*

The elements of finitely presented algebras in {\GAP} are records that
store lists of coefficients and of words in abstract generators.
Note that the elements of the ground field are not regarded as elements
of the algebra, especially the identity and zero element are denoted by
'a.one' and 'a.zero', respectively.
Functions and operators for elements of finitely presented algebras are
listed in "Elements of Finitely Presented Algebras".

\vspace{3mm}

*Implementation of Functions for Finitely Presented Algebras*

Every question about a finitely presented algebra $A$ that cannot be answered
from the presentation directly is delegated to an isomorphic matrix algebra
$M$ using the {\VE} share library.  This may be impossible because the
dimension of an isomorphic matrix algebra is too large.  But for small $A$
it seems to be valuable.

For example, if one asks for the size of $A$, {\VE} tries to find such a
matrix algebra $M$, and then {\GAP} computes its size.
$M$ and the isomorphism between $A$ and $M$ are stored in the component
'<A>.matAlgebraA', so {\VE} is called only once for $A$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{FreeAlgebra}

'FreeAlgebra( <F>, <rank> )'\\
'FreeAlgebra( <F>, <rank>, <name> )'\\
'FreeAlgebra( <F>, <name1>, <name2>, ... )'

return a free algebra with ground field <F>.  In the first two forms an
algebra on <rank> free generators is returned, their names will be
'<name>.1', \ldots, '<name>.<rank>', the default for <name> is the string
'\"a\"'.

|    gap> a:= FreeAlgebra( GF(2), 2 );
    UnitalAlgebra( GF(2), [ a.1, a.2 ] )
    gap> b:= FreeAlgebra( Rationals, "x", "y" );
    UnitalAlgebra( Rationals, [ x, y ] )
    gap> x:= b.1;
    x |

Finitely presented algebras are constructed from free algebras via factoring
by a suitable ideal (see "Operators for Finitely Presented Algebras").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{FpAlgebra}

'FpAlgebra( <A> )'

returns a finitely presented algebra isomorphic to the
algebra <A>.  At the moment this is implemented only for matrix algebras
and finitely presented algebras.

|    gap> a:= FreeAlgebra( GF(2), 2 );
    UnitalAlgebra( GF(2), [ a.1, a.2 ] )
    gap> a:= a / [ a.one+a.1^2, a.one+a.2^2, a.one+(a.1*a.2)^3 ];;
    gap> a.name:= "a";; s:= Subalgebra( a, [ a.2 ] );;
    gap> f:= FpAlgebra( s );
    UnitalAlgebra( GF(2), [ a.1 ] )
    gap> PrintDefinitionFpAlgebra( f, "f" );
    f:= FreeAlgebra( GF(2), "a.1" );
    f:= f / [ f.one+f.1^2 ]; |
    
\vspace{5mm}

'FpAlgebra( <F>, <fpgroup> )'

returns the *group algebra* of the finitely presented group <fpgroup> over
the field  <F>, this is the algebra of formal linear combinations of
elements of <fpgroup>, with coefficients in <F>; in this case the number of
algebra generators is twice the number of group generators, the first half
corresponding to the group generators, the second half to their inverses.

|    gap> f:= FreeGroup( 2 );;
    gap> s3:= f / [ f.1^2, f.2^2, (f.1*f.2)^3 ];
    Group( f.1, f.2 )
    gap> a:= FpAlgebra( GF(2), s3 );
    UnitalAlgebra( GF(2), [ a.1, a.2, a.3, a.4 ] ) |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsFpAlgebra}

'IsFpAlgebra( <obj> )'

returns 'true' if <obj> is a finitely presented algebra,
and 'false' otherwise.

|    gap> IsFpAlgebra( FreeAlgebra( GF(2), 0 ) );
    true
    gap> IsFpAlgebra( last );
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Operators for Finitely Presented Algebras}

'<A> / <relators>'

returns a finitely presented algebra that is the quotient of the free algebra
<A> (see "FreeAlgebra") by the two-sided ideal in <A> spanned by the elements
in the list <relators>.

This is the general method to construct finitely presented algebras in
{\GAP}.  For the special case of group algebras of finitely presented groups
see "FpAlgebra".

\vspace{5mm}

'<A> \^\ <n>'

returns a free <A>-module of dimension <n> (see chapter "Modules") for the
finitely presented algebra <A>.

|    gap> f:= FreeAlgebra( Rationals, 2 );
    UnitalAlgebra( Rationals, [ a.1, a.2 ] )
    gap> a:= f / [ f.1^2 - f.one, f.2^2 - f.one, (f.1*f.2)^2 - f.one ];
    UnitalAlgebra( Rationals, [ a.1, a.2 ] )
    gap> a = f;
    false
    gap> a^2;
    Module( UnitalAlgebra( Rationals, [ a.1, a.2 ] ), 
    [ [ a.one, a.zero ], [ a.zero, a.one ] ] ) |

\vspace{5mm}

'<a> in <A>'

returns 'true' if <a> is an element of the finitely presented algebra <A>,
and 'false' otherwise.  Note that the answer may require the computation of
an isomorphic matrix algebra if <A> is not a parent algebra.

|    gap> a.1 in a;
    true
    gap> f.1 in a;
    false
    gap> 1 in a;
    false |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Functions for Finitely Presented Algebras}

The following functions are overlaid in the operations record of finitely
presented algebras.

The *set theoretic functions*: \\
    'Elements', 'Intersection', 'IsFinite', 'IsSubset', 'Size';

the *vector space functions*: \\
    'Base', 'Coefficients', and 'Dimension',

Note that at the moment no basis records (see "Row Space Bases") for finitely
presented algebras are supported.

and the *algebra functions*: \\
    'Closure', 'IsAbelian', 'IsTrivial', 'Operation' (see "Operation for
    Algebras", "Operation for Finitely Presented Algebras", "Examples of
    Vector Enumeration"), 'Subalgebra', and 'TrivialSubalgebra'.

*Note* that these functions try to compute a faithful matrix representation
of the algebra using the {\VE} share library (see chapter "Vector
Enumeration").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PrintDefinitionFpAlgebra}

'PrintDefinitionFpAlgebra( <A>, <name> )'

prints the assignment of the finitely presented algebra <A> to the variable
name <name>.  Using the call as an argument of 'PrintTo' (see "PrintTo"),
this can be used to save <A> to a file.

|    gap> a:= FreeAlgebra( GF(2), "x", "y" );
    UnitalAlgebra( GF(2), [ x, y ] )
    gap> a:= a / [ a.1^2-a.one, a.2^2-a.one, (a.1*a.2)^3 - a.one ];
    UnitalAlgebra( GF(2), [ x, y ] )
    gap> PrintDefinitionFpAlgebra( a, "b" );
    b:= FreeAlgebra( GF(2), "x", "y" );
    b:= b / [ b.one+b.1^2, b.one+b.2^2, b.one+b.1*b.2*b.1*b.2*b.1*b.2 ];
    gap> PrintTo( "algebra", PrintDefinitionFpAlgebra( a, "b" ) ); |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{MappedExpression}

'MappedExpression( <expr>, <gens1>, <gens2> )'

For an arithmetic expression <expr> in terms of <gens1>,
'MappedExpression' returns the corresponding expression in terms of 
<gens2>.

<gens1> may be a list of abstract generators (in this case the result is the
same as the object returned by "MappedWord" 'MappedWord'), or of generators
of a finitely presented algebra.

|    gap> a:= FreeAlgebra( Rationals, 2 );;
    gap> a:= a / [ a.1^2 - a.one, a.2^2 - a.one, (a.1*a.2)^2 - a.one ];;
    gap> matgens:= [ [[0,0,0,1],[0,0,1,0],[0,1,0,0],[1,0,0,0]],
    >                [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]] ];;
    gap> permgens:= [ (1,4)(2,3), (1,2)(3,4) ];;
    gap> MappedExpression( a.1^2 + a.1, a.generators, matgens );
    [ [ 1, 0, 0, 1 ], [ 0, 1, 1, 0 ], [ 0, 1, 1, 0 ], [ 1, 0, 0, 1 ] ]
    gap> MappedExpression( a.1 * a.2, a.generators, permgens );
    (1,3)(2,4) |

Note that this can be done also in terms of (algebra or group) homomorphisms
(see "Algebra Homomorphisms").

'MappedExpression' may raise elements in <gens2> to the zero-th power.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Elements of Finitely Presented Algebras}%
\index{IsFpAlgebraElement}

*Zero and One of Finitely Presented Algebras*

A finitely presented algebra <A> contains a zero element '<A>.zero'.
If the number of generators of <A> is not zero, the multiplicative neutral
element of <A> is '<A>.one', which is the zero-th power of any nonzero
element of <A>.

\vspace{5mm}

*Comparisons of Elements of Finitely Presented Algebras*

'<x> = <y>'\\
'<x> \<\ <y>'

Elements of the same algebra can be compared in order to form sets.
*Note* that probably it will be necessary to compute an isomorphic
matrix representation in order to decide equality if <x> and <y> are
not elements of a free algebra.

|    gap> a:= FreeAlgebra( Rationals, 1 );;
    gap> a:= a / [ a.1^2 - a.one ];
    UnitalAlgebra( Rationals, [ a.1 ] )
    gap> [ a.1^3 = a.1, a.1^3 > a.1, a.1 > a.one, a.zero > a.one ];
    [ true, false, false, false ] |

\vspace{5mm}

*Arithmetic Operations for Elements of Finitely Presented Algebras*

'<x> + <y>'\\
'<x> - <y>'\\
'<x> \*\ <y>'\\
'<x> \^\ <n>' \\
'<x> / <c>'

The usual arithmetical operations for ring elements apply to elements of
finitely presented algebras.  Exponentiation '\^' can be used to raise
an element <x> to the <n>-th power.  Division '/' is only defined for
denominators in the base field of the algebra.

|    gap> a:= FreeAlgebra( Rationals, 2 );;
    gap> x:= a.1 - a.2;
    a.1+-1*a.2
    gap> x^2;
    a.1^2+-1*a.1*a.2+-1*a.2*a.1+a.2^2
    gap> y:= 4 * x - a.1;
    3*a.1+-4*a.2
    gap> y^2;
    9*a.1^2+-12*a.1*a.2+-12*a.2*a.1+16*a.2^2 |

\vspace{5mm}

'IsFpAlgebraElement( <obj> )'

returns 'true' if <obj> is an element of a finitely presented algebra,
and 'false' otherwise.

|    gap> IsFpAlgebraElement( a.zero );
    true
    gap> IsFpAlgebraElement( a.field.zero );
    false |

\vspace{5mm}

'FpAlgebraElement( <A>, <coeff>, <words> )'

Elements of finitely presented algebras normally arise from arithmetical
operations.  It is, however, possible to construct directly the element
of the finitely presented algebra <A> that is the sum of the words in the
list <words>, with coefficients given by the list <coeff>, by calling
'FpAlgebraElement( <A>, <coeff>, <words> )'.  *Note* that this function
does *not* check whether some of the words are equal, or whether all
coefficients are nonzero.  So one should probably not use it.

|    gap> a;
    UnitalAlgebra( Rationals, [ a.1, a.2 ] )
    gap> FpAlgebraElement( a, [ 1, 1 ], a.generators );
    a.1+a.2
    gap> FpAlgebraElement( a, [ 1, 1, 1 ], List( [ 1..3 ], i -> a.1^i ) );
    a.1+a.1^2+a.1^3 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ElementAlgebra}

'ElementAlgebra( <A>, <nr> )'

returns the <nr>-th element in terms of the generators of the free algebra
<A> over the finite field <F>, with respect to the following ordering.

We form the elements as linear combinations with coefficients in the base
field of <A>, with respect to the basis defined by the ordering of words
according to length and lexicographic order; this sequence starts as follows.

$a_1^0$, $a_1$, $a_2$, \ldots, $a_n$, $a_1^2$, $a_1 a_2$, $a_1 a_3$, \ldots,
$a_1 a_n$, $a_2 a_1$, \ldots, $a_2 a_n$, \ldots, $a_n^2$, $a_1^3$,
$a_1^2 a_2$, \ldots, $a_1^2 a_n$, $a_1 a_2 a_1$, \ldots

Let $n$ be the number of generators of <A>, $q$ the size of <F>,
and $<nr> = \sum_{i=0}^k a_i q^i$ the $q$-adic expression of <nr>.
Then the $a_i$-th element of '<A>.field' is the coefficient of the
$i$-th base element in the required algebra element.
The ordering of field elements is the same as that defined in the
{\MeatAxe} package, that is, 'FFList( <F> )[ <m>+1 ]' (see "FFList") is
the <m>-th element of the field <F>.

|    gap> a:= FreeAlgebra( GF(2), 2 );;
    gap> List( [ 10 .. 20 ], x -> ElementAlgebra( a, x ) );
    [ a.1+a.1^2, a.one+a.1+a.1^2, a.2+a.1^2, a.one+a.2+a.1^2, 
      a.1+a.2+a.1^2, a.one+a.1+a.2+a.1^2, a.1*a.2, a.one+a.1*a.2, 
      a.1+a.1*a.2, a.one+a.1+a.1*a.2, a.2+a.1*a.2 ]
    gap> ElementAlgebra( a, 0 );
    a.zero |

The function can be applied also if <A> is an arbitrary finitely presented
algebra or a matrix algebra.  In these cases the result is the element of
the algebra obtained on replacing the generators of the corresponding free
algebra by the generators of <A>.

*Note* that the zero-th power of elements may be needed, which is not
necessarily an element of a matrix algebra.

|    gap> a:= UnitalAlgebra( GF(2), GL(2,2).generators );
    UnitalAlgebra( GF(2), [ [ [ Z(2)^0, Z(2)^0 ], [ 0*Z(2), Z(2)^0 ] ], 
      [ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2) ] ] ] )
    gap> ElementAlgebra( a, 17 );
    [ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, Z(2)^0 ] ] |

The number of an element <a> can be computed using "NumberAlgebraElement".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{NumberAlgebraElement}

'NumberAlgebraElement( <a> )'

returns the number <n> such that the element <a> of the finitely presented
algebra <A> is the <n>-th element of <A> in the sense of "ElementAlgebra",
that is, '<a> = ElementAlgebra( <A>, <n> )'.

|    gap> a:= FreeAlgebra( GF(2), 2 );;
    gap> NumberAlgebraElement( ( a.1 + a.one )^4 );
    32769
    gap> NumberAlgebraElement( a.zero );
    0
    gap> NumberAlgebraElement( a.one );
    1 |

Note that '<A>.field' must be finite.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
%%
%%  Local Variables:
%%  mode:               outline
%%  outline-regexp:     "%F\\|%V\\|%E"
%%  fill-column:        73
%%  fill-prefix:        "%%  "
%%  eval:               (hide-body)
%%  End:
