Let T be a positive integer and M be a finitely presented module over the Laurent polynomial ring ℤ/T[X1±, …, XN±]. We consider S-unit equations over M: these are equations of the form x1 m1 + ⋯ + xK mK = m0, where the variables x1, …, xK range over the set of monomials (with coefficient 1) of ℤ/T[X1±, …, XN±]. When T is a power of a prime number p, we show that the solution set of an S-unit equation over M is effectively p-normal in the sense of Derksen and Masser (2015). This generalizes their result on S-unit equations in fields of prime characteristic. When T is an arbitrary positive integer, we show that deciding whether an S-unit equation over M admits a solution is Turing equivalent to solving a system of linear-exponential Diophantine equations, whose base contains the prime divisors of T. Combined with a recent result of Karimov, Luca, Nieuwveld, Ouaknine and Worrell (2025), this yields decidability when T has at most two distinct prime divisors. This also shows that proving either decidability or undecidability in the case of arbitrary T would entail major breakthroughs in number theory. S-unit equations in modules have direct connections to many problems in computational algebra such as finding sparse polynomials in ideals, identifying zeros of linear recurrence sequences, and deciding membership problems in metabelian groups. In particular, a direct consequence of our result is the decidability Submonoid Membership in wreath products of the form ℤ/pa qb ≀ ℤd.

We show that the Skolem Problem is decidable in finitely generated commutative rings of positive characteristic. More precisely, we show that there exists an algorithm which, given a finite presentation of a (unitary) commutative ring R = ℤ/T[X1, …, Xn]/I of characteristic T > 0, and a linear recurrence sequence (γn)n ∈ ℕ ∈ Rℕ, determines whether (γn)n ∈ ℕ contains a zero term. Our proof is based on two recent results: Dong and Shafrir (2026) on the solution set of S-unit equations over pe-torsion modules, and Karimov, Luca, Nieuwveld, Ouaknine, and Worrell (2025) on solving linear equations over powers of two multiplicatively independent numbers. Our result implies, moreover, that the zero set of a linear recurrence sequence over a ring of characteristic T = p1e1 ⋯ pkek is effectively a finite union of pi-normal sets in the sense of Derksen (2007).

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.

The Tits alternative states that a finitely generated matrix group either contains a nonabelian free subgroup F2, or it is virtually solvable. This paper considers two decision problems in virtually solvable matrix groups: the Identity Problem (does a given finitely generated subsemigroup contain the identity matrix?), and the Group Problem (is a given finitely generated subsemigroup a group?). We show that both problems are decidable in virtually solvable matrix groups over the field of algebraic numbers $\overline {\mathbb{Q}} $ . Our proof also extends the decidability result for nilpotent groups by Bodart, Ciobanu, Metcalfe and Shaffrir, and the decidability result for metabelian groups by Dong (STOC’24). Since the Identity Problem and the Group Problem are known to be undecidable in matrix groups containing F2 × F2, our result significantly reduces the decidability gap for both decision problems.

We show that it is undecidable whether a system of linear equations over the Laurent polynomial ring ℤ [X±] admit solutions where a specified subset of variables take value in the set of monomials {Xz | z ϵ ℤ}. In particular, we construct a finitely presented ℤ[X±]-module, where it is undecidable whether a linear equation XZ1 f1 + ··· + XZn fn = f 0 has solutions z1,…,zn ϵ ℤ. This contrasts the decidability of the case n = 1, which can be deduced from Noskov’s Lemma.

We consider semigroup algorithmic problems in the Special Affine group $\mathsf{SA}(2, \mathbb{Z}) = \mathbb{Z}^2 \rtimes \mathsf{SL}(2, \mathbb{Z})$, which is the group of affine transformations of the lattice $\mathbb{Z}^2$ that preserve orientation. Our paper focuses on two decision problems introduced by Choffrut and Karhum\"{a}ki (2005): the Identity Problem (does a semigroup contain a neutral element?) and the Group Problem (is a semigroup a group?) for finitely generated sub-semigroups of $\mathsf{SA}(2, \mathbb{Z})$. We show that both problems are decidable and NP-complete. Since $\mathsf{SL}(2, \mathbb{Z}) \leq \mathsf{SA}(2, \mathbb{Z}) \leq \mathsf{SL}(3, \mathbb{Z})$, our result extends that of Bell, Hirvensalo and Potapov (2017) on the NP-completeness of both problems in $\mathsf{SL}(2, \mathbb{Z})$, and contributes a first step towards the open problems in $\mathsf{SL}(3, \mathbb{Z})$.

Let G be a unitriangular matrix group of nilpotency class at most ten. We show that the Identity Problem (does a semigroup contain the identity matrix?) and the Group Problem (is a semigroup a group?) are decidable in polynomial time for finitely generated subsemigroups of G. Our decidability results also hold when G is an arbitrary finitely generated nilpotent group of class at most ten. This extends earlier work of Babai et al. on commutative matrix groups (SODA’96) and work of Bell et al. on SL(2, ℤ) (SODA’17). Furthermore, we formulate a sufficient condition for the generalization of our results to nilpotent groups of class d > 10. For every such d, we exhibit an effective procedure that verifies this condition in case it is true.

We consider semigroup algorithmic problems in finitely generated metabelian groups. Our paper focuses on three decision problems introduced by Choffrut and Karhum'aki (2005): the Identity Problem (does a semigroup contain a neutral element?), the Group Problem (is a semigroup a group?) and the Inverse Problem (does a semigroup contain the inverse of a generator?). We show that all three problems are decidable for finitely generated subsemigroups of finitely generated metabelian groups. In particular, we establish a correspondence between polynomial semirings and subsemigroups of metabelian groups using an interaction of graph theory, convex polytopes, algebraic geometry and number theory. Since the Semigroup Membership problem (does a semigroup contain a given element?) is known to be undecidable in finitely generated metabelian groups, our result completes the decidability characterization of semigroup algorithmic problems in metabelian groups.

Abstract. We consider two algorithmic problems concerning subsemigroups of Heisenberg groups and, more generally, 2-step nilpotent groups. The first problem is Intersection Emptiness, which asks whether a finite number of given finitely generated semigroups have empty intersection. This problem was first studied by Markov in the 1940s. We show that Intersection Emptiness is PTIME decidable in the Heisenberg groups [Formula: see text] over any algebraic number field [Formula: see text]. We also extend our decidability result to arbitrary finitely generated 2-step nilpotent groups. The second problem is Orbit Intersection, which asks whether the orbits of two matrices under multiplication by two semigroups intersect with each other. This problem was first studied by Babai, Beals, Cai, Ivanyos, and Luks (1996), who showed its decidability in commutative matrix groups. We show that Orbit Intersection is decidable in the Heisenberg group [Formula: see text].

We consider semigroup algorithmic problems in the wreath product $\mathbb{Z} \wr \mathbb{Z}$. Our paper focuses on two decision problems introduced by Choffrut and Karhumäki (2005): the Identity Problem (does a semigroup contain the neutral element?) and the Group Problem (is a semigroup a group?) for finitely generated sub-semigroups of $\mathbb{Z} \wr \mathbb{Z}$. We show that both problems are decidable. Our result complements the undecidability of the Semigroup Membership Problem (does a semigroup contain a given element?) in $\mathbb{Z} \wr \mathbb{Z}$ shown by Lohrey, Steinberg and Zetzsche (ICALP 2013), and contributes an important step towards solving semigroup algorithmic problems in general metabelian groups.

We consider the following problem: given d × d rational matrices A1, …, Ak and a polyhedral cone , decide whether there exists a non-zero vector whose orbit under multiplication by A1, …, Ak is contained in . This problem can be interpreted as verifying the termination of multi-path while loops with linear updates and linear guard conditions. We show that this problem is decidable for commuting invertible matrices A1, …, Ak. The key to our decision procedure is to reinterpret this problem in a purely algebraic manner. Namely, we discover its connection with modules over the polynomial ring as well as the polynomial semiring . The loop termination problem is then reduced to deciding whether a submodule of contains a “positive” element.

We consider semigroup algorithmic problems in the Special Affine group ${\text{SA}}(2,{\mathbb{Z}}) = {{\mathbb{Z}}^2} \rtimes {\text{SL}}(2,{\mathbb{Z}})$, which is the group of affine transformations of the lattice ${{\mathbb{Z}}^2}$ that preserve orientation. Our paper focuses on two decision problems introduced by Choffrut and Karhumäki (2005): the Identity Problem (does a semigroup contain a neutral element?) and the Group Problem (is a semigroup a group?) for finitely generated sub-semigroups of ${\text{SA}}(2,{\mathbb{Z}})$. We show that both problems are decidable and NP-complete. Since ${\text{SL}}(2,{\mathbb{Z}}) \leq {\text{SA}}(2,{\mathbb{Z}}) \leq {\text{SL}}(3,{\mathbb{Z}})$, our result extends that of Bell, Hirvensalo and Potapov (SODA 2017) on the NP-completeness of both problems in ${\text{SL}}(2,{\mathbb{Z}})$, and contributes a first step towards the open problems in ${\text{SL}}(3,{\mathbb{Z}})$.

We show that the Identity Problem is decidable in polynomial time for finitely generated sub-semigroups of the group $\mathsf{UT}(4, \mathbb{Z})$ of $4 \times 4$ unitriangular integer matrices. As a byproduct of our proof, we also show the polynomial-time decidability of several subset reachability problems in $\mathsf{UT}(4, \mathbb{Z})$.