The conjugacy problem for groups of alternating prime tame links is polynomial-time

Johnsgard, Karin

doi:10.1090/S0002-9947-97-01617-6

The conjugacy problem for groups of alternating prime tame links is polynomial-time
HTML articles powered by AMS MathViewer

by Karin Johnsgard PDF

Trans. Amer. Math. Soc. 349 (1997), 857-901 Request permission

Abstract:

An alternating projection of a prime link can to used to produce a group presentation (of the link group under free product with the infinite cyclic group) with some useful peculiarities, including small cancellation conditions. In this presentation, conjugacy diagrams are shown to have the form of a tiling of squares in the Euclidean plane in one of a limited number of shapes. An argument based on the shape of the link projection is used to show that the tiling requires no more square tiles than a linear function of word length (with constant multiple based on the number of link crossings). It follows that the computation time for testing conjugacy of two group elements (previously known to be no worse than exponential) is bounded by a cubic polynomial. This bounds complexity in the original link group.

References

Kenneth I. Appel, On the conjugacy problem for knot groups, Math. Z. 138 (1974), 273–294. MR 357622, DOI 10.1007/BF01237125
K. I. Appel and P. E. Schupp, The conjugacy problem for the group of any tame alternating knot is solvable, Proc. Amer. Math. Soc. 33 (1972), 329–336. MR 294460, DOI 10.1090/S0002-9939-1972-0294460-X
K. I. Appel and P. E. Schupp, Artin groups and infinite Coxeter groups, Invent. Math. 72 (1983), no. 2, 201–220. MR 700768, DOI 10.1007/BF01389320
Max Dehn, Papers on group theory and topology, Springer-Verlag, New York, 1987. Translated from the German and with introductions and an appendix by John Stillwell; With an appendix by Otto Schreier. MR 881797, DOI 10.1007/978-1-4612-4668-8
S. M. Gersten and H. B. Short, Small cancellation theory and automatic groups, Invent. Math. 102 (1990), no. 2, 305–334. MR 1074477, DOI 10.1007/BF01233430
S. M. Gersten and H. Short, Small cancellation theory and automatic groups. II, Invent. Math. 105 (1991), no. 3, 641–662. MR 1117155, DOI 10.1007/BF01232283
K. Johnsgard, The Structure of the Cayley Complex and a Cubic-time Algorithm for Solving the Conjugacy Problem for Groups of Prime Alternating Knots, Univ. Illinois—Urbana-Champaign: Ph. D. thesis, 1993.
—, Geometric Tilings for Equal Geodesic Words in $C^{\prime \prime }(p)-T(q)$ Group Presentations, 1993, Preprint.
I. Kapovitch, Small Cancellation Groups and Translation Numbers, 1993, Preprint.
Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. MR 0577064
W. Menasco, Closed incompressible surfaces in alternating knot and link complements, Topology 23 (1984), no. 1, 37–44. MR 721450, DOI 10.1016/0040-9383(84)90023-5
Saunders MacLane and O. F. G. Schilling, Infinite number fields with Noether ideal theories, Amer. J. Math. 61 (1939), 771–782. MR 19, DOI 10.2307/2371335
Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
Paul E. Schupp, On Dehn’s algorithm and the conjugacy problem, Math. Ann. 178 (1968), 119–130. MR 237620, DOI 10.1007/BF01350654
Z. Sela, The conjugacy problem for knot groups, Topology 32 (1993), no. 2, 363–369. MR 1217075, DOI 10.1016/0040-9383(93)90026-R
Friedhelm Waldhausen, The word problem in fundamental groups of sufficiently large irreducible $3$-manifolds, Ann. of Math. (2) 88 (1968), 272–280. MR 240822, DOI 10.2307/1970574
C. M. Weinbaum, The word and conjugacy problems for the knot group of any tame, prime, alternating knot, Proc. Amer. Math. Soc. 30 (1971), 22–26. MR 279169, DOI 10.1090/S0002-9939-1971-0279169-X