What fraction of finitely presented groups have unsolvable word problem?

Question

What fraction of finitely presented groups have unsolvable word problem?

I suspect the answer is "almost all" for some suitable notion, but I can't find any results on the topic. Any references you have would be amazing.

Thanks!

Answer 1

There is a well-developed theory of "random groups". As you specifically ask for a reference, a basic reference is Ollivier's A January 2005 invitation to random groups, which you can find on his webpage here. At the moment, the theory explained in Ollivier's book is the best you are going to get. On the one hand, it doesn't answer your question because, as YCor mentioned in the comments to the question, it is really the theory of random presentations. On the other hand, hyperbolic groups have soluble word problem and all the "random groups" defined in the various known models (as of 2005) are all hyperbolic (see p27, line 1 of Ollivier's book for the appropriate quote!). Hence, in a certain sense the "random groups" of Ollivier's book do answer your question.

---

I now want to give you a flavour of what we mean by a "random group". I'll describe the "few relator" model, which is also called the "$0$-density" model. This is the most basic model, which is why I am typing it up now. It has its advantages and disadvantages. This post is not meant as an endorsement for this model :-)

What follows uses the $C'(\lambda)$ small cancellation conditions, $\lambda\leq1/6$. For more information either Google "small cancellation theory" or see Lyndon and Schupp's book Combinatorial Group Theory, Springer (1977). Basically, this is an easily-checkable condition on the relators which implies that the underlying group has decidable word problem (in a really pretty way), and is in fact hyperbolic.

Fix two numbers $m$ and $n$. We are going to see what properties a group defined by a generic $m$-generator, $n$-relator presentation $\langle x_1, \ldots, x_m\mid r_1, \ldots, r_n\rangle$ possesses by looking at relators of bounded length $t$ and then increasing the ball which contains them. The following lemma is due to Arzhantseva and Ol'shanskii* (I believe 0.2.A of Gromov's seminal Hyperbolic groups essay is analogous, although I do not have this to hand)):

Lemma. Among all finite sequences $\{r_1, \ldots, r_n\}$ of freely and cyclically reduced words whose lengths are at most $t$, the fraction of sequences satisfying the small cancellation $C'(\lambda)$ condition is $\geq1-a(2m-1)^{-\lambda t/5}$ for $t\geq a$, where $a>0$ and depends on $m$, $n$ and $\lambda$.

Group presentations $\langle x_1, \ldots, x_m\mid r_1, \ldots, r_n\rangle$ are associated in an obvious way with sequences $\{r_1, \ldots, r_n\}$ of freely and cyclically reduced words. Therefore, fixing some $\lambda\leq1/6$, by letting $t\rightarrow\infty$ in the above lemma we see that "almost all" $m$-generator, $n$-relator presentations satisfy $C'(\lambda)$. By unioning these models, it follows that "almost all" finite presentations satisfy $C'(\lambda)$. As we chose $\lambda\leq1/6$, these groups are hyperbolic and have decidable word problem (in fact the solution is super nice).

We can then address the question in your title. Getting a fraction is stronger than just saying "almost all".

Theorem. The fraction of finite presentations defining groups with unsolvable word problem is $0$.

Proof. This is because the fraction satisfying $C'(1/6)$ is $1$, because $\lim_{t\rightarrow\infty}1-a(2m-1)^{-\lambda t/5}=1$.

*The citation here is not short: G. N. Arzhantseva, A. Yu. Ol’shanski˘ı, The class of groups all of whose subgroups with lesser number of generators are free is generic, Mat. Zametki 59 (1996), no. 4, 489–496; English translation in Math. Notes 59 (1996), no. 3–4, 350–355.