Submonoid Membership in n-Dimensional Lamplighter Groups and S-Unit Equations

Dong, Ruiwen

doi:10.4230/LIPIcs.ICALP.2025.154

Submonoid Membership in n-Dimensional Lamplighter Groups and S-Unit Equations

Ruiwen Dong

Department of Mathematics, Saarland University, Saarbrücken, Germany
Magdalen College, University of Oxford, UK

Abstract

We show that Submonoid Membership is decidable in $n$ -dimensional lamplighter groups $(\mathbb{Z}/p\mathbb{Z})\wr\mathbb{Z}^{n}$ for any prime $p$ and integer $n$ . More generally, we show decidability of Submonoid Membership in semidirect products of the form $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ , where $\mathcal{Y}$ is any finitely presented module over the Laurent polynomial ring $\mathbb{F}_{p}[X_{1}^{\pm},\ldots,X_{n}^{\pm}]$ . Combined with a result of Shafrir (2024), this gives the first example of a group $G$ and a finite index subgroup $\widetilde{G}\leq G$ , such that Submonoid Membership is decidable in $\widetilde{G}$ but undecidable in $G$ .

To obtain our decidability result, we reduce Submonoid Membership in $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ to solving S-unit equations over $\mathbb{F}_{p}[X_{1}^{\pm},\ldots,X_{n}^{\pm}]$ -modules. We show that the solution set of such equations is effectively $p$ -automatic, extending a result of Adamczewski and Bell (2012). As an intermediate result, we also obtain that the solution set of the Knapsack Problem in $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ is effectively $p$ -automatic.

Keywords and phrases:

Submonoid Membership, lamplighter groups, S-unit equations, p-automatic sets, Knapsack in groups

Category:

Track B: Automata, Logic, Semantics, and Theory of Programming

Copyright and License:

2012 ACM Subject Classification:

Computing methodologies

\rightarrow

Symbolic and algebraic manipulation

Related Version:

Full Version: https://arxiv.org/abs/2409.07077

Acknowledgements:

The author would like to thank Doron Shafrir for pointing out the open problem on Submonoid Membership in finite extension of groups, as well as for discussion of his work [37]. The author would like to thank the anonymous reviewers for their helpful comments.

Funding:

This work was funded by the European Union (ERC, AdG grant 101097307). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

DOI:

10.4230/LIPIcs.ICALP.2025.154

Event:

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Editors:

Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Algorithmic problems in infinite groups

Algorithmic problems concerning groups are a classical topic in algebra and theoretical computer science. Dating back to the work of Max Dehn from the 1910s, this area has traditionally served as a bridge between geometry, algebra and logic, and has now found numerous applications in automata theory, program analysis and complexity theory [7, 9, 14, 22]. One of the central decision problems on groups is the Submonoid Membership problem: given a finite number of elements $g_{1},g_{2},\ldots,g_{k}$ in a group $G$ and an element $g\in G$ , does $g$ belong to the submonoid generated by $g_{1},g_{2},\ldots,g_{k}$ ? In the seminal work of Markov from the 1950s [30], it was shown that Submonoid Membership is undecidable for a matrix group of dimension six. The undecidability result was later strengthened to the group $\mathsf{SL}(4,\mathbb{Z})$ of $4\times 4$ integer matrices of determinant one [31]. Subsequently, a number of positive decidability results were obtained, such as for commutative matrix groups [2], low-dimensional matrix groups [12, 33], and certain graph groups [26]. See [15, 25] for recent surveys.

A generalization of Submonoid Membership is the Rational Subset Membership problem: given a rational subset $S$ of a group $G$ and an element $g\in G$ , does $g$ belong to $S$ ? Here, a subset $S$ of a group $G$ is called a rational subset if there is a finite alphabet $\Sigma$ , a monoid homomorphism $\varphi\colon\Sigma^{*}\rightarrow G$ , and a regular language $L\subseteq\Sigma^{*}$ , such that $\varphi(L)=S$ . In particular, if $L=\Sigma^{*}$ , then we recover the definition of Submonoid Membership. In fact, many decidability results for Submonoid Membership are also proven for the more general Rational Subset Membership, such as in free groups [8], abelian groups [20], and certain wreath products [28]. Nevertheless, Bodart [10] and Shafrir¹¹1An example appeared in the Bachelor’s thesis of Potthast [34], based on an unpublished draft of Shafrir. recently provided examples of groups with undecidable Rational Subset Membership but decidable Submonoid Membership.

A longstanding open problem in computational group theory is whether decidability of Submonoid Membership is preserved under finite extension of groups. Grunschlag [20] showed that for any group $G$ and a finite index subgroup $\widetilde{G}\leq G$ , Rational Subset Membership is decidable in $\widetilde{G}$ if and only if it is decidable in $G$ . The same statement is also true for the Subgroup Membership problem [20] (given $g_{1},g_{2},\ldots,g_{k},g$ , does $g$ belong to the subgroup generated by $g_{1},g_{2},\ldots,g_{k}$ ?). Whether the same holds for Submonoid Membership remained open. One of the goals of this paper is to construct a counterexample to this open problem: we construct a group $G$ and a finite index subgroup $\widetilde{G}\leq G$ , such that Submonoid Membership is decidable in $\widetilde{G}$ but undecidable in $G$ .

n-dimensional lamplighter groups

In this paper, we study Submonoid Membership in $n$ -dimensional lamplighter groups as well as their generalizations. The lamplighter groups are well-studied objects in the context of geometric group theory [19, 38]. Given an integer $p\geq 2$ and $n\in\mathbb{N}$ , the $n$ -dimensional lamplighter group, denoted $(\mathbb{Z}/p\mathbb{Z})\wr\mathbb{Z}^{n}$ , can be most easily defined as the (multiplicative) $2\times 2$ upper-triangular matrix group

\left\{\begin{pmatrix}X_{1}^{a_{1}}X_{2}^{a_{2}}\cdots X_{n}^{a_{n}}&f\\ 0&1\\ \end{pmatrix}\;\middle|\;a_{1},a_{2},\ldots,a_{n}\in\mathbb{Z},\;f\in(\mathbb{% Z}/p\mathbb{Z})[X_{1},X_{1}^{-1},\ldots,X_{n},X_{n}^{-1}]\right\},

(1)

where $(\mathbb{Z}/p\mathbb{Z})[X_{1},X_{1}^{-1},\ldots,X_{n},X_{n}^{-1}]$ is the Laurent polynomial ring over $n$ variables, with coefficients in the finite ring $\mathbb{Z}/p\mathbb{Z}=\{0,1,\ldots,p-1\}$ . When $p$ is prime, $\mathbb{Z}/p\mathbb{Z}$ is actually the finite field $\mathbb{F}_{p}$ . Intuitively, an element in $(\mathbb{Z}/p\mathbb{Z})\wr\mathbb{Z}^{n}$ can be understood as the following configuration: at each position in the lattice $\mathbb{Z}^{n}$ there is a lamp, each lamp has a state among $\mathbb{Z}/p\mathbb{Z}=\{0,1,\ldots,p-1\}$ , and there is a pointer at some position in $\mathbb{Z}^{n}$ . In particular, for the element $\begin{pmatrix}X_{1}^{a_{1}}\cdots X_{n}^{a_{n}}&f\\ 0&1\\ \end{pmatrix}$ , the pointer is at position $(a_{1},\ldots,a_{n})\in\mathbb{Z}^{n}$ , the lamp at position $(z_{1},\ldots,z_{n})\in\mathbb{Z}^{n}$ has state $s$ if the monomial $X_{1}^{z_{1}}\cdots X_{n}^{z_{n}}$ appearing in $f$ has coefficient $s$ . In particular, all but finitely many lamps have state 0. Multiplication in the group $(\mathbb{Z}/p\mathbb{Z})\wr\mathbb{Z}^{n}$ , like matrix multiplication, corresponds to first moving the pointer by a vector $(a_{1},\ldots,a_{n})$ , then additively changing the states of the lamps around the new location.

Owing to this geometric interpretation, the study of lamplighter groups has close connections to automata theory, tiling problems, random walks, and graph theory [3, 4, 23, 27, 29]. Lamplighter groups are also important examples of metabelian groups, which are some of the most tractable generalization of abelian groups. Recall that a group $G$ is called metabelian if it admits a normal subgroup $A$ such that both $A$ and $G/A$ are abelian. An important amount of research in computational group theory concentrates on metabelian groups, since decision problems in abelian groups are already well-understood. For example, Cadilhac, Chistikov and Zetzsche [11] showed decidability of Rational Subset Membership in the Baumslag-Solitar groups $\mathsf{BS}(1,p)$ ; Lohrey, Steinberg and Zetzsche [27] showed decidability of Rational Subset Membership in $1$ -dimensional lamplighter groups. On the other hand, the $2$ -dimensional lamplighter groups occupy an interesting position as they have undecidable Rational Subset Membership [27] but decidable Submonoid Membership [34]. The decision algorithm in [34] cannot be generalized to dimensions larger than 2 as it relies on a reduction to Rational Subset Membership in dimension 1. It is thus left as an open problem whether Submonoid Membership is decidable in lamplighter groups of dimension $n\geq 3$ .

Contributions of this paper

In this paper, we show that Submonoid Membership is decidable in lamplighter groups $(\mathbb{Z}/p\mathbb{Z})\wr\mathbb{Z}^{n}$ of every dimension $n\in\mathbb{N}$ and prime $p$ . In fact, we prove a much more general result (Theorem 3.1): Submonoid Membership is decidable for semidirect products $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ , where $\mathcal{Y}$ is a finitely presented module over the Laurent polynomial ring $\mathbb{F}_{p}[X_{1}^{\pm},\ldots,X_{n}^{\pm}]$ .

An important consequence of the more general Theorem 3.1 is the resolution of a longstanding open problem (Corollary 3.2). Combined with a recent result of Shafrir [37], we show that there exist a group $G$ and a finite index subgroup $\widetilde{G}\leq G$ , such that Submonoid Membership decidable in $\widetilde{G}$ but undecidable in $G$ .

Our main strategy to decide Submonoid Membership in $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ is to reduce it to solving S-unit equations over modules: these are equations of the form $x_{1}c_{1}+x_{2}c_{2}+\cdots+x_{m}c_{m}=c_{0}$ , where the variables $x_{i}$ take value in a multiplicative subgroup of a commutative ring. We show that the solutions of such S-unit equations over an $\mathbb{F}_{p}[X_{1}^{\pm},\ldots,X_{n}^{\pm}]$ -module forms an effectively $p$ -automatic set (Theorem 3.3), generalizing a result of Adamczewski and Bell [1]. As an intermediate result, we also obtain effective $p$ -automaticity for the solution set of the Knapsack Problem in $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ : given $g_{1},g_{2},\ldots,g_{k},g\in\mathcal{Y}\rtimes\mathbb{Z}^{n}$ , find $(z_{1},\ldots,z_{k})\in\mathbb{Z}^{k}$ such that $g_{1}^{z_{1}}g_{2}^{z_{2}}\cdots g_{k}^{z_{k}}=g$ . We give an example (Example 4.9) where the solution set is $p$ -automatic but not semilinear. This shows that the situation in semidirect products is much more complicated than in the wreath product of two abelian groups, as seen in the work of Ganardi, König, Lohrey, and Zetzsche [18].

Note that our decidability results heavily rely on working over the finite ring $\mathbb{Z}/p\mathbb{Z}$ instead of the infinite ring $\mathbb{Z}$ . Indeed, Submonoid Membership is known to be undecidable [28] in $\mathbb{Z}\wr\mathbb{Z}^{n}$ for $n\geq 1$ , and solving S-unit equations over $\mathbb{Z}[X_{1}^{\pm}]$ -modules is also known to be undecidable [16]. Nevertheless, it is not clear whether the decidability for $(\mathbb{Z}/p\mathbb{Z})\wr\mathbb{Z}^{n}$ can be generalized to non-prime numbers $p$ , for example when $p=p_{1}p_{2}$ for two primes $p_{1}\neq p_{2}$ . This is closely related to deciding emptiness of the intersection of a $p_{1}$ -automatic set and a $p_{2}$ -automatic set, which to the best of our knowledge remains an open problem (however, see [21, 24] for recent progress). Progress towards a solution for non-prime $p$ will also be the first step towards a classification of metabelian groups with decidable Submonoid Membership, namely by tackling those with torsion commutators.

2 Preliminaries

Laurent polynomial ring and modules

Let $p$ be a prime number, denote by $\mathbb{F}_{p}$ the finite field of size $p$ . Denote by $\mathbb{F}_{p}[X_{1}^{\pm},\ldots,X_{n}^{\pm}]$ the Laurent polynomial ring over $\mathbb{F}_{p}$ with $n$ variables: this is the set of polynomials over the variables $X_{1},X_{1}^{-1},\ldots,X_{n},X_{n}^{-1}$ , with coefficients in $\mathbb{F}_{p}$ , such that $X_{i}X_{i}^{-1}=1$ for all $i$ . When $n$ is fixed, we denote by $\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu$ the tuple of variables $(X_{1},\ldots,X_{n})$ , and $\mathbb{F}_{p}[X_{1}^{\pm},\ldots,X_{n}^{\pm}]$ is written in short as $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ .

For a vector $\boldsymbol{a}=(a_{1},\ldots,a_{n})\in\mathbb{Z}^{n}$ , denote by $\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}}$ the monomial $X_{1}^{a_{1}}X_{2}^{a_{2}}\cdots X_{n}^{a_{n}}$ . When $\Lambda$ is a subgroup of $\mathbb{Z}^{n}$ , we denote by $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \Lambda}]\subseteq\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5% mu}\mkern 1.5mu^{\pm}]$ the subring of polynomials of the form $\sum_{\boldsymbol{a}\in\Lambda}c_{\boldsymbol{a}}\mkern 1.5mu\overline{\mkern-% 1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}}$ .

Since we work in polynomial rings over a finite field $\mathbb{F}_{p}$ , it is worth pointing out a useful equation, folklorishly dubbed “the freshman’s dream”. For any $f\in\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5% mu^{\pm}]$ , we have $(f+1)^{p}=f^{p}+1$ , and more generally $(f+1)^{p^{k}}=f^{p^{k}}+1$ for all $k\in\mathbb{N}$ .

When $R$ is a commutative ring (such as $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ ), an $R$ -module is defined as an abelian group $(M,+)$ along with an operation $\cdot\;\colon R\times M\rightarrow M$ satisfying $f\cdot(m+m^{\prime})=f\cdot m+f\cdot m^{\prime}$ , $(f+g)\cdot m=f\cdot m+g\cdot m$ , $fg\cdot m=f\cdot(g\cdot m)$ and $1\cdot m=m$ . For example, for any $d\in\mathbb{N}$ , $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]^{d}$ is an $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module by $f\cdot(h_{1},\ldots,h_{d})=(fh_{1},\ldots,fh_{d})$ . We often use a bold symbol $\boldsymbol{h}$ to denote a vector $(h_{1},\ldots,h_{d})\in\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX% \mkern-1.5mu}\mkern 1.5mu^{\pm}]^{d}$ .

Given elements $\boldsymbol{h}_{1},\ldots,\boldsymbol{h}_{k}$ in an $R$ -module $M$ , we say that they generate the $R$ -module

\sum_{i=1}^{k}R\cdot\boldsymbol{h}_{i}\coloneqq\left\{\sum_{i=1}^{k}r_{i}\cdot% \boldsymbol{h}_{i}\;\middle|\;r_{1},\ldots,r_{k}\in R\right\}\subseteq M.

Given submodules $M,M^{\prime}$ of $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]^{d}$ such that $M\supseteq M^{\prime}$ , we define the quotient $M/M^{\prime}\coloneqq\{\overline{m}\mid m\in M\}$ where $\overline{m}_{1}=\overline{m}_{2}$ if and only if $m_{1}-m_{2}\in M^{\prime}$ . This quotient is also an $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module. We say that an $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module $\mathcal{Y}$ is finitely presented if it can be written as a quotient $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]^{d}/M$ for a finitely generated submodule $M$ of $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]^{d}$ for some $d\in\mathbb{N}$ . We call a finite presentation of $\mathcal{Y}$ the generators of such $M$ . Every finitely generated $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module admits a finite presentation.

Given a finitely presented $\mathbb{F}_{p}[X_{1}^{\pm},\ldots,X_{n}^{\pm}]$ -module $\mathcal{Y}$ , we can define the following group using semidirect product:

\mathcal{Y}\rtimes\mathbb{Z}^{n}\coloneqq\{(y,\boldsymbol{a})\mid y\in\mathcal% {Y},\boldsymbol{a}\in\mathbb{Z}^{n}\};

(2)

multiplication and inversion in this group are defined by

(y,\boldsymbol{a})\cdot(y^{\prime},\boldsymbol{a}^{\prime})=\big{(}y+\mkern 1.% 5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}}\cdot y^{% \prime},\boldsymbol{a}+\boldsymbol{a}^{\prime}\big{)},\quad(y,\boldsymbol{a})^% {-1}=\big{(}\!-\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{-% \boldsymbol{a}}\cdot y,-\boldsymbol{a}\big{)}.

(3)

The neutral element of $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ is $(0,\boldsymbol{0})$ , where $\boldsymbol{0}$ denotes the zero vector in $\mathbb{Z}^{n}$ . Intuitively, the element $(y,\boldsymbol{a})$ can be seen as a $2\times 2$ matrix $\begin{pmatrix}\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \boldsymbol{a}}&y\\ 0&1\\ \end{pmatrix}$ , where group multiplication is represented by matrix multiplication. We have the formula $(f,\boldsymbol{a})(y,\boldsymbol{0})(f,\boldsymbol{a})^{-1}=(\mkern 1.5mu% \overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}}\cdot y,% \boldsymbol{0})$ . Note that $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ naturally contains the subgroup $\mathcal{Y}\cong\{(y,\boldsymbol{0})\mid y\in\mathcal{Y}\}$ , and there is a projection map $\pi\colon\mathcal{Y}\rtimes\mathbb{Z}^{n}\rightarrow\mathbb{Z}^{n},\,(y,% \boldsymbol{a})\mapsto\boldsymbol{a}$ , such that $\ker(\pi)=\mathcal{Y}$ .

In particular, if we take $\mathcal{Y}=\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}% \mkern 1.5mu^{\pm}]$ considered as a $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module, then we recover the definition (1) of the $n$ -dimensional lamplighter group $(\mathbb{Z}/p\mathbb{Z})\wr\mathbb{Z}^{n}$ .

Effective computation in modules

In order to effectively compute in groups of the form $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ , we need to be able to effectively compute in the $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module $\mathcal{Y}$ . The following are some classic problems with effective algorithms that we will make use of. We state the following result over $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ , although they hold over polynomial rings over any field.

Lemma 2.1 ([5, Lemma 2.1, 2.2]).

Let $\mathcal{Y}$ be an $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module with a given finite presentation. The following problems are effectively solvable:

(i)

(Submodule Membership) Given elements $y_{1},\ldots,y_{k},y\in\mathcal{Y}$ , decide whether $y$ is in the submodule generated by $y_{1},\ldots,y_{k}$ .
(ii)

(Submodule Presentation) Given elements $y_{1},\ldots,y_{k}\in\mathcal{Y}$ , compute a finite presentation for the submodule generated by $y_{1},\ldots,y_{k}$ .
(iii)

(Computing intersection and sum) Given the generators of a submodule $A\subseteq\mathcal{Y}$ and the generators of a submodule $B\subseteq\mathcal{Y}$ , compute the generators for the submodule $A\cap B$ and for the submodule $A+B=\{a+b\mid a\in A,b\in B\}$ .
(iv)

(Computing quotient) Given the generators of a submodule $\mathcal{Y}^{\prime}\subseteq\mathcal{Y}$ , compute a finite presentation of the quotient $\mathcal{Y}/\mathcal{Y}^{\prime}$ .

Let $\Lambda$ be a subgroup of $\mathbb{Z}^{n}$ , then any $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module can be considered as a (possibly infinitely generated) $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \Lambda}]$ -module. For example, the $\mathbb{F}_{p}[X_{1}^{\pm},X_{2}^{\pm}]$ -module $\mathbb{F}_{p}[X_{1}^{\pm},X_{2}^{\pm}]$ can be considered as an $\mathbb{F}_{p}[X_{1}^{\pm}]$ -module, but it is not finitely generated (it is generated by the infinite set $\{\ldots,X_{2}^{-2},X_{2}^{-1},1,X_{2},X_{2}^{2},\ldots\}$ ). However, finitely generated $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \Lambda}]$ -submodules of an $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module are still effectively computable:

Lemma 2.2 ([5, Theorem 2.14] or [6, Theorem 2.6]).

Let $\Lambda$ be a subgroup of $\mathbb{Z}^{n}$ , and $\mathcal{Y}$ be a finitely presented $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module. Given a finite subset $S$ of $\mathcal{Y}$ , one can effectively compute the finite presentation of the $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \Lambda}]$ -module $\sum_{s\in S}\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}% \mkern 1.5mu^{\Lambda}]\cdot s$ .

p-automatic sets

We recall the standard notion of $p$ -automatic subsets of $\mathbb{Z}$ , and more generally, $p$ -automatic subsets of $\mathbb{Z}^{d}$ .

Let $\Sigma$ be a finite alphabet. An automaton over $\Sigma$ is a tuple $\mathcal{A}=(Q,\Sigma,\delta,q_{I},F)$ , where $Q$ is a finite set of states, $\delta\colon Q\times\Sigma\rightarrow Q$ is the transition function, $q_{I}$ is the initial state, and $F\subseteq Q$ is the set of final states. For a state $q$ in $Q$ and for a finite word $w=w_{1}w_{2}\cdots w_{n}$ over the alphabet $\Sigma$ , we define $\delta(q,w)$ recursively by $\delta(q,w)=\delta(\delta(q,w_{1}w_{2}\cdots w_{n-1}),w_{n})$ . The word $w$ is accepted by $\mathcal{A}$ if $\delta(q_{I},w)\in F$ .

Let $p\geq 2$ be an integer, define the alphabet $\Sigma_{p}\coloneqq\{+,-,0,1,2,\ldots,p-1\}$ . Let $n\geq 0$ be a non-negative integer and let $w_{r}w_{r-1}\cdots w_{1}w_{0}\in(\Sigma_{p})^{r+1}$ be the base- $p$ expansion of $n$ . That is, $n=\sum_{i=0}^{r}w_{i}p^{i}$ with the smallest possible $r$ . We denote by $w(n)$ the word $+w_{0}w_{1}\cdots w_{r}$ . For example, if $p=2$ , then $w(4)=+001$ . Similarly, for a negative integer $-n$ , let $w(-n)$ denote the word $-w_{0}w_{1}\cdots w_{r}$ . A subset $S$ of $\mathbb{Z}$ is called $p$ -automatic if there is an automaton over $\Sigma_{p}$ that accepts exactly the set $w(S)\coloneqq\{w(s)\mid s\in S\}$ . For example, the set $S=\{2^{k}\mid k\in\mathbb{N}\}$ is 2-automatic, because $w(S)=\{+1,+01,+001,+0001,\cdots\}$ is accepted by an automaton over $\Sigma_{2}=\{+,-,0,1\}$ .

Let $d\in\mathbb{N}$ . The definition of $p$ -automatic subsets of $\mathbb{Z}$ can be naturally generalized to $p$ -automatic subsets of $\mathbb{Z}^{d}$ . For $(z_{1},\ldots,z_{d})\in\mathbb{Z}^{d}$ , consider the tuple of words $(w(z_{1}),\ldots,w(z_{d}))$ over the alphabet $\Sigma_{p}$ . We naturally identify a $d$ -tuple of words $(w(z_{1}),\ldots,w(z_{d}))$ over the alphabet $\Sigma_{p}$ as a single word $w(z_{1},\ldots,z_{d})$ over the alphabet $\Sigma_{p}^{d}$ : if the words $w(z_{1}),\ldots,w(z_{d})$ have different lengths, we add a minimal number of zeros at the end so they all have equal lengths. Naturally, a subset $S$ of $\mathbb{Z}^{d}$ is called $p$ -automatic if there is an automaton over $\Sigma_{p}^{d}$ that accepts exactly the set $w(S)\coloneqq\{w(s)\mid s\in S\}$ . For example, the set $S=\{(a,2a)\mid a<-1\}$ $\subset\mathbb{Z}^{2}$ is 2-automatic, because

w(S)=\{(-,-)(a_{1},0)(a_{2},a_{1})(a_{3},a_{2})\cdots(a_{k},a_{k-1})(1,a_{k})(% 0,1)\mid k\in\mathbb{N},a_{1},\ldots,a_{k}\in\{0,1\}\}

is accepted by an automaton over $\Sigma_{2}^{2}$ . We say a subset $S\subseteq\mathbb{Z}^{d}$ is effectively $p$ -automatic if its accepting automaton is explicitly given. $p$ -automatic sets enjoy various closure properties. In this paper, we will use the following:

Lemma 2.3 ([39]).

Let $p\geq 2$ be an integer.

(1)

If $S$ and $T$ are effectively $p$ -automatic subsets of $\mathbb{Z}^{d}$ , then $S\cap T$ and $S\cup T$ are also effectively $p$ -automatic.
(2)

If $S\subseteq\mathbb{Z}^{d}$ is effectively $p$ -automatic, and $\varphi\colon\mathbb{Z}^{d}\rightarrow\mathbb{Z}^{n}$ is a linear transformation, then $\varphi(S)\subseteq\mathbb{Z}^{n}$ is also effectively $p$ -automatic.
(3)

If $S\subseteq\mathbb{Z}^{d}$ is effectively $p$ -automatic, and $\phi\colon\mathbb{Z}^{N}\rightarrow\mathbb{Z}^{d}$ is a linear transformation, then $\phi^{-1}(S)\coloneqq\{v\in\mathbb{Z}^{N}\mid\phi(v)\in S\}$ is also effectively $p$ -automatic.
(4)

It is decidable whether a given effectively $p$ -automatic set $S$ is empty.

3 Main results and consequences

The main result of this paper is the following.

Theorem 3.1.

Let $p$ be a prime number, $\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu=(X_{1},\ldots,X_{% n})$ be a tuple of variables and $\mathcal{Y}$ be a finitely presented $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module. Then, Submonoid Membership is decidable in the group $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ .

In particular, taking $\mathcal{Y}=\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}% \mkern 1.5mu^{\pm}]$ , we immediately obtain decidability of Submonoid Membership in the $n$ -dimensional lamplighter groups $(\mathbb{Z}/p\mathbb{Z})\wr\mathbb{Z}^{n}$ for prime $p$ .

We say a group is virtually abelian if it has a finite index subgroup that is abelian. A recent result of Shafrir [37, Theorem 8.1] shows that membership problem in a fixed rational subset $S$ of a group $L$ can be reduced to the membership problem in a fixed submonoid $M$ of the group $L\times H$ , where $H$ is an explicitly constructed finitely generated virtually abelian group. Combined with Theorem 3.1, this allows us to construct an example where decidability of Submonoid Membership is not preserved under finite extension of groups:

Corollary 3.2.

There exist a group $G$ and a finite index subgroup $\widetilde{G}\leq G$ , such that Submonoid Membership is decidable in $\widetilde{G}$ but undecidable in $G$ .

Proof.

By [27, Theorem 10], there is a rational subset $S$ of the two-dimensional lamplighter group $L\coloneqq(\mathbb{Z}/2\mathbb{Z})\wr\mathbb{Z}^{2}$ , whose membership problem (given $g\in L$ , whether $g\in S$ ?) is undecidable. By Shafrir’s result [37, Theorem 8.1], the membership problem in $S$ reduces to the membership problem in a finitely generated submonoid of the group $G\coloneqq L\times H$ , where $H$ is finitely generated virtually abelian. Therefore, Submonoid Membership is undecidable in $G=L\times H$ .

Since $H$ is finitely generated virtually abelian, it has a finite index subgroup $\mathbb{Z}^{d}\leq H$ for some $d$ . Let $\widetilde{G}\coloneqq L\times\mathbb{Z}^{d}$ , so the index $[G\colon\widetilde{G}]=[H\colon\mathbb{Z}^{d}]$ is finite. We now show that Submonoid Membership is decidable in $\widetilde{G}$ .

Note that $\widetilde{G}=L\times\mathbb{Z}^{d}=\left((\mathbb{Z}/2\mathbb{Z})\wr\mathbb{Z% }^{2}\right)\times\mathbb{Z}^{d}$ can be written as a semidirect product $\mathcal{Y}\rtimes\mathbb{Z}^{d+2}$ , where $\mathcal{Y}\coloneqq\mathbb{F}_{2}[X_{1}^{\pm},X_{2}^{\pm}]$ is considered as an $\mathbb{F}_{2}[X_{1}^{\pm},X_{2}^{\pm},X_{3}^{\pm}\ldots,X_{d+2}^{\pm}]$ -module where the elements $X_{3},\ldots,X_{d+2}$ act trivially. That is, $\mathcal{Y}=\mathbb{F}_{2}[X_{1}^{\pm},\ldots,X_{d+2}^{\pm}]/\sum_{i=3}^{d+2}% \mathbb{F}_{2}[X_{1}^{\pm},\ldots,X_{d+2}^{\pm}]\cdot(X_{i}-1)$ . So by Theorem 3.1, Submonoid Membership is decidable in $\widetilde{G}$ . $\hfill\blacktriangleleft$

Our proof of Theorem 3.1 is divided into two parts. First, in Section 4, we reduce Submonoid Membership to solving S-unit equations over modules. Then, in Section 5, we prove the following result for S-unit equations over modules.

Theorem 3.3.

Let $p$ be a prime number, $\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu=(X_{1},\ldots,X_{% n})$ be a tuple of variables, $M$ be a finitely presented $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module, and let $c_{0},c_{1},\ldots,c_{m}\in M$ . Then, the set of solutions $(\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{m})\in\left(\mathbb{Z}^{n}\right)^{m}$ for the equation

\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{z}_{% 1}}\cdot c_{1}+\cdots+\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1% .5mu^{\boldsymbol{z}_{m}}\cdot c_{m}=c_{0}

(4)

is an effectively $p$ -automatic subset of $\left(\mathbb{Z}^{n}\right)^{m}\cong\mathbb{Z}^{nm}$ .

During the reduction in Section 4, we go through an intermediate step involving the Knapsack Problem in groups. In particular, we obtain the following intermediate result that is of independent interest:

Theorem 3.4.

Let $p$ be a prime number, $\mathcal{Y}$ be a finitely presented $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module and $G=\mathcal{Y}\rtimes\mathbb{Z}^{n}$ . Let $h_{1},\ldots,h_{m},g$ be elements of $G$ , then the solution set $(n_{1},\ldots,n_{m})\in\mathbb{Z}^{m}$ of

h_{1}^{n_{1}}h_{2}^{n_{2}}\cdots h_{m}^{n_{m}}=g

(5)

is an effectively $p$ -automatic subset of $\mathbb{Z}^{m}$ .

4 From Submonoid Membership to S-unit equation

In this section we reduce the problem of Submonoid Membership in $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ to solving S-unit equations over $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -modules. The reduction is done in three steps. In Step 1, we reduce Submonoid Membership in $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ to deciding membership in a product of conjugate groups (Proposition 4.1). In Step 2, we reduce membership in a product of conjugate groups to solving the Knapsack Problem in another semidirect product $\mathcal{Y}^{\prime}\rtimes\mathbb{Z}^{n^{\prime}}$ (Proposition 4.4). In Step 3, we show that the solution set of the Knapsack Problem is effectively $p$ -automatic (Theorem 3.4), assuming a theorem on S-unit equations (Theorem 3.3).

Recall that the rank of an abelian group $A$ is defined as smallest cardinality of a generating set for $A$ . If $A\leq\mathbb{Z}^{n}$ , then $A$ is a lattice in $\mathbb{Z}^{n}$ , the rank of $A$ is the dimension of this lattice.

Step 1: from Submonoid Membership to Group Product Membership

Given $q\in G$ and a subgroup $H\leq G$ , define the conjugate subgroup $\mathchoice{\mathop{}\kern 4.41634pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt]% [l]{\mathmakebox[r]{q}}}}{\mathop{}\kern 4.41634pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q}}}}{\mathop{}\kern 6.58748pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q}}}}{\mathop{}\kern 7.616% 4pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q}}}}H% \coloneqq\{qhq^{-1}\mid h\in H\}$ . For $q_{1},q_{2},\ldots,q_{k}\in G$ , denote the set

\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt]% [l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^% {\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H\coloneqq\{h_{1}h_{2}\cdots h_{k}\mid h_{1}\in% \mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt]% [l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^% {\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H,\ldots,h_{k}\in\mathchoice{\mathop{}\kern 8.7879pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 11.98796pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}H\}.

(6)

Note that $\mathchoice{\mathop{}\kern 4.41634pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt]% [l]{\mathmakebox[r]{q}}}}{\mathop{}\kern 4.41634pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q}}}}{\mathop{}\kern 6.58748pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q}}}}{\mathop{}\kern 7.616% 4pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q}}}}H$ is always a group, but the product $\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt]% [l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^% {\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H$ is in general not a group. Our first step is the following reduction from Submonoid Membership to the membership problem in sets of the form (6), originally due to Shafrir. We give a proof here for the sake of completeness. Recall that the projection $\pi\colon G=\mathcal{Y}\rtimes\mathbb{Z}^{n}\rightarrow\mathbb{Z}^{n}$ is surjective and its kernel is $\mathcal{Y}$ . A group $A$ is called torsion if for all $a\in A$ , there exists $t\geq 1$ such that $a^{t}$ is the neutral element. In particular, an $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module $\mathcal{Y}$ considered as an abelian group is torsion, because $py=0$ for all $y\in\mathcal{Y}$ .

Proposition 4.1 ([34, Theorem 4.3.3]).

Let G be a finitely generated group and $\pi\colon G\rightarrow\mathbb{Z}^{n}$ be a surjective homomorphism with $\ker(\pi)$ being a torsion group. Submonoid Membership in $G$ can be reduced to the following membership problem:

Input: elements $g,q_{1},\ldots,q_{k}\in G$ and finitely many generators of a subgroup $H\leq G$ .

Question: whether $g\in\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[% 0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{% H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H$ ?

Proof.

For a subset $T\subseteq G$ , denote by $\langle{T}\rangle$ the submonoid generated by $T$ : this is the set of elements of the form $g_{1}g_{2}\dots g_{s}$ where $s\geq 0$ and $g_{i}\in T$ for $1\leq i\leq s$ .

Let $g_{1},g_{2},\ldots,g_{m},g\in G$ , and suppose we want to decide whether $g\in\langle{g_{1},g_{2},\ldots,g_{m}}\rangle$ . Consider the elements $\pi(g_{1}),\ldots,\pi(g_{m}),\pi(g)\in\mathbb{Z}^{n}\subset\mathbb{R}^{n}$ , let $\mathcal{C}\subseteq\mathbb{R}^{n}$ be the $\mathbb{R}_{\geq 0}$ -cone generated by $\pi(g_{1}),\pi(g_{2}),\ldots,\pi(g_{m})$ , and let $\mathcal{C}_{0}$ be the maximal $\mathbb{R}$ -subspace of $\mathcal{C}$ . In particular, there exists $v\in\mathbb{R}^{n}$ , such that $v^{\top}\cdot w=0$ for all $w\in\mathcal{C}_{0}$ , and $v^{\top}\cdot w>0$ for all $w\in\mathcal{C}\setminus\mathcal{C}_{0}$ (if $\mathcal{C}_{0}=\mathcal{C}$ then we can take $v=\boldsymbol{0}$ ). Without loss of generality suppose $\pi(g_{1}),\ldots,\pi(g_{\ell})\in\mathcal{C}_{0}$ and $\pi(g_{\ell+1}),\ldots,\pi(g_{m})\in\mathcal{C}\setminus\mathcal{C}_{0}$ , for some $1\leq\ell\leq m$ .

If $g\in\langle{g_{1},g_{2},\ldots,g_{m}}\rangle$ , then we can write $g$ as a word $g_{i_{1}}g_{i_{2}}\cdots g_{i_{s}}$ over $\{g_{1},\ldots,g_{m}\}$ . In this case, $\pi(g)=\pi(g_{i_{1}})+\pi(g_{i_{2}})+\cdots+\pi(g_{i_{s}})$ , so we must have $v^{\top}\cdot\pi(g)\geq 0$ , and the elements $g_{\ell+1},\ldots,g_{m}$ can only be used a bounded number of times (in fact, bounded by $B\coloneqq v^{\top}\cdot\pi(g)/\min\left\{v^{\top}\cdot\pi(g_{\ell+1}),\ldots,% v^{\top}\cdot\pi(g_{m})\right\}$ ). Therefore, it suffices to check, for each possible choice of $g_{j_{1}},\ldots,g_{j_{b}}\in\{g_{\ell+1},\ldots,g_{m}\},\;b\leq B$ , whether $g$ can be written as $h_{1}g_{j_{1}}h_{2}g_{j_{2}}h_{3}\cdots g_{j_{b}}h_{b+1}$ for $h_{1},\ldots,h_{b+1}\in\langle{g_{1},g_{2},\ldots,g_{\ell}}\rangle$ .

Let $H\coloneqq\langle{g_{1},g_{2},\ldots,g_{\ell}}\rangle$ , we claim that the monoid $H$ is actually a group. It is easy to see that the $\mathbb{R}_{\geq 0}$ -cone generated by $\pi(g_{1}),\ldots,\pi(g_{\ell})$ is the linear space $\mathcal{C}_{0}$ . Therefore we can find positive integers $n_{1},\ldots,n_{\ell}>0$ such that $n_{1}\pi(g_{1})+\cdots+n_{\ell}\pi(g_{\ell})=\boldsymbol{0}$ . Thus, $\pi(g_{1}^{n_{1}}g_{2}^{n_{2}}\cdots g_{\ell}^{n_{\ell}})=\boldsymbol{0}$ , so $g_{1}^{n_{1}}g_{2}^{n_{2}}\cdots g_{\ell}^{n_{\ell}}\in\ker(\pi)$ . But $\ker(\pi)$ is torsion, so $\left(g_{1}^{n_{1}}g_{2}^{n_{2}}\cdots g_{\ell}^{n_{\ell}}\right)^{t}$ is the neutral element for some $t\geq 1$ . This yields $g_{1}^{-1}=g_{1}^{n_{1}-1}g_{2}^{n_{2}}\cdots g_{\ell}^{n_{\ell}}\left(g_{1}^{% n_{1}}g_{2}^{n_{2}}\cdots g_{\ell}^{n_{\ell}}\right)^{t-1}\in H$ . Similarly, $g_{2}^{-1},\ldots,g_{\ell}^{-1}\in H$ , so the monoid $H$ is actually a group.

By the discussion above, it suffices to check for finitely many instances of $g_{j_{1}},\ldots,g_{j_{b}}$ , whether $g\in Hg_{j_{1}}Hg_{j_{2}}H\cdots g_{j_{b}}H$ . But $Hg_{j_{1}}Hg_{j_{2}}H\cdots g_{j_{b}}H$ is equal to

H(g_{j_{1}}Hg_{j_{1}}^{-1})(g_{j_{1}}g_{j_{2}}Hg_{j_{2}}^{-1}g_{j_{1}}^{-1})% \cdots(g_{j_{1}}g_{j_{2}}\cdots g_{j_{b}}Hg_{j_{b}}^{-1}\cdots g_{j_{2}}^{-1}g% _{j_{1}}^{-1})g_{j_{1}}g_{j_{2}}\cdots g_{j_{b}}.

So $g\in Hg_{j_{1}}Hg_{j_{2}}H\cdots g_{j_{b}}H$ is equivalent to

gg_{j_{b}}^{-1}\cdots g_{j_{2}}^{-1}g_{j_{1}}^{-1}\in H\cdot\mathchoice{% \mathop{}\kern 12.29114pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{g_{j_{1}}}}}}{\mathop{}\kern 12.29114pt\mathopen{\vphantom{H}}% ^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{j_{1}}}}}}{\mathop{}\kern 14.43451pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{j_{1}}}}}}{% \mathop{}\kern 15.46342pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{g_{j_{1}}}}}}H\cdot\mathchoice{\mathop{}\kern 24.08228pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{j_{1}}g_{j_{2% }}}}}}{\mathop{}\kern 24.08228pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{g_{j_{1}}g_{j_{2}}}}}}{\mathop{}\kern 25.75551pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{j_{1}}g_{j_{2}}}}}}{% \mathop{}\kern 26.78442pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{g_{j_{1}}g_{j_{2}}}}}}H\cdot\ldots\cdot\mathchoice{\mathop{}% \kern 40.88725pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{% g_{j_{1}}g_{j_{2}}\cdots g_{j_{b}}}}}}{\mathop{}\kern 40.88725pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{j_{1}}g_{j_{2}}\cdots g% _{j_{b}}}}}}{\mathop{}\kern 40.59035pt\mathopen{\vphantom{H}}^{\mathmakebox[0% pt][l]{\mathmakebox[r]{g_{j_{1}}g_{j_{2}}\cdots g_{j_{b}}}}}}{\mathop{}\kern 4% 1.61926pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{j_{1% }}g_{j_{2}}\cdots g_{j_{b}}}}}}H,

which is a product of conjugate groups. This finishes the reduction from Submonoid Membership to membership in products of conjugate groups. $\hfill\blacktriangleleft$

In particular, for the case of $G=\mathcal{Y}\rtimes\mathbb{Z}^{n}$ , Proposition 4.1 is effective, meaning one can explicitly compute the elements $q_{1},\ldots,q_{k}\in G$ and the generators of $H$ .

Example 4.2 (label=exa:cont).

Let $\mathcal{Y}=\mathbb{F}_{2}[X_{1}^{\pm},X_{2}^{\pm}]$ considered as an $\mathbb{F}_{2}[X_{1}^{\pm},X_{2}^{\pm}]$ -module, so $\mathcal{Y}\rtimes\mathbb{Z}^{2}$ is the 2-dimensional lamplighter group $(\mathbb{Z}/2\mathbb{Z})\wr\mathbb{Z}^{2}$ . Let $g_{1}=\big{(}1+X_{2},\,(2,0)\big{)},g_{2}=\big{(}1,\,(-2,0)\big{)},g_{3}=\big{% (}1+X_{1},\,(0,1)\big{)}$ be the generators of a submonoid, and let $g=\big{(}X_{2}^{2},\,(4,2)\big{)}$ .

We have $\pi(g_{1})=(2,0),\;\pi(g_{2})=(-2,0),\;\pi(g_{3})=(0,1)$ , so the $\mathbb{R}_{\geq 0}$ -cone they generate is $\mathcal{C}=\{(x,y)\in\mathbb{R}^{2}\mid y\geq 0\}$ . Its maximal subspace is $\mathcal{C}_{0}=\{(x,0)\mid x\in\mathbb{R}\}$ . We have $\pi(g_{1}),\pi(g_{2})\in\mathcal{C}_{0}$ and $\pi(g_{3})\in\mathcal{C}\setminus\mathcal{C}_{0}$ .

Suppose $g=g_{i_{1}}g_{i_{2}}\cdots g_{i_{s}}$ with $i_{1},i_{2},\ldots,i_{s}\in\{1,2,3\}$ . Let $v=(0,1)$ . Since $v^{\top}\cdot\pi(g)=v^{\top}\cdot(4,2)=2$ , and $v^{\top}\cdot\pi(g_{1})=v^{\top}\cdot\pi(g_{2})=0,\;v^{\top}\cdot\pi(g_{3})=1$ , the element $g_{3}$ must appear exactly twice in the product $g_{i_{1}}g_{i_{2}}\cdots g_{i_{s}}$ . Therefore, $g$ must be of the form $w_{1}g_{3}w_{2}g_{3}w_{3}$ , where $w_{1},w_{2},w_{3}$ are words over $\{g_{1},g_{2}\}$ . Let $H$ be the monoid generated by $g_{1},g_{2}$ : this is actually a group because $(g_{1}g_{2})^{2}=(0,\boldsymbol{0})$ . The above discussion shows $g\in\langle{g_{1},g_{2},g_{3}}\rangle$ if and only if $g\in Hg_{3}Hg_{3}H$ : this is equivalent to $gg_{3}^{-2}\in H\cdot\mathchoice{\mathop{}\kern 8.55528pt\mathopen{\vphantom{H% }}^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{3}}}}}{\mathop{}\kern 8.55528pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{3}}}}}{% \mathop{}\kern 10.69865pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{g_{3}}}}}{\mathop{}\kern 11.72757pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{g_{3}}}}}H\cdot\mathchoice{\mathop{}\kern 8% .55528pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{3}^{2% }}}}}{\mathop{}\kern 8.55528pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{g_{3}^{2}}}}}{\mathop{}\kern 10.69865pt\mathopen{\vphantom{H}}% ^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{3}^{2}}}}}{\mathop{}\kern 11.72757pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{g_{3}^{2}}}}}H$ . $\lrcorner$

Remark 4.3.

If $G=(\mathbb{Z}/2\mathbb{Z})\wr\mathbb{Z}^{2}$ and $\pi(H)$ is of rank one (i.e. $\pi(H)\cong\mathbb{Z}$ ) as in Example 4.2, then membership problem in the product $\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt]% [l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^% {\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H$ can be reduced to Rational Subset Membership in the 1-dimensional lamplighter group $(\mathbb{Z}/2\mathbb{Z})\wr\mathbb{Z}$ , which is known to be decidable [28]. In fact, this is the key idea in Shafrir’s solution [34] for Submonoid Membership in 2-dimensional lamplighter groups. However, when the dimension $n$ is greater or equal to three, the rank of $\pi(H)$ may be greater or equal to two: in this case, the membership problem in $\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt]% [l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^% {\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H$ has been open and will be solved in the rest of this paper. Notably, we do not want to reduce it to Rational Subset Membership in lamplighter groups of dimension $\geq 2$ , as it is undecidable [27].

Step 2: from Group Product Membership to Knapsack Problem

The goal of this step is to reduce membership problem in the product $\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt]% [l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^% {\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H$ to a version of the Knapsack Problem in groups. Namely, we will prove:

Proposition 4.4.

Let $G=\mathcal{Y}\rtimes\mathbb{Z}^{n}$ where $\mathcal{Y}$ is a finitely presented $\mathbb{F}_{p}[X_{1}^{\pm},\ldots,X_{n}^{\pm}]$ -module. Let $g,q_{1},\ldots,q_{k}\in G$ and let $H\leq G$ be a finitely generated subgroup. Then, one can effectively find a group $G^{\prime}=\mathcal{Y}^{\prime}\rtimes\mathbb{Z}^{n^{\prime}}$ , where $\mathcal{Y}^{\prime}$ is a finitely presented $\mathbb{F}_{p}[X_{1}^{\pm},\ldots,X_{n^{\prime}}^{\pm}]$ -module, as well as elements $g^{\prime},h_{1},\ldots,h_{m}\in G^{\prime}$ , such that

g\in\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[% 0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{% H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H

if and only if there exist $z_{1},\ldots,z_{m}\in\mathbb{Z}$ satisfying

h_{1}^{z_{1}}h_{2}^{z_{2}}\cdots h_{m}^{z_{m}}=g^{\prime}.

(7)

We now proceed to prove Proposition 4.4. Recall that $\mathcal{Y}$ can be identified with the subgroup $\mathcal{Y}\times\{\boldsymbol{0}\}=\ker(\pi)$ of $G=\mathcal{Y}\rtimes\mathbb{Z}^{n}$ . First, we give the following classic result on the structure of subgroups $H\leq G$ . Note that $\pi(H)\leq\pi(G)=\mathbb{Z}^{n}$ , let $d\leq n$ be the rank of $\pi(H)$ .

Lemma 4.5 ([6, Theorem 3.3] or [35, Lemma 2]).

Let $G=\mathcal{Y}\rtimes\mathbb{Z}^{n}$ and $H\leq G$ be a finitely generated subgroup. Let $\boldsymbol{a}_{1},\ldots,\boldsymbol{a}_{d}\in\mathbb{Z}^{n}$ be a $\mathbb{Z}$ -basis of $\pi(H)$ , and choose elements $h_{1},\ldots,h_{d}\in H$ so that $\pi(h_{i})=\boldsymbol{a}_{i},i=1,\ldots,d$ . Then, the subgroup $\mathcal{Y}\cap H$ is a finitely generated $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pi(H)}]$ -module, whose finite presentation can be effectively computed. Furthermore, $H$ is generated by $h_{1},\ldots,h_{d}$ and the set $\mathcal{Y}\cap H$ .

Example 4.6 (continues=exa:cont).

As in Example 4.2, let $\mathcal{Y}=\mathbb{F}_{2}[X_{1}^{\pm},X_{2}^{\pm}]$ . Consider the subgroup $H\leq\mathcal{Y}\rtimes\mathbb{Z}^{2}$ generated by $g_{1}=\big{(}1+X_{2},\,(2,0)\big{)}$ and $g_{2}=\big{(}1,\,(-2,0)\big{)}$ . Then $\pi(H)$ is the subgroup of $\mathbb{Z}^{2}$ generated by $\boldsymbol{a}_{1}\coloneqq(2,0)$ , it has rank $d=1$ . We can choose $h_{1}\coloneqq g_{1}$ in Lemma 4.5.

The subgroup $\mathcal{Y}\cap H$ is an $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pi(H)}]=\mathbb{F}_{p}[X_{1}^{2},X_{1}^{-2}]$ -module. We have $g_{1}g_{2}=\big{(}1+X_{2}+X_{1}^{2},\boldsymbol{0}\big{)}$ . We claim that $1+X_{2}+X_{1}^{2}$ is the generator of the $\mathbb{F}_{p}[X_{1}^{2},X_{1}^{-2}]$ -module $\mathcal{Y}\cap H$ : that is, $\mathcal{Y}\cap H=\{F\cdot(1+X_{2}+X_{1}^{2})\mid F\in\mathbb{F}_{p}[X_{1}^{2}% ,X_{1}^{-2}]\}$ . Indeed, recall the formula $(f,\boldsymbol{a})(y,\boldsymbol{0})(f,\boldsymbol{a})^{-1}=(\mkern 1.5mu% \overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}}\cdot y,% \boldsymbol{0})$ . For each $m\in\mathbb{Z}$ , we have $g_{1}^{m}(g_{1}g_{2})g_{1}^{-m}=g_{1}^{m}\big{(}1+X_{2}+X_{1}^{2},\boldsymbol{% 0}\big{)}g_{1}^{-m}=\big{(}X_{1}^{2m}\cdot(1+X_{2}+X_{1}^{2}),\boldsymbol{0}% \big{)}$ . So $X_{1}^{2m}\cdot(1+X_{2}+X_{1}^{2})\in\mathcal{Y}\cap H$ for all $m\in\mathbb{Z}$ . Consequently, $F\cdot(1+X_{2}+X_{1}^{2})\in\mathcal{Y}\cap H$ for all $F\in\mathbb{F}_{p}[X_{1}^{2},X_{1}^{-2}]$ . It is not difficult to show that $\{F\cdot(1+X_{2}+X_{1}^{2})\mid F\in\mathbb{F}_{p}[X_{1}^{2},X_{1}^{-2}]\}$ is indeed all the elements in $\mathcal{Y}\cap H$ , but we will omit the details. Note that $\mathcal{Y}\cap H$ is finitely generated as an $\mathbb{F}_{p}[X_{1}^{2},X_{1}^{-2}]$ -module but not finitely generated as an abelian group.

Finally, for any element $h=(f,2z)\in H$ , we have $\pi(h_{1}^{-z}h)=\boldsymbol{0}$ , so $(y,\boldsymbol{0})\coloneqq h_{1}^{-z}h\in\mathcal{Y}\cap H$ . Consequently, $h$ can actually be written in a “canonical form” $h_{1}^{z}\,(y,\boldsymbol{0})$ , where $z\in\mathbb{Z}$ and $y\in\mathcal{Y}\cap H$ . Such canonical forms will be extensively used below. $\lrcorner$

Define

\mathcal{Y}_{i}\coloneqq\mathcal{Y}\cap\left(\mathchoice{\mathop{}\kern 7.5841% 8pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{% \mathop{}\kern 7.58418pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 9.75533pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 10.78424pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}H\right% ),\quad i=1,\ldots,k.

Note that for any $q\in G$ , we have $\pi(\mathchoice{\mathop{}\kern 4.41634pt\mathopen{\vphantom{H}}^{\mathmakebox[% 0pt][l]{\mathmakebox[r]{q}}}}{\mathop{}\kern 4.41634pt\mathopen{\vphantom{H}}^% {\mathmakebox[0pt][l]{\mathmakebox[r]{q}}}}{\mathop{}\kern 6.58748pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q}}}}{\mathop{}\kern 7.616% 4pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q}}}}H)=\pi(H)$ because $\mathbb{Z}^{n}$ is abelian. Therefore $\pi(\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[% 0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{% H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H)=\cdots=\pi(\mathchoice{\mathop{}\kern 8.7879pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 11.98796pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}H)=\pi(H)$ . So by Lemma 4.5, all the $\mathcal{Y}_{i}$ ’s are finitely generated $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pi(H)}]$ -modules. Let $\boldsymbol{a}_{1},\ldots,\boldsymbol{a}_{d}\in\mathbb{Z}^{n}$ be a $\mathbb{Z}$ -basis of $\pi(H)$ . For each $1\leq i\leq k$ , choose elements $h_{i,1},\ldots,h_{i,d}\in\mathchoice{\mathop{}\kern 7.58418pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 7% .58418pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}% }{\mathop{}\kern 9.75533pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 10.78424pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}H$ so that $\pi(h_{i,1})=\boldsymbol{a}_{1},\ldots,\pi(h_{i,d})=\boldsymbol{a}_{d}$ . Then, $\mathchoice{\mathop{}\kern 7.58418pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt]% [l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 7.58418pt\mathopen{\vphantom{H}}^% {\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 9.75533pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{% \mathop{}\kern 10.78424pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{i}}}}}H$ is generated by $h_{i,1},\ldots,h_{i,d}$ and $\mathcal{Y}_{i}$ .

Fix any $i$ . Since $\boldsymbol{a}_{1},\ldots,\boldsymbol{a}_{d}\in\mathbb{Z}^{n}$ form a $\mathbb{Z}$ -basis for $\pi(\mathchoice{\mathop{}\kern 7.58418pt\mathopen{\vphantom{H}}^{\mathmakebox[% 0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 7.58418pt\mathopen{\vphantom{% H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 9.75533pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{% \mathop{}\kern 10.78424pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{i}}}}}H)$ , for each element $h\in\mathchoice{\mathop{}\kern 7.58418pt\mathopen{\vphantom{H}}^{\mathmakebox[% 0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 7.58418pt\mathopen{\vphantom{% H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 9.75533pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{% \mathop{}\kern 10.78424pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{i}}}}}H$ we can find integers $z_{1},\ldots,z_{d}$ such that

\pi(h)=z_{1}\boldsymbol{a}_{1}+z_{2}\boldsymbol{a}_{2}+\cdots+z_{d}\boldsymbol% {a}_{d}=z_{1}\pi(h_{i,1})+z_{2}\pi(h_{i,2})+\cdots+z_{d}\pi(h_{i,d}).

This shows $\pi(h_{i,d}^{-z_{i,d}}\cdots h_{i,2}^{-z_{i,2}}h_{i,1}^{-z_{i,1}}h)=% \boldsymbol{0}$ , so $h_{i,d}^{-z_{i,d}}\cdots h_{i,2}^{-z_{i,2}}h_{i,1}^{-z_{i,1}}h\in\ker(\pi)\cap% \mathchoice{\mathop{}\kern 7.58418pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt]% [l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 7.58418pt\mathopen{\vphantom{H}}^% {\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 9.75533pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{% \mathop{}\kern 10.78424pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{i}}}}}H=\mathcal{Y}_{i}$ . Consequently, $h$ is equal to $h_{i,1}^{z_{i,1}}h_{i,2}^{z_{i,2}}\cdots h_{i,d}^{z_{i,d}}(y_{i},\boldsymbol{0})$ for some $y_{i}\in\mathcal{Y}_{i}$ .

The form of this product of powers gives us the motivation to reduce membership in group products to the Knapsack Problem. Denote

\widetilde{\mathcal{Y}}\coloneqq\mathcal{Y}_{1}+\cdots+\mathcal{Y}_{k}.

Again we identify $\widetilde{\mathcal{Y}}$ with the subgroup $\widetilde{\mathcal{Y}}\times\{\boldsymbol{0}\}$ of $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ . We show the following:

Lemma 4.7.

We have $g\in\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[% 0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{% H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H$ , if and only if there exist integers $z_{1,1},\ldots,z_{1,d}$ , $\ldots$ , $z_{k,1},\ldots,z_{k,d}$ , such that

\left(h_{1,1}^{z_{1,1}}h_{1,2}^{z_{1,2}}\cdots h_{1,d}^{z_{1,d}}\right)\cdots% \left(h_{k,1}^{z_{k,1}}h_{k,2}^{z_{k,2}}\cdots h_{k,d}^{z_{k,d}}\right)\cdot g% ^{-1}\in\widetilde{\mathcal{Y}}.

(8)

Proof.

For the “only if” part, suppose $g\in\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[% 0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{% H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H$ , and write $g=h_{1}h_{2}\cdots h_{k}$ with $h_{i}\in\mathchoice{\mathop{}\kern 7.58418pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 7.58418pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{% \mathop{}\kern 9.75533pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 10.78424pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}H$ for each $1\leq i\leq k$ . As shown above, we can write

h_{i}=h_{i,1}^{z_{i,1}}h_{i,2}^{z_{i,2}}\cdots h_{i,d}^{z_{i,d}}(y_{i},% \boldsymbol{0})

for some $y_{i}\in\mathcal{Y}_{i},\,i=1,\ldots,k$ . Denote $y_{i}^{\prime}\coloneqq\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1% .5mu^{\sum_{j=1}^{d}z_{1,j}\boldsymbol{a}_{j}+\sum_{j=1}^{d}z_{2,j}\boldsymbol% {a}_{j}+\cdots+\sum_{j=1}^{d}z_{i,j}\boldsymbol{a}_{j}}\cdot y_{i}$ , then $y_{i}^{\prime}\in\mathcal{Y}_{i}$ . Recall the formula $(f,\boldsymbol{a})(y,\boldsymbol{0})(f,\boldsymbol{a})^{-1}=(\mkern 1.5mu% \overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}}\cdot y,% \boldsymbol{0})$ , that is $(f,\boldsymbol{a})(y_{i},\boldsymbol{0})=(\mkern 1.5mu\overline{\mkern-1.5muX% \mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}}\cdot y_{i},\boldsymbol{0})(f,% \boldsymbol{a})$ . Therefore,

	$\displaystyle g$	$\displaystyle=h_{1}h_{2}\cdots h_{k}=\left(h_{1,1}^{z_{1,1}}h_{1,2}^{z_{1,2}}% \cdots h_{1,d}^{z_{1,d}}\right)(y_{1},\boldsymbol{0})\cdots\left(h_{k,1}^{z_{k% ,1}}h_{k,2}^{z_{k,2}}\cdots h_{k,d}^{z_{k,d}}\right)(y_{k},\boldsymbol{0})$
		$\displaystyle=(y_{k}^{\prime},\boldsymbol{0})\cdots(y_{2}^{\prime},\boldsymbol% {0})(y_{1}^{\prime},\boldsymbol{0})\left(h_{1,1}^{z_{1,1}}h_{1,2}^{z_{1,2}}% \cdots h_{1,d}^{z_{1,d}}\right)\cdots\left(h_{k,1}^{z_{k,1}}h_{k,2}^{z_{k,2}}% \cdots h_{k,d}^{z_{k,d}}\right)$

Therefore

\left(h_{1,1}^{z_{1,1}}h_{1,2}^{z_{1,2}}\cdots h_{1,d}^{z_{1,d}}\right)\cdots% \left(h_{k,1}^{z_{k,1}}h_{k,2}^{z_{k,2}}\cdots h_{k,d}^{z_{k,d}}\right)\cdot g% ^{-1}=(-y_{k}^{\prime}-\cdots-y_{2}^{\prime}-y_{1}^{\prime},\boldsymbol{0})\in% \mathcal{Y}_{1}+\cdots+\mathcal{Y}_{k}=\widetilde{\mathcal{Y}}.

For the “if” part, let $z_{1,1},\ldots,z_{1,d}$ , $\ldots$ , $z_{k,1},\ldots,z_{k,d}$ be integers that satisfy Equation (8). Since $\widetilde{\mathcal{Y}}\coloneqq\mathcal{Y}_{1}+\cdots+\mathcal{Y}_{k}$ , there exist $y_{1}\in\mathcal{Y}_{1},\ldots,y_{k}\in\mathcal{Y}_{k}$ , such that

\left(h_{1,1}^{z_{1,1}}h_{1,2}^{z_{1,2}}\cdots h_{1,d}^{z_{1,d}}\right)\cdots% \left(h_{k,1}^{z_{k,1}}h_{k,2}^{z_{k,2}}\cdots h_{k,d}^{z_{k,d}}\right)\cdot g% ^{-1}=(y_{1}+y_{2}+\cdots+y_{k},\boldsymbol{0}).

Denote $y_{i}^{\prime}\coloneqq-\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1% .5mu^{-\sum_{j=1}^{d}z_{1,j}\boldsymbol{a}_{j}-\sum_{j=1}^{d}z_{2,j}% \boldsymbol{a}_{j}-\cdots-\sum_{j=1}^{d}z_{i,j}\boldsymbol{a}_{j}}\cdot y_{i}$ , then $y_{i}^{\prime}\in\mathcal{Y}_{i}$ . We have

	$\displaystyle g$	$\displaystyle=(-y_{1}-y_{2}-\cdots-y_{k},\boldsymbol{0})\left(h_{1,1}^{z_{1,1}% }h_{1,2}^{z_{1,2}}\cdots h_{1,d}^{z_{1,d}}\right)\cdots\left(h_{k,1}^{z_{k,1}}% h_{k,2}^{z_{k,2}}\cdots h_{k,d}^{z_{k,d}}\right)$
		$\displaystyle=(-y_{k},\boldsymbol{0})\cdots(-y_{2},\boldsymbol{0})(-y_{1},% \boldsymbol{0})\left(h_{1,1}^{z_{1,1}}h_{1,2}^{z_{1,2}}\cdots h_{1,d}^{z_{1,d}% }\right)\cdots\left(h_{k,1}^{z_{k,1}}h_{k,2}^{z_{k,2}}\cdots h_{k,d}^{z_{k,d}}\right)$
		$\displaystyle=\left(h_{1,1}^{z_{1,1}}h_{1,2}^{z_{1,2}}\cdots h_{1,d}^{z_{1,d}}% \right)(y_{1}^{\prime},\boldsymbol{0})\cdots\left(h_{k,1}^{z_{k,1}}h_{k,2}^{z_% {k,2}}\cdots h_{k,d}^{z_{k,d}}\right)(y_{k}^{\prime},\boldsymbol{0}).$

For each $i$ , we have $(y_{i}^{\prime},\boldsymbol{0})\in\mathcal{Y}_{i}\leq\mathchoice{\mathop{}% \kern 7.58418pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q% _{i}}}}}{\mathop{}\kern 7.58418pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]% {\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 9.75533pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 10.78424pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}H$ , so $\left(h_{i,1}^{z_{i,1}}h_{i,2}^{z_{i,2}}\cdots h_{i,d}^{z_{i,d}}\right)(y_{i}^% {\prime},\boldsymbol{0})\in\mathchoice{\mathop{}\kern 7.58418pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 7% .58418pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}% }{\mathop{}\kern 9.75533pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{i}}}}}{\mathop{}\kern 10.78424pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{i}}}}}H$ . Therefore $g\in\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[% 0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{% H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H$ . $\hfill\blacktriangleleft$

Proposition 4.4 then follows from Lemma 4.7:

Proof of Proposition 4.4.

By Lemma 4.7, we have $g\in\mathchoice{\mathop{}\kern 8.31917pt\mathopen{\vphantom{H}}^{\mathmakebox[% 0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 8.31917pt\mathopen{\vphantom{% H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{\mathop{}\kern 10.49031pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{1}}}}}{% \mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{1}}}}}H\cdot\mathchoice{\mathop{}\kern 8.31917pt\mathopen{% \vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 8% .31917pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}% }{\mathop{}\kern 10.49031pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{2}}}}}{\mathop{}\kern 11.51923pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{2}}}}}H\cdot\ldots\cdot\mathchoice{% \mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 8.7879pt\mathopen{\vphantom{H}}^{% \mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{\mathop{}\kern 10.95905pt% \mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{\mathmakebox[r]{q_{k}}}}}{% \mathop{}\kern 11.98796pt\mathopen{\vphantom{H}}^{\mathmakebox[0pt][l]{% \mathmakebox[r]{q_{k}}}}}H$ if and only if Equation (8) has integer solutions. Write $h_{i,j}$ as $(f_{i,j},\boldsymbol{a}_{j})$ for $i=1,\ldots,k;\,j=1,\ldots,d$ , and write $g$ as $(f_{0},\boldsymbol{a}_{0})$ . Let $\mathcal{F}$ denote the $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pi(H)}]$ -submodule of $\mathcal{Y}$ generated by $f_{0}$ and $f_{i,j},\,i=1,\ldots,k;\,j=1,\ldots,d$ . Notably, $\mathcal{F}$ contains $\mathcal{Y}_{i},\,i=1,\ldots,k$ . A finite presentation of $\mathcal{F}$ can be computed (see Lemma 2.2). The group generated by $g$ and all the $h_{i,j}$ ’s is contained in the subgroup $\mathcal{F}\rtimes\pi(H)$ of $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ . Hence, Equation (8) is equivalent to the following equation in $(\mathcal{F}/\widetilde{\mathcal{Y}})\rtimes\pi(H)$ :

\left(h_{1,1}^{z_{1,1}}h_{1,2}^{z_{1,2}}\cdots h_{1,d}^{z_{1,d}}\right)\cdots% \left(h_{k,1}^{z_{k,1}}h_{k,2}^{z_{k,2}}\cdots h_{k,d}^{z_{k,d}}\right)=g.

(9)

Choose the new variables $X_{1}^{\prime}\coloneqq\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1% .5mu^{\boldsymbol{a}_{1}},\ldots,X_{d}^{\prime}\coloneqq\mkern 1.5mu\overline{% \mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}_{d}}$ . Then the ring $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pi(H)}]$ can be written as the polynomial ring $\mathbb{F}_{p}[{X_{1}^{\prime}}^{\pm},\ldots,{X_{d}^{\prime}}^{\pm}]$ , and $\mathcal{Y}^{\prime}\coloneqq\mathcal{F}/\widetilde{\mathcal{Y}}$ is now a finitely presented $\mathbb{F}_{p}[{X_{1}^{\prime}}^{\pm},\ldots,{X_{d}^{\prime}}^{\pm}]$ -module. We conclude by letting $G^{\prime}\coloneqq\mathcal{Y}^{\prime}\rtimes\mathbb{Z}^{d}=(\mathcal{F}/% \widetilde{\mathcal{Y}})\rtimes\pi(H)$ , and observing that Equation (9) is a Knapsack equation of the form (7). $\hfill\blacktriangleleft$

Remark 4.8.

Note that even if we only considered the lamplighter group $G=(\mathbb{Z}/p\mathbb{Z})\wr\mathbb{Z}^{n}$ by supposing $\mathcal{Y}=\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}% \mkern 1.5mu]$ , we would inevitably introduce the quotient by $\widetilde{\mathcal{Y}}$ during our reduction from Submonoid Membership to the Knapsack Problem. Therefore, it is reasonable to directly consider Submonoid Membership in the more general case of semidirect product $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ with finitely presented $\mathcal{Y}$ , instead of only the special case of lamplighter groups $(\mathbb{Z}/p\mathbb{Z})\wr\mathbb{Z}^{n}$ . In other words, it does not appear that the special case of lamplighter groups admits a more direct solution.

Step 3: from Knapsack Problem to S-unit equation

The goal of this step is to solve the Knapsack Problem in groups of the form $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ . Namely, assuming a theorem on S-unit equations (Theorem 3.3), we will prove the following result:

See 3.4

Before we proceed to the formal proof, let us show another example to illustrate the ideas.

Example 4.9.

Let $p=2$ , $n=2$ . Let $\mathcal{Y}=\mathbb{F}_{2}[X_{1}^{\pm},X_{2}^{\pm}]/(X_{1}+X_{2}+1)$ , that is, the quotient of $\mathbb{F}_{2}[X_{1}^{\pm},X_{2}^{\pm}]$ by the submodule $\mathbb{F}_{2}[X_{1}^{\pm},X_{2}^{\pm}]\cdot(X_{1}+X_{2}+1)$ . Let $h_{1}=\big{(}0,(1,0)\big{)},h_{2}=\big{(}1-X_{2},(0,1)\big{)},h_{3}=\big{(}0,(% 1,0)\big{)},h_{4}=\big{(}0,(0,1)\big{)},g=\big{(}1,(0,0)\big{)}$ be elements of $\mathcal{Y}\rtimes\mathbb{Z}^{2}$ . We will to show that the solution set of the equation

h_{1}^{n_{1}}h_{2}^{n_{2}}h_{3}^{n_{3}}h_{4}^{n_{4}}=g

(10)

is 2-automatic.

By direct computation, we have $(f,\boldsymbol{a})^{z}=\big{(}(1+\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5% mu}\mkern 1.5mu^{\boldsymbol{a}}+\cdots+\mkern 1.5mu\overline{\mkern-1.5muX% \mkern-1.5mu}\mkern 1.5mu^{(z-1)\boldsymbol{a}})\cdot f,z\boldsymbol{a}\big{)}$ for $z>0$ and $(f,\boldsymbol{a})^{z}=\big{(}(-\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5% mu}\mkern 1.5mu^{z\boldsymbol{a}}-\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.% 5mu}\mkern 1.5mu^{(z+1)\boldsymbol{a}}-\cdots-\mkern 1.5mu\overline{\mkern-1.5% muX\mkern-1.5mu}\mkern 1.5mu^{-\boldsymbol{a}})\cdot f,z\boldsymbol{a}\big{)}$ for $z<0$ . In either case (and for $z=0$ ), we have

(f,\boldsymbol{a})^{z}=\left(\frac{1-\mkern 1.5mu\overline{\mkern-1.5muX\mkern% -1.5mu}\mkern 1.5mu^{z\boldsymbol{a}}}{1-\mkern 1.5mu\overline{\mkern-1.5muX% \mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}}}\cdot f,\;z\boldsymbol{a}\right).

Hence,

	$\displaystyle h_{1}^{n_{1}}h_{2}^{n_{2}}h_{3}^{n_{3}}h_{4}^{n_{4}}$	$\displaystyle=\big{(}0,(1,0)\big{)}^{n_{1}}\big{(}1-X_{2},(0,1)\big{)}^{n_{2}}% \big{(}0,(1,0)\big{)}^{n_{3}}\big{(}0,(0,1)\big{)}^{n_{4}}$
		$\displaystyle=\big{(}0,(n_{1},0)\big{)}\left(\frac{1-X_{2}^{n_{2}}}{1-X_{2}}% \cdot(1-X_{2}),(0,n_{2})\right)\big{(}0,(n_{3},0)\big{)}\big{(}0,(0,n_{4})\big% {)}$
		$\displaystyle=\big{(}X_{1}^{n_{1}}(1-X_{2}^{n_{2}}),(n_{1}+n_{3},n_{2}+n_{4})% \big{)}$

Since $g=\big{(}1,(0,0)\big{)}$ , we have $h_{1}^{n_{1}}h_{2}^{n_{2}}h_{3}^{n_{3}}h_{4}^{n_{4}}=g$ if and only if

X_{1}^{n_{1}}(1-X_{2}^{n_{2}})=1,\;n_{1}+n_{3}=0,\;n_{2}+n_{4}=0.

We now show that the solution set $(n_{1},n_{2},n_{3},n_{4})\in\mathbb{Z}^{4}$ is 2-automatic. Since $n_{3}=-n_{1}$ and $n_{4}=-n_{2}$ , it suffices to show that the solution set $(n_{1},n_{2})\in\mathbb{Z}^{2}$ of $X_{1}^{n_{1}}(1-X_{2}^{n_{2}})=1$ is 2-automatic.

The equation $X_{1}^{n_{1}}(1-X_{2}^{n_{2}})=1$ can be rewritten as

X_{1}^{-n_{1}}+X_{2}^{n_{2}}=1

(11)

Therefore, we have reduced the Knapsack equation (10) to the S-unit equation (11) over the module $\mathbb{F}_{2}[X_{1}^{\pm},X_{2}^{\pm}]/(X_{1}+X_{2}+1)$ . The 2-automaticity of its solution set can already be deduced from Theorem 3.3 (see below). However, we now prove “by hand” that the solution set of the S-unit Equation (11) is 2-automatic, in order to give an idea of how 2-automaticity can arise from such equations.

Since we work in the module $\mathbb{F}_{2}[X_{1}^{\pm},X_{2}^{\pm}]/(X_{1}+X_{2}+1)$ , we have $X_{2}=-(X_{1}+1)=X_{1}+1$ (we are in characteristic 2). Therefore, Equation (11) is equivalent to $(X_{1}+1)^{n_{2}}=X_{1}^{-n_{1}}+1$ . We claim that its solution set is $(n_{1},n_{2})\in\{(-2^{k},2^{k})\mid k\in\mathbb{N}\}$ .

Indeed, since $X_{1}^{-n_{1}}+1\in\mathbb{F}_{2}[X_{1}^{\pm}]$ , we must have $n_{2}\geq 0$ so that $(X_{1}+1)^{n_{2}}$ is also in $\mathbb{F}_{2}[X_{1}^{\pm}]$ . Considering the degree of both sides we have $n_{1}=-n_{2}$ . Now, in order for $(X_{1}+1)^{n_{2}}=X_{1}^{n_{2}}+1$ to hold, $n_{2}$ must be a power of 2. Indeed, $n_{2}=0$ is not a solution, so suppose $n_{2}\geq 1$ and write $n_{2}=2^{k}+a$ with $0\leq a<2^{k}$ . By “freshman’s dream”, we have

(X_{1}+1)^{n_{2}}=(X_{1}+1)^{2^{k}}(X_{1}+1)^{a}=(X_{1}^{2^{k}}+1)(X_{1}+1)^{a% }=X_{1}^{2^{k}}(X_{1}+1)^{a}+(X_{1}+1)^{a}.

Every monomial appearing in $X_{1}^{2^{k}}(X_{1}+1)^{a}$ has degree larger than every monomial appearing $(X_{1}+1)^{a}$ . But $(X_{1}+1)^{n_{2}}=X_{1}^{n_{2}}+1$ has only two monomials. So both $X_{1}^{2^{k}}(X_{1}+1)^{a}$ and $(X_{1}+1)^{a}$ must be monomials, meaning $a=0$ . Therefore $n_{2}=2^{k}$ , and $n_{1}=-n_{2}=-2^{k}$ .

In conclusion, the solution set of Equation (10) is $(n_{1},n_{2},n_{3},n_{4})\in\{(-2^{k},2^{k},2^{k},-2^{k})\mid k\in\mathbb{N}\}$ , which is 2-automatic. Note that this set is not semilinear, so the situation in semidirect products is more complicated than in the wreath product of two abelian groups [18]. $\lrcorner$

Example 4.9 shows that there will be two parts in the proof of Theorem 3.4: a (fairly elementary) first part reducing Knapsack Equations to S-unit equations, then a (rather non-trivial) second part showing that S-unit equations have $p$ -automatic solution sets. The second part is summarized as Theorem 3.3 below, which we will prove in Section 5. In the rest of this section, we will focus on the first part of the proof, assuming Theorem 3.3 as a blackbox.

See 3.3

Proof of Theorem 3.4 (assuming Theorem 3.3).

Write $h_{i}=(f_{i},\boldsymbol{a}_{i}),\,i=1,\ldots,m$ , and $g=(f,\boldsymbol{b})$ .

Case 1: none of the $\boldsymbol{a}_{i}$ is $\boldsymbol{0}$

(in fact this case already suffices to solve the Equation (5) arising from the previous step). We have

h_{i}^{n_{i}}=(f_{i},\boldsymbol{a}_{i})^{n_{i}}=\left(\frac{1-\mkern 1.5mu% \overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{n_{i}\boldsymbol{a}_{i}}}{1-% \mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}_{% i}}}\cdot f_{i},\;n_{i}\boldsymbol{a}_{i}\right).

Computing their product gives

h_{1}^{n_{1}}h_{2}^{n_{2}}\cdots h_{m}^{n_{m}}=\left(\sum_{i=1}^{m}\mkern 1.5% mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{n_{1}\boldsymbol{a}_{1}+% \cdots+n_{i-1}\boldsymbol{a}_{i-1}}\cdot\frac{1-\mkern 1.5mu\overline{\mkern-1% .5muX\mkern-1.5mu}\mkern 1.5mu^{n_{i}\boldsymbol{a}_{i}}}{1-\mkern 1.5mu% \overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}_{i}}}\cdot f_% {i},\;n_{1}\boldsymbol{a}_{1}+\cdots+n_{m}\boldsymbol{a}_{m}\right).

Therefore, writing $\boldsymbol{z}_{i}\coloneqq n_{1}\boldsymbol{a}_{1}+\cdots+n_{i}\boldsymbol{a}% _{i}$ for $i=1,\ldots,m$ , and $\boldsymbol{z}_{0}\coloneqq\boldsymbol{0}$ , we have $h_{1}^{n_{1}}h_{2}^{n_{2}}\cdots h_{m}^{n_{m}}=g$ if and only if

	$\displaystyle\sum_{i=1}^{m}\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}% \mkern 1.5mu^{\boldsymbol{z}_{i-1}}\cdot\frac{1-\mkern 1.5mu\overline{\mkern-1% .5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{z}_{i}-\boldsymbol{z}_{i-1}}}{1-% \mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}_{% i}}}\cdot f_{i}$	$\displaystyle=f,$		(12)
	$\displaystyle\text{and}\quad\boldsymbol{z}_{m}$	$\displaystyle=\boldsymbol{b}.$		(13)

Write $\mathcal{Y}=\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}% \mkern 1.5mu^{\pm}]^{d}/N$ for some $N\subseteq\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}% \mkern 1.5mu^{\pm}]^{d}$ . Considering $f_{1},\ldots,f_{m},f,$ as elements in $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]^{d}$ , Equation (12) is equivalent to

\sum_{i=1}^{m}(\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \boldsymbol{z}_{i-1}}-\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1% .5mu^{\boldsymbol{z}_{i}})\prod_{j\neq i}(1-\mkern 1.5mu\overline{\mkern-1.5% muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}_{j}})\cdot f_{i}-\prod_{i=1}^{m}(% 1-\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}% _{i}})\cdot f\in\prod_{i=1}^{m}(1-\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.% 5mu}\mkern 1.5mu^{\boldsymbol{a}_{i}})\cdot N.

Letting $c_{0}\coloneqq-\prod_{j\neq 1}(1-\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5% mu}\mkern 1.5mu^{\boldsymbol{a}_{j}})\cdot f_{1}+\prod_{i=1}^{m}(1-\mkern 1.5% mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}_{i}})\cdot f$ , $\;c_{i}\coloneqq\prod_{j\neq(i+1)}(1-\mkern 1.5mu\overline{\mkern-1.5muX\mkern% -1.5mu}\mkern 1.5mu^{\boldsymbol{a}_{j}})\cdot f_{i+1}-\prod_{j\neq i}(1-% \mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}_{% j}})\cdot f_{i},\;i=1,\ldots,m-1$ and $c_{m}\coloneqq-\prod_{j\neq m}(1-\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5% mu}\mkern 1.5mu^{\boldsymbol{a}_{j}})\cdot f_{m}$ , the equation above is equivalent to the following equation in $M\coloneqq\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}% \mkern 1.5mu^{\pm}]^{d}/\prod_{i=1}^{m}(1-\mkern 1.5mu\overline{\mkern-1.5muX% \mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{a}_{i}})N$ :

\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{z}_{% 1}}\cdot c_{1}+\cdots+\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1% .5mu^{\boldsymbol{z}_{m}}\cdot c_{m}=c_{0}.

(14)

Therefore, we have $h_{1}^{n_{1}}h_{2}^{n_{2}}\cdots h_{m}^{n_{m}}=g$ if and only if $\boldsymbol{z}_{i}\coloneqq n_{1}\boldsymbol{a}_{1}+\cdots+n_{i}\boldsymbol{a}% _{i},i=1,\ldots,m$ satisfy Equations (13) and (14). By Theorem 3.3, the set $\mathcal{Z}$ of $(\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{m})\in\mathbb{Z}^{mn}$ satisfying (13) and (14) is $p$ -automatic. Define the map $\varphi\colon\mathbb{Z}^{m}\rightarrow\mathbb{Z}^{mn},(n_{1},\ldots,n_{m})% \mapsto(n_{1}\boldsymbol{a}_{1},n_{1}\boldsymbol{a}_{1}+n_{2}\boldsymbol{a}_{2% },\ldots,n_{1}\boldsymbol{a}_{1}+\cdots+n_{m}\boldsymbol{a}_{m})$ . Then the solution set of $h_{1}^{n_{1}}h_{2}^{n_{2}}\cdots h_{m}^{n_{m}}=g$ is $\varphi^{-1}(\mathcal{Z})$ . Since $\mathcal{Z}$ is $p$ -automatic and $\varphi$ is linear, $\varphi^{-1}(\mathcal{Z})$ is also $p$ -automatic (see Lemma 2.3).

Case 2: some of the $\boldsymbol{a}_{i}$ ’s are $\boldsymbol{0}$ .

This case can easily be reduced to the previous case. The full proof is given in the appendix of the full version of this paper. $\hfill\blacktriangleleft$

Combining the three steps in this section, we have proven Theorem 3.1:

Proof of Theorem 3.1.

By Proposition 4.1, Proposition 4.4 and Theorem 3.4, Submonoid Membership in $\mathcal{Y}\rtimes\mathbb{Z}^{n}$ reduces to checking whether the solution set of the Knapsack Equation (5) is empty. Since the solution set is effectively $p$ -automatic, its emptiness is decidable (Lemma 2.3). $\hfill\blacktriangleleft$

5 S-unit equation over modules

The purpose of this section is to prove Theorem 3.3 on S-unit equations over modules.

See 3.3

As a comparison, S-unit equations over fields are an intensively studied area in number theory. In the positive characteristic case, Adamczewski and Bell gave the following result.

Theorem 5.1 ([1, Theorem 3.1]).

Let $K$ be a field of characteristic $p>0$ , let $c_{1},\ldots,c_{m}\in K^{*}$ , and let $\overline{x}=(x_{1},\ldots,x_{n})\in\left(K^{*}\right)^{n}$ . Then the set of solutions $(\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{m})\in\left(\mathbb{Z}^{n}\right)^{m}$ for the equation

\overline{x}^{\boldsymbol{z}_{1}}c_{1}+\cdots+\overline{x}^{\boldsymbol{z}_{m}% }c_{m}=1

is an effectively $p$ -automatic subset of $\left(\mathbb{Z}^{n}\right)^{m}\cong\mathbb{Z}^{nm}$ .

Our objective is to generalize Theorem 5.1 from fields to modules. Notably, we need to replace the field $K$ by the polynomial ring $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ , and replace the elements $c_{1},\ldots,c_{m}$ in $K^{*}$ by elements in the finitely presented $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module $M$ . To give a general idea of our approach, consider the following example.

Example 5.2 (label=exa:Sunit).

For simplicity, we present this example using regular polynomial rings instead of Laurent polynomial rings. Consider the equation

X^{a}+Y^{b}=1

(15)

in the $\mathbb{F}_{2}[X,Y]$ -module $\mathbb{F}_{2}[X,Y]/Y^{2}(X+Y+1)$ . Here, the variables are $a,b\in\mathbb{N}$ . (Technically, in order to match the form of the equation in Theorem 3.3, one needs to consider the equation $X^{a}Y^{c}+X^{d}Y^{b}=1$ instead of (15). However, to keep this example simple, we only consider the solutions with $c=d=0$ .)

Equation (15) in $\mathbb{F}_{2}[X,Y]/Y^{2}(X+Y+1)$ is equivalent to $Y^{2}(X+Y+1)\mid X^{a}+Y^{b}+1$ in $\mathbb{F}_{2}[X,Y]$ , which in turn is equivalent to “ $Y^{2}\mid X^{a}+Y^{b}+1$ and $X+Y+1\mid X^{a}+Y^{b}+1$ ”. In other words, Equation (15) holds in $\mathbb{F}_{2}[X,Y]/Y^{2}(X+Y+1)$ if and only if it holds in both $\mathbb{F}_{2}[X,Y]/Y^{2}$ and in $\mathbb{F}_{2}[X,Y]/(X+Y+1)$ .

The $\mathbb{F}_{2}[X,Y]$ -module $\mathbb{F}_{2}[X,Y]/Y^{2}$ can be considered as a finitely generated $\mathbb{F}_{2}[X]$ -module $\mathbb{F}_{2}[X,Y]/Y^{2}=\mathbb{F}_{2}[X]+Y\cdot\mathbb{F}_{2}[X]\cong% \mathbb{F}_{2}[X]^{2}$ by $1\mapsto(1,0),\;Y\mapsto(0,1)$ . Considered as an equation in $\mathbb{F}_{2}[X]^{2}$ , the equation $X^{a}+Y^{b}=1$ becomes

(X^{a},0)=(1,0)\;\text{ if }\;b\geq 2,\quad(X^{a},1)=(1,0)\;\text{ if }\;b=1,% \quad(X^{a}+1,0)=(1,0)\;\text{ if }\;b=0.

So the solution set of $X^{a}+Y^{b}=1$ in $\mathbb{F}_{2}[X,Y]/Y^{2}$ is $\mathcal{Z}_{1}\coloneqq\{(a,b)\mid a=0,\;b\geq 2\}$ .

The $\mathbb{F}_{2}[X,Y]$ -module $\mathbb{F}_{2}[X,Y]/(X+Y+1)$ can be considered as the $\mathbb{F}_{2}[X]$ -module $\mathbb{F}_{2}[X]$ through the variable substitution $Y=X+1$ . Under this variable substitution, the equation $X^{a}+Y^{b}=1$ becomes $X^{a}+(X+1)^{b}=1$ , so its solution set is $\mathcal{Z}_{2}\coloneqq\{(a,b)\mid a=b\in 2^{\mathbb{N}}\}$ . This can be shown similar to Example 4.9, or by directly applying Theorem 5.1 on the quotient field $K=\mathbb{F}_{2}(X)$ .

Thus, the solution set of Equation (15) in $\mathbb{F}_{2}[X,Y]/Y^{2}(X+Y+1)$ is $\mathcal{Z}_{1}\cap\mathcal{Z}_{2}=\emptyset$ . $\lrcorner$

Example 5.2 illustrates the idea that, to solve an equation in a module $M$ , we first “decompose” it into several equations in coprimary modules $M_{1},\ldots,M_{l}$ (such as $\mathbb{F}_{2}[X,Y]/Y^{2}$ and $\mathbb{F}_{2}[X,Y]/(X+Y+1)$ ). This will be formalized in Lemma 5.6. Then, for the equation in each coprimary module, we “eliminate” variables to simplify the quotients (for example $\mathbb{F}_{2}[X,Y]/Y^{2}\cong\mathbb{F}_{2}[X]^{2}$ and $\mathbb{F}_{2}[X,Y]/(X+Y+1)\cong\mathbb{F}_{2}[X]$ both eliminate the variable $Y$ ). In general, variable elimination might not be directly possible, and we need to perform a “change of variables” using Noether Normalization. This will be formalized in Lemma 5.8 and Lemma 5.9. Finally, we show that each such equation “without quotient” (more precisely, in torsion-free modules) has a $p$ -automatic solution set, by reducing to the case of fields (for example, considering equations over $\mathbb{F}_{2}[X]$ as equations over the quotient field $\mathbb{F}_{2}(X)$ ). This will be formalized in Lemma 5.10. Thus, the solution set of the original equation over $M$ is an intersection of effectively $p$ -automatic sets, and is therefore also effectively $p$ -automatic. This approach is inspired by Derkson’s proof of the Skolem-Mahler-Lech theorem in modules over positive characteristic [13, Chapter 9].

The starting point of our proof is the following deep theorem by Adamczewski and Bell, generalizing Theorem 5.1.

Theorem 5.3 ([1, Theorem 4.1]).

Let $K$ be a field of characteristic $p>0$ and let $D$ be a positive integer. Let $V$ be a Zariski closed subset of $\mathsf{GL}_{D}(K)$ and let $A_{1},\ldots,A_{N}$ be commuting matrices in $\mathsf{GL}_{D}(K)$ . Then the set $\{(z_{1},\ldots,z_{N})\in\mathbb{Z}^{N}\mid A_{1}^{z_{1}}A_{2}^{z_{2}}\cdots A% _{n}^{z_{N}}\in V\}$ is effectively $p$ -automatic.

For effectiveness reasons, we need to suppose $K$ to be an effectively computable field (field where all arithmetic operations are effective): this will be the case in all our applications. We will not give the formal definition of a Zariski closed subset because in our application of Theorem 5.3, the set $V$ will be of the form

V=\{A\in\mathsf{GL}_{D}(K)\mid BAv=0^{d}\}

(16)

for some $d\in\mathbb{N},B\in K^{d\times D},v\in K^{D\times 1}$ . This is a linear subset of $\mathsf{GL}_{D}(K)$ and hence Zariski closed. For a tuple of commutative matrices $\overline{A}=(A_{1},\ldots,A_{n})\in\left(\mathsf{GL}_{d}(K)\right)^{n}$ and a vector $\boldsymbol{z}=(z_{1},\ldots,z_{n})\in\mathbb{Z}^{n}$ , denote

\overline{A}^{\boldsymbol{z}}\coloneqq A_{1}^{z_{1}}A_{2}^{z_{2}}\cdots A_{n}^% {z_{n}},

similar to our notation for monomials. In the case where $V$ has the form (16), Theorem 5.3 gives the following corollary, which can be considered as a version of Theorem 3.3 where the module $M$ is replaced by a vector space over a field $K$ .

Corollary 5.4.

Let $K$ be a field of characteristic $p>0$ and let $\overline{A}=(A_{1},\ldots,A_{n})\in\left(\mathsf{GL}_{d}(K)\right)^{n}$ be a tuple of commuting matrices. Let $c_{0},c_{1},\ldots,c_{m}$ be elements in the $d$ -dimensional vector space $K^{d}$ . Then, the set of solutions $(\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{m})\in\left(\mathbb{Z}^{n}\right)^{m}$ for the equation

\overline{A}^{\boldsymbol{z}_{1}}c_{1}+\cdots+\overline{A}^{\boldsymbol{z}_{m}% }c_{m}=c_{0}

(17)

is an effectively $p$ -automatic subset of $\left(\mathbb{Z}^{n}\right)^{m}\cong\mathbb{Z}^{nm}$ .

Proof.

For any $B_{1},\ldots,B_{m+1}\in\mathsf{GL}_{d}(K)$ , we denote by $\operatorname{diag}(B_{1},\ldots,B_{m+1})$ the block diagonal matrix in $\mathsf{GL}_{(m+1)d}(K)$ whose block diagonal entries are $B_{1},\ldots,B_{m+1}$ . Let $I$ denote the identity matrix of dimension $d$ and denote $D=(m+1)d$ . Consider the following elements in $\mathsf{GL}_{D}(K)$ . For $j=1,\ldots,n$ , let $A_{1j}\coloneqq\operatorname{diag}(A_{j},I,\ldots,I),A_{2j}=\operatorname{diag% }(I,A_{j},\ldots,I),\ldots,A_{mj}=\operatorname{diag}(I,\ldots,A_{j},I)$ .

Furthermore, let $v\coloneqq(c_{1}^{\top},c_{2}^{\top},\ldots,c_{m}^{\top},c_{0}^{\top})^{\top}% \in K^{D\times 1}$ , and $B\coloneqq(I,I,\ldots,I,-I)\in K^{d\times D}$ . Then, Equation (17) is equivalent to

B\left(\prod_{i=1}^{m}\prod_{j=1}^{n}A_{ij}^{z_{ij}}\right)v=0^{d}.

(18)

We then apply Theorem 5.3 to the set

V=\{A\in\mathsf{GL}_{D}(K)\mid BAv=0^{d}\}

and the commuting matrices $A_{ij},i=1,\ldots,m;j=1,\ldots,n$ . This shows that the set of solutions $(z_{ij})_{1\leq i\leq m,1\leq j\leq n}$ for Equation (18) is an effectively $p$ -automatic subset of $\mathbb{Z}^{nm}$ . $\hfill\blacktriangleleft$

To pass from vector spaces to modules, we now introduce the primary decomposition of a module. First, we recall some standard definitions and tools from commutative algebra [17].

Definition 5.5.

Let $R$ be a commutative Noetherian ring (for example, $R=\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm}]$ for some field $\mathbb{K}$ ).

(1)

An ideal of $R$ is an $R$ -submodule of $R$ . An ideal $I\subseteq R$ is called prime if $I\neq R$ , and for every $a,b\in R$ , $ab\in I$ implies $a\in I$ or $b\in I$ . Prime ideals are usually denoted by the Gothic letter $\mathfrak{p}$ .
(2)

Let $M$ be a finitely generated $R$ -module. The annihilator of an element $m\in M$ , denoted by $\operatorname{Ann}_{R}(m)$ , is the set $\{r\in R\mid r\cdot m=0\}$ .
(3)

An $R$ -module $M$ is called torsion-free if for every $r\in R,m\in M$ , $r\cdot m=0$ implies $r=0$ or $m=0$ . That is, $M$ is torsion-free if and only if $\operatorname{Ann}_{R}(m)=\{0\}$ for all $m\in M\setminus\{0\}$ .
(4)

A prime ideal $\mathfrak{p}\subset R$ is called associated to $M$ if there exists a non-zero $m\in M$ such that $\mathfrak{p}=\operatorname{Ann}_{R}(m)$ .
(5)

Let $N$ be a finitely generated $R$ -module. A submodule $N^{\prime}$ of $N$ is called primary if $N/N^{\prime}$ has only one associated prime ideal. If we denote this prime ideal by $\mathfrak{p}$ , then $N^{\prime}\subseteq N$ is called $\mathfrak{p}$ -primary.
(6)

Let $N^{\prime}$ be a submodule of a finitely generated $R$ -module $N$ . The primary decomposition of $N^{\prime}$ is the writing of $N^{\prime}$ as a finite intersection $\bigcap_{i=1}^{l}N_{i}$ , where $N_{i}$ is a $\mathfrak{p}_{i}$ -primary submodule of $N$ for some prime ideal $\mathfrak{p}_{i}\subset R$ . A primary decomposition always exists [17, Theorem 3.10]. If $R=\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^% {\pm}]$ and $N,N^{\prime}$ are finitely generated submodules of $R^{d}$ for some $d\in\mathbb{N}$ , then a primary decomposition of $N^{\prime}\subseteq N$ can be effectively computed [36].
(7)

A finitely generated $R$ -module $M$ is called coprimary if the submodule $\{0\}$ is primary, that is, if $M$ has only one associated prime ideal. If we denote this prime ideal by $\mathfrak{p}$ , then $M$ is called $\mathfrak{p}$ -coprimary. If $M$ is $\mathfrak{p}$ -coprimary, and $m$ is a non-zero element in $M$ , then $\operatorname{Ann}_{R}(m)\subseteq\mathfrak{p}$ .

Let $M=\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^% {\pm}]^{d}/N,\;N\subseteq\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX% \mkern-1.5mu}\mkern 1.5mu^{\pm}]^{d}$ be the finite presentation of $M$ in Theorem 3.3. Let $N=\bigcap_{i=1}^{l}N_{i}$ be the primary decomposition of $N$ as a submodule of $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]^{d}$ , where $N_{i}$ is $\mathfrak{p}_{i}$ -primary for a prime ideal $\mathfrak{p}_{i}\subset\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX% \mkern-1.5mu}\mkern 1.5mu^{\pm}]$ , $i=1,\ldots,l$ . Then $M_{i}\coloneqq\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}% \mkern 1.5mu^{\pm}]^{d}/N_{i}$ is $\mathfrak{p}_{i}$ -coprimary. The finite presentation of $N_{i}$ , and hence $M_{i}$ , can be effectively computed (Definition 5.5(6)). Since $N\subseteq N_{i}$ , there is a canonical map $\rho_{i}\colon M=\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5% mu}\mkern 1.5mu^{\pm}]^{d}/N\rightarrow M_{i}=\mathbb{F}_{p}[\mkern 1.5mu% \overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm}]^{d}/N_{i}$ . Since $N=\bigcap_{i=1}^{l}N_{i}$ , the intersection of kernels $\bigcap_{i=1}^{l}\ker(\rho_{i})$ is $\{0\}$ .

Lemma 5.6.

For $i=1,\ldots,l$ , let $\mathcal{Z}_{i}$ denote the set of solutions $(\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{m})\in\left(\mathbb{Z}^{n}\right)^{m}$ of the following equation in $M_{i}$ :

\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{z}_{% 1}}\cdot\rho_{i}(c_{1})+\cdots+\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu% }\mkern 1.5mu^{\boldsymbol{z}_{m}}\cdot\rho_{i}(c_{m})=\rho_{i}(c_{0}).

(19)

Then the solution set of Equation (4) is exactly the intersection $\bigcap_{i=1}^{l}\mathcal{Z}_{i}$ .

Proof.

Since $\bigcap_{i=1}^{l}\ker(\rho_{i})=\{0\}$ , an element $y\in M$ is zero if and only if $\rho_{i}(y)=0$ for all $i=1,\ldots,l$ . Equation (4) is equivalent to $\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{z}_{% 1}}\cdot c_{1}+\cdots+\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1% .5mu^{\boldsymbol{z}_{m}}\cdot c_{m}-c_{0}=0$ . This holds if and only if $\rho_{i}\left(\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \boldsymbol{z}_{1}}\cdot c_{1}+\cdots+\mkern 1.5mu\overline{\mkern-1.5muX% \mkern-1.5mu}\mkern 1.5mu^{\boldsymbol{z}_{m}}\cdot c_{m}-c_{0}\right)=0$ for all $i=1,\ldots,l$ . Therefore, Equation (4) holds if and only if Equation (19) holds for all $i$ . Hence, the solution set of Equation (4) is exactly $\bigcap_{i=1}^{l}\mathcal{Z}_{i}$ . $\hfill\blacktriangleleft$

Example 5.7 (continues=exa:Sunit).

In Example 5.2, we took $R$ to be the ring $\mathbb{F}_{2}[X,Y]$ , and $M$ to be the finitely presented $R$ -module $\mathbb{F}_{2}[X,Y]/Y^{2}(X+Y+1)$ . In this case, we have $M=\mathbb{F}_{2}[X,Y]/N$ with $N=\mathbb{F}_{2}[X,Y]\cdot Y^{2}(X+Y+1)$ , whose primary decomposition is $N=N_{1}\cap N_{2},\;N_{1}=\mathbb{F}_{2}[X,Y]\cdot Y^{2},\,N_{2}=\mathbb{F}_{2% }[X,Y]\cdot(X+Y+1)$ . The modules $M_{1}=\mathbb{F}_{2}[X,Y]/N_{1}=\mathbb{F}_{2}[X,Y]/Y^{2}$ and $M_{2}=\mathbb{F}_{2}[X,Y]/N_{2}=\mathbb{F}_{2}[X,Y]/(X+Y+1)$ are respectively $\mathfrak{p}_{1}$ and $\mathfrak{p}_{2}$ -coprimary, where $\mathfrak{p}_{1}$ is the ideal of $R$ generated by $Y$ , and $\mathfrak{p}_{2}$ is the ideal of $R$ generated by $X+Y+1$ . The sets $\mathcal{Z}_{1},\mathcal{Z}_{2}$ are respectively solutions of the equation $X^{a}+Y^{b}=1$ in $M_{1}$ and $M_{2}$ . $\lrcorner$

Our next step is to show that each $\mathcal{Z}_{i}$ is effectively $p$ -automatic. If so, then their intersection $\bigcap_{i=1}^{l}\mathcal{Z}_{i}$ will also be $p$ -automatic (see Lemma 2.3). Fix $i\in\{1,\ldots,l\}$ . Note that Equation (19) is now an equation over the $\mathfrak{p}_{i}$ -coprimary $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]$ -module $M_{i}$ . This motivates us to consider the quotient ring $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]/\mathfrak{p}_{i}$ . We start with the following staple result in commutative algebra, which can be intuitively understood as performing a “change of variable” to simplify $\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]/\mathfrak{p}_{i}$ .

Lemma 5.8 (Noether Normalization Lemma [32, p.2]).

Let $\mathbb{K}$ be an infinite field and $A$ be a finitely generated $\mathbb{K}$ -algebra. Then there exist algebraically independent elements $\widetilde{X}_{1},\ldots,\widetilde{X}_{s}\in A$ such that $A$ is a finitely generated $\mathbb{K}[\widetilde{X}_{1},\ldots,\widetilde{X}_{s}]$ -module.

Ideally we would want to apply the Noether Normalization Lemma to $A=\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^% {\pm}]/\mathfrak{p}_{i}$ . Even though $\mathbb{F}_{p}$ is not an infinite field, we can without loss of generality replace it with its algebraic closure $\mathbb{K}$ (which is infinite). Formally, we replace $\mathfrak{p}_{i}$ with $\mathfrak{p}_{i}\otimes_{\mathbb{F}_{p}}\mathbb{K}$ and $M_{i}$ with $M_{i}\otimes_{\mathbb{F}_{p}}\mathbb{K}$ . Now $\mathfrak{p}_{i}$ and $M_{i}$ are respectively an ideal and a module over the ring $\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm}]% =\mathbb{F}_{p}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{% \pm}]\otimes_{\mathbb{F}_{p}}\mathbb{K}$ . Note that this does not change the solution set $\mathcal{Z}_{i}$ .

The classical proof of Noether Normalization Lemma is constructive [32, p.2]. In our context, this means that given $A=\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm% }]/\mathfrak{p}_{i}$ , the lemma explicitly gives the expressions for $\widetilde{X}_{1},\ldots,\widetilde{X}_{s}\in A$ as elements in $\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm}]% /\mathfrak{p}_{i}$ .

Choose $Y_{1},\ldots,Y_{s}\in\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5% mu}\mkern 1.5mu^{\pm}]$ such that $Y_{i}+\mathfrak{p}_{i}=\widetilde{X}_{i}$ for all $i$ . Since $\widetilde{X}_{1},\ldots,\widetilde{X}_{s}$ are algebraically independent in $A=\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm% }]/\mathfrak{p}_{i}$ , we have $\mathfrak{p}_{i}\cap\mathbb{K}[Y_{1},\ldots,Y_{s}]=\{0\}$ . Any finitely generated $\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm}]$ -module $M$ is also a $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ -module. However, $M$ might not be finitely generated as a $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ -module. However, in case $M$ is also finitely generated as a $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ -module, then a finite presentation can be effectively computed. This is summarized in the following rather standard result in effective commutative algebra.

Lemma 5.9 ([5, Section 2]).

Let $Y_{1},\ldots,Y_{s}\in\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5% mu}\mkern 1.5mu^{\pm}]$ . Suppose we are given the finite presentation of an $\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm}]$ -module $M$ , as well as a finite number of generators $m_{1},\ldots,m_{t}$ of $M$ as a $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ -module. Then one can effectively compute the finite presentation of $M$ as a $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ -module.

Lemma 5.10.

The set $\mathcal{Z}_{i}$ is effectively $p$ -automatic.

Proof.

The main line of our proof follows [13, Lemma 9.7-9.8], with additional remarks given on effectiveness. As above, we can replace the base field $\mathbb{F}_{p}$ by its algebraic closure $\mathbb{K}$ .

Since $M_{i}$ is $\mathfrak{p}_{i}$ -coprimary, we can compute $t\in\mathbb{N}$ such that $\mathfrak{p}_{i}^{t}M_{i}=0$ (such $t$ exists by the ascending chain condition [17, Chapter 1.4]). We have $M_{i}\supseteq\mathfrak{p}_{i}M_{i}\supseteq\mathfrak{p}_{i}^{2}M_{i}\supseteq% \cdots\supseteq\mathfrak{p}_{i}^{t}M_{i}=0$ . Because $\mathfrak{p}_{i}\cdot(\mathfrak{p}_{i}^{j}M_{i}/\mathfrak{p}_{i}^{j+1}M_{i})=0$ , each quotient $\mathfrak{p}_{i}^{j}M_{i}/\mathfrak{p}_{i}^{j+1}M_{i}$ is a finitely generated $\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm}]% /\mathfrak{p}_{i}$ -module with effectively computable generators, and therefore a finitely generated $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ -module with effectively computable generators. It follows that the $\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm}]$ -module $M_{i}$ is also finitely generated as a $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ -module, with effectively computable generators. Since the finite presentation of $M_{i}$ as a $\mathbb{K}[\mkern 1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu^{\pm}]$ -module is given, we can compute the finite presentation of $M_{i}$ as a $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ -module by Lemma 5.9.

Since $M_{i}$ is $\mathfrak{p}_{i}$ -coprimary, the annihilator of any non-zero element in $M_{i}$ as a $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ -module is contained in $\mathfrak{p}_{i}\cap\mathbb{K}[Y_{1},\ldots,Y_{s}]=\{0\}$ (see Definition 5.5(7)). Therefore, $M_{i}$ is a finitely generated torsion-free $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ -module (see Definition 5.5(3)).

Consider the quotient field $K\coloneqq\mathbb{K}(Y_{1},\ldots,Y_{s})$ of $\mathbb{K}[Y_{1},\ldots,Y_{s}]$ . The localization $\widetilde{M_{i}}\coloneqq M_{i}\otimes_{\mathbb{K}[Y_{1},\ldots,Y_{s}]}K$ is a finite dimensional $K$ -linear space, so $\widetilde{M_{i}}\cong K^{d}$ for some integer $d$ . Because $M_{i}$ is torsion-free, the canonical map $\varphi\colon M_{i}\rightarrow M_{i}\otimes_{\mathbb{K}[Y_{1},\ldots,Y_{s}]}K$ is injective. The linear transformations $A_{j}\colon\widetilde{M_{i}}\rightarrow\widetilde{M_{i}},y\mapsto X_{j}\cdot y,$ commute for $j=1,\ldots,n$ , and they are respectively inverses of the transformations $A_{j}^{-1}\colon\widetilde{M_{i}}\rightarrow\widetilde{M_{i}},y\mapsto X_{j}^{% -1}\cdot y$ . Hence, $A_{j}$ is in $\mathsf{GL}_{d}(K)$ for $j=1,\ldots,n$ , for a fixed basis of $\widetilde{M_{i}}\cong K^{d}$ , and these matrices commute.

Since $\varphi$ is injective, Equation (19) holds if and only if

\overline{A}^{\boldsymbol{z}_{1}}\cdot\varphi(\rho_{i}(c_{1}))+\cdots+% \overline{A}^{\boldsymbol{z}_{m}}\cdot\varphi(\rho_{i}(c_{m}))=\varphi(\rho_{i% }(c_{0})),

(20)

where $\overline{A}=(A_{1},\ldots,A_{n})$ . So $\mathcal{Z}_{i}$ is the solution set for Equation (20). Note that $K=\mathbb{K}(Y_{1},\ldots,Y_{s})$ is an effective field. We now apply Corollary 5.4, and conclude that the solution set for Equation (20) is an effectively $p$ -automatic subset of $\left(\mathbb{Z}^{n}\right)^{m}\cong\mathbb{Z}^{nm}$ . $\hfill\blacktriangleleft$

Example 5.11 (continues=exa:Sunit).

As above, the $\mathbb{K}[X,Y]$ -module $M_{1}=\mathbb{K}[X,Y]/Y^{2}$ is isomorphic to the $\mathbb{K}[X]$ -module $\mathbb{K}[X]^{2}$ by $\mathbb{K}[X,Y]/Y^{2}\xrightarrow[]{\sim}\mathbb{K}[X]^{2},\,f_{0}+Yf_{1}+Y^{2% }f_{2}+\cdots\mapsto(f_{0},f_{1})$ , for $f_{0},f_{1},f_{2},\ldots\in\mathbb{K}[X]$ .

We would like to solve the equation $X^{a}+Y^{b}=1$ in $M_{1}$ . Let $\mathbb{K}(X)$ denote the quotient field of $\mathbb{K}[X]$ : this is the set of univariate rational functions over the field $\mathbb{K}$ . Note that $\varphi:M_{1}\cong\mathbb{K}[X]^{2}\hookrightarrow\mathbb{K}(X)^{2}$ is injective. Consider $\mathbb{K}(X)^{2}$ as a 2-dimensional vector space over $\mathbb{K}(X)$ , then the map $\varphi(m)\mapsto\varphi(X\cdot m),m\in M_{1},$ extends to a linear transformation associated to the matrix $A_{X}=\begin{pmatrix}X&0\\ 0&X\\ \end{pmatrix}$ , and the map $\varphi(m)\mapsto\varphi(Y\cdot m),m\in M_{1}$ extends to a linear transformation associated to the matrix $A_{Y}=\begin{pmatrix}0&1\\ 0&0\\ \end{pmatrix}$ . (Here, $A_{Y}$ is not invertible because the variable $Y$ is not invertible in $\mathbb{K}[X,Y]$ . However in the proof of Lemma 5.10, we are considering Laurent polynomial rings, so all the associated matrices would be invertible.)

As a result, the equation $X^{a}+Y^{b}=1$ in $M_{1}$ is equivalent to the equation $A_{X}^{a}\cdot(1,0)^{\top}+A_{Y}^{b}(1,0)^{\top}=(1,0)^{\top}$ in the 2-dimensional vector space $\mathbb{K}(X)^{2}$ . Subject to the invertibility of $A_{Y}$ , we can then use Corollary 5.4 to conclude that the equation admits an effectively $2$ -automatic solution set. $\lrcorner$

Combining Lemma 5.6 and Lemma 5.10, we obtain a proof of Theorem 3.3:

Proof of Theorem 3.3.

By Lemma 5.6, the solution set of Equation (4) is the intersection $\bigcap_{i=1}^{l}\mathcal{Z}_{i}$ . Lemma 5.10 shows that each $\mathcal{Z}_{i}$ is effectively $p$ -automatic, so their intersection is also effectively $p$ -automatic (Lemma 2.3). $\hfill\blacktriangleleft$

References

[1] Boris Adamczewski and Jason P. Bell. On vanishing coefficients of algebraic power series over fields of positive characteristic. Inventiones mathematicae, 187(2):343–393, 2012.
[2] László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, and Eugene M. Luks. Multiplicative equations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 498–507, 1996. URL: http://dl.acm.org/citation.cfm?id=313852.314109.
[3] Sebastián Barbieri, Jarkko Kari, and Ville Salo. The group of reversible Turing machines. In Cellular Automata and Discrete Complex Systems: 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016, Proceedings 22, pages 49–62. Springer, 2016. doi:10.1007/978-3-319-39300-1_5.
[4] Laurent Bartholdi and Ville Salo. Simulations and the lamplighter group. Groups, Geometry, and Dynamics, 16(4):1461–1514, 2022.
[5] Gilbert Baumslag, Frank B. Cannonito, and Charles F. Miller III. Computable algebra and group embeddings. Journal of Algebra, 69(1):186–212, 1981.
[6] Gilbert Baumslag, Frank B. Cannonito, and Derek J.S. Robinson. The algorithmic theory of finitely generated metabelian groups. Transactions of the American Mathematical Society, 344(2):629–648, 1994.
[7] Robert Beals and László Babai. Las Vegas algorithms for matrix groups. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 427–436. IEEE, 1993. doi:10.1109/SFCS.1993.366844.
[8] Michèle Benois. Parties rationnelles du groupe libre. C. R. Acad. Sci. Paris, Sér. A,, 269:1188–1190, 1969.
[9] Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier. Decidable and undecidable problems about quantum automata. SIAM Journal on Computing, 34(6):1464–1473, 2005. doi:10.1137/S0097539703425861.
[10] Corentin Bodart. Membership problems in nilpotent groups. arXiv preprint arXiv:2401.15504, 2024. doi:10.48550/arXiv.2401.15504.
[11] Michaël Cadilhac, Dmitry Chistikov, and Georg Zetzsche. Rational subsets of Baumslag-Solitar groups. In 47th International Colloquium on Automata, Languages, and Programming, ICALP, volume 168 of LIPIcs, pages 116:1–116:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.ICALP.2020.116.
[12] Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, and James Worrell. On reachability problems for low-dimensional matrix semigroups. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 44:1–44:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.ICALP.2019.44.
[13] Harm Derksen. A Skolem–Mahler–Lech theorem in positive characteristic and finite automata. Inventiones mathematicae, 168(1):175–224, 2007.
[14] Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. Quantum automata and algebraic groups. Journal of Symbolic Computation, 39(3-4):357–371, 2005. doi:10.1016/j.jsc.2004.11.008.
[15] Ruiwen Dong. Recent advances in algorithmic problems for semigroups. ACM SIGLOG News, 10(4):3–23, 2023. doi:10.1145/3636362.3636365.
[16] Ruiwen Dong. Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1892–1908. SIAM, 2025. doi:10.1137/1.9781611978322.59.
[17] David Eisenbud. Commutative algebra: with a view toward algebraic geometry, volume 150. Springer Science & Business Media, 2013.
[18] Moses Ganardi, Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack problems for wreath products. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 32:1–32:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPICS.STACS.2018.32.
[19] Rostislav Grigorchuk and Andrzej Żuk. The lamplighter group as a group generated by a 2-state automaton, and its spectrum. Geometriae Dedicata, 87(1):209–244, 2001.
[20] Zeph Grunschlag. Algorithms in geometric group theory. University of California, Berkeley, 1999.
[21] Philipp Hieronymi and Christian Schulz. A strong version of Cobham’s theorem. SIAM Journal on Computing, 51(6):1400–1421, 2022. doi:10.1137/22M1538065.
[22] Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell. Polynomial invariants for affine programs. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 530–539, 2018. doi:10.1145/3209108.3209142.
[23] Mark Kambites, Pedro V. Silva, and Benjamin Steinberg. The spectra of lamplighter groups and Cayley machines. Geometriae Dedicata, 120(1):193–227, 2006.
[24] Toghrul Karimov, Florian Luca, Joris Nieuwveld, Joël Ouaknine, and James Worrell. On the decidability of Presburger arithmetic expanded with powers. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2755–2778. SIAM, 2025. doi:10.1137/1.9781611978322.89.
[25] Markus Lohrey. Membership problems in infinite groups. In Conference on Computability in Europe, pages 44–59. Springer, 2024. doi:10.1007/978-3-031-64309-5_5.
[26] Markus Lohrey and Benjamin Steinberg. The submonoid and rational subset membership problems for graph groups. Journal of Algebra, 320(2):728–755, 2008.
[27] Markus Lohrey and Benjamin Steinberg. Tilings and submonoids of metabelian groups. Theory of Computing Systems, 48(2):411–427, 2011. doi:10.1007/S00224-010-9264-9.
[28] Markus Lohrey, Benjamin Steinberg, and Georg Zetzsche. Rational subsets and submonoids of wreath products. Information and Computation, 243:191–204, 2015. doi:10.1016/J.IC.2014.12.014.
[29] Russell Lyons, Robin Pemantle, and Yuval Peres. Random walks on the lamplighter group. The annals of probability, pages 1993–2006, 1996.
[30] A. Markov. On an unsolvable problem concerning matrices. Doklady Akad. Nauk SSSR, 78(6):1089–1092, 1951.
[31] K. A. Mikhailova. The entrance problem for direct unions of groups. Doklady Akad. Nauk SSSR, 119(6):1103–1105, 1958.
[32] David Mumford. The Red Book of Varieties and Schemes, volume 1358 of Lecture Notes in Mathematics. Springer, 1999.
[33] Igor Potapov and Pavel Semukhin. Decidability of the membership problem for 2 $\times$ 2 integer matrices. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 170–186. SIAM, 2017.
[34] Felix Potthast. Submonoid Membership for Wreath Products. Bachelor’s thesis, Universität Siegen, 2020. Based on the unpublished draft of Doron Shafrir: The Submonoid Problem in Torsion-by- $\mathbb{Z}^{d}$ Groups, private communication with Markus Lohrey and Benjamin Steinberg. May 2018.
[35] N.S. Romanovskii. Some algorithmic problems for solvable groups. Algebra and Logic, 13(1):13–16, 1974.
[36] Elizabeth W. Rutman. Gröbner bases and primary decomposition of modules. Journal of symbolic computation, 14(5):483–503, 1992. doi:10.1016/0747-7171(92)90019-Z.
[37] Doron Shafrir. Is decidability of the Submonoid Membership Problem closed under finite extensions? arXiv preprint arXiv:2405.12921, 2024. doi:10.48550/arXiv.2405.12921.
[38] Pedro V. Silva and Benjamin Steinberg. On a class of automata groups generalizing lamplighter groups. International journal of algebra and computation, 15(05n06):1213–1234, 2005. doi:10.1142/S0218196705002761.
[39] Pierre Wolper and Bernard Boigelot. On the construction of automata from linear arithmetic constraints. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 1–19. Springer, 2000. doi:10.1007/3-540-46419-0_1.

[bib.bib1] [1] Boris Adamczewski and Jason P. Bell. On vanishing coefficients of algebraic power series over fields of positive characteristic. Inventiones mathematicae, 187(2):343–393, 2012.

[bib.bib2] [2] László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, and Eugene M. Luks. Multiplicative equations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 498–507, 1996. URL: http://dl.acm.org/citation.cfm?id=313852.314109.

[bib.bib3] [3] Sebastián Barbieri, Jarkko Kari, and Ville Salo. The group of reversible Turing machines. In Cellular Automata and Discrete Complex Systems: 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016, Proceedings 22, pages 49–62. Springer, 2016. doi:10.1007/978-3-319-39300-1_5.

[bib.bib4] [4] Laurent Bartholdi and Ville Salo. Simulations and the lamplighter group. Groups, Geometry, and Dynamics, 16(4):1461–1514, 2022.

[bib.bib5] [5] Gilbert Baumslag, Frank B. Cannonito, and Charles F. Miller III. Computable algebra and group embeddings. Journal of Algebra, 69(1):186–212, 1981.

[bib.bib6] [6] Gilbert Baumslag, Frank B. Cannonito, and Derek J.S. Robinson. The algorithmic theory of finitely generated metabelian groups. Transactions of the American Mathematical Society, 344(2):629–648, 1994.

[bib.bib7] [7] Robert Beals and László Babai. Las Vegas algorithms for matrix groups. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 427–436. IEEE, 1993. doi:10.1109/SFCS.1993.366844.

[bib.bib8] [8] Michèle Benois. Parties rationnelles du groupe libre. C. R. Acad. Sci. Paris, Sér. A,, 269:1188–1190, 1969.

[bib.bib9] [9] Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier. Decidable and undecidable problems about quantum automata. SIAM Journal on Computing, 34(6):1464–1473, 2005. doi:10.1137/S0097539703425861.

[bib.bib10] [10] Corentin Bodart. Membership problems in nilpotent groups. arXiv preprint arXiv:2401.15504, 2024. doi:10.48550/arXiv.2401.15504.

[bib.bib11] [11] Michaël Cadilhac, Dmitry Chistikov, and Georg Zetzsche. Rational subsets of Baumslag-Solitar groups. In 47th International Colloquium on Automata, Languages, and Programming, ICALP, volume 168 of LIPIcs, pages 116:1–116:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.ICALP.2020.116.

[bib.bib12] [12] Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, and James Worrell. On reachability problems for low-dimensional matrix semigroups. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 44:1–44:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.ICALP.2019.44.

[bib.bib13] [13] Harm Derksen. A Skolem–Mahler–Lech theorem in positive characteristic and finite automata. Inventiones mathematicae, 168(1):175–224, 2007.

[bib.bib14] [14] Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. Quantum automata and algebraic groups. Journal of Symbolic Computation, 39(3-4):357–371, 2005. doi:10.1016/j.jsc.2004.11.008.

[bib.bib15] [15] Ruiwen Dong. Recent advances in algorithmic problems for semigroups. ACM SIGLOG News, 10(4):3–23, 2023. doi:10.1145/3636362.3636365.

[bib.bib16] [16] Ruiwen Dong. Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1892–1908. SIAM, 2025. doi:10.1137/1.9781611978322.59.

[bib.bib17] [17] David Eisenbud. Commutative algebra: with a view toward algebraic geometry, volume 150. Springer Science & Business Media, 2013.

[bib.bib18] [18] Moses Ganardi, Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack problems for wreath products. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 32:1–32:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPICS.STACS.2018.32.

[bib.bib19] [19] Rostislav Grigorchuk and Andrzej Żuk. The lamplighter group as a group generated by a 2-state automaton, and its spectrum. Geometriae Dedicata, 87(1):209–244, 2001.

[bib.bib20] [20] Zeph Grunschlag. Algorithms in geometric group theory. University of California, Berkeley, 1999.

[bib.bib21] [21] Philipp Hieronymi and Christian Schulz. A strong version of Cobham’s theorem. SIAM Journal on Computing, 51(6):1400–1421, 2022. doi:10.1137/22M1538065.

[bib.bib22] [22] Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell. Polynomial invariants for affine programs. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 530–539, 2018. doi:10.1145/3209108.3209142.

[bib.bib23] [23] Mark Kambites, Pedro V. Silva, and Benjamin Steinberg. The spectra of lamplighter groups and Cayley machines. Geometriae Dedicata, 120(1):193–227, 2006.

[bib.bib24] [24] Toghrul Karimov, Florian Luca, Joris Nieuwveld, Joël Ouaknine, and James Worrell. On the decidability of Presburger arithmetic expanded with powers. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2755–2778. SIAM, 2025. doi:10.1137/1.9781611978322.89.

[bib.bib25] [25] Markus Lohrey. Membership problems in infinite groups. In Conference on Computability in Europe, pages 44–59. Springer, 2024. doi:10.1007/978-3-031-64309-5_5.

[bib.bib26] [26] Markus Lohrey and Benjamin Steinberg. The submonoid and rational subset membership problems for graph groups. Journal of Algebra, 320(2):728–755, 2008.

[bib.bib27] [27] Markus Lohrey and Benjamin Steinberg. Tilings and submonoids of metabelian groups. Theory of Computing Systems, 48(2):411–427, 2011. doi:10.1007/S00224-010-9264-9.

[bib.bib28] [28] Markus Lohrey, Benjamin Steinberg, and Georg Zetzsche. Rational subsets and submonoids of wreath products. Information and Computation, 243:191–204, 2015. doi:10.1016/J.IC.2014.12.014.

[bib.bib29] [29] Russell Lyons, Robin Pemantle, and Yuval Peres. Random walks on the lamplighter group. The annals of probability, pages 1993–2006, 1996.

[bib.bib30] [30] A. Markov. On an unsolvable problem concerning matrices. Doklady Akad. Nauk SSSR, 78(6):1089–1092, 1951.

[bib.bib31] [31] K. A. Mikhailova. The entrance problem for direct unions of groups. Doklady Akad. Nauk SSSR, 119(6):1103–1105, 1958.

[bib.bib32] [32] David Mumford. The Red Book of Varieties and Schemes, volume 1358 of Lecture Notes in Mathematics. Springer, 1999.

[bib.bib33] [33] Igor Potapov and Pavel Semukhin. Decidability of the membership problem for 2 $\times$ 2 integer matrices. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 170–186. SIAM, 2017.

[bib.bib34] [34] Felix Potthast. Submonoid Membership for Wreath Products. Bachelor’s thesis, Universität Siegen, 2020. Based on the unpublished draft of Doron Shafrir: The Submonoid Problem in Torsion-by- $\mathbb{Z}^{d}$ Groups, private communication with Markus Lohrey and Benjamin Steinberg. May 2018.

[bib.bib35] [35] N.S. Romanovskii. Some algorithmic problems for solvable groups. Algebra and Logic, 13(1):13–16, 1974.

[bib.bib36] [36] Elizabeth W. Rutman. Gröbner bases and primary decomposition of modules. Journal of symbolic computation, 14(5):483–503, 1992. doi:10.1016/0747-7171(92)90019-Z.

[bib.bib37] [37] Doron Shafrir. Is decidability of the Submonoid Membership Problem closed under finite extensions? arXiv preprint arXiv:2405.12921, 2024. doi:10.48550/arXiv.2405.12921.

[bib.bib38] [38] Pedro V. Silva and Benjamin Steinberg. On a class of automata groups generalizing lamplighter groups. International journal of algebra and computation, 15(05n06):1213–1234, 2005. doi:10.1142/S0218196705002761.

[bib.bib39] [39] Pierre Wolper and Bernard Boigelot. On the construction of automata from linear arithmetic constraints. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 1–19. Springer, 2000. doi:10.1007/3-540-46419-0_1.

Submonoid Membership in n-Dimensional Lamplighter Groups and S-Unit Equations

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Algorithmic problems in infinite groups

n-dimensional lamplighter groups

Contributions of this paper

2 Preliminaries

Laurent polynomial ring and modules

Effective computation in modules

Lemma 2.1 ([5, Lemma 2.1, 2.2]).

Lemma 2.2 ([5, Theorem 2.14] or [6, Theorem 2.6]).

p-automatic sets

Lemma 2.3 ([39]).

3 Main results and consequences

Theorem 3.1.

Corollary 3.2.

Proof.

Theorem 3.3.

Theorem 3.4.

4 From Submonoid Membership to S-unit equation

Step 1: from Submonoid Membership to Group Product Membership

Proposition 4.1 ([34, Theorem 4.3.3]).

Proof.

Example 4.2 (label=exa:cont).

Remark 4.3.

Step 2: from Group Product Membership to Knapsack Problem

Proposition 4.4.

Lemma 4.5 ([6, Theorem 3.3] or [35, Lemma 2]).

Example 4.6 (continues=exa:cont).

Lemma 4.7.

Proof.

Proof of Proposition 4.4.

Remark 4.8.

Step 3: from Knapsack Problem to S-unit equation

Example 4.9.

Proof of Theorem 3.4 (assuming Theorem 3.3).

Case 1: none of the 𝒂𝒊 is 𝟎

Case 2: some of the 𝒂𝒊’s are 𝟎.

Proof of Theorem 3.1.

5 S-unit equation over modules

Theorem 5.1 ([1, Theorem 3.1]).

Example 5.2 (label=exa:Sunit).

Theorem 5.3 ([1, Theorem 4.1]).

Corollary 5.4.

Proof.

Definition 5.5.

Lemma 5.6.

Proof.

Example 5.7 (continues=exa:Sunit).

Lemma 5.8 (Noether Normalization Lemma [32, p.2]).

Lemma 5.9 ([5, Section 2]).

Lemma 5.10.

Proof.

Example 5.11 (continues=exa:Sunit).

Proof of Theorem 3.3.

References

Case 1: none of the $\boldsymbol{a}_{i}$ is $\boldsymbol{0}$

Case 2: some of the $\boldsymbol{a}_{i}$ ’s are $\boldsymbol{0}$ .