On shortest linear recurrences

This is 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, which we call "realization", plays a key role throughout the paper. We also give 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. Our approach is algebraic and independent of any particular application. We view a linear recurring sequence 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 we use short Fibonacci sequences as running examples. (C) 1999 Academic Press.