# 39 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 Operators for Finitely Presented Algebras, PrintDefinitionFpAlgebra), and the final sections introduce functions for elements of finitely Elements of Finitely Presented Algebras, ElementAlgebra, NumberAlgebraElement).

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

## 39.1 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).

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" ); `

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.

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.

## 39.2 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).

## 39.3 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 ]; ```

`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 ] ) ```

## 39.4 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 ```

## 39.5 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.

`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 ] ] ) ```

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

## 39.6 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:

Examples of Vector Enumeration), `Subalgebra`, and `TrivialSubalgebra`.

Note that these functions try to compute a faithful matrix representation Vector Enumeration).

## 39.7 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" ) ); ```

## 39.8 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.

## 39.9 Elements of Finitely Presented Algebras

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.

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 ] ```

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

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

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

## 39.10 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.

## 39.11 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.

GAP 3.4.4
April 1997