FPRD-LRS-D01 · input model

The indexed zero question

An order-$d$ rational linear recurrence sequence is supplied by binary-encoded initial values and coefficients satisfying

$$f_{k+d}=\sum_{i=0}^{d-1}c_i f_{k+i}.$$

The index $n$ is also binary encoded. The decision problem asks only whether $f_n=0$; it does not ask for the full expansion of $f_n$.

The public source specifies a rational LRS and a binary index but not a concrete syntax. This page fixes the ordinary explicit recurrence representation above. Rational generating functions, weighted automata, closed forms, or succinct recurrence order are different input models and are not covered automatically.

FPRD-LRS-T01 · proposition

A zero-preserving integer normalization

Choose positive common multiples $Q$ of the coefficient denominators and $E$ of the initial-value denominators. Put

$$g_k=EQ^k f_k.$$

Clearing recurrence denominators only once is not valid; the index-dependent factor $Q^k$ is essential.

FPRD-LRS-T02 · theorem

Equivalence with a binary matrix-power entry

A companion representation gives an integer matrix $A$, row $\alpha$, and column $\beta$ with

$$g_n=\alpha A^n\beta.$$

Use the block matrix

$$M=\begin{pmatrix}0&\alpha&0\\0&A&\beta\\0&0&0\end{pmatrix}.$$

Then $(M^{n+2})_{1,d+2}=g_n$. Conversely, every entry sequence $(M^k)_{s,t}$ satisfies the characteristic recurrence of $M$ by Cayley–Hamilton.

FPRD-LRS-T03 · randomized upper bound

A compact circuit and a one-sided zero test

Repeated squaring builds a division-free integer circuit for the selected entry using $O(d^3\log n)$ arithmetic gates with ordinary matrix multiplication.

This is a direct many-one reduction to integer straight-line- program zeroness, usually called EquSLP. Schönhage's standard randomized modular argument places EquSLP in$\mathsf{coRP}$: zero outputs remain zero modulo every sampled prime, while the sampling range is chosen from the circuit-size growth bound so that a nonzero output is missed with probability at most one half. Independent repetition reduces that one-sided error.

“Choose a random large prime” without a circuit-dependent range is not a proof. The proposition imports the quantified EquSLP upper bound; it asserts no reverse reduction, EquSLP hardness, or deterministic algorithm.

FPRD-LRS-T04 · certificate upper bound

A short certificate for nonzeroness

The prime-size step uses a standard upper bound on the$k$th prime; deterministic polynomial-time verification of primality is supplied by Agrawal–Kayal–Saxena. The certificate does not require factoring the circuit output.

FPRD-LRS-F01 · failed approach

Why explicit powering is not enough

The order-one recurrence$$u_0=1,\qquad u_{k+1}=2u_k$$has $u_n=2^n$, whose binary expansion has $n+1$ bits. A binary index of length $\ell$ can therefore request an output with $2^{\Theta(\ell)}$ bits.

This rules out explicit expansion as a general polynomial-time strategy. It is not a hardness result for zeroness—the example itself is trivially nonzero.

FPRD-LRS-B01 · open boundary

The deterministic question remains

The present work separates compact representation, randomized one-sided verification, nondeterministic nonzero certificates, and deterministic decision. It does not provide a deterministic polynomial-time zero test. Nor does it prove that these structured repeated-power circuits are as hard as general EquSLP.

A fixed polynomial list of moduli is insufficient: a nonzero term may be divisible by every prime in that list. Promising narrower targets include fixed order, diagonalizable characteristic polynomials, nondegenerate recurrences, and restricted coefficient semigroups.