Pith. sign in

REVIEW 2 major objections 4 minor 34 references

Conjectural Decidability of the Skolem Problem

T0 review · 2 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that, under a strengthening of the classical prime-gap conjecture, the Skolem Problem is decidable, and unconditionally that the 'large' zeros of linear recurrence sequences are a density-zero set.

desk verdict Attractive new framework for the Skolem Problem, but the central conditional theorem has a clear arithmetic mistake and the unconditional theorem rests on an unproved smallness claim; the advertised results don't follow as written. read the letter →

arxiv 2607.15510 v1 pith:3YWNRP2V submitted 2026-07-16 cs.DM math.NT

Florian Luca , Joël Ouaknine , James Worrell This is my paper · ORCID
classification cs.DMmath.NT MSC 11B3711N0503D40
keywords SkolemProblemlinearrecurrencesequencesdecidabilityprimegapsgoodprimesUniversalSetlargezerosalgebraicnorms
topics The Twin Prime Conjecture
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tackles the Skolem Problem — whether a given integer linear recurrence sequence has a zero term — a decidability question open for decades. It introduces the notion of a 'large' zero, one occurring at an index beyond a double exponential in the height of the recurrence, and claims two things. Conditionally on a strengthening of the classical prime-gap conjecture to a dense subset of primes called 'good' primes, large zeros cannot exist; this would give an effective bound on all zeros and hence make the problem decidable. Unconditionally, the paper proves that the set of indices that can be large zeros for some recurrence has density zero, which yields a Universal Skolem Set of density one — answering an open question. A sympathetic reader comes away with a concrete plan: verify the prime-gap hypothesis, or at least accept that the hard zeros are a negligible set.

What carries the argument

The load-bearing mechanism is the good-prime/bad-prime dichotomy. A prime P is bad at scale X if, for some LRS that is 'small' at level X (height H below roughly log log X divided by 10 log log log X), some non-zero exponential-polynomial expression v_{m,σ} has norm divisible by P. Good primes are the complement; they have density one among primes. The proof of Theorem 4.3 reduces a large zero n = P+m modulo a prime ideal above a good prime P, forcing P to divide a norm; if the norm is non-zero, P is bad, and if zero, a known upper bound on the number of zeros of algebraic linear recurrences says there cannot be enough such m. The density-one unconditional result uses the same reduction toge

What would settle it

Exhibit one non-degenerate integer LRS of height H with a zero at index n >= exp exp(10 H log H); the unconditional theorem would fall. A more targeted check: recompute the claimed contradiction in the proof of Theorem 4.3 with the corrected factor 3/4 — if the lower bound 10 H log H >= (3/2) log log Y no longer follows, the conditional proof has a gap that a single numerical counterexample to the derived inequality would expose.

Watch

Extended reading notes

Core claim

The paper's central claim is that the Skolem Problem reduces to a question about prime gaps. It defines good primes as those that are not 'bad', where badness means that a prime divides the algebraic norm of a certain exponential-polynomial expression associated to a small LRS around a potential large zero. For any large zero of an LRS, the paper shows there must be an interval around the zero containing far fewer good primes than the prime-gap conjecture would predict; if the conjecture holds for good primes, this contradiction rules out large zeros. The unconditional theorem shows that across all LRS, the set of large-zero indices is so sparse that its complement still allows an algorithm

Load-bearing premise

Both theorems assume that any LRS with a large zero at n is 'small' at scale n, meaning its height H satisfies H < log log n divided by 10 log log log n; Theorem 4.3 tries to derive this from the large-zero bound but the derivation contains an arithmetic error (a factor 3/2 that should be 3/4), and Theorem 5.1 simply asserts smallness. If smallness does not hold, the bad-prime/norm argument that powers both proofs collapses.

Editorial extensions

If this is right

  • If the strengthened prime-gap conjecture is ever proved, the Skolem Problem is decidable: every zero of a non-degenerate LRS lies before a double-exponential bound in its height, and finitely many small LRS can be handled by an oracle.
  • Unconditionally, the complement of the set of large zeros is a recursive Universal Skolem Set of density one, so for every LRS and every index outside that set, whether the LRS vanishes there can be computed.
  • The set of large zeros has strong quantitative sparsity: its counting function is O(X/(log X)^B) for any fixed B, making large zeros negligible for any asymptotic purpose.
  • The connection between recurrence zeros and prime gaps suggests that decision problems in computer science can hinge on fine statistical properties of primes.
  • The results imply a finite, if astronomically large, search bound for the zeros of any sufficiently high LRS, conditional on the prime-gap conjecture.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The arithmetic slip in the smallness derivation suggests a natural repair: if the intended factor 3/4 still yields a contradiction under a slightly larger constant in the prime-gap conjecture, the conditional result would survive the correction.
  • A singly exponential bound for the largest zero would be a much stronger statement; the paper itself notes that no family of LRS with singly exponential zeros is known, so the double-exponential threshold in the definition is likely a proof artifact.
  • The technique of filtering primes by divisibility properties of norms could be reused to obtain explicit bounds for other ineffective results in Diophantine approximation or automata theory.
  • If one only needs a practical termination prover, the density-one Universal Skolem Set already gives a sound-but-incomplete procedure that is correct for almost all time steps — an engineering payoff even before decidability is settled.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes a new approach to the Skolem Problem for integer linear recurrence sequences. It introduces the notion of a 'large zero' (a zero n with n ≥ exp exp(10H log H), where H is the height of the LRS) and defines 'good' and 'bad' primes in terms of divisibility properties of algebraic norms attached to LRS that are 'small' at a given dyadic level. The authors prove that bad primes have null density among all primes. Assuming a Cramér-Granville-type conjecture for good primes (Conjecture 4.2), Theorem 4.3 claims that large zeros do not exist for sufficiently high LRS, which would imply decidability of the Skolem Problem. Theorem 5.1 claims unconditionally that the set of all possible large zeros has null density, yielding a Universal Skolem Set of density one.

Significance. If correct, the paper would be a major contribution: a conditional resolution of the Skolem Problem under a plausible strengthening of the Cramér conjecture, and the first unconditional Universal Skolem Set of density one. The counting framework, the use of Amoroso-Viada bounds and Jia's theorem, and the general strategy are coherent and potentially reusable. However, both main theorems currently rest on a smallness assertion whose proof is invalid. The central claims are therefore not established in the submitted form.

major comments (2)
  1. [Section 4, proof of Theorem 4.3, inequality (7)] The algebraic manipulation is incorrect. From the negation of (7) one has H ≥ log log Y/(10 log log log Y) and log H ≥ 3/4 log log log Y, so 10H log H ≥ 3/4 log log Y, not 3/2 log log Y as printed. Consequently the lower bound obtained is exp exp(10H log H) ≥ exp((log Y)^{3/4}), which is far smaller than Y(log Y)^{1/2} and does not contradict n < 2Y. At the boundary H = log log Y/(10 log log log Y), a large zero with n ≈ Y is compatible with (6). Thus the proof does not establish that a large zero is small at level Y = X/2. Since this smallness is what makes expression (8) fall under the definition of a bad prime, the subsequent contradiction with Conjecture 4.2 collapses.
  2. [Section 5, proof of Theorem 5.1] The step 'using the same notation and reasoning as in Thm. 4.3' is insufficient for the conclusion 'If the above expression is non-zero, then P is a bad prime.' Definition 3.1 requires the LRS u to be small at the relevant level X. No proof is given that a large zero n (with n ≥ exp exp(10H log H)) implies this smallness; as in Theorem 4.3, H can sit at the smallness threshold while satisfying the large-zero bound. Hence expression (9) non-zero does not imply P ∈ P_bad, and the bound #P_bad(X) = O(X^{2/3}) cannot be applied. The null-density claim and Corollary 5.2 are therefore unsupported. The gap is repairable in principle by strengthening the constant in (2) (any c > 10 suffices), but the current text does not contain the needed argument.
minor comments (4)
  1. [Footnote 9 and Eq. (2)] The constant 10 is explicitly chosen ad hoc; given the arithmetic error in Thm 4.3, it is too small for the claimed implication. Please either prove smallness for c = 10 or change the definition and all dependent statements accordingly.
  2. [Section 5, proof of Theorem 5.1] The chain leading to n < exp exp(9H log H) relies on the inequality n < (n^{1/19}/(log n)^2)^{20} for sufficiently large n. This should be stated and justified explicitly, since it is not immediate.
  3. [Corollary 5.2] The claim that L is recursive should be justified: for a given n, the condition n ≥ exp exp(10H log H) bounds H, so only finitely many LRS need be checked.
  4. [Introduction] Typo: 'succeded' should be 'succeeded'.

Circularity Check

0 steps flagged · score 2.0 of 10

No material circularity; minor self-citation context only

full rationale

No step in the derivation is equivalent to its inputs by construction. Theorem 4.3 is a genuine conditional proof: Conjecture 4.2 supplies a gap property for 'good' primes, and good primes are defined by a divisibility condition on norms of exponential-polynomial expressions, not by the absence of large zeros. The later reduction of a large zero to the presence of a bad prime is an application of Definition 3.1, not a renaming. Theorem 5.1 and Corollary 5.2 similarly use external results (Amoroso–Viada, Jia) and the recursive definition of L. The self-citations [20-24] are contextual and do not carry the argument; the double-exponential threshold in (2) is acknowledged in footnote 9 as a choice made to allow the argument, but a definitional threshold is not a fitted parameter relabeled as a prediction. The obligation to flag unsupported steps is met: the smallness assertion in Thm 4.3 relies on an algebraic inequality that appears to be erroneous (the factor is 3/4, not 3/2), and Thm 5.1 invokes 'the same reasoning' without proving smallness at level X. These are correctness gaps, not circularity; they do not make the conclusion identical to the assumptions. Hence circularity score 2, reflecting only non-load-bearing self-citations and definitional choices, not circular derivation.

Assumptions & free parameters 3 free parameters · 5 assumptions · 2 invented entities

The central claims rest on a double-exponential threshold whose constants are chosen ad hoc (footnote 9), on two unproved Cramér-type conjectures for the conditional part, and on external theorems (Amoroso-Viada, Jia, PNT). No data fitting is involved, so the circularity burden is low, but the parameter choices and unproved conjectures carry significant load.

free parameters (3)
  • constant 10 in large-zero bound (2) = 10
    The bound n < exp exp(10 H_u log H_u) uses a hand-chosen constant. Footnote 9 explicitly states this expression was chosen to make the mathematical argument go through.
  • constant 10 in smallness definition = 10
    The definition of "small at level X" uses H < log log X / (10 log log log X); this constant is chosen to fit the proof structure, and the proof's validity depends on it.
  • absolute height threshold C
    The paper postulates an absolute constant C such that all LRS have height > C. C is not specified; its value would depend on the final form of Conjecture 4.2.
assumptions (5)
  • domain assumption Cramér-Granville conjecture (Conjecture 4.1)
    Unproved number-theoretic conjecture used to motivate Conjecture 4.2 about good-prime gaps.
  • domain assumption Strengthened Cramér conjecture for good primes (Conjecture 4.2)
    The main conditional hypothesis of Theorem 4.3; no proof or independent evidence is provided.
  • standard math Amoroso-Viada bound on zeros of LRS (Ref [33])
    External theorem used to bound the number of m for which expression (8) or (9) can vanish.
  • standard math Jia's short-interval prime theorem (Ref [34])
    External theorem used in Theorem 5.1 to ensure most intervals I_n contain many primes.
  • standard math Prime number theorem
    Used to conclude that good primes have density one among all primes, since bad primes are X^{2/3}.
invented entities (2)
  • good primes / bad primes
    purpose: A partition of primes designed to detect divisibility by exponential-polynomial expressions derived from LRS; used to contradict Cramér-type prime gaps near large zeros.
    New mathematical objects defined in Definition 3.1; their properties are proven internally, and there is no external falsifiable prediction attached to them.
  • large zeros
    purpose: Zeros occurring at index beyond exp exp(10 H log H); the paper proves they are sparse and conditionally non-existent.
    A newly defined notion (Section 3, Eq. (2)); not independently observable, and the threshold constant is admitted to be chosen for the proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Conjectural Decidability of the Skolem Problem." pith.science (2026). https://pith.science/paper/3YWNRP2V

@misc{pith2026260715510,
  author       = {Pith},
  title        = {Pith review of: Conjectural Decidability of the Skolem Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3YWNRP2V}},
  note         = {Machine review of arXiv:2607.15510}
}
read the original abstract

The Skolem Problem asks to determine whether a given integer linear recurrence sequence (LRS) has a zero term. This problem, whose decidability has been open for many decades, arises across a wide range of topics in computer science, including loop termination, formal languages, automata theory, and probabilistic model checking, amongst many others. In the present paper, we introduce a notion of "large" zeros of (non-degenerate) linear recurrence sequences, i.e., zeros occurring at an index larger than a double exponential of the magnitude of the data defining the given LRS. We establish two main results. First, we define an infinite set of prime numbers, termed "good", having density one amongst all prime numbers, with the following property: for any large zero of a given LRS, there is an interval around the large zero together with an upper bound on the number of good primes possibly present in that interval. The bound in question is much lower than one would expect if good primes were distributed similarly as ordinary prime numbers, as per the Cram\'er model in number theory. We therefore conclude, conditionally on a strengthening of the classical Cram\'er conjecture, that large zeros do not exist, which would entail decidability of the Skolem Problem. Second, we show unconditionally that large zeros are very sparse: the set of positive integers that can possibly arise as large zeros of some LRS has null density. This in turn immediately yields a Universal Skolem Set of density one, answering a question left open in the literature.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 1 linked inside Pith

  1. [1]

    Skolem, Ein Verfahren zur Behandlung gewisser exponentialer Gle- ichungen, in: Comptes rendus du congrès des mathématiciens scandi- naves, 1934

    T. Skolem, Ein Verfahren zur Behandlung gewisser exponentialer Gle- ichungen, in: Comptes rendus du congrès des mathématiciens scandi- naves, 1934

    1934

  2. [2]

    Mahler, Eine arithmetische Eigenschaft der Taylor Koeffizienten ra- tionaler Funktionen, Proc

    K. Mahler, Eine arithmetische Eigenschaft der Taylor Koeffizienten ra- tionaler Funktionen, Proc. Akad. Wet. Amsterdam 38 (1935)

    1935

  3. [3]

    Lech, A note on recurring series, Ark

    C. Lech, A note on recurring series, Ark. Mat. 2 (1953)

    1953

  4. [4]

    Everest, A

    G. Everest, A. van der Poorten, I. Shparlinski, T. Ward, Recurrence Sequences, American Mathematical Society, 2003

    2003

  5. [5]

    Kauers, P

    M. Kauers, P. Paule, The Concrete Tetrahedron — Symbolic Sums, Re- currenceEquations, GeneratingFunctions, AsymptoticEstimates, Texts & Monographs in Symbolic Computation, Springer, 2011

    2011

  6. [6]

    R. P. Stanley, Enumerative combinatorics, Cambridge studies in ad- vanced mathematics Volume 1, 2nd Edition (2011). 17

    2011

  7. [7]

    Berstel, C

    J. Berstel, C. Reutenauer, Noncommutative Rational Series with Appli- cations, Cambridge University Press, 2010

    2010

  8. [8]

    Tao, Structure and randomness: pages from year one of a mathemat- ical blog, American Mathematical Society, 2008

    T. Tao, Structure and randomness: pages from year one of a mathemat- ical blog, American Mathematical Society, 2008

    2008

Show all 34 references
  1. [9]

    Rozenberg, A

    G. Rozenberg, A. Salomaa, Cornerstones of Undecidability, Prentice Hall, 1994

    1994

  2. [10]

    Beauquier, A

    D. Beauquier, A. M. Rabinovich, A. Slissenko, A logic of probability with decidable model checking, J. Log. Comput. 16 (4) (2006)

    2006

  3. [11]

    Piribauer, C

    J. Piribauer, C. Baier, On Skolem-hardness and saturation points in Markov decision processes, in: ICALP, Vol. 168 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 138:1–138:17

    2020

  4. [12]

    Blondel, J

    V. Blondel, J. Tsitsiklis, A survey of computational complexity results in systems and control, Automatica 36 (9) (2000) 1249–1274

    2000

  5. [13]

    Fijalkow, J

    N. Fijalkow, J. Ouaknine, A. Pouly, J. S. Pinto, J. Worrell, On the decidability of reachability in linear time-invariant systems, in: HSCC, ACM, 2019, pp. 77–86

    2019

  6. [14]

    Ouaknine, J

    J. Ouaknine, J. Worrell, On linear recurrence sequences and loop termi- nation, ACM SIGLOG News 2 (2) (2015) 4–13

    2015

  7. [15]

    J.-Y. Cai, R. J. Lipton, Y. Zalcstein, The complexity of the A B C problem, SIAM J. Comput. 29 (6) (2000)

    2000

  8. [16]

    Kannan, R

    R. Kannan, R. J. Lipton, Polynomial-time algorithm for the orbit prob- lem, JACM 33 (4) (1986)

    1986

  9. [17]

    Mignotte, T

    M. Mignotte, T. Shorey, R. Tijdeman, The distance between terms of an algebraic recurrence sequence, J. für die reine und angewandte Math. 349 (1984)

    1984

  10. [18]

    N. K. Vereshchagin, The problem of appearance of a zero in a linear recurrence sequence (in Russian), Mat. Zametki 38 (2) (1985)

    1985

  11. [19]

    Akshay, N

    S. Akshay, N. Balaji, A. Murhekar, R. Varma, N. Vyas, Near-optimal complexity bounds for fragments of the Skolem problem, in: STACS, Vol. 154 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 37:1–37:18. 18

    2020

  12. [20]

    Lipton, F

    R. Lipton, F. Luca, J. Nieuwveld, J. Ouaknine, D. Purser, J. Worrell, On the Skolem problem and the Skolem conjecture, in: LICS, ACM, 2022, pp. 5:1–5:9

    2022

  13. [21]

    Y. Bilu, F. Luca, J. Nieuwveld, J. Ouaknine, D. Purser, J. Worrell, Skolem meets Schanuel, in: MFCS, Vol. 241 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 20:1–20:15

    2022

  14. [22]

    F.Luca, J.Ouaknine, J.Worrell, UniversalSkolemsets, in: LICS,IEEE, 2021, pp. 1–6

    2021

  15. [23]

    F. Luca, J. Ouaknine, J. Worrell, A universal Skolem set of positive lower density, in: MFCS, Vol. 241 of LIPIcs, Schloss Dagstuhl - Leibniz- Zentrum für Informatik, 2022, pp. 73:1–73:12

    2022

  16. [24]

    F. Luca, J. Maynard, A. Noubissie, J. Ouaknine, J. Worrell, Skolem meets bateman-horn, CoRR abs/2308.01152 (2023)

    2023 arXiv

  17. [25]

    Cramér, On the order of magnitude of the difference between consec- utive prime numbers, Acta Arith

    H. Cramér, On the order of magnitude of the difference between consec- utive prime numbers, Acta Arith. 2 (1936) 23–46

    1936

  18. [26]

    Oliveira e Silva, S

    T. Oliveira e Silva, S. Herzog, S. Pardi, Empirical verification of the even Goldbach conjecture and computation of prime gaps up to4·1018, Math. Comp. 83 (288) (2014) 2033–2060

    2014

  19. [27]

    R. C. Baker, G. Harman, J. Pintz, The difference between consecu- tive primes, ii, Proceedings of the London Mathematical Society 83 (3) (2001) 532–562

    2001

  20. [28]

    K. Ford, B. Green, S. Konyagin, J. Maynard, T. Tao, Long gaps between primes, Journal of the American Mathematical Society 31 (1) (2018) 65– 105

    2018

  21. [29]

    Granville, Harald Cramér and the distribution of prime numbers, Scandinavian Actuarial Journal 1995 (1) (1995) 12–28

    A. Granville, Harald Cramér and the distribution of prime numbers, Scandinavian Actuarial Journal 1995 (1) (1995) 12–28

    1995

  22. [30]

    Fröhlich, M

    A. Fröhlich, M. J. Taylor, Algebraic Number Theory, Vol. 27 of Cam- bridge Studies in Advanced Mathematics, Cambridge University Press, 1993

    1993

  23. [31]

    Odlyzko, M

    A. Odlyzko, M. Rubinstein, M. Wolf, Jumping champions, Experimental Mathematics 8 (2) (1999) 107–118. 19

    1999

  24. [32]

    T. R. Nicely, New maximal prime gaps and first occurrences, Math. Comput. 68 (227) (1999) 1311–1315

    1999

  25. [33]

    Amoroso, E

    F. Amoroso, E. Viada, On the zeros of linear recurrence sequences, Acta Arith. 147 (4) (2011) 387–396

    2011

  26. [34]

    Jia, Almost all short intervals containing prime numbers, Acta Arith

    C. Jia, Almost all short intervals containing prime numbers, Acta Arith. 76 (1) (1996) 21–84. 20

    1996

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.