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.
There exist several characterizations of k-regular sequences, all of which are equivalent.
is the set of subsequences The sequence
-module generated by Kk(s) is a finitely-generated R′-module.
is contained in a finite-dimensional vector space over
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
, where cij is an integer, fij ≤ E, and 0 ≤ bij ≤ kfij − 1.
[2] 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).
[2] 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
[3] The formal series definition of a k-regular sequence leads to an automaton characterization similar to Schützenberger's matrix machine.
[4][5] The notion of k-regular sequences was first investigated in a pair of papers by Allouche and Shallit.
[6] Prior to this, Berstel and Reutenauer studied the theory of rational series, which is closely related to k-regular sequences.
-kernel is contained in the two-dimensional vector space generated by
These basis elements lead to the recurrence relations which, along with the initial conditions
[8] The Thue–Morse sequence t(n) (OEIS: A010060) is the fixed point of the morphism 0 → 01, 1 → 10.
The sequence of Cantor numbers c(n) (OEIS: A005823) consists of numbers whose ternary expansions contain no 1s.
It is straightforward to show that and therefore the sequence of Cantor numbers is 2-regular.
Similarly the Stanley sequence of numbers whose ternary expansions contain no 2s is also 2-regular.
[9] A somewhat interesting application of the notion of k-regularity to the broader study of algorithms is found in the analysis of the merge sort algorithm.
Given a list of n values, the number of comparisons made by the merge sort algorithm are the sorting numbers, governed by the recurrence relation As a result, the sequence defined by the recurrence relation for merge sort, T(n), constitutes a 2-regular sequence.
Allouche and Shallit give a number of additional examples of k-regular sequences in their papers.
[6] k-regular sequences exhibit a number of interesting properties.
that is not known to be k-regular, k-regularity can typically be proved directly from the definition by calculating elements of the kernel of
and proving that all elements of the form
can be written as linear combinations of kernel elements with smaller exponents in the place of
On the other hand, disproving k-regularity of the candidate sequence
, the right-hand side of the equation is monotone because it is of the form
, whereas the left-hand side is not, as can be checked by successively plugging in