Kourovka Notebook Problem 21.62

Definitions and mathematical statement

Fix a finite-rank free group $F_n=\langle x_1,\ldots,x_n\rangle$, $n\ge1$, and an automorphism $\varphi:F_n\to F_n$. Put \[ G=F_n\rtimes_\varphi\mathbb Z =\langle x_1,\ldots,x_n,t\mid tx_it^{-1}=\varphi(x_i),\ 1\le i\le n\rangle. \] Words in the finite alphabet $x_i^{\pm1},t^{\pm1}$ encode elements of this fixed group. The automorphism and ambient presentation may be built into the algorithm.

The uniform subgroup membership problem for $G$ has input a word $w$ and a finite list of words $h_1,\ldots,h_k$. Its required answer is whether \[ w\in H:=\langle h_1,\ldots,h_k\rangle. \] Equivalently, a positive answer asserts that $w$ equals in $G$ some finite product of the $h_i$ and their inverses; the empty product is allowed. An empty generating list therefore specifies the trivial subgroup. Equality is in $G$, not literal equality of word strings.

Does every fixed group $G$ of the stated form admit an algorithm which halts and gives the correct yes-or-no answer for every such input? Uniformity here refers to the subgroup: the algorithm must handle all finite generating lists, not merely membership in one particular subgroup chosen in advance. The list length and word lengths may vary without bound. No bound on running time is requested, and enumerating positive certificates without halting on negative instances would not decide the problem.

Short English statement

Is membership in a finitely generated subgroup decidable uniformly over all finite generating lists in every fixed free-by-cyclic group?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 2571 (KOU-21.62), Kourovka Notebook - New Problems, Issue 21. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 The Kourovka Notebook, 21st edition, new problems, Problem 21.62. Expanded formulation of the supplied catalogue statement. https://arxiv.org/pdf/1401.0300v47.