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.
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.
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 Mn(k).
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.
The monoid algebra of any finitely-presented monoid (or group, of
course) is
finitely-presented, since
k< X | l1 = r1, ..., lk=rk >_((monoid)) = < X | l1 - r1, ..., lk - rk >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.
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.
We consider some examples in the abstract. Below we will see how these
and other calculations may be performed in Magma.
- (1)
- A permutation module
In practice, it is always better to use the classical Todd-Coxeter
algorithm to construct permutation representations of groups.
We know that the group with presentation < a, b | a4 = b2 =
(ab)2 = 1 > is the dihedral group of order 8. Its group
algebra over any field k is thus the fp-k-algebra < a, b, a', b' | aa' - 1, a'a - 1, bb' - 1, b'b - 1, a4 - 1, b2 - 1, (ab)2 - 1 >.
The permutation module of degree 4 of this algebra is presented by one
generator (as it is transitive) and the submodule generator b - 1.
Applying the algorithm to this case we obtain the matrices
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 ]
and their inverses for a' and b'.
- (2)
- A quotient of a permutation module
Like all permutation modules, this one fixes the all-ones vector
(1, 1, 1, 1), which we can see to be an image of 1 + a'(1 + b + a'). We can
construct the quotient of the permutation module by this 1-dimensional
submodule by adding that word to the submodule generators. This gives
a = [ 0 0 1 ]
[ 1 0 0 ]
[ -1 -1 -1 ]
b = [ 1 0 0 ]
[ 0 0 1 ]
[ 0 1 0 ]
- (3)
- A non-cyclic module
A permutation module of a group-ring is cyclic (that is, generated as a
module by one element) just when the permutation representation is
transitive. An intransitive permutation representation can be easily
constructed from its transitive components, but in general it is not
so easy to construct an arbitrary module from cyclic submodules.
Accordingly it can be worthwhile to construct non-cyclic modules
directly.
As an example we take two copies of the representation constructed in
example one, and fuse their one-dimensional submodules. The generators
and relators are as before, and now s=2 and the submodule generators
are a2 =
{(b - 1, 0), (0, b - 1), (1 + a'(1 + a' + b), - 1 - a'(1 + a' + b))}. We obtain a
representation of degree seven, given by
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 ]
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 Rs. The algorithm also computes this
isomorphism, giving images in the vector space for the s standard
generators of Rs and pre-images in Rs 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'2
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), (a2, 0), (0, a') and (0, a).
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.
The algorithm begins by applying the fourth fact and creating s
linearly independent vectors. It then applies the third, computing the
action with defining of the relators of M (the set called L
above). The fact that these images should be zero gives a linear
dependence among our basis vectors (called a coincidence), which we
use to reduce their number. As we do this, we have to take care not to
lose the information already in the table, which may give rise to
further coincidences.
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.
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 wr by the user, and each basis vector e
has a weight we. 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 wb + wr ≤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.
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, 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.
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 As/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 As.
The matrices M specify a homomorphism from A to Endk(kn),
under which kn becomes an A-module isomorphic to As/N.
That isomorphism is given in one direction by the vectors I, which are the images in
kn of the s generators (1, 0, ..., 0), (0, 1, 0, ..., 0), ..., (0, ..., 0, 1) of As. In the other direction, the
elements P give representatives for the images in As/N of the
images of the n standard basis elements of kn.
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 As,
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).
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.
The third group play the same role as subgroup generators in the
Todd-Coxeter algorithm, and are treated specially, while the first
two groups are logically equivalent, forming the relations of A in
the variety of free finitely-generated associative algebras. However,
when the underlying monoid of A is actually an fp-group G, the vector
enumeration algorithm can use a more efficient technique to process the
relations of G, and can take advantage of the fact that the
generators of G are known to be invertible.
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.
The QuotientModule function supports a large selection of
optional arguments.
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.
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 w1, w2,
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.
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.
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.
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.
First we repeat the examples above, in Magma.
The permutation action of D
8 :
> 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 ]
>
A quotient of that module.
We continue from the last example and set:
> 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]
]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]