These pages are not updated anymore. They reflect the state of . 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}