Finite presentations of metabelian groups: effective enumeration via Laurent relations

Problem

Can the ordinary finite presentations defining metabelian groups be recursively enumerated?

\mathcal M=\{\langle x_1,\ldots,x_n\mid r_1,\ldots,r_m\rangle:G''=1\} \quad\stackrel{?}{\in}\quad\Sigma^0_1.

A positive answer requires finite checkable witnesses for $G''=1$ . It does not require a terminating decision procedure on presentations of nonmetabelian groups.

The enumeration theorem

Let $F_n=F(x_1,\ldots,x_n)$ and let $R$ be a finite list of words in $F_n$ . We consider ordinary presentations

P=\langle x_1,\ldots,x_n\mid R\rangle,\qquad G(P)=F_n/\langle\!\langle R\rangle\!\rangle,\qquad \mathcal M=\{P:G(P)''=1\}.

The empty generating set is allowed. Encodings with a letter outside $\{x_1,\ldots,x_n\}$ are rejected.

Theorem 1. There is a primitive-recursive predicate $V$ on natural-number encodings of presentations and finite witnesses such that

\tag{2} P\in\mathcal M \quad\Longleftrightarrow\quad \exists c\in\mathbb N:\ V(P,c)=1.

In particular, $\mathcal M$ is recursively enumerable.

This answers the enumeration question in Kourovka Problem 17.124 (5) and the enumeration and witness questions of Shpilrain (7, Problems 4 and 5). The ordinary-presentation recognition question also occurs in (2, Problem 42, arXiv version), with attribution to Miller (6).

The covering presentations come from Bieri and Strebel (3, §3.5, equations (3.1)–(3.4), Lemma 3.5 and §3.6). We make their finite data effectively recognizable and obtain ordinary finite presentations $P_R$ satisfying

\tag{3} P_R''=1,\qquad G''=1,\ G\text{ finitely presented} \ \Longrightarrow\ \exists P_R\twoheadrightarrow G.

A finite witness for the epimorphism consists of identities in a free group, each a product of conjugates of defining relators. These two ingredients give (2).

The algorithms of Baumslag, Cannonito and Robinson (1, p. 630 and Theorems 2.1, 3.1) take finite presentations in the metabelian variety. Here the input is $F_n/\langle\!\langle R\rangle\!\rangle$ in the variety of all groups. The geometric and module-theoretic ingredients remain classical; the construction makes their finite data sufficient for ordinary-presentation enumeration.

For abelian-by-cyclic groups, recursive enumerability of ordinary finite presentations is already recorded in the proof of (4, Lemma 11.4). Theorem 1 treats arbitrary metabelian groups. Its certificate gives explicit finite Laurent data and normal-closure derivations witnessing metabelianity.

Conventions and classical inputs

We use right conjugation and right commutators:

a^w=w^{-1}aw,\qquad [a,b]=a^{-1}b^{-1}ab.

A group $G$ is metabelian when its derived subgroup $G'$ is abelian, equivalently when $[[a,b],[c,d]]=1$ for all $a,b,c,d\in G$ . Given letters $t_1,\ldots,t_k$ , put

q(v)=t_1^{v_1}\cdots t_k^{v_k}\qquad(v\in\mathbb Z^k).

We retain the literal inverse

q(v)^{-1}=t_k^{-v_k}\cdots t_1^{-v_1}.

Unsubscripted norms are Euclidean.

Lemma 2. Let $k\ge1$ and let $\mathcal A$ be a finite alphabet, with a designated letter $a_{ij}$ for each $1\le i<j\le k$ . For $\rho>0$ , let $H_\rho$ have generators $t_1,\ldots,t_k$ and $\mathcal A$ , and relators

[t_i,t_j]=a_{ij},\qquad [a,b^{q(v)}]=1 \quad(a,b\in\mathcal A,\ v\in\mathbb Z^k,\ \lVert v\rVert<\rho).

Suppose $\rho>2k$ and $u,v\in\mathbb Z^k$ satisfy

\tag{8} \lVert u\rVert\le \frac{\rho}{2k},\qquad \lVert v\rVert<\rho+\frac1{2k},\qquad \lVert u+v\rVert<\rho.

Then, for all $a,b\in\mathcal A$ , the following hold in $H_\rho$ :

[a,b^{q(u)q(v)}]=1,\qquad [a,b^{q(u)^{-1}q(v)^{-1}}]=1.

If all ordered commutation relators are imposed, with no radius restriction, the normal closure of $\mathcal A$ is abelian.

These are the ordered and inverse-ordered cases of (3, Lemma 3.4b); the normal-closure assertion is (3, Corollary 3.3). The collection argument (3, Lemma 3.2) is valid in every quotient of $H_\rho$ .

For the second input, let $A$ be an abelian normal subgroup of a group $E$ with $E/A\cong\mathbb Z^k$ . Conjugation gives $A$ a right module structure over $\mathbb Z[t_1^{\pm 1},\ldots,t_k^{\pm 1}]$ , independent of the chosen lifts of the quotient generators. Let $A^*$ denote the inverse-action module, in which $t_i$ acts as $t_i^{-1}$ acts on $A$ .

Lemma 3. Let $k\ge1$ . Suppose $E$ is finitely presented and metabelian, $E/A\cong\mathbb Z^k$ , and $A$ is finitely generated as a $\mathbb Z[t_1^{\pm 1},\ldots,t_k^{\pm 1}]$ -module. There is a finite family of nonzero Laurent polynomials

\lambda=\sum_{u\in S_\lambda} c_{\lambda,u}t^u \quad(c_{\lambda,u}\in\mathbb Z\setminus\{0\}),

indexed by a signed family $\Lambda=\Lambda_+\sqcup\Lambda_-$ , such that

\begin{gather*} A(\lambda-1)=0\quad(\lambda\in\Lambda_+),\qquad A^*(\lambda-1)=0\quad(\lambda\in\Lambda_-),\\[3pt] \forall v\in\mathbb R^k\setminus\{0\}\ \exists\lambda\in\Lambda: \min_{u\in S_\lambda}v\cdot u>0. \end{gather*}

Apply the necessity direction of (3, Theorem A) and the centralizer criterion (3, Lemma 2.6) to $A$ and $A^*$ . For $A=0$ , use the monomials $t_i^{\pm1}$ ; for $A\ne0$ , an identity-acting polynomial is nonzero. The minus sign changes the module action; the displayed support remains $S_\lambda$ .

Rational separation and the commutation radius

Fix $k\ge1$ and a finite family $(S_\lambda)_{\lambda\in\Lambda}$ of nonempty subsets of $\mathbb Z^k$ . Consider

\tag{12} \forall v\ne0\ \exists\lambda\ \forall u\in S_\lambda: v\cdot u>0.

Only rational arithmetic is needed to test this condition.

Lemma 4. Condition (12) is decidable. If it holds, there is an integer $r\ge0$ such that, for $\varepsilon=2^{-r}$ ,

\tag{13} \forall v\in\mathbb R^k,\ \lVert v\rVert_\infty=1 \ \Longrightarrow\ \exists\lambda\ \forall u\in S_\lambda:\ v\cdot u>\varepsilon.

Whether a proposed $r$ satisfies (13) is decidable by a primitive-recursive computation on the finite integer data.

Proof. Put $\Sigma=\{v\in\mathbb R^k:\lVert v\rVert_\infty=1\}$ . Its faces are

F_{j,s}=\{v\in[-1,1]^k:v_j=s\},\qquad \Sigma=\bigcup_{j=1}^{k}\ \bigcup_{s\in\{-1,1\}}F_{j,s}.

Failure of (13) on $F_{j,s}$ is equivalent to the existence of $(u_\lambda)_\lambda\in\prod_\lambda S_\lambda$ and $v$ satisfying

\tag{15} v\cdot u_\lambda\le\varepsilon\quad(\lambda\in\Lambda), \qquad -1\le v_i\le1,\qquad v_j=s.

Fourier–Motzkin elimination is the following rational equivalence. For $\alpha_i x+\beta_i\cdot y\le\gamma_i$ , put $I_\pm=\{i:\pm\alpha_i>0\}$ and $I_0=\{i:\alpha_i=0\}$ . Then

\exists x\ \forall i:\ \alpha_i x+\beta_i\cdot y\le\gamma_i \quad\Longleftrightarrow\quad \begin{cases} \beta_i\cdot y\le\gamma_i &(i\in I_0),\\[4pt] \dfrac{\gamma_n-\beta_n\cdot y}{\alpha_n} \le\dfrac{\gamma_p-\beta_p\cdot y}{\alpha_p} &(n\in I_-,\ p\in I_+). \end{cases}

After $k$ eliminations, only rational inequalities remain. At each stage, rational values of the remaining coordinates admit a rational choice of the eliminated coordinate. Thus rational and real feasibility agree. Applying the same test with $\varepsilon=0$ decides (12).

Under (12), $\Lambda\ne\varnothing$ and compactness gives

0<\mu:=\min_{v\in\Sigma}\max_\lambda \min_{u\in S_\lambda}v\cdot u, \qquad 2^{-r}<\mu\ \Longrightarrow\ \text{(13)}.

Hence some $r\in\mathbb N$ succeeds. For a supplied $r$ , the $k$ elimination steps, finite choices of supports and exact rational comparisons are primitive recursive. ◻

For data passing this margin test put

\tag{18} C=\frac{2^{-r}}{k},\qquad D=1+\sum_\lambda\sum_{u\in S_\lambda}\lVert u\rVert_1,\qquad R=1+2k\bigl(1+D+D^2k\,2^r\bigr).

Thus $D$ is an integer, $0<C\le1$ , and $R=1+2k(1+D+D^2/C)$ . In particular,

\tag{19} R>2k,\qquad D<\frac{R}{2k},\qquad R>\max\{C,D^2/C\}.

By homogeneity and $\lVert v\rVert_\infty\ge1/k$ for $\lVert v\rVert=1$ , (13) implies that for each Euclidean unit vector $v$ some support satisfies $v\cdot u>C$ throughout.

Lemma 5. Put $\delta=\min\{C/4,1/(4k)\}$ . If $\rho\ge R$ and $\rho\le\lVert v\rVert<\rho+\delta$ , there is a support $S_\lambda$ such that

\lVert v+u\rVert<\rho \qquad(u\in S_\lambda).

Proof. Put $s=\lVert v\rVert$ . The margin in direction $-v/\lVert v\rVert$ gives $\lambda$ with $v\cdot u\le-Cs$ for all $u\in S_\lambda$ . For each such $u$ , $\lVert u\rVert<D$ , and

\begin{align*} \lVert v+u\rVert^2 &=s^2+2v\cdot u+\lVert u\rVert^2\\ &<s^2-2Cs+D^2\\ &<(\rho+\delta)^2-2C(\rho+\delta)+D^2\\ &=\rho^2-2(C-\delta)\rho+\delta^2-2C\delta+D^2\\ &\le\rho^2-\tfrac32 C\rho+D^2 <\rho^2. \end{align*}

Indeed $s\ge\rho\ge R>C$ , $\delta\le C/4$ and $\rho>D^2/C$ . The same $\lambda$ works for every $u\in S_\lambda$ . ◻

Metabelian presentations from Laurent relations

A cover datum consists of $k\ge1$ , a finite nonempty alphabet $\mathcal A$ with designated letters $a_{ij}$ , a finite family of signed nonzero Laurent polynomials, and an integer $r$ passing the margin test. Write $\Lambda_+$ and $\Lambda_-$ for the two signed families, and fix an order on every support. Using the radius (18), define $P_R$ on the alphabet $\{t_1,\ldots,t_k\}\cup\mathcal A$ by

\begin{alignat*} {2} &[t_i,t_j]=a_{ij} &\qquad &(1\le i<j\le k), \tag{22a}\\[3pt] &[a,b^{q(v)}]=1 &\qquad &(a,b\in\mathcal A,\ \lVert v\rVert<R), \tag{22b}\\[3pt] &a=\prod_{u\in S_\lambda}(a^{c_{\lambda,u}})^{q(u)} &\qquad &(a\in\mathcal A,\ \lambda\in\Lambda_+), \tag{22c}\\[3pt] &a=\prod_{u\in S_\lambda}(a^{c_{\lambda,u}})^{q(u)^{-1}} &\qquad &(a\in\mathcal A,\ \lambda\in\Lambda_-). \tag{22d} \end{alignat*}

Products follow the chosen support order; the minus case uses the literal inverse $q(u)^{-1}$ . The relator set is finite since

B_R=\{v\in\mathbb Z^k:\lVert v\rVert<R\} =\left\{v\in[-R,R]^k\cap\mathbb Z^k:\sum_i v_i^2<R^2\right\}.

Proposition 6. Every group $P_R$ constructed from an accepted cover datum is metabelian.

Proof. In a group satisfying (22a), (22c) and (22d), write

\mathcal C(\rho):\quad [a,b^{q(v)}]=1\quad (a,b\in\mathcal A,\ v\in\mathbb Z^k,\ \lVert v\rVert<\rho).

We prove $\mathcal C(\rho)\Rightarrow\mathcal C(\rho+\delta)$ for $\rho\ge R$ .

Only vectors $v$ with $\rho\le\lVert v\rVert<\rho+\delta$ need consideration. Choose $\lambda$ by Lemma 5. Then, for every $u\in S_\lambda$ ,

\tag{25} \lVert u\rVert<D<\rho/(2k),\qquad \lVert v\rVert<\rho+1/(2k),\qquad \lVert u+v\rVert<\rho.

If $\lambda$ has sign $+$ , Lemma 2 and (25) give

[a,b^{q(u)q(v)}]=1\qquad(u\in S_\lambda).

Writing $C_H(a)$ for the centralizer of $a$ in the ambient group, relation (22c) therefore yields

b^{q(v)} =\prod_{u\in S_\lambda}(b^{c_{\lambda,u}})^{q(u)q(v)} \in C_H(a).

If $\lambda$ has sign $-$ , the inverse-word assertion of Lemma 2, with the alphabet letters interchanged, gives

[b,a^{q(u)^{-1}q(v)^{-1}}]=1\qquad(u\in S_\lambda).

Now (22d) yields

a^{q(v)^{-1}} =\prod_{u\in S_\lambda}(a^{c_{\lambda,u}})^{q(u)^{-1}q(v)^{-1}} \in C_H(b).

Conjugating this commutation identity by $q(v)$ gives $[a,b^{q(v)}]=1$ . Thus both signs prove the propagation step.

In $P_R$ , relation (22b) supplies $\mathcal C(R)$ , so

\mathcal C(R+n\delta)\quad(n\in\mathbb N),\qquad \bigcup_{n\ge0}\{v\in\mathbb Z^k:\lVert v\rVert<R+n\delta\}=\mathbb Z^k.

All ordered commutators vanish. Lemma 2 and (22a) imply, for $A_R=\langle\!\langle \mathcal A\rangle\!\rangle$ ,

A_R'=1,\qquad (P_R/A_R)'=1,\qquad P_R'\le A_R,\qquad P_R''=1.\quad\Box

◻

Cofinality of the covers

Lemma 7. If $1\to K\to E\to G\to1$ is a central extension, $G$ is finitely presented, and $K$ is free abelian of finite rank, then $E$ is finitely presented.

Proof. Let $G=\langle x_1,\ldots,x_m\mid r_1,\ldots,r_\ell\rangle$ . Choose lifts $y_i\in E$ and a basis $z_1,\ldots,z_s$ of $K$ ; write

r_j(y)=\prod_{h=1}^{s}z_h^{b_{jh}},\qquad b_{jh}\in\mathbb Z.

For alphabets $Y=\{y_1,\ldots,y_m\}$ and $Z=\{z_1,\ldots,z_s\}$ , set

\begin{align*} \mathcal R_0 &=\{[z_h,z_{h'}]:1\le h<h'\le s\} \cup\{[z_h,y_i]:1\le h\le s,\ 1\le i\le m\},\\[3pt] \mathcal R_1 &=\left\{r_j(y)\left(\prod_{h=1}^{s}z_h^{b_{jh}}\right)^{-1} :1\le j\le\ell\right\}. \end{align*}

The lifts induce an epimorphism

\varphi:\widetilde E:= \langle Y\sqcup Z\mid\mathcal R_0\cup\mathcal R_1\rangle \twoheadrightarrow E.

If $w\in\ker\varphi$ , its image in $G$ is trivial. Express its $Y$ -word as a product of conjugates of $r_j^{\pm1}$ . The relations $\mathcal R_1$ and centrality relations $\mathcal R_0$ give

w=\prod_{h=1}^{s}z_h^{n_h}\quad\text{in }\widetilde E, \qquad 1=\varphi(w)=\prod_{h=1}^{s}z_h^{n_h}\quad\text{in }K.

Independence of the basis implies $n_1=\cdots=n_s=0$ . Hence $\ker\varphi=1$ and $\widetilde E\cong E$ . ◻

Proposition 8. Every finitely presented metabelian group $G$ is an epimorphic image of some certified cover $P_R$ .

Proof. Put $A=G'$ and $Q=G/A$ . Choose a surjection $\pi:\mathbb Z^k\twoheadrightarrow Q$ with $k\ge1$ and form the pullback

E=\{(g,z)\in G\times\mathbb Z^k:gA=\pi(z)\}.

Both projections are surjective. Their kernels give exact sequences

\tag{37} 1\longrightarrow A\longrightarrow E\longrightarrow\mathbb Z^k\longrightarrow1, \qquad 1\longrightarrow\ker\pi\longrightarrow E\longrightarrow G\longrightarrow1.

The second kernel consists of $(1,z)$ with $z\in\ker\pi$ , and is central and free abelian of finite rank. Lemma 7 makes $E$ finitely presented. As a subgroup of the metabelian group $G\times\mathbb Z^k$ , it is metabelian.

For a finite generating set $g_1,\ldots,g_m$ of $G$ ,

G'=\langle\!\langle [g_i,g_j]:i<j\rangle\!\rangle,\qquad A=\sum_{i<j}[g_i,g_j]\,\mathbb ZQ.

The second equality uses additive module notation for the abelian group $A$ . Pullback along $\pi$ preserves these module generators.

Choose lifts $t_i\in E$ of the standard basis of $\mathbb Z^k$ . Take a finite module-generating alphabet $\mathcal A$ for $A$ , including letters representing every $[t_i,t_j]$ . A letter representing the identity may be added to ensure that the alphabet is nonempty. Lemma 3 supplies signed Laurent identities on this module. Lemma 4 supplies a finite margin certificate.

The selected elements satisfy (22a) by construction, (22b) because $A'=1$ , and (22c)–(22d) by the module identities. They induce $\psi:P_R\to E$ . If $B$ is the image of $\mathcal A$ , then

A=\langle b^{q(v)}:b\in B,\ v\in\mathbb Z^k\rangle \le\operatorname{im}\psi, \qquad E=A\langle t_1,\ldots,t_k\rangle=\operatorname{im}\psi.

Thus $\psi$ is surjective, and $P_R\twoheadrightarrow E\twoheadrightarrow G$ . ◻

Epimorphisms and normal closures

For $P=\langle X\mid R\rangle$ and $w\in F(X)$ ,

\tag{40} w\in\langle\!\langle R\rangle\!\rangle \quad\Longleftrightarrow\quad w=\prod_{\nu=1}^{m}h_\nu^{-1}r_{j_\nu}^{\epsilon_\nu}h_\nu \text{ in }F(X), \qquad \epsilon_\nu\in\{-1,1\}.

Here the right side means existence of $m\ge0$ , $h_\nu\in F(X)$ , $r_{j_\nu}\in R$ and the indicated signs. A specified identity is checked by free reduction.

Lemma 9. Let $H=\langle y_1,\ldots,y_\ell\mid S\rangle$ and $G=\langle x_1,\ldots,x_n\mid R\rangle$ . Then

\exists\,f:H\twoheadrightarrow G \quad\Longleftrightarrow\quad \begin{gathered} \exists u_1,\ldots,u_\ell\in F(X),\ v_1,\ldots,v_n\in F(Y):\\ s(u_1,\ldots,u_\ell)\in\langle\!\langle R\rangle\!\rangle\quad(s\in S),\\ v_j(u_1,\ldots,u_\ell)x_j^{-1}\in\langle\!\langle R\rangle\!\rangle\quad(1\le j\le n). \end{gathered}

Together with products (40) for these finitely many normal-closure memberships, the words $u_i,v_j$ have a primitive-recursive checking predicate.

Proof. The first family of identities induces

f:H\longrightarrow G,\qquad y_i\longmapsto u_i\langle\!\langle R\rangle\!\rangle.

The second gives $f(v_j)=x_j\langle\!\langle R\rangle\!\rangle$ , hence $\operatorname{im}f=G$ . Conversely, choose words representing the images and preimages of the generators under an epimorphism. Its defining identities lie in $\langle\!\langle R\rangle\!\rangle$ and therefore admit (40). Substitution and free reduction of finite words, and the finite integer and index checks in (40), are primitive recursive. ◻

Proof of Theorem 1. Write $\mathsf A(d,r)$ for the margin condition (13) on finite Laurent data $d$ , and $P_{d,r}$ for the presentation (22a)–(22d) at the radius (18). Let $\mathsf E(H,P;\eta)$ check the words and products in Lemma 9. For a decoded witness $c=(d,r,\eta)$ , set

\tag{43} \begin{aligned} V(P,c)=1\quad\Longleftrightarrow\quad& \mathsf{WF}(P)\ \land\\ &\bigl(n(P)=0\ \lor\ [\mathsf A(d,r)\land\mathsf E(P_{d,r},P;\eta)]\bigr), \end{aligned}

where $\mathsf{WF}$ checks the generating alphabet and $n(P)$ is its size. All finite syntax checks are included in $\mathsf A$ and $\mathsf E$ . The radius is an integer expression in the data, and

\{v\in\mathbb Z^k:\lVert v\rVert<R\} = \left\{v\in[-R,R]^k\cap\mathbb Z^k:\sum_i v_i^2<R^2\right\}.

Consequently, constructing $P_{d,r}$ uses a bounded finite list. Lemma 4 and Lemma 9 show that $V$ is primitive recursive.

For $n(P)>0$ , soundness is the implication

V(P,c)=1 \ \Longrightarrow\ P_{d,r}''=1,\quad P_{d,r}\twoheadrightarrow G(P) \ \Longrightarrow\ G(P)''=1,

by Proposition 6. For completeness, Proposition 8 and Lemma 4 give

G(P)''=1 \ \Longrightarrow\ \exists d,r:\ \mathsf A(d,r),\quad P_{d,r}\twoheadrightarrow G(P).

Lemma 9 supplies $\eta$ . If $n(P)=0$ and $P$ is well formed, $G(P)=1$ , as required by the first branch of (43). This proves (2). Finally, projection of the primitive-recursive relation $\{(P,c):V(P,c)=1\}$ gives the asserted recursive enumeration. ◻

References

Preprint · Lean (GitHub)

G. Baumslag, F. B. Cannonito and D. J. S. Robinson, The algorithmic theory of finitely generated metabelian groups, Trans. Amer. Math. Soc. 344 (1994), no. 2, 629–648. doi:10.2307/2154499.

L. Bartholdi, L. Pernak and E. Rauzy, Groups with presentations in EDT0L, Groups Geom. Dyn., published online first, 25 August 2025. doi:10.4171/GGD/911. Author version arXiv:2402.01601v2 (2024).

R. Bieri and R. Strebel, Valuations and finitely presented metabelian groups, Proc. London Math. Soc. (3) 41 (1980), no. 3, 439–464. doi:10.1112/plms/s3-41.3.439.

D. P. Groves, J. F. Manning and H. Wilton, Recognizing geometric 3-manifold groups using the word problem (2012). arXiv:1210.2101.

E. I. Khukhro and V. D. Mazurov (eds.), The Kourovka Notebook: Unsolved Problems in Group Theory, 21st ed., version of 1 September 2026. arXiv:1401.0300v46.

C. F. Miller III, Decision problems for groups—survey and reflections, in Algorithms and Classification in Combinatorial Group Theory, G. Baumslag and C. F. Miller III (eds.), Math. Sci. Res. Inst. Publ. 23, Springer, New York, 1992, pp. 1–59. doi:10.1007/978-1-4613-9730-4_1.

V. Shpilrain, Search and witness problems in group theory, Groups Complex. Cryptol. 2 (2010), no. 2, 231–246. doi:10.1515/GCC.2010.015. arXiv:1010.0382.