On Shortest Linear Recurrences

✍ Scribed by G.H. Norton

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 601 KB
• Volume: 27
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1999.0255

✦ Synopsis

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.