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 $s(n)_$ is the set of subsequences
:$K_(s) = \.$
The sequence $s(n)_$ is (''R''′, ''k'')-regular (often shortened to just "''k''-regular") if the $R'$-module generated by ''K''_''k''(''s'') is a finitely-generated ''R''′- module.Allouche and Shallit (1992), Definition 2.1.

In the special case when $R' = R = \mathbb$, the sequence $s(n)_$ is $k$-regular if $K_k(s)$ is contained in a finite-dimensional vector space over $\mathbb$.

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 $\sum_ c_ s(k^n + b_)$, where ''c''_''ij'' is an integer, ''f''_''ij'' ≤ ''E'', and 0 ≤ ''b''_''ij'' ≤ ''k''^''f''_''ij'' − 1.Allouche & Shallit (1992), Theorem 2.2.

Alternatively, a sequence ''s''(''n'') is ''k''-regular if there exist an integer ''r'' and subsequences ''s''₁(''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''₀, ..., ''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''₀. Then a sequence ''s''(''n'') is ''k''-regular if and only if the formal series $\sum_ s(n) \tau (n)$ is $\mathbb$-rational.Allouche & Shallit (1992), Theorem 4.3.

Automata-theoretic

The formal series definition of a ''k''-regular sequence leads to an automaton characterization similar to Schützenberger's matrix machine.Allouche & Shallit (1992), Theorem 4.4.

History

The notion of ''k''-regular sequences was first investigated in a pair of papers by Allouche and Shallit.Allouche & Shallit (1992, 2003). 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) = \nu_2(n+1)$ be the $2$-adic valuation of $n+1$. The ruler sequence $s(n)_ = 0, 1, 0, 2, 0, 1, 0, 3, \dots$ () is $2$-regular, and the $2$-kernel
:$\$
is contained in the two-dimensional vector space generated by $s(n)_$ and the constant sequence $1, 1, 1, \dots$. These basis elements lead to the recurrence relations
:$\begin s(2 n) &= 0, \\ s(4 n + 1) &= s(2 n + 1) - s(n), \\ s(4 n + 3) &= 2 s(2 n + 1) - s(n), \end$
which, along with the initial conditions $s(0) = 0$ and $s(1) = 1$, uniquely determine the sequence.Allouche & Shallit (1992), Example 8.

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 $t(n)_$ and $t(2 n + 1)_$.

Cantor numbers

The sequence of Cantor numbers ''c''(''n'') () consists of numbers whose ternary expansions contain no 1s. It is straightforward to show that
:$\begin c(2n) &= 3c(n), \\ c(2n+1) &= 3c(n) + 2, \end$
and therefore the sequence of Cantor numbers is 2-regular. Similarly the Stanley sequence
:0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ...
of numbers whose ternary expansions contain no 2s is also 2-regular.Allouche & Shallit (1992), Examples 3 and 26.

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
:$\begin T(1) &= 0, \\ T(n) &= T(\lfloor n / 2 \rfloor) + T(\lceil n / 2 \rceil) + n - 1, \ n \geq 2. \end$
As a result, the sequence defined by the recurrence relation for merge sort, ''T''(''n''), constitutes a 2-regular sequence.Allouche & Shallit (1992), Example 28.

Other sequences

If $f(x)$ is an integer-valued polynomial, then $f(n)_$ is ''k''-regular for every $k \geq 2$.

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.
*Every ''k''-automatic sequence is ''k''-regular.
*Every ''k''-synchronized sequence is ''k''-regular.
*A ''k''-regular sequence takes on finitely many values if and only if it is ''k''-automatic.Allouche & Shallit (2003) p. 441. This is an immediate consequence of the class of ''k''-regular sequences being a generalization of the class of ''k''-automatic sequences.
*The class of ''k''-regular sequences is closed under termwise addition, termwise multiplication, and convolution. The class of ''k''-regular sequences is also closed under scaling each term of the sequence by an integer λ.Allouche & Shallit (2003) p. 445. In particular, the set of ''k''-regular power series forms a ring.
*If $s(n)_$ is ''k''-regular, then for all integers $m \ge 1$, $(s(n) \bmod)_$ is ''k''-automatic. However, the converse does not hold.
*For multiplicatively independent ''k'', ''l'' ≥ 2, if a sequence is both ''k''-regular and ''l''-regular, then the sequence satisfies a linear recurrence. This is a generalization of a result due to Cobham regarding sequences that are both ''k''-automatic and ''l''-automatic.
*The ''n''th term of a ''k''-regular sequence of integers grows at most polynomially in ''n''.
*If $F$ is a field and $x \in F$, then the sequence of powers $(x^n)_$ is ''k''-regular if and only if $x = 0$ or $x$ is a root of unity.

Proving and disproving ''k''-regularity

Given a candidate sequence $s = s(n)_$ 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 $s$ and proving that all elements of the form $(s(k^r n + e))_$ with $r$ sufficiently large and $0 \le e < 2^r$ can be written as linear combinations of kernel elements with smaller exponents in the place of $r$. This is usually computationally straightforward.

On the other hand, disproving ''k''-regularity of the candidate sequence $s$ usually requires one to produce a $\mathbb$-linearly independent subset in the kernel of $s$, which is typically trickier. Here is one example of such a proof.

Let $e_0(n)$ denote the number of $0$'s in the binary expansion of $n$. Let $e_1(n)$ denote the number of $1$'s in the binary expansion of $n$. The sequence $f(n) := e_0(n)-e_1(n)$ can be shown to be 2-regular. The sequence $g = g(n) := , f(n),$ is, however, not 2-regular, by the following argument. Suppose $(g(n))_$ is 2-regular. We claim that the elements $g(2^k n)$ for $n \ge 1$ and $k \ge 0$ of the 2-kernel of $g$ are linearly independent over $\mathbb$. The function $n \mapsto e_0(n)-e_1(n)$ is surjective onto the integers, so let $x_m$ be the least integer such that $e_0(x_m)-e_1(x_m) = m$. By 2-regularity of $(g(n))_$, there exist $b \ge 0$ and constants $c_i$ such that for each $n \ge 0$,
:$\sum_ c_i g(2^i n) = 0.$

Let $a$ be the least value for which $c_a \ne 0$. Then for every $n \ge 0$,
:$g(2^a n) = \sum_ -(c_i/c_a) g(2^i n).$

Evaluating this expression at $n = x_m$, where $m = 0,-1,1,2,-2$ and so on in succession, we obtain, on the left-hand side
:$g(2^a x_m) = , e_0(x_m)-e_1(x_m)+a, = , m+a, ,$

and on the right-hand side,
:$\sum_ -(c_i/c_a), m+i, .$

It follows that for every integer $m$,
:$, m+a, = \sum_ -(c_i/c_a) , m+i, .$

But for $m \ge -a-1$, the right-hand side of the equation is monotone because it is of the form $Am+B$ for some constants $A,B$, whereas the left-hand side is not, as can be checked by successively plugging in $m = -a-1$, $m = -a$, and $m = -a+1$. Therefore, $(g(n))_$ is not 2-regular.Allouche and Shallit (1993) p. 168–169.

Notes

References

*.
*.
*{{cite book , last1 = Allouche , first1 = Jean-Paul , last2 = Shallit , first2 = Jeffrey , author2-link = Jeffrey Shallit , isbn = 978-0-521-82332-6 , publisher = Cambridge University Press , title = Automatic Sequences: Theory, Applications, Generalizations , year = 2003 , zbl=1086.11015

Combinatorics on words
Automata (computation)
Integer sequences
Recurrence relations