Density of metric small cancellation in finitely presented groups (Q6566688)

Let \(G=\langle X \mid W \rangle\) be a finitely presented group with \(|W|=r\) generators and \(|R|=m\) relators. If the presentation of \(G\) satisfies the metric small cancellation condition \(C'(\lambda)\) (\(\lambda \in ]0,1[\)), then \(G\) has many desirable algebraic and algorithmic properties. For example \textit{M. Greendlinger} [Commun. Pure Appl. Math. 13, 641--677 (1960; Zbl 0156.01303)] showed that if \(G\) satisfies the \(C'(1/6)\) small cancellation condition, then \(G\) has the word problem and the conjugacy problem uniformly solvable in linear time by Dehn's algorithm.\N\NThe authors prove the following results:\N\NTheorem 1.1: There is a function \(p_{\lambda}^{\leq}(r,\ell_{1},\ell_{2}, m)\) given by a closed-form formula such that a presentation chosen uniformly at random from the set of all presentations of the form \(\langle X \mid W \rangle\), where \(|X|=r\), \(|W|=m\) and \(\ell_{1} \leq |w| \leq \ell_{2}\) for each \(w \in W\), is power-free and satisfies the metric small cancellation condition \(C'(\lambda)\) with probability at least \(p_{\lambda}^{\leq}(r,\ell_{1},\ell_{2}, m)\). Moreover, we have\N\[\N1-p_{\lambda}^{\leq}(r,\ell_{1},\ell_{2},m) \leq 8m^{2}r\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)(2r-1)^{-\lambda \ell_{2}-1},\N\]\Nand thus \(\lim_{\ell_{2} \rightarrow \infty} p_{\lambda}^{\leq}(r,\ell_{1},\ell_{2},m)=1\) for each fixed \(r \geq 2\), \(\lambda\) and \(m\).\N\NTheorem 1.2: There is a function \(p_{\lambda}^{\geq}(r,\ell, m)\) given by a closed-form formula such that a presentation chosen uniformly at random from the set of all presentations of the form \(\langle X \mid W \rangle\), where \(|X|=r\), \(|W|=m\) and \(|w|=\ell\) for all \(w \in W\), is power-free and satisfies the metric small cancellation condition \(C'(\lambda)\) with probability at most \(p_{\lambda}^{\geq}(r,\ell, m)\). Moreover, for each \(m \geq 1\) and \(r \geq 2\), we have\N\[\N\ln(1/p_{\lambda}^{\geq}(r,\ell, m)) \geq \frac{1}{8}(m-1)^{2} \ell (2r-1)^{-\lceil \lambda \ell \rceil},\N\]\Nthat is, \(p_{\lambda}^{\geq}(r,\ell, m)\) is not simply the constant function 1. Notice that from Theorem 1.1 we have \(\lim_{\ell \rightarrow \infty} p_{\lambda}^{\geq}(r,\ell, m)=1\) and thus \(\lim_{\ell \rightarrow \infty} \ln (p_{\lambda}^{\geq}(r,\ell, m))=0\).\N\NIn the interesting Appendix A, the authors compare their theoretical results with experimental data. In particular, they provide several heat maps which show how their bounds change when they vary the parameters of the presentation.