k-regular sequence

From HandWiki
Jump to: navigation, search

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.

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 Kk(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 ej > E and 0 ≤ rjkej − 1, every subsequence of s of the form s(kejn + rj) is expressible as an R′-linear combination [math]\sum_{i} c_{ij} s(k^{f_{ij}}n + b_{ij})[/math], where cij is an integer, fijE, and 0 ≤ bijkfij − 1.[2]

Alternatively, a sequence s(n) is k-regular if there exist an integer r and subsequences s1(n), ..., sr(n) such that, for all 1 ≤ ir and 0 ≤ ak − 1, every sequence si(kn + a) in the k-kernel Kk(s) is an R′-linear combination of the subsequences si(n).[2]

Formal series

Let x0, ..., xk − 1 be a set of k non-commuting variables and let τ be a map sending some natural number n to the string xa0 ... xae − 1, where the base-k representation of x is the string ae − 1...a0. 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] (OEISA007814) 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) (OEISA010060) 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) (OEISA005823) 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

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]

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 kl ≥ 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 nth term of a k-regular sequence of integers grows at most polynomially in n.[18]

Notes

  1. Allouche & Shallit (1992), Definition 2.1
  2. 2.0 2.1 Allouche & Shallit (1992), Theorem 2.2
  3. Allouche & Shallit (1992), Theorem 4.3
  4. Allouche & Shallit (1992), Theorem 4.4
  5. 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. 6.0 6.1 Allouche & Shallit (1992, 2003)
  7. 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. 
  8. Allouche & Shallit (1992), Example 8
  9. Allouche & Shallit (1992), Examples 3 and 26
  10. Allouche & Shallit (1992), Example 28
  11. Allouche & Shallit (1992), Theorem 2.3
  12. 12.0 12.1 Allouche & Shallit (2003) p. 441
  13. Allouche & Shallit (1992), Theorem 2.5
  14. Allouche & Shallit (1992), Theorem 3.1
  15. Allouche & Shallit (2003) p. 445
  16. Bell, J. (2006). "A generalization of Cobham's theorem for regular sequences". Séminaire Lotharingien de Combinatoire 54A. 
  17. 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. 
  18. 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.