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

## Contents

## 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 [math]s(n)_{n \geq 0}[/math] is the set of subsequences

- [math]K_{k}(s) = \{s(k^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq k^e - 1\}.[/math]

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

In the special case when [math]R' = R = \mathbb{Q}[/math], the sequence [math]s(n)_{n \geq 0}[/math] is [math]k[/math]-regular if [math]K_k(s)[/math] is contained in a finite-dimensional vector space over [math]\mathbb{Q}[/math].

### 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*^{ej} − 1, every subsequence of *s* of the form *s*(*k*^{ej}*n* + *r*_{j}) is expressible as an *R*′-linear combination [math]\sum_{i} c_{ij} s(k^{f_{ij}}n + b_{ij})[/math], where *c*_{ij} is an integer, *f*_{ij} ≤ *E*, and 0 ≤ *b*_{ij} ≤ *k*^{fij} − 1.^{[2]}

Alternatively, a sequence *s*(*n*) is *k*-regular if there exist an integer *r* and subsequences *s*_{1}(*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]}

### Formal series

Let *x*_{0}, ..., *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*_{0}. Then a sequence *s*(*n*) is *k*-regular if and only if the formal series [math]\sum_{n \geq 0} s(n) \tau (n)[/math] is [math]\mathbb{Z}[/math]-rational.^{[3]}

### Automata-theoretic

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

## History

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]}

## Examples

### Ruler sequence

Let [math]s(n) = \nu_2(n+1)[/math] be the [math]2[/math]-adic valuation of [math]n+1[/math]. The ruler sequence [math]s(n)_{n \geq 0} = 0, 1, 0, 2, 0, 1, 0, 3, \dots[/math] (OEIS: A007814) is [math]2[/math]-regular, and the [math]2[/math]-kernel

- [math]\{s(2^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq 2^e - 1\}[/math]

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

- [math] \begin{align} 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), \end{align} [/math]

which, along with the initial conditions [math]s(0) = 0[/math] and [math]s(1) = 1[/math], uniquely determine the sequence.^{[8]}

### Thue–Morse sequence

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

- [math]\{t(2^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq 2^e - 1\}[/math]

consists of the subsequences [math]t(n)_{n \geq 0}[/math] and [math]t(2 n + 1)_{n \geq 0}[/math].

### Cantor numbers

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

- [math] \begin{align} c(2n) &= 3c(n), \\ c(2n+1) &= 3c(n) + 2, \end{align} [/math]

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

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

### Sorting numbers

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

- [math] \begin{align} T(1) &= 0, \\ T(n) &= T(\lfloor n / 2 \rfloor) + T(\lceil n / 2 \rceil) + n - 1, \ n \geq 2. \end{align} [/math]

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

### Other sequences

If [math]f(x)[/math] is an integer-valued polynomial, then [math]f(n)_{n \geq 0}[/math] is *k*-regular for every [math]k \geq 2[/math].

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

## Properties

*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]} - For multiplicatively independent
*k*,*l*≥ 2, if a sequence is both*k*-regular and*l*-regular, then the sequence satisfies a linear recurrence.^{[16]}This is a generalization of a result due to Cobham regarding sequences that are both*k*-automatic and*l*-automatic.^{[17]} - The
*n*th term of a*k*-regular sequence of integers grows at most polynomially in*n*.^{[18]}

## Notes

- ↑ Allouche & Shallit (1992), Definition 2.1
- ↑
^{2.0}^{2.1}Allouche & Shallit (1992), Theorem 2.2 - ↑ Allouche & Shallit (1992), Theorem 4.3
- ↑ Allouche & Shallit (1992), Theorem 4.4
- ↑ Schützenberger, M.-P. (1961), "On the definition of a family of automata",
*Information and Control***4**(2–3): 245–270, doi:10.1016/S0019-9958(61)80020-X. - ↑
^{6.0}^{6.1}Allouche & Shallit (1992, 2003) - ↑ Berstel, Jean; Reutenauer, Christophe (1988).
*Rational Series and Their Languages*. EATCS Monographs on Theoretical Computer Science.**12**. Springer-Verlag. ISBN 978-3-642-73237-9. - ↑ Allouche & Shallit (1992), Example 8
- ↑ Allouche & Shallit (1992), Examples 3 and 26
- ↑ Allouche & Shallit (1992), Example 28
- ↑ Allouche & Shallit (1992), Theorem 2.3
- ↑
^{12.0}^{12.1}Allouche & Shallit (2003) p. 441 - ↑ Allouche & Shallit (1992), Theorem 2.5
- ↑ Allouche & Shallit (1992), Theorem 3.1
- ↑ Allouche & Shallit (2003) p. 445
- ↑ Bell, J. (2006). "A generalization of Cobham's theorem for regular sequences".
*Séminaire Lotharingien de Combinatoire***54A**. - ↑ Cobham, A. (1969). "On the base-dependence of sets of numbers recognizable by finite automata".
*Math. Systems Theory***3**(2): 186–192. doi:10.1007/BF01746527. - ↑ Allouche & Shallit (1992) Theorem 2.10

## References

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

*https://en.wikipedia.org/wiki/K-regular sequence was the original source. Read more*.