Documentation

Set-Theoretic Operations

Membership and Equality

g in G : GrpSLPElt, GrpSLP -> BoolElt

Given a straight-line program g and an SLP-group G, return true if g is an element of G, false otherwise.

g notin G : GrpSLPElt, GrpSLP -> BoolElt

Given an straight-line program g and an SLP-group G, return true if g is not an element of G, false otherwise.

S subset G : { GrpSLPElt } , GrpSLP -> BoolElt

Given a group G and a set S of elements belonging to a group H, where G and H are related, return true if S is a subset of G, false otherwise.

S notsubset G : { GrpSLPElt } , GrpSLP -> BoolElt

Given a group G and a set S of elements belonging to a group H, where G and H are related, return true if S is not a subset of G, false otherwise.

Set Operations

RandomProcess(G) : GrpSLP -> Process

    Slots: RngIntElt                    Default: 10

    Scramble: RngIntElt                 Default: 100

Create a process to generate randomly chosen elements from the group G. The process is based on the product-replacement algorithm of [CLGM+95], modified by the use of an accumulator. At all times, N elements are stored where N is the maximum of the specified value for Slots and Ngens(G) + 1. Initially, these are just the generators of G. As well, one extra group element is stored, the accumulator. Initially, this is the identity. Random elements are now produced by successive calls to Random(P), where P is the process created by this function. Each such call chooses one of the elements in the slots and multiplies it into the accumulator. The element in that slot is replaced by the product of it and another randomly chosen slot. The random value returned is the new accumulator value. Setting Scramble := m causes m such operations to be performed before the process is returned.
It should be noted that this process is not suitable for infinite groups, since all elements produced are products of the generators only and not their inverses. However, as long as the homomorphic image of G that is being worked with is finite, there is no problem.

Random(P) : Process -> GrpSLPElt

Given a random element process P created by the function RandomProcess(G) for the SLP-group G, construct a random element of G by forming a random product over the expanded generating set stored as part of the process. The expanded generating set stored with the process is modified by replacing an existing generator by the element returned.

Rep(G) : GrpSLP -> GrpSLPElt

A representative element of G.

Example `GrpSLP_HomomorphismSpeed (H83E3)`

As an illustration of the efficiency of computing homomorphisms from SLP-groups, we set up the same random expression as both a straight-line program and a linear word.

> G := SLPGroup(3);
> F := FreeGroup(3);
> M := GeneralOrthogonalGroup(7, 3);
> gf := hom<G -> F | F.1, F.2, F.3>;
> gm := hom<G -> M | M.1, M.2, M.3>;
> fm := hom<F -> M | M.1, M.2, M.3>;
> P := RandomProcess(G);
> x := Random(P);
> #x;
85

The evaluation of the straight-line program will take 85 operations in M.

> w := gf(x);
> #w;
52307

The evaluation of the word will take 52306 multiplications in M.

> time h1 := gm(x);
Time: 0.020
> time h2 := fm(w);
Time: 1.640
> h1 eq h2;
true

Coercions Between Related Groups

G ! g : GrpSLP, GrpSLPElt -> GrpSLPElt

Given an element g belonging to an SLP-group H related to the group G, rewrite g as an element of G.

V2.28, 13 July 2023

Contents