gpt 6 astra ultra attempt on Math-300

Positivity Problem for Linear Recurrence Sequences

Definitions and mathematical statement

Input consists of $k\ge1$, rational numbers $a_1,\ldots,a_k$, and rational initial values, all exactly encoded in binary, defining \[ u_{n+k}=\sum_{i=1}^k a_i u_{n+k-i}\qquad(n\ge0). \] The target is a single total algorithm deciding whether $u_n\ge0$ for every $n\ge0$. No running-time bound is imposed, and $k$ is not fixed. Coefficients may vanish, including $a_k$, so the displayed recurrence need not have minimal order $k$. Eventual nonnegativity or nonnegativity up to a supplied finite index is a different decision problem. Equality to zero is permitted in the desired sequence.

Formulation and concept references: [S1].

Short English statement

Can an algorithm always determine whether every term of an arbitrary rational linear recurrence sequence is nonnegative?

Research attempt

GPT-6 Astra Ultra, 27 September 2026. Status: UNRESOLVED.

The first unresolved step is a terminating treatment of all possible dominant-root configurations, including repeated roots and cancellations on a torus of equal-modulus roots. Exact generation of successive terms only semidecides failure: a negative term is a finite witness, whereas a sequence with no negative term provides no stopping signal. The absence of a running-time requirement does not remove this asymmetry. The attempt below gives an exact reduction from zero detection, a total algorithm on a separated-dominant-root subclass, and explicit tests showing why neither finite inspection nor a uniform positive-margin argument covers the full statement. Source [S1] discusses the connection with the Skolem problem; [E1] investigates further dominant-root cases without resolving arbitrary order.

Integer normalization and zero detection

Choose a positive integer $D$ divisible by the denominators of every coefficient and initial value. Set \[ v_n=D^{n+1}u_n. \] For the initial indices these are integers. Multiplying the recurrence by $D^{n+k+1}$ gives \[ v_{n+k}=\sum_{i=1}^k a_iD^i\,v_{n+k-i}, \tag{296.1} \] whose coefficients are integers. Hence every $v_n$ is integral, and scaling preserves signs and zeros. This operation is effective even when the last recurrence coefficient vanishes; no assertion that the given order is minimal is needed.

For an integer recurrence $(v_n)$, the sequence \[ w_n=v_n^2-1 \tag{296.2} \] is again an effectively computable integer linear recurrence. To see this without guessing its characteristic polynomial, represent $v_n=\ell C^n s$ using the integer companion matrix $C$ and the initial state $s$. Then \[ v_n^2=(\ell\otimes\ell)(C\otimes C)^n(s\otimes s). \] Adding a constant coordinate represents $w_n$ by a matrix of dimension $k^2+1$. The Cayley--Hamilton identity provides an explicit integer recurrence of order at most that dimension.

Because $v_n$ is an integer, \[ w_n\ge0\ \hbox{for every }n \quad\Longleftrightarrow\quad v_n\ne0\ \hbox{for every }n. \tag{296.3} \] Thus a total Positivity algorithm would decide whether an arbitrary rational recurrence has a zero: normalize, form $296.2$, run the algorithm, and reverse its answer. The subtraction of one is essential. Using $v_n^2$ alone always produces a nonnegative sequence and loses the information entirely. Integrality is equally essential: for an unnormalized rational value $v_n=1/2$, the square minus one is negative without $v_n$ being zero.

This is an obstacle transfer, not an undecidability proof. It demonstrates that a general positivity certificate must handle at least the difficulties of zero detection, including exact equality, rather than merely approximate real numbers until their signs seem stable.

A total algorithm when one positive root dominates

Consider the effectively recognizable subclass in which the nonzero characteristic roots with nonzero contribution have a unique largest modulus, attained by a simple positive real root $\lambda$, with coefficient $c>0$. After a finite initial segment accounting for a possible zero characteristic root, the exact exponential-polynomial form is \[ u_n=c\lambda^n+\sum_j P_j(n)\lambda_j^n,\qquad |\lambda_j|<\lambda. \tag{296.4} \] All roots and coefficients are algebraic and can be determined by exact polynomial factorization, algebraic-number arithmetic, and linear equations for the initial values. Zero contributions can be tested exactly. These procedures may be expensive; only effective termination is asserted.

Choose rational numbers $c_0,C>0$ and $0<\rho<1$, and a nonnegative integer $d$, so that \[ 0<c_0<c,\qquad \left|\sum_j P_j(n)\lambda_j^n\right|/\lambda^n \le C(n+1)^d\rho^n \tag{296.5} \] for all indices beyond that initial segment. Such choices are effective from strict modulus separation: bound the absolute values of the finitely many polynomial coefficients and choose $\rho$ strictly above every $|\lambda_j|/\lambda$. If there is no remainder, the bound is vacuous and the tail sign is immediate.

It is not enough to find one index where the right side is small; one needs a bound valid thereafter. Choose $N_0$ so that \[ \rho\left(1+\frac1{N_0+1}\right)^d<1. \] The ratio of successive values of $(n+1)^d\rho^n$ is then below one for every $n\ge N_0$. Search for $N\ge N_0$, also beyond the transient segment, with $C(N+1)^d\rho^N<c_0/2$. Exponential decay ensures termination, and monotonicity makes the same inequality hold for every later index. Equations $296.4$--$296.5$ imply \[ u_n/\lambda^n>c-c_0/2>0\qquad(n\ge N). \] An exact check of the finite prefix $0\le n<N$ now decides Positivity for this subclass.

A negative coefficient at such a unique positive dominant root instead forces an eventually negative tail. A unique negative real dominant root with nonzero coefficient forces opposite eventual signs on the two parities. These observations extend the easy separated case but do not eliminate the equal-modulus obstruction. Nonnegative recurrence coefficients and nonnegative initial values give another simple positive subclass by induction; this sufficient test is not necessary, as the nonnegative sequence $n^2$ has recurrence coefficients $3,-3,1$.

An equal-modulus test with no positive margin

Let \[ z=(3+4i)/5,\qquad u_n=2+z^n+\overline z^{\,n}=2+2\operatorname{Re}(z^n). \tag{296.6} \] The sequence is rational and nonnegative. Its characteristic polynomial is \[ (X-1)(X^2-\tfrac65X+1) =X^3-\tfrac{11}5X^2+\tfrac{11}5X-1, \] with initial values $u_0=4$, $u_1=16/5$, and $u_2=36/25$.

The number $z$ is not a root of unity. Otherwise $z+z^{-1}=6/5$ would be both rational and an algebraic integer, and therefore an integer. Its powers are consequently dense on the unit circle, by the elementary density theorem for an irrational rotation. For completeness, the latter follows by finding arbitrarily small nonzero rotation increments through the pigeonhole principle and using their successive multiples to approximate any arc. Thus the values in $296.6$ approach zero arbitrarily closely. They never equal zero: $z^n=-1$ would make $z$ a root of unity. We have proved \[ u_n>0\quad\hbox{for every }n,\qquad \inf_n u_n=0. \tag{296.7} \] A rule requiring a fixed positive lower margin on the dominant normalized expression would therefore reject a genuinely positive recurrence. Adding smaller exponential terms in other examples requires quantitative comparison near these small values; qualitative density alone supplies no bound sufficient for that comparison. The proof of the separated-root algorithm cannot simply set $\rho=1$ and continue.

Finite prefixes, verification, and outcome

For any supplied integer $M\ge0$, the recurrence $u_n=M-n$, with coefficients $2,-1$, is nonnegative through index $M$ and negative at $M+1$. Since $M$ needs only $O(\log(M+1))$ bits, a very long successful prefix can be misleading. This example is not a lower bound against all algorithms, and a length depending exponentially on the input would still be compatible with the target. Its point is that a prefix must be accompanied by a proved stopping criterion.

The saved exact-arithmetic checks verify normalization, the tensor-square construction on several recurrences, the recurrence and initial values in $296.6$, and the finite-prefix countertest. The dominant-root proof provides its own explicit tail criterion and does not infer a tail from those finite checks.

UNRESOLVED. Positivity is decided here for a rigorously specified separated-root subclass, and general zero detection reduces to it through $296.2$. A terminating procedure covering every equal-modulus and repeated-root configuration is still missing; eventual nonnegativity alone would also leave the initial terms to be controlled effectively.

Sources

• S1 Positivity-hardness results on Markov decision processes, arXiv2302.13675v2, 5 April 2024; TheoretiCS3 Article9. https://arxiv.org/pdf/2302.13675v2. Formulation source.
• E1 Alaa Ibrahim, Positivity Proofs for Linear Recurrences with Several Dominant Eigenvalues, arXiv:2503.14264 $2025$. https://arxiv.org/abs/2503.14264. Primary research on additional dominant-root configurations; not a general decision algorithm for arbitrary order.