Title: Genetic algorithms and the Andrews-Curtis conjecture Author: Alexei D. Miasnikov Categories: GR Group Theory Math Subject Class: 20E05, 20F05, 68T05 (Primary) 57M05,57M20 Journal reference: International Journal of Algebra and Computation, Vol. 9 No. 6, (1999) 671-686 Comments: 19 pages Abstract: The Andrews-Curtis conjecture claims that every balanced presentation of the trivial group can be transformed into the trivial presentation by a finite sequence of "elementary transformations" which are Nielsen transformations together with an arbitrary conjugation of a relator. It is believed that the Andrews-Curtis conjecture is false; however, not so many possible counterexamples are known. It is not a trivial matter to verify whether the conjecture holds for a given balanced presentation or not. The purpose of this paper is to describe some non-deterministic methods, called Genetic Algorithms, designed to test the validity of the Andrews-Curtis conjecture. Using such algorithm we have been able to prove that all known (to us) balanced presentations of the trivial group where the total length of the relators is at most 12 satisfy the conjecture. In particular, the Andrews-Curtis conjecture holds for the presentation <x,y|x y x = y x y, x^2 = y^3> which was one of the well known potential counterexamples. From: Alexei Miasnikov <alex@groups.sci.ccny.cuny.edu> Date: Mon, 21 Apr 2003 21:07:18 GMT (13kb) BibTeX @misc{math.GR/0304306, title = {{Genetic algorithms and the Andrews-Curtis conjecture}}, author = {Alexei D. Miasnikov}, howpublished = {International Journal of Algebra and Computation, Vol. 9 No. 6, (1999) 671-686}, eprint = {arXiv:math.GR/0304306}}

root 2004-05-05