HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
and
theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, a ''k''-regular sequence is a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
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 In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Perhaps most familiar as a pr ...
Noetherian ring In mathematics, a Noetherian ring is a ring that satisfies the ascending chain condition on left and right ideals. If the chain condition is satisfied only for left ideals or for right ideals, then the ring is said left-Noetherian or right-Noethe ...
and we take ''R'' to be a
ring (The) Ring(s) may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell Arts, entertainment, and media Film and TV * ''The Ring'' (franchise), a ...
containing ''R''′.


''k''-kernel

Let ''k'' ≥ 2. The ''k-kernel'' of the sequence s(n)_ is the set of subsequences :K_(s) = \. The sequence s(n)_ is (''R''′, ''k'')-regular (often shortened to just "''k''-regular") if the R'-module generated by ''K''''k''(''s'') is a finitely-generated ''R''′- module.Allouche and Shallit (1992), Definition 2.1. In the special case when R' = R = \mathbb, the sequence s(n)_ is k-regular if K_k(s) is contained in a finite-dimensional vector space over \mathbb.


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''''e''''j'' − 1, every subsequence of ''s'' of the form ''s''(''k''''e''''j''''n'' + ''r''''j'') is expressible as an ''R''′-
linear combination In mathematics, a linear combination or superposition is an Expression (mathematics), expression constructed from a Set (mathematics), set of terms by multiplying each term by a constant and adding the results (e.g. a linear combination of ''x'' a ...
\sum_ c_ s(k^n + b_), where ''c''''ij'' is an integer, ''f''''ij'' ≤ ''E'', and 0 ≤ ''b''''ij'' ≤ ''k''''f''''ij'' − 1.Allouche & Shallit (1992), Theorem 2.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'').


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''''a''0 ... ''x''''a''''e'' − 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 \sum_ s(n) \tau (n) is \mathbb-
rational Rationality is the quality of being guided by or based on reason. In this regard, a person acts rationally if they have a good reason for what they do, or a belief is rational if it is based on strong evidence. This quality can apply to an ...
.Allouche & Shallit (1992), Theorem 4.3.


Automata-theoretic

The formal series definition of a ''k''-regular sequence leads to an automaton characterization similar to Schützenberger's matrix machine.Allouche & Shallit (1992), Theorem 4.4.


History

The notion of ''k''-regular sequences was first investigated in a pair of papers by Allouche and Shallit.Allouche & Shallit (1992, 2003). Prior to this, Berstel and Reutenauer studied the theory of rational series, which is closely related to ''k''-regular sequences.


Examples


Ruler sequence

Let s(n) = \nu_2(n+1) be the 2-adic valuation of n+1. The ruler sequence s(n)_ = 0, 1, 0, 2, 0, 1, 0, 3, \dots () is 2-regular, and the 2-kernel :\ is contained in the two-dimensional vector space generated by s(n)_ and the constant sequence 1, 1, 1, \dots. These basis elements lead to the recurrence relations : \begin 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 which, along with the initial conditions s(0) = 0 and s(1) = 1, uniquely determine the sequence.Allouche & Shallit (1992), Example 8.


Thue–Morse sequence

The
Thue–Morse sequence In mathematics, the Thue–Morse or Prouhet–Thue–Morse sequence is the binary sequence (an infinite sequence of 0s and 1s) that can be obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus ...
''t''(''n'') () 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 t(n)_ and t(2 n + 1)_.


Cantor numbers

The sequence of Cantor numbers ''c''(''n'') () consists of numbers whose ternary expansions contain no 1s. It is straightforward to show that : \begin c(2n) &= 3c(n), \\ c(2n+1) &= 3c(n) + 2, \end 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, ... of numbers whose ternary expansions contain no 2s is also 2-regular.Allouche & Shallit (1992), Examples 3 and 26.


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 In computer science, merge sort (also commonly spelled as mergesort and as ) is an efficient, general-purpose, and comparison sort, comparison-based sorting algorithm. Most implementations of merge sort are Sorting algorithm#Stability, stable, wh ...
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 : \begin T(1) &= 0, \\ T(n) &= T(\lfloor n / 2 \rfloor) + T(\lceil n / 2 \rceil) + n - 1, \ n \geq 2. \end As a result, the sequence defined by the recurrence relation for merge sort, ''T''(''n''), constitutes a 2-regular sequence.Allouche & Shallit (1992), Example 28.


Other sequences

If f(x) is an
integer-valued polynomial In mathematics, an integer-valued polynomial (also known as a numerical polynomial) P(t) is a polynomial whose value P(n) is an integer for every integer ''n''. Every polynomial with integer coefficients is integer-valued, but the converse is not tr ...
, then f(n)_ is ''k''-regular for every 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.


Properties

''k''-regular sequences exhibit a number of interesting properties. *Every ''k''-automatic sequence is ''k''-regular. *Every ''k''-synchronized sequence is ''k''-regular. *A ''k''-regular sequence takes on finitely many values if and only if it is ''k''-automatic.Allouche & Shallit (2003) p. 441. 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 In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions f and g that produces a third function f*g, as the integral of the product of the two ...
. The class of ''k''-regular sequences is also closed under scaling each term of the sequence by an integer λ.Allouche & Shallit (2003) p. 445. In particular, the set of ''k''-regular
power series In mathematics, a power series (in one variable) is an infinite series of the form \sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots where ''a_n'' represents the coefficient of the ''n''th term and ''c'' is a co ...
forms a ring. *If s(n)_ is ''k''-regular, then for all integers m \ge 1, (s(n) \bmod)_ is ''k''-automatic. However, the converse does not hold. *For multiplicatively independent ''k'', ''l'' ≥ 2, if a sequence is both ''k''-regular and ''l''-regular, then the sequence satisfies a linear recurrence. This is a generalization of a result due to Cobham regarding sequences that are both ''k''-automatic and ''l''-automatic. *The ''n''th term of a ''k''-regular sequence of integers grows at most polynomially in ''n''. *If F is a field and x \in F, then the sequence of powers (x^n)_ is ''k''-regular if and only if x = 0 or x is a
root of unity In mathematics, a root of unity is any complex number that yields 1 when exponentiation, raised to some positive integer power . Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory ...
.


Proving and disproving ''k''-regularity

Given a candidate sequence s = s(n)_ 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 and proving that all elements of the form (s(k^r n + e))_ with r sufficiently large and 0 \le e < 2^r can be written as linear combinations of kernel elements with smaller exponents in the place of r. This is usually computationally straightforward. On the other hand, disproving ''k''-regularity of the candidate sequence s usually requires one to produce a \mathbb-linearly independent subset in the kernel of s, which is typically trickier. Here is one example of such a proof. Let e_0(n) denote the number of 0's in the binary expansion of n. Let e_1(n) denote the number of 1's in the binary expansion of n. The sequence f(n) := e_0(n)-e_1(n) can be shown to be 2-regular. The sequence g = g(n) := , f(n), is, however, not 2-regular, by the following argument. Suppose (g(n))_ is 2-regular. We claim that the elements g(2^k n) for n \ge 1 and k \ge 0 of the 2-kernel of g are linearly independent over \mathbb. The function n \mapsto e_0(n)-e_1(n) is surjective onto the integers, so let x_m be the least integer such that e_0(x_m)-e_1(x_m) = m. By 2-regularity of (g(n))_, there exist b \ge 0 and constants c_i such that for each n \ge 0, :\sum_ c_i g(2^i n) = 0. Let a be the least value for which c_a \ne 0. Then for every n \ge 0, :g(2^a n) = \sum_ -(c_i/c_a) g(2^i n). Evaluating this expression at n = x_m, where 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, , and on the right-hand side, :\sum_ -(c_i/c_a), m+i, . It follows that for every integer m, :, m+a, = \sum_ -(c_i/c_a) , m+i, . But for m \ge -a-1, the right-hand side of the equation is monotone because it is of the form Am+B for some constants A,B, whereas the left-hand side is not, as can be checked by successively plugging in m = -a-1, m = -a, and m = -a+1. Therefore, (g(n))_ is not 2-regular.Allouche and Shallit (1993) p. 168–169.


Notes


References

*. *. *{{cite book , last1 = Allouche , first1 = Jean-Paul , last2 = Shallit , first2 = Jeffrey , author2-link = Jeffrey Shallit , isbn = 978-0-521-82332-6 , publisher =
Cambridge University Press Cambridge University Press was the university press of the University of Cambridge. Granted a letters patent by King Henry VIII in 1534, it was the oldest university press in the world. Cambridge University Press merged with Cambridge Assessme ...
, title = Automatic Sequences: Theory, Applications, Generalizations , year = 2003 , zbl=1086.11015 Combinatorics on words Automata (computation) Integer sequences Recurrence relations