Generic properties of Whitehead’s algorithm and isomorphism rigidity of random one-relator groups
Generic properties of Whitehead’s algorithm and isomorphism rigidity of random one-relator groups
复制标题
怀特海德算法的泛性与随机一相关群的同构刚性
DOI：
10.2140/pjm.2006.223.113
复制
发表时间：
2003
影响因子：
0.6
通讯作者：
V. Shpilrain
中科院分区：
文献类型：
--
作者：
Ilya Kapovich;P. Schupp;V. Shpilrain
我们证明了Whitehead的算法求解自同构问题在一个固定的自由群Fk具有强线性时间的一般情况下的复杂性。这是通过显示算法的“硬”部分在线性时间内终止于指数通用输入对集合来完成的。然后，我们将这些结果应用到一个关系群。我们得到了随机单关系群的Mostow型同构刚性结果：如果两个这样的群是同构的，则它们在给定生成集上的Cayley图是等距的。虽然以前没有非平凡的例子，我们证明了单关系子群是一般完备群，即它们有平凡中心和平凡外自同构群。我们还证明了Aut（Fk）中Fk的类元的稳定子是由内自同构生成的循环群，并且Aut（Fk）-轨道在其增长熵意义下是一致小的.进一步证明了定义关系子长度为n的k-生成单关系子群的同构类型数Ik（n）满足c1 n（2k-1）n ≤ c2 n（2k-1）n，其中c1，c2是依赖于k而不依赖于n的正常数.因此，I k（n）的增长方式基本上与长度为n的循环字的数量相同。
We prove that Whitehead's algorithm for solving the automorphism problem in a fixed free group F k has strongly linear time generic-case complexity. This is done by showing that the "hard" part of the algorithm terminates in linear time on an exponentially generic set of input pairs. We then apply these results to one-relator groups. We obtain a Mostow-type isomorphism rigidity result for random one-relator groups: If two such groups are isomorphic then their Cayley graphs on the given generating sets are isometric. Although no nontrivial examples were previously known, we prove that one-relator groups are generically complete groups, that is, they have trivial center and trivial outer automorphism group. We also prove that the stabilizers of generic elements of F k in Aut(F k ) are cyclic groups generated by inner automorphisms and that Aut(F k )-orbits are uniformly small in the sense of their growth entropy. We further prove that the number I k (n) of isomorphism types of k-generator one-relator groups with defining relators of length n satisfies c 1 n(2k-1) n ≤c 2 n(2k-1) n , where c 1 , c 2 are positive constants depending on k but not on n. Thus I k (n) grows in essentially the same manner as the number of cyclic words of length n.