|
Unless otherwise noted, the functions in this section assume that a
BSGS-representation for the group can be constructed.
Unless the order is already known, each of the functions in this family will
create a base and strong generating set for the group if one does not already
exist.
Given a matrix group G, return whether G is finite together with
the order of G if G is finite.
The function rigorously proves
its result (i.e., the result is not probable).
Let R be the ring over which G is defined,
and let the degree of G be n.
If R is finite, then the first return value is trivially {true}.
If R is the integer ring or rational field,
then the function works as follows.
The function successively generates random elements of G and
tests whether each element has infinite order via the function
HasFiniteOrder; if so, then the non-finiteness of G is proven.
Otherwise, at regular intervals, the function attempts to construct
a positive definite form fixed by G (see the function
PositiveDefiniteForm in the chapter on matrix groups over Q and Z), using
a finite number of steps; if one is successively constructed,
then the finiteness of G is proven. The number of steps attempted
for the positive definite form constructed is increased as the algorithm
progresses; if G is finite, such a form must exist and will be found when
enough steps are tried, while if G is infinite, an element of infinite
order is found very quickly in practice.
If R is an algebraic number field of degree d over Q (including
cyclotomic and quadratic fields), then the standard companion matrix
blowup is applied to the generators of G to obtain an isomorphic
matrix group of (nd) over Q, and the above algorithm is then
applied to this matrix group.
# G : GrpMat -> RngIntElt
The order of the group G as an integer. If the order is not currently
known, a base and strong generating set will be constructed for G.
If G has infinite order, an error ensues.
The order of the group G returned as a factored integer. The format is
the same as for FactoredIndex. If the order of G is not known,
it will be computed.
If G has infinite order, an error ensues.
The exponent of the group G.
> G := MatrixGroup<2,Integers()|[1,1,0,1],[0,1,-1,0]>;
> IsFinite(G);
false
> G24, e := ChangeRing(G, Integers(24));
> Order(G24);
9216
> G.-1*G.2;
[ 1 1]
[-1 0]
> (G.-1*G.2) @ e;
[ 1 1]
[23 0]
> (G24.2^2) @@ e;
[23 0]
[ 0 23]
Given a matrix g and a matrix group G, return
true if g is an element of G, false otherwise.
Given a matrix g and a matrix group G, return
true if g is not an element of G, false otherwise.
Given a matrix group G and a set S of matrices
belonging to a group H, where G and H belong to the same
generic group, return true if S is a subset of G, false otherwise.
Given matrix groups G and H belonging to the same
generic group, return true if H is a subgroup of G, false
otherwise.
Given a matrix group G and a set S of matrices
belonging to a group H, where G and H belong to the same
generic group, return true if S is not a subset of G, false
otherwise.
Given matrix groups G and H belonging to the same
generic group, return true if H is not a subgroup of G,
false otherwise.
Given matrix groups G and H belonging to the same
generic group, return true if G and H are the same group,
false otherwise.
Given matrix groups G and H belonging to the same
generic group, return true if G and H are distinct groups,
false otherwise.
The creation of a base and strong generating set for a matrix
group G provides us with a very compact representation of the set of
elements of G. A particular BSGS imposes an order on the elements of
G (lexicographic ordering of base images). It thus makes sense to
talk about the `number' of a group element relative to a particular
BSGS.
A bijective mapping from the group G onto the set of integers
{ 1 ... |G| }. The actual mapping depends upon
the base and strong generating set chosen for G.
Slots: RngIntElt Default: 10
Scramble: RngIntElt Default: 20
Create a process to generate randomly chosen elements from the finite
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.
Short: BoolElt Default: false
A randomly chosen element for the group G. If a BSGS is known
for G, then the element chosen will be genuinely random. If
no BSGS is known, then the random element is chosen by
multiplying out a random word in the generators. Since it
is not usually practical to choose words long enough to
properly sample the elements of G, the element returned will
usually be biased. The boolean-valued parameter Short is
used in this situation to indicate that a short word will
suffice. Thus, if Random is invoked with Short
assigned the value true then the element is constructed
using a short word.
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 degree groups, or groups for which a
BSGS is not known, this function should be used in preference to
Random(G).
We use the random function to sample the orders of elements in
the group GL(20, 16).
> G := GeneralLinearGroup(20, GF(16));
> RP := RandomProcess(G);
> [ FactoredOrder(Random(RP)) : i in [1..20] ];
[
[ <3, 1>, <5, 1> ],
[ <3, 2>, <5, 1>, <7, 1>, <11, 1>, <13, 1>, <17, 1>, <31, 1>, <41, 1>,
<61681, 1> ],
[ <3, 1>, <5, 1>, <17, 1>, <23, 1>, <89, 1>, <257, 1>, <397, 1>, <683, 1>,
<2113, 1> ],
[ <3, 1>, <5, 1> ],
[ <3, 2>, <5, 1>, <7, 1>, <11, 1>, <13, 1>, <17, 1>, <31, 1>, <41, 1>,
<61681, 1> ],
[ <3, 1>, <31, 1>, <8191, 1> ],
[ <3, 2>, <5, 1>, <7, 1>, <11, 1>, <13, 1>, <17, 1>, <31, 1>, <41, 1>,
<61681, 1> ],
[ <3, 3>, <5, 1>, <7, 1>, <13, 1>, <17, 1>, <19, 1>, <29, 1>, <37, 1>,
<43, 1>, <73, 1>, <109, 1>, <113, 1>, <127, 1>, <257, 1> ],
[ <5, 1> ],
[ <3, 1>, <5, 1> ],
[ <3, 1>, <5, 2>, <11, 1>, <17, 1>, <31, 1>, <41, 1>, <53, 1>, <157, 1>,
<1613, 1>, <2731, 1>, <8191, 1> ],
[ <3, 2>, <5, 1>, <7, 1>, <13, 1>, <17, 1>, <97, 1>, <241, 1>, <257, 1>,
<673, 1> ],
[ <3, 1>, <5, 1>, <17, 1>, <29, 1>, <43, 1>, <113, 1>, <127, 1>, <257, 1>,
<65537, 1> ],
[ <3, 1>, <5, 2>, <11, 1>, <29, 1>, <31, 1>, <41, 1>, <43, 1>, <113, 1>,
<127, 1> ],
[ <3, 1>, <5, 2>, <11, 1>, <17, 1>, <31, 1>, <41, 1>, <53, 1>, <157, 1>,
<1613, 1>, <2731, 1>, <8191, 1> ],
[ <3, 2>, <5, 2>, <11, 1>, <13, 1>, <17, 1>, <31, 1>, <41, 1>, <61, 1>,
<151, 1>, <257, 1>, <331, 1>, <1321, 1> ],
[ <3, 1>, <5, 1>, <11, 1>, <31, 1>, <41, 1>, <257, 1>, <61681, 1>,
<4278255361, 1> ],
[ <3, 2>, <5, 1>, <7, 1>, <11, 1>, <13, 1>, <17, 1>, <31, 1>, <41, 1>,
<61681, 1> ],
[ <3, 1>, <5, 1>, <17, 1>, <23, 1>, <89, 1>, <257, 1>, <397, 1>, <683, 1>,
<2113, 1> ], [ <3, 2>, <5, 1>, <7, 1>, <11, 1>, <13, 1>, <23, 1>, <31, 1>,
<41, 1>, <89, 1>, <397, 1>, <683, 1>, <2113, 1> ]
]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|