Engineering / Mathematics — Polynomial Algorithms
Linearly Generated Sequences
Sequences satisfying linear recurrences, their minimal polynomials, and the equivalence with rational generating functions.
Executive summary
A sequence is linearly generated if it satisfies a linear recurrence with constant coefficients. The set of such recurrences forms an ideal whose monic generator is the minimal polynomial.
Equivalently, the generating function is rational, which is what connects the topic to rational function reconstruction.
Learning objectives
- Define linearly generated sequences and their minimal polynomial.
- State the equivalence with rational generating functions.
- Identify where such sequences arise.
01Definition and the annihilator ideal
Linearly generated sequence
A sequence (s₀, s₁, ...) over a field is linearly generated if there are constants c₀, ..., c_{d−1} with
s_{n+d} = c_{d−1}s_{n+d−1} + ... + c₀s_n for all n.
The annihilator is an ideal
The set of polynomials annihilating a sequence is an ideal of F[X], hence principal. Its monic generator is the minimal polynomial of the sequence.
Every recurrence satisfied by the sequence corresponds to a multiple of the minimal polynomial, so the minimal one is the shortest recurrence and every other is derived from it. This is the same structure as the minimal polynomial of an algebra element, and for good reason — both are annihilator ideals in a principal ideal domain.
02Rational generating functions
Equivalence
A sequence is linearly generated if and only if its generating function Σ s_n X^n is a rational function, with denominator the reversed minimal polynomial.
The correspondence turns a question about recurrences into one about rational functions, which is what makes rational function reconstruction the right tool for finding the minimal polynomial.
Σ s_n X^n = g(X) / f*(X), where f* is the reversal of the minimal polynomial f03Where such sequences arise
| Source | Sequence | Minimal polynomial meaning |
|---|---|---|
| Powers of a matrix | uᴼAⁿv for fixed vectors | Divides the minimal polynomial of A |
| Powers of a field element | Trace of αⁿ | The minimal polynomial of α |
| Linear feedback shift register | The output stream | The feedback polynomial |
| Reed-Solomon syndromes | Syndrome sequence | The error locator polynomial |
| Combinatorial counts | Fibonacci and relatives | The characteristic polynomial |
The first row is the basis of block Wiedemann sparse linear algebra: projecting matrix powers onto vectors gives a linearly generated sequence whose minimal polynomial reveals the structure needed to solve the system, without ever forming a dense matrix.
The fourth row is the coding connection. The syndrome sequence of a Reed–Solomon codeword is linearly generated by the error locator polynomial, so decoding is finding that minimal polynomial — which is why Berlekamp–Massey serves as a decoder.
04Frequently asked questions
How many terms determine the minimal polynomial?
Twice its degree suffices. With 2d terms, Berlekamp-Massey or the Euclidean method recovers a minimal polynomial of degree at most d, and fewer terms leave genuine ambiguity.
Is every sequence linearly generated?
No. A sequence must satisfy some finite recurrence, and most do not — the factorials and the primes are not linearly generated. Finite sequences trivially are, by a recurrence of length equal to the sequence.
What is the relation to LFSRs?
A linear feedback shift register produces exactly a linearly generated sequence, and its feedback polynomial is the minimal polynomial. Berlekamp-Massey recovers the register from its output, which is why the algorithm matters in stream cipher cryptanalysis.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 423-428.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.