<html><head><title>[Nilmat] 2 Computing with nilpotent linear groups</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP001.htm">Previous</a>] [<a href ="CHAP003.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>2 Computing with nilpotent linear groups</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP002.htm#SECT001">Preliminaries</a> <li> <A HREF="CHAP002.htm#SECT002">Testing nilpotency</a> <li> <A HREF="CHAP002.htm#SECT003">Finiteness, Sylow subgroups, testing complete reducibility</a> <li> <A HREF="CHAP002.htm#SECT004">A library of primitive nilpotent groups</a> <li> <A HREF="CHAP002.htm#SECT005">Further examples of nilpotent matrix groups</a> </ol><p> <p> <a name = "I0"></a> This chapter contains the main functions of this package for computing with nilpotent matrix groups. <p> <p> <h2><a name="SECT001">2.1 Preliminaries</a></h2> <p><p> We first describe some of the basic functions used in <font face="Gill Sans,Helvetica,Arial">Nilmat</font> for nilpotency testing of a group <var>G</var> input by a finite generating set of matrices. <p> <a name = "SSEC001.1"></a> <li><code>JordanSplitting( </code><var>G</var><code> ) A</code> <p> For a subgroup <var>G</var> of <var>GL(n,<font face="helvetica,arial">F</font>)</var>, <var><font face="helvetica,arial">F</font>=GF(q)</var> or <var><font face="helvetica,arial">Q</font></var>, returns a list of two groups <var>[S,U]</var>, where <var>S</var> is the semisimple part of <var>G</var> (the group generated by the semisimple parts of the generators of <var>G</var>), and <var>U</var> is the unipotent part of <var>G</var> (the group generated by the unipotent parts of the generators of <var>G</var>). If <var>G</var> is nilpotent, then <var>G congS timesU</var>, the group <var>S</var> is completely reducible and <var>U</var> is unipotent. This attribute relies on the <font face="Gill Sans,Helvetica,Arial">GAP</font> attribute <code>JordanDecomposition</code>. <p> <a name = "SSEC001.2"></a> <li><code>IsUnipotentMatGroup( </code><var>G</var><code> ) P</code> <p> For a subgroup <var>G</var> of <var>GL(n,<font face="helvetica,arial">F</font>)</var>, <var><font face="helvetica,arial">F</font>=GF(q)</var> or <var><font face="helvetica,arial">Q</font></var>, returns <code>true</code> if <var>G</var> is unipotent (i.e. conjugate to a group of upper unitriangular matrices) and <code>false</code> otherwise. <p> <a name = "SSEC001.3"></a> <li><code>ClassLimit( </code><var>n</var><code> , </code><var>F</var><code> ) F</code> <p> returns an upper bound on the nilpotency class of nilpotent subgroups of <var>GL(n,<font face="helvetica,arial">F</font>)</var>, <var><font face="helvetica,arial">F</font>=GF(q)</var> or <var><font face="helvetica,arial">Q</font></var>. <p> <a name = "SSEC001.4"></a> <li><code>AbelianNormalSeries( </code><var>G</var><code>, </code><var>l</var><code> ) F</code> <p> Here <var>G< GL(n,q)</var> and <var>l</var> is a positive integer. If <var>G</var> is nilpotent of class at most <var>l</var> and the order of <var>G</var> is coprime to the characteristic of <var>GF(q)</var>, then this function determines a normal series with abelian factors for <var>G</var>. Otherwise, the function may still return such a series or it may return <code>fail</code>. The function is based on recursively selecting non-central elements from the second centers of terms in the abelian series. <p> <a name = "SSEC001.5"></a> <li><code>PiPrimarySplitting( </code><var>G</var><code> ) A</code> <p> For a subgroup <var>G</var> of <var>GL(n,q)</var>, this function returns a list of two subgroups <var>[B,C]</var> with <var>G = BC</var>. If <var>G</var> is nilpotent, then <var>G congB timesC</var>, the group <var>C</var> is the product of all Sylow <var>p</var>-subgroups with <var>p>n</var> and <var>B</var> is the product of all other Sylow subgroups of <var>G</var>. <p> <p> <h2><a name="SECT002">2.2 Testing nilpotency</a></h2> <p><p> The following is one of the main functions of the <font face="Gill Sans,Helvetica,Arial">Nilmat</font> package. <p> <a name = "SSEC002.1"></a> <li><code>IsNilpotentMatGroup( </code><var>G</var><code> ) F</code> <p> For a subgroup <var>G</var> of <var>GL(n,<font face="helvetica,arial">F</font>)</var>, <var><font face="helvetica,arial">F</font>=GF(q)</var> or <var><font face="helvetica,arial">Q</font></var>, returns <code>true</code> if <var>G</var> is nilpotent and <code>false</code> otherwise. This function is also installed as method for the property <code>IsNilpotentGroup</code>. <p> We include a brief description of the algorithm behind this function. Let <var>X</var> be a generating set of the given group <var>G</var>. The first stage of testing nilpotency of <var>G</var> is reduction to the semisimple part <var>S</var> of <var>G</var>. The procedure for reducing to the semisimple case is based on the <font face="Gill Sans,Helvetica,Arial">Nilmat</font> functions <code>JordanSplitting</code> and <code>IsUnipotentGroup</code> described in the previous section. In the following, we assume that all elements of <var>X</var> are semisimple matrices. <p> If <var><font face="helvetica,arial">F</font>=GF(q)</var>, then we apply the function <code>PiPrimarySplitting</code> to the group <var>S</var> and thus reduce to a smaller group <var>B</var>. Next, we attempt to compute an abelian normal series for <var>B</var> using the function <code>AbelianNormalSeries</code>. If no such series exists, then <var>G</var> is not nilpotent. If such a series exists, then we use it to construct the Sylow subgroups of <var>B</var> and check that they commute pairwise. For details on this method, see <a href="biblio.htm#DF06"><cite>DF06</cite></a>. <p> If <var><font face="helvetica,arial">F</font>=<font face="helvetica,arial">Q</font></var>, then we first use a reduction mod <var>p</var> for a suitable prime <var>p</var> and check that the image of <var>G</var> under the corresponding congruence homomorphism is nilpotent using the finite field method above. If so, then we construct the kernel of the congruence homomorphism and test whether this is central in <var>G</var>. We refer to <a href="biblio.htm#DF07"><cite>DF07</cite></a> for details. Note that the construction of the congruence homomorphism and its kernel is based on the methods of the Package <font face="Gill Sans,Helvetica,Arial">Polenta</font>; see also <a href="biblio.htm#AE05"><cite>AE05</cite></a> for background. <p> The nilpotency testing functions of the package <font face="Gill Sans,Helvetica,Arial">Nilmat</font> have advantages over the standard <font face="Gill Sans,Helvetica,Arial">GAP</font> methods for <code>IsNilpotentGroup</code>. When <var><font face="helvetica,arial">F</font></var> is finite, the <font face="Gill Sans,Helvetica,Arial">Nilmat</font> functions have better runtimes for all input groups we tested. When <var><font face="helvetica,arial">F</font></var> is infinite, the standard <font face="Gill Sans,Helvetica,Arial">GAP</font> functions frequently do not terminate at all in sensible time; on the other hand, the <font face="Gill Sans,Helvetica,Arial">Nilmat</font> functions always terminate, with comparatively small runtimes (see the examples in Chapter 3). <p> <p> <h2><a name="SECT003">2.3 Finiteness, Sylow subgroups, testing complete reducibility</a></h2> <p><p> The function <code>IsNilpotentMatGroup</code> determines various structural properties of the given group as by-products. The functions in this section have been designed to exploit these by-products. <p> <a name = "SSEC003.1"></a> <li><code>IsFiniteNilpotentMatGroup( </code><var>G</var><code> ) F</code> <p> For a nilpotent subgroup <var>G</var> of <var>GL(n,<font face="helvetica,arial">Q</font>)</var>, returns <code>true</code> if <var>G</var> is finite and <code>false</code> otherwise. Note that the function assumes that <var>G</var> is nilpotent and may return an incorrect result if not. The function exploits the by-products of the nilpotency testing functions in <font face="Gill Sans,Helvetica,Arial">Nilmat</font> and hence runs particularly fast (and usually faster than the standard <font face="Gill Sans,Helvetica,Arial">GAP</font> method for testing finiteness) if they have been used to check nilpotency. This function is also installed as method for the property <code>IsFinite</code>. <p> <a name = "SSEC003.2"></a> <li><code>SylowSubgroupsOfNilpotentFFMatGroup( </code><var>G</var><code> ) F</code> <p> For a nilpotent subgroup <var>G</var> of <var>GL(n,<font face="helvetica,arial">F</font>)</var>, <var><font face="helvetica,arial">F</font>=GF(q)</var>, returns the list of all Sylow subgroups. The advantage of this function over the <font face="Gill Sans,Helvetica,Arial">GAP</font> function <code>SylowSubgroup</code> is that the former function returns all Sylow subgroups of <var>G</var> without first computing all prime divisors of the order of <var>G</var>. This function is installed as method for <code>SylowSystem</code> for nilpotent matrix groups. <p> <a name = "SSEC003.3"></a> <li><code>SizeOfNilpotentMatGroup( </code><var>G</var><code> ) F</code> <p> For a finite nilpotent subgroup <var>G</var> of <var>GL(n,<font face="helvetica,arial">F</font>)</var>, <var><font face="helvetica,arial">F</font>=GF(q)</var> or <var><font face="helvetica,arial">Q</font></var>, this function returns the order of <var>G</var>. The function is based on by-products of the nilpotency testing in <font face="Gill Sans,Helvetica,Arial">Nilmat</font>. Again, in some situations it is more efficient than the similar default <font face="Gill Sans,Helvetica,Arial">GAP</font> function; see the examples in Chapter 3. <p> <a name = "SSEC003.4"></a> <li><code>IsCompletelyReducibleNilpotentMatGroup( </code><var>G</var><code> ) F</code> <p> For a nilpotent subgroup <var>G</var> of <var>GL(n,<font face="helvetica,arial">F</font>)</var>, <var><font face="helvetica,arial">F</font>=GF(q)</var> or <var><font face="helvetica,arial">Q</font></var>, returns <code>true</code> if <var>G</var> is completely reducible and <code>false</code> otherwise. <p> <p> <h2><a name="SECT004">2.4 A library of primitive nilpotent groups</a></h2> <p><p> Another main part of <font face="Gill Sans,Helvetica,Arial">Nilmat</font> is a library of nilpotent primitive matrix groups over finite fields. <p> <a name = "SSEC004.1"></a> <li><code>NilpotentPrimitiveMatGroups( </code><var>n</var><code> , </code><var>p</var><code> , </code><var>l</var><code> ) F</code> <p> returns a complete and irredundant list <var>L</var> of the conjugacy class representatives of the nilpotent primitive subgroups of <var>GL(n,p<sup>l</sup>)</var>. The list <var>L</var> contains non-abelian (i.e. non-cyclic) subgroups only if <var>n=2m</var>, <var>m</var> is odd, and <var>p<sup>l</sup> equiv3</var> mod <var>4</var>. Every non-abelian group in <var>L</var> is given by three generators. Note that the groups in <var>L</var> know their orders i.e. the attribute <code>Size</code> has been set for these groups. <p> <a name = "SSEC004.2"></a> <li><code>SizesOfNilpotentPrimitiveMatGroups( </code><var>n</var><code> , </code><var>p</var><code> , </code><var>l</var><code> ) F</code> <p> returns the list of orders of groups in the list <var>L</var> output by <code>NilpotentPrimitiveMatGroups( </code><var>n</var><code> , </code><var>p</var><code> , </code><var>l</var><code> )</code>. <p> <p> <h2><a name="SECT005">2.5 Further examples of nilpotent matrix groups</a></h2> <p><p> In this section we describe various functions designed to produce interesting examples of nilpotent matrix groups. <p> <a name = "SSEC005.1"></a> <li><code>MaximalAbsolutelyIrreducibleNilpotentMatGroup( </code><var>n</var><code> , </code><var>p</var><code> , </code><var>l</var><code>) F</code> <p> constructs the unique (up to conjugacy) maximal absolutely irreducible nilpotent subgroup of <var>GL(n,p<sup>l</sup>)</var> if such a group exists. Note that such a group exists if and only if each prime divisor of <var>n</var> divides <var>p<sup>l</sup>-1</var>. Otherwise the function returns <code>fail</code>. <p> <a name = "SSEC005.2"></a> <li><code>MonomialNilpotentMatGroup( </code><var>n</var><code> ) F</code> <p> constructs an example of a finite nilpotent monomial subgroup of <var>GL(n,<font face="helvetica,arial">Q</font>)</var>. <p> <a name = "SSEC005.3"></a> <li><code>ReducibleNilpotentMatGroup( </code><var>m</var><code>, </code><var>k</var><code>, [</code><var>p</var><code>, </code><var>l</var><code>] ) F</code> <p> constructs an example of a reducible but not completely reducible nilpotent subgroup of <var>GL(mk, <font face="helvetica,arial">F</font>)</var>, where <var><font face="helvetica,arial">F</font>= <font face="helvetica,arial">Q</font></var> if there are two arguments given and <var><font face="helvetica,arial">F</font>= GF(p<sup>l</sup>)</var> if there are four arguments given. <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP001.htm">Previous</a>] [<a href ="CHAP003.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <address>Nilmat manual<br>June 2007 </address></body></html>