pith. sign in

arxiv: 2504.14413 · v4 · submitted 2025-04-19 · 💻 cs.LO · math.NT

On the p-adic Skolem Problem

Piotr Bacik , Jo\"el Ouaknine , David Purser , James Worrell This is my paper

Pith reviewed 2026-05-22 17:52 UTC · model grok-4.3

classification 💻 cs.LO math.NT
keywords p-adic Skolem problemlinear recurrence sequencesp-adic zerosSchanuel conjecturedecidabilitySkolem-Mahler-Lech theoremeffective methods
0
0 comments X

The pith

Algorithms decide whether linear recurrence sequences have p-adic zeros and compute exact representations of all such zeros.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops algorithms to decide if a given linear recurrence sequence has a zero in the p-adic numbers and to list exact representations of every such zero. These procedures produce correct answers without any extra assumptions, yet they are guaranteed to finish only when the p-adic Schanuel Conjecture holds. The authors then use the same tools to prove that the Simultaneous Skolem Problem—deciding whether two coprime linear recurrences share a common natural-number zero—is decidable under that same conjecture. A sympathetic reader cares because the classical Skolem problem has resisted effective resolution for decades, and progress on its p-adic version supplies a concrete route toward locating zeros in the integers or rationals once modest extra hypotheses are added.

Core claim

The paper presents algorithms for the decision problem of whether a linear recurrence sequence has a p-adic zero and for the function problem of computing exact representations of all p-adic zeros. The output of the algorithms is unconditionally correct, and termination is guaranteed subject to the p-adic Schanuel Conjecture. These results are applied to establish decidability of the Simultaneous Skolem Problem subject to the same conjecture.

What carries the argument

Algorithms that reduce the search for p-adic zeros of a linear recurrence sequence to effective computations with the p-adic exponential function, whose linear independence properties are invoked via the p-adic Schanuel Conjecture.

If this is right

  • If the p-adic Schanuel Conjecture holds, both the decision problem and the computation problem for p-adic zeros become solvable.
  • The Simultaneous Skolem Problem is decidable subject to the p-adic Schanuel Conjecture.
  • The same algorithms can be used to locate natural-number and rational zeros of linear recurrence sequences when combined with additional hypotheses.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The p-adic methods could be combined with existing techniques for real or rational zeros to obtain conditional decision procedures for the classical Skolem Problem.
  • Concrete implementations of the algorithms would allow systematic checks on sequences that arise in applications such as population dynamics or linear feedback shift registers.

Load-bearing premise

Termination of the algorithms is guaranteed only if the p-adic Schanuel Conjecture holds.

What would settle it

An explicit linear recurrence sequence together with a p-adic integer that the algorithm neither accepts nor rejects as a zero, assuming the p-adic Schanuel Conjecture, would falsify the claim of unconditional correctness or the termination guarantee.

read the original abstract

The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) has a zero term. Showing decidability of this problem is equivalent to giving an effective proof of the Skolem-Mahler-Lech Theorem, which asserts that a non-degenerate LRS has finitely many zeros. The latter result was proven over 90 years ago via an ineffective method showing that such an LRS has only finitely many $p$-adic zeros. In this paper we consider the problem of determining whether a given LRS has a $p$-adic zero, as well as the corresponding function problem of computing exact representations of all $p$-adic zeros. We present algorithms for both problems and report on their implementation. The output of the algorithms is unconditionally correct, and termination is guaranteed subject to the $p$-adic Schanuel Conjecture (a standard number-theoretic hypothesis concerning the $p$-adic exponential function). While these algorithms do not solve the Skolem Problem, they can be exploited to find natural-number and rational zeros under additional hypotheses. To illustrate this, we apply our results to show decidability of the Simultaneous Skolem Problem (determine whether two coprime linear recurrences have a common natural-number zero), again subject to the $p$-adic Schanuel Conjecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper presents algorithms for deciding whether a given linear recurrence sequence has a p-adic zero and for computing exact representations of all such zeros. The outputs of these algorithms are unconditionally correct, while termination is guaranteed only subject to the p-adic Schanuel Conjecture. The results are further applied to establish decidability of the Simultaneous Skolem Problem (whether two coprime LRS have a common natural-number zero) under the same hypothesis.

Significance. If the reduction and correctness arguments hold, this constitutes a meaningful advance by supplying the first effective procedures for the p-adic Skolem problem and its function variant. The explicit conditioning on the p-adic Schanuel Conjecture, combined with unconditional correctness of any produced output and a reported implementation, is a clear strength; it avoids hidden assumptions and permits practical use even when termination is not assured. The work also illustrates how the p-adic results can yield conditional decidability for natural-number variants, which is a useful bridge to related open problems.

minor comments (3)
  1. The preliminaries section would benefit from a short recap of the precise statement of the p-adic Schanuel Conjecture (including the relevant transcendence statement for the exponential) to make the termination argument self-contained for readers outside number theory.
  2. In the description of the Simultaneous Skolem application, the notion of 'coprime' linear recurrences should be defined or referenced explicitly, as the coprimality condition is used to reduce to the p-adic case.
  3. The experimental section reports successful runs on random instances but does not indicate the p-adic precision parameter or the timeout threshold used; adding these details would improve reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the recognition that the algorithms provide unconditionally correct outputs with termination conditioned on the p-adic Schanuel Conjecture, and for the recommendation of minor revision. The report contains no enumerated major comments, so we have no specific points requiring rebuttal or clarification at this stage. We will incorporate any minor editorial suggestions in the revised version.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via external conjecture

full rationale

The paper develops algorithms for the p-adic Skolem problem and the associated function problem of computing p-adic zeros of linear recurrence sequences. Outputs are stated to be unconditionally correct, while termination is conditioned on the external p-adic Schanuel Conjecture, which is a standard open number-theoretic hypothesis not derived from the paper's own definitions, fits, or prior self-citations. No load-bearing step reduces by construction to an input parameter, renames a known result, or relies on a uniqueness theorem imported from the authors' own earlier work. The derivation chain therefore remains independent of the target claims and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The primary additional assumption is the p-adic Schanuel Conjecture required for termination; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption p-adic Schanuel Conjecture
    Invoked to guarantee termination of the algorithms for computing p-adic zeros.

pith-pipeline@v0.9.0 · 5765 in / 1207 out tokens · 26565 ms · 2026-05-22T17:52:33.809021+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On the Subspace Orbit Problem and the Simultaneous Skolem Problem

    cs.DM 2026-01 unverdicted novelty 7.0

    Decidability of the Orbit Problem for logarithmic-dimensional target subspaces and Skolem-hardness for linear-dimensional targets.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · cited by 1 Pith paper

  1. [1]

    Completing the Picture for the Skolem Problem on Order-4 Linear Recurrence Sequences.TheoretiCS, Volume 4, Dec 2025.doi:10.46298/theoretics.25.28

    1 Piotr Bacik. Completing the Picture for the Skolem Problem on Order-4 Linear Recurrence Sequences.TheoretiCS, Volume 4, Dec 2025.doi:10.46298/theoretics.25.28. 2 Piotr Bacik, Joris Nieuwveld, and David Purser. Skolem tool, August

    work page doi:10.46298/theoretics.25.28 2025

  2. [2]

    3 Piotr Bacik, Joël Ouaknine, and James Worrell

    Tool available online athttps://skolem.mpi-sws.org/?padic.doi:10.5281/zenodo.16794130. 3 Piotr Bacik, Joël Ouaknine, and James Worrell. On the Complexity of the Skolem Problem at Low Orders, July 2025.doi:10.48550/arXiv.2507.11234. 4 Yuri Bilu. Skolem Problem for Linear Recurrence Sequences with 4 Dominant Roots (after Mignotte, Shorey, Tijdeman, Vereshch...

    work page doi:10.5281/zenodo.16794130 2025

  3. [3]

    6 Yuri Bilu, Florian Luca, Joris Nieuwveld, Joël Ouaknine, and James Worrell

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs.MFCS.2022.20. 6 Yuri Bilu, Florian Luca, Joris Nieuwveld, Joël Ouaknine, and James Worrell. Twisted rational zeros of linear recurrence sequences.Journal of the London Mathematical Society, 111(3), March 2025.doi:10.1112/jlms.70126. 7 Frank Calegari and Barry Mazur. Nearly ordinary Galoi...

    work page doi:10.4230/lipics.mfcs.2022.20 2022

  4. [4]

    9 Ventsislav Chonev, Joel Ouaknine, and James Worrell

    Association for Computing Machinery.doi: 10.1145/2488608.2488728. 9 Ventsislav Chonev, Joel Ouaknine, and James Worrell. On the zeros of exponential polynomials. J. ACM, 70(4), August 2023.doi:10.1145/3603543. 10 Thierry Combot. Computing linear relations between polynomial roots.Mathematics of Computation, March 2025.doi:10.1090/mcom/4081. 11 Keith Conra...

    work page doi:10.1145/2488608.2488728 2023

  5. [5]

    Cox, John Little, & Donal O’Shea

    doi: 10.1007/978-3-319-16721-3. 13 Graham Everest, Alf Van der Poorten, Igor Shparlinski, and Thomas Ward.Recurrence sequences. Number v. 104 in Mathematical surveys and monographs. American Mathematical Society, Providence, RI,

    work page doi:10.1007/978-3-319-16721-3

  6. [6]

    Everest and Alf J

    STACS 2026 51:22 On thep-adic Skolem Problem 14 Graham R. Everest and Alf J. van der Poorten. Factorisation in the ring of exponential polynomials.Proceedings of the American Mathematical Society, 125(5):1293–1298, July

    work page 2026

  7. [7]

    15 Ravindran Kannan and Richard J

    doi:10.1090/S0002-9939-97-03919-1. 15 Ravindran Kannan and Richard J. Lipton. Polynomial-time algorithm for the orbit problem. J. ACM, 33(4):808–821, August 1986.doi:10.1145/6490.6496. 16 Christer Lech. A note on recurring series.Arkiv för Matematik, 2(5):417–421, 8

    work page doi:10.1090/s0002-9939-97-03919-1 1986

  8. [8]

    17 Richard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, and James Worrell

    doi:10.1007/BF02590997. 17 Richard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, and James Worrell. On the Skolem Problem and the Skolem Conjecture. InProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1–9, Haifa Israel,

    work page doi:10.1007/bf02590997

  9. [9]

    Transducers of polynomial growth (invited talk)

    ACM.doi:10.1145/3531130.3533328. 18 Kurt Mahler. Eine arithmetische Eigenschaft der Taylor-Koeffizienten rationaler Funktionen. Proc. Akad. Wet. Amsterdam, 38:50–60,

    work page doi:10.1145/3531130.3533328

  10. [10]

    23 Alain Robert.A course in p-adic analysis

    doi: 10.1007/978-3-662-03983-0. 23 Alain Robert.A course in p-adic analysis. Number 198 in Graduate texts in mathematics. Springer, New York, NY, 2000.doi:10.1007/978-1-4757-3254-2. 24 W. H. Schikhof.CALCULUS, page 56–144. Cambridge Studies in Advanced Mathematics. Cambridge University Press,

    work page doi:10.1007/978-3-662-03983-0 2000

  11. [11]

    Mat.-Kongr., 163-188 (1935).,

    Skand. Mat.-Kongr., 163-188 (1935).,

    work page 1935

  12. [12]

    27 Robert Tijdeman, Maurice Mignotte, and Tarlok N. Shorey. The distance between terms of an algebraic recurrence sequence.Journal für die reine und angewandte Mathematik (Crelles Journal), 1984(349):63–76, May 1984.doi:10.1515/crll.1984.349.63. 28 Nikolay K. Vereshchagin. Occurrence of zero in a linear recursive sequence.Mathematical Notes of the Academy...

    work page doi:10.1515/crll.1984.349.63 1984