zbMATH — the first resource for mathematics

Delzant’s \(T\)-invariant, Kolmogorov complexity and one-relator groups. (English) Zbl 1151.20026
For any finite presentation \(P=\langle X\mid R\rangle\) define the ‘length’ \(l(P)\) as \[ l(P)=\sum_{r\in R}\max\{|r|-2,0\}. \] If \(G\) is a finitely presentable group, the ‘\(T\)-invariant’ \(T(G)\) of \(G\) is defined as \[ T(G)=\min\{l(P)\mid P\text{ is a finite presentation of }G\}. \] It is shown that for a “random” one-relator group the \(T\)-invariant is comparable in magnitude with the length of the defining relator. The proof relies on the authors previous results regarding isomorphism rigidity of generic one-relator groups and on the methods of the theory of Kolmogoroff-Chaitin complexity.
As a second result it is shown that the number of isomorphism types of \(k\)-generator one-relator groups with cyclically reduced defining relators of length \(n\) is for large \(n\) asymptotically equal to \[ \frac{(2k-1)^n}{nk!2^{k+1}}. \]

20F05 Generators, relations, and presentations of groups
20F69 Asymptotic properties of groups
20E36 Automorphisms of infinite groups
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI arXiv