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. On sequences, rational functions and decomposition Applicable Algebra in Engineering, Communications and Computing   Check publisher's open access policy 0938-12791432-0622 2015 2015 Article (original research) 10.1007/s00200-015-0256-5 Not yet assessed 26 5 427 463 37 Heidelberg, Germany Springer 2016 eng 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. Berlekampâ€“Massey algorithmContinued fractionKey equationLaurent seriesLinear recurrenceMinimal polynomialPartial quotientRational function C1 Confirmed Code UQ

 Document type: Journal Article Article (original research) School of Mathematics and Physics Official 2016 Collection

 Versions Version Filter Type Tue, 12 May 2015, 00:37:08 EST Tue, 12 May 2015, 06:32:37 EST Tue, 04 Aug 2015, 13:03:03 EST Tue, 04 Aug 2015, 13:04:17 EST Mon, 31 Aug 2015, 11:42:52 EST Tue, 06 Oct 2015, 02:48:57 EST Wed, 14 Oct 2015, 00:03:36 EST Sun, 18 Oct 2015, 00:17:58 EST Fri, 30 Oct 2015, 09:52:05 EST Fri, 30 Oct 2015, 09:55:54 EST Filtered Full
Citation counts: Cited 0 times in Thomson Reuters Web of Science Article Cited 0 times in Scopus Article Search Google Scholar Tue, 12 May 2015, 00:37:04 EST by System User on behalf of School of Mathematics & Physics