On sequences, rational functions and decomposition

It is classical that well-known identities and properties of partial quotients furnish rational approximation in $$\mathbb {F}[[x^{-1}]]$$F[[]]. For a rational function, this is the extended Euclidean algorithm in $$\mathbb {F}[x]$$F[x]. Berlekamp’s heuristic solution of the ‘key equation’ essentially approximates an element of $$\mathbb {F}[x]$$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 $$\mathrm {D}[x^{-1},x], \mathrm {D}$$D[,x],D a commutative domain. The linear complexity (of a finite initial subsequence) of an infinite sequence over $$\mathbb {F}$$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 $$\mathrm {D}$$D. Examples are classical approximation in $$\mathbb {F}[[x^{-1}]]$$F[[]] and approximation using $$\mathrm {D}[x^{-1},x]$$D[,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 $$\mathbb {F}[x^{-1},x]$$F[,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