🔢 mathematics

On the $p$ -adic Skolem Problem

This paper presents algorithms for determining and computing all $p$ -adic zeros of linear recurrence sequences, which are unconditionally correct and terminate under the $p$ -adic Schanuel Conjecture, thereby enabling the decidability of the Simultaneous Skolem Problem for coprime sequences under the same hypothesis.

Original authors: Piotr Bacik, Joël Ouaknine, David Purser, James Worrell

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Piotr Bacik, Joël Ouaknine, David Purser, 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

The Big Picture: The "Missing Zero" Hunt

Imagine you have a machine that spits out a never-ending list of numbers based on a simple rule (like a recipe). For example, "add the last two numbers to get the next one" (the Fibonacci sequence). This is called a Linear Recurrence Sequence (LRS).

The famous Skolem Problem asks a simple question: Does this list ever contain the number zero?

For over 90 years, mathematicians have known that if the list isn't "broken" (mathematically called "non-degenerate"), it can only have a finite number of zeros. However, they have never been able to build a guaranteed computer program that can say "Yes, it hits zero" or "No, it never does" for every possible recipe. It's like trying to find a specific grain of sand on a beach, but you don't have a map, and you don't know if the beach is even big enough to hold the sand.

The New Approach: Looking Through a "Magic Lens"

This paper doesn't solve the original problem directly. Instead, the authors introduce a new way of looking at the numbers using p-adic numbers.

The Analogy: The Zoom Lens
Think of the standard number line (1, 2, 3...) as a wide-angle photo. You can see the big picture, but the details are blurry.
The p-adic lens is a magical microscope that zooms in on the numbers based on how they are divisible by a specific prime number (like 3, 5, or 7).

In our normal world, 100 is close to 101.
In the 3-adic world, 100 and 101 might be very far apart, while 100 and 103 might be very close because they share a factor of 3.

The authors realized that if you look at the number sequence through this p-adic microscope, the "zeros" (where the sequence hits zero) behave very nicely. They form a finite, countable set that can be mapped out precisely.

The Main Discovery: The "Rational Zero" Rule

The paper's biggest breakthrough is a rule about multiplicity (how "deep" a zero is).

Imagine a ball rolling down a hill.

Simple Zero: The ball rolls past the bottom of the valley and keeps going. It crosses the zero line once.
Double Zero: The ball rolls down, stops exactly at the bottom, and then rolls back up. It touches zero but doesn't cross it in the usual way.

The authors proved (assuming a famous mathematical guess called the p-adic Schanuel Conjecture) that if a sequence has a "deep" zero (multiplicity 2 or more) in this p-adic world, that zero must be a rational number (a fraction like 1/2 or -3/4).

Why is this a game-changer?
If you are searching for zeros and you find a "deep" one, you don't need to guess. You just check all the fractions. If you find a "shallow" one, you can use a mathematical tool called Hensel's Lemma (think of it as a GPS that refines your location step-by-step) to find it exactly.

This allows them to build an algorithm that always stops. It searches for simple zeros using the GPS method and deep zeros by checking fractions. It guarantees it won't run forever.

The Results: What They Actually Did

They Built a Tool: They wrote a computer program (available online) that takes a sequence recipe and finds all its p-adic zeros.
It Works (with a caveat): The tool is 100% correct when it finishes. It will finish, provided the "p-adic Schanuel Conjecture" is true. (This is a standard assumption in this field, similar to assuming the Riemann Hypothesis in other areas).
Solving a Harder Puzzle: They used this tool to solve the Simultaneous Skolem Problem. This asks: "Do two different sequences ever hit zero at the same time?" If the two sequences are "coprime" (they don't share a hidden common structure), the authors proved this is now solvable.
Real-World Testing: They tested their tool on thousands of random sequences.
- It found zeros very quickly for sequences of "order" 2, 3, and 4 (how complex the recipe is).
- It started to slow down for order 5 and 6, but it still worked.
- They found that "deep" zeros (multiplicity > 1) are extremely rare in random sequences.

Important Limitations (What They Didn't Do)

They didn't solve the original Skolem Problem yet. Just because they can find p-adic zeros doesn't automatically tell us if the sequence hits zero in the normal integer world. Sometimes a p-adic zero looks like a fraction (e.g., 1/2), which isn't a whole number.
The "Twisted" Zeros: Sometimes the p-adic lens creates "fake" zeros that look like they should be integers but aren't (due to how square roots are chosen in that specific lens). The authors have to be careful to filter these out.
No Clinical or Future Applications: The paper is purely theoretical computer science and number theory. It does not claim to help with cryptography, physics, medicine, or engineering. It is a tool for mathematicians to understand the structure of number sequences.

Summary in One Sentence

The authors created a new mathematical "microscope" (p-adic analysis) and a guaranteed search algorithm that can find all the zeros of a number sequence in this new world, proving that if a sequence has a "deep" zero, it must be a simple fraction, which allows computers to solve specific, previously unsolvable versions of the zero-finding problem.

Technical Summary: On the p-adic Skolem Problem

1. Problem Statement
The Skolem Problem asks whether a given linear recurrence sequence (LRS) of integers has a zero term. While the Skolem-Mahler-Lech Theorem (proven over 90 years ago) establishes that the zero set of a non-degenerate LRS consists of a finite set and finitely many arithmetic progressions, the proof is ineffective; it does not provide an algorithm to determine if such a zero exists. Consequently, the decidability of the Skolem Problem remains a major open question in theoretical computer science.

This paper addresses a relaxation of the problem: the p-adic Skolem Problem. Instead of seeking zeros in the natural numbers ( $\mathbb{N}$ ), the authors investigate whether an LRS has a zero in the ring of p-adic integers ( $\mathbb{Z}_p$ ) for a given prime $p$ . Furthermore, they address the corresponding function problem: computing exact representations of all such p-adic zeros. While solving the p-adic version does not immediately solve the original Skolem Problem (as p-adic zeros may not correspond to integer zeros), the authors demonstrate that working p-adically offers a practical approach to finding integer zeros and enables decidability results for related problems under standard number-theoretic hypotheses.

2. Methodology and Algorithmic Framework
The core methodology involves extending an LRS $u = \langle u_n \rangle$ to a continuous, analytic function $f: \mathbb{Z}_p \to \mathbb{Z}_p$ . This is achieved via p-adic interpolation:

Given an LRS with characteristic roots $\lambda_i$ , the sequence is decomposed into subsequences $u_{Nn+\ell}$ (for $0 \le \ell < N$ ) that can be represented as analytic functions $f_\ell(x)$ involving p-adic exponentials and logarithms.
The problem of finding zeros of the LRS reduces to finding zeros of these analytic functions $f_\ell$ within $\mathbb{Z}_p$ .

The proposed algorithm combines two distinct search strategies to ensure termination and correctness:

Hensel's Lemma Search: The algorithm performs a brute-force search over residue classes modulo $p^r$ (for increasing $r$ ). If a residue class contains a simple zero (where the valuation of the function is strictly greater than twice the valuation of its derivative), Hensel's Lemma guarantees a unique zero in that class, which can be approximated to arbitrary precision.
Rational Enumeration: The algorithm faces a challenge with multiple zeros (multiplicity $\ge 2$ ), where Hensel's condition may never be met, potentially causing an infinite loop. To resolve this, the authors rely on a key technical lemma derived from the p-adic Schanuel Conjecture. This lemma proves that for irreducible exponential polynomials, any common zero of multiplicity $\ge 2$ must be rational. Consequently, the algorithm runs a parallel search enumerating rational numbers to detect these multiple zeros.

The algorithm outputs a finite representation of all p-adic zeros (as discs in $\mathbb{Z}_p$ ) and terminates subject to the p-adic Schanuel Conjecture.

3. Key Contributions and Theoretical Results
The paper presents the following main results:

Decidability of the p-adic Skolem Problem: Assuming the p-adic Schanuel Conjecture, the decision problem $SP(\mathbb{Z}_p)$ (does a p-adic zero exist?) is decidable, and the function problem $FSP(\mathbb{Z}_p)$ (computing all p-adic zeros) is computable.
Technical Lemma on Multiple Zeros: The authors prove that if two coprime exponential polynomials share a p-adic zero, that zero must be rational (under the p-adic Schanuel Conjecture). This result is crucial for ensuring the termination of the algorithm by bounding the search for multiple zeros to the set of rational numbers.
Decidability of the Simultaneous Skolem Problem: As a direct application of the above lemma, the paper proves that the Simultaneous Skolem Problem (determining if two coprime LRS share a common integer zero) is decidable, again assuming the p-adic Schanuel Conjecture. This is achieved by constructing a new LRS $w_n = v_n^2 + p u_n^2$ and analyzing its p-adic zeros.
Implementation: The authors implemented the algorithm in the "Skolem tool" (integrated with SageMath). The tool handles cases where the characteristic polynomial splits in $\mathbb{Z}_p$ .

4. Experimental Results
The authors report on experiments using randomly generated LRS of orders 2 through 7.

Hensel-only Algorithm: A simplified version of the algorithm, assuming all zeros are simple (multiplicity 1), successfully solved nearly 100% of instances up to order 4 and roughly 50% of order 5 within a 60-second timeout.
Full Algorithm: The complete algorithm, which includes the rational enumeration step, showed similar success rates but with increased runtime (1.3x to 1.5x slower than the simplified version for orders 2–4).
Observations: In the tested dataset, no LRS with a zero of multiplicity greater than 1 was found, suggesting such cases are rare in practice. The tool effectively identifies integer and rational zeros by matching p-adic expansions to rational approximations.

5. Significance and Limitations
The paper claims that while the proposed algorithms do not solve the general Skolem Problem (as they cannot always distinguish between rational and irrational p-adic zeros, nor guarantee that a p-adic zero corresponds to an integer zero), they provide a powerful practical tool.

Practical Utility: The p-adic approach serves as an effective heuristic for finding integer zeros of LRS.
Theoretical Advancement: The work establishes a conditional decidability for the Simultaneous Skolem Problem, a significant step in the broader landscape of LRS decidability.
Correctness vs. Termination: The authors emphasize that the output of the algorithm is unconditionally correct whenever it terminates. The p-adic Schanuel Conjecture is required solely to guarantee termination (by ensuring the rational search catches all multiple zeros), not for the correctness of the identified zeros.

The paper concludes that the p-adic perspective offers a viable path for analyzing LRS zeros, bridging the gap between ineffective theoretical proofs and effective computational methods under standard number-theoretic assumptions.