Given a straight-line program g and an SLP-group G, return true
if g is an element of G, false otherwise.
Given an straight-line program g and an SLP-group G, return true
if g is not an element of G, false otherwise.
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.
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.
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.
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.
A representative element of G.
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
Given an element g belonging to an SLP-group H related to the
group G, rewrite g as an element of G.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|