Debian Codegraph @

doc/chap1.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 <title>GAP (primgrp) - Chapter 1: Primitive Permutation Groups</title>
9 <meta http-equiv="content-type" content="text/html; charset=UTF-8" />
10 <meta name="generator" content="GAPDoc2HTML" />
11 <link rel="stylesheet" type="text/css" href="manual.css" />
12 <script src="manual.js" type="text/javascript"></script>
13 <script type="text/javascript">overwriteStyle();</script>
14 </head>
15 <body class="chap1" onload="jscontent()">
16
17
18 <div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
19
20 <div class="chlinkprevnexttop">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp; <a href="chap0.html#contents">[Contents]</a>&nbsp; &nbsp;<a href="chap0.html">[Previous Chapter]</a>&nbsp; &nbsp;<a href="chap2.html">[Next Chapter]</a>&nbsp; </div>
21
22 <p id="mathjaxlink" class="pcenter"><a href="chap1_mj.html">[MathJax on]</a></p>
23 <p><a id="X7AE00EA7791F2574" name="X7AE00EA7791F2574"></a></p>
24 <div class="ChapSects"><a href="chap1.html#X7AE00EA7791F2574">1 <span class="Heading">Primitive Permutation Groups</span></a>
25 <div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap1.html#X7AE00EA7791F2574">1.1 <span class="Heading">Primitive Permutation Groups</span></a>
26 </span>
27 <div class="ContSSBlock">
28 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1.html#X81BDF8CA7CCBFC95">1.1-1 PrimitiveGroupsAvailable</a></span>
29 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1.html#X7BCEA0C57B6D9F42">1.1-2 PrimitiveGroup</a></span>
30 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1.html#X8564FECC8477F199">1.1-3 NrPrimitiveGroups</a></span>
31 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1.html#X86EF380E8007D304">1.1-4 AllPrimitiveGroups</a></span>
32 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1.html#X82870C177DB70470">1.1-5 OnePrimitiveGroup</a></span>
33 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1.html#X7B1D4C0483A7F444">1.1-6 PrimitiveGroupsIterator</a></span>
34 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1.html#X81329B9B7F5FF8DE">1.1-7 COHORTS_PRIMITIVE_GROUPS</a></span>
35 </div></div>
36 <div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap1.html#X7DA239CC848F6CAE">1.2 <span class="Heading">Index numbers of primitive groups</span></a>
37 </span>
38 <div class="ContSSBlock">
39 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1.html#X870400597FD4E392">1.2-1 PrimitiveIdentification</a></span>
40 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1.html#X790D50447ABDF7EE">1.2-2 SimsNo</a></span>
41 <span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap1.html#X784820DA86D0E6F4">1.2-3 PRIMITIVE_INDICES_MAGMA</a></span>
42 </div></div>
43 </div>
44
45 <h3>1 <span class="Heading">Primitive Permutation Groups</span></h3>
46
47 <p><a id="X7AE00EA7791F2574" name="X7AE00EA7791F2574"></a></p>
48
49 <h4>1.1 <span class="Heading">Primitive Permutation Groups</span></h4>
50
51 <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.html#biBRoneyDougal05">[Ron05]</a> and <a href="chapBib.html#biBCRDQ11">[Qui11]</a>, in particular,</p>
52
53
54 <ul>
55 <li><p>the primitive permutation groups up to degree 50, calculated by C. Sims,</p>
56
57 </li>
58 <li><p>the primitive groups with insoluble socles of degree <span class="SimpleMath">&lt; 1000</span> as calculated in <a href="chapBib.html#biBDixonMortimer88">[DM88]</a>,</p>
59
60 </li>
61 <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.html#biBSho92">[Sho92]</a>,</p>
62
63 </li>
64 <li><p>some insolvable affine primitive permutation groups of degree <span class="SimpleMath">&lt; 256</span> as calculated in <a href="chapBib.html#biBTheissen97">[The97]</a>.</p>
65
66 </li>
67 <li><p>The solvable primitive groups of degree up to <span class="SimpleMath">999</span> as calculated in <a href="chapBib.html#biBEickHoefling02">[EH03]</a>.</p>
68
69 </li>
70 <li><p>The primitive groups of affine type of degree up to <span class="SimpleMath">999</span> as calculated in <a href="chapBib.html#biBRoneyDougal02">[RU03]</a>.</p>
71
72 </li>
73 </ul>
74 <p>Not all groups are named, those which do have names use ATLAS notation. Not all names are necessarily unique!</p>
75
76 <p>The list given in <a href="chapBib.html#biBRoneyDougal05">[Ron05]</a> is believed to be complete, correcting various omissions in <a href="chapBib.html#biBDixonMortimer88">[DM88]</a>, <a href="chapBib.html#biBSho92">[Sho92]</a> and <a href="chapBib.html#biBTheissen97">[The97]</a>.</p>
77
78 <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>
79
80
81 <ul>
82 <li><p>All groups in the library are primitive permutation groups of the indicated degree.</p>
83
84 </li>
85 <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>
86
87 </li>
88 <li><p>Different groups in the library are not conjugate in <span class="SimpleMath">S_n</span>.</p>
89
90 </li>
91 <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>
92
93 </li>
94 </ul>
95 <p>(Note that the arrangement of groups is not guaranteed to be in increasing size, though it holds for many degrees.)</p>
96
97 <p>The selection functions (see <a href="../../../doc/ref/chap50.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>
98
99 <p><code class="func">NrMovedPoints</code> (<a href="../../../doc/ref/chap42.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.html#X858ADA3B7A684421"><span class="RefLink">Reference: Size</span></a>), <code class="func">Transitivity</code> (<a href="../../../doc/ref/chap41.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.html#X7E50211A7B92455F"><span class="RefLink">Reference: ONanScottType</span></a>), <code class="func">IsSimpleGroup</code> (<a href="../../../doc/ref/chap39.html#X7A6685D7819AEC32"><span class="RefLink">Reference: IsSimpleGroup</span></a>), <code class="func">IsSolvableGroup</code> (<a href="../../../doc/ref/chap39.html#X809C78D5877D31DF"><span class="RefLink">Reference: IsSolvableGroup</span></a>), and <code class="func">SocleTypePrimitiveGroup</code> (<a href="../../../doc/ref/chap43.html#X7E89A46A86A3F4A2"><span class="RefLink">Reference: SocleTypePrimitiveGroup</span></a>).</p>
100
101 <p>(Note, that for groups of degree up to 2499, O'Nan-Scott types 4a, 4b and 5 cannot occur.)</p>
102
103 <p><a id="X81BDF8CA7CCBFC95" name="X81BDF8CA7CCBFC95"></a></p>
104
105 <h5>1.1-1 PrimitiveGroupsAvailable</h5>
106
107 <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>
108 <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>
109
110 <p><a id="X7BCEA0C57B6D9F42" name="X7BCEA0C57B6D9F42"></a></p>
111
112 <h5>1.1-2 PrimitiveGroup</h5>
113
114 <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>
115 <p>returns the primitive permutation group of degree <var class="Arg">deg</var> with number <var class="Arg">nr</var> from the list.</p>
116
117 <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.html#X790D50447ABDF7EE"><span class="RefLink">1.2-2</span></a>).</p>
118
119 <p><a id="X8564FECC8477F199" name="X8564FECC8477F199"></a></p>
120
121 <h5>1.1-3 NrPrimitiveGroups</h5>
122
123 <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>
124 <p>returns the number of primitive permutation groups of degree <var class="Arg">deg</var> in the library.</p>
125
126
127 <div class="example"><pre>
128 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">NrPrimitiveGroups(25);</span>
129 28
130 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveGroup(25,19);</span>
131 5^2:((Q(8):3)'4)
132 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveGroup(25,20);</span>
133 ASL(2, 5)
134 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveGroup(25,22);</span>
135 AGL(2, 5)
136 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveGroup(25,23);</span>
137 (A(5) x A(5)):2
138 </pre></div>
139
140 <p><a id="X86EF380E8007D304" name="X86EF380E8007D304"></a></p>
141
142 <h5>1.1-4 AllPrimitiveGroups</h5>
143
144 <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>
145 <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.html#X82676ED5826E9E2E"><span class="RefLink">Reference: Selection Functions</span></a> of the <strong class="pkg">GAP</strong> reference manual.</p>
146
147 <p><a id="X82870C177DB70470" name="X82870C177DB70470"></a></p>
148
149 <h5>1.1-5 OnePrimitiveGroup</h5>
150
151 <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>
152 <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.html#X82676ED5826E9E2E"><span class="RefLink">Reference: Selection Functions</span></a> of the <strong class="pkg">GAP</strong> reference manual.</p>
153
154 <p><a id="X7B1D4C0483A7F444" name="X7B1D4C0483A7F444"></a></p>
155
156 <h5>1.1-6 PrimitiveGroupsIterator</h5>
157
158 <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>
159 <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>
160
161 <p><a id="X81329B9B7F5FF8DE" name="X81329B9B7F5FF8DE"></a></p>
162
163 <h5>1.1-7 COHORTS_PRIMITIVE_GROUPS</h5>
164
165 <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>
166 <p>In <a href="chapBib.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.html#X7E89A46A86A3F4A2"><span class="RefLink">Reference: SocleTypePrimitiveGroup</span></a>)), the second entry listing the index numbers of the groups in this degree.</p>
167
168 <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 × A_7):2^2</span>, lies in the third cohort with socle <span class="SimpleMath">(A_7 × A_7)</span>.</p>
169
170
171 <div class="example"><pre>
172 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">COHORTS_PRIMITIVE_GROUPS[49];</span>
173 [ [ rec( parameter := 7, series := "Z", width := 2 ),
174 [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
175 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33 ] ],
176 [ rec( parameter := [ 2, 7 ], series := "L", width := 2 ), [ 34 ] ],
177 [ rec( parameter := 7, series := "A", width := 2 ), [ 35, 36, 37, 38 ] ],
178 [ rec( parameter := 49, series := "A", width := 1 ), [ 39, 40 ] ] ]
179 </pre></div>
180
181 <p><a id="X7DA239CC848F6CAE" name="X7DA239CC848F6CAE"></a></p>
182
183 <h4>1.2 <span class="Heading">Index numbers of primitive groups</span></h4>
184
185 <p><a id="X870400597FD4E392" name="X870400597FD4E392"></a></p>
186
187 <h5>1.2-1 PrimitiveIdentification</h5>
188
189 <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>
190 <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.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>
191
192 <p>Methods only exist if the primitive groups library is installed.</p>
193
194 <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>
195
196
197 <div class="example"><pre>
198 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PrimitiveIdentification(Group((1,2),(1,2,3)));</span>
199 2
200 </pre></div>
201
202 <p><a id="X790D50447ABDF7EE" name="X790D50447ABDF7EE"></a></p>
203
204 <h5>1.2-2 SimsNo</h5>
205
206 <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>
207 <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.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>
208
209
210 <div class="example"><pre>
211 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">g:=PrimitiveGroup(25,2);</span>
212 5^2:S(3)
213 <span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SimsNo(g);</span>
214 3
215 </pre></div>
216
217 <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>
218
219 <p><a id="X784820DA86D0E6F4" name="X784820DA86D0E6F4"></a></p>
220
221 <h5>1.2-3 PRIMITIVE_INDICES_MAGMA</h5>
222
223 <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>
224 <p>The system <strong class="pkg">Magma</strong> also provides a list of primitive groups (see <a href="chapBib.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>
225
226 <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>
227
228 <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>
229
230 <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>
231
232
233 <div class="chlinkprevnextbot">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp; <a href="chap0.html#contents">[Contents]</a>&nbsp; &nbsp;<a href="chap0.html">[Previous Chapter]</a>&nbsp; &nbsp;<a href="chap2.html">[Next Chapter]</a>&nbsp; </div>
234
235
236 <div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
237
238 <hr />
239 <p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
240 </body>
241 </html>