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.
