Selected Publications from 2000

TITLE: Computing in groups with exponent six
AUTHORS: George Havas, M.F. Newman, Alice C. Niemeyer and Charles C. Sims
CITATION: Computational and Geometric Aspects of Modern Algebra, London Mathematical Society Lecture Note Series 275, Cambridge University Press (2000) 87-100
ABSTRACT: We have investigated the nature of sixth power relations required to provide proofs of finiteness for some two-generator groups with exponent six. We have solved various questions about such groups using substantial computations. In this paper we elaborate on some of the calculations and address related problems for some three-generator groups with exponent six.

TITLE: Proving a group trivial made easy: a case study in coset enumeration
AUTHORS: George Havas and Colin Ramsay
CITATION: Bulletin of the Australian Mathematical Society 62 (2000) 105-118
ABSTRACT: Coset enumeration, based on the methods described by Todd and Coxeter, is one of the basic tools for investigating finitely presented groups. The process is not well understood, and various pathological presentations of, for example, the trivial group have been suggested as challenge problems. Here we consider one such family of presentations proposed by B.H. Neumann. We show that the problems are much easier than they first appear, albeit at the expense of considerable preliminary `experimentation' This demonstrates how far the range of applicability of coset enumeration has improved.

TITLE: Parallel coset enumeration using threads
AUTHORS: George Havas and Colin Ramsay
CITATION: Computer Mathematics, Proceedings of the Fourth Asian Symposium (ASCM 2000), Lecture Notes Series on Computing 8, World Scientific (2000) 29-38
ABSTRACT: Coset enumeration is one of the basic tools for investigating finitely presented groups. Many enumerations require significant resources, in terms of CPU time or memory space. We develop a fully functional parallel coset enumeration procedure and we discuss some of the issues involved in such parallelisation using the POSIX threads library. Our results can equally well be applied to any master-slave parallel activity exhibiting a medium level of granularity.

TITLE: Experiments in coset enumeration
AUTHORS: George Havas and Colin Ramsay
CITATION: Groups and Computation III, Ohio State University Mathematical Research Institute Publications 8, de Gruyter (2001) 183-192
ABSTRACT: Coset enumeration, based on the methods described by Todd and Coxeter, is one of the basic tools for investigating finitely presented groups. These methods do not, in general, constitute an algorithm. Each problem has to be addressed individually, and determining whether or not an acceptable solution can be found using the given resources requires an empirical approach (i.e., experimentation). We discuss some of the ideas involved, and illustrate with a few examples.

TITLE: A presentation for the Thompson sporadic simple group
AUTHORS: George Havas, Leonard H. Soicher and Robert A. Wilson
CITATION: Groups and Computation III, Ohio State University Mathematical Research Institute Publications 8, de Gruyter (2001) 193-200
ABSTRACT: We determine a presentation for the Thompson sporadic simple group, Th. The proof of correctness of this presentation uses a coset enumeration of 143,127,000 cosets. In the process of our work, we determine presentations for various subgroups of Th. We also provide, via the internet, matrices generating Th and satisfying our presentation.

TITLE: Giesbrecht's algorithm, the HFE cryptosystem and Ore's ps-polynomials
AUTHORS: Robert Coulter, George Havas and Marie Henderson
CITATION: Computer Mathematics, Proceedings of the Fifth Asian Symposium (ASCM 2001), Lecture Notes Series on Computing 8, World Scientific (2001) 36-45
ABSTRACT: We report on a recent implementation of Giesbrecht's algorithm for factoring polynomials in a skew-polynomial ring. We also discuss the equivalence between factoring polynomials in a skew-polynomial ring and decomposing ps-polynomials over a finite field, and how Giesbrecht's algorithm is outlined in some detail by Ore in the 1930's. We end with some observations on the security of the Hidden Field Equation (HFE) cryptosystem, where p-polynomials play a central role.

TITLE: Certain cyclically presented groups are infinite
AUTHORS: George Havas, Derek F. Holt and M.F. Newman
CITATION: Communications in Algebra 29 (2001) 5175-5178
ABSTRACT: We prove that the groups in two infinite families considered by Johnson, Kim and O'Brien are almost all infinite.

TITLE: Efficient simple groups
AUTHORS: Colin M. Campbell, George Havas, Alexander Hulpke and Edmund F. Robertson
CITATION: Communications in Algebra 30 (2002) 4613-4619
ABSTRACT: We prove that the simple group L3(5) which has order 372000 is efficient by providing an efficient presentation for it. This leaves one simple group with order less than one million, S4(4) which has order 979200, whose efficiency or otherwise remains to be determined.

TITLE: Andrews-Curtis and Todd-Coxeter proof words
AUTHORS: George Havas and Colin Ramsay
CITATION: Groups St Andrews 2001 in Oxford, London Mathematical Society Lecture Note Series, Cambridge University Press (to appear)
ABSTRACT: Andrews and Curtis have conjectured that every balanced presentation of the trivial group can be transformed into a standard presentation by a finite sequence of elementary transformations. It can be difficult to determine whether or not the conjecture holds for a particular presentation. We show that the utility PEACE, which produces proofs based on Todd-Coxeter coset enumeration, can produce Andrews-Curtis proofs.

TITLE: Breadth-first search and the Andrews-Curtis conjecture
AUTHORS: George Havas and Colin Ramsay
CITATION: International Journal of Algebra and Computation (to appear)
ABSTRACT: Andrews and Curtis have conjectured that every balanced presentation of the trivial group can be transformed into the standard presentation by a finite sequence of elementary transformations. Previous computational work on this problem has been based on genetic algorithms. We show that a computational attack based on a breadth-first search of the tree of equivalent presentations is also viable, and seems to outperform that based on genetic algorithms. It allows us to extract shorter proofs (in some cases, provably shortest) and to consider the length thirteen case for two generators. We prove that, up to equivalence, there is a unique minimum potential counterexample.

TITLE: Irreducible cyclic presentations of the trivial group
AUTHORS: George Havas and Edmund F. Robertson
CITATION: Experimental Mathematics (to appear)
ABSTRACT: We produce families of irreducible cyclic presentations of the trivial group. These families comprehensively answer questions about such presentations asked by Dunwoody and by Edjvet, Hammond and Thomas. Our theorems are purely theoretical, but their derivation is based on practical computations. We explain how we chose the computations and how we deduced the theorems.

TITLE: Short balanced presentations of perfect groups
AUTHORS: George Havas and Colin Ramsay
CITATION: Groups St Andrews 2001 in Oxford, London Mathematical Society Lecture Note Series, Cambridge University Press (to appear)
ABSTRACT: We report some initial results from an investigation of short balanced presentations of perfect groups. We determine the minimal length 2-generator balanced presentations for SL2(5) and SL2(7) and we show that ^M22, the full covering group of the sporadic simple group M22, has deficiency zero. We give presentations for SL2(7) and ^M22 that are both new and of minimal length. We also determine the shortest 2-generator presentations for an infinite perfect group. This is done in the context of a complete classification of short 2-generator balanced presentations of perfect groups in terms of canonic presentations.

TITLE: On the efficiency of some finite groups
AUTHORS: George Havas, M.F. Newman and E.A. O'Brien
CITATION: Communications in Algebra (to appear)
ABSTRACT: We describe a new technique for finding efficient presentations for finite groups. We use it to answer three previously unresolved questions about the efficiency of group and semigroup presentations.

Last updated: 4 November 2002