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

Testing whether every term of a recurrence stays nonnegative. — A structural automaton diagram of the statement's mathematical objects.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

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

Saved packet · August 1, 2026

What counts as a solution

Saved packet 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]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 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] Relevance to this problem This is the dated publication status for the canonical target Decidability of positivity for linear recurrence sequences. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details 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. Open full record →
Decidability is known through order five, for simple sequences through order nine, and for additional reversible or dominant-root subclasses.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 2 Decidability is known through order five, for simple sequences through order nine, and for additional reversible or dominant-root subclasses.^[1][2] Relevance to this problem Locates the present research frontier immediately below Decidability of positivity for linear recurrence sequences. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details Decidability is known through order five, for simple sequences through order nine, and for additional reversible or dominant-root subclasses. This leaves the following boundary unresolved: A decision procedure for unrestricted order, already beyond the low-order frontier, remains open. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
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.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 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][2] Relevance to this problem Documents why Decidability of positivity for linear recurrence sequences was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - positivity problem linear recurrence sequences general decidability open 2026 - linear recurrence positivity order 6 Diophantine approximation 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. Related: Claim 1 Open full record →
A decision procedure for unrestricted order, already beyond the low-order frontier, remains open.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 2 A decision procedure for unrestricted order, already beyond the low-order frontier, remains open. Relevance to this problem Turns the remaining uncertainty in Decidability of positivity for linear recurrence sequences into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: A decision procedure for unrestricted order, already beyond the low-order frontier, remains open. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Give a terminating correct decision algorithm for arbitrary order. - Or prove undecidability through a computable reduction. Related: Claim 1 Open full record →
No records match these filters.

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

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemDecidability of positivity for linear recurrence sequences

All 3 recorded relations between these records and the problem

2See also

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Decidability of positivity for linear recurrence sequences.” TheoremDB. P3116. Problem statement; statement text SHA-256 5290f7c62e0290d36e30f3800da2c39078f5e4c2e85d4c22a9cf198f9820cc49. https://theoremdb.org/statement/?ref=P3116

BibTeX

@misc{theoremdb-problem-5290f7c62e0290d36e30f3800da2c39078f5e4c2e85d4c22a9cf198f9820cc49,
  title = {{Decidability of positivity for linear recurrence sequences}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 5290f7c62e0290d36e30f3800da2c39078f5e4c2e85d4c22a9cf198f9820cc49},
  url = {https://theoremdb.org/statement/?ref=P3116}
}

Plain text: Built Markdown snapshot

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[1], current as of August 1, 2026.

1Lean verification

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.

[#P3116] Decidability of positivity for linear recurrence sequences

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance