k-regular sequence

In mathematics and theoretical computer science, a k-regular sequence is an infinite sequence of terms characterized by a finite automaton with auxiliary storage. They are a generalization 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) is the set of subsequences

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

The sequence s(n) is (R′, k)-regular (often shortened to just "k-regular") if K_k(s) is a sub-module of a finitely-generated R′-module.

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\geq 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\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.

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

$\{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$.

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.

References

• Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k-regular sequences", Theoret. Comput. Sci., 98: 163–197, doi:10.1016/0304-3975(92)90001-v.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003), "The ring of k-regular sequences, II", Theoret. Comput. Sci., 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.