Context
The equivalence identifies the native computational object: exact zeroness of one coordinate of an exponentially long linear orbit.
Definitions
- Binary matrix-power zeroness supplies an integer matrix, two indices, and a binary exponent.
Hypotheses and scope
- Matrices and recurrence data are explicit and binary encoded.
Proof or evidence
A companion representation gives g_n=αA^nβ; a two-state block extension makes this one entry of M^{n+2}. Conversely, every entry sequence (M^k)_{s,t} satisfies the characteristic recurrence by Cayley–Hamilton, with polynomial-size initial data.
Verification notes
The block dimensions, exponent shift, characteristic-polynomial signs, and initial-term size were checked.
Limitations
- The equivalence is about zeroness, not efficient expansion of the integer value.