The ALCO package provides some basic tools to compute the closure of a set with respect to a binary operation. Some of these tools compute the closure by brute force, while others use random selection of pairs to attempt to find new members not in the set.
‣ Closure( gens, op[, option] ) | ( function ) |
For gens satisfying IsHomogeneousList, this function computes the closure of gens by addition of all elements of the form op(x,y), starting with x and y any elements in gens. The function will not terminate until no new members are produced when applying op to all ordered pairs of generated elements. The argument option, if supplied, ensures that the function treats op as a commutative operation.
Caution must be exercised when using this function to prevent attempting to compute the closure of large or possibly infinite sets.
gap> Closure([1,E(7)], \*); [ 1, E(7)^6, E(7)^5, E(7)^4, E(7)^3, E(7)^2, E(7) ] gap> QuaternionD4Basis; Basis( <algebra-with-one of dimension 4 over Rationals>, [ (-1/2)*e+(-1/2)*i+(-1/2)*j+(1/2)*k, (-1/2)*e+(-1/2)*i+(1/2)*j+(-1/2)*k, (-1/2)*e+(1/2)*i+(-1/2)*j+(-1/2)*k, e ] ) gap> Closure(QuaternionD4Basis,\*); [ (-1)*e, (-1/2)*e+(-1/2)*i+(-1/2)*j+(-1/2)*k, (-1/2)*e+(-1/2)*i+(-1/2)*j+(1/2)*k, (-1/2)*e+(-1/2)*i+(1/2)*j+(-1/2)*k, (-1/2)*e+(-1/2)*i+(1/2)*j+(1/2)*k, (-1/2)*e+(1/2)*i+(-1/2)*j+(-1/2)*k, (-1/2)*e+(1/2)*i+(-1/2)*j+(1/2)*k, (-1/2)*e+(1/2)*i+(1/2)*j+(-1/2)*k, (-1/2)*e+(1/2)*i+(1/2)*j+(1/2)*k, (-1)*i, (-1)*j, (-1)*k, k, j, i, (1/2)*e+(-1/2)*i+(-1/2)*j+(-1/2)*k, (1/2)*e+(-1/2)*i+(-1/2)*j+(1/2)*k, (1/2)*e+(-1/2)*i+(1/2)*j+(-1/2)*k, (1/2)*e+(-1/2)*i+(1/2)*j+(1/2)*k, (1/2)*e+(1/2)*i+(-1/2)*j+(-1/2)*k, (1/2)*e+(1/2)*i+(-1/2)*j+(1/2)*k, (1/2)*e+(1/2)*i+(1/2)*j+(-1/2)*k, (1/2)*e+(1/2)*i+(1/2)*j+(1/2)*k, e ]
In many cases the Closure (6.1-1) function is impractical to use due to the long computation time of the brute force method. The following functions provide tools to generate more elements of a set under a binary operation without directly proving closure.
‣ RandomClosure( gens, op[, N[, print]] ) | ( function ) |
For gens satisfying IsHomogeneousList, this function selects a random element r in gens and computes all elements of the form op(r,x) for x either in gens or obtained in a previous closure step. Once this process yields a set of elements with equal cardinality N+1 times, the function terminates and returns all elements obtained so far as a set. The default value of N is 1. The optional print argument, if supplied, prints the cardinality of the set of elements obtain so far at each iteration.
Caution must be exercised when using this function to prevent attempting to compute the random closure of an infinite set. Caution is also required in interpreting the output. Even for large values of N, the result is not necessarily the full closure of set gens. Furthermore, repeated calls to this function may result in different outputs due to the random selection of elements involved throughout. If the size of the expected closed set is known, use of a repeat-until loop can permit generating the full set of elements faster than Closure (6.1-1) would.
gap> start := Basis(QuaternionAlgebra(Rationals)){[2,3]}; [ i, j ] gap> repeat > start := RandomClosure(start, \*); > until Length(start) = 8; gap> start; [ (-1)*e, (-1)*i, (-1)*j, (-1)*k, k, j, i, e ]
‣ RandomOrbitOnSets( gens, start, op[, N[, print]] ) | ( function ) |
This function proceeds in a manner very similar to RandomClosure (6.2-1) with the following differences. This function instead selects a random element r in gens and then for every x in start, or the set of previously generated elements, computes op(r,x). At each step the cardinality of the union of start and any previously generated elements is computed. Once the cardinality is fixed for N + 1 steps, the function returns the set of generated elements.
The same cautions as described in RandomClosure (6.2-1) apply. Note that while start is always a subset of the output, the elements of gens are not necessarily included in the output.
gap> start := Basis(QuaternionAlgebra(Rationals)){[1,2]}; [ e, i ] gap> gens := Basis(QuaternionAlgebra(Rationals)){[3]}; [ j ] gap> repeat > start := RandomOrbitOnSets(gens, start, {x,y} -> x*y); > until Length(start) = 8; gap> start; [ (-1)*e, (-1)*i, (-1)*j, (-1)*k, k, j, i, e ]
generated by GAPDoc2HTML