K regular sequence - Alchetron, The Free Social Encyclopedia

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.

Definition

Let k ≥ 2 . An integer sequence s ( n ) n ≥ 0 is k-regular if the set of sequences

{ s ( k e n + r ) n ≥ 0 : e ≥ 0 and 0 ≤ r ≤ k e − 1 }

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

Ruler sequence

Let s ( n ) = ν 2 ( n + 1 ) be the 2 -adic valuation of n + 1 . The ruler sequence s ( n ) n ≥ 0 = 0 , 1 , 0 , 2 , 0 , 1 , 0 , 3 , … ( A007814) is 2 -regular, and the set

{ s ( 2 e n + r ) n ≥ 0 : e ≥ 0 and 0 ≤ r ≤ 2 e − 1 }

is contained in the 2 -dimensional vector space generated by s ( n ) n ≥ 0 and the constant sequence 1 , 1 , 1 , … . These basis elements lead to the recurrence equations

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 ) ,

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 ≥ 0 = 0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , … is 2 -regular, and

{ T ( 2 e n + r ) n ≥ 0 : e ≥ 0 and 0 ≤ r ≤ 2 e − 1 }

consists of the two sequences T ( n ) n ≥ 0 and T ( 2 n + 1 ) n ≥ 0 = 1 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , … .

Polynomial sequences

If f ( x ) is an integer-valued polynomial, then f ( n ) n ≥ 0 is k-regular for every k ≥ 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 ≥ 0 with values in R is ( R ′ , k ) -regular if the R ′ -module generated by

{ s ( k e n + r ) n ≥ 0 : e ≥ 0 and 0 ≤ r ≤ k e − 1 }

is finitely generated.

References

K-regular sequence Wikipedia

(Text) CC BY-SA

Contents