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

Let $s(n)=\nu _{2}(n+1)$ be the $2$-adic valuation of $n+1$. The ruler sequence $s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots$ (OEIS: 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{aligned}s(2n)&=0\\s(4n+1)&=s(2n+1)-s(n)\\s(4n+3)&=2s(2n+1)-s(n),\end{aligned}}$

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

Every k-automatic sequence is k-regular. 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(2n+1)_{n\geq 0}=1,0,0,1,0,1,1,0,\dots$.

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.

The nth term in a k-regular sequence grows at most polynomially in n.

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.

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.