On shortest linear recurrences (Q1286449)

The author gives an expository account of a constructive theorem on the shortest linear recurrences of a finite sequence over an arbitrary integral domain \(R\). A generalization of rational approximation, called ``realization'', plays a key role in this paper. He also gives the associated ``minimal realization'' algorithm, which has a simple control structure and is division-free. It is easy to show that the number of \(R\)-multiplications required is \(O(n^2)\), where \(n\) is the length of the input sequence. His approach is algebraic and independent of any particular application viewing a linear recurring sequences as a torsion element in a natural \(R[X]\)-module. The standard \(R[X]\)-module of Laurent polynomials over \(R\) underlies our approach to finite sequences. The prerequisites are nominal and short Fibonacci sequences are used as running examples. \(\copyright\) Academic Press.