Debian Codegraph @

htm/CHAP001.htm

raw
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 &nbsp;<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&gt; TransitiveGroup(10,22);
84 S(5)[x]2
85 gap&gt; 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&gt; 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&gt; 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&gt; 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&gt; AllTransitiveGroups(NrMovedPoints,[10..15],
141 &gt; Size, [1..100],
142 &gt; 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>