GENETIC ALGORITHMS AND THE ANDREWS–CURTIS CONJECTURE

DOI10.1142/S0218196799000370MaRDI QIDQ4484940zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 3 December 2000

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0304306

zbMATH Keywords

genetic algorithmsbalanced presentationsNielsen transformationsAndrews-Curtis conjecture

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Free nonabelian groups (20E05) Generators, relations, and presentations of groups (20F05) Fundamental group, presentations, free differential calculus (57M05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

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.

Recommendations

• BREADTH-FIRST SEARCH AND THE ANDREWS–CURTIS CONJECTURE
• Balanced presentations of the trivial group on two generators and the Andrews-Curtis conjecture
• scientific article
• Conjugacy search problem and the Andrews-Curtis conjecture

Cites work

• A potential smooth counterexample in dimension 4 to the Poincaré conjecture, the Schoenflies conjecture, and the Andrews-Curtis conjecture
• Balanced Presentations of the Trivial Group
• Remarks on Groups of Order 1

Cited in

(14)

• Fitness landscapes and the Andrews-Curtis conjecture
• Fast Searching for Andrews–Curtis Trivializations
• Morse theory for group presentations
• A family of Andrews-Curtis trivializations via 4-manifold trisections
• Balanced presentations of the trivial group on two generators and the Andrews-Curtis conjecture
• Balanced finite presentations of the trivial group
• Codes of \(m\)-complexity 1.
• Irreducible Cyclic Presentations of the Trivial Group
• Andrews–Curtis groups and the Andrews–Curtis conjecture
• BREADTH-FIRST SEARCH AND THE ANDREWS–CURTIS CONJECTURE
• On Conjectures of Andrews and Curtis
• scientific article; zbMATH DE number 2144696 (Why is no real title available?)
• THE ANDREWS–CURTIS CONJECTURE AND BLACK BOX GROUPS
• Conjugacy search problem and the Andrews-Curtis conjecture

This page was built for publication: GENETIC ALGORITHMS AND THE ANDREWS–CURTIS CONJECTURE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4484940)