# P2836: Decidability of zeros in integer linear recurrence sequences

- ID: `P2836`
- Reference: `skolem-problem-decidability`
- Page: https://theoremdb.org/statements/P2836
- Record maturity: Reviewed problem with recorded work

## Problem

Is there an algorithm that, given integers \(d\ge1\), \(c_1,\ldots,c_d\), and \(u_0,\ldots,u_{d-1}\), always halts and decides whether the sequence defined by \(u_{n+d}=c_1u_{n+d-1}+\cdots+c_du_n\) for every \(n\ge0\) has some zero term \(u_n=0\)?

### Remarks

- **Remark.** The order \(d\), recurrence coefficients, and initial values are all part of the finite input and are written in binary.
- **Remark.** A zero term may occur at any index \(n\ge0\); no bound on the first zero is supplied to the algorithm.
- **Remark.** This decision question is the Skolem problem for integer linear recurrence sequences.

### What counts as a solution

- Give and prove correct a terminating algorithm for every integer linear recurrence input, or prove undecidability by a computable reduction from an undecidable problem.

## Status

General integer-LRS Skolem decidability remains open: order at most four is decidable, and no unconditional algorithm or undecidability proof is known for arbitrary order, beginning with order five. [6](#reference-6)

## Work

### Evidence for the current status

**Claim 1 (General Skolem decidability remains open beyond order four).** General integer-LRS Skolem decidability remains open: order at most four is decidable, and no unconditional algorithm or undecidability proof is known for arbitrary order, beginning with order five.

The source audit through 2026-07-28 found no unconditional decision procedure for arbitrary-order integer linear recurrence sequences and no undecidability reduction. Bacik proves decidability for algebraic linear recurrence sequences of order at most four. Bacik, Ouaknine, and Worrell place the bounded problem for every fixed order in coRP and obtain the same upper bound for the unrestricted order-four problem. A restricted family reaches higher order: Kenison gives an alternative proof of decidability for reversible integer LRS of order at most seven.

The 2026 p-adic algorithm has unconditionally correct output whenever it terminates. Its termination proof assumes the p-adic Schanuel Conjecture. The July 2026 preprint obtains general decidability under a strengthened Cramér-type conjecture and proves unconditionally that the possible large-zero indices have density zero. These results narrow the search without deciding the general target. The first order outside the unconditional general frontier is five.

### Background and intake notes

Low-order algorithms, root-configuration classifications, modular sieves, and explicit bounds for nondegenerate sequences can be stored independently. Together they map which recurrence families have effective zero tests and where ineffectivity remains.

- Original intake status: UNKNOWN as of 2026-07-27. Current primary work states that general decidability remains open. Decision procedures are known through order four, and recent results make large zeros sparse or give conditional algorithms.
- 2026-07-27 status search checked the 2025 low-order complexity paper, MFCS 2025 large-zero results, STACS 2026 p-adic algorithms, and the July 2026 conditional-decidability preprint. None gives an unconditional general algorithm.
- The strongest checked unconditional order result decides sequences of order at most four. The 2026 work gives general decidability under a strengthened Cramér-type conjecture and proves that possible large-zero indices have density zero.
- Certificates for a found zero are short once the index is known in binary and the term is evaluated by fast recurrence methods. Negative certificates require effective control of all indices and are the difficult side.

- Recorded example: The Fibonacci recurrence \(u_{n+2}=u_{n+1}+u_n\) with \(u_0=0,u_1=1\) has a zero at index zero. The same recurrence with \(u_0=u_1=1\) has no zero term.

### Other known results

- **Claim 2** (reported): If an integer LRS has final recurrence coefficient ±1 and a negative-index zero in its bi-infinite extension, every modulus has a congruent zero at some nonnegative index. [3](#reference-3) [9](#reference-9)

### Prior approaches

- **Route 1** (supported): Six primary sources preserve the general open status while locating the order-four frontier, the order-seven reversible subclass, fixed-order bounded complexity, conditional p-adic procedures, and sparse large-zero results. [1](#reference-1) [2](#reference-2) [3](#reference-3) [9](#reference-9) [5](#reference-5) [6](#reference-6)
- **Route 2** (ruled out): The Fibonacci shift has no zero at a nonnegative integer index, yet every modulus has a zero somewhere on its nonnegative modular orbit. [4](#reference-4) [9](#reference-9)

### Open directions

- **Route 3** (reported): Formalize companion-state invertibility, finite modular recurrence, and the Fibonacci shift so later sieve records cannot conflate integer-index and nonnegative-index zeros.

### Runnable artifacts

- **Artifact 1** (reproduced): Exact replay classifies all 2,401 tuples in the coefficient-and-initial box [-3,3]^4: 841 gain a zero witness through index 1000, 1,508 gain a complete modular nonzero certificate, and 52 remain inconclusive.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `skolem-problem-decidability`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Piotr Bacik, “Completing the picture for the Skolem Problem on order-4 linear recurrence sequences”. TheoretiCS Volume 4 (2025), 14219. DOI 10.46298/theoretics.25.28. Abstract and Theorem 4.1 https://doi.org/10.46298/theoretics.25.28
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Proves unconditional decidability for every algebraic linear recurrence sequence of order at most four.
   - For Decidability of zeros in integer linear recurrence sequences: Proves unconditional decidability for every algebraic linear recurrence sequence of order at most four.
   - Proves decidability for every algebraic LRS of order at most four.
2. <a id="reference-2"></a>Piotr Bacik, Joël Ouaknine, and James Worrell, “On the Complexity of the Skolem Problem at Low Orders”. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2026), 5255-5269. DOI 10.1137/1.9781611978971.191. Theorems 3.1 and 3.6 and Corollary 3.7 https://doi.org/10.1137/1.9781611978971.191
   - Also cited at Theorems 3.1 and 3.6 and Corollary 3.7, pages 5255-5269
   - proceedings_article; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Gives a coRP algorithm for the bounded problem at every fixed order and the same upper bound for unrestricted order four.
   - For Decidability of zeros in integer linear recurrence sequences: Gives the fixed-order bounded coRP algorithm and the order-four coRP corollary.
   - Gives the fixed-order bounded coRP algorithm and the order-four coRP corollary.
3. <a id="reference-3"></a>Kenison, George, “On the Skolem Problem for Reversible Sequences”. LIPIcs, Volume 241, MFCS 2022 (2022). DOI 10.4230/LIPIcs.MFCS.2022.61. Theorem 1 and the definition after it, p. 61:2; order-eight discussion, p. 61:3 https://doi.org/10.4230/LIPIcs.MFCS.2022.61
   - Also cited at Theorem 1 and the definition following it, page 61:2; order-eight discussion on page 61:3
   - Also cited at Definition following Theorem 1, page 61:2
   - proceedings_article; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Gives an alternative decidability proof for reversible integer sequences through order seven and identifies the next frontier for that subclass.
   - For Decidability of zeros in integer linear recurrence sequences: Supplies the reversible-LRS terminology and the integral bi-infinite extension characterization used by the boundary lemma.
   - Defines reversible integer LRS and gives an alternative proof of decidability for that subclass through order seven.
   - Supplies the reversible-LRS terminology and the integral bi-infinite extension characterization used by the boundary lemma.
4. <a id="reference-4"></a>Bacik, Piotr, Ouaknine, Joël, Purser, David, and Worrell, James, “On the p-adic Skolem Problem”. LIPIcs, Volume 364, STACS 2026 (2026). DOI 10.4230/LIPIcs.STACS.2026.8. Abstract, Theorem 4, Remark 18, and Conjecture 19 https://doi.org/10.4230/LIPIcs.STACS.2026.8
   - Also cited at Bacik et al., On the p-adic Skolem Problem, Section 3.7 and Conjecture 19, pages 8:16-8:17. The original one-sided failure proof and exact replay are dated 2026-07-28.
   - proceedings_article; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Provides p-adic zero algorithms with unconditional correctness on termination and a conjectural termination argument.
   - Source used to assess the problem's recorded status.
   - For Decidability of zeros in integer linear recurrence sequences: The Fibonacci shift has no zero at a nonnegative integer index, yet every modulus has a zero somewhere on its nonnegative modular orbit.
5. <a id="reference-5"></a>Bacik, Piotr and Varonka, Anton, “On the Subspace Orbit Problem and the Simultaneous Skolem Problem”. LIPIcs, Volume 380, LICS 2026 (2026). DOI 10.4230/LIPIcs.LICS.2026.8. Abstract, pp. 8:1–8:2 https://doi.org/10.4230/LIPIcs.LICS.2026.8
   - Also cited at Abstract, pages 8:1-8:2
   - proceedings_article; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Records that the hyperplane Orbit Problem, equivalent to general Skolem, remains open.
   - For Decidability of zeros in integer linear recurrence sequences: Records that the hyperplane Orbit Problem, equivalent to general Skolem, remains open.
6. <a id="reference-6"></a>Florian Luca, Joël Ouaknine, and James Worrell, Conjectural Decidability of the Skolem Problem, arXiv:2607.15510v1, abstract and Sections 1, 4, and 5, especially Theorems 4.3 and 5.1. Checked 2026-07-28. Abstract and Sections 1, 4, and 5, especially Theorems 4.3 and 5.1 https://arxiv.org/abs/2607.15510v1
   - Also cited at Florian Luca, Joël Ouaknine, and James Worrell, Conjectural Decidability of the Skolem Problem, arXiv:2607.15510v1, abstract and Sections 1, 4, and 5, especially Theorems 4.3 and 5.1. Checked 2026-07-28.
   - Also cited at Abstract, Sections 1, 4, and 5, especially Theorems 4.3 and 5.1
   - preprint; reference source; arXiv:2607.15510v1; checked 2026-07-28
   - Source use: citation_only
   - Gives conditional general decidability and proves that the possible large-zero indices form a set of density zero.
   - Source used to assess the problem's recorded status.
   - For Decidability of zeros in integer linear recurrence sequences: Gives conditional general decidability, the unconditional null-density theorem for possible large-zero indices, and a current statement of the open general problem.
   - Gives conditional general decidability, the unconditional null-density theorem for possible large-zero indices, and a current statement of the open general problem.
   - Gives conditional general decidability and the unconditional null-density theorem for possible large-zero indices.
7. <a id="reference-7"></a>Florian Luca, Joël Ouaknine, and James Worrell, On Large Zeros of Linear Recurrence Sequences, MFCS 2025, LIPIcs 345, Article 71, 1–11. Abstract and Sections 1 and 4, especially Theorems 9 and 11 https://doi.org/10.4230/LIPIcs.MFCS.2025.71
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - States the general Skolem problem as open and proves density-one coverage by a universal set of indices together with conditional coverage of sufficiently large zeros.
   - Source used to assess the problem's recorded status.
   - For Decidability of zeros in integer linear recurrence sequences: Original CC0 record prose for the classical Skolem decidability problem.