Conjugacy search problem and the Andrews-Curtis conjecture

Dmitry Panteleev, Alexander Ushakov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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).

Original languageEnglish
JournalGroups, Complexity, Cryptology
DOIs
StateAccepted/In press - 2019

Keywords

  • Akbulut-Kurby presentations
  • Andrews-Curtis conjecture
  • computations
  • conjugacy search problem
  • trivial group

Fingerprint

Dive into the research topics of 'Conjugacy search problem and the Andrews-Curtis conjecture'. Together they form a unique fingerprint.

Cite this