#############################################################################
##
#W  mgmring.gd                  GAP library                     Thomas Breuer
##
#H  @(#)$Id: mgmring.gd,v 4.33 2002/04/15 10:05:03 sal Exp $
##
#Y  Copyright (C)  1997,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
#Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
#Y  Copyright (C) 2002 The GAP Group
##
##  This file declares operations for magma rings.
##

#1
##  Given a magma $M$ then the *free magma ring* (or *magma ring* for short)
##  $RM$ of $M$ over a ring-with-one $R$ is the set of finite sums
##  $\sum_{i\in I} r_i m_i$ with $r_i \in R$, and $m_i \in M$.
##  With the obvious addition and $R$-action from the left, $RM$ is a free
##  $R$-module with $R$-basis $M$,
##  and with the usual convolution product, $RM$ is a ring.
##
##  Typical examples of free magma rings are
##  \beginlist%unordered
##  \item{$-$}
##      (multivariate) polynomial rings (see~"Polynomial Rings"), where the
##      magma is a free abelian monoid generated by the indeterminates,
##  \item{$-$}
##      group rings (see~"IsGroupRing"), where the magma is a group,
##  \item{$-$}
##      Laurent polynomial rings, which are group rings of the free abelian
#T      (see~???)
##      groups generated by the indeterminates,
##  \item{$-$}
##      free algebras and free associative algebras, with or without one,
##      where the magma is a free magma or a free semigroup,
##      or a free magma-with-one or a free monoid, respectively.
##  \endlist
##  Note that a free Lie algebra is *not* a magma ring,
##  because of the additional relations given by the Jacobi identity;
##  see~"Magma Rings modulo Relations" for a generalization of magma rings
##  that covers such structures.
##
##  The coefficient ring $R$ and the magma $M$ cannot be regarded
##  as subsets of $RM$,
##  hence the natural *embeddings* of $R$ and $M$ into $RM$ must be handled
##  via explicit embedding maps
##  (see~"Natural Embeddings related to Magma Rings").
##  Note that in a magma ring, the addition of elements is in general
##  different from an addition that may be defined already for the elements
##  of the magma;
##  for example, the addition in the group ring of a matrix group does in
##  general *not* coincide with the addition of matrices.
##  Consider the following example.
##  \beginexample
##  gap> a:= Algebra( GF(2), [ [ [ Z(2) ] ] ] );;  Size( a );
##  2
##  gap> rm:= FreeMagmaRing( GF(2), a );;
##  gap> emb:= Embedding( a, rm );;
##  gap> z:= Zero( a );;  o:= One( a );;
##  gap> imz:= z ^ emb;  IsZero( imz );
##  (Z(2)^0)*[ [ 0*Z(2) ] ]
##  false
##  gap> im1:= ( z + o ) ^ emb;
##  (Z(2)^0)*[ [ Z(2)^0 ] ]
##  gap> im2:= z ^ emb + o ^ emb;
##  (Z(2)^0)*[ [ 0*Z(2) ] ]+(Z(2)^0)*[ [ Z(2)^0 ] ]
##  gap> im1 = im2;
##  false
##  \endexample

#2
##  In order to treat elements of free magma rings uniformly,
##  also without an external representation, the attributes
##  `CoefficientsAndMagmaElements' (see~"CoefficientsAndMagmaElements")
##  and `ZeroCoefficient' (see~"ZeroCoefficient")
##  were introduced that allow one to ``take an element of an arbitrary
##  magma ring into pieces''.
##
##  Conversely, for constructing magma ring elements from coefficients
##  and magma elements, `ElementOfMagmaRing' (see~"ElementOfMagmaRing")
##  can be used.
##  (Of course one can also embed each magma element into the magma ring,
##  see~"Natural Embeddings related to Magma Rings",
##  and then form the linear combination,
##  but many unnecessary intermediate elements are created this way.)

#3
##  \atindex{Embedding!for magma rings}{@\noexpand`Embedding'!for magma rings}
##  Neither the coefficient ring $R$ nor the magma $M$
##  are regarded as subsets of the magma ring $RM$,
##  so one has to use *embeddings* (see~"Embedding") explicitly
##  whenever one needs for example the magma ring element
##  corresponding to a given magma element.
##  Here is an example.
##  \beginexample
##  gap> f:= Rationals;;  g:= SymmetricGroup( 3 );;
##  gap> fg:= FreeMagmaRing( f, g );
##  <algebra-with-one over Rationals, with 2 generators>
##  gap> Dimension( fg );
##  6
##  gap> gens:= GeneratorsOfAlgebraWithOne( fg );
##  [ (1)*(1,2,3), (1)*(1,2) ]
##  gap> ( 3*gens[1] - 2*gens[2] ) * ( gens[1] + gens[2] );
##  (-2)*()+(3)*(2,3)+(3)*(1,3,2)+(-2)*(1,3)
##  gap> One( fg );
##  (1)*()
##  gap> emb:= Embedding( g, fg );;
##  gap> elm:= (1,2,3)^emb;  elm in fg;
##  (1)*(1,2,3)
##  true
##  gap> new:= elm + One( fg );
##  (1)*()+(1)*(1,2,3)
##  gap> new^2;
##  (1)*()+(2)*(1,2,3)+(1)*(1,3,2)
##  gap> emb2:= Embedding( f, fg );;
##  gap> elm:= One( f )^emb2;  elm in fg;
##  (1)*()
##  true
##  \endexample

#4
##  A more general construction than that of free magma rings allows one
##  to create rings that are not free $R$-modules on a given magma $M$
##  but arise from the magma ring $RM$ by factoring out certain identities.
##  Examples for such structures are finitely presented (associative)
##  algebras and free Lie algebras (see~"FreeLieAlgebra").
#T see ... ?
##
##  In {\GAP}, the use of magma rings modulo relations is limited to
##  situations where a normal form of the elements is known and where
##  one wants to guarantee that all elements actually constructed are
##  in normal form.
##  (In particular, the computation of the normal form must be cheap.)
##  This is because the methods for comparing elements in magma rings
##  modulo relations via `\\=' and `\\\<' just compare the involved
##  coefficients and magma elements,
##  and also the vector space functions regard those monomials as
##  linearly independent over the coefficients ring that actually occur
##  in the representation of an element of a magma ring modulo relations.
##
##  Thus only very special finitely presented algebras will be represented
##  as magma rings modulo relations,
##  in general finitely presented algebras are dealt with via the
##  mechanism described in Chapter~"Finitely Presented Algebras".

#5
##  The *family* containing elements in the magma ring $RM$
##  in fact contains all elements with coefficients in the family of elements
##  of $R$ and magma elements in the family of elements of $M$.
##  So arithmetic operations with coefficients outside $R$ or with
##  magma elements outside $M$ might create elements outside $RM$.
##
##  It should be mentioned that each call of `FreeMagmaRing' creates
##  a new family of elements,
##  so for example the elements of two group rings of permutation groups
##  over the same ring lie in different families and therefore are regarded
##  as different.
##  \beginexample
##  gap> g:= SymmetricGroup( 3 );;
##  gap> h:= AlternatingGroup( 3 );;
##  gap> IsSubset( g, h );
##  true
##  gap> f:= GF(2);;
##  gap> fg:= GroupRing( f, g );
##  <algebra-with-one over GF(2), with 2 generators>
##  gap> fh:= GroupRing( f, h );
##  <algebra-with-one over GF(2), with 1 generators>
##  gap> IsSubset( fg, fh );
##  false
##  gap> o1:= One( fh );  o2:= One( fg );  o1 = o2;
##  (Z(2)^0)*()
##  (Z(2)^0)*()
##  false
##  gap> emb:= Embedding( g, fg );;
##  gap> im:= Image( emb, h );
##  <group of size 3 with 1 generators>
##  gap> IsSubset( fg, im );
##  true
##  \endexample
##
##  There is *no* generic *external representation* for elements in an
##  arbitrary free magma ring.
##  For example, polynomials are elements of a free magma ring,
##  and they have an external representation relying on the special form
##  of the underlying monomials.
##  On the other hand, elements in a group ring of a permutation group
##  do not admit such an external representation.
##
##  For convenience, magma rings constructed with `FreeAlgebra',
##  `FreeAssociativeAlgebra', `FreeAlgebraWithOne', and
##  `FreeAssociativeAlgebraWithOne' support an external representation of
##  their elements, which is defined as a list of length 2,
##  the first entry being the zero coefficient, the second being a list with
##  the external representations of the magma elements at the odd positions
##  and the corresponding coefficients at the even positions.
##
##  As the above examples show, there are several possible representations
##  of magma ring elements, the representations used for polynomials
##  (see~"Polynomials and Rational Functions")
##  as well as the default representation `IsMagmaRingObjDefaultRep'
##  of magma ring elements.
##  The latter simply stores the zero coefficient and a list containing
##  the coefficients of the element at the even positions
##  and the corresponding magma elements at the odd positions,
##  where the succession is compatible with the ordering of magma elements
##  via `\/'.
##
Revision.mgmring_gd :=
    "@(#)$Id: mgmring.gd,v 4.33 2002/04/15 10:05:03 sal Exp $";


#############################################################################
##
#C  IsElementOfMagmaRingModuloRelations( <obj> )
#C  IsElementOfMagmaRingModuloRelationsCollection( <obj> )
##
##  This category is used, e.~g., for elements of free Lie algebras.
##
DeclareCategory( "IsElementOfMagmaRingModuloRelations", IsScalar );

DeclareCategoryCollections( "IsElementOfMagmaRingModuloRelations" );


#############################################################################
##
#C  IsElementOfMagmaRingModuloRelationsFamily( <Fam> )
##
DeclareCategoryFamily( "IsElementOfMagmaRingModuloRelations" );


#############################################################################
##
#C  IsElementOfFreeMagmaRing( <obj> )
#C  IsElementOfFreeMagmaRingCollection( <obj> )
##
DeclareCategory( "IsElementOfFreeMagmaRing",
    IsElementOfMagmaRingModuloRelations );

DeclareCategoryCollections( "IsElementOfFreeMagmaRing" );


#############################################################################
##
#C  IsElementOfFreeMagmaRingFamily( <Fam> )
##
##  Elements of families in this category have trivial normalisation, i.e.,
##  efficient methods for `\\=' and `\\\<'.
##
DeclareCategoryFamily( "IsElementOfFreeMagmaRing" );


#############################################################################
##
#A  CoefficientsAndMagmaElements( <elm> ) . . . . .  for elm. in a magma ring
##
##  is a list that contains at the odd positions the magma elements,
##  and at the even positions their coefficients in the element <elm>.
##
DeclareAttribute( "CoefficientsAndMagmaElements",
    IsElementOfMagmaRingModuloRelations );


#############################################################################
##
#A  ZeroCoefficient( <elm> )
##
##  For an element <elm> of a magma ring (modulo relations) $RM$,
##  `ZeroCoefficient' returns the zero element of the coefficient ring $R$.
##
DeclareAttribute( "ZeroCoefficient", IsElementOfMagmaRingModuloRelations );


#############################################################################
##
#O  NormalizedElementOfMagmaRingModuloRelations( <F>, <descr> )
##
##  Let <F> be a family of magma ring elements modulo relations,
##  and <descr> the description of an element in a magma ring modulo
##  relations.
##  `NormalizedElementOfMagmaRingModuloRelations' returns a description of
##  the same element,
##  but normalized w.r.t.~the relations.
##  So two elements are equal if and only if the result of
##  `NormalizedElementOfMagmaRingModuloRelations' is equal for their internal
##  data, that is, `CoefficientsAndMagmaElements' will return the same
##  for the corresponding two elements.
##
##  `NormalizedElementOfMagmaRingModuloRelations' is allowed to return
##  <descr> itself, it need not make a copy.
##  This is the case for example in the case of free magma rings.
##
DeclareOperation( "NormalizedElementOfMagmaRingModuloRelations",
    [ IsElementOfMagmaRingModuloRelationsFamily, IsList ] );


#############################################################################
##
#C  IsMagmaRingModuloRelations( <obj> )
##
##  A {\GAP} object lies in the category `IsMagmaRingModuloRelations'
##  if it has been constructed as a magma ring modulo relations.
##  Each element of such a ring has a unique normal form,
##  so `CoefficientsAndMagmaElements' is well-defined for it.
##
##  This category is not inherited to factor structures,
##  which are in general best described as finitely presented algebras,
##  see Chapter~"Finitely Presented Algebras".
##
DeclareCategory( "IsMagmaRingModuloRelations", IsFLMLOR );


#############################################################################
##
#C  IsFreeMagmaRing( <D> )
##
##  A domain lies in the category `IsFreeMagmaRing' if it has been
##  constructed as a free magma ring.
##  In particular, if <D> lies in this category then the operations
##  `LeftActingDomain' (see~"LeftActingDomain") and `UnderlyingMagma'
##  (see~"UnderlyingMagma") are applicable to <D>,
##  and yield the ring $R$ and the magma $M$
##  such that <D> is the magma ring $RM$.
##
##  So being a magma ring in {\GAP} includes the knowledge of the ring and
##  the magma.
##  Note that a magma ring $RM$ may abstractly be generated as a magma ring
##  by a magma different from the underlying magma $M$.
##  For example, the group ring of the dihedral group of order $8$
##  over the field with $3$ elements is also spanned by a quaternion group
##  of order $8$ over the same field.
##  \beginexample
##  gap> d8:= DihedralGroup( 8 );
##  <pc group of size 8 with 3 generators>
##  gap> rm:= FreeMagmaRing( GF(3), d8 );
##  <algebra-with-one over GF(3), with 3 generators>
##  gap> emb:= Embedding( d8, rm );;
##  gap> gens:= List( GeneratorsOfGroup( d8 ), x -> x^emb );;
##  gap> x1:= gens[1] + gens[2];;
##  gap> x2:= ( gens[1] - gens[2] ) * gens[3];;
##  gap> x3:= gens[1] * gens[2] * ( One( rm ) - gens[3] );;
##  gap> g1:= x1 - x2 + x3;;
##  gap> g2:= x1 + x2;;
##  gap> q8:= Group( g1, g2 );;
##  gap> Size( q8 );
##  8
##  gap> ForAny( [ d8, q8 ], IsAbelian );
##  false
##  gap> List( [ d8, q8 ], g -> Number( AsList( g ), x -> Order( x ) = 2 ) );
##  [ 5, 1 ]
##  gap> Dimension( Subspace( rm, q8 ) );
##  8
##  \endexample
##
DeclareCategory( "IsFreeMagmaRing", IsMagmaRingModuloRelations );


#############################################################################
##
#C  IsFreeMagmaRingWithOne( <obj> )
##
DeclareSynonym( "IsFreeMagmaRingWithOne",
    IsFreeMagmaRing and IsMagmaWithOne );


#############################################################################
##
#P  IsGroupRing( <obj> )
##
##  A *group ring* is a magma ring where the underlying magma is a group.
##
DeclareProperty( "IsGroupRing", IsFreeMagmaRing );


#############################################################################
##
#A  UnderlyingMagma( <RM> )
##
DeclareAttribute( "UnderlyingMagma", IsFreeMagmaRing );


#############################################################################
##
#O  ElementOfMagmaRing( <Fam>, <zerocoeff>, <coeffs>, <mgmelms> )
##
##  `ElementOfMagmaRing' returns the element $\sum_{i=1}^n c_i m_i^{\prime}$,
##  where $<coeffs> = [ c_1, c_2, \ldots, c_n ]$ is a list of coefficients,
##  $<mgmelms> = [ m_1, m_2, \ldots, m_n ]$ is a list of magma elements,
##  and $m_i^{\prime}$ is the image of $m_i$ under an embedding
##  of a magma containing $m_i$ into a magma ring
##  whose elements lie in the family <Fam>.
##  <zerocoeff> must be the zero of the coefficient ring
##  containing the $c_i$.
##
DeclareOperation( "ElementOfMagmaRing",
    [ IsFamily, IsRingElement, IsHomogeneousList, IsHomogeneousList ] );


#############################################################################
##
#F  FreeMagmaRing( <R>, <M> )
##
##  is a free magma ring over the ring <R>, free on the magma <M>.
##
DeclareGlobalFunction( "FreeMagmaRing" );


#############################################################################
##
#F  GroupRing( <R>, <G> )
##
##  is the group ring of the group <G>, over the ring <R>.
##
DeclareGlobalFunction( "GroupRing" );


#############################################################################
##
#A  AugmentationIdeal( <RG> )
##
##  is the augmentation ideal of the group ring <RG>,
##  i.e., the kernel of the trivial representation of <RG>.
##
DeclareAttribute( "AugmentationIdeal", IsFreeMagmaRing );


#############################################################################
##
#F  MagmaRingModuloSpanOfZero( <R>, <M>, <z> )
##
##  Let <R> be a ring, <M> a magma, and <z> an element of <M> with the
##  property that $<z> \* m = <z>$ for all $m \in M$.
##  The element <z> could be called a ``zero element'' of <M>,
##  but note that in general <z> cannot be obtained as `Zero( $m$ )'
##  for each $m \in M$, so this situation does not match the definition of
##  `Zero' (see~"Zero").
##
##  `MagmaRingModuloSpanOfZero' returns the magma ring $<R><M>$ modulo
##  the relation given by the identification of <z> with zero.
##  This is an example of a magma ring modulo relations,
##  see~"Magma Rings modulo Relations".
##
DeclareGlobalFunction( "MagmaRingModuloSpanOfZero" );


#############################################################################
##
#C  IsMagmaRingModuloSpanOfZero( <RM> )
##
DeclareCategory( "IsMagmaRingModuloSpanOfZero", IsMagmaRingModuloRelations );


#############################################################################
##
#C  IsElementOfMagmaRingModuloSpanOfZeroFamily( <Fam> )
##
##  We need this for the normalization method, which takes a family as first
##  argument.
##
DeclareCategory( "IsElementOfMagmaRingModuloSpanOfZeroFamily",
    IsElementOfMagmaRingModuloRelationsFamily );


#############################################################################
##
##  3. Free left modules in magma rings modulo relations
##


#############################################################################
##
#F  IsSpaceOfElementsOfMagmaRing( <V> )
##
##  If an $F$-vector space <V> is in the filter
##  `IsSpaceOfElementsOfMagmaRing' then this expresses that <V> consists of
##  elements in a magma ring modulo relations, and that <V> is
##  handled via the mechanism of nice bases (see~"...") in the following way.
##  Let $V$ be a free $F$-module of elements in a magma ring modulo relations
##  $FM$, and let $S$ be the set of magma elements that occur in the
##  vector space generators of $V$.
##  Then the `NiceFreeLeftModuleInfo' value of <V> is a record with the
##  following components.
##  \beginitems
##  `family' : &
##     the elements family of <V>,
##
##  `monomials' : &
##     the list $S$ of magma elements that occur in elements of <V>,
##
##  `zerocoeff' : &
##     the zero coefficient of elements in <V>,
##
##  `zerovector' : &
##     the zero row vector in the nice left module.
##  \enditems
##  The `NiceVector' value of $v \in <V>$ is defined as the row vector of
##  coefficients of $v$ w.r.t.~$S$.
##
##  Finite dimensional free left modules of elements in a magma ring modulo
##  relations (*not* the magma rings themselves, they have special methods)
##  are by default handled via the mechanism of nice bases.
##
DeclareHandlingByNiceBasis( "IsSpaceOfElementsOfMagmaRing",
    "for free left modules of magma rings modulo relations" );


#############################################################################
##
#E

