gap-online-help 4r7p9-1 / usr / share / gap / doc / ref / chap65.txt

  
  65 Magma Rings
  
  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 ∑_{i ∈ I} r_i m_i with r_i
  ∈  R,  and m_i ∈ 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
  
      (multivariate) polynomial rings (see 66.15), where the magma is a free
        abelian monoid generated by the indeterminates,
  
      group rings (see IsGroupRing (65.1-5)), where the magma is a group,
  
      Laurent  polynomial  rings,  which are group rings of the free abelian
        groups generated by the indeterminates,
  
      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.
  
  Note  that  formally,  polynomial  rings  in GAP are not constructed as free
  magma rings.
  
  Furthermore,  a  free  Lie  algebra  is  not  a  magma  ring, because of the
  additional   relations   given  by  the  Jacobi  identity;  see 65.4  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 65.3).  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.
  
    Example  
    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
  
  
  
  65.1 Free Magma Rings
  
  65.1-1 FreeMagmaRing
  
  FreeMagmaRing( R, M )  function
  
  is a free magma ring over the ring R, free on the magma M.
  
  65.1-2 GroupRing
  
  GroupRing( R, G )  function
  
  is the group ring of the group G, over the ring R.
  
  65.1-3 IsFreeMagmaRing
  
  IsFreeMagmaRing( D )  Category
  
  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  (57.1-11)  and  UnderlyingMagma  (65.1-6)  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.
  
    Example  
    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
  
  
  65.1-4 IsFreeMagmaRingWithOne
  
  IsFreeMagmaRingWithOne( obj )  Category
  
  IsFreeMagmaRingWithOne  is  just  a  synonym for the meet of IsFreeMagmaRing
  (65.1-3) and IsMagmaWithOne (35.1-2).
  
  65.1-5 IsGroupRing
  
  IsGroupRing( obj )  property
  
  A group ring is a magma ring where the underlying magma is a group.
  
  65.1-6 UnderlyingMagma
  
  UnderlyingMagma( RM )  attribute
  
  stores the underlying magma of a free magma ring.
  
  65.1-7 AugmentationIdeal
  
  AugmentationIdeal( RG )  attribute
  
  is  the  augmentation  ideal  of  the group ring RG, i.e., the kernel of the
  trivial representation of RG.
  
  
  65.2 Elements of Free Magma Rings
  
  In  order  to  treat elements of free magma rings uniformly, also without an
  external   representation,   the   attributes   CoefficientsAndMagmaElements
  (65.2-4) and ZeroCoefficient (65.2-5) 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  (65.2-6) can be used. (Of course one can also
  embed  each  magma  element into the magma ring, see 65.3, and then form the
  linear  combination,  but many unnecessary intermediate elements are created
  this way.)
  
  65.2-1 IsMagmaRingObjDefaultRep
  
  IsMagmaRingObjDefaultRep( obj )  Representation
  
  The default representation of a magma ring element is a list of length 2, at
  first  position  the  zero  coefficient,  at second position a list with the
  coefficients  at  the  even  positions,  and  the  magma elements at the odd
  positions, with the ordering as defined for the magma elements.
  
  It  is  assumed  that  arithmetic  operations  on  magma  rings produce only
  normalized elements.
  
  65.2-2 IsElementOfFreeMagmaRing
  
  IsElementOfFreeMagmaRing( obj )  Category
  IsElementOfFreeMagmaRingCollection( obj )  Category
  
  The  category  of  elements  of  a  free  magma  ring  (See  IsFreeMagmaRing
  (65.1-3)).
  
  65.2-3 IsElementOfFreeMagmaRingFamily
  
  IsElementOfFreeMagmaRingFamily( Fam )  Category
  
  Elements  of  families  in  this  category have trivial normalisation, i.e.,
  efficient methods for \= and \<.
  
  65.2-4 CoefficientsAndMagmaElements
  
  CoefficientsAndMagmaElements( elm )  attribute
  
  is  a list that contains at the odd positions the magma elements, and at the
  even positions their coefficients in the element elm.
  
  65.2-5 ZeroCoefficient
  
  ZeroCoefficient( elm )  attribute
  
  For  an  element  elm of a magma ring (modulo relations) RM, ZeroCoefficient
  returns the zero element of the coefficient ring R.
  
  65.2-6 ElementOfMagmaRing
  
  ElementOfMagmaRing( Fam, zerocoeff, coeffs, mgmelms )  operation
  
  ElementOfMagmaRing  returns the element ∑_{i = 1}^n c_i m_i', where coeffs =
  [ c_1, c_2, ..., c_n ] is a list of coefficients, mgmelms = [ m_1, m_2, ...,
  m_n  ]  is  a  list of magma elements, and m_i' 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.
  
  
  65.3 Natural Embeddings related to 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 (32.2-10))
  explicitly   whenever   one   needs  for  example  the  magma  ring  element
  corresponding to a given magma element.
  
    Example  
    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
  
  
  
  65.4 Magma Rings modulo Relations
  
  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 (64.2-4)).
  
  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 63.
  
  65.4-1 IsElementOfMagmaRingModuloRelations
  
  IsElementOfMagmaRingModuloRelations( obj )  Category
  IsElementOfMagmaRingModuloRelationsCollection( obj )  Category
  
  This category is used, e. g., for elements of free Lie algebras.
  
  65.4-2 IsElementOfMagmaRingModuloRelationsFamily
  
  IsElementOfMagmaRingModuloRelationsFamily( Fam )  Category
  
  The  family  category  for  the category IsElementOfMagmaRingModuloRelations
  (65.4-1).
  
  65.4-3 NormalizedElementOfMagmaRingModuloRelations
  
  NormalizedElementOfMagmaRingModuloRelations( F, descr )  operation
  
  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
  (65.2-4) 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.
  
  65.4-4 IsMagmaRingModuloRelations
  
  IsMagmaRingModuloRelations( obj )  Category
  
  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  (65.2-4) 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 63.
  
  
  65.5 Magma Rings modulo the Span of a Zero Element
  
  65.5-1 IsElementOfMagmaRingModuloSpanOfZeroFamily
  
  IsElementOfMagmaRingModuloSpanOfZeroFamily( Fam )  Category
  
  We  need  this  for  the normalization method, which takes a family as first
  argument.
  
  65.5-2 IsMagmaRingModuloSpanOfZero
  
  IsMagmaRingModuloSpanOfZero( RM )  Category
  
  The category of magma rings modulo the span of a zero element.
  
  65.5-3 MagmaRingModuloSpanOfZero
  
  MagmaRingModuloSpanOfZero( R, M, z )  function
  
  Let R be a ring, M a magma, and z an element of M with the property that z *
  m  =  z holds for all m ∈ 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 ∈
  M, so this situation does not match the definition of Zero (31.10-3).
  
  MagmaRingModuloSpanOfZero  returns  the  magma  ring  RM modulo the relation
  given  by  the  identification of z with zero. This is an example of a magma
  ring modulo relations, see 65.4.
  
  
  65.6 Technical Details about the Implementation of Magma Rings
  
  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 (65.1-1) 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.
  
    Example  
    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
  
  
  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  (62.3-1),
  FreeAssociativeAlgebra    (62.3-3),    FreeAlgebraWithOne    (62.3-2),   and
  FreeAssociativeAlgebraWithOne (62.3-4) 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 Chapter
   66) as well as the default representation IsMagmaRingObjDefaultRep (65.2-1)
  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 \<.