2015/02/28 by Graham H. Norton
Computer Science · Mathematics · #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics #Converse #Degree (music) #Discrete mathematics #Finite field #Mathematical analysis #Mathematics #Polynomial #Pure mathematics #Quotient #Rational function #Rational number #Sequence (biology) #cs.SC #semigroups and automata theory
paper · pdf · doi:10.1007/s00200-015-0256-5
Several more typos corrected. To appear in J. Applied Algebra in Engineering, Communication and Computing. The final publication version is available at Springer via http://dx.doi.org/10.1007/s00200-015-0256-5
arxiv created 2015/04/07 · arxiv updated 2015/04/08 · openalex publication_date 2015/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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) 'nth 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.