TY - JOUR
T1 - Conjugacy search problem and the Andrews-Curtis conjecture
AU - Panteleev, Dmitry
AU - Ushakov, Alexander
N1 - Publisher Copyright:
© 2019 Walter de Gruyter GmbH, Berlin/Boston 2019.
PY - 2019
Y1 - 2019
N2 - We develop new computational methods for studying potential counterexamples to the Andrews-Curtis conjecture, in particular, Akbulut-Kurby examples AK(n) {\operatorname{AK}(n)}. We devise a number of algorithms in an attempt to disprove the most interesting counterexample AK(3) {\operatorname{AK}(3)}. That includes an efficient implementation of the folding procedure for pseudo-conjugacy graphs, based on the original modification of a classic disjoint-set data structure. To improve metric properties of the search space (the set of balanced presentations of the trivial group), we introduce a new transformation, called an ACM-move, that generalizes the original Andrews-Curtis transformations and discuss details of a practical implementation. To reduce growth of the search space, we introduce a strong equivalence relation on balanced presentations and study the space modulo automorphisms of the underlying free group. We prove that automorphism moves can be applied to Akbulut-Kurby presentations. The improved technique allows us to enumerate balanced presentations AC-equivalent to AK(3) {\operatorname{AK}(3)} with relations of lengths up to 20 (previous record was 17).
AB - We develop new computational methods for studying potential counterexamples to the Andrews-Curtis conjecture, in particular, Akbulut-Kurby examples AK(n) {\operatorname{AK}(n)}. We devise a number of algorithms in an attempt to disprove the most interesting counterexample AK(3) {\operatorname{AK}(3)}. That includes an efficient implementation of the folding procedure for pseudo-conjugacy graphs, based on the original modification of a classic disjoint-set data structure. To improve metric properties of the search space (the set of balanced presentations of the trivial group), we introduce a new transformation, called an ACM-move, that generalizes the original Andrews-Curtis transformations and discuss details of a practical implementation. To reduce growth of the search space, we introduce a strong equivalence relation on balanced presentations and study the space modulo automorphisms of the underlying free group. We prove that automorphism moves can be applied to Akbulut-Kurby presentations. The improved technique allows us to enumerate balanced presentations AC-equivalent to AK(3) {\operatorname{AK}(3)} with relations of lengths up to 20 (previous record was 17).
KW - Akbulut-Kurby presentations
KW - Andrews-Curtis conjecture
KW - computations
KW - conjugacy search problem
KW - trivial group
UR - http://www.scopus.com/inward/record.url?scp=85064414046&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85064414046&partnerID=8YFLogxK
U2 - 10.1515/gcc-2019-2005
DO - 10.1515/gcc-2019-2005
M3 - Article
AN - SCOPUS:85064414046
SN - 1867-1144
JO - Groups, Complexity, Cryptology
JF - Groups, Complexity, Cryptology
ER -