Breadth-first search and the Andrews-Curtis conjecture. (English) Zbl 1059.20029
Summary: Andrews and Curtis conjectured in 1965 that every balanced presentation of the trivial group can be transformed into a standard presentation by a finite sequence of elementary transformations. Recent computational work by A. D. Miasnikov and A. G. Myasnikov [Ohio State Univ. Math. Res. Inst. Publ. 8, 257-263 (2001; Zbl 0992.20025)] on this problem has been based on genetic algorithms. We show that a computational attack based on a breadth-first search of the tree of equivalent presentations is also viable, and seems to outperform that based on genetic algorithms. It allows us to extract shorter proofs (in some cases, provably shortest) and to consider the length thirteen case for two generators. We prove that, up to equivalence, there is a unique minimum potential counterexample.
MSC:
20F05 | Generators, relations, and presentations of groups |
20E05 | Free nonabelian groups |
20-04 | Software, source code, etc. for problems pertaining to group theory |
57M05 | Fundamental group, presentations, free differential calculus |
68W30 | Symbolic computation and algebraic computation |
Keywords:
Andrews-Curtis conjecture; trivial group; balanced presentations; computer generated proofs; genetic algorithmsCitations:
Zbl 0992.20025References:
[1] | DOI: 10.1016/0040-9383(85)90010-2 · Zbl 0584.57009 · doi:10.1016/0040-9383(85)90010-2 |
[2] | DOI: 10.1090/S0002-9939-1965-0173241-8 · doi:10.1090/S0002-9939-1965-0173241-8 |
[3] | DOI: 10.1112/blms/25.6.513 · Zbl 0796.20022 · doi:10.1112/blms/25.6.513 |
[4] | DOI: 10.1017/S0004972700036388 · Zbl 0938.20026 · doi:10.1017/S0004972700036388 |
[5] | Grattan-Guinness I., Notices Amer. Math. Soc. 48 pp 167– |
[6] | Havas G., Andrews–Curtis and Todd–Coxeter proof words, in: Group St. Andrews 2001 in Oxford · Zbl 1047.20024 |
[7] | DOI: 10.1142/S0218196799000370 · Zbl 0949.20022 · doi:10.1142/S0218196799000370 |
[8] | A. D. Miasnikov and A. G. Myasnikov, Groups and Computation III, Balanced presentations of the trivial group on two generators and the Andrews–Curtis conjecture 8, eds. W. M. Kantor and A. Seress (Ohio State Math. Res. Inst. Publ. 8, de Gruyter, Berlin, 2001) pp. 257–263. · Zbl 0992.20025 |
[9] | DOI: 10.1090/conm/250/03848 · doi:10.1090/conm/250/03848 |
[10] | DOI: 10.1090/S0002-9947-1975-0380813-5 · doi:10.1090/S0002-9947-1975-0380813-5 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.