Lune

STOC2026Top-tier venue

S-Unit Equations in Modules and Linear-Exponential Diophantine Equations

Ruiwen Dong, Doron Shafrir

Abstract

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • The Skolem Problem in Rings of Positive Characteristic cites On the Skolem Problem and the Skolem Conjecture
  • The Skolem Problem in Rings of Positive Characteristic cites A strong version of Cobham's theorem
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. The Skolem Problem in Rings of Positive CharacteristicRuiwen Dong, Doron ShafrirSTOC 2026 · 2 citations

Builds on6

  1. On the Skolem Problem and the Skolem ConjectureRichard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine et al.LICS 2022 · 6 citations
  2. Linear equations with monomial constraints and decision problems in abelian-by-cyclic groupsRuiwen DongSODA 2025 · 4 citations
  3. Positivity Certificates for Linear RecurrencesAlaa Ibrahim, Bruno SalvySODA 2024 · 4 citations
  4. A strong version of Cobham's theoremPhilipp Hieronymi, Christian SchulzSTOC 2022 · 3 citations
  5. On the Decidability of Monadic Second-Order Logic with Arithmetic PredicatesValérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine et al.LICS 2024 · 3 citations

Related papers

  1. The Identity Problem in nilpotent groups of bounded classRuiwen DongSODA 2024 · 4 citations
  2. Trading Determinism for Noncommutativity in Edmonds' ProblemVikraman Arvind, Abhranil Chatterjee, Partha MukhopadhyayFOCS 2024 · 2 citations
  3. The Power of PositivityToghrul Karimov, Edon Kelmendi, Joris Nieuwveld, Joël Ouaknine et al.LICS 2023 · 3 citations
  4. Multiple Reachability in Linear Dynamical SystemsToghrul Karimov, Edon Kelmendi, Joël Ouaknine, James WorrellLICS 2025 · 1 citation
  5. On Variable-Bounded Non-Linear Expansions of Presburger ArithmeticPiotr Bacik, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala et al.LICS 2026
Dusk over the sea between two cliffs drawn in fine vertical lines