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 [Celler et al., 1995], 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: Homomorphism Speed (ex-827c15)#

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

Run in calculator

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

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

Run in calculator

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

Run in calculator