S-unit equations in modules and linear-exponential Diophantine equations

2025/05/25 by Dong, Ruiwen, Shafrir, Doron · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2505.19141

Abstract

Let T be a positive integer, and M be a finitely presented module over the Laurent polynomial ring ℤ_/T[X₁^±, …, X_N^±]. We consider S-unit equations over M: these are equations of the form x₁ m₁ + ⋯ + x_K m_K = m₀, where the variables x₁, …, x_K range over the set of monomials (with coefficient 1) of ℤ_/T[X₁^±, …, X_N^±]. 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), generalizing 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. We mention some potential applications of our results, such as deciding Submonoid Membership in wreath products of the form ℤ_{/p^a q^b} \wr ℤ^d, as well as progressing towards solving the Skolem problem in rings whose additive group is torsion. More connections in these directions will be explored in follow up papers.

Citations

• The Skolem Problem in rings of positive characteristic
• Submonoid Membership in n-dimensional lamplighter groups and S-unit equations
• On the Decidability of Presburger Arithmetic Expanded with Powers
• Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups
• The complexity of Presburger arithmetic with power or powers
• The complexity of knapsack problems in wreath products
• A robust implementation for solving the S-unit equation and several applications
• Finding binomials in polynomial ideals
• A Skolem-Mahler-Lech Theorem in Positive Characteristic and Finite Automata

Cited by

• The Skolem Problem in rings of positive characteristic

Related

• Submonoid Membership in n-dimensional lamplighter groups and S-unit equations
• The Skolem Problem in rings of positive characteristic
• Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups
• A robust implementation for solving the S-unit equation and several applications
• On finding many solutions to S-unit equations by solving linear equations on average