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{)}_{n\ge 0}$ is the set of subsequences

$K_k(s)=\{s(k^{e}n+r{)}_{n\ge 0}:e\ge 0\text{ and }0\le r\le k^e-1\}.$

The sequence $s(n{)}_{n\ge 0}$ is (R′, k)-regular (often shortened to just "k-regular") if the $R^{\prime }$-module generated by K_k(s) is a finitely-generated R′-module.

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

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_jn + r_j) is expressible as an R′-linear combination $\sum _i{c}_{ij}s(k^{f_{ij}}n+b_{ij})$, 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₁(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_a0 ... x_ae − 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 _{n\ge 0}s(n)\tau (n)$ is $\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)={\nu }_2(n+1)$ be the $2$-adic valuation of $n+1$. The ruler sequence $s(n{)}_{n\ge 0}=0,1,0,2,0,1,0,3,\dots$ (Template:OEIS2C) is $2$-regular, and the $2$-kernel

$\{s(2^{e}n+r{)}_{n\ge 0}:e\ge 0\text{ and }0\le r\le 2^e-1\}$

is contained in the two-dimensional vector space generated by $s(n{)}_{n\ge 0}$ and the constant sequence $1,1,1,\dots$. These basis elements lead to the recurrence relations

$\begin{array}{cc}s(2n)& =0,\\ s(4n+1)& =s(2n+1)-s(n),\\ s(4n+3)& =2s(2n+1)-s(n),\end{array}$

which, along with the initial conditions $s(0)=0$ and $s(1)=1$, uniquely determine the sequence.

Thue–Morse sequence

The Thue–Morse sequence t(n) (Template:OEIS2C) 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

$\{t(2^{e}n+r{)}_{n\ge 0}:e\ge 0\text{ and }0\le r\le 2^e-1\}$

consists of the subsequences $t(n{)}_{n\ge 0}$ and $t(2n+1{)}_{n\ge 0}$.

Cantor numbers

The sequence of Cantor numbers c(n) (Template:OEIS2C) consists of numbers whose ternary expansions contain no 1s. It is straightforward to show that

$\begin{array}{cc}c(2n)& =3c(n),\\ c(2n+1)& =3c(n)+2,\end{array}$

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, ... Template:OEIS

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

$\begin{array}{cc}T(1)& =0,\\ T(n)& =T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,n\ge 2.\end{array}$

As a result, the sequence defined by the recurrence relation for merge sort, T(n), constitutes a 2-regular sequence.

Other sequences

If $f(x)$ is an integer-valued polynomial, then $f(n{)}_{n\ge 0}$ is k-regular for every $k\ge 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. 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 λ. In particular, the set of k-regular power series forms a ring.
• If $s(n{)}_{n\ge 0}$ is k-regular, then for all integers $m\ge 1$, $(s(n)modm{)}_{n\ge 0}$ 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 nth 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{)}_{n\ge 0}$ 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{)}_{n\ge 0}$ 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){)}_{n\ge 0}$ 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{Z}$-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){)}_{n\ge 0}$ 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{Z}$. 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){)}_{n\ge 0}$, there exist $b\ge 0$ and constants $c_i$ such that for each $n\ge 0$,

$\sum _{0\le i\le b}{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 _{a+1\le i\le b}-(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 _{a+1\le i\le b}-(c_i/c_a)|m+i|.$

It follows that for every integer $m$,

$|m+a|=\sum _{a+1\le i\le b}-(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){)}_{n\ge 0}$ is not 2-regular.

References

• Template:Citation.
• Template:Citation.
• Template:Cite book