{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,25]],"date-time":"2024-03-25T16:47:37Z","timestamp":1711385257075},"reference-count":68,"publisher":"Walter de Gruyter GmbH","issue":"1","funder":[{"name":"National Science Foundation","award":["DMS-1318716"],"award-info":[{"award-number":["DMS-1318716"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,5,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We develop new computational methods for studying potential counterexamples to the Andrews\u2013Curtis conjecture, in particular, Akbulut\u2013Kurby examples<jats:inline-formula id=\"j_gcc-2019-2005_ineq_9999_w2aab3b7e1024b1b6b1aab1c14b1b1Aa\"><jats:alternatives><jats:tex-math>{\\operatorname{AK}(n)}<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We devise a number of algorithms in an attempt to disprove the most interesting counterexample<jats:inline-formula id=\"j_gcc-2019-2005_ineq_9998_w2aab3b7e1024b1b6b1aab1c14b1b3Aa\"><jats:alternatives><jats:tex-math>{\\operatorname{AK}(3)}<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. 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\u2013Curtis 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\u2013Kurby presentations. The improved technique allows us to enumerate balanced presentations AC-equivalent to<jats:inline-formula id=\"j_gcc-2019-2005_ineq_9997_w2aab3b7e1024b1b6b1aab1c14b1b5Aa\"><jats:alternatives><jats:tex-math>{\\operatorname{AK}(3)}<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>with relations of lengths up to 20 (previous record was 17).<\/jats:p>","DOI":"10.1515\/gcc-2019-2005","type":"journal-article","created":{"date-parts":[[2019,4,7]],"date-time":"2019-04-07T02:48:35Z","timestamp":1554605315000},"page":"43-60","source":"Crossref","is-referenced-by-count":1,"title":["Conjugacy search problem and the Andrews\u2013Curtis conjecture"],"prefix":"10.1515","volume":"11","author":[{"given":"Dmitry","family":"Panteleev","sequence":"first","affiliation":[{"name":"Department of Mathematics, Stevens Institute of Technology, Hoboken, NJ, USA"}]},{"given":"Alexander","family":"Ushakov","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Stevens Institute of Technology, Hoboken, NJ, USA"}]}],"member":"374","reference":[{"key":"ref101","first-page":"195","article-title":"Dehn functions and l1l_{1}-norms of finite presentations","year":"1992","journal-title":"Algorithms and Classification in Combinatorial Group Theory"},{"key":"ref91","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1112\/blms\/25.6.513","article-title":"Balanced presentations of the trivial group","volume":"25","year":"1993","journal-title":"Bull. Lond. Math. Soc."},{"key":"ref331","first-page":"341","article-title":"On the dunce hat","volume":"2","year":"1964","journal-title":"Topology"},{"key":"ref431","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1112\/blms\/25.6.513","article-title":"Balanced presentations of the trivial group","volume":"25","year":"1993","journal-title":"Bull. Lond. Math. Soc."},{"key":"ref281","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/BF01350654","article-title":"On Dehn\u2019s algorithm and the conjugacy problem","volume":"178","year":"1968","journal-title":"Math. Ann."},{"key":"ref591","first-page":"491","article-title":"Extended Nielsen transformations and the trivial group","volume":"35","year":"1984","journal-title":"Mat. Zametki"},{"key":"ref611","first-page":"1","article-title":"On the algorithmic unsolvability of the word problem in group theory","volume":"44","year":"1955","journal-title":"Proc. Steklov Inst."},{"key":"ref301","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.1142\/S0218196706003396","article-title":"A fast algorithm for Stallings\u2019 folding process","volume":"16","year":"2006","journal-title":"Internat. J. Algebra Comput."},{"key":"ref321","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1090\/S0002-9947-1975-0380813-5","article-title":"Group presentations and formal deformations","volume":"208","year":"1975","journal-title":"Trans. Amer. Math. Soc."},{"key":"ref121","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0040-9383(83)90017-4","article-title":"The Zeeman conjecture for standard spines is equivalent to the Poincar\u00e9 conjecture","volume":"22","year":"1983","journal-title":"Topology"},{"key":"ref151","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s00222-005-0497-1","article-title":"On balanced presentations of the trivial group","volume":"165","year":"2006","journal-title":"Invent. Math."},{"key":"ref231","first-page":"121","article-title":"Random van Kampen diagrams and algorithmic problems in groups","volume":"3","year":"2011","journal-title":"Groups Complex. Cryptol."},{"key":"ref11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1080\/00029890.1966.11970717","article-title":"Extended Nielsen operations in free groups","volume":"73","year":"1966","journal-title":"Amer. Math. Monthly"},{"key":"ref451","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/A:1019682203828","article-title":"Filling length in finitely presentable groups","volume":"92","year":"2002","journal-title":"Geom. Dedicata"},{"key":"ref71","volume-title":"The Geometry of the Word Problem for Finitely Generated Groups","year":"2007"},{"key":"ref21","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1017\/S1446788700007783","article-title":"A non-cyclic one-relator group all of whose finite quotients are cyclic","volume":"10","year":"1969","journal-title":"J. Austral. Math. Soc."},{"key":"ref41","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1073\/pnas.44.10.1061","article-title":"The word problem","volume":"44","year":"1958","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref161","doi-asserted-by":"crossref","first-page":"1561","DOI":"10.1090\/S0002-9939-05-08450-9","article-title":"On Rourke\u2019s extension of group presentations and a cyclic version of the Andrews\u2013Curtis conjecture","volume":"134","year":"2006","journal-title":"Proc. Amer. Math. Soc."},{"key":"ref481","journal-title":"Website"},{"key":"ref441","first-page":"195","article-title":"Dehn functions and l1l_{1}-norms of finite presentations","year":"1992","journal-title":"Algorithms and Classification in Combinatorial Group Theory"},{"key":"ref391","first-page":"15","article-title":"The finitary Andrews\u2013Curtis conjecture","year":"2005","journal-title":"Infinite Groups: Geometric, Combinatorial and Dynamical Aspects"},{"key":"ref191","volume-title":"The Kourovka Notebook. Unsolved Problems in Group Theory","year":"2014"},{"key":"ref311","year":"2005","journal-title":"Fundamental search problems in groups"},{"key":"ref221","volume-title":"Non-commutative Cryptography and Complexity of Group-theoretic Problems","year":"2011"},{"key":"ref601","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1515\/jgth-2015-0031","article-title":"Andrews\u2013Curtis and Nielsen equivalence relations on some infinite groups","volume":"19","year":"2016","journal-title":"J. Group Theory"},{"key":"ref631","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","article-title":"Worst-case analysis of set union algorithms","volume":"31","year":"1984","journal-title":"J. Assoc. Comput. Mach."},{"key":"ref111","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/A:1019682203828","article-title":"Filling length in finitely presentable groups","volume":"92","year":"2002","journal-title":"Geom. Dedicata"},{"key":"ref501","doi-asserted-by":"crossref","first-page":"1561","DOI":"10.1090\/S0002-9939-05-08450-9","article-title":"On Rourke\u2019s extension of group presentations and a cyclic version of the Andrews\u2013Curtis conjecture","volume":"134","year":"2006","journal-title":"Proc. Amer. Math. Soc."},{"key":"ref181","volume-title":"Combinatorial Group Theory","year":"1977"},{"key":"ref671","first-page":"341","article-title":"On the dunce hat","volume":"2","year":"1964","journal-title":"Topology"},{"key":"ref531","volume-title":"The Kourovka Notebook. Unsolved Problems in Group Theory","year":"2014"},{"key":"ref371","first-page":"1","article-title":"Open problems in combinatorial group theory. 2nd ed.","year":"2002","journal-title":"Combinatorial and Geometric Group Theory"},{"key":"ref521","volume-title":"Combinatorial Group Theory","year":"1977"},{"key":"ref401","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1080\/10586458.2006.10128962","article-title":"Fast searching for Andrews\u2013Curtis trivializations","volume":"15","year":"2006","journal-title":"Exp. Math."},{"key":"ref51","first-page":"15","article-title":"The finitary Andrews\u2013Curtis conjecture","year":"2005","journal-title":"Infinite Groups: Geometric, Combinatorial and Dynamical Aspects"},{"key":"ref351","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1080\/00029890.1966.11970717","article-title":"Extended Nielsen operations in free groups","volume":"73","year":"1966","journal-title":"Amer. Math. Monthly"},{"key":"ref491","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s00222-005-0497-1","article-title":"On balanced presentations of the trivial group","volume":"165","year":"2006","journal-title":"Invent. Math."},{"key":"ref651","year":"2005","journal-title":"Fundamental search problems in groups"},{"key":"ref171","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1142\/S1793525317500182","article-title":"Balanced finite presentations of the trivial group","volume":"9","year":"2017","journal-title":"J. Topol. Anal."},{"key":"ref241","first-page":"183","article-title":"On the Andrews\u2013Curtis equivalence","year":"2002","journal-title":"Combinatorial and Geometric Group Theory"},{"key":"ref541","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1142\/S0218196799000370","article-title":"Genetic algorithms and the Andrews\u2013Curtis conjecture","volume":"9","year":"1999","journal-title":"Internat. J. Algebra Comput."},{"key":"ref621","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/BF01350654","article-title":"On Dehn\u2019s algorithm and the conjugacy problem","volume":"178","year":"1968","journal-title":"Math. Ann."},{"key":"ref641","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.1142\/S0218196706003396","article-title":"A fast algorithm for Stallings\u2019 folding process","volume":"16","year":"2006","journal-title":"Internat. J. Algebra Comput."},{"key":"ref461","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0040-9383(83)90017-4","article-title":"The Zeeman conjecture for standard spines is equivalent to the Poincar\u00e9 conjecture","volume":"22","year":"1983","journal-title":"Topology"},{"key":"ref381","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1073\/pnas.44.10.1061","article-title":"The word problem","volume":"44","year":"1958","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref551","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1142\/S0218196715500058","article-title":"Search problems in groups and branching processes","volume":"25","year":"2015","journal-title":"Internat. J. Algebra Comput."},{"key":"ref31","first-page":"1","article-title":"Open problems in combinatorial group theory. 2nd ed.","year":"2002","journal-title":"Combinatorial and Geometric Group Theory"},{"key":"ref131","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1142\/S0218196703001365","article-title":"Breadth-first search and the Andrews\u2013Curtis conjecture","volume":"13","year":"2003","journal-title":"Internat. J. Algebra Comput."},{"key":"ref411","volume-title":"The Geometry of the Word Problem for Finitely Generated Groups","year":"2007"},{"key":"ref511","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1142\/S1793525317500182","article-title":"Balanced finite presentations of the trivial group","volume":"9","year":"2017","journal-title":"J. Topol. Anal."},{"key":"ref341","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1090\/S0002-9939-1965-0173241-8","article-title":"Free groups and handlebodies","volume":"16","year":"1965","journal-title":"Proc. Amer. Math. Soc."},{"key":"ref561","volume-title":"Non-commutative Cryptography and Complexity of Group-theoretic Problems","year":"2011"},{"key":"ref571","first-page":"121","article-title":"Random van Kampen diagrams and algorithmic problems in groups","volume":"3","year":"2011","journal-title":"Groups Complex. Cryptol."},{"key":"ref581","first-page":"183","article-title":"On the Andrews\u2013Curtis equivalence","year":"2002","journal-title":"Combinatorial and Geometric Group Theory"},{"key":"ref271","first-page":"1","article-title":"On the algorithmic unsolvability of the word problem in group theory","volume":"44","year":"1955","journal-title":"Proc. Steklov Inst."},{"key":"ref361","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1017\/S1446788700007783","article-title":"A non-cyclic one-relator group all of whose finite quotients are cyclic","volume":"10","year":"1969","journal-title":"J. Austral. Math. Soc."},{"key":"ref421","article-title":"The complexity of balanced presentations and the Andrews\u2013Curtis conjecture","year":"2015","journal-title":"Preprint"},{"key":"ref81","article-title":"The complexity of balanced presentations and the Andrews\u2013Curtis conjecture","year":"2015","journal-title":"Preprint"},{"key":"ref251","first-page":"491","article-title":"Extended Nielsen transformations and the trivial group","volume":"35","year":"1984","journal-title":"Mat. Zametki"},{"key":"ref661","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1090\/S0002-9947-1975-0380813-5","article-title":"Group presentations and formal deformations","volume":"208","year":"1975","journal-title":"Trans. Amer. Math. Soc."},{"key":"ref61","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1080\/10586458.2006.10128962","article-title":"Fast searching for Andrews\u2013Curtis trivializations","volume":"15","year":"2006","journal-title":"Exp. Math."},{"key":"ref201","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1142\/S0218196799000370","article-title":"Genetic algorithms and the Andrews\u2013Curtis conjecture","volume":"9","year":"1999","journal-title":"Internat. J. Algebra Comput."},{"key":"ref211","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1142\/S0218196715500058","article-title":"Search problems in groups and branching processes","volume":"25","year":"2015","journal-title":"Internat. J. Algebra Comput."},{"key":"ref291","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","article-title":"Worst-case analysis of set union algorithms","volume":"31","year":"1984","journal-title":"J. Assoc. Comput. Mach."},{"key":"ref471","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1142\/S0218196703001365","article-title":"Breadth-first search and the Andrews\u2013Curtis conjecture","volume":"13","year":"2003","journal-title":"Internat. J. Algebra Comput."},{"key":"ref261","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1515\/jgth-2015-0031","article-title":"Andrews\u2013Curtis and Nielsen equivalence relations on some infinite groups","volume":"19","year":"2016","journal-title":"J. Group Theory"},{"key":"ref141","journal-title":"Website"},{"key":"ref01","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1090\/S0002-9939-1965-0173241-8","article-title":"Free groups and handlebodies","volume":"16","year":"1965","journal-title":"Proc. Amer. Math. Soc."}],"container-title":["Groups Complexity Cryptology"],"original-title":[],"link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/gcc\/11\/1\/article-p43.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/downloadpdf\/journals\/gcc\/11\/1\/article-p43.xml","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T11:39:48Z","timestamp":1663241988000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/gcc-2019-2005\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,1]]},"references-count":68,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.1515\/gcc-2019-2005","relation":{},"ISSN":["1869-6104","1867-1144"],"issn-type":[{"value":"1869-6104","type":"electronic"},{"value":"1867-1144","type":"print"}],"subject":[],"published":{"date-parts":[[2019,5,1]]}}}