Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind
[Top of Book] [Contents] [Previous Chapter] [Next Chapter]

[MathJax on]

65 Magma Rings
65.1 Free Magma Rings
65.1-1 FreeMagmaRing
65.1-2 GroupRing
65.1-3 IsFreeMagmaRing
65.1-4 IsFreeMagmaRingWithOne
65.1-5 IsGroupRing
65.1-6 UnderlyingMagma
65.1-7 AugmentationIdeal
65.2 Elements of Free Magma Rings
65.2-1 IsMagmaRingObjDefaultRep
65.2-2 IsElementOfFreeMagmaRing
65.2-3 IsElementOfFreeMagmaRingFamily
65.2-4 CoefficientsAndMagmaElements
65.2-5 ZeroCoefficient
65.2-6 ElementOfMagmaRing
65.3 Natural Embeddings related to Magma Rings
65.4 Magma Rings modulo Relations
65.4-1 IsElementOfMagmaRingModuloRelations
65.4-2 IsElementOfMagmaRingModuloRelationsFamily
65.4-3 NormalizedElementOfMagmaRingModuloRelations
65.4-4 IsMagmaRingModuloRelations
65.5 Magma Rings modulo the Span of a Zero Element
65.5-1 IsElementOfMagmaRingModuloSpanOfZeroFamily
65.5-2 IsMagmaRingModuloSpanOfZero
65.5-3 MagmaRingModuloSpanOfZero
65.6 Technical Details about the Implementation of Magma Rings

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

    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.

    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-11)) explicitly whenever one needs for example the magma ring element corresponding to a given magma element.

    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 R M 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.

    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 generator>
    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 generator>
    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 `\<`.

[Top of Book] [Contents] [Previous Chapter] [Next Chapter]
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

generated by GAPDoc2HTML