The Skolem Problem in rings of positive characteristic

This paper establishes the decidability of the Skolem Problem for linear recurrence sequences in finitely generated commutative rings of positive characteristic by proving that their zero sets are effectively finite unions of $p$-normal sets, leveraging recent advances in solving S-unit equations and linear equations over multiplicatively independent numbers.

The Gist

Imagine you are a detective trying to solve a mystery. The mystery is a sequence of numbers that follows a strict rule (like a recipe: "the next number is the sum of the last two"). This is called a Linear Recurrence Sequence.

Your job is the Skolem Problem: You need to answer one simple question: "Does this sequence ever hit zero?"

In the world of standard numbers (like 1, 2, 3...), this is one of the biggest unsolved mysteries in mathematics. We know the answer exists, but we don't have a "magic wand" (an algorithm) to find it quickly. It's like trying to find a specific grain of sand on a beach that might not even exist, without a map.

However, this paper solves the mystery for a specific, slightly different kind of world: Rings of Positive Characteristic.

The Setting: A World with a "Reset Button"

In normal math, numbers go on forever. But in the "Positive Characteristic" world described in this paper, there is a Reset Button.

Imagine a clock that only has 6 hours (0, 1, 2, 3, 4, 5). If you add 1 to 5, it doesn't go to 6; it wraps around to 0. In math terms, $6 = 0$.

• If the clock has 5 hours, it's a "prime" clock.
• If the clock has 6 hours (which is $2 \times 3$), it's a "composite" clock.

The authors are asking: "If we play this number game on a clock with a reset button (like 6, 10, or 12), can we always figure out if the sequence hits zero?"

The answer is YES. They have built a machine (an algorithm) that can solve this puzzle for any such clock.

How They Solved It: The Two-Step Strategy

The authors didn't just guess; they used a clever two-step strategy, like a detective breaking a complex case into smaller, solvable clues.

Step 1: The "Prime Clock" Detective (Proposition 1.2)

First, they looked at clocks that are made of a single prime number repeated (like a clock with 4 hours, which is $2^2$, or 8 hours, which is$2^3$).

• The Problem: In these clocks, numbers can get "sticky" (mathematicians call them zero-divisors). It's like trying to divide by zero in a normal world; things get messy.
• The Solution: They used a technique called Primary Decomposition. Imagine you have a tangled knot of yarn. Instead of trying to untangle the whole mess at once, you cut the knot into smaller, simpler loops.
  • They broke the messy ring down into simpler pieces where the "sticky" numbers become harmless (nilpotent).
  • Once the pieces were clean, they used a powerful new tool (a recent result by Dong and Shafrir) to prove that the "zero-hitting" pattern on these clocks follows a very specific, predictable structure called a $p$-normal set.
  • Analogy: Think of a $p$-normal set as a pattern that looks like a mix of "arithmetic progressions" (2, 4, 6, 8...) and "powers of a number" (2, 4, 8, 16...). It's a pattern you can describe with a simple formula.

Step 2: The "Intersection" Puzzle (Proposition 1.3)

Now, imagine your clock has 6 hours. Mathematically, a 6-hour clock is actually a combination of a 2-hour clock and a 3-hour clock working together (thanks to the Chinese Remainder Theorem).

• The Problem: To know if the sequence hits zero on the 6-hour clock, it must hit zero on the 2-hour clock AND the 3-hour clock at the same time.
• The Challenge: We know the "zero patterns" for the 2-hour clock (it's a 2-normal set) and the 3-hour clock (it's a 3-normal set). But what happens when you try to find the overlap (intersection) of two different patterns? Usually, mixing different patterns creates a mess that is impossible to predict.
• The Breakthrough: The authors used a recent discovery by Karimov et al. regarding equations involving powers of numbers. They proved that even though mixing different patterns usually creates chaos, in this specific mathematical world, the overlap always breaks down into a neat, manageable list of patterns again.
  • Analogy: Imagine you have a list of days that are "Blue" (multiples of 2) and a list of days that are "Red" (multiples of 3). You want to know which days are both Blue and Red. The authors proved that even if the lists are complex, the days that are both Blue and Red can always be described as a simple list of "Blue days" and a simple list of "Red days" combined.

The Grand Conclusion

By combining these two steps, the authors built a complete algorithm:

1. Break it down: Take any complex ring (like a 12-hour clock) and break it into its prime-power components (2-hour, 3-hour, 4-hour, etc.).
2. Solve the pieces: Use the "Primary Decomposition" trick to find the zero-pattern for each piece.
3. Reassemble: Use the "Intersection" trick to combine these patterns back together.

Because every step is mechanical and predictable, the computer can always run the program and say, "Yes, it hits zero," or "No, it never does."

Why This Matters

This is a huge victory for computer science and logic.

• Program Verification: It helps us prove that computer programs will never crash or enter an infinite loop (which often relates to a variable hitting zero).
• Control Theory: It helps engineers ensure that machines (like self-driving cars or robots) stay stable and don't drift into dangerous states.
• Mathematics: It solves a version of a 90-year-old mystery (the Skolem Problem) for a whole new class of numbers, showing that even in complex, "reset-button" worlds, order and predictability reign supreme.

In short: The authors found a way to map the "zero" spots in complex number worlds, proving that even in a universe with reset buttons, we can always predict when the count will hit zero.

Technical Summary

Here is a detailed technical summary of the paper "The Skolem Problem in rings of positive characteristic" by Ruiwen Dong and Doron Shafrir.

1. Problem Statement

The Skolem Problem asks whether a given linear recurrence sequence (LRS) over a commutative ring $R$ contains a zero term. Formally, given a sequence $(\gamma_n)_{n \in \mathbb{N}}$ satisfying $\gamma_n = \sum_{i=1}^d a_i \gamma_{n-i}$, the problem is to decide if the set $Z(\gamma) = \{n \in \mathbb{N} \mid \gamma_n = 0\}$ is non-empty.

• Context: Over the integers $\mathbb{Z}$ (or rationals $\mathbb{Q}$), this is a major open problem. The Skolem-Mahler-Lech theorem guarantees that the zero set is a union of a finite set and finitely many arithmetic progressions, but the theorem is non-effective (no computable bound exists for the finite set), leaving decidability open.
• Positive Characteristic: Decidability was previously established for fields of prime characteristic $p$ by Derksen (2007), who showed the zero set is a "$p$-normal set."
• Gap: This paper addresses the case of finitely generated commutative rings of arbitrary positive characteristic $T > 0$. Unlike fields, such rings may have composite characteristics (e.g., $T=6$) and contain zero-divisors, making the interaction between different prime factors of the characteristic a significant hurdle.

2. Methodology and Proof Structure

The authors prove that the Skolem Problem is decidable for any finitely generated commutative ring $R$ of characteristic $T > 0$. The proof proceeds in three main stages:

A. Decomposition via Chinese Remainder Theorem

Let the characteristic be $T = p_1^{e_1} \cdots p_k^{e_k}$. The ring $R$ can be analyzed via the quotient rings $A_i = R/p_i^{e_i}R$.

• The zero set of the sequence $\gamma$ over $R$ is the intersection of the zero sets of its projections $\alpha_i$ over each $A_i$:
  $$Z(\gamma) = Z(\alpha_1) \cap Z(\alpha_2) \cap \dots \cap Z(\alpha_k)$$
• The problem reduces to two sub-problems:
  1. Deciding the structure of $Z(\alpha_i)$ where the characteristic is a prime power $p^e$.
  2. Computing the intersection of sets defined over different prime powers.

B. Extension to Prime-Power Characteristics (Proposition 1.2)

Derksen's original result applies to fields (characteristic $p$). The authors extend this to rings of characteristic $p^e$ ($e \ge 2$).

• Challenge: In rings with zero-divisors, standard exponential polynomial representations of LRS terms fail because zero-divisors cannot be inverted or localized easily.
• Solution:
  1. Primary Decomposition: The authors decompose the zero ideal $\langle 0 \rangle$ into primary ideals. This reduces the problem to rings where every zero-divisor is nilpotent.
  2. Localization: They construct a localized ring $S^{-1}A$ where specific non-zero-divisors are inverted. This allows the LRS term $\gamma_n$ to be expressed as a sum of terms involving powers of roots $r_i^n$ multiplied by binomial coefficients $\binom{n}{k}$.
  3. Reduction to S-unit Equations: For large $n$, the sequence behaves like a "simple" recurrence. The condition $\gamma_n = 0$ translates into an equation of the form $\sum c_i r_i^n = 0$.
  4. Key Theorem: They invoke a recent result by Dong and Shafrir (2026) regarding S-unit equations over $p^e$-torsion modules. This theorem states that the solution set to such equations is effectively $p$-normal.
• Result: The zero set $Z(\alpha_i)$ is effectively a finite union of $p_i$-normal sets.

C. Intersection of $p_i$-Normal Sets (Proposition 1.3)

The final step is to decide if the intersection of $p_i$-normal sets (for distinct, multiplicatively independent primes $p_1, \dots, p_k$) is empty.

• Challenge: Generally, the intersection of $p$-automatic sets for different $p$ is not known to be computable. However, $p$-normal sets have a specific algebraic structure.
• Solution:
  1. Reduction to Linear Equations: The intersection of two $p$-normal sets (e.g., sets defined by $p^a$ and $q^b$) can be reduced to solving linear equations involving powers of multiplicatively independent integers (e.g., $p^a \cdot A + q^b \cdot B = C$).
  2. Use of Recent Logic Results: The authors utilize a result by Karimov et al. (2025) on the existential fragment of Presburger arithmetic extended with two power predicates. This provides an effective procedure to solve equations involving two powers.
  3. Inductive Argument: For $k > 2$ primes, they use an inductive argument. They show that the intersection of a $p_1$-normal set and a $p_2$-normal set can be rewritten as a union of a $p_1$-normal set and a $p_2$-normal set. This property allows the intersection of $k$ sets to be reduced to a finite union of sets, each defined by a single prime, making emptiness testing decidable.

3. Key Contributions

1. Decidability in Composite Characteristic: Proves the Skolem Problem is decidable for all finitely generated commutative rings of positive characteristic, not just fields or prime characteristics.
2. Extension of Derksen's Theorem: Generalizes the effective description of zero sets from prime characteristic $p$ to prime-power characteristic $p^e$ in the presence of zero-divisors.
3. Intersection Algorithm: Develops a method to effectively compute the intersection of $p_i$-normal sets for distinct primes, showing that such an intersection is effectively a finite union of $p_i$-normal sets.
4. Effective Characterization: Establishes that the zero set of an LRS over a ring of characteristic $T = \prod p_i^{e_i}$ is effectively a finite union of $p_i$-normal sets.

4. Main Results

• Theorem 1.1: Given a finitely generated commutative ring $R$ of characteristic $T > 0$ and a linear recurrence sequence $\gamma$, it is decidable whether $\gamma$ contains a zero.
• Proposition 1.2: For a ring of characteristic $p^e$, the zero set of an LRS is effectively $p$-normal.
• Proposition 1.3: The intersection of $p_i$-normal sets (for multiplicatively independent $p_i$) is effectively equal to a union of $p_i$-normal sets, and emptiness is decidable.

5. Significance

• Theoretical Impact: This resolves a significant open direction in the Skolem Problem, moving from fields to general rings. It bridges commutative algebra (primary decomposition, localization) with logic and number theory (S-unit equations, $p$-normal sets).
• Applications: The Skolem Problem is central to program verification (termination of loops), control theory (stability of systems), and dynamical systems. Decidability in rings of positive characteristic expands the scope of systems that can be algorithmically verified, particularly those modeled over finite rings or polynomial rings over such rings.
• Methodological Innovation: The paper demonstrates how recent advances in the decidability of S-unit equations and Presburger arithmetic with power predicates can be combined to solve classical problems in recurrence sequences. It highlights the power of decomposing complex algebraic structures (rings with composite characteristic) into simpler prime-power components.

In summary, Dong and Shafrir provide a complete algorithmic solution to the Skolem Problem for a broad class of algebraic structures, leveraging deep structural properties of rings and recent breakthroughs in the decidability of exponential Diophantine equations.