Skolem Problem

Skolem Problem

Definitions and mathematical statement

A linear recurrence sequence of order $k$ is determined by coefficients $c_0,\ldots,c_{k-1}$ and initial terms $u_0,\ldots,u_{k-1}$ through \[ u_{n+k}=c_{k-1}u_{n+k-1}+\cdots+c_0u_n\quad(n\ge0). \] The data are integers or algebraic numbers given by effective exact encodings. The Skolem problem asks for an algorithm that always halts and decides whether $\exists n\ge0$ with $u_n=0$. The order is part of the input and is unbounded. An algorithm for a fixed low order, or a description of the zero set without effective bounds on the exceptional indices, does not settle the general decision problem.

Formulation and concept references: [S1].

Short English statement

Can one always decide from a linear recurrence and its initial values whether any term of the resulting sequence is exactly zero?

Research attempt

Current frontier.

Bacik's order-four theorem includes algebraic coefficients and initial values [S1]; the order is not bounded by four in this entry. The Skolem--Mahler--Lech description gives a finite union of arithmetic progressions together with a finite exceptional zero set, but finiteness alone does not bound the last exceptional index. Luca--Ouaknine--Worrell's July 2026 manuscript [E1], Conjecture 4.2 and Theorem 4.3, obtains a conditional large-zero bound from a spacing conjecture for a specified set of "good primes." That conjecture is stronger than invoking the usual Cramér--Granville conjecture for all primes. The manuscript's unconditional sparsity statements do not decide whether an individual exceptional index exists. These distinctions leave room for both archimedean estimates and local certificates, examined below without assuming the prime-gap conjecture.

Attack route.

Enumerating terms semidecides the existence of a zero. To make a total decision procedure, seek either a finite modular certificate of zero-freeness, a $p$-adic zero isolation argument that rules out integer indices, or an effective dominating-term estimate. The modular strategy is attractive because every finite residue orbit is computable. I actively test its completeness and find an exact order-seven counterexample to that intermediate strategy, not to decidability. The dominating-term route then supplies a genuine terminating subcase and isolates what fails when several characteristic roots have the same modulus.

Attempt.

1. Finite residue tests are sound but not complete. For an integer recurrence of order $k$, the state vector of $k$ successive terms evolves deterministically on $({\mathbb{Z}}/m{\mathbb{Z}})^k$. By recording states until repetition, one can decide whether any term is zero modulo $m$. If none is, then the integer sequence has no zero. It is tempting to run this search over $m=2,3,\ldots$ in parallel with exact zero enumeration, expecting one side to halt. The following sequence disproves that expectation: \[ u_n=(n^2-13)(n^2-17)(n^2-221),\qquad n\ge0. \tag{217.1} \] It never vanishes at an integer, since $13,17,221$ are not integer squares. As a polynomial in $n$ of degree six, it satisfies $(T-1)^7u=0$, where $Tu_n=u_{n+1}$. Explicitly, \[ \begin{split} u_{n+7}={}&7u_{n+6}-21u_{n+5}+35u_{n+4}-35u_{n+3}\\ &+21u_{n+2}-7u_{n+1}+u_n. \end{split}\tag{217.2} \] Thus it is a valid input of order seven to the original problem.

Nevertheless, $u_n\equiv0\pmod m$ is solvable for every $m\ge1$. For an odd prime $p\notin\{13,17\}$, if neither $13$ nor $17$ is a quadratic residue, their product $221$ is. Choose a square root modulo $p$ of one of these nonzero residues; its derivative $2n$ is nonzero, so the root lifts to every $p$-power. At $p=13$, $17\equiv2^2$; at $p=17$, $13\equiv8^2$. These roots also lift. At $p=2$, $17\equiv1\pmod8$ has a square root in ${\mathbb{Z}}_2$, hence modulo every power of two. The last elementary fact follows by lifting an odd square root one binary digit at a time: replacing an odd root modulo $2^j$ by that root plus $2^{j-1}$ toggles its square modulo $2^{j+1}$. The Chinese remainder theorem combines the chosen prime-power roots, possibly from different factors, into one nonnegative index modulo $m$. This proves the asserted failure for all moduli, not just those searched by a program.

The reproduction script verifies $217.2$ symbolically and finds a root of $217.1$ modulo every integer $2\le m\le256$. The finite check is only a test of the implementation; the prime-power argument proves the unbounded statement. The polynomial nature of $217.1$ makes its actual zero-freeness easy to decide. The example therefore does not imply that Skolem is undecidable; it proves incompleteness of this particular modular certificate scheme. Its only characteristic root is $1$ with multiplicity seven, so the obstruction also highlights the distinction between "simple" characteristic roots and the usual nondegeneracy condition on quotients of distinct roots.

2. What $p$-adic interpolation does and does not supply. For clarity, first consider an integer matrix representation $u_n=\ell A^n v$ with $\det A\ne0$. Choose an odd prime $p$ not dividing $\det A$. Some computable $h>0$ satisfies $A^h\equiv I\pmod p$, so write $A^h=I+pB$ with $B$ integral. For each $0\le r<h$, the function \[ F_r(z)=\ell A^r\sum_{j=0}^{\infty} \binom zj p^jB^jv,\qquad z\in{\mathbb{Z}}_p, \tag{217.3} \] interpolates $u_{r+hn}$ at every nonnegative integer $n$. The convergence is uniform because $\binom zj\in{\mathbb{Z}}_p$ for $z\in{\mathbb{Z}}_p$. Moreover the coefficients of the polynomial $\binom zj$ have $p$-adic sizes at most $p^{v_p(j!)}$, and $j-v_p(j!)\to\infty$ for odd $p$. Thus the series converges in the algebra of restricted power series on ${\mathbb{Z}}_p$: $217.3$ is analytic, not just continuous. A nonzero such series has finitely many zeros by Strassmann's theorem. The standard interpolation perspective underlies the structural zero-set theorem discussed in [E1], Section 1.

The missing step is arithmetic, not the uniform convergence just proved. A zero of $F_r$ may be a $p$-adic integer without being an ordinary nonnegative integer. Finitely many isolated $p$-adic roots do not by themselves give a terminating procedure for recognizing that none is an ordinary integer. Increasing $p$-adic precision only narrows congruence classes, each of which contains arbitrarily large nonnegative integers. In $217.1$, the interpolating polynomial has a local root for every prime but no integer root. Algebraicity of its roots resolves that particular example; it is not established for roots of every analytic interpolant $217.3$. Thus an integer-recognition theorem would be a substantive extra input, not an automatic application of zero isolation.

3. A completely effective dominant-root subcase. There is a useful escape from this obstruction when one archimedean term dominates. Effective algebraic linear algebra gives, after any finite initial transient coming from the root zero, an expression \[ u_n=\sum_{i=0}^s P_i(n)\lambda_i^n \tag{217.4} \] with distinct nonzero algebraic $\lambda_i$ and algebraic-coefficient polynomials $P_i$. Terms with zero polynomials are deleted. Fix one complex embedding. Suppose \[ |\lambda_0|>\max_{i\ge1}|\lambda_i|, \qquad P_0\ne0. \tag{217.5} \] All comparisons needed here can be decided for algebraic real numbers $|\lambda_i|^2$. Let $r=\deg P_0$ and $a\ne0$ be its leading coefficient. Effective rational bounds on its coefficients give a computable $N_0$ and a positive rational $c<|a|/2$ such that \[ |P_0(n)|\ge c n^r\quad(n\ge N_0). \] For example, for $r\ge1$, bound the lower terms by $n^{r-1}\sum_{j<r}|a_j|$ and take $n\ge 2\sum_{j<r}|a_j|/|a|$, with rational upper and lower bounds used in the computation. For $r=0$ the estimate holds immediately. Choose a computable rational $\rho$ with $\max_{i\ge1}|\lambda_i/\lambda_0|<\rho<1$, and rational $C>0$ and integer $s_0\ge0$ such that \[ \sum_{i\ge1}|P_i(n)|\le C n^{s_0}\quad(n\ge1). \] The case with no other terms is simpler and is handled by the leading polynomial bound alone. Otherwise put $d_0=\max(s_0-r,0)$ and search for an integer $N\ge\max(N_0,1)$ satisfying \[ C N^{d_0}\rho^N<c, \qquad \rho(1+1/N)^{d_0}<1. \tag{217.6} \] This is an exact rational search. It terminates because exponential decay beats every fixed polynomial. The second inequality makes $n^{d_0}\rho^n$ decreasing for all integers $n\ge N$. Therefore \[ \left|\sum_{i\ge1}P_i(n)(\lambda_i/\lambda_0)^n\right| \le C n^{s_0}\rho^n<c n^r\le |P_0(n)|\quad(n\ge N). \] So $u_n\ne0$ throughout the tail. Checking the finitely many earlier indices by exact algebraic arithmetic decides existence of a zero. This rederives a standard dominance mechanism with an explicit stopping condition; it is not a claim of a newly solved unrestricted class. It also treats the one-characteristic-root polynomial example $217.1$.

4. The remaining oscillatory regime. When several $|\lambda_i|$ share the maximum, normalization of $217.4$ leaves a sum of oscillating algebraic phases with polynomial amplitudes. The factor $\rho<1$ used in $217.6$ is no longer available for their mutual cancellation. A successful replacement needs an effective separation estimate, or a different finite certificate, valid for every nonzero value in the tail. A bound on the number of zeros is not such an estimate: one zero could occur after every cutoff reached so far. Nor does a density-one set of decidable indices cover the exceptional complement. The conditional good-prime argument in [E1], Sections 4--6, addresses precisely a large-index issue, but its spacing hypothesis is not established by the present reasoning.

Stress test.

The modular example uses only integer data and hence genuinely lies inside the original algebraic-data scope. Its zero-free proof covers every nonnegative index, and its local-solvability proof covers every modulus. It refutes a proposed completeness lemma rather than the existence of all possible algorithms. The interpolation discussion is explicitly restricted to invertible integral $A$; no claim that every input immediately has that form is needed for the identified obstruction. In the dominance argument, zero characteristic roots and zero coefficient polynomials are removed with their finite transients accounted for; the remaining finite-prefix checks are exact, not floating-point root tests.

There is a methodological relation to Section 208: an ineffective finite exceptional set does not supply a stopping rule. No reduction from Effective Roth to full Skolem, or conversely, has been proved here. In particular, neither the known order-four theorem [S1] nor the conditional 2026 prime-gap theorem may be applied with its order or conjectural hypothesis deleted.

Outcome.

Outcome: Exploratory approach with unresolved gap.

The attempt gives a proved obstruction to completeness of all finite modular zero-freeness tests, a carefully justified $p$-adic interpolation with its integer-recognition gap exposed, and an explicit terminating algorithm when a unique characteristic root has strictly maximal modulus. These results do not decide arbitrary-order recurrences in the remaining oscillatory regime. No general zero cutoff, unconditional replacement for the prime-gap hypothesis, or counterexample to algorithmic decidability has been obtained.

Sources

• S1 Piotr Bacik, "Completing the picture for the Skolem Problem on order-4 linear recurrence sequences," TheoretiCS, Volume 4 (published 2 December 2025), DOI 10.46298/theoretics.25.28; arXiv:2409.01221. https://theoretics.episciences.org/17020. Catalogue formulation source.
• E1 F. Luca, J. Ouaknine and J. Worrell, "Conjectural Decidability of the Skolem Problem," arXiv:2607.15510v1 (16 July 2026), Theorem 1.1, Conjecture 4.2, Theorem 4.3, and Sections 5--6. The good-prime spacing assumption is conjectural, and sparsity alone is not full decidability. https://arxiv.org/html/2607.15510v1.