• « Previous
• Up
• Contents
• Index
• Search
• Next »

Vector Enumeration

Vector enumeration (originally misnamed module enumeration) is an algorithm for converting a finitely-presented module for a finitely-presented algebra into a concrete vector space on which the algebra has explicit matrix action. The algebra may be the group algebra of an fp-group, in which case the resulting module will be a matrix representation of the group, or it might be a more general fp-algebra, such as a Hecke algebra or a quotient of a polynomial ring.

Finitely Presented Modules

For a ring R, let M be an R-module M, generated as an R-module by s elements {m₁, ..., m_s}. There is an R-module epimorphism ψ: R^s |-> M, given by (r₁, ..., r_s) |-> m₁r₁ + ... + m_sr_s. This shows that M is isomorphic to A^s/kerψ.

If kerψ is generated as an R-module by a finite set L then we will say that M is presented by s generators and the relators L.

S-algebras

Suppose there is another ring S, equipped with a ring homomorphism φ: S |-> R, such that φ(S) is central in R. In this situation any R-module can be described as an S-module, on which R acts as a ring of S-module endomorphisms. We say that R is an S-algebra. In particular, when S is a field k, any R-module is a k-vector space. If such a module V has finite k-dimension n, then V is characterised by this dimension and R will act on it as a subring of M_n(k).

Finitely Presented Algebras

Given a finite set X, and a ring S, we can define the free S-algebra A generated by X. This can be seen either as the monoid algebra of the free monoid of words in X, or as all expressions in X and k, combined by addition and multiplication.

Given a finite set R⊂A we can define P = (A/< ARA >). We say that P is a finitely-presented S-algebra, with generators X and relators R, and write it P = < X | R >.

The monoid algebra of any finitely-presented monoid (or group, of course) is finitely-presented, since k< X | l₁ = r₁, ..., l_k=r_k >_((monoid)) = < X | l₁ - r₁, ..., l_k - r_k >_{k- algebra}. Furthermore, any quotient of a finitely-presented algebra by a finitely-generated two-sided ideal is finitely-presented. This gives us the general form of a finitely-presented algebra in Magma, as the quotient of the monoid algebra of an fp-monoid, by the two-sided ideal generated by some additional relators.

Vector Enumeration

The vector enumeration algorithm explicitly reconciles these two descriptions of an R-module, in the case where R is a finitely presented k-algebra for a field k, and M is a finitely presented R-module, which also has finite k-dimension.

Given the presentation of R as k-algebra, and that of M as R-module, it computes the k-dimension of M and the matrices giving the action of the generators of R on M. If M has infinite k-dimension the algorithm will fail to terminate.

a = [ 0 0 1 0 ]
    [ 1 0 0 0 ]
    [ 0 0 0 1 ]
    [ 0 1 0 0 ]
b = [ 1 0 0 0 ]
    [ 0 0 1 0 ]
    [ 0 1 0 0 ]
    [ 0 0 0 1 ]

a = [  0  0  0  1  0  0  0 ]
    [  0  0  0  0  0  0  1 ]
    [  1  0  0  0  0  0  0 ]
    [  0  0  0  0  1  0  0 ]
    [  0  0  1  0  0  0  0 ]
    [  0  1  0  0  0  0  0 ]
    [  1 -1  1  1  1 -1 -1 ]
b = [  1  0  0  0  0  0  0 ]
    [  0  1  0  0  0  0  0 ]
    [  0  0  0  1  0  0  0 ]
    [  0  0  1  0  0  0  0 ]
    [  0  0  0  0  1  0  0 ]
    [  0  0  0  0  0  0  1 ]
    [  0  0  0  0  0  1  0 ]

The Isomorphism

In determining the k-dimension of M, and giving matrices representing the action of R on M, the algorithm is, in effect, constructing a k-vector space, on which R has matrix action, and which is R-module isomorphic to M, which is formally a quotient module of R^s. The algorithm also computes this isomorphism, giving images in the vector space for the s standard generators of R^s and pre-images in R^s of the basis of the vector space.

In example (1) above, we find that the module generator has image (1, 0, 0, 0), while the basis vectors have pre-images 1, a', a'² and b.

In example (3) the images of the two module generators are (1, 0, 0, 0, 0, 0, 0) and (0, 1, 0, 0, 0, 0, 0) while the basis vectors are images of (1, 0), (0, 1), (a', 0) ,(a, 0), (a², 0), (0, a') and (0, a).

Sketch of the Algorithm

The algorithm is based on the Haselgrove-Leech-Trotter (HLT) version of the Todd-Coxeter algorithm, which we consider as a means of constructing the permutation representation of a finitely-presented group on the cosets of a finitely generated subgroup.

The algorithm proceeds by manipulating a partial action of the free algebra on a vector space. This is represented as a table, with columns indexed by the generators of the algebra, and rows indexed by the basis of the space. Each entry is either a vector or bot, signifying that no action is given.

We can extend this to a "complete action with side-effects", by adding a new row to the table whenever needed. We call this the action with defining.

The action of the fp-algebra P on M gives an action for the free algebra A, and our objective is to modify out partial action until it becomes this action. We know certain things about this action, which drive our modification process:

1.

It is a complete action.

2.

The relators of P annihilate every vector.

3.

The images in the space of the relators of M are zero.

4.

The space contains images of the R-module generators of M.

We now start to exploit the second fact about M, constructing the action (with defining) of the relators of P, on the basis vectors, and applying the resulting coincidences. This process may not terminate, as we are defining new basis vectors on the one hand, and removing them through coincidences on the other. It is possible to prove, however, that if M is in fact finite-dimensional then the process will terminate.

The first fact is applied by adding the relators x - x for each x∈X to the relators of P, so that the image of every basis vector under each x is sure to be defined.

Weights

The above sketch leaves open the question of the order in which the relators are applied to the basis vectors. The proof that the algorithm completes when M is finite-dimensional imposes some rather loose constraints, but within these constraints there is considerable choice.

The implementation in Magma uses a system of weights. Each relator r is assigned a weight w_r by the user, and each basis vector e has a weight w_e. There is a current weight w, which increases as the computation progresses, and at weight w all basis vector, relator pairs (b, r) such that w_b + w_r ≤w, which have not been processed already, are processed. New basis vectors defined during this process are assigned weight w. The initial basis vectors and those defined during processing of the submodule generators are assigned weight 1. See below for details of how to set the weights, and their default values.

Setup Functions

For V2.11, the following functions create the old representation for fp-algebras which are necessary for the Vector Enumeration algorithm. These are compatible with older versions of Magma. See the examples below for examples of how to use these functions.

FreeAlgebra(R, M) : Rng, MonFP -> AlgFPOld

FreeAlgebra(R, G) : Rng, GrpFP -> AlgFPOld

Construct the special fp-algebra over the ring R and the monoid M or the group G, for use in the Vector Enumeration algorithm.

The Quotient Module Function

QuotientModule(A, S) : AlgFPOld, AlgFPOld -> [AlgMatElt], [ModTupFldElt], [AlgFPEltOld]

Given an fp-k-algebra A, for a field k, with r generators, and a submodule N of the free A-module of rank s specified by S, construct an A-module isomorphic to the quotient module A^s/N together with the isomorphism.

The three values returned are:

M

a sequence of r n x n matrices with entries in k;

I

a sequence of s vectors of length n with entries in k;

P

a sequence of n elements of the free A-module A^s.

The matrices M specify a homomorphism from A to End_k(kⁿ), under which kⁿ becomes an A-module isomorphic to A^s/N. That isomorphism is given in one direction by the vectors I, which are the images in kⁿ of the s generators (1, 0, ..., 0), (0, 1, 0, ..., 0), ..., (0, ..., 0, 1) of A^s. In the other direction, the elements P give representatives for the images in A^s/N of the images of the n standard basis elements of kⁿ.

The submodule N may be specified by the parameter S in three ways:

(1)

S may simply be N, a finitely generated submodule of a free A-module (except that such an object cannot currently be created).

(2)

S may be a finitely generated right ideal of A, in which case s = 1 and N is S considered as a submodule of A considered as a right module for itself.

(3)

S may be a sequence of elements of a free A-module A^s, in which case N is the submodule that they generate (this is a stand in for 1 and could be removed when 1 is implemented).

Structuring Presentations

The relations used by the vector enumeration algorithm come from three sources:

(1)

The relations of the fp-group or fp-monoid underlying A.

(2)

The relations of A itself.

(3)

The generators of N.

This greatly improves the performance of the algorithm, and so users are recommended to ensure as far as possible that:

(1)

If the underlying monoid of an fp-algebra is in fact an fp-group then it should be presented to Magma as such.

(2)

Relations which can be written as equations between monomials should be given as relations of the underlying monoid, rather than as relations of the algebra.

Options and Controls

The QuotientModule function supports a large selection of optional arguments.

Weights

The processing of the relations of A by the vector enumeration algorithm depends on weights which are assigned to those relations (see above). The higher the weight of a relation the later it will be processed. By default, all relations are given weight 3, except those arising from relators of an fp-group, which are given weight equal to half the length of the relator.

Separate weights are used in lookahead mode, with the same default values.

QuotientModule(A, S) : AlgFP, AlgFP -> AlgFP

     MonomialWeights: [ RngIntElt ]      Default:

     MonWts: [ RngIntElt ]               Default:

This option sets the sequence of weights for the relations derived from the relations of the underlying monoid of A. The weights w₁, w₂, etc. are applied to the relations in the order in which they appear. If there are fewer weights than relations the remaining relations are assigned the default weight; if there are more weights than relations the extra weights are silently discarded.

Unless the MonomialLookaheadweights or MonLWts parameters are present, these weights are also used in lookahead mode.

     MonomialLookaheadWeights: [ RngIntElt ] Default:

     MonLWts: [ RngIntElt ]              Default:

This option sets the sequence of weights for the relations derived from the relations of the underlying monoid of A in lookahead mode only. It is otherwise similar to MonomialWeights.

     AlgebraWeights: [ RngIntElt ]       Default:

     AlgWts: [ RngIntElt ]               Default:

This option sets the sequence of weights for the relations given explicitly as relations of the algebra A. It is otherwise similar to MonomialWeights.

     AlgebraLookaheadWeights: [ RngIntElt ] Default:

     AlgLWts: [ RngIntElt ]              Default:

This option sets the sequence of weights for the relations given explicitly as relations of the algebra A in lookahead mode only. It is otherwise similar to AlgebraWeights.

Limits

QuotientModule(A, S) : AlgFP, AlgFP -> AlgFP

Options in this group set limits on the progress of the algorithm. If the calculation cannot be performed under these constraints the value undef is returned, unless the ErrorOnFail option was set, in which case a run-time error is generated.

     MaximumDimension: RngIntElt         Default: ∞

     MaxDim: [ RngIntElt ]               Default: ∞

This sets a limit of n on the dimension of the vector-space constructed, and on the dimension of the intermediate spaces used in the construction.

By default there is no limit, except for available memory.

     MaximumTime: FldReElt               Default: ∞

     MaxTime: FldReElt                   Default: ∞

This sets a limit on the CPU time available for the vector enumeration. The limit is given as a real number t and is measured in seconds.

This limit is only checked at certain points in the calculation, so it is possible for a vector enumeration to over-run, possibly by a significant amount.

By default, there is no limit.

     MaximumWeight: RngIntElt            Default: 100

     MaxWt: RngIntElt                    Default: 100

This sets a limit on the maximum weight of (basis vector, relation) pairs that will be used by the algorithm.

The weight of a basis vector is the weight of the pair that was being processed when it was defined. The weight of a pair is the weight of the basis vector plus the weight of the relation (see above).

The default limit is 100.

Logging

QuotientModule(A, S) : AlgFP, AlgFP -> AlgFP

There are a number of options to control the level of detail provided in the informational message from the vector enumerator. When multiple contradictory options are given the first one given takes precedence.

     NoLogging: BoolElt                  Default: false

     NoLog: BoolElt                      Default: false

     Silent: BoolElt                     Default: false

This option turns off all the informational messages produced by the vector enumerator.

     MaximumLogging: BoolElt             Default: false

     MaxLog: BoolElt                     Default: false

This option turns on the highest possible level of detail in the informational messages. This is too detailed for almost all purposes except debugging.

     LogActions: RngIntElt               Default: 0

     LogAct: RngIntElt                   Default: 0

This option sets the level of messages about the computation of the action of the algebra on the vector space under construction. At level 0 (the default) no messages are produced. All other levels produce copious output, with all levels above 2 being equivalent.

     LogCoincidences: RngIntElt          Default: 0

     LogCoin: RngIntElt                  Default: 0

This option sets the level of messages about the coincidences discovered and the processing of them. At level 0 (the default) no messages are produced. At level 1 every coincidence and deduction is recorded when it is discovered and when it is processed. At level 2 or higher the operation of finding the undeleted image of a vector is also recorded.

     LogInitialization: RngIntElt        Default: 0

     LogInitialisation: RngIntElt        Default: 0

     LogInit: RngIntElt                  Default: 0

This option sets the level of messages about the initialisation of new basis vectors. At level 0 (the default) no messages are produced. All other levels produce a message whenever a new basis vector is defined.

     LogPacking: RngIntElt               Default: 1

     LogPack: RngIntElt                  Default: 1

This option sets the level of messages about the reclamation of free space in the tables used by the algorithm. At level 0 no messages are produced. At level 1 (the default) it produces a message each time the pack routine is called. At level 2 or higher it records the exact renaming used to reclaim the space.

     LogPushes: RngIntElt                Default: 0

     LogPush: RngIntElt                  Default: 0

This option sets the level of messages about the pushing (or tracing) of (basis vector, relation) pairs. At level 0 (the default) it produces no messages. At level 1 a message is produced for each push that is started. At level 2 or higher the outcome of the push is also recorded.

     LogProgress: RngIntElt              Default: 0

     LogStages: RngIntElt                Default: 0

This option sets the level of messages about the overall progress of the algorithm. At level 0 no messages are produced. At level 1, simple messages are printed as the algorithm passes through its major stages. At level 2 the relations are printed as they are read in, and the complete action on the final module is printed. At level 3 or higher the action is also printed after the processing of submodule generators is complete.

     LogWeightChanges: RngIntElt         Default: 1

     LogWt: RngIntElt                    Default: 1

This option sets the level of messages about changes in the current weight (ie the weight of (basis vector, relation pairs) currently being pushed. At level 0 no such messages are produced. At level 1 (the default) or higher a message giving the new weight and the current dimension is printed.

Miscellaneous

QuotientModule(A, S) : AlgFP, AlgFP -> AlgFP

     Lookahead: BoolElt                  Default: true

This option controls whether, and to what extent, lookahead is used. If x is false then lookahead is not used. If x is true, the default, the lookahead by the default amount (two weights) is used. If x is a positive integer n then lookahead n weights is used. A sufficiently large value of n is equivalent to complete lookahead. Lookahead is commenced approximately every time the dimension doubles.

     EarlyClosing: BoolElt               Default: false

     Early: BoolElt                      Default: false

This option permits the algorithm to stop as soon as the table represents a complete action (but see below), without checking to see whether the action satisfies all the relations. In practice this action is usually correct. The default behaviour is to continue and check all the relations.

     EarlyClosingMinimum: RngIntElt      Default:

     ECMin: RngIntElt                    Default:

This option sets a minimum dimension at which the algorithm may stop without checking all the relators. It implies EarlyClosing.

     EarlyClosingMaximum: RngIntElt      Default:

     ECMax: RngIntElt                    Default:

This option sets a maximum dimension at which the algorithm aamy stop without checking all the relators. It implies EarlyClosing.

     ConstructMorphism: BoolElt          Default: true

     Morphism: BoolElt                   Default: true

This option controls whether the third return value of the QuotientModule function is in fact computed. A small overhead of time and space is required to compute it, and many applications do not need it, so this option is provided. When b is true (the default) the third return value is computed, when b is false it is not.

     ErrorOnFail: BoolElt                Default:

     ErrFail: BoolElt                    Default:

This option controls the behaviour of the program if there is insufficient time or space to complete the calculation, or if the calculation has not been completed when the maximum weight is reached. If it is present a run-time error is generated, otherwise the value undef is returned.

> d8<a,b> := Group<a,b | a^ 4 = b^ 2 = (a*b)^ 2 = 1>;
> q := RationalField();
> a1<a,b> := FreeAlgebra(q,d8);
> i1 := rideal<a1 | b-1 >;
> mats, im, preim := QuotientModule(a1,i1);
Read Input
Done submodule generators
Starting weight 2 in define mode, 1 alive out of 2
Starting weight 3 in define mode, 1 alive out of 2
Looking ahead ...
Starting weight 4 in lookahead mode, 4 alive out of 5
Starting weight 5 in lookahead mode, 4 alive out of 5
    ...done
Packing 5 to 4
Starting weight 4 in define mode, 4 alive out of 4
Starting weight 5 in define mode, 4 alive out of 4
Starting weight 6 in define mode, 4 alive out of 4
Starting weight 7 in define mode, 5 alive out of 6
Starting weight 8 in define mode, 6 alive out of 7
Starting weight 9 in define mode, 4 alive out of 7
Starting weight 10 in define mode, 4 alive out of 7
Closed, 7 rows defined
Packing 7 to 4
4 live dimensions
Successful
> mats;
[
    [0 0 1 0]
    [1 0 0 0]
    [0 0 0 1]
    [0 1 0 0],
    [1 0 0 0]
    [0 0 1 0]
    [0 1 0 0]
    [0 0 0 1]
]
> im;
[
    (1 0 0 0)
]
> preim;
[ Id(), a^ -1, a^ -1 * b, a^ -2 ]
>

> d8<a,b> := Group<a,b | a^ 4 = b^ 2 = (a*b)^ 2 = 1>;
> q := RationalField();
> a1<a,b> := FreeAlgebra(q,d8);
> i2 := rideal<a1 | b-1, 1+a^ 3+a^ 3*b+a^ 2>;
> mats, im, preim := QuotientModule(a1,i2);
Read Input
Done submodule generators
Starting weight 2 in define mode, 4 alive out of 6
Starting weight 3 in define mode, 5 alive out of 7
Starting weight 4 in define mode, 3 alive out of 7
Starting weight 5 in define mode, 3 alive out of 7
Closed, 7 rows defined
Packing 7 to 3
3 live dimensions
Successful
> mats;
[
    [ 0  1  0]
    [ 0  0  1]
    [-1 -1 -1],
    [ 1  0  0]
    [-1 -1 -1]
    [ 0  0  1]
]

• « Previous
• Up
• Contents
• Index
• Search
• Next »