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.
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 GAP3 are always unital, that is, for an element a in a subalgebra A of a free algebra always the element a0 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 GAP3 as a share library (see chapter Vector Enumeration, and the references there), and this makes finitely presented algebra in GAP3 more than an object one can only use for the obvious arithmetics with elements of free algebras.
GAP3 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 GAP3 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 GAP3 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.
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, ..., 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).
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 ] )
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
40.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 GAP3. 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
40.6 Functions for Finitely Presented Algebras
The following functions are overlaid in the operations record of finitely presented algebras.
Elements, Intersection, IsFinite, IsSubset, Size;
Base, Coefficients, and Dimension,
Note that at the moment no basis records (see Row Space Bases) for finitely presented algebras are supported.
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).
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" ) );
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.
40.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
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.
a10, a1, a2, ..., an, a12, a1 a2, a1 a3, ..., a1 an, a2 a1, ..., a2 an, ..., an2, a13, a12 a2, ..., a12 an, a1 a2 a1, ...
Let n be the number of generators of A, q the size of F,
and <nr> = ∑i=0k ai qi the q-adic expression of nr.
Then the ai-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.
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.
gap3-jm