<html><head><title>[cubefree] 2 Functionality of the Cubefree package</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 Functionality of the Cubefree package</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP002.htm#SECT001">New methods</a>
<li> <A HREF="CHAP002.htm#SECT002">Comments on the implementation</a>
<li> <A HREF="CHAP002.htm#SECT003">Comments on the efficiency</a>
<li> <A HREF="CHAP002.htm#SECT004">An example session</a>
<li> <A HREF="CHAP002.htm#SECT005">Accuracy check</a>
</ol><p>
<p>
<a name = "I0"></a>
This chapter describes the methods available from the <font face="Gill Sans,Helvetica,Arial">Cubefree</font> package.
<p>
<p>
<h2><a name="SECT001">2.1 New methods</a></h2>
<p><p>
This section lists the implemented functions.
<p>
<a name = "SSEC001.1"></a>
<li><code>ConstructAllCFGroups( </code><var>order</var><code> ) F</code>
<p>
The input <var>order</var> has to be a positive cubefree integer. The output is a complete and irredundant list of isomorphism
type representatives of groups of this size. If possible, the groups are given
as pc groups and as permutations groups otherwise.
<p>
<a name = "SSEC001.2"></a>
<li><code>ConstructAllCFSolvableGroups( </code><var>order</var><code> ) F</code>
<p>
The input <var>order</var> has to be a positive cubefree integer. The output is a complete and irredundant list of isomorphism
type representatives of solvable groups of this size. The groups are given as pc groups.
<p>
<a name = "SSEC001.3"></a>
<li><code>ConstructAllCFNilpotentGroups( </code><var>order</var><code> ) F</code>
<p>
The input <var>order</var> has to be a positive cubefree integer. The output is a complete and irredundant list of isomorphism
type representatives of nilpotent groups of this size. The groups are given as pc groups.
<p>
<a name = "SSEC001.4"></a>
<li><code>ConstructAllCFSimpleGroups( </code><var>order</var><code> ) F</code>
<p>
The input <var>order</var> has to be a positive cubefree integer. The output is a complete and irredundant list of isomorphism
type representatives of simple groups of this size. In particular, there
exists either none or exactly one simple group of the given order.
<p>
<a name = "SSEC001.5"></a>
<li><code>ConstructAllCFFrattiniFreeGroups( </code><var>order</var><code> ) F</code>
<p>
The input <var>order</var> has to be a positive cubefree integer. The output is a complete and irredundant list of isomorphism
type representatives of Frattini-free groups of this size.
<p>
<a name = "SSEC001.6"></a>
<li><code>NumberCFGroups( </code><var>n</var><code>[, </code><var>bool</var><code> ] ) F</code>
<p>
The input <var>n</var> has to be a positive cubefree integer and the output is the number of all
cubefree groups of order <var>n</var>. The <font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library is used for squarefree
orders, orders of the type <var>p<sup>2</sup></var> and <var>p<sup>2</sup>q</var>, and cubefree orders less than
50000. Only if <var>bool</var> is set to false, then only the squarefree
orders and orders of the type <var>p<sup>2</sup></var> and <var>p<sup>2</sup>q</var>,are taken from the <font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library.
<p>
<a name = "SSEC001.7"></a>
<li><code>NumberCFSolvableGroups( </code><var>n</var><code>[, </code><var>bool</var><code> ] ) F</code>
<p>
The input <var>n</var> has to be a positive cubefree integer and the output is the number of all
cubefree solvable groups of order <var>n</var>. The <font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library is used for squarefree
orders, orders of the type <var>p<sup>2</sup></var> and <var>p<sup>2</sup>q</var>, and cubefree orders less than
50000. Only if <var>bool</var> is set to false, then only the squarefree
orders and orders of the type <var>p<sup>2</sup></var> and <var>p<sup>2</sup>q</var>,are taken from the <font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library.
<p>
<a name = "SSEC001.8"></a>
<li><code>CountAllCFGroupsUpTo( </code><var>n</var><code>[, </code><var>bool</var><code> ]) F</code>
<p>
The input is a positive integer <var>n</var> and the output is a list <var>L</var> of size <var>n</var> such that
<var>L[i]</var> contains the number of isomorphism types of groups of order <var>i</var> if <var>i</var>
is cubefree and <var>L[i]</var> is not bound, otherwise, <var>1leqi leqn</var>. The
<font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library is used for squarefree orders, orders of the type <var>p<sup>2</sup></var> and <var>p<sup>2</sup>q</var>, and cubefree orders less than
50000. Only if <var>bool</var> is set to false, then only the squarefree
orders and orders of the type <var>p<sup>2</sup></var> and <var>p<sup>2</sup>q</var> are taken from the
<font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library. This function was implemented only for experimental
purposes and its implementation could be improved.
<p>
<a name = "SSEC001.9"></a>
<li><code>CubefreeOrderInfo( </code><var>n</var><code>[, </code><var>bool</var><code> ] ) F</code>
<p>
This function displays some (very vague)
information about the complexity of the construction of the groups of
(cubefree) order <var>n</var>. It returns the number of possible pairs <var>(a,b)</var> where
<var>a</var> is the order of a Frattini-free group <var>F</var> with socle <var>S</var> of order <var>b</var> which
has to be constructed in order to construct all groups of order <var>n</var>: In fact,
for each of these pairs <var>(a,b)</var> one would have to construct up to conjugacy all
subgroups of order <var>a/b</var> of Aut<var>(S)</var>. The sum of the numbers of these
subgroups for all pairs <var>(a,b)</var> as above is the number of groups of order
<var>n</var>. Thus the output of <code>CubefreeOrderInfo</code> is a trivial lower bound for the number of
groups of order <var>n</var>. There is no additional information
displayed if <var>bool</var> is set to false.
<p>
<a name = "SSEC001.10"></a>
<li><code>CubefreeTestOrder( </code><var>n</var><code> ) F</code>
<p>
The input has to be a cubefree integer between 1 and 50000. This function
tests the functionality of <font face="Gill Sans,Helvetica,Arial">Cubefree</font>, i.e. functions (1)--(7), and compares it with the data
of the <font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library. It returns true if everything is okay,
otherwise an error message will be displayed.
<p>
<a name = "SSEC001.11"></a>
<li><code>IsCubeFreeInt( </code><var>n</var><code> ) P</code>
<p>
The output is <var>true</var> if <var>n</var> is a cubefree integer and <var>false</var> otherwise.
<p>
<a name = "SSEC001.12"></a>
<li><code>IsSquareFreeInt( </code><var>n</var><code> ) P</code>
<p>
The output is <var>true</var> if <var>n</var> is a squarefree integer and <var>false</var> otherwise.
<p>
<a name = "SSEC001.13"></a>
<li><code>IrreducibleSubgroupsOfGL( </code><var>n</var><code>, </code><var>q</var><code> ) O</code>
<p>
The current version of this function allows only <var>n</var>=2. The input <var>q</var> has to be a prime-power <var>q</var><var>=p<sup>r</sup></var> with <var>pgeq5</var> a prime. The output
is a list of all irreducible subgroups of GL<var>(2,q)</var> up to conjugacy.
<p>
<a name = "SSEC001.14"></a>
<li><code>RewriteAbsolutelyIrreducibleMatrixGroup( </code><var>G</var><code> ) F</code>
<p>
The input <var>G</var> has to be an absolutely irreducible matrix group over a finite
field GF<var>(q)</var>. If possible, the output is
<var>G</var> rewritten over the subfield of GF<var>(q)</var> generated by the traces of the
elements of <var>G</var>. If no rewriting is possible, then the
input <var>G</var> is returned.
<p>
<p>
<h2><a name="SECT002">2.2 Comments on the implementation</a></h2>
<p><p>
This section provides some information about the implementations.
<p>
<strong>ConstructAllCFGroups</strong>
<p>
The function <code>ConstructAllCFGroups</code> constructs all groups of a given
cubefree order up to isomorphism using the Frattini Extension Method as described in <a href="biblio.htm#Di05"><cite>Di05</cite></a>,
<a href="biblio.htm#DiEi05"><cite>DiEi05</cite></a>, <a href="biblio.htm#BeEia"><cite>BeEia</cite></a>, and <a href="biblio.htm#BeEib"><cite>BeEib</cite></a>. One step in the Frattini
Extension Method is to compute Frattini extensions
and for this purpose some already implemented
methods of the required <font face="Gill Sans,Helvetica,Arial">GAP</font> package <font face="Gill Sans,Helvetica,Arial">GrpConst</font> are used.
<p>
Since <code>ConstructAllCFGroups</code> requires only
some special types of irreducible subgroups of GL<var>(2,p)</var> (e.g. of cubefree order), it
contains a modified internal version of
<code>IrreducibleSubgroupsOfGL</code>. This means that the latter is not called explicitely by
<code>ConstructAllCFGroups</code>.
<p>
<p>
<p>
<strong>ConstructAllCFSimpleGroups and ConstructAllCFNilpotentGroups</strong>
<p>
The construction of simple or nilpotent groups of cubefree
order is rather easy, see <a href="biblio.htm#Di05"><cite>Di05</cite></a> or <a href="biblio.htm#DiEi05"><cite>DiEi05</cite></a>. In particular, the
methods used in these cases are independent from the methods used in the general cubefree case.
<p>
<strong>CountAllCFGroupsUpTo</strong>
<p>
As described in <a href="biblio.htm#Di05"><cite>Di05</cite></a> and <a href="biblio.htm#DiEi05"><cite>DiEi05</cite></a>, every cubefree group <var>G</var> has
the form <var>G=AtimesI</var> where <var>A</var> is trivial or non-abelian simple and <var>I</var> is
solvable. Further, there is a one-to-one correspondence between the solvable
cubefree groups and <var>some</var> solvable Frattini-free groups. This one-to-one
correspondence allows to count the number of groups of a given cubefree order without
computing any Frattini extension.
To reduce runtime, the
computed irreducible and reducible subgroups of the general linear groups
GL<var>(2,p)</var> and also the number of the computed solvable
Frattini-free groups are stored during the whole computation. This is very
memory consuming but reduces the runtime significantly. The alternative is to
run a loop over <code>NumberCFGroups</code>.
This function was implemented only for experimental purposes and its
implementation could be improved.
<p>
<strong>IrreducibleSubgroupsOfGL</strong>
<p>
If the input is a matrix group over GF<var>(q)</var>, then the algorithm needs to
construct GF<var>(q<sup>3</sup>)</var> or GF<var>(q<sup>6</sup>)</var> internally.
<p>
<strong>RewriteAbsolutelyIrreducibleMatrixGroup</strong>
<p>
The function <code>RewriteAbsolutelyIrreducibleMatrixGroup</code> as described
algorithmically in
<a href="biblio.htm#GlHo97"><cite>GlHo97</cite></a> is a probabilistic Las Vegas algorithm; it retries until a correct
answer is returned. If the input is <var>Gleq</var>GL<var>(d,p<sup>r</sup>)</var>, then the
expected runtime is <var>O(rd<sup>3</sup>)</var>.
<p>
<p>
<h2><a name="SECT003">2.3 Comments on the efficiency</a></h2>
<p><p>
The package <font face="Gill Sans,Helvetica,Arial">GrpConst</font> contains several implementations of algorithms to
construct groups of a given order. One of these algorithms is the Frattini
extension method, see Chapter 1. The algorithm used in
<font face="Gill Sans,Helvetica,Arial">Cubefree</font> is a modification of the Frattini extension method to the case of
cubefree orders.
<p>
The advantage of this modification is that the isomorphism
problem at the construction of Frattini extensions is solved completely on a
theoretic level. Also, the construction of the Frattini-free groups up to
isomorphism is reduced to the determination of certain subgroups of groups of
the type GL<var>(2,p)</var> and <var>C<sub>p-1</sub></var>, <var>p</var> a prime, and to the construction of subdirect products
of these subgroups. As this is exponential, this is a main bottleneck of the current implementation.
<p>
A modification of the Frattini extension method to squarefree orders yields a
powerful
construction algorithm for squarefree groups which is based on number theory
only. An implementation of this algorithm can be found
in the <font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library. Thus for squarefree
groups one should definitely use <code>AllSmallGroups</code> and <code>NumberSmallGroups</code>
instead of the functions of <font face="Gill Sans,Helvetica,Arial">Cubefree</font>. The same holds for groups of order
<var>p<sup>2</sup></var> or <var>p<sup>2</sup>q</var>.
<p>
Moreover, using the functionality of <font face="Gill Sans,Helvetica,Arial">Cubefree</font>, the <font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library now
contains all groups of cubefree order at most 50000. Hence, also in this case,
one should prefer <code>AllSmallGroups</code> and <code>NumberSmallGroups</code> to access the data
of the library directly.
<p>
For all other cubefree orders <var>n</var> one can try to use
<font face="Gill Sans,Helvetica,Arial">Cubefree</font> to construct or count the corresponding groups. Note, that the
success of these computations depends basically on the complexity and number
theory of the
prime-power factorization of <var>n</var>. For each prime <var>p</var> with <var>p<sup>2</sup>midn</var> one
might have to construct subgroups of GL<var>(2,p)</var> and subdirect products
involving these subgroups. One can use the info class <code>InfoCF</code> to get some
information during the computation.
In order to construct subdirect products, we need a permutation representation of these
matrix groups. To rewrite them at once, we compute a
permutation representation of GL<var>(2,p)</var> and apply this isomorphism to the
constructed subgroups. Unfortunately, this is quite time and memory consuming
for bigger primes.
<p>
In other words, <font face="Gill Sans,Helvetica,Arial">Cubefree</font> can note handle <var>unreasonable</var>
cubefree orders. To get a rough idea of the complexity of the computation of
groups of order <var>n</var> and to get a trivial lower bound for the number of
groups, one can use <code>CubefreeOrderInfo(n)</code>.
<p>
At the end of this section we consider the quotient <var>q(n)</var> of <code>NumberSmallGroups(n)</code>
and <code>CubefreeOrderInfo(n)</code> for cubefree <var>1leqnleq
50000</var>. Although for most of these integers we have a small quotient, note
that <var>q(n)</var> seems to be unbounded in general. There are 41597 cubefree integers between <var>1</var> and <var>50000</var> and <var>26414</var>
of these integers fulfill <var>q(n)=1</var>. Moreover, 13065 of these integers fulfill
<var>1< q(n)< 5</var> and the remaining 2118 integers have <var>5leqq(n)leq
54</var>; e.g. <var>n=2<sup>2</sup>.3.5.7<sup>2</sup>.13</var> has <var>q(n)=1221/23</var>.
<p>
<p>
<h2><a name="SECT004">2.4 An example session</a></h2>
<p><p>
In this section we outline some examples of applications of
the methods described above. We
included runtimes for all examples, but omitted the output
in some cases, since it would be too long to be printed.
The runtimes have been obtained on an Intel(R) Pentium(R) 4 CPU 3.00GHz PC running under Linux.
<p>
<pre>
gap> n:=5^2*7*13^2*67^2*97*107;
1377938614325
gap> CubefreeOrderInfo(n,false);
12
gap> Length(ConstructAllCFGroups(n));time;
12
53111
</pre>
<pre>
gap> n:=19^2*23^2*29*37*73^2*107^2;
12501895704027377
gap> CubefreeOrderInfo(n,false);
24
gap> NumberCFGroups(n);time;
24
190536
gap> Length(ConstructAllCFGroups(n));time;
24
948319
</pre>
<pre>
gap> n:=5^2*13*23^2*43^2*191;
60716861075
gap> CubefreeOrderInfo(n,false);
16
gap> Length(ConstructAllCFGroups(n)); time;
16
29146
</pre>
<p>
Now we compute some more data.
<p>
<pre>
gap> n:=2*2*3*11*17*67;
150348
gap> CubefreeOrderInfo(n,false);
20
gap> NumberCFGroups(n);time;
145
12073
gap> Length(ConstructAllCFGroups(n)); time;
145
20757
gap> NumberCFSolvableGroups(n);time;
144
11925
gap> Length(ConstructAllCFSolvableGroups(n)); time;
144
18893
gap> Length(ConstructAllCFFrattiniFreeGroups(n)); time;
109
14421
gap> Length(ConstructAllCFNilpotentGroups(n));time;
2
12
gap> Length(ConstructAllCFSimpleGroups(n));time;
1
8
</pre>
<p>
We consider another example with some info class output.
<p>
<pre>
gap> SetInfoLevel(InfoCF,1);
gap> ConstructAllCFGroups(4620);;time;
#I Construct all groups of order 4620.
#I Compute solvable Frattini-free groups of order 2310.
#I Compute solvable Frattini-free groups of order 4620.
#I Construct 138 Frattini extensions.
#I Compute solvable Frattini-free groups of order 77.
#I Construct 1 Frattini extensions.
#I Compute solvable Frattini-free groups of order 7.
#I Construct 1 Frattini extensions.
15501
</pre>
<p>
<pre>
gap> n:=101^2*97*37^2*29^2;
1139236591513
gap> CubefreeOrderInfo(n,false);
8
gap> NumberCFGroups(n);time;
8
36
gap> SetInfoLevel(InfoCF,1);
gap> ConstructAllCFGroups(n);time;
#I Construct all groups of order 1139236591513.
#I Compute solvable Frattini-free groups of order 10512181.
#I Compute solvable Frattini-free groups of order 304853249.
#I Compute solvable Frattini-free groups of order 388950697.
#I Compute solvable Frattini-free groups of order 1061730281.
#I Compute solvable Frattini-free groups of order 11279570213.
#I Compute solvable Frattini-free groups of order 30790178149.
#I Compute solvable Frattini-free groups of order 39284020397.
#I Compute solvable Frattini-free groups of order 1139236591513.
#I Construct 8 Frattini extensions.
[ <pc group of size 1139236591513 with 7 generators>,
<pc group of size 1139236591513 with 7 generators>,
<pc group of size 1139236591513 with 7 generators>,
<pc group of size 1139236591513 with 7 generators>,
<pc group of size 1139236591513 with 7 generators>,
<pc group of size 1139236591513 with 7 generators>,
<pc group of size 1139236591513 with 7 generators>,
<pc group of size 1139236591513 with 7 generators> ]
1848
</pre>
<p>
The last example considers the cubefree order less than 50000 for which the
number of groups with this order is maximal: there are 3093 groups of order 44100.
<p>
<pre>
gap> n:=2*2*3*3*5*5*7*7;
44100
gap> CubefreeOrderInfo(n,false);
100
gap> NumberCFSolvableGroups(n,false);time;
3087
572639
gap> Length(ConstructAllCFSolvableGroups(n)); time;
3087
843085
gap> NumberCFGroups(n,false);time;
3093
719245
gap> Length(ConstructAllCFGroups(n)); time;
3093
1016763
gap> Length(ConstructAllCFFrattiniFreeGroups(n)); time;
1305
504451
gap> Length(ConstructAllCFNilpotentGroups(n));time;
16
180
</pre>
<p>
<p>
<h2><a name="SECT005">2.5 Accuracy check</a></h2>
<p><p>
We have compared the results of <code>ConstructAllCFGroups</code> with the library of
cubefree groups of <font face="Gill Sans,Helvetica,Arial">SmallGroups</font>. Further, we compared the
solvable groups constructed by <code>IrreducibleSubgroupsOfGL</code> with the library of
<font face="Gill Sans,Helvetica,Arial">IrredSol</font>. We have also done random isomorphism tests to verify that the
list of groups we computed is not redundant.
<p>
One can call the following test files. The first one constructs some groups of order at most 2000 and compares the results with the
<font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library:
<p>
<code>RereadPackage("cubefree","tst/testQuick.g");</code>
<p>
The command
<p>
<code>RereadPackage("cubefree","tst/testBig.g");</code>
<p>
constructs the solvable groups of a random cubefree (but not squarefree) order at most <var>2<sup>28</sup>-1</var> and does a random isomorphism test. Depending on the chosen number, the computation might not terminate due to memory problems.
<p>
The following constructs the groups of three random cubefree orders less than 50000 compares the result with the
<font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library. Depending on the chosen orders, this may take a while:
<p>
<code>RereadPackage("cubefree","tst/testSG.g");</code>
<p>
The test file <var>testSGlong.g</var> constructs all cubefree groups of order at most
50000 compares the results with the
<font face="Gill Sans,Helvetica,Arial">SmallGroups</font> library. There will be a positive progress report every 50th
order so that you can abort the test whenever you want.
<p>
<code>RereadPackage("cubefree","tst/testSGlong.g");</code>
<p>
Three of these four test files use the function <code>CubefreeTestOrder</code>, see Section 2.1.
<p>
The last test file compares some results of <code>IrreducibleSubgroupsOfGL</code> with the
database of <font face="Gill Sans,Helvetica,Arial">IrredSol</font>. This may take a while:
<p>
<code>RereadPackage("cubefree","tst/testMat.g");</code>
<p>
<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>cubefree manual<br>October 2007
</address></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
896
