Example Grp_RandomOperations (H64E21)

> G := WreathProduct(Sym(4), CyclicGroup(6));
> G;
Permutation group G acting on a set of cardinality 24
    (1, 5, 9, 13, 17, 21)(2, 6, 10, 14, 18, 22) (3, 7, 11, 15, 19, 23)
        (4, 8, 12, 16, 20, 24)
    (1, 2, 3, 4)
    (1, 2)
> Order(G);
1146617856
> Random(G);
(1, 17, 12, 4, 18, 10, 3, 20, 9, 2, 19, 11)(5, 22, 13, 6, 21, 15)
    (7, 24, 16)(8, 23, 14)
// We display the cycle structures of 10 random elements of G
> R := [ CycleStructure(Random(G)) : i in [1..10] ];
> R;
[
    [ <6, 1>, <3, 6> ],
    [ <9, 1>, <6, 2>, <3, 1> ],
    [ <9, 2>, <3, 2> ],
    [ <12, 1>, <9, 1>, <3, 1> ],
    [ <18, 1>, <6, 1> ],
    [ <18, 1>, <6, 1> ],
    [ <12, 1>, <6, 2> ],
    [ <6, 3>, <2, 3> ],
    [ <6, 1>, <4, 3>, <2, 3> ],
    [ <6, 3>, <3, 2> ]
]

RandomProcess(G) : GrpFin -> Process

RandomProcessWithWords(G) : GrpFin -> Process

RandomProcessWithValues(G, Q) : GrpFin, SeqEnum -> Process

RandomProcessWithWordsAndValues(G, Q) : GrpFin, SeqEnum ->Process

    Slots: RngIntElt                    Default: 10

    Scramble: RngIntElt                 Default: 50

    WordGroup: GrpSLP                   Default: 

Create a process to generate randomly chosen elements from the group G. The process uses a variant of the product-replacement method similar to the Rattle method of [LGM02]. The generating set stored in the process has N elements, where N is the maximum of the specified value for Slots and Ngens(G) + 1. Initially they are the generators of G repeated as necessary and the accumulator 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 returns the current value of the accumulator, modifying the generating set as for product-replacement, and modifying the accumulator by multiplying by the new member of the generating set. Setting Scramble := m causes m such operations to be performed before the process is returned.

The functions with words and values create a process that returns extra group elements for each call. A process created with words returns, as second return value for each call to Random(P), the GrpSLPElt describing the random element returned as a straight-line program in the group generators. The parameter WordGroup may be used to specify a particular group for the words to be elements of.

A process created with values takes as input a sequence of group elements Q giving the values assigned to each generator of G. The second value returned is the result of computing in parallel with these values as with the generators of G. In particular, if the elements of Q are homomorphic images of the generators of G, then the second return value from Random(P) will be the image of the first under this homomorphism.

A process created with words and values does all of the above, with the three return values of Random(P) being a random element of G, the straight-line program and the value.

The use of this function on a finitely-presented group G is not recommended. Since there is no reduction of words, the random elements generated may be extremely long.

Random(P) : Process -> GrpFinElt

Given a random element process P created by the function RandomProcess(G) for the finite group G, construct a random element of G by forming a random product over the expanded generating set constructed when the process was created. For large permutation or matrix groups for which a BSGS is not known, this function should be used in preference to Random(G).

If the process was created with words or values then there will be second and third return values as described under RandomProcess above.

Random(P) : Process -> GrpFinElt

Given a random element process P created by the function RandomProcess(G) for the finite group G, return G.

InitialiseProspector(G:parameters): GrpMat ->

InitialiseProspector(G:parameters): GrpPerm ->

Initialise a product-replacement prospector for the given group. This is an extension of the product-replacement algorithm that searches for an element x∈G such that some predicate is true for this element. The prospector aims to find elements x so that the corresponding straight-line program for x is short. Statistical tests and various heuristics are used to achieve this.

Generally, output from product-replacement with short straight-line programs is not very random. Prospector aims to run product-replacement until the output looks random, then start a search for the element wanted. At all times, if the output starts to look non-random, or word lengths grow too far without finding an element, the prospector may return to a previous state of product replacement and try again, searching in a different direction. The statistical tests are used to make concrete the notion of "looks random". For permutation groups the test used is based on number of cycles of the element. For matrix groups the test statistic is the number of factors of the characteristic polynomial.

Prospector(G, f:parameters): Grp, UserProgram -> BoolElt, GrpElt, GrpSLPElt

Run an initialised prospector for group G to find x∈G such that f(x) is true. The first return value gives the success or failure of the search. If this value is true, then the second and third return values are x and a straight-line program giving x in terms of the group generators. The parameter texttt{MaxTries} may be set to limit the number of random selections made by the prospector when attempting to find x.

> SetSeed(1);
> S := Sym(300);
> repeat G := sub<S|Random(S),Random(S)>;
> until IsSymmetric(G);
> P := RandomProcessWithWords(G);
> repeat x,w := Random(P);
> until CycleStructure(x) eq [<300,1>];
> #w;
936

> InitialiseProspector(G);
true
> test := func<x|CycleStructure(x) eq [<300,1>]>;
> repeat a,x,w := Prospector(G, test); until a;
> #w;
206
> Evaluate(w, [G.1,G.2]) eq x;
true