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 ${\displaystyle s(n)_{n\geq 0}}$ is k-regular if the set of sequences

${\displaystyle \{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 ${\displaystyle s(n)=\nu _{2}(n+1)}$ be the $2$-adic valuation of $n+1$. The ruler sequence ${\displaystyle s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots }$ ( A007814) is $2$-regular, and the set

${\displaystyle \{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 ${\displaystyle s(n)_{n\geq 0}}$ and the constant sequence ${\displaystyle 1,1,1,\dots }$. These basis elements lead to the recurrence equations

${\displaystyle {\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 ${\displaystyle s(0)=0}$ and ${\displaystyle s(1)=1}$, uniquely determine the sequence.

Thue–Morse sequence

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

${\displaystyle \{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 ${\displaystyle T(n)_{n\geq 0}}$ and ${\displaystyle T(2n+1)_{n\geq 0}=1,0,0,1,0,1,1,0,\dots }$.

Polynomial sequences

If $f(x)$ is an integer-valued polynomial, then ${\displaystyle 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 ${\displaystyle s(n)_{n\geq 0}}$ with values in $R$ is ${\displaystyle (R',k)}$-regular if the $R'$-module generated by

${\displaystyle \{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, doi:10.1016/0304-3975(92)90001-v.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003), "The ring of k-regular sequences, II", Theoretical Computer Science, 307: 3–29, doi:10.1016/s0304-3975(03)00090-2.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.