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 . An integer sequence is k-regular if the set of sequences

is contained in a finite-dimensional vector space over the field of rational numbers.

Examples

Ruler sequence

Let be the -adic valuation of . The ruler sequence (A007814) is -regular, and the set

is contained in the -dimensional vector space generated by and the constant sequence . These basis elements lead to the recurrence equations

which, along with initial conditions and , uniquely determine the sequence.

Thue–Morse sequence

Every k-automatic sequence is k-regular.[1] For example, the Thue–Morse sequence is -regular, and

consists of the two sequences and .

Polynomial sequences

If is an integer-valued polynomial, then is k-regular for every .

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 as follows. Let be a commutative Noetherian subring of . A sequence with values in is -regular if the -module generated by

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

This article is issued from Wikipedia - version of the 8/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.