Debian Codegraph @

doc/chap1_mj.html

raw
1 <?xml version="1.0" encoding="UTF-8"?>
2
3 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
4 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
5
6 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
7 <head>
8 <script type="text/javascript"
9 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
10 </script>
11 <title>GAP (primgrp) - Chapter 1: Primitive Permutation Groups</title>
12 <meta http-equiv="content-type" content="text/html; charset=UTF-8" />
13 <meta name="generator" content="GAPDoc2HTML" />
14 <link rel="stylesheet" type="text/css" href="manual.css" />
15 <script src="manual.js" type="text/javascript"></script>
16 <script type="text/javascript">overwriteStyle();</script>
17 </head>
18 <body class="chap1" onload="jscontent()">
19
20
21 <div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
22
23 <div class="chlinkprevnexttop">&nbsp;<a href="chap0_mj.html">[Top of Book]</a>&nbsp; <a href="chap0_mj.html#contents">[Contents]</a>&nbsp; &nbsp;<a href="chap0_mj.html">[Previous Chapter]</a>&nbsp; &nbsp;<a href="chap2_mj.html">[Next Chapter]</a>&nbsp; </div>
24
25 <p id="mathjaxlink" class="pcenter"><a href="chap1.html">[MathJax off]</a></p>
26 <p><a id="X7AE00EA7791F2574" name="X7AE00EA7791F2574"></a></p>
27 <div class="ChapSects"><a href="chap1_mj.html#X7AE00EA7791F2574">1 <span class="Heading">Primitive Permutation Groups</span></a>
28 <div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap1_mj.html#X7AE00EA7791F2574">1.1 <span class="Heading">Primitive Permutation Groups</span></a>
29 </span>
30 <div class="ContSSBlock">
31 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1_mj.html#X81BDF8CA7CCBFC95">1.1-1 PrimitiveGroupsAvailable</a></span>
32 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1_mj.html#X7BCEA0C57B6D9F42">1.1-2 PrimitiveGroup</a></span>
33 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1_mj.html#X8564FECC8477F199">1.1-3 NrPrimitiveGroups</a></span>
34 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1_mj.html#X86EF380E8007D304">1.1-4 AllPrimitiveGroups</a></span>
35 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1_mj.html#X82870C177DB70470">1.1-5 OnePrimitiveGroup</a></span>
36 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1_mj.html#X7B1D4C0483A7F444">1.1-6 PrimitiveGroupsIterator</a></span>
37 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1_mj.html#X81329B9B7F5FF8DE">1.1-7 COHORTS_PRIMITIVE_GROUPS</a></span>
38 </div></div>
39 <div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap1_mj.html#X7DA239CC848F6CAE">1.2 <span class="Heading">Index numbers of primitive groups</span></a>
40 </span>
41 <div class="ContSSBlock">
42 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1_mj.html#X870400597FD4E392">1.2-1 PrimitiveIdentification</a></span>
43 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1_mj.html#X790D50447ABDF7EE">1.2-2 SimsNo</a></span>
44 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1_mj.html#X784820DA86D0E6F4">1.2-3 PRIMITIVE_INDICES_MAGMA</a></span>
45 </div></div>
46 </div>
47
48 <h3>1 <span class="Heading">Primitive Permutation Groups</span></h3>
49
50 <p><a id="X7AE00EA7791F2574" name="X7AE00EA7791F2574"></a></p>
51
52 <h4>1.1 <span class="Heading">Primitive Permutation Groups</span></h4>
53
54 <p><strong class="pkg">GAP</strong> contains a library of primitive permutation groups which includes, up to permutation isomorphism (i.e., up to conjugacy in the corresponding symmetric group), all primitive permutation groups of degree <span class="SimpleMath">\(&lt; 4096\)</span>, calculated in <a href="chapBib_mj.html#biBRoneyDougal05">[Ron05]</a> and <a href="chapBib_mj.html#biBCRDQ11">[Qui11]</a>, in particular,</p>
55
56
57 <ul>
58 <li><p>the primitive permutation groups up to degree 50, calculated by C. Sims,</p>
59
60 </li>
61 <li><p>the primitive groups with insoluble socles of degree <span class="SimpleMath">\(&lt; 1000\)</span> as calculated in <a href="chapBib_mj.html#biBDixonMortimer88">[DM88]</a>,</p>
62
63 </li>
64 <li><p>the solvable (hence affine) primitive permutation groups of degree <span class="SimpleMath">\(&lt; 256\)</span> as calculated by M. Short <a href="chapBib_mj.html#biBSho92">[Sho92]</a>,</p>
65
66 </li>
67 <li><p>some insolvable affine primitive permutation groups of degree <span class="SimpleMath">\(&lt; 256\)</span> as calculated in <a href="chapBib_mj.html#biBTheissen97">[The97]</a>.</p>
68
69 </li>
70 <li><p>The solvable primitive groups of degree up to <span class="SimpleMath">\(999\)</span> as calculated in <a href="chapBib_mj.html#biBEickHoefling02">[EH03]</a>.</p>
71
72 </li>
73 <li><p>The primitive groups of affine type of degree up to <span class="SimpleMath">\(999\)</span> as calculated in <a href="chapBib_mj.html#biBRoneyDougal02">[RU03]</a>.</p>
74
75 </li>
76 </ul>
77 <p>Not all groups are named, those which do have names use ATLAS notation. Not all names are necessarily unique!</p>
78
79 <p>The list given in <a href="chapBib_mj.html#biBRoneyDougal05">[Ron05]</a> is believed to be complete, correcting various omissions in <a href="chapBib_mj.html#biBDixonMortimer88">[DM88]</a>, <a href="chapBib_mj.html#biBSho92">[Sho92]</a> and <a href="chapBib_mj.html#biBTheissen97">[The97]</a>.</p>
80
81 <p>In detail, we guarantee the following properties for this and further versions (but <em>not</em> versions which came before <strong class="pkg">GAP</strong> 4.2) of the library:</p>
82
83
84 <ul>
85 <li><p>All groups in the library are primitive permutation groups of the indicated degree.</p>
86
87 </li>
88 <li><p>The positions of the groups in the library are stable. That is <code class="code">PrimitiveGroup(<var class="Arg">n</var>,<var class="Arg">nr</var>)</code> will always give you a permutation isomorphic group. Note however that we do not guarantee to keep the chosen <span class="SimpleMath">\(S_n\)</span>-representative, the generating set or the name for eternity.</p>
89
90 </li>
91 <li><p>Different groups in the library are not conjugate in <span class="SimpleMath">\(S_n\)</span>.</p>
92
93 </li>
94 <li><p>If a group in the library has a primitive subgroup with the same socle, this group is in the library as well.</p>
95
96 </li>
97 </ul>
98 <p>(Note that the arrangement of groups is not guaranteed to be in increasing size, though it holds for many degrees.)</p>
99
100 <p>The selection functions (see <a href="../../../doc/ref/chap50_mj.html#X82676ED5826E9E2E"><span class="RefLink">Reference: Selection Functions</span></a>) for the primitive groups library are <code class="code">AllPrimitiveGroups</code> and <code class="code">OnePrimitiveGroup</code>. They obtain the following properties from the database without having to compute them anew:</p>
101
102 <p><code class="func">NrMovedPoints</code> (<a href="../../../doc/ref/chap42_mj.html#X85E7B1E28430F49E"><span class="RefLink">Reference: NrMovedPoints for a list or collection of permutations</span></a>), <code class="func">Size</code> (<a href="../../../doc/ref/chap30_mj.html#X858ADA3B7A684421"><span class="RefLink">Reference: Size</span></a>), <code class="func">Transitivity</code> (<a href="../../../doc/ref/chap41_mj.html#X8295D733796B7A37"><span class="RefLink">Reference: Transitivity for a group and an action domain</span></a>), <code class="func">ONanScottType</code> (<a href="../../../doc/ref/chap43_mj.html#X7E50211A7B92455F"><span class="RefLink">Reference: ONanScottType</span></a>), <code class="func">IsSimpleGroup</code> (<a href="../../../doc/ref/chap39_mj.html#X7A6685D7819AEC32"><span class="RefLink">Reference: IsSimpleGroup</span></a>), <code class="func">IsSolvableGroup</code> (<a href="../../../doc/ref/chap39_mj.html#X809C78D5877D31DF"><span class="RefLink">Reference: IsSolvableGroup</span></a>), and <code class="func">SocleTypePrimitiveGroup</code> (<a href="../../../doc/ref/chap43_mj.html#X7E89A46A86A3F4A2"><span class="RefLink">Reference: SocleTypePrimitiveGroup</span></a>).</p>
103
104 <p>(Note, that for groups of degree up to 2499, O'Nan-Scott types 4a, 4b and 5 cannot occur.)</p>
105
106 <p><a id="X81BDF8CA7CCBFC95" name="X81BDF8CA7CCBFC95"></a></p>
107
108 <h5>1.1-1 PrimitiveGroupsAvailable</h5>
109
110 <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PrimitiveGroupsAvailable</code>( <var class="Arg">deg</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
111 <p>To offer a clearer interface to the primitive groups library, this function checks whether the primitive groups of degree <var class="Arg">deg</var> are available.</p>
112
113 <p><a id="X7BCEA0C57B6D9F42" name="X7BCEA0C57B6D9F42"></a></p>
114
115 <h5>1.1-2 PrimitiveGroup</h5>
116
117 <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PrimitiveGroup</code>( <var class="Arg">deg</var>, <var class="Arg">nr</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
118 <p>returns the primitive permutation group of degree <var class="Arg">deg</var> with number <var class="Arg">nr</var> from the list.</p>
119
120 <p>The arrangement of the groups of degrees not greater than 50 differs from the arrangement of primitive groups in the list of C. Sims, which was used in <strong class="pkg">GAP</strong> 3. See <code class="func">SimsNo</code> (<a href="chap1_mj.html#X790D50447ABDF7EE"><span class="RefLink">1.2-2</span></a>).</p>
121
122 <p><a id="X8564FECC8477F199" name="X8564FECC8477F199"></a></p>
123
124 <h5>1.1-3 NrPrimitiveGroups</h5>
125
126 <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; NrPrimitiveGroups</code>( <var class="Arg">deg</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
127 <p>returns the number of primitive permutation groups of degree <var class="Arg">deg</var> in the library.</p>
128
129
130 <div class="example"><pre>
131 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">NrPrimitiveGroups(25);</span>
132 28
133 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveGroup(25,19);</span>
134 5^2:((Q(8):3)'4)
135 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveGroup(25,20);</span>
136 ASL(2, 5)
137 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveGroup(25,22);</span>
138 AGL(2, 5)
139 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveGroup(25,23);</span>
140 (A(5) x A(5)):2
141 </pre></div>
142
143 <p><a id="X86EF380E8007D304" name="X86EF380E8007D304"></a></p>
144
145 <h5>1.1-4 AllPrimitiveGroups</h5>
146
147 <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; AllPrimitiveGroups</code>( <var class="Arg">attr1</var>, <var class="Arg">val1</var>, <var class="Arg">attr2</var>, <var class="Arg">val2</var>, <var class="Arg">...</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
148 <p>This is a selection function which permits to select all groups from the Primitive Group Library that have a given set of properties. It accepts arguments as specified in Section <a href="../../../doc/ref/chap50_mj.html#X82676ED5826E9E2E"><span class="RefLink">Reference: Selection Functions</span></a> of the <strong class="pkg">GAP</strong> reference manual.</p>
149
150 <p><a id="X82870C177DB70470" name="X82870C177DB70470"></a></p>
151
152 <h5>1.1-5 OnePrimitiveGroup</h5>
153
154 <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; OnePrimitiveGroup</code>( <var class="Arg">attr1</var>, <var class="Arg">val1</var>, <var class="Arg">attr2</var>, <var class="Arg">val2</var>, <var class="Arg">...</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
155 <p>This is a selection function which permits to select at most one group from the Primitive Group Library that have a given set of properties. It accepts arguments as specified in Section <a href="../../../doc/ref/chap50_mj.html#X82676ED5826E9E2E"><span class="RefLink">Reference: Selection Functions</span></a> of the <strong class="pkg">GAP</strong> reference manual.</p>
156
157 <p><a id="X7B1D4C0483A7F444" name="X7B1D4C0483A7F444"></a></p>
158
159 <h5>1.1-6 PrimitiveGroupsIterator</h5>
160
161 <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PrimitiveGroupsIterator</code>( <var class="Arg">attr1</var>, <var class="Arg">val1</var>, <var class="Arg">attr2</var>, <var class="Arg">val2</var>, <var class="Arg">...</var> )</td><td class="tdright">(&nbsp;function&nbsp;)</td></tr></table></div>
162 <p>returns an iterator through <code class="code">AllPrimitiveGroups(<var class="Arg">attr1</var>,<var class="Arg">val1</var>,<var class="Arg">attr2</var>,<var class="Arg">val2</var>,...)</code> without creating all these groups at the same time.</p>
163
164 <p><a id="X81329B9B7F5FF8DE" name="X81329B9B7F5FF8DE"></a></p>
165
166 <h5>1.1-7 COHORTS_PRIMITIVE_GROUPS</h5>
167
168 <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; COHORTS_PRIMITIVE_GROUPS</code></td><td class="tdright">(&nbsp;global variable&nbsp;)</td></tr></table></div>
169 <p>In <a href="chapBib_mj.html#biBDixonMortimer88">[DM88]</a> the primitive groups are sorted in <q>cohorts</q> according to their socle. For each degree less than 2500, the variable <code class="func">COHORTS_PRIMITIVE_GROUPS</code> contains a list of the cohorts for the primitive groups of this degree. Each cohort is represented by a list of length 2, the first entry specifies the socle type (see <code class="func">SocleTypePrimitiveGroup</code> (<a href="../../../doc/ref/chap43_mj.html#X7E89A46A86A3F4A2"><span class="RefLink">Reference: SocleTypePrimitiveGroup</span></a>)), the second entry listing the index numbers of the groups in this degree.</p>
170
171 <p>For example in degree 49, we have four cohorts with socles <span class="SimpleMath">\((ℤ / 7 ℤ)^2\)</span>, <span class="SimpleMath">\(L_2(7)^2\)</span>, <span class="SimpleMath">\(A_7^2\)</span> and <span class="SimpleMath">\(A_{49}\)</span> respectively. the group <code class="code">PrimitiveGroup(49,36)</code>, which is isomorphic to <span class="SimpleMath">\((A_7 \times A_7):2^2\)</span>, lies in the third cohort with socle <span class="SimpleMath">\((A_7 \times A_7)\)</span>.</p>
172
173
174 <div class="example"><pre>
175 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">COHORTS_PRIMITIVE_GROUPS[49];</span>
176 [ [ rec( parameter := 7, series := "Z", width := 2 ),
177 [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
178 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33 ] ],
179 [ rec( parameter := [ 2, 7 ], series := "L", width := 2 ), [ 34 ] ],
180 [ rec( parameter := 7, series := "A", width := 2 ), [ 35, 36, 37, 38 ] ],
181 [ rec( parameter := 49, series := "A", width := 1 ), [ 39, 40 ] ] ]
182 </pre></div>
183
184 <p><a id="X7DA239CC848F6CAE" name="X7DA239CC848F6CAE"></a></p>
185
186 <h4>1.2 <span class="Heading">Index numbers of primitive groups</span></h4>
187
188 <p><a id="X870400597FD4E392" name="X870400597FD4E392"></a></p>
189
190 <h5>1.2-1 PrimitiveIdentification</h5>
191
192 <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PrimitiveIdentification</code>( <var class="Arg">G</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
193 <p>For a primitive permutation group for which an <span class="SimpleMath">\(S_n\)</span>-conjugate exists in the library of primitive permutation groups (see <a href="chap1_mj.html#X7AE00EA7791F2574"><span class="RefLink">1.1</span></a>), this attribute returns the index position. That is <var class="Arg">G</var> is conjugate to <code class="code">PrimitiveGroup(NrMovedPoints(<var class="Arg">G</var>),PrimitiveIdentification(<var class="Arg">G</var>))</code>.</p>
194
195 <p>Methods only exist if the primitive groups library is installed.</p>
196
197 <p>Note: As this function uses the primitive groups library, the result is only guaranteed to the same extent as this library. If it is incomplete, <code class="code">PrimitiveIdentification</code> might return an existing index number for a group not in the library.</p>
198
199
200 <div class="example"><pre>
201 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveIdentification(Group((1,2),(1,2,3)));</span>
202 2
203 </pre></div>
204
205 <p><a id="X790D50447ABDF7EE" name="X790D50447ABDF7EE"></a></p>
206
207 <h5>1.2-2 SimsNo</h5>
208
209 <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; SimsNo</code>( <var class="Arg">G</var> )</td><td class="tdright">(&nbsp;attribute&nbsp;)</td></tr></table></div>
210 <p>If <var class="Arg">G</var> is a primitive group of degree not greater than 50, obtained by <code class="func">PrimitiveGroup</code> (<a href="chap1_mj.html#X7BCEA0C57B6D9F42"><span class="RefLink">1.1-2</span></a>) (respectively one of the selection functions), then this attribute contains the number of the isomorphic group in the original list of C. Sims. (This is the arrangement as it was used in <strong class="pkg">GAP</strong> 3.)</p>
211
212
213 <div class="example"><pre>
214 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g:=PrimitiveGroup(25,2);</span>
215 5^2:S(3)
216 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SimsNo(g);</span>
217 3
218 </pre></div>
219
220 <p>As mentioned in the previous section, the index numbers of primitive groups in <strong class="pkg">GAP</strong> are guaranteed to remain stable. (Thus, missing groups will be added to the library at the end of each degree.) In particular, it is safe to refer to a primitive group of type <var class="Arg">deg</var>, <var class="Arg">nr</var> in the <strong class="pkg">GAP</strong> library.</p>
221
222 <p><a id="X784820DA86D0E6F4" name="X784820DA86D0E6F4"></a></p>
223
224 <h5>1.2-3 PRIMITIVE_INDICES_MAGMA</h5>
225
226 <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PRIMITIVE_INDICES_MAGMA</code></td><td class="tdright">(&nbsp;global variable&nbsp;)</td></tr></table></div>
227 <p>The system <strong class="pkg">Magma</strong> also provides a list of primitive groups (see <a href="chapBib_mj.html#biBRoneyDougal02">[RU03]</a>). For historical reasons, its indexing up to degree 999 differs from the one used by <strong class="pkg">GAP</strong>. The variable <code class="func">PRIMITIVE_INDICES_MAGMA</code> can be used to obtain this correspondence. The magma index number of the <strong class="pkg">GAP</strong> group <code class="code">PrimitiveGroup(<var class="Arg">deg</var>,<var class="Arg">nr</var>)</code> is stored in the entry <code class="code">PRIMITIVE_INDICES_MAGMA[<var class="Arg">deg</var>][<var class="Arg">nr</var>]</code>, for degree at most 999.</p>
228
229 <p>Vice versa, the group of degree <var class="Arg">deg</var> with <strong class="pkg">Magma</strong> index number <var class="Arg">nr</var> has the <strong class="pkg">GAP</strong> index</p>
230
231 <p><code class="code">Position(PRIMITIVE_INDICES_MAGMA[<var class="Arg">deg</var>],<var class="Arg">nr</var>)</code>, in particular it can be obtained by the <strong class="pkg">GAP</strong> command</p>
232
233 <p><code class="code">PrimitiveGroup(<var class="Arg">deg</var>,Position(PRIMITIVE_INDICES_MAGMA[<var class="Arg">deg</var>],<var class="Arg">nr</var>));</code></p>
234
235
236 <div class="chlinkprevnextbot">&nbsp;<a href="chap0_mj.html">[Top of Book]</a>&nbsp; <a href="chap0_mj.html#contents">[Contents]</a>&nbsp; &nbsp;<a href="chap0_mj.html">[Previous Chapter]</a>&nbsp; &nbsp;<a href="chap2_mj.html">[Next Chapter]</a>&nbsp; </div>
237
238
239 <div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
240
241 <hr />
242 <p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
243 </body>
244 </html>