K-regular sequence

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 formula_1 is the set of subsequences
The sequence formula_1 is ("R"′, "k")-regular (often shortened to just ""k"-regular") if the formula_4-module generated by "K""k"("s") is a finitely-generated "R"′-module.
In the special case when formula_5, the sequence formula_1 is formula_7-regular if formula_8 is contained in a finite-dimensional vector space over formula_9.
Linear combinations.
A sequence "s"("n") is "k"-regular if there exists an integer "E" such that, for all "e""j" > "E" and 0 ≤ "r""j" ≤ "k""e""j" − 1, every subsequence of "s" of the form "s"("k""e""j""n" + "r""j") is expressible as an "R"′-linear combination formula_10, where "c""ij" is an integer, "f""ij" ≤ "E", and 0 ≤ "b""ij" ≤ "k""f""ij" − 1.
Alternatively, a sequence "s"("n") is "k"-regular if there exist an integer "r" and subsequences "s"1("n"), ..., "s""r"("n") such that, for all 1 ≤ "i" ≤ "r" and 0 ≤ "a" ≤ "k" − 1, every sequence "s""i"("kn" + "a") in the "k"-kernel "K""k"("s") is an "R"′-linear combination of the subsequences "s""i"("n").
Formal series.
Let "x"0, ..., "x""k" − 1 be a set of "k" non-commuting variables and let τ be a map sending some natural number "n" to the string "x""a"0 ... "x""a""e" − 1, where the base-"k" representation of "x" is the string "a""e" − 1..."a"0. Then a sequence "s"("n") is "k"-regular if and only if the formal series formula_11 is formula_12-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 formula_13 be the formula_14-adic valuation of formula_15. The ruler sequence formula_16 () is formula_14-regular, and the formula_14-kernel
is contained in the two-dimensional vector space generated by formula_1 and the constant sequence formula_21. These basis elements lead to the recurrence relations
which, along with the initial conditions formula_23 and formula_24, uniquely determine the sequence.
Thue–Morse sequence.
The Thue–Morse sequence "t"("n") () is the fixed point of the morphism 0 → 01, 1 → 10. It is known that the Thue–Morse sequence is 2-automatic. Thus, it is also 2-regular, and its 2-kernel
consists of the subsequences formula_26 and formula_27.
Cantor numbers.
The sequence of Cantor numbers "c"("n") () 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.
Sorting numbers.
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.
Other sequences.
If formula_30 is an integer-valued polynomial, then formula_31 is "k"-regular for every formula_32.
The Glaisher–Gould sequence is 2-regular. The Stern–Brocot sequence is 2-regular.
Allouche and Shallit give a number of additional examples of "k"-regular sequences in their papers.
Properties.
"k"-regular sequences exhibit a number of interesting properties.
Proving and disproving "k"-regularity.
Given a candidate sequence formula_41 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 formula_42 and proving that all elements of the form formula_43 with formula_44 sufficiently large and formula_45 can be written as linear combinations of kernel elements with smaller exponents in the place of formula_44. This is usually computationally straightforward.
On the other hand, disproving "k"-regularity of the candidate sequence formula_42 usually requires one to produce a formula_12-linearly independent subset in the kernel of formula_42, which is typically trickier. Here is one example of such a proof.
Let formula_50 denote the number of formula_51's in the binary expansion of formula_52. Let formula_53 denote the number of formula_54's in the binary expansion of formula_52. The sequence formula_56 can be shown to be 2-regular. The sequence formula_57 is, however, not 2-regular, by the following argument. Suppose formula_58 is 2-regular. We claim that the elements formula_59 for formula_60 and formula_61 of the 2-kernel of formula_62 are linearly independent over formula_12. The function formula_64 is surjective onto the integers, so let formula_65 be the least integer such that formula_66. By 2-regularity of formula_58, there exist formula_68 and constants formula_69 such that for each formula_70,
Let formula_72 be the least value for which formula_73. Then for every formula_70,
Evaluating this expression at formula_76, where formula_77 and so on in succession, we obtain, on the left-hand side
and on the right-hand side,
It follows that for every integer formula_80,
But for formula_82, the right-hand side of the equation is monotone because it is of the form formula_83 for some constants formula_84, whereas the left-hand side is not, as can be checked by successively plugging in formula_85, formula_86, and formula_87. Therefore, formula_58 is not 2-regular.