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

edit

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

edit

Let k ≥ 2. The k-kernel of the sequence   is the set of subsequences

 

The sequence   is (R′, k)-regular (often shortened to just "k-regular") if the  -module generated by Kk(s) is a finitely-generated R′-module.[1]

In the special case when  , the sequence   is  -regular if   is contained in a finite-dimensional vector space over  .

Linear combinations

edit

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

edit

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   is  -rational.[3]

Automata-theoretic

edit

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

History

edit

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

edit

Ruler sequence

edit

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

 

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

 

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

Thue–Morse sequence

edit

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

 

consists of the subsequences   and  .

Cantor numbers

edit

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

 

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

edit

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

 

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

Other sequences

edit

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

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]

Properties

edit

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   is k-regular, then for all integers  ,   is k-automatic. However, the converse does not hold.[17]
  • For multiplicatively independent kl ≥ 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   is a field and  , then the sequence of powers   is k-regular if and only if   or   is a root of unity.[21]

Proving and disproving k-regularity

edit

Given a candidate sequence   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   and proving that all elements of the form   with   sufficiently large and   can be written as linear combinations of kernel elements with smaller exponents in the place of  . This is usually computationally straightforward.

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

Let   denote the number of  's in the binary expansion of  . Let   denote the number of  's in the binary expansion of  . The sequence   can be shown to be 2-regular. The sequence   is, however, not 2-regular, by the following argument. Suppose   is 2-regular. We claim that the elements   for   and   of the 2-kernel of   are linearly independent over  . The function   is surjective onto the integers, so let   be the least integer such that  . By 2-regularity of  , there exist   and constants   such that for each  ,

 

Let   be the least value for which  . Then for every  ,

 

Evaluating this expression at  , where   and so on in succession, we obtain, on the left-hand side

 

and on the right-hand side,

 

It follows that for every integer  ,

 

But for  , the right-hand side of the equation is monotone because it is of the form   for some constants  , whereas the left-hand side is not, as can be checked by successively plugging in  ,  , and  . Therefore,   is not 2-regular.[22]

Notes

edit
  1. ^ Allouche and Shallit (1992), Definition 2.1.
  2. ^ a b 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. ^ a b Allouche & Shallit (1992, 2003).
  7. ^ Berstel, Jean; Reutenauer, Christophe (1988). Rational Series and Their Languages. EATCS Monographs on Theoretical Computer Science. Vol. 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. ^ a b 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. ^ Allouche and Shallit (2003) p. 446.
  17. ^ Allouche and Shallit (2003) p. 441.
  18. ^ Bell, J. (2006). "A generalization of Cobham's theorem for regular sequences". Séminaire Lotharingien de Combinatoire. 54A.
  19. ^ 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. S2CID 19792434.
  20. ^ Allouche & Shallit (1992) Theorem 2.10.
  21. ^ Allouche and Shallit (2003) p. 444.
  22. ^ Allouche and Shallit (1993) p. 168–169.

References

edit