K-regular sequence

In mathematics and theoretical computer science, a k-regular sequence is a sequence satisfying linear recurrence equations that reflect the base-k representations of the integers. The class of k-regular sequences generalizes the class of k-automatic sequences to alphabets of infinite size.

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′.

Let k ≥ 2. The k-kernel of the sequence s ( n ) n ≥ 0 {\displaystyle s(n)_{n\geq 0}} is the set of subsequences

K k ( s ) = { s ( k e n + r ) n ≥ 0 : e ≥ 0  and  0 ≤ r ≤ k e − 1 } . {\displaystyle K_{k}(s)=\{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.}

The sequence s ( n ) n ≥ 0 {\displaystyle s(n)_{n\geq 0}} is (R′, k)-regular (often shortened to just "k-regular") if the R ′ {\displaystyle R'} -module generated by K_k(s) is a finitely-generated R′-module.^[1]

In the special case when R ′ = R = Q {\displaystyle R'=R=\mathbb {Q} } , the sequence s ( n ) n ≥ 0 {\displaystyle s(n)_{n\geq 0}} is k {\displaystyle k} -regular if K k ( s ) {\displaystyle K_{k}(s)} is contained in a finite-dimensional vector space over Q {\displaystyle \mathbb {Q} } .

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 ∑ i c i j s ( k f i j n + b i j ) {\displaystyle \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.^[2]

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).^[2]

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 ∑ n ≥ 0 s ( n ) τ ( n ) {\displaystyle \sum _{n\geq 0}s(n)\tau (n)} is Z {\displaystyle \mathbb {Z} } -rational.^[3]

The formal series definition of a k-regular sequence leads to an automaton characterization similar to Schützenberger's matrix machine.^[4][5]

The notion of k-regular sequences was first investigated in a pair of papers by Allouche and Shallit.^[6] Prior to this, Berstel and Reutenauer studied the theory of rational series, which is closely related to k-regular sequences.^[7]

Let s ( n ) = ν 2 ( n + 1 ) {\displaystyle s(n)=\nu _{2}(n+1)} be the 2 {\displaystyle 2} -adic valuation of n + 1 {\displaystyle n+1} . The ruler sequence s ( n ) n ≥ 0 = 0 , 1 , 0 , 2 , 0 , 1 , 0 , 3 , … {\displaystyle s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots } (OEIS: A007814) is 2 {\displaystyle 2} -regular, and the 2 {\displaystyle 2} -kernel

{ s ( 2 e n + r ) n ≥ 0 : e ≥ 0  and  0 ≤ r ≤ 2 e − 1 } {\displaystyle \{s(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}

is contained in the two-dimensional vector space generated by s ( n ) n ≥ 0 {\displaystyle s(n)_{n\geq 0}} and the constant sequence 1 , 1 , 1 , … {\displaystyle 1,1,1,\dots } . These basis elements lead to the recurrence relations

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 ) , {\displaystyle {\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 the initial conditions s ( 0 ) = 0 {\displaystyle s(0)=0} and s ( 1 ) = 1 {\displaystyle s(1)=1} , uniquely determine the sequence.^[8]

The Thue–Morse sequence t(n) (OEIS: A010060) is the fixed point of the morphism 0 → 01, 1 → 10. It is known that the Thue–Morse sequence is 2-automatic. Thus, it is also 2-regular, and its 2-kernel

{ t ( 2 e n + r ) n ≥ 0 : e ≥ 0  and  0 ≤ r ≤ 2 e − 1 } {\displaystyle \{t(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}

consists of the subsequences t ( n ) n ≥ 0 {\displaystyle t(n)_{n\geq 0}} and t ( 2 n + 1 ) n ≥ 0 {\displaystyle t(2n+1)_{n\geq 0}} .

The sequence of Cantor numbers c(n) (OEIS: A005823) consists of numbers whose ternary expansions contain no 1s. It is straightforward to show that

c ( 2 n ) = 3 c ( n ) , c ( 2 n + 1 ) = 3 c ( n ) + 2 , {\displaystyle {\begin{aligned}c(2n)&=3c(n),\\c(2n+1)&=3c(n)+2,\end{aligned}}}

and therefore the sequence of Cantor numbers is 2-regular. Similarly the Stanley sequence

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (sequence A005836 in the OEIS)

of numbers whose ternary expansions contain no 2s is also 2-regular.^[9]

A somewhat interesting application of the notion of k-regularity to the broader study of algorithms is found in the analysis of the merge sort algorithm. Given a list of n values, the number of comparisons made by the merge sort algorithm are the sorting numbers, governed by the recurrence relation

T ( 1 ) = 0 , T ( n ) = T ( ⌊ n / 2 ⌋ ) + T ( ⌈ n / 2 ⌉ ) + n − 1 ,   n ≥ 2. {\displaystyle {\begin{aligned}T(1)&=0,\\T(n)&=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,\ n\geq 2.\end{aligned}}}

As a result, the sequence defined by the recurrence relation for merge sort, T(n), constitutes a 2-regular sequence.^[10]

If f ( x ) {\displaystyle f(x)} is an integer-valued polynomial, then f ( n ) n ≥ 0 {\displaystyle f(n)_{n\geq 0}} is k-regular for every k ≥ 2 {\displaystyle k\geq 2} .

The Glaisher–Gould sequence is 2-regular. The Stern–Brocot sequence is 2-regular.

Allouche and Shallit give a number of additional examples of k-regular sequences in their papers.^[6]

k-regular sequences exhibit a number of interesting properties.

• Every k-automatic sequence is k-regular.^[11]
• Every k-synchronized sequence is k-regular.
• A k-regular sequence takes on finitely many values if and only if it is k-automatic.^[12] This is an immediate consequence of the class of k-regular sequences being a generalization of the class of k-automatic sequences.
• The class of k-regular sequences is closed under termwise addition, termwise multiplication, and convolution. The class of k-regular sequences is also closed under scaling each term of the sequence by an integer λ.^{[12][13][14][15]} In particular, the set of k-regular power series forms a ring.^[16]
• If s ( n ) n ≥ 0 {\displaystyle s(n)_{n\geq 0}} is k-regular, then for all integers m ≥ 1 {\displaystyle m\geq 1} , ( s ( n ) mod m ) n ≥ 0 {\displaystyle (s(n){\bmod {m}})_{n\geq 0}} is k-automatic. However, the converse does not hold.^[17]
• For multiplicatively independent k, l ≥ 2, if a sequence is both k-regular and l-regular, then the sequence satisfies a linear recurrence.^[18] This is a generalization of a result due to Cobham regarding sequences that are both k-automatic and l-automatic.^[19]
• The nth term of a k-regular sequence of integers grows at most polynomially in n.^[20]
• If F {\displaystyle F} is a field and x ∈ F {\displaystyle x\in F} , then the sequence of powers ( x n ) n ≥ 0 {\displaystyle (x^{n})_{n\geq 0}} is k-regular if and only if x = 0 {\displaystyle x=0} or x {\displaystyle x} is a root of unity.^[21]

Given a candidate sequence s = s ( n ) n ≥ 0 {\displaystyle s=s(n)_{n\geq 0}} that is not known to be k-regular, k-regularity can typically be proved directly from the definition by calculating elements of the kernel of s {\displaystyle s} and proving that all elements of the form ( s ( k r n + e ) ) n ≥ 0 {\displaystyle (s(k^{r}n+e))_{n\geq 0}} with r {\displaystyle r} sufficiently large and 0 ≤ e < 2 r {\displaystyle 0\leq e<2^{r}} can be written as linear combinations of kernel elements with smaller exponents in the place of r {\displaystyle r} . This is usually computationally straightforward.

On the other hand, disproving k-regularity of the candidate sequence s {\displaystyle s} usually requires one to produce a Z {\displaystyle \mathbb {Z} } -linearly independent subset in the kernel of s {\displaystyle s} , which is typically trickier. Here is one example of such a proof.

Let e 0 ( n ) {\displaystyle e_{0}(n)} denote the number of 0 {\displaystyle 0} 's in the binary expansion of n {\displaystyle n} . Let e 1 ( n ) {\displaystyle e_{1}(n)} denote the number of 1 {\displaystyle 1} 's in the binary expansion of n {\displaystyle n} . The sequence f ( n ) := e 0 ( n ) − e 1 ( n ) {\displaystyle f(n):=e_{0}(n)-e_{1}(n)} can be shown to be 2-regular. The sequence g = g ( n ) := | f ( n ) | {\displaystyle g=g(n):=|f(n)|} is, however, not 2-regular, by the following argument. Suppose ( g ( n ) ) n ≥ 0 {\displaystyle (g(n))_{n\geq 0}} is 2-regular. We claim that the elements g ( 2 k n ) {\displaystyle g(2^{k}n)} for n ≥ 1 {\displaystyle n\geq 1} and k ≥ 0 {\displaystyle k\geq 0} of the 2-kernel of g {\displaystyle g} are linearly independent over Z {\displaystyle \mathbb {Z} } . The function n ↦ e 0 ( n ) − e 1 ( n ) {\displaystyle n\mapsto e_{0}(n)-e_{1}(n)} is surjective onto the integers, so let x m {\displaystyle x_{m}} be the least integer such that e 0 ( x m ) − e 1 ( x m ) = m {\displaystyle e_{0}(x_{m})-e_{1}(x_{m})=m} . By 2-regularity of ( g ( n ) ) n ≥ 0 {\displaystyle (g(n))_{n\geq 0}} , there exist b ≥ 0 {\displaystyle b\geq 0} and constants c i {\displaystyle c_{i}} such that for each n ≥ 0 {\displaystyle n\geq 0} ,

∑ 0 ≤ i ≤ b c i g ( 2 i n ) = 0. {\displaystyle \sum _{0\leq i\leq b}c_{i}g(2^{i}n)=0.}

Let a {\displaystyle a} be the least value for which c a ≠ 0 {\displaystyle c_{a}\neq 0} . Then for every n ≥ 0 {\displaystyle n\geq 0} ,

g ( 2 a n ) = ∑ a + 1 ≤ i ≤ b − ( c i / c a ) g ( 2 i n ) . {\displaystyle g(2^{a}n)=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})g(2^{i}n).}

Evaluating this expression at n = x m {\displaystyle n=x_{m}} , where m = 0 , − 1 , 1 , 2 , − 2 {\displaystyle m=0,-1,1,2,-2} and so on in succession, we obtain, on the left-hand side

g ( 2 a x m ) = | e 0 ( x m ) − e 1 ( x m ) + a | = | m + a | , {\displaystyle g(2^{a}x_{m})=|e_{0}(x_{m})-e_{1}(x_{m})+a|=|m+a|,}

and on the right-hand side,

∑ a + 1 ≤ i ≤ b − ( c i / c a ) | m + i | . {\displaystyle \sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}

It follows that for every integer m {\displaystyle m} ,

| m + a | = ∑ a + 1 ≤ i ≤ b − ( c i / c a ) | m + i | . {\displaystyle |m+a|=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}

But for m ≥ − a − 1 {\displaystyle m\geq -a-1} , the right-hand side of the equation is monotone because it is of the form A m + B {\displaystyle Am+B} for some constants A , B {\displaystyle A,B} , whereas the left-hand side is not, as can be checked by successively plugging in m = − a − 1 {\displaystyle m=-a-1} , m = − a {\displaystyle m=-a} , and m = − a + 1 {\displaystyle m=-a+1} . Therefore, ( g ( n ) ) n ≥ 0 {\displaystyle (g(n))_{n\geq 0}} is not 2-regular.^[22]

• Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k-regular sequences", Theoret. Comput. Sci., 98 (2): 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.