💻 computer science

Conjectural Decidability of the Skolem Problem

This paper establishes that large zeros of linear recurrence sequences are extremely sparse and, under a strengthened Cramér conjecture, likely non-existent, thereby providing a conditional proof for the decidability of the Skolem Problem and unconditionally identifying a universal Skolem set of density one.

Original authors: Florian Luca, Joël Ouaknine, James Worrell

Published 2026-07-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Florian Luca, Joël Ouaknine, James Worrell

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a very long, very predictable dance performed by a line of numbers. This isn't a random shuffle; it's a strict routine where every new number is created by adding up the previous few numbers in a specific recipe. Mathematicians call these "Linear Recurrence Sequences." They are the hidden rhythm behind everything from the spirals in a sunflower to the way interest grows in a bank account, and even the logic inside computer programs that check if a process will ever stop running.

The big mystery that has kept mathematicians up at night for decades is the "Skolem Problem." It asks a simple, deceptively easy question: Will this number dance ever hit a zero? Will one of the steps in the routine land exactly on the number 0? For some simple dances, we know the answer. But for the complex, high-energy routines, we have no idea if a zero is coming, or if the dancers will just keep spinning forever without ever stopping on that specific spot. Solving this isn't just a game of numbers; it's the key to unlocking whether we can automatically prove that computer programs will eventually finish their tasks or if they might get stuck in an infinite loop.

In this paper, the authors, Florian Luca, Joël Ouaknine, and James Worrell, tackle this decades-old puzzle by looking at the "biggest" zeros that could possibly exist. They introduce a new way of thinking about these sequences, defining a "large zero" as a zero that appears at a position so far out in the sequence that it is larger than a double exponential of the size of the recipe that created it. Think of it like this: if the recipe is a small instruction manual, a "large zero" would be a step number so huge it would take more time to count to it than the age of the universe.

The authors don't prove once and for all that these giant zeros don't exist, but they do something incredibly clever. They show that if we accept a famous guess about how prime numbers (the building blocks of math) are spaced out—known as the Cramér conjecture—then these "large zeros" simply cannot exist. Their argument is like a detective story: they show that if a large zero did exist, it would force the prime numbers around it to be spaced in a way that breaks the rules of how primes usually behave. Since the rules of prime spacing seem solid, the authors suggest that the large zeros are likely a ghost story; they probably aren't real.

Furthermore, even without relying on that guess about prime numbers, the authors prove a solid, unshakeable fact: if these large zeros do exist, they are incredibly rare. They are so sparse that if you picked a random number from the infinite list of all positive integers, the chance of it being a "large zero" is effectively zero. This discovery allows them to construct a "Universal Skolem Set," a special collection of numbers that covers almost everything in the sense of asymptotic density one. If you check for zeros only within this special set, you are guaranteed to find them if they exist at all.

So, what does this paper actually find? First, it establishes a mathematical boundary. It proves that the set of all possible "large zeros" has a density of zero, meaning they are vanishingly rare. This is a hard, unconditional proof. Second, it offers a conditional solution. It argues that if we assume the Cramér-Granville conjecture (a refined guess about prime number gaps) is true, then large zeros are impossible. If they are impossible, then the Skolem Problem is solved: we can simply check all the numbers up to that massive double-exponential boundary, and if we don't find a zero there, we know the sequence never has one.

The paper is careful not to claim victory yet. It admits that the boundary they found is so astronomically large that checking it with a computer is currently impossible. However, it shifts the problem from "Is it decidable?" to "Can we prove these giant zeros don't exist?" By showing that their existence would break the known laws of prime numbers, the authors provide a strong, logical reason to believe the Skolem Problem is indeed solvable, even if the final proof is still waiting to be written. They haven't solved the whole puzzle, but they've found the missing piece that makes the picture look complete.

Technical Summary: Conjectural Decidability of the Skolem Problem

Problem Statement
The Skolem Problem asks whether a given integer linear recurrence sequence (LRS) $\langle u_n \rangle_{n=0}^\infty$ contains a zero term. Despite being a central decision problem in computer science with applications in loop termination, formal languages, and probabilistic model checking, its decidability has remained open for decades. While the Skolem-Mahler-Lech theorem establishes that the set of zeros is a union of finitely many arithmetic progressions and a finite set, known proofs are ineffective; no algorithm is currently known to compute the finite set of zeros for a general non-degenerate LRS. Decidability is known only for restricted cases, such as LRS of order at most 4 or those with at most three dominant characteristic roots.

Methodology
The authors introduce a novel approach based on the concept of "large zeros." An integer $n$ is defined as a large zero of an LRS $u$ if it exceeds a double-exponential bound relative to the height $H_u$ of the sequence (where height is the maximum magnitude of the coefficients and initial values). Specifically, a zero is large if:
$n \ge \exp(\exp(10 H_u \log H_u))$

The methodology proceeds in two main directions:

Definition of "Good" and "Bad" Primes: The authors define a subset of prime numbers termed "bad primes" based on the divisibility properties of specific algebraic integers derived from the LRS. These algebraic integers are constructed using the Frobenius automorphism and the characteristic roots of the sequence. A prime $P$ is "bad" if it divides the norm of a non-zero algebraic integer constructed from a "small" LRS (one with height significantly smaller than the magnitude of the prime) and a specific permutation of its roots.
Density Analysis: Using bounds on the number of possible LRS and the magnitude of the associated algebraic integers, the authors prove that the set of bad primes has null density among all primes. Consequently, the set of "good primes" (the complement) has density one.
Heuristic Argument via Cramér's Conjecture: The paper employs a heuristic argument based on the Cramér-Granville conjecture regarding gaps between consecutive primes. The authors posit that if good primes behave statistically like ordinary primes, the gaps between them should satisfy a specific upper bound (Conjecture 4.2). They demonstrate that the existence of a large zero would necessitate an interval containing a number of good primes that violates this conjectured gap bound.

Key Contributions and Results

Conditional Decidability (Theorem 4.3):
The paper establishes that if the Cramér-Granville conjecture is strengthened to apply to the gaps between consecutive "good primes" (Conjecture 4.2), then large zeros do not exist. Specifically, there exists an absolute constant $C$ such that for any non-degenerate LRS with height $H_u \ge C$ , all zeros $n$ satisfy $n < \exp(\exp(10 H_u \log H_u))$ .
- Implication: If this conjecture holds, the Skolem Problem becomes decidable. The algorithm would involve checking for zeros only up to the double-exponential bound, as any zero beyond this range is impossible.
Unconditional Sparsity of Large Zeros (Theorem 5.1):
Without assuming any unproven conjectures, the authors prove that the set $L$ of all positive integers that can arise as large zeros of some non-degenerate LRS has null density. In fact, the counting function of this set satisfies $\#L(X) = O(X/(\log X)^B)$ for any constant $B > 0$ .
- Implication: This result relies on deep upper bounds on the number of zeros of non-degenerate algebraic LRS due to Amoroso and Viada, combined with the sparsity of bad primes.
Universal Skolem Set of Density One (Corollary 5.2):
As a direct consequence of the unconditional sparsity result, the set $S = \mathbb{N} \setminus L$ is a Universal Skolem Set of density one.
- Definition: A Universal Skolem Set is a recursive set $S$ such that there exists an algorithm to determine if an arbitrary LRS has a zero within $S$ .
- Significance: This answers an open question in the literature regarding the existence of Universal Skolem Sets with strictly positive density, and specifically, density one. The algorithm for $S$ works because any zero in $S$ must be a "small" zero, which can be effectively checked within the double-exponential bound.

Significance and Claims
The paper claims to provide a pathway to the decidability of the Skolem Problem, contingent upon a strengthening of the classical Cramér conjecture. The authors argue that the non-existence of large zeros is a highly probable heuristic truth, given the statistical distribution of good primes.

Furthermore, the paper establishes a significant unconditional result: the existence of a Universal Skolem Set of density one. This improves upon previous work which had only established sets of null density or positive density under specific restrictions (e.g., simple LRS).

The authors are modest regarding the practicality of the conditional decidability result. They explicitly note that even if the conjecture is proven and the constant $C$ is known, the resulting algorithm is currently impractical due to the immense magnitude of the double-exponential bound, which precludes reasonable implementation. The primary contribution is thus theoretical, narrowing the gap between the known decidability of special cases and the general problem, and providing a new structural understanding of the distribution of zeros in linear recurrence sequences.

Technical Summary: Conjectural Decidability of the Skolem Problem

More like this