In mathematics and theoretical computer science, a k-regular sequence is a sequence satisfying linear recurrence equations that reflect the base-k representations of the integers. The class of k-regular sequences generalizes the class of k-automatic sequences to alphabets of infinite size.
Definition There exist several characterizations of k-regular sequences, all of which are equivalent. Some common characterizations are as follows. For each, we take R′ to be a commutative Noetherian ring and we take R to be a ring containing R′.
k-kernel Let k ≥ 2. The k-kernel of the sequence s ( n ) n ≥ 0 {\displaystyle s(n)_{n\geq 0}} is the set of subsequences
K k ( s ) = { s ( k e n + r ) n ≥ 0 : e ≥ 0 and 0 ≤ r ≤ k e − 1 } . {\displaystyle K_{k}(s)=\{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.}
The sequence s ( n ) n ≥ 0 {\displaystyle s(n)_{n\geq 0}} is (R′, k)-regular (often shortened to just "k-regular") if the R ′ {\displaystyle R'} -module generated by Kk(s) is a finitely-generated R′-module. In the special case when R ′ = R = Q {\displaystyle R'=R=\mathbb {Q} } , the sequence s ( n ) n ≥ 0 {\displaystyle s(n)_{n\geq 0}} is k {\displaystyle k} -regular if K k ( s ) {\displaystyle K_{k}(s)} is contained in a finite-dimensional vector space over Q {\displaystyle \mathbb {Q} } .
Linear combinations A sequence s(n) is k-regular if there exists an integer E such that, for all ej > E and 0 ≤ rj ≤ kej − 1, every subsequence of s of the form s(kejn + rj) is expressible as an R′-linear combination ∑ i c i j s ( k f i j n + b i j ) {\displaystyle \sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})} , where cij is an integer, fij ≤ E, and 0 ≤ bij ≤ kfij − 1. Alternatively, a sequence s(n) is k-regular if there exist an integer r and subsequences s1(n), ..., sr(n) such that, for all 1 ≤ i ≤ r and 0 ≤ a ≤ k − 1, every sequence si(kn + a) in the k-kernel Kk(s) is an R′-linear combination of the subsequences si(n).
Formal series Let x0, ..., xk − 1 be a set of k non-commuting variables and let τ be a map sending some natural number n to the string xa0 ... xae − 1, where the base-k representation of x is the string ae − 1...a0. Then a sequence s(n) is k-regular if and only if the formal series ∑ n ≥ 0 s ( n ) τ ( n ) {\displaystyle \sum _{n\geq 0}s(n)\tau (n)} is Z {\displaystyle \mathbb {Z} } -rational.
Automata-theoretic The formal series definition of a k-regular sequence leads to an automaton characterization similar to Schützenberger's matrix machine.
History The notion of k-regular sequences was first investigated in a pair of papers by Allouche and Shallit. Prior to this, Berstel and Reutenauer studied the theory of rational series, which is closely related to k-regular sequences.
Examples
Ruler sequence Let s ( n ) = ν 2 ( n + 1 ) {\displaystyle s(n)=\nu _{2}(n+1)} be the 2 {\displaystyle 2} -adic valuation of n + 1 {\displaystyle n+1} . The ruler sequence s ( n ) n ≥ 0 = 0 , 1 , 0 , 2 , 0 , 1 , 0 , 3 , … {\displaystyle s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots } (OEIS: A007814) is 2 {\displaystyle 2} -regular, and the 2 {\displaystyle 2} -kernel
{ s ( 2 e n + r ) n ≥ 0 : e ≥ 0 and 0 ≤ r ≤ 2 e − 1 } {\displaystyle \{s(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}
… excerpt ends here. Continue reading the full article.
