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.