On sequences, rational functions and decomposition

Norton, Graham H. (2015) On sequences, rational functions and decomposition. Applicable Algebra in Engineering, Communications and Computing, 26 5: 427-463. doi:10.1007/s00200-015-0256-5

Author Norton, Graham H.
Title On sequences, rational functions and decomposition
Journal name Applicable Algebra in Engineering, Communications and Computing   Check publisher's open access policy
ISSN 0938-1279
Publication date 2015
Year available 2015
Sub-type Article (original research)
DOI 10.1007/s00200-015-0256-5
Open Access Status Not yet assessed
Volume 26
Issue 5
Start page 427
End page 463
Total pages 37
Place of publication Heidelberg, Germany
Publisher Springer
Collection year 2016
Language eng
Formatted abstract
It is classical that well-known identities and properties of partial quotients furnish rational approximation in F[[x−1]]. For a rational function, this is the extended Euclidean algorithm in F[x]. Berlekamp’s heuristic solution of the ‘key equation’ essentially approximates an element of F[x] with constant term 1 via a quotient of reciprocals, and his solutions satisfy a number of identities. In earlier papers we gave a solution of an analogous problem using D[x−1,x],D a commutative domain. The linear complexity (of a finite initial subsequence) of an infinite sequence over F has been related to the degrees of its partial quotients by Mills, Cheng, Niederreiter and others. We use first principles and induction to relate these linear complexities to the degrees of its partial quotients. Berlekamp has also described the set of solutions of the key equation. We define a pairing of minimal solutions and a ‘minimal system’ of a finite sequence over D. Examples are classical approximation in F[[x−1]] and approximation using D[x−1,x]. We use minimal systems to generalise results of Massey and Niederreiter to arbitrary solutions, including numerators. This includes explicit and unique decomposition of both parts of a solution into a sum of (polynomial) multiples of solutions with minimal degree denominators. The unique multipliers also satisfy degree constraints. We give several applications to gcd’s of sequence polynomials and relate partial-quotient solutions to solutions derived using F[x−1,x]. We give a precise count of the number of solutions when the field is finite. Our final application concerns when the first component of a minimal solution vanishes at some scalar; a simple modification of our approach gives a new solution, the first component of which does not vanish at the scalar and which has minimal degree. We also describe the corresponding set of solutions. This simplifies and generalises work of Salagean. We conclude that numerators (or second components) of solutions can play a significant role in proofs of properties of denominators (or first components) and that they enjoy similar properties.
Keyword Berlekamp–Massey algorithm
Continued fraction
Key equation
Laurent series
Linear recurrence
Minimal polynomial
Partial quotient
Rational function
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Official 2016 Collection
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 12 May 2015, 00:37:04 EST by System User on behalf of School of Mathematics & Physics