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 (open archive)
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)
(open access)
ABSTRACT: Euclid's algorithm for computing the
greatest common divisor of 2 numbers is considered to be the
oldest proper algorithm known. This algorithm can be
amplified naturally in various ways. The GCD problem for more
than two numbers is interesting in its own right. Thus, we
can use Euclid's algorithm recursively to compute the GCD of
more than two numbers. Also, we can do a constructive
computation, the so-called extended GCD, which expresses the
GCD as a linear combination of the input numbers.
Extended GCD computation is of particular interest in number
theory and in computational linear algebra, in both of which
it takes a basic role in fundamental algorithms. It dates
back to at least Euler. Efforts to find good algorithms for
extended GCD computation show that this is genuinely
difficult. There are a number of problems for which efficient
solutions are not readily available.
TITLE: Irreducible
cyclic presentations of the trivial group
AUTHORS: George Havas and Edmund F. Robertson
CITATION: Experimental
Mathematics 12 (2003) 487-490 (open access)
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 (open archive)
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 (open access)
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 (open
access)
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
(open access)
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.
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 (open archive)
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 (open access)
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
ABSTRACT: Even after 25 years the article An
elementary introduction to coset table methods in
computational group theory by Joachim Neubueser remains
the first source to which all three of us refer those who
want to find out about the use of coset tables for studying
groups. Our view is confirmed by the 14 Reference Citations
from 1998 to 2005 which MathSciNet reveals for this article.
Here we loosely follow the structure of the original article
and provide some updates on the area (oriented towards our
own interests).
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)
67-81.
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 85 (2008)
323-332 (open archive)
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.
TITLE: On
counterexamples to the Hughes conjecture
AUTHORS: George Havas and Michael Vaughan-Lee
CITATION: Journal
of Algebra 322 (2009) 791-801 (open archive)
ABSTRACT: In 1957 D.R. Hughes published the following
problem in group theory. Let G be a group and p a prime.
Define Hp(G) to be the subgroup of G generated by
all the elements of G which do not have order p. Is the
following conjecture true: either Hp(G) = 1,
Hp(G)=G, or [G:Hp(G)]=p? After various
classes of groups were shown to satisfy the conjecture, G.E.
Wall and E.I. Khukhro described counterexamples for p=5, 7
and 11. Finite groups which do not satisfy the conjecture,
anti-Hughes groups, have interesting properties. We give
explicit constructions of a number of anti-Hughes groups via
power-commutator presentations, including relatively small
examples with orders 546 and 766. It is
expected that the conjecture is false for all primes larger
than 3. We show that it is false for p = 13, 17 and 19.
TITLE: On
Coxeter's families of group presentations
AUTHORS: George Havas and Derek F. Holt
CITATION: Journal of
Algebra 324 (2010) 1076-1082 (open archive)
ABSTRACT: In 1939 Coxeter published three infinite
families of group presentations. He studied their properties,
in particular determining when groups defined by members of
the families are infinite and the structure of finite ones.
Eight presentations remained for which the finiteness
question was unsettled. We show that two of these eight
presentations define finite groups (for which we give
comprehensive proofs and provide detailed structural
information) and that two of the presentations define
infinite groups. Our results rely on substantial amounts of
computer calculations, in particular on coset enumeration to
prove finiteness and on computation of automatic structures
using Knuth-Bendix rewriting to prove infiniteness.
TITLE: On
one-relator quotients of the modular group
AUTHORS: Marston Conder, George Havas and M.F.
Newman
CITATION: Proc.
Groups St Andrews 2009 in Bath, London Mathematical
Society Lecture Note Series 387, Cambridge University
Press (2011) 183-197
ABSTRACT: We investigate the modular group as a
finitely presented group. It has a large collection of
interesting quotients. In 1987 Conder substantially
identified the one-relator quotients of the modular group
which are defined using representatives of the 300
inequivalent extra relators with length up to 24. We study
all such quotients where the extra relator has length up to
36. Up to equivalence, there are 8296 more presentations. We
confirm Conder's results and we determine the order of all
except five of the quotients. Once we find the order of a
finite quotient it is easy to determine detailed structural
information about the group. The presentations of the groups
whose order we have not been able to determine provide
interesting challenge problems.
Our study of one-relator quotients of the modular group is
`in the small', that is, with a short extra relator. We
briefly compare and contrast our results with generic
results.
TITLE: All simple
groups with order from 1 million to 5 million are
efficient
AUTHORS: Colin M. Campbell, George Havas, Colin Ramsay
and Edmund F. Robertson
CITATION: International
Journal of Group Theory 3 (2014) 17-30.
ABSTRACT: There is much interest in finding short
presentations for the finite simple groups. Indeed it has
been suggested that all these groups are efficient in a
technical sense. In previous papers we produced nice
efficient presentations for all except one of the simple
groups with order less than one million. Here we show that
all simple groups with order between 1 million and 5 million
are efficient by giving efficient presentations for all of
them. Apart from some linear groups these results are all
new. We also show that some covering groups and some larger
simple groups are efficient. We make substantial use of
systems for computational group theory and, in particular, of
computer implementations of coset enumeration to find and
verify our presentations.
TITLE: On
presentations for unitary groups
AUTHORS: Marston Conder, George Havas, M.F. Newman and
Colin Ramsay
CITATION: Journal of
Algebra 545 (2020) 100-110
ABSTRACT: Concise presentations for groups are useful
for both theoretical and computational purposes. We give
short 2-generator presentations for the 3-dimensional unitary
groups U3(q) and SU3(q) for q up to 11.
