On sequences, rational functions and decomposition

DOI10.1007/S00200-015-0256-5MaRDI QIDQ499747zbMATH OpenOpenAlexFDO

Authors G. H. Norton

Publication date 6 October 2015

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.06152

zbMATH Keywords

minimal polynomialcontinued fractionLaurent seriesrational functionpartial quotientlinear recurrenceBerlekamp-Massey algorithmkey equation

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Arithmetic rings and other special commutative rings (13F99) Combinatorial codes (94B25)

Abstract: Our overall goal is to unify and extend some results in the literature related to the approximation of generating functions of finite and infinite sequences over a field by rational functions. In our approach, numerators play a significant role. We revisit a theorem of Niederreiter on (i) linear complexities and (ii) '$n^{th}$ minimal polynomials' of an infinite sequence, proved using partial quotients. We prove (i) and its converse from first principles and generalise (ii) to rational functions where the denominator need not have minimal degree. We prove (ii) in two parts: firstly for geometric sequences and then for sequences with a jump in linear complexity. The basic idea is to decompose the denominator as a sum of polynomial multiples of two polynomials of minimal degree; there is a similar decomposition for the numerators. The decomposition is unique when the denominator has degree at most the length of the sequence. The proof also applies to rational functions related to finite sequences, generalising a result of Massey. We give a number of applications to rational functions associated to sequences.

Recommendations

• Continued fractions and the Berlekamp-Massey algorithm
• An algebraic method to solve the minimal partial realization problem for scalar sequences
• Fast rational interpolation, Reed-Solomon decoding, and the linear complexity profiles of sequences
• The Berlekamp-Massey algorithm and linear recurring sequences over a factorial domain
• A generalized rational interpolation problem and the solution of the Welch-Berlekamp key equation

Cites work

• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• scientific article; zbMATH DE number 4062985 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• Algebraic coding theory
• An Algorithm for Computing Minimal Bidirectional Linear Recurrence Relations
• Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm
• Continued Fractions and Linear Recurrences
• Continued fractions and Berlekamp's algorithm
• Infective Envelopes and Inverse Polynomials
• On shortest linear recurrences
• On the continued fraction and Berlekamp's algorithm (Corresp.)
• On the minimal realizations of a finite sequence
• Shift-register synthesis and BCH decoding

Cited in

(3)

• scientific article; zbMATH DE number 7043132 (Why is no real title available?)
• On the annihilator ideal of an inverse form
• On a sequence of rational functions

Describes a project that uses

Uses Software

• CoCoA

This page was built for publication: On sequences, rational functions and decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499747)