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: GAP package ACE; Advanced Coset Enumerator
AUTHORS: Greg Gamble, Alexander Hulpke, George Havas, Colin Ramsay
CITATION:
Web page for the most recent ACE share package for GAP.
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 S. 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 31 (2003) 5191-5197
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 304,
Cambridge University Press (2003) 232-237
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
13 (2003) 61-68
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: On the Complexity of the Extended Euclidean Algorithm
(extended abstract)
AUTHOR: George Havas
CITATION: Electronic Notes in Theoretical Computer Science 78
(2003)
Full Text (PDF 81Kb)
Full Text (PostScript 121Kb)
TITLE: Irreducible cyclic presentations of the trivial group
AUTHORS: George Havas and Edmund F. Robertson
CITATION: Experimental Mathematics 12 (2003) 487-490.
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 304,
Cambridge University Press (2003) 238-243
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 32 (2004) 649-656.
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.
TITLE: On decomposition of sub-linearised polynomials
AUTHORS: Robert S. Coulter, George Havas and Marie Henderson
CITATION: Journal of the Australian Mathematical Society
76 (2004) 317-328
ABSTRACT: Previously it has been shown that there is a direct
relationship between linearised and sub-linearised polynomials over a
finite field. By exploiting this relationship we give a formula for
the number of indecomposable sub-linearised polynomials of given degree.
Also we note that these two classes of polynomials satisfy a theorem of
Ritt concerning complete decompositions into indecomposables.
TITLE: 4-Engel groups are locally nilpotent
AUTHORS: George Havas and M. R. Vaughan-Lee
CITATION: International Journal of Algebra and Computation
15 (2005) 649-682
ABSTRACT:
Questions about nilpotency of groups satisfying Engel conditions have
been considered since 1936, when Zorn proved that finite Engel groups
are nilpotent. We prove that 4-Engel groups are locally nilpotent.
Our proof makes substantial use of both hand and machine calculations.
TITLE: Experimenting with infinite groups, I
AUTHORS: Gilbert Baumslag, Sean Cleary and George Havas
CITATION: Experimental Mathematics 13 (2004) 495-502
ABSTRACT:
A group is termed parafree if it is residually nilpotent and has the
same nilpotent quotients as a given free group. Since free groups are
residually nilpotent, they are parafree. Nonfree parafree groups abound
and they all have many properties in common with free groups. Finitely
presented parafree groups have solvable word problems, but little is known
about the conjugacy and isomorphism problems. The conjugacy problem plays
an important part in determining whether an automorphism is inner, which
we term the inner automorphism problem. We will attack these and other
problems about parafree groups experimentally, in a series of papers,
of which this is the first and which is concerned with the isomorphism
problem. The approach that we take here is to distinguish some parafree
groups by computing the number of epimorphisms onto selected finite
groups. It turns out, rather unexpectedly, that an understanding of the
quotients of certain groups leads to some new results about equations
in free and relatively free groups. We touch on this only lightly here
but will discuss this in more depth in a future paper.
TITLE:
Nice efficient presentations for all small simple groups and their covers
AUTHORS:
Colin M. Campbell, George Havas, Colin Ramsay and Edmund F. Robertson
CITATION: LMS Journal of Computation and Mathematics 7 (2004)
266-283
ABSTRACT:
Prior to this paper all small simple groups were known to be efficient
but the status of four of their covering groups was unknown. We produce
nice efficient presentations for all of these groups, resolving the
previously unknown cases. We give presentations that are better than
available before in terms of length and in terms of computational
properties. In many cases our presentations have minimal possible length.
Our results are based on major amounts of computation. We make substantial
use of systems for computational group theory and, in particular, of
computer implementations of coset enumeration. To assist in reducing the
number of relators we provide theorems which enable the amalgamation of
power relations in certain presentations. We conclude with a selection
of unsolved problems about efficient presentations for simple groups
and their covers.
TITLE: Efficient presentations for the Mathieu simple group
M22 and its cover
AUTHORS: Marston Conder, George Havas and Colin Ramsay
CITATION: Finite Geometries, Groups, and Computation
(Proceedings of the conference Finite Geometries, Groups, and Computation,
September 4-9, 2004, Pingree Park, Colorado, USA), Walter de Gruyter
(2006) 33-42
ABSTRACT:
Questions about the efficiency of finite simple groups and their covering
groups have been the subject of much research. We provide new efficient
presentations for the Mathieu simple group M22 and its cover,
including the shortest known efficient presentation for M22
and a somewhat longer presentation which is very suitable for computation.
TITLE: Certain Roman and flock generalized quadrangles have
nonisomorphic elation groups
AUTHORS:
George Havas, C.R. Leedham-Green, E.A. O'Brien and Michael C. Slattery
CITATION: Advances in Geometry 6 (2006) 389-395
ABSTRACT:
We prove that the elation groups of a certain infinite family of
Roman generalized quadrangles are not isomorphic to those of
associated flock generalized quadrangles.
TITLE: Computing with elation groups
AUTHORS:
George Havas, C.R. Leedham-Green, E.A. O'Brien and Michael C. Slattery
CITATION: Finite Geometries, Groups, and Computation
(Proceedings of the conference Finite Geometries, Groups, and Computation,
September 4-9, 2004, Pingree Park, Colorado, USA), Walter de Gruyter
(2006) 95-102
ABSTRACT:
We have proved that the elation groups of a certain infinite
family of Roman generalized quadrangles are not isomorphic to those
of associated flock generalized quadrangles. The proof is theoretical,
but is based upon detailed computations. Here we elaborate on the
explicit computer calculations which inspired the proof.
TITLE: The Fa,b,c conjecture, I
AUTHORS: George Havas and Edmund F. Robertson
CITATION:
Irish Mathematical Society Bulletin 56 (2005), 75-80.
ABSTRACT:
In 1977 a five-part conjecture was made about a family of groups related
to trivalent graphs and one part of the conjecture was proved. The
conjecture completely determines all finite members of the family.
Here we prove another part of the conjecture and foreshadow a paper
which completes the proof of the other three parts.
Reprint (PDF 96Kb) by permission of the
Irish Mathematical Society.
TITLE: Computing with 4-Engel groups
AUTHORS: George Havas and M. R. Vaughan-Lee
CITATION: Groups St Andrews 2005, London Mathematical Society
Lecture Note Series 340, Cambridge University Press (2007),
475-485
ABSTRACT:
We have proved that 4-Engel groups are locally nilpotent. The proof
is based upon detailed computations by both hand and machine. Here we
elaborate on explicit computer calculations which provided some of
the motivation behind the proof. In particular we give details on the
hardest coset enumerations now required to show in a direct proof
that 4-Engel p-groups are locally finite for 5 <= p <= 31.
We provide a theoretical result which enables us to do requisite coset
enumerations much better and we also give a new, tight bound on the class
of 4-Engel 5-groups.
TITLE: On proofs in finitely presented groups
AUTHORS: George Havas and Colin Ramsay
CITATION: Groups St Andrews 2005, London Mathematical Society
Lecture Note Series 340, Cambridge University Press (2007),
457-474
ABSTRACT:
Given a finite presentation of a group G, proving properties of G
can be difficult. Indeed, many questions about finitely presented groups
are unsolvable in general. Algorithms exist for answering some questions
while for other questions algorithms exist for verifying the truth of
positive answers. An important tool in this regard is the Todd-Coxeter
coset enumeration procedure. It is possible to extract formal proofs
from the internal working of coset enumerations. We give examples of how
this works, and show how the proofs produced can be mechanically verified
and how they can be converted to alternative forms. We discuss these
automatically produced proofs in terms of their size and the insights
they offer. We compare them to hand proofs and to the simplest possible
proofs. We point out that this technique has been used to help solve
a longstanding conjecture about an infinite class of finitely presented
groups.
TITLE: The Fa,b,c conjecture is true, II
AUTHORS: George Havas, Edmund F. Robertson and Dale C. Sutherland
CITATION: Journal of Algebra 300 (2006), 57-72
ABSTRACT:
In 1977 a five-part conjecture was made about a family of groups related
to trivalent graphs and subsequently two parts of the conjecture were
proved. The conjecture completely determines all finite members of the
family. Here we complete the proof of the conjecture by giving proofs
for the remaining three parts.
TITLE: Experiences with the Knuth-Bendix procedure
AUTHOR: George Havas
CITATION: Oberwolfach Report 30/2006,
European Mathematical Society Publishing House (2007), 1834-1837.
TITLE:
On the efficiency of the simple groups with order less than a million
and their covers
AUTHORS:
Colin M. Campbell, George Havas, Colin Ramsay and Edmund F. Robertson
CITATION: Experimental Mathematics 16 (2007), 347-358.
ABSTRACT:
There is much interest in finding short presentations for the finite
simple groups. In a previous paper we produced nice efficient
presentations for all small simple groups and for their covering
groups. Here we extend those results from simple group order less than
100,000 up to order one million, but we leave one simple group and one
covering group for which the efficiency question remains unresolved.
We give presentations that are better than available before, in terms of
length and in terms of computational properties, in the process answering
two previously unresolved problems about the efficiency of covering groups
of simple groups. Our results are based on major amounts of computation.
We make substantial use of systems for computational group theory
and, in particular, of computer implementations of coset enumeration.
TITLE:
Addendum to an elementary introduction to coset table
methods in computational group theory
AUTHORS:
Colin M. Campbell, George Havas and Edmund F. Robertson
CITATION: Groups St Andrews 1981 (revised edition),
London Mathematical Society Lecture Note Series 71, Cambridge
University Press (2007), 361-364
TITLE:
Defining set spectra for designs can have arbitrarily large gaps
AUTHORS: George Havas, Julie L. Lawrence, Colin Ramsay,
Anne Penfold Street and Emine Sule Yazici
CITATION: Utilitas Mathematica 75 (2008), 65-79.
ABSTRACT:
Previously, the spectra of only a limited number of designs were known
and all of these were continuous. The question whether the spectrum is
continuous for all designs was raised in 2003. We describe a new algorithm
which finds all minimal defining sets of designs. Using this algorithm we
investigated the spectra for a variety of small designs, and found several
examples of non-continuous spectra. We also derive some theoretical
results which enable us to construct an infinite family of designs with
arbitrarily large sequences of consecutive holes in their spectra.
TITLE:
Behind and beyond a theorem on groups related to trivalent graphs
AUTHORS: George Havas, Edmund F. Robertson and Dale C. Sutherland
CITATION: Journal of the Australian Mathematical Society
(to appear)
ABSTRACT:
In 2006 we completed the proof of a five-part conjecture which was made
in 1977 about a family of groups related to trivalent graphs. This family
covers all 2-generator, 2-relator groups where one relator specifies that
a generator is an involution and the other relator has three syllables.
Our proof relies upon detailed but general computations in the groups
under question. The proof is theoretical, but based upon explicit proofs
produced by machine for individual cases. Here we explain how we derived
the general proofs from specific cases. The conjecture essentially
addressed only the finite groups in the family. Here we extend the results
to infinite groups, effectively determining when members of this family
of finitely presented groups are simply isomorphic to a specific quotient.