Exact-prefix identification of rational sequences

Exact statement

A rational series of positive Hankel rank $r$ is determined and reconstructible from exactly $2r$ initial coefficients, and this count is sharp. With a known bound $R\ge r$ , $2R$ coefficients give certified exact reconstruction; without a known rank bound, repeated reconstruction identifies every rational series in the limit. The rank-zero class contains only the zero series.

StatusClassical recurrence reconstruction, restated and proved for this model

External reviewThe recurrence-reconstruction theorem is classical; no external review of this FPRD exposition is recorded.

Context

Over a field, finite Hankel rank is the algebraic dimension of a rational sequence and equals the size of its minimal linear representation.

Hypotheses and scope

The target is a rational formal power series over the rationals.
The learner receives exact coefficients in increasing degree order.

Proof or evidence

Massey's shift-register synthesis recovers a complexity-r recurrence from 2r samples. Multiplying the connection polynomial by the observed prefix recovers the numerator. Uniqueness follows because a nonzero sequence first nonzero at index m has Hankel rank at least m+1. Sharpness follows by splitting the order-(2r-1) finite-difference identity into its even and odd nodes, producing two rank-r exponential sums that agree on 2r-1 coefficients and differ on the next.

Exact-prefix theorem →

Verification notes

The former ‘more than 2r’ and ‘2R+1’ wording was one coefficient too conservative and disagreed with its own uniqueness proof. The corrected 2r count was checked on 5,856 exact small recurrences and seven sharp finite-difference families. Field-operation complexity remains separate from rational bit complexity.

Limitations

The theorem does not provide a finite stopping certificate when no rank bound is known.
It does not extend automatically to arbitrary semirings or approximate coefficients.

Open work

Quantify coefficient bit growth for the intended application and add a certified-prefix extractor if its approximants provide one.