16 - k-Regular Sequences

Summary

Up to now in this book we have dealt almost exclusively with sequences over a finite alphabet. While many interesting sequences, such as the Thue—Morse sequence, are of this form, there are also a large number of well-studied sequences over infinite alphabets such as Z. This naturally suggests the question of how the class of k-automatic sequences can be fruitfully generalized to the case of infinite alphabets.

In this chapter we examine one such possible generalization, called the class of k-regular sequences.

Basics

Recall that a sequence is k-automatic if and only if its k-kernel is finite. We say a sequence is k-regular if the Z-module generated by its k-kernel is finitely generated. (More general definitions are possible, but we do not cover them here.)

Example 16.1.1 Consider the function s₂(n) introduced in Chapter 3, which counts the sum of the bits in the binary expansion of n. If i ≥ 0 and 0 ≤ b < 2ⁱ, then we have s₂(2ⁱn + b) = s₂(n) + s₂(b). It follows that every element of the 2-kernel of the sequence (s₂(n))_n≥0 can be written as a Z-linear combination of the sequence (s₂(n))_n≥0 and the constant sequence 1. This is a prototypical example of a k-regular sequence.