Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.

DOI10.2140/pjm.2006.223.113zbMath1149.20028arXivmath/0303386MaRDI QIDQ868743

Ilya Kapovich, Vladimir Shpilrain, Paul E. Schupp

Publication date: 26 February 2007

Published in: Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0303386

zbMATH Keywords

one-relator groups; Whitehead algorithm; generic-case complexity

Mathematics Subject Classification ID

68W40: Analysis of algorithms

20F05: Generators, relations, and presentations of groups

20E36: Automorphisms of infinite groups

03D15: Complexity of computation (including implicit computational complexity)

57M05: Fundamental group, presentations, free differential calculus

20E05: Free nonabelian groups

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

20P05: Probabilistic methods in group theory

Related Items

The primitivity index function for a free group, and untangling closed curves on hyperbolic surfaces.With the appendix by Khalid Bou–Rabee, Statistical properties of subgroups of free groups, Non-∀-homogeneity in free groups, Subnormal subgroups in free groups, their growth and cogrowth, Root extraction in one-relator groups and slenderness, GENERICITY OF FILLING ELEMENTS, ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS, Primitivity index bounds in free groups, and the second Chebyshev function, Average-case complexity of the Whitehead problem for free groups, Counting and boundary limit theorems for representations of Gromov‐hyperbolic groups, Conformal dimension and random groups., Random groups arising as graph products., Random equations in nilpotent groups., Almost all one-relator groups with at least three generators are residually finite., On mathematical contributions of Paul E. Schupp, Sublinear time algorithms in the theory of groups and semigroups., Exponentially generic subsets of groups, Immersed cycles and the JSJ decomposition, Randomness and complexity in matrix groups, Some metric properties of automorphisms of groups., A tighter bound for the number of words of minimum length in an automorphic orbit., The subadditive ergodic theorem and generic stretching factors for free group automorphisms., Følner functions and the generic word problem for finitely generated amenable groups, On the asymptotics of visible elements and homogeneous equations in surface groups., Random subgroups, automorphisms, splittings, Primitivity rank for random elements in free groups, Partial word and equality problems and Banach densities, Every group is the outer automorphism group of an HNN-extension of a fixed triangle group, Primitive and almost primitive elements of Schreier varieties, A hybrid search algorithm for the Whitehead minimization problem., Counting words of minimum length in an automorphic orbit., Random equations in free groups, Virtual geometricity is rare, Search and witness problems in group theory, Asymptotic invariants, complexity of groups and related problems, ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM, On an algorithm to decide whether a free group is a free factor of another