%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %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 '.matAlgebraA', so {\VE} is called only once for $A$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{FreeAlgebra} 'FreeAlgebra( , )'\\ 'FreeAlgebra( , , )'\\ 'FreeAlgebra( , , , ... )' return a free algebra with ground field . In the first two forms an algebra on free generators is returned, their names will be '.1', \ldots, '.', the default for 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( )' returns a finitely presented algebra isomorphic to the algebra . 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( , )' returns the *group algebra* of the finitely presented group over the field , this is the algebra of formal linear combinations of elements of , with coefficients in ; 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( )' returns 'true' if 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} ' / ' returns a finitely presented algebra that is the quotient of the free algebra (see "FreeAlgebra") by the two-sided ideal in spanned by the elements in the list . 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} ' \^\ ' returns a free -module of dimension (see chapter "Modules") for the finitely presented algebra . | 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} ' in ' returns 'true' if is an element of the finitely presented algebra , and 'false' otherwise. Note that the answer may require the computation of an isomorphic matrix algebra if 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( , )' prints the assignment of the finitely presented algebra to the variable name . Using the call as an argument of 'PrintTo' (see "PrintTo"), this can be used to save 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( , , )' For an arithmetic expression in terms of , 'MappedExpression' returns the corresponding expression in terms of . 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 to the zero-th power. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Elements of Finitely Presented Algebras}% \index{IsFpAlgebraElement} *Zero and One of Finitely Presented Algebras* A finitely presented algebra contains a zero element '.zero'. If the number of generators of is not zero, the multiplicative neutral element of is '.one', which is the zero-th power of any nonzero element of . \vspace{5mm} *Comparisons of Elements of Finitely Presented Algebras* ' = '\\ ' \<\ ' 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 and 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* ' + '\\ ' - '\\ ' \*\ '\\ ' \^\ ' \\ ' / ' The usual arithmetical operations for ring elements apply to elements of finitely presented algebras. Exponentiation '\^' can be used to raise an element to the -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( )' returns 'true' if 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( , , )' Elements of finitely presented algebras normally arise from arithmetical operations. It is, however, possible to construct directly the element of the finitely presented algebra that is the sum of the words in the list , with coefficients given by the list , by calling 'FpAlgebraElement( , , )'. *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( , )' returns the -th element in terms of the generators of the free algebra over the finite field , with respect to the following ordering. We form the elements as linear combinations with coefficients in the base field of , 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 , $q$ the size of , and $ = \sum_{i=0}^k a_i q^i$ the $q$-adic expression of . Then the $a_i$-th element of '.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( )[ +1 ]' (see "FFList") is the -th element of the field . | 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 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 . *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 can be computed using "NumberAlgebraElement". %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{NumberAlgebraElement} 'NumberAlgebraElement( )' returns the number such that the element of the finitely presented algebra is the -th element of in the sense of "ElementAlgebra", that is, ' = ElementAlgebra( , )'. | 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 '.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: