K-regular sequence

A k-regular sequence is an infinite sequence satisfying recurrence equations of a certain type, in which the nth term is a linear combination of mth terms for some integers m whose base-k representations are close to that of n.

Regular sequences generalize automatic sequences to infinite alphabets.

Definition

Let $k \geq 2$. An integer sequence $s(n)_{n \geq 0}$ is k-regular if the set of sequences

$\{s(k^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq k^e - 1\}$

is contained in a finite-dimensional vector space over the field of rational numbers.

Examples

Ruler sequence

Let $s(n) = \nu_2(n+1)$ be the $2$ of $n+1$. The ruler sequence $s(n)_{n \geq 0} = 0, 1, 0, 2, 0, 1, 0, 3, \dots$ ( A007814) is $2$-regular, and the set

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

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

$\begin{align} 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{align}$

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

Thue–Morse sequence

Every k-automatic sequence is k-regular.^[1] For example, the Thue–Morse sequence $T(n)_{n \geq 0} = 0, 1, 1, 0, 1, 0, 0, 1, \dots$ is $2$-regular, and

$\{T(2^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq 2^e - 1\}$

consists of the two sequences $T(n)_{n \geq 0}$ and $T(2 n + 1)_{n \geq 0} = 1, 0, 0, 1, 0, 1, 1, 0, \dots$.

Polynomial sequences

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

Properties

The class of k-regular sequences is closed under termwise addition and multiplication.^[2]

The nth term in a k-regular sequence grows at most polynomially in n.^[3]

Generalizations

The notion of a k-regular sequence can be generalized to a ring $R$ as follows. Let $R'$ be a commutative Noetherian subring of $R$. A sequence $s(n)_{n \geq 0}$ with values in $R$ is $(R', k)$-regular if the $R'$-module generated by

$\{s(k^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq k^e - 1\}$

is finitely generated.

Notes

1. Allouche & Shallit (1992) Theorem 2.3
2. Allouche & Shallit (1992) Theorem 2.5
3. Allouche & Shallit (1992) Theorem 2.10

References

• Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k-regular sequences", Theoretical Computer Science 98: 163–197.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003), "The ring of k-regular sequences, II", Theoretical Computer Science 307: 3–29.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.