🔢 mathematics

Skolem Meets Bateman-Horn

This paper advances the decidability of the Skolem Problem by constructing a Universal Skolem Set with a lower density of at least 1/8, which is shown to have density 1 under Martin's uniform formulation of the Bateman-Horn conjecture.

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

Published 2026-08-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Florian Luca, James Maynard, Armand Noubissie, 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

The Mystery of the Silent Numbers

Imagine a machine that generates a list of numbers, where each new number is created by adding up a specific recipe of the numbers that came before it. This is called a linear recurrence sequence. Think of it like a musical loop where every note is a mix of the previous few notes. Sometimes, this musical loop hits a "zero"—a moment of silence. The big question in computer science and math, known as the Skolem Problem, is: Can we always predict if and when that silence will happen?

This isn't just a puzzle for mathematicians; it's the "halting problem" for certain types of computer programs. If we can't tell if a program will ever hit a zero, we can't be sure if it will ever stop running or get stuck in an infinite loop. For decades, we've been able to solve this for very simple machines (those with short recipes), but for more complex ones, the answer has remained a stubborn mystery. We know the zeros exist in a predictable pattern, but we have no effective way to find them or even know if they exist at all. It's like knowing a treasure map has a spot marked "X," but having no compass to find it.

The New Map and the Magic Garden

In this paper, a team of researchers takes a fresh approach to this decades-old mystery. Instead of trying to find every zero for every possible sequence, they ask a slightly different question: Can we find a special, giant garden of numbers where we can guarantee to find the zeros if they are hiding there? They call this a Universal Skolem Set.

The authors successfully built such a garden. They proved that this garden is huge—it contains at least 1/8 of all the positive integers. This means that for any complex number-generating machine, if it ever produces a zero, there is a very good chance that zero will fall on a number inside this special garden. Furthermore, they showed that if we accept a famous, unproven guess about how prime numbers are distributed (called the Bateman–Horn conjecture), then this garden actually covers 100% of the integers. In other words, if that guess is true, we can find the zeros for every sequence.

How They Built the Garden

To build this garden, the authors used a clever trick involving prime numbers. They defined their garden as the set of numbers that can be written in a very specific way: a number $n$ is in the garden if it can be formed by multiplying a large prime number by a smaller prime number and adding a tiny bit of extra value.

Think of it like a lock and key system. The researchers realized that if a sequence hits a zero at a number $n$ in their garden, that zero creates a "companion equation"—a mathematical shadow of the original problem. Because the numbers in the garden are built from primes in a specific way, these shadows become much easier to analyze.

The team used powerful mathematical tools (developed by other mathematicians like Schlickewei, Schmidt, Amoroso, and Viada) that act like a sieve. These tools can count how many times a specific type of equation can be solved. The authors showed that if a number $n$ is in their garden, it must have many different ways to be built from primes. However, if the sequence hits a zero at $n$ , the math says there can only be a limited number of ways to build it.

This creates a conflict. If the number $n$ is too big, it would need to be built in more ways than the math allows for a zero to exist. Therefore, any zero found in this garden must be relatively small. By calculating exactly how small, the authors created a "stop sign" for the search. They proved that for any sequence, we only need to check numbers up to a specific, calculable limit within their garden. If the sequence hasn't hit zero by then, it never will (at least within that garden).

The Results: A Big Step Forward

The paper makes two major claims:

Unconditionally (without needing any unproven guesses): The authors constructed a Universal Skolem Set that has a lower density of at least 1/8. This means that no matter what, this set is large enough to be useful. It proves that we can effectively decide if a sequence has a zero within this specific subset of numbers.
Conditionally (assuming the Bateman–Horn conjecture): If we assume a standard hypothesis about how prime numbers appear in polynomial formulas, then this set actually has a density of 1. This would mean the set includes almost every single integer, effectively solving the Skolem Problem for all practical purposes.

The authors are careful to note that they haven't solved the Skolem Problem completely for all numbers yet (since they don't know if the Bateman–Horn conjecture is true, and their set might miss some numbers even if it's 1/8 dense). However, they have successfully bridged the gap between the known world of small sequences and the unknown world of complex ones. They've shown that by looking at numbers through the lens of prime number distributions, we can find a massive, effective territory where the mystery of the "silent numbers" can finally be solved.

Technical Summary: Skolem Meets Bateman–Horn

1. The Problem: The Skolem Problem

The Skolem Problem asks whether a given integer linear recurrence sequence (LRS) contains a zero term. An LRS $u = \langle u_n \rangle_{n=0}^\infty$ satisfies a recurrence of the form $u_{n+k} = a_0 u_{n+k-1} + \dots + a_{k-1} u_n$ with integer coefficients. Equivalently, $u_n$ admits a closed form $u_n = \sum_{i=1}^s Q_i(n) \alpha_i^n$ , where $\alpha_i$ are the roots of the characteristic polynomial and $Q_i$ are polynomials.

While the Skolem-Mahler-Lech theorem establishes that the set of zeros of a non-degenerate LRS is a finite union of arithmetic progressions, the problem of deciding whether such a set is non-empty remains open. The state of the art, established four decades ago, provides a decision procedure only for recurrences of order at most 4, relying on Baker's theorem on linear forms in logarithms. For general orders, the problem is undecidable in the general case of degenerate sequences, but the non-degenerate case remains a fundamental open problem in theoretical computer science, often characterized as the "halting problem for linear automata."

2. Methodology: Universal Skolem Sets and Diophantine Bounds

The paper adopts the framework of Universal Skolem Sets, introduced in prior work [LOW21, LOW22]. A set $S \subseteq \mathbb{N}$ is a Universal Skolem Set if there exists an effective procedure that, given a non-degenerate LRS, computes the finite set of its zeros lying within $S$ . Proving that $\mathbb{N}$ itself is a Universal Skolem Set would solve the Skolem Problem.

The authors construct a specific Universal Skolem Set $S$ by leveraging a novel transfer principle:

Representation via Primes: The set $S$ consists of integers $n$ that admit many representations of the form $n = Pq + a$, where $P$ and $q$ are primes, and $a$ is small relative to $n$ .
Companion Equations: If $u_n = 0$ for such an $n$ , substituting $n = Pq + a$ into the closed form and applying a generalization of Fermat's Little Theorem (via Frobenius automorphisms) yields a "companion equation" of the form $\sum Q_i(a) \sigma(\alpha_i)^q \alpha_i^a = 0$ .
Bounding Solutions: The core technical innovation is using deep results on the number of solutions to exponential-polynomial Diophantine equations (specifically from Schlickewei, Schmidt, Amoroso, and Viada) to bound the number of solutions $(q, a)$ to these companion equations.
Magnitude Transfer: By ensuring that elements in $S$ have many representations (specifically more than a slowly diverging function $\Phi(n)$ ), but the companion equations can only have a bounded number of solutions, the authors derive an explicit upper bound on the magnitude of any zero $n \in S$ . If $n$ were larger than this bound, the number of required representations would exceed the maximum possible solutions to the companion equation, a contradiction.

3. Key Contributions

A. Construction of a Universal Skolem Set with Positive Lower Density

The paper constructs a set $S$ that is a Universal Skolem Set for all non-degenerate LRS (removing the restriction to "simple" LRS found in previous work [LOW22]).

Explicit Bounds: The authors provide an explicit upper bound on the magnitude of any zero of a given LRS that lies in $S$ . This bound depends only on the order $k$ of the recurrence and the height of its coefficients.
Technical Adaptation: To handle non-simple LRS (where characteristic roots have multiplicities), the authors adapt techniques from [AV09, ESS02, SS00] rather than using existing bounds "off the shelf." This involves a detailed induction on the number of summands in the companion equations, utilizing the non-correlation of representations to separate solutions.

B. Density Results

The paper establishes the density of the constructed set $S$ :

Unconditional Result: The set $S$ has a lower density of at least $1/8$ . This is proven using the standard two-dimensional Brun–Selberg upper-bound sieve.
Conditional Result: Subject to Martin's uniform formulation of the Bateman–Horn conjecture (Hypothesis UH), the set $S$ has density 1. This hypothesis concerns the frequency of prime values in systems of polynomials and generalizes the Hardy-Littlewood twin prime conjecture.

4. Results and Significance

The primary result is Theorem 9, which states that for any non-degenerate LRS of order $k$ , if $u_n = 0$ and $n \in S$ , then $n$ is bounded by an explicit function $T(k, A)$ , where $A$ is the maximum absolute value of the initial terms and coefficients. This effectively solves the Skolem Problem for the subset $S$ .

Significance claimed by the authors:

New Direction: The paper proposes a new direction for the Skolem Problem: transferring upper bounds on the multiplicity of solutions to exponential Diophantine equations into upper bounds on the magnitude of solutions.
Connection to Number Theory: It establishes a concrete link between the decidability of the Skolem Problem and classical questions regarding the distribution of prime numbers (specifically the Bateman–Horn conjecture), distinct from the $p$ -adic techniques used in recent conditional decidability results [BLN+22].
Progress on Decidability: While not solving the Skolem Problem for all integers unconditionally, the construction of a Universal Skolem Set with positive lower density (and density 1 under a standard conjecture) represents a significant step toward the full decidability of the problem.

The paper concludes that while standard heuristics suggest $S$ does not contain all integers (due to the existence of integers with no prime representations), the set $S$ is sufficiently dense to make the problem decidable for a "large" portion of the natural numbers, contingent on the Bateman–Horn conjecture for full coverage.