FPRD-MN-D01 · definitions

Three questions with different quantifiers

Let $M\in\mathbb Q^{d\times d}$ and read $M^n\ge0$ entrywise. The three standard questions are

The first asks for one positive exponent; the second asks for an entire tail. If the first allowed $n=0$, every matrix would satisfy it because $M^0=I\ge0$. Keeping the exponent domain explicit prevents the existential, eventual, and everywhere variants from being conflated.

FPRD-MN-T01 · published theorem

The good exponents are effectively periodic

The proof first chooses a modulus that separates root-of-unity collisions among eigenvalues. Each residue class then gives nondegenerate linear recurrence sequences for the matrix entries. Here dominated means that an entry recurrence has a unique characteristic root of greatest modulus. If every entry sequence in a residue is dominated, their eventual signs are computable and can be intersected.

The load-bearing step is global. If$n_0\equiv \ell\pmod L$ and$M^{n_0}\ge0$, then the powers$M^{n_0(1+Lt)}$ remain in the same residue and have nonnegative matrix realizations. Applied entry by entry, Berstel's theorem (or Perron–Frobenius theory) forces those nondegenerate subsequences, and hence the original residue sequences, to be dominated. Therefore a single nondominated entry makes the entire residue empty.

This one-matrix theorem is unconditional. Schanuel's conjecture is used for the paper's broader theorem about commuting matrix semigroups, not for this result.

FPRD-MN-C01 · corollary

Both natural readings are decidable

An effective ultimately periodic set has a finite exceptional prefix and a periodic tail. Consequently,

• power nonnegativity asks whether $S(M)$ contains a positive exponent;
• eventual nonnegativity asks whether $S(M)$ is cofinite.

Both tests are decidable from the published construction. This is an application of an existing theorem, not a claim that FPRD Lab independently closed the decision problem.

FPRD-MN-C02 · counterexample

One good power does not give a good tail

For the scalar matrix $M=[-1]$, every even power is $[1]$ and every odd power is $[-1]$. Thus one positive nonnegative power exists, but the powers are not eventually nonnegative.

More generally, if $M^k\ge0$, then every multiple $M^{rk}=(M^k)^r$ is nonnegative. This gives an arithmetic progression, not necessarily a cofinite tail.

FPRD-MN-R01 · reduction

All entries can be interleaved into one recurrence

Each sequence $u_{ij}(n)=(M^n)_{ij}$is an LRS of order at most $d$. Number the $s=d^2$ entries by$r=0,\ldots,s-1$ and define$$v_{sn+r}=u_r(n).$$

If $U_r(x)=N_r(x)/D(x)$, then$$V(x)=\sum_{r=0}^{s-1}x^rU_r(x^s) =\frac{\sum_r x^rN_r(x^s)}{D(x^s)}.$$Hence $v$ has order at most$d^3$, and its ultimate nonnegativity is equivalent to eventual nonnegativity of the whole matrix sequence.

This reduction is valid but not decisive: general Ultimate Positivity for one LRS remains open. The matrix theorem succeeds by using structure shared across all entries.

FPRD-MN-F01 · counterfamily

A polynomial cutoff misses valid instances

Take a signed cycle of odd prime length $p$with one negative edge. Its first nonnegative power is$2p$. For block lengths$p_1,\ldots,p_k$, the block diagonal sum first becomes nonnegative at

Choosing the first odd primes gives dimension$d=\sum_i p_i$ and a least good exponent $\exp(\Theta(\sqrt{d\log d}))$. Thus no dimension-polynomial forward search is sound.

The exponent still has a short binary description. This family rules out one algorithmic strategy; it is not a decision-problem complexity lower bound.