[#P3116] Decidability of positivity for linear recurrence sequences
Problem. Is there an algorithm that, given an integer linear recurrence sequence \(u_{n+d}=a_1u_{n+d-1}+\cdots+a_du_n\) with the order, coefficients, and initial values as input, decides whether \(u_n\ge0\) for every \(n\ge0\)?
1Context
Known frontier: Decidability is known through order five, for simple sequences through order nine, and for additional reversible or dominant-root subclasses. Open boundary: A decision procedure for unrestricted order, already beyond the low-order frontier, remains open.
2Problem setup
Definition 1 (linear recurrence sequence). A sequence satisfying a fixed homogeneous recurrence with constant integer coefficients.
Definition 2 (positivity problem). Determine whether every term of the input sequence is nonnegative.
Remark 1. A negative term is a finite witness, while a positive answer requires control of the entire infinite sequence. Characteristic roots on the same dominant circle lead to difficult Diophantine approximation questions.
3What counts as a solution
- Give a terminating correct decision algorithm for arbitrary order.
- Or prove undecidability through a computable reduction.
1Status
Current status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: Decidability is known through order five, for simple sequences through order nine, and for additional reversible or dominant-root subclasses. Exact unresolved remainder: A decision procedure for unrestricted order, already beyond the low-order frontier, remains open.[1][2]
1Records
Notes and companion material
Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: Decidability is known through order five, for simple sequences through order nine, and for additional reversible or dominant-root subclasses. Exact unresolved remainder: A decision procedure for unrestricted order, already beyond the low-order frontier, remains open.
- Equivalent-formulation queries: positivity problem linear recurrence sequences general decidability open 2026; linear recurrence positivity order 6 Diophantine approximation
- Strongest checked neighboring result: Decidability is known through order five, for simple sequences through order nine, and for additional reversible or dominant-root subclasses.
- Exact unresolved remainder: A decision procedure for unrestricted order, already beyond the low-order frontier, remains open.
How the 4 records connect
ProblemDecidability of positivity for linear recurrence sequences
2See also
How to cite
TheoremDB contributors, “Decidability of positivity for linear recurrence sequences,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/linear-recurrence-positivity-decidabilityThis page as plain text: linear-recurrence-positivity-decidability.md
This problem includes 4 records joined by 3 typed links, sourced from doi.org[1], current as of August 1, 2026.
1References
- Packet source. Joël Ouaknine and James Worrell, “Positivity Problems for Low-Order Linear Recurrence Sequences”. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (2014), 366-379. DOI 10.1137/1.9781611973402.27. main decidability theorems. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Proves positivity decidable through order five and explains the Diophantine barrier at order six.Also cited at J. Ouaknine and J. Worrell, Positivity Problems for Low-Order Linear Recurrence Sequences, SODA 2014. main decidability theorems.Source used to assess the problem's recorded status.For Decidability of positivity for linear recurrence sequences: This is the dated publication status for the canonical target Decidability of positivity for linear recurrence sequences.Source named by the research packet.
- Kenison, George, Nieuwveld, Joris, Ouaknine, Joël, and Worrell, James, “Positivity Problems for Reversible Linear Recurrence Sequences”. LIPIcs, Volume 261, ICALP 2023 (2023). DOI 10.4230/LIPIcs.ICALP.2023.130. abstract and main theorems. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Calls general decidability longstanding and proves new reversible-sequence cases.Source used to assess the problem's recorded status.For Decidability of positivity for linear recurrence sequences: Calls general decidability longstanding and proves new reversible-sequence cases.
Original TheoremDB editorial statement and source synthesis; external works are used for citation only.