# P3116: Decidability of positivity for linear recurrence sequences

- ID: `P3116`
- Reference: `linear-recurrence-positivity-decidability`
- Page: https://theoremdb.org/statements/P3116
- Record maturity: Reviewed problem with recorded work

## 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\)?

### Context

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.

### Problem setup

- **Definition (linear recurrence sequence).** A sequence satisfying a fixed homogeneous recurrence with constant integer coefficients.
- **Definition (positivity problem).** Determine whether every term of the input sequence is nonnegative.
- **Remark.** 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.

### What counts as a solution

- Give a terminating correct decision algorithm for arbitrary order.
- Or prove undecidability through a computable reduction.

## 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. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: Decidability is known through order five, for simple sequences through order nine, and for additional reversible or dominant-root subclasses.

The exact unresolved remainder is: A decision procedure for unrestricted order, already beyond the low-order frontier, remains open.

A complete resolution must meet the following acceptance conditions:
- Give a terminating correct decision algorithm for arbitrary order.
- Or prove undecidability through a computable reduction.

### Background and intake notes

- 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.
- The release review checked 2 structured sources on 2026-08-01.
- 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.

### Other known results

- **Claim 2** (supported): Decidability is known through order five, for simple sequences through order nine, and for additional reversible or dominant-root subclasses. [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Decidability is known through order five, for simple sequences through order nine, and for additional reversible or dominant-root subclasses. Unresolved remainder: A decision procedure for unrestricted order, already beyond the low-order frontier, remains open. [1](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): A decision procedure for unrestricted order, already beyond the low-order frontier, remains open.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `linear-recurrence-positivity-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>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 https://doi.org/10.1137/1.9781611973402.27
   - Also cited at J. Ouaknine and J. Worrell, Positivity Problems for Low-Order Linear Recurrence Sequences, SODA 2014. main decidability theorems
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Proves positivity decidable through order five and explains the Diophantine barrier at order six.
   - 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.
2. <a id="reference-2"></a>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 https://doi.org/10.4230/LIPIcs.ICALP.2023.130
   - journal_article; primary source; checked 2026-08-01
   - Source 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.