| 1 |
<html><head><title>[transgrp] 1 The Library of Transitive Groups</title></head> |
| 2 |
<body text="#000000" bgcolor="#ffffff"> |
| 3 |
[<a href = "chapters.htm">Up</a>] [<a href = "theindex.htm">Index</a>] |
| 4 |
<h1>1 The Library of Transitive Groups</h1><p> |
| 5 |
<P> |
| 6 |
<H3>Sections</H3> |
| 7 |
<oL> |
| 8 |
<li> <A HREF="CHAP001.htm#SECT001">Transitive Permutation Groups</a> |
| 9 |
<li> <A HREF="CHAP001.htm#SECT002">Selection Functions</a> |
| 10 |
<li> <A HREF="CHAP001.htm#SECT003">Interfacing with the library</a> |
| 11 |
<li> <A HREF="CHAP001.htm#SECT004">Supplemental Downloads</a> |
| 12 |
</ol><p> |
| 13 |
<p> |
| 14 |
The Transitive Groups Library is created by Alexander Hulpke. |
| 15 |
You are free to distribute it, provided that you make no modifications. |
| 16 |
<p> |
| 17 |
The actual groups in the library and their generating sets are due to a |
| 18 |
number of authors: |
| 19 |
Gregory Butler, John McKay, Gordon |
| 20 |
Royle, Alexander Hulpke, John Cannon, Gareth Tracy, and Derek Holt. |
| 21 |
<p> |
| 22 |
The list of transitive groups up to degree 11 |
| 23 |
was published in <a href="biblio.htm#BM83"><cite>BM83</cite></a>, the list of degree 12 was published in |
| 24 |
<a href="biblio.htm#Roy87"><cite>Roy87</cite></a>, degree 14 and 15 were published in <a href="biblio.htm#Butler93"><cite>Butler93</cite></a> and |
| 25 |
degrees 16--30 were published in <a href="biblio.htm#Hulpke96"><cite>Hulpke96</cite></a> and <a href="biblio.htm#HulpkeTG"><cite>HulpkeTG</cite></a>. |
| 26 |
Degree 32 was published in <a href="biblio.htm#CanHolt32"><cite>CanHolt32</cite></a>, degrees 34-46 have been |
| 27 |
obtained by Derek Holt and Gordon Royle in <a href="biblio.htm#HoltRoyle47"><cite>HoltRoyle47</cite></a>, |
| 28 |
and degree 48 is due to Derek Holt, Gordon Royle, and Gareth Tracy in |
| 29 |
<a href="biblio.htm#HoltRoyleTracy48"><cite>HoltRoyleTracy48</cite></a>. |
| 30 |
Groups of prime degree of course are primitive and were known long before. |
| 31 |
<p> |
| 32 |
The transitive groups library will contain representatives for all |
| 33 |
transitive permutation groups of degree at most 47. Not all degrees might |
| 34 |
be yet available in the current release. Due to the total number, |
| 35 |
degree 32 and 48 need to be downloaded separately, see section ``Supplemental |
| 36 |
Downloads'' below. |
| 37 |
<p> |
| 38 |
Two permutations groups of the same degree are considered to be |
| 39 |
equivalent, if there is a renumbering of points, which maps one group into |
| 40 |
the other one. |
| 41 |
In other words, if they lie in the same conjugacy class under operation |
| 42 |
of the full symmetric group by conjugation. |
| 43 |
<p> |
| 44 |
<p> |
| 45 |
<h2><a name="SECT001">1.1 Transitive Permutation Groups</a></h2> |
| 46 |
<p><p> |
| 47 |
<a name = "SSEC001.1"></a> |
| 48 |
<li><code>TransitiveGroupsAvailable( </code><var>deg</var><code> ) F</code> |
| 49 |
<p> |
| 50 |
returns whether the transitive groups groups of degree <var>deg</var> are available |
| 51 |
for use. This function should be used to test for the scope of the library |
| 52 |
available. |
| 53 |
<p> |
| 54 |
<a name = "SSEC001.2"></a> |
| 55 |
<li><code>TransitiveGroup( </code><var>deg</var><code>, </code><var>nr</var><code> ) F</code> |
| 56 |
<p> |
| 57 |
returns the <var>nr</var>-th transitive group of degree <var>deg</var>. Both <var>deg</var> and |
| 58 |
<var>nr</var> must be positive integers. The transitive groups of equal degree |
| 59 |
are sorted with respect to their size, so for example |
| 60 |
<code>TransitiveGroup( </code><var>deg</var><code>, 1 )</code> is a transitive group of degree and |
| 61 |
size <var>deg</var>, e.g, the cyclic group of size <var>deg</var>, if <var>deg</var> is a |
| 62 |
prime. |
| 63 |
<p> |
| 64 |
<a name = "SSEC001.3"></a> |
| 65 |
<li><code>NrTransitiveGroups( </code><var>deg</var><code> ) F</code> |
| 66 |
<p> |
| 67 |
returns the number of transitive groups of degree <var>deg</var> stored in the |
| 68 |
library of transitive groups. The function returns <code>fail</code> if <var>deg</var> is |
| 69 |
beyond the range of the library. |
| 70 |
<p> |
| 71 |
The arrangement and the names of the groups of degree up to 15 is the same |
| 72 |
as given in <a href="biblio.htm#ConwayHulpkeMcKay98"><cite>ConwayHulpkeMcKay98</cite></a>. With the exception of the symmetric |
| 73 |
and alternating group (which are represented as <code>SymmetricGroup</code> and |
| 74 |
<code>AlternatingGroup</code>) the generators for these groups also conform to this |
| 75 |
paper with the only difference that 0 (which is not permitted in <font face="Gill Sans,Helvetica,Arial">GAP</font> for |
| 76 |
permutations to act on) is always replaced by the degree. |
| 77 |
<p> |
| 78 |
The arrangement for all degrees is intended to be equal to the arangement |
| 79 |
within the system Magma, thus it should be safe to refer to particular |
| 80 |
(classes of) groups by their index numbers. |
| 81 |
<p> |
| 82 |
<pre> |
| 83 |
gap> TransitiveGroup(10,22); |
| 84 |
S(5)[x]2 |
| 85 |
gap> l:=AllTransitiveGroups(NrMovedPoints,12,Size,1440,IsSolvable,false); |
| 86 |
[ S(6)[x]2, M_10.2(12)=A_6.E_4(12)=[S_6[1/720]{M_10}S_6]2 ] |
| 87 |
gap> List(l,IsSolvable); |
| 88 |
[ false, false ] |
| 89 |
</pre> |
| 90 |
<p> |
| 91 |
<a name = "SSEC001.4"></a> |
| 92 |
<li><code>TransitiveIdentification( </code><var>G</var><code> ) A</code> |
| 93 |
<p> |
| 94 |
Let <var>G</var> be a permutation group, acting transitively on a set of up to 30 |
| 95 |
points. Then <code>TransitiveIdentification</code> will return the position of this |
| 96 |
group in the transitive groups library. This means, if <var>G</var> acts on |
| 97 |
<var>m</var> points and <code>TransitiveIdentification</code> returns <var>n</var>, then <var>G</var> is |
| 98 |
permutation isomorphic to the group <code>TransitiveGroup(m,n)</code>. |
| 99 |
<p> |
| 100 |
Note: The points moved do <strong>not</strong> need to be [1..<var>n</var>], the group |
| 101 |
<var>langle(2,3,4),(2,3)rangle</var> is considered to be transitive on 3 |
| 102 |
points. If the group has several orbits on the points moved by it the |
| 103 |
result of <code>TransitiveIdentification</code> is undefined. |
| 104 |
<p> |
| 105 |
<pre> |
| 106 |
gap> TransitiveIdentification(Group((1,2),(1,2,3))); |
| 107 |
2 |
| 108 |
</pre> |
| 109 |
<p> |
| 110 |
<a name = "SSEC001.5"></a> |
| 111 |
<li><code>MinimalTransitiveIndices( </code><var>deg</var><code> ) F</code> |
| 112 |
<p> |
| 113 |
returns a list of indices of the transitive groups of degree <var>deg</var>, which |
| 114 |
are minimally trransitive, i.e. for which every proper subgroup is not |
| 115 |
transitive. |
| 116 |
<p> |
| 117 |
<pre> |
| 118 |
gap> MinimalTransitiveIndices(12); |
| 119 |
[ 1, 2, 3, 4, 5, 7, 9, 17, 31, 34, 40, 46, 47, 57, 162, 166, 246 ] |
| 120 |
</pre> |
| 121 |
<p> |
| 122 |
<p> |
| 123 |
<h2><a name="SECT002">1.2 Selection Functions</a></h2> |
| 124 |
<p><p> |
| 125 |
<a name = "SSEC002.1"></a> |
| 126 |
<li><code>AllTransitiveGroups( </code><var>fun1</var><code>, </code><var>val1</var><code>, ... ) F</code> |
| 127 |
<a name = "SSEC002.1"></a> |
| 128 |
<li><code>AllLibraryTransitiveGroups( </code><var>fun1</var><code>, </code><var>val1</var><code>, ... ) F</code> |
| 129 |
<a name = "SSEC002.1"></a> |
| 130 |
<li><code>OneTransitiveGroup( </code><var>fun1</var><code>, </code><var>val1</var><code>, ... ) F</code> |
| 131 |
<p> |
| 132 |
These functions take an arbitrary number of pairs (but at least one pair) |
| 133 |
of arguments. The first argument in such a pair is a function that can be |
| 134 |
applied to the groups in the library, and the second argument is either a |
| 135 |
single value that this function must return in order to have this group |
| 136 |
included in the selection, or a list of such values. |
| 137 |
It returns all (ore one) group satisfying the parameters: |
| 138 |
<p> |
| 139 |
<pre> |
| 140 |
gap> AllTransitiveGroups(NrMovedPoints,[10..15], |
| 141 |
> Size, [1..100], |
| 142 |
> IsAbelian, false ); |
| 143 |
</pre> |
| 144 |
<p> |
| 145 |
returns a list of all transitive groups with degree between 10 and 15 and |
| 146 |
size less than 100 that are not abelian. |
| 147 |
<p> |
| 148 |
Thus the <code>AllTransitiveGroups</code> behaves as if it was implemented by a |
| 149 |
function similar to the one defined below, where <code>TransitiveGroupsList</code> is a |
| 150 |
list of all transitive groups. (Note that in the definition below we assume |
| 151 |
for simplicity that <code>AllTransitiveGroups</code> accepts exactly 4 arguments. It is |
| 152 |
of course obvious how to change this definition so that the function would |
| 153 |
accept a variable number of arguments.) |
| 154 |
<p> |
| 155 |
<pre> |
| 156 |
AllTransitiveGroups := function( fun1, val1, fun2, val2 ) |
| 157 |
local groups, g, i; |
| 158 |
groups := []; |
| 159 |
for i in [ 1 .. Length( TransitiveGroupsList ) ] do |
| 160 |
g := TransitiveGroupsList[i]; |
| 161 |
if fun1(g) = val1 or IsList(val1) and fun1(g) in val1 |
| 162 |
and fun2(g) = val2 or IsList(val2) and fun2(g) in val2 |
| 163 |
then |
| 164 |
Add( groups, g ); |
| 165 |
fi; |
| 166 |
od; |
| 167 |
return groups; |
| 168 |
end; |
| 169 |
</pre> |
| 170 |
Note that the real selection functions are considerably more difficult, |
| 171 |
to improve the efficiency. Most important, each recognizes a certain set |
| 172 |
of properties which are precomputed for the library without having to |
| 173 |
compute them anew for each group. This will substantially speed up the |
| 174 |
selection process. |
| 175 |
<p> |
| 176 |
The selection functions for the transitive |
| 177 |
groups library are <code>AllTransitiveGroups</code> and <code>OneTransitiveGroup</code>. They |
| 178 |
obtain the following properties from the database without having to compute |
| 179 |
them anew: |
| 180 |
<p> |
| 181 |
<code>NrMovedPoints</code>, <code>Size</code>, <code>Transitivity</code>, and <code>IsPrimitive</code>. |
| 182 |
<p> |
| 183 |
The function <code>AllLibraryTransitiveGroups</code> works the same way as |
| 184 |
<code>AllTransitiveGroups</code> but does not warn if no degree is specified. |
| 185 |
<p> |
| 186 |
<p> |
| 187 |
<h2><a name="SECT003">1.3 Interfacing with the library</a></h2> |
| 188 |
<p><p> |
| 189 |
Only access using the functions described in this manual is promised to |
| 190 |
remain stable. Code that wants to use the transitive groups library should |
| 191 |
use <code>TransitiveGroupsAvailable</code> to establish the data being installed for |
| 192 |
the desired degree. (This function has a dummy equivalent in the main <font face="Gill Sans,Helvetica,Arial">GAP</font> |
| 193 |
library so that it is always available to return <code>false</code>.) Then |
| 194 |
<code>NrTransitiveGroups</code> should be used to determine the range of valid indices for |
| 195 |
the given degree. Routines should not try to access data structures of the |
| 196 |
library directly. |
| 197 |
<p> |
| 198 |
<p> |
| 199 |
<h2><a name="SECT004">1.4 Supplemental Downloads</a></h2> |
| 200 |
<p><p> |
| 201 |
There are almost 3 million groups of degree 32 and these groups require over |
| 202 |
a GB of disk space when uncompressed. |
| 203 |
These groups are therefore not part of the package |
| 204 |
distribution, but are made available as a supplemental download at |
| 205 |
<pre> |
| 206 |
https://www.math.colostate.edu/~hulpke/transgrp/trans32.tgz |
| 207 |
</pre> |
| 208 |
<p> |
| 209 |
Simply unpack this archive (which is a tar archive compressed with gzip -- |
| 210 |
consult your computer administrator on the correct way of unpacking) |
| 211 |
in the top folder of the <code>transgrp</code> package (this |
| 212 |
folder will contain the <code>PackageInfo.g</code> file, it will create a folder dat32 |
| 213 |
containing the groups of degree 32. Once you restart GAP it will |
| 214 |
automatically recognize the existence of these groups. |
| 215 |
<p> |
| 216 |
The <var>195826352</var> groups of degree 48 take over 30GB of disk space in |
| 217 |
compressed form and thus require a particular download: |
| 218 |
<p> |
| 219 |
Create a folder <code>dat48</code> in the top folder of the <code>transgrp</code> package. Then |
| 220 |
download the 11 files <code>Trans48Part....tar</code> from |
| 221 |
<pre> |
| 222 |
https://zenodo.org/record/5935751 |
| 223 |
</pre> |
| 224 |
and unpack them into this folder. |
| 225 |
<strong>Do not uncompress the resulting <code>.gz</code> files</strong> |
| 226 |
(You can delete the <code>.tar</code> archive files afterwards.) |
| 227 |
Once GAP is restarted these groups will be available, but |
| 228 |
<code>TransitiveIdentification</code> (for groups not created from the library) or |
| 229 |
the <code>AllTransitiveGroups</code> selector will not work. |
| 230 |
<p> |
| 231 |
Conversion of these groups to GAP is due in part to Jesse Lansdown, whose |
| 232 |
help is greatly appreciated |
| 233 |
<p> |
| 234 |
Due to the compressed storage, it is perceivable that the groups of degree 48 |
| 235 |
do not work under Windows. This has not been tested and no promise for this |
| 236 |
particular functionality is made. |
| 237 |
<p> |
| 238 |
[<a href = "chapters.htm">Up</a>] [<a href = "theindex.htm">Index</a>] |
| 239 |
<P> |
| 240 |
<address>transgrp manual<br>February 2022 |
| 241 |
</address></body></html> |