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

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \{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$-adic valuation 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

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \{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

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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. For example, the Thue–Morse sequence $T(n)_{n \geq 0} = 0, 1, 1, 0, 1, 0, 0, 1, \dots$ is $2$-regular, and

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \{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.

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

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \{s(k^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq k^e - 1\}

is finitely generated.

References

• .
• .