Kourovka Notebook Problem 12.56

Definitions and mathematical statement

Let $X$ be a finite set of generators, and let $R$ be a finite set of cyclically reduced words in the alphabet $X\sqcup X^{-1}$. A word is cyclically reduced if it has no adjacent inverse letters and, when nonempty, its first and last letters are not inverses. Write $|r|$ for the number of letters in a relator $r$, counting each generator or inverse generator as one letter. Define the length of the finite presentation $P=\langle X\mid R\rangle$ by \[ \ell(P)=|X|+\sum_{r\in R}|r|. \] For each integer $n\geq 0$, define \[ F(n)=\#\left\{[G]_{\cong}:G\text{ admits a finite presentation }P\text{ with cyclically reduced relators and }\ell(P)\leq n\right\}. \] Here $[G]_{\cong}$ denotes the isomorphism class of $G$; the groups counted need not be finite, and multiple presentations of the same group contribute only one isomorphism class.

The problem, proposed by A. Mann, asks what can be said about the function $F(n)$. This is an open-ended request: the supplied statement does not specify a particular asymptotic estimate or other property to establish.

The source reports that $F$ is not recursive, attributing this assertion to D. Segal: no algorithm computes the exact value $F(n)$ and terminates for every integer $n\geq0$. It also reports that $F$ is at least exponential, attributing this assertion to L. Pyber. Under the usual eventual exponential lower-bound interpretation, this means that there exist $a>1$ and an integer $n_0\geq0$ such that $F(n)\geq a^n$ for every integer $n\geq n_0$. The source supplies no constants or more precise formulation of that lower bound. These assertions are supplied background claims, not independently verified results of this draft.

Short English statement

Count the isomorphism classes of groups that can be presented using at most $n$ generators and relator letters in total, with all relators cyclically reduced. A. Mann asks for information about this counting function. The source attributes noncomputability to D. Segal and an exponential lower bound to L. Pyber, without specifying a sharper target.

Sources

• Local UnsolvedMath registry, permanent ID $700875$, exact source code catalogue entry, title Kourovka Notebook Problem 12.56. The supplied registry labels the problem open; this status is supplied metadata, not an independently verified literature assessment.
• The Kourovka Notebook (Unsolved Problems in Group Theory), original problem 12.56, 12th issue (1992); proposed by A. Mann. The supplied background also identifies the 21st issue edition (2026), arXiv:1401.0300v48. The collection metadata names E. I. Khukhro and V. D. Mazurov as editors.
• The supplied problem statement attributes nonrecursiveness of $F$ to D. Segal and an exponential lower bound to L. Pyber. No separate references for these assertions are supplied.