Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publishers TeX code     *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you retrieve the article in DVI,       *
%_ * PostScript, or PDF format.                                             *
%_ **************************************************************************
% Author Package file for use with AMS-LaTeX 1.2
\controldates{9-FEB-2001,9-FEB-2001,9-FEB-2001,9-FEB-2001}
 
\documentclass{era-l}

\issueinfo{7}{01}{}{2001}
\dateposted{February 12, 2001}
\pagespan{1}{4}
\PII{S 1079-6762(01)00087-7}
%\newcommand{\copyrightyear}{2001}
\copyrightinfo{2001}{American Mathematical Society}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

\newcommand{\GAP}{{\sf GAP}}
\newcommand{\MAGMA}{{\sc Magma}}                                                         
\newcommand{\smallgroups}{{\sc Small Groups}}                                            

\begin{document}

\title{The groups of order at most 2000}

\author{Hans Ulrich Besche}
\address{Lehrstuhl D f\"ur Mathematik,
RWTH Aachen, Templergraben 64, 52062 Aachen, Germany}
\email{hbesche@math.rwth-aachen.de}

\author{Bettina Eick}
\address{ Fachbereich Mathematik,  
Universit\"at Kassel, Heinrich-Plett-Str.\ 40,
34132 Kassel, Germany}
\email{eick@mathematik.uni-kassel.de}

\author{E. A. O'Brien}
\address{ Department of Mathematics,
University of Auckland, 
Private Bag 92019,
Auckland, New Zealand} 
\email{obrien@math.auckland.ac.nz}

\thanks{This work was supported in part by the Marsden Fund of
New Zealand via grant \#9144/3368248.
Eick and O'Brien acknowledge the financial support of the
Alexander von Humboldt Foundation, Bonn.} 

%    General info
\subjclass[2000]{Primary 20D10, 20D15; Secondary 20-04}

\date{May 31, 2000}
\commby{Efim Zelmanov}

\keywords{Enumeration, determination, small groups, algorithms}

\begin{abstract}
We announce the construction up to isomorphism of the 
$49\,910\,529\,484$ groups of order at most 2000.        
\end{abstract} 
\maketitle

\section{Introduction}
The problem of explicitly constructing all of the groups of a given 
finite order has a long and somewhat chequered history; its 
study was initiated by Cayley in 1854 when he determined the 
groups of order at most $6$. 
The aim is to determine a complete and irredundant 
list of the groups of a given order: 
a representative of each isomorphism type is present and no two groups in 
the list are isomorphic.  It is  
usually comparatively easy to generate a complete list; 
the difficulty lies in the reduction
to distinct isomorphism types. 

In practice, the difficulty experienced in constructing the
groups of a given order is determined by the number 
of groups of that order.
Higman \cite{Higman60} and Sims \cite{Sims65} provide asymptotic 
estimates which 
show that the number of groups of order $p^m$, for a prime $p$,
is $p^{2 m^3 /27 + O(m^{8/3})}$. Further, the number of
groups of order $n$ depends on the prime factorisation of $n$: 
if $e(n)$ is the largest exponent of a prime dividing $n$, then 
Pyber \cite{Pyber93} shows that the number of groups of order $n$ is at 
most $n^{(2/27 + o(1)) e(n)^2}$. 

Historically, the approaches to the group construction problem 
involved a large number of hand computations and case distinctions, 
and focused on specific properties of the groups. They were consequently
{\it ad hoc} in nature, and many contained errors.
As one indicator of progress, the groups 
of order at most 100 were determined by 1980. 
We cite here three modern, significant, and accurate contributions: 
Hall and  Senior \cite{HallSenior64}, Neub\"user \cite{Neubuser67}, 
and Laue \cite{Laue82}.

Here we announce a significant step forward
in providing a solution to the group construction 
problem in its original form.
We have developed {\it practical} algorithms 
to construct or enumerate the groups of a given order.  
While these methods rely on group-theoretic properties, 
they are inherently general-purpose. 
Motivated by the millennium, we used our implementations
of these algorithms 
to enumerate the $49\,487\,365\,422$ groups of order $2^{10}$,
and to determine explicitly the $423\,164\,062$ remaining groups of
order at most 2000. 

For a survey of the group construction problem, including 
an extensive bibliography, an outline of the algorithms used, 
and details of the construction of the groups of order at most 2000, 
we refer the reader to \cite{BescheEickOBrien00}.

\section{The algorithms}

Our construction and enumeration algorithms 
were employed to determine the groups of order at 
most 2000.  Here, we provide only the briefest summary of each 
algorithm and references to the primary sources for each.
Naturally, the techniques used depend on inherent group-theoretic
structural properties, such as nilpotence and solubility.
 
\begin{enumerate}
\item
 The $p$-group generation algorithm of Newman \cite{Newman77}
and O'Brien \cite{OBrien90}: given as input a $p$-group $P$, this
algorithm constructs a complete and irredundant list of 
certain central extensions ({\it immediate descendants}) of $P$.
\item
 The $p$-group enumeration methods of Eick and O'Brien \cite{EickOBrien99}:
given as input a $p$-group $P$, these algorithms {\it count} the number 
of nonisomorphic immediate descendants of $P$.
\item
 The coprime split extension algorithm of Besche and Eick 
\cite{BescheEick99a,BescheEick00}:
given as input positive integers $r$, $s$ 
where $\gcd (|r|, |s|) = 1$, this algorithm
determines up to isomorphism all groups of order
$r \cdot s$ with normal Hall $r$-subgroup.
\item
 The Frattini extension method of Besche and Eick 
\cite{BescheEick99a,BescheEick00}: this algorithm
first determines candidates $F$ for Frattini
factors of the soluble groups of order $n$;
for each $F$, it 
now constructs Frattini extensions $G$ of order $n$ 
(that is, $G$ has normal subgroup $N$, where 
$N \leq \Phi(G)$ and $G/N \cong F$),
and solves the isomorphism problem for the resulting list.
\item
Algorithms to construct insoluble groups 
\cite{BescheEickOBrien00,BescheEick99a}:
given a perfect group $N$ as input and a positive integer $n$, this 
algorithm constructs those finite groups $G$ of order $n$ 
having soluble residuum $M \cong N$ (that is, $M$ is the smallest
normal subgroup of $G$ with $G/M$ soluble).
\end{enumerate}
A central requirement is that these algorithms are practical.
Implementations of the algorithms are publicly available in
the computer algebra systems \GAP\ \cite{GAP} 
or \MAGMA\ \cite{Magma}.

\section{The results}
In Table \ref{difficult}, we list the ten most challenging 
orders, and the number of groups of each order. 
We enumerated the groups of order $2^{10}$; 
all other groups were explicitly constructed.

While it is practically possible to construct explicitly the 
groups of order $2^{10}$, we did not do so; of course,
subsets of these groups can be constructed on demand 
using our implementations.  
We observe that $48\,803\,495\,722$ of 
these groups have exponent-$2$ class precisely 2.

\begin{table}[htb]
\caption{The ten most difficult orders}\label{difficult}
\begin{center}
\begin{tabular}{|r||r|} 
\hline Order & Number  \\
\hline $2^{10}$ & $49\,487\,365\,422$ \\
\hline $2^9 \cdot 3$ & $408\,641\,062$ \\
\hline $2^9$ & $10\,494\,213$ \\
\hline $2^8 \cdot 5$ & $1\,116\,461$ \\
\hline $2^8 \cdot 3$ & $1\,090\,235$ \\
\hline $2^8 \cdot 7$ & $1\,083\,553$ \\
\hline $2^7 \cdot 3 \cdot 5$ & $241\,004$ \\
\hline $2^7 \cdot 3^2$ & $157\,877$  \\
\hline $2^8$ & $56\,092$ \\
\hline $2^6 \cdot 3^3$ & $47\,937$  \\
\hline
\end{tabular}
\end{center}
\end{table}

The resulting catalogue of groups is published in 
electronic form; in particular, it is distributed with 
\GAP\ and \MAGMA\ as the \smallgroups\ library.  
We also provide, as one component of the library, 
an algorithm to identify a given group in the library;
see \cite{BescheEickOBrien00} for details.
The library data was generated electronically, 
without intermediate hand computations.  

\section{Future directions}
Our algorithms and their implementations are publicly available 
and can be used to extend existing determinations.                             
However, we believe that the new challenge is to 
construct ``generic" groups---for example,
those whose orders factorise in a certain way.  As contributions
in this direction, the \smallgroups\
library includes those groups whose orders have at most 3 prime
divisors; Besche and Eick \cite{BescheEick00} present an algorithm 
to determine the groups of order $p^n \cdot q$ for fixed prime power
$p^n$ and arbitrary prime $q \neq p$.  

\begin{thebibliography}{99}

\bibitem{BescheEickOBrien00}
Hans Ulrich Besche, Bettina Eick, and E. A. O'Brien, 
``A millennium project: constructing small groups'',
{\rm Preprint}.
\bibitem{BescheEick99a}
        Hans Ulrich Besche and Bettina Eick, 
        ``Construction of finite groups'', 
        \textit{ J.\ Symbolic Comput.} \textbf{ 27} (1999), 387--404.
\MR{2000c:20001}
\bibitem{BescheEick00}
        Hans Ulrich Besche and Bettina Eick, 
        ``The groups of order $q^n \cdot p$'', 
        \textit{ Comm.\ Algebra} 2001.
\bibitem{EickOBrien99}
        Bettina Eick and E. A. O'Brien, 
        ``Enumerating $p$-groups'', 
        \textit{ J. Austral. Math. Soc. Ser. A} \textbf{ 67} (1999), 191--205.
\MR{2000h:20033}
\bibitem{GAP}
        The {\sf GAP} Group, 
        \textit{ {{\sf GAP}---Groups, Algorithms, and Programming, Version
$4.2$}}, Lehrstuhl D f{\accent127 u}r Mathematik, RWTH Aachen and School of
        Mathematical and Computational Sciences, University of St Andrews, 2000.
\bibitem{HallSenior64}
Marshall {Hall, Jr.,} and James K. Senior, \textit{ The Groups of order
  $2^n$\ $(n \leq 6)$,}
\newblock Macmillan, New York, 1964.
\MR{29:5889}
\bibitem{Higman60}
Graham Higman,  ``Enumerating $p$-groups. {I}: {I}nequalities'', \textit{
  Proc.\ London Math.\ Soc.\ $(3)$} \textbf{ 10} (1960), 24--30.
\MR{22:4779}
\bibitem {Laue82}
Reinhard Laue, \textit{ Zur Konstruktion und Klassifikation endlicher
  aufl\"{o}sbarer Gruppen}, Bayreuth. Math. Schr. no. 9 (1982).
\MR{84e:20018}
\bibitem{Newman77}
         M. F. Newman,  
         ``Determination of groups of prime-power order'',  
         \textit{ Group Theory}, Lecture Notes in Math. \textbf{573} (Canberra, 
     1975), pp. 73--84, Springer-Verlag, Berlin, Heidelberg, New York, 1977.
\MR{56:12115}
\bibitem{Magma}
         Wieb Bosma, John Cannon, and Catherine Playoust,  
         ``The {\sc Magma} Algebra System I: The User Language'', 
         \textit{ J.\ Symbolic Comput.} \textbf{ 24} (1997), 235--265.
\MR{98f:68006}
\bibitem{Neubuser67}
Joachim Neub{\"u}ser,  ``Die {U}ntergruppenverb{\"a}nde der {G}ruppen
  der {O}rdnungen $\leq 100$ mit {A}usnahme der {O}rdnungen 64 und 96'',
\newblock Habilitationsschrift, Kiel, 1967.
\bibitem{OBrien90}
E. A. O'Brien,  
``The \textit{ p}-group generation algorithm'', 
\textit{ J. Symbolic Comput.} \textbf{ 9} (1990), 677--698.
\MR{91j:20050}
\bibitem{Pyber93}
L\'aszl\'o Pyber,  ``Asymptotic results for permutation groups'', Amer.
  Math. Soc. DIMACS Series, \textbf{11} (DIMACS, 1991), 1993, pp. 197--219.
\MR{94g:20003}
\bibitem{Sims65}
Charles C. Sims,  ``Enumerating $p$-groups'', \textit{ Proc. London Math.
  Soc. $(3)$} \textbf{ 15} (1965), 151--166.
\MR{30:164}
\end{thebibliography}

\end{document}