|
Magma includes the Small Groups Library prepared by
Besche, Eick and O'Brien. For a
description of the algorithms used to generate these groups, details on the
data structures used and applications we refer to
[BE99a], [BEO01], [BE99b], [O'B90], [BE01], [O'B91], [MNVL04], [DEP22] and
the references therein.
The Small Groups Library contains the following groups.
- -
- All groups of order up to 2000, excluding the groups of order 1024.
- -
- The groups whose order is a product of at most 4 (not necessarily distinct) primes.
- -
- The groups of order dividing p7 for p a prime.
- -
- The groups of order 38.
- -
- The groups of order qn p, where qn is a prime-power dividing
28, 36, 55 or 74 and p is a prime different to q.
- -
- The groups of square-free order.
The descriptions of the groups of order p4, p5, p6 for p>3
were contributed by Boris Girnat, Robert McKibbin, M.F. Newman,
E.A. O'Brien, and M.R. Vaughan-Lee.
The Magma version of this library uses the same internal data format as the
implementation available in GAP. In particular, the numbering of the groups
of a given order in both packages is the same.
For a different mechanism for accessing the p-groups in this collection,
see the The p-groups of Order Dividing p7 section, specifically the functions
SearchPGroups and CountPGroups. These functions also access
the groups of order p7 (contributed by O'Brien and Vaughan-Lee).
The groups of order 38 (also contributed by O'Brien and Vaughan-Lee)
form an optional database that must be downloaded separately.
Many of the functions in this section have an optional parameter Search.
It can be used to limit the small group search to soluble
(Search := "Soluble") or insoluble (Search := "Insoluble") groups.
The default is Search := "All", which allows all groups to be considered.
When a group is extracted from the database, it is returned
as a GrpPC if it is soluble, or as a GrpPerm if it
is insoluble.
When using the small groups database for an extended search, it is
advisable to open the database using the function
SmallGroupDatabase, which opens the database and returns
a reference to it. This reference can then be passed as first argument
to most of the functions described below, and will save that function
from opening and closing the database for itself. Doing so will reduce the
number of file operations when a lot of use is made of the database. When the
database is no longer needed, it can be closed using the delete
statement.
OpenSmallGroupDatabase() : -> DB
Open the small groups database (for extended search) and return a
reference to it. This reference may be passed to other functions
so that they do fewer file operations.
Close the small groups database D and free the resources associated with
its use.
SmallGroupDatabaseLimit(D) : DB -> RngIntElt
The limiting order up to which all groups (except those of order 1024) are
stored in the database of small groups, that is, currently 2000.
IsInSmallGroupDatabase(D, o) : DB, RngIntElt -> BoolElt
Return true if the groups of order o are contained in the database and
false otherwise. This function can be used to check whether
o is a legitimate argument for other functions described in this section,
avoiding runtime errors in user written loops or functions.
NumberOfSmallGroups(D, o) : DB, RngIntElt -> RngIntElt
Given a positive integer o, return the number of groups of order o in the
database. If the groups of order o are not contained in the database, 0 is
returned. This function can be used to check whether a pair o, n defines
a group contained in the small groups database, that is, whether it
is a legitimate argument for other functions described in this
section, avoiding runtime errors in user written loops or functions.
SmallGroup(o, n) : RngIntElt, RngIntElt -> Grp
SmallGroup(D, o, n) : DB, RngIntElt, RngIntElt -> Grp
Group(D, o, n) : DB, RngIntElt, RngIntElt -> Grp
Given a positive integer o, such that the groups of order o are contained
in the small groups library, and a positive integer n, return the n-th
group of order o in the database.
If the groups of order o are not contained in the database or if n
exceeds the number of groups of order o in the database, an error is
reported. The function NumberOfSmallGroups can be used
to check whether the arguments are valid.
SmallGroup(D, o: parameters) : DB, RngIntElt -> Grp
Search: MonStgElt Default: "All"
Given a positive integer o, such that the groups of order o are contained
in the small groups library, return the first
group of order o in the database meeting the search criterion set by the
parameter Search.
If the groups of order o are not contained in the database, an error is
reported. The function IsInSmallGroupDatabase can be used
to check whether o is a valid argument for this function.
SmallGroup(D, o, f: parameters) : RngIntElt, Program -> Grp
Search: MonStgElt Default: "All"
Given a positive integer o such that the groups of order o are contained
in the small groups library and a predicate f (as a function or intrinsic),
return the first group of order o in the database meeting the search
criterion set by the parameter Search, which satisfies f.
IsSolvable(D, o, n) : DB, RngIntElt, RngIntElt -> Grp
SmallGroupIsSoluble(o, n) : RngIntElt, RngIntElt -> Grp
SmallGroupIsSoluble(D, o, n) : DB, RngIntElt, RngIntElt -> Grp
SmallGroupIsSolvable(o, n) : RngIntElt, RngIntElt -> Grp
SmallGroupIsSolvable(D, o, n) : DB, RngIntElt, RngIntElt -> Grp
Return true iff SmallGroup(o, n) is soluble.
This function does not load the group. If the group specified by the arguments
does not exist in the database, an error is reported. The function
NumberOfSmallGroups can be used to check whether the
arguments are valid.
SmallGroupIsInsoluble(D, o, n) : DB, RngIntElt, RngIntElt -> Grp
SmallGroupIsInsolvable(o, n) : RngIntElt, RngIntElt -> Grp
SmallGroupIsInsolvable(D, o, n) : DB, RngIntElt, RngIntElt -> Grp
Return true iff SmallGroup(o, n) is insoluble.
This function does not load the group. If the group specified by the arguments
does not exist in the database, an error is reported. The function
NumberOfSmallGroups can be used to check whether the
arguments are valid.
SmallGroup(S, f: parameters) : [RngIntElt], Program -> Grp
SmallGroup(D, o, f: parameters) : DB, RngIntElt, Program -> Grp
SmallGroup(D, S, f: parameters) : DB, [RngIntElt], Program -> Grp
Search: MonStgElt Default: "All"
Given a sequence S of orders or a single order o contained in the
database and a predicate f
(as a function or intrinsic), return the first group with order in S
or equal to o, respectively, which meets the search criterion set by the
parameter Search and satisfies f.
SmallGroups(D, o: parameters) : DB, RngIntElt -> [* Grp *]
Search: MonStgElt Default: "All"
Warning: BoolElt Default: true
Given an order o contained in the database, return a list of all
groups of order o, meeting the search criterion
set by the parameter Search. Some orders
will produce a very large sequence of groups -- in such cases a warning
will be printed unless the user specifies Warning := false.
SmallGroups(D, S: parameters) : DB, [RngIntElt] -> [* Grp *]
Search: MonStgElt Default: "All"
Warning: BoolElt Default: true
Given a sequence S of orders contained in the database, return a list
of all groups
with order in S, meeting the search criterion set by the
parameter Search. The resulting sequence may be very long -- in such
cases a warning will be printed unless the user specifies
Warning := false.
SmallGroups(D, o, f: parameters) : DB, RngIntElt, Program -> [* Grp *]
Search: MonStgElt Default: "All"
Given an order o contained in the database and a predicate (function or
intrinsic) f, return a list containing all groups G of order o,
meeting the search criterion set by the parameter Search and satisfying
f(G) eq true.
SmallGroups(D, S, f: parameters) : DB, [RngIntElt], Program -> [* Grp *]
Search: MonStgElt Default: "All"
Given a sequence S of orders contained in the database and a predicate
(function or intrinsic) f, return a list containing all groups G
with order in S, meeting the search criterion set by the parameter
Search and satisfying f(G) eq true.
- (1)
- We find the non-abelian groups of order 27.
> list := SmallGroups(27, func<x|not IsAbelian(x)> );
> list;
[*
GrpPC of order 27 = 3^3
PC-Relations:
$.2^$.1 = $.2 * $.3,
GrpPC of order 27 = 3^3
PC-Relations:
$.1^3 = $.3,
$.2^$.1 = $.2 * $.3
*]
- (2)
- We get the first group in the database with derived length greater than 2.
> G := SmallGroup([1..100], func<x|DerivedLength(x) gt 2>);
> G;
GrpPC of order 24 = 2^3 * 3
PC-Relations:
G.1^3 = Id(G),
G.2^2 = G.4,
G.3^2 = G.4,
G.4^2 = Id(G),
G.2^G.1 = G.3,
G.3^G.1 = G.2 * G.3,
G.3^G.2 = G.3 * G.4
- (3)
- Now for a list of the insoluble groups of order 240.
The insoluble groups in the database are returned as
permutation groups.
> list := SmallGroups(240:Search:="Insoluble");
> #list;
8
> list[7];
Permutation group acting on a set of cardinality 7
(1, 2, 3, 4)
(1, 5, 2, 4, 3)(6, 7)
- (4)
- The groups of order 2432 = 27.19 should be contained in the small
groups database. We check this using the function
IsInSmallGroupDatabase ...
> IsInSmallGroupDatabase(2432);
true
... and determine the number of groups of order 2432.
> NumberOfSmallGroups(2432);
19324
- (5)
- We find all groups of order 76 with cyclic centre of order 72.
> f := function (G)
> Z := Centre (G);
> return IsCyclic (Z) and #Z eq 7^2;
> end function;
> P := SmallGroups(7^6, f);
> #P;
30
> NumberOfSmallGroups(7^6);
860
A small group process makes it possible to iterate over all
groups of specified orders satisfying a given predicate, without
having to create and store all such groups in a list.
A small group process is created via the function
SmallGroupProcess (in various forms).
The standard process functions IsEmpty, Current,
CurrentLabel and Advance can then be applied to the process.
The functions used to create a small group process all have a parameter
Search attached to them.
This can be used to limit the small group search to soluble
(Search := "Soluble") or insoluble (Search := "Insoluble") groups.
The default is Search := "All", which allows all groups to be considered.
The Process functions described below do not have a variant with
the database as first argument, as each process opens the database for
an extended search automatically.
Search: MonStgElt Default: "All"
Given an order o contained in the small groups database, return a small
group process which will iterate though all groups of order o meeting the
search criterion set by the parameter Search.
Search: MonStgElt Default: "All"
Given a sequence S of orders contained in the small groups database, return
a small group process which will iterate though all groups with order in the
sequence S meeting the search criterion set by the parameter Search.
Search: MonStgElt Default: "All"
Given an order o contained in the small groups database and a predicate f
(as function or intrinsic), return a small group process which will iterate
though all groups of order o, which meet the search criterion set by the
parameter Search and satisfy the predicate f.
Search: MonStgElt Default: "All"
Given a sequence S of orders contained in the small groups database and a
predicate f (as function or intrinsic), return a small group process which
will iterate though all groups with order in the sequence S, which meet
the search criterion set by the parameter Search and satisfy the
predicate f.
Returns true if the process p has passed its last group.
Return the current group of the process p.
Return the label of the current group of the process p.
That is, return o and n such that the current group is
SmallGroup(o, n).
Move the process p to its next group.
We employ a small group process to examine all the groups of
order 128 and determine the nilpotency class of each of them.
> P := SmallGroupProcess(128);
> count := {* *};
> repeat
> G := Current(P);
> Include(~count, NilpotencyClass(G));
> Advance(~P);
> until IsEmpty(P);
> count;
{* 1^^15, 2^^947, 3^^1137, 4^^197, 5^^29, 6^^3 *}
Intrinsics are provided that allow the user to find the database
group that is isomorphic to a given group. Given a group G such
that the database includes a group isomorphic to G and assuming
that identification of groups of order |G| is supported, the
identification functions return a pair < o, n >
so that SmallGroup(o, n) is isomorphic to G.
Identifying a finitely presented group G involves constructing
a permutation representation G which may fail. The identification
process tries to construct a permutation representation of G by
enumerating the cosets of the trivial subgroup in G. Assuming
that a group isomorphic to G is contained in the database, the
resulting coset table will be fairly small.
Hence for performance reasons, a coset limit of 100.N is
imposed, where N is the largest order of groups in the database.
If the order of G is known to be less or equal to N,
the implicitly invoked coset enumeration can be given a more
appropriate value for the maximum number of cosets that can be defined.
This is done by means of the intrinsic SetGlobalTCParameters.
If the coset enumeration for G fails with the coset limit set to
100.N, this can be seen as a reasonable indication that
G is probably too large to be includes in the database of small
groups.
To deal with cases where the coset enumeration fails when G is
known or suspected to be included in the database, the user should
attempt to compute the order of G using the intrinsic Order
prior to the actual group identification. If this shows G is small
enough to be included in the database, the intrinsic
SetGlobalTCParameters can be used to set a larger
limit on maximum number of cosets that can be defined by the Todd-Coxeter
procedure in a subsequent call to IdentifyGroup. This is illustrated
in the following example.
IdentifyGroup(D, G): DB, Grp -> Tup
Locate the pair of integers < o, n > so that
SmallGroup(o, n) is isomorphic to G. If there is no such group
in the database or if identification of groups of order |G| is not
supported, then an error will result. The function
CanIdentifyGroup can be used to test whether groups
of a certain order can be identified; this may be useful for avoiding
runtime errors in user written loops or functions.
CanIdentifyGroup(D, o) : DB, RngIntElt -> BoolElt
Return true if identification of groups of order o in the database is
supported. This function can be used to check whether a group
is a legitimate argument for the functions IdentifyGroup
described above, avoiding runtime errors in user written loops or functions.
We identify a permutation group in the small group database,
and get an isomorphic group from the database.
> G := DihedralGroup(10);
> G;
Permutation group G acting on a set of cardinality 10
Order = 20 = 2^2 * 5
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
(1, 10)(2, 9)(3, 8)(4, 7)(5, 6)
> IdentifyGroup(G);
<20, 4>
> H := SmallGroup(20, 4);
> H;
GrpPC : H of order 20 = 2^2 * 5
PC-Relations:
H.1^2 = Id(H),
H.2^2 = Id(H),
H.3^5 = Id(H),
H.3^H.1 = H.3^4
Consider the group defined by the presentation
< a, b | (ba - 1)3, (ba - 1b)2,
a12b2a7b2ab2 >.
> G := Group<a,b | (b*a^-1)^3, (b*a^-1*b)^2,
> a^12*b^2*a^7*b^2*a*b^2 >;
We suspect (for some reason) that G is a small group and want to identify
its isomorphism type in the database of small groups.
> IdentifyGroup(G);
IdentifyGroup(
G: GrpFP: G
)
In file "/home/magma/package/Group/Grp/smallgps2.m", line 220,
column 25:
>> res := IdentifyGroup(db, G);
^
Runtime error in 'IdentifyGroup': Coset enumeration failed; group
may be too large (see handbook entry for details)
The group couldn't be identified, because it was not possible to construct a
permutation representation with the default value of the coset limit.
Since we still believe the group is small, we try to prove this using
the function Order.
> Order(G : Print := true);
INDEX = 6 (a=6 r=66709 h=999999 n=999999; l=1247 c=1.56; m=969169 t=999998)
6
The output line beginning with "INDEX" gives information about the coset
enumeration: in particular 999,998 cosets had to be designed in order to
construct the coset table.
We were correct; the group has order 6. However, we can see from
the verbose output of the Order intrinsic that this wasn't easy
to do: almost one million cosets were used in the coset enumeration.
Since the order of G is now known to Magma, a subsequent call to
IdentifyGroup will use 100*6 as the coset limit. We tell
the system to be prepared to work a little harder using the intrinsic
SetGlobalTCParameters and again try to identify G:-
> SetGlobalTCParameters( : Strategy := "Hard");
>
> IdentifyGroup(G);
<6, 1>
So G has now been identified!
The following functions provide access to data used internally by the
Small Groups Library for representing groups. They are included
just for completeness and are intended to be used by experts only. In
particular, we do not give a detailed explanation of the (complicated)
data format in this manual.
Returns the data from which the group number n of order o in D is
constructed. The format and the meaning of the items in the returned list
depends on the group indicated by the pair (o, n).
Given a finite solvable group G in the category GrpPC, return two
integers c and o encoding the power conjugate presentation of G.
The second return value is the order of G. The first return value is an
integer specifying the power conjugate relations in the presentation of G.
Given two integers c and o encoding a power conjugate presentation G,
return G as a group in the category GrpPC.
The second argument is the order of G. The first return value is an
integer specifying the power conjugate relations in the presentation G.
- (1)
- We extract a power conjugate presentation from the database and compute
its encoding.
> D := SmallGroupDatabase();
> G := SmallGroup(D,1053,51);
> Category(G);
GrpPC
> SmallGroupEncoding(G);
100286712487397165939678173 1053
- (2)
- The second group of order 525 in the small groups database is stored as
encoded power conjugate presentation.
> Data(D,525,2);
[* code, 666501 *]
We can create the corresponding group by decoding this information.
> G := SmallGroupDecoding(666501, 525);
> G;
GrpPC : G of order 525 = 3 * 5^2 * 7
PC-Relations:
G.1^3 = Id(G),
G.2^5 = G.4,
G.3^7 = Id(G),
G.4^5 = Id(G)
This gives the same presentation as accessing the database in the "usual"
way.
> SmallGroup(D,525,2);
GrpPC of order 525 = 3 * 5^2 * 7
PC-Relations:
$.1^3 = Id($),
$.2^5 = $.4,
$.3^7 = Id($),
$.4^5 = Id($)
The following functions provide access to functions used internally by the
Small Groups Library for constructing groups of order divisible by four primes.
These functions are based on the paper [DEP22] by Dietrich, Eick,
and Pan. This article gives constructions for all groups of orders
p2q, p3q, p2q2, and p2qr, where p, q, r are distinct primes.
These constructions have been implemented in Magma and are available as
follows. This includes a function to identify such a group in the lists.
In all the functions here, the primes p, q, r must be < 230.
The functions here are used by the Small Groups Library when the group order
is as above, except when the order is less than 2000, or has the form p2q,
or the form p3q with p≤7 (which were in the small groups library
before these functions were written). In these exceptional cases the numbering
of the groups within each order usually differs between the Small Groups Library
and the functions here.
The groups are constructed as pc-groups, except in one case: order 60, group
number 13 is the only insoluble group within these orders (it is A5),
and this group is returned as a permutation group.
Returns the ith group in the list of groups of order o given by
[DEP22]. The order o must have the form
p2q, p3q, p2q2, or p2qr, where p, q, r are distinct primes.
Returns the list of groups of order o given by
[DEP22]. The order o must have the form
p2q, p3q, p2q2, or p2qr, where p, q, r are distinct primes.
Returns the length of the list of groups of order o given by
[DEP22]. The order o must have the form
p2q, p3q, p2q2, or p2qr, where p, q, r are distinct primes.
IdentifyGroup4P(G) : GrpPerm -> RngIntElt
IdentifyGroup4P(G) : GrpMat -> RngIntElt
Returns the number of the group isomorphic to G in the
the list of groups of order o=|G| given by [DEP22].
The order o must have the form
p2q, p3q, p2q2, or p2qr, where p, q, r are distinct primes.
Note that this number may not agree with the number returned by
texttt{IdentifyGroup} (see above).
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|