On sequences, rational functions and decomposition

DOI10.1007/S00200-015-0256-5zbMATH Open1400.11160arXiv1502.06152OpenAlexW2015702637MaRDI QIDQ499747FDOQ499747

Authors: G. H. Norton 

Publication date: 6 October 2015

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Algebraic coding theory
• Title not available (Why is that?)
• Shift-register synthesis and BCH decoding
• Title not available (Why is that?)
• On the continued fraction and Berlekamp's algorithm (Corresp.)
• Infective Envelopes and Inverse Polynomials
• On shortest linear recurrences
• On the minimal realizations of a finite sequence
• Continued Fractions and Linear Recurrences
• Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm
• Continued fractions and Berlekamp's algorithm
• An Algorithm for Computing Minimal Bidirectional Linear Recurrence Relations

Cited In (3)

• Title not available (Why is that?)
• On the annihilator ideal of an inverse form
• On a sequence of rational functions

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)