The Andrews-Curtis Conjecture
This page contains some historical material on work by George Havas and Colin Ramsay associated with the Andrews-Curtis conjecture. (Most materials date back to about 2002/2003.) In particular it contains information on software written by Colin called ACME.
The Andrews-Curtis conjecture posits that every balanced presentation of the trivial group can be transformed into the standard presentation by a finite sequence of elementary transformations. We have developed software to enumerate sequences of Andrews-Curtis moves (the ACME package), and used this to investigate the minimal potential counterexamples - which turns out to be unique.
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.
software: ACME source code (ANSI C) .... [29K .tar.gz file]
draft manual: ACME 1.000: an Andrews-Curtis move enumerator .... [118K .pdf file]
examples/utilites: stuff for the IJAC paper .... [20K .tar.gz file]
