k-regular sequence

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\; \backslash geq\; 0\}$ is the set of subsequences

:$K\_\{k\}(s)\; =\; \backslash \{s(k^e\; n\; +\; r)\_\{n\; \backslash geq\; 0\}\; :\; e\; \backslash geq\; 0\; \backslash text\{\; and\; \}\; 0\; \backslash leq\; r\; \backslash leq\; k^e\; -\; 1\backslash \}.$

The sequence $s(n)\_\{n\; \backslash geq\; 0\}$ is (R′, k)-regular (often shortened to just "k-regular") if the $R\text{'}$-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\text{'}\; =\; R\; =\; \backslash mathbb\{Q\}$, the sequence $s(n)\_\{n\; \backslash geq\; 0\}$ is $k$-regular if $K\_k(s)$ is contained in a finite-dimensional vector space over $\backslash 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 $\backslash 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.Allouche & Shallit (1992), Theorem 2.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).

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 $\backslash sum\_\{n\; \backslash geq\; 0\}\; s(n)\; \backslash tau\; (n)$ is $\backslash mathbb\{Z\}$-rational.Allouche & Shallit (1992), Theorem 4.3.

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.{{citation | last = Schützenberger | first = M.-P. | title = On the definition of a family of automata | journal = Information and Control | volume = 4 | issue = 2–3 | year = 1961 | pages = 245–270 | doi=10.1016/S0019-9958(61)80020-X | doi-access = free }}.

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.{{cite book | last1 = Berstel | first1 = Jean | last2 = Reutenauer | first2 = Christophe | title = Rational Series and Their Languages | volume = 12 | series = EATCS Monographs on Theoretical Computer Science | year = 1988 | isbn = 978-3-642-73237-9 | publisher = Springer-Verlag }}

Let $s(n)\; =\; \backslash nu\_2(n+1)$ be the $2$-adic valuation of $n+1$. The ruler sequence $s(n)\_\{n\; \backslash geq\; 0\}\; =\; 0,\; 1,\; 0,\; 2,\; 0,\; 1,\; 0,\; 3,\; \backslash dots$ ({{OEIS2C|id=A007814}}) is $2$-regular, and the $2$-kernel

:$\backslash \{s(2^e\; n\; +\; r)\_\{n\; \backslash geq\; 0\}\; :\; e\; \backslash geq\; 0\; \backslash text\{\; and\; \}\; 0\; \backslash leq\; r\; \backslash leq\; 2^e\; -\; 1\backslash \}$

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

:$$

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

which, along with the initial conditions $s(0)\; =\; 0$ and $s(1)\; =\; 1$, uniquely determine the sequence.Allouche & Shallit (1992), Example 8.

The Thue–Morse sequence t(n) ({{OEIS2C|id=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

:$\backslash \{t(2^e\; n\; +\; r)\_\{n\; \backslash geq\; 0\}\; :\; e\; \backslash geq\; 0\; \backslash text\{\; and\; \}\; 0\; \backslash leq\; r\; \backslash leq\; 2^e\; -\; 1\backslash \}$

consists of the subsequences $t(n)\_\{n\; \backslash geq\; 0\}$ and $t(2\; n\; +\; 1)\_\{n\; \backslash geq\; 0\}$.

The sequence of Cantor numbers c(n) ({{OEIS2C|id=A005823}}) consists of numbers whose ternary expansions contain no 1s. It is straightforward to show that

:$$

\begin{align}

c(2n) &= 3c(n), \\

c(2n+1) &= 3c(n) + 2,

\end{align}

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, ... {{OEIS|A005836}}

of numbers whose ternary expansions contain no 2s is also 2-regular.Allouche & Shallit (1992), Examples 3 and 26.

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

:$$

\begin{align}

T(1) &= 0, \\

T(n) &= T(\lfloor n / 2 \rfloor) + T(\lceil n / 2 \rceil) + n - 1, \ n \geq 2.

\end{align}

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.

If $f(x)$ is an integer-valued polynomial, then $f(n)\_\{n\; \backslash geq\; 0\}$ is k-regular for every $k\; \backslash 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.

k-regular sequences exhibit a number of interesting properties.

• Every k-automatic sequence is k-regular.Allouche & Shallit (1992), Theorem 2.3.
• 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. The class of k-regular sequences is also closed under scaling each term of the sequence by an integer λ.Allouche & Shallit (1992), Theorem 2.5.Allouche & Shallit (1992), Theorem 3.1.Allouche & Shallit (2003) p. 445. In particular, the set of k-regular power series forms a ring.Allouche and Shallit (2003) p. 446.
• If $s(n)\_\{n\; \backslash ge\; 0\}$ is k-regular, then for all integers $m\; \backslash ge\; 1$, $(s(n)\; \backslash bmod\{m\})\_\{n\; \backslash ge\; 0\}$ is k-automatic. However, the converse does not hold.Allouche and Shallit (2003) p. 441.
• For multiplicatively independent k, l ≥ 2, if a sequence is both k-regular and l-regular, then the sequence satisfies a linear recurrence.{{cite journal | first=J. | last=Bell | title=A generalization of Cobham's theorem for regular sequences| journal=Séminaire Lotharingien de Combinatoire | volume=54A | year=2006 }} This is a generalization of a result due to Cobham regarding sequences that are both k-automatic and l-automatic.{{cite journal | first=A. | last=Cobham | title=On the base-dependence of sets of numbers recognizable by finite automata | journal=Math. Systems Theory | volume=3 | issue=2 | year=1969 | pages=186–192 | doi=10.1007/BF01746527 | s2cid=19792434 }}
• The nth term of a k-regular sequence of integers grows at most polynomially in n.Allouche & Shallit (1992) Theorem 2.10.
• If $F$ is a field and $x\; \backslash in\; F$, then the sequence of powers $(x^n)\_\{n\; \backslash ge\; 0\}$ is k-regular if and only if $x\; =\; 0$ or $x$ is a root of unity.Allouche and Shallit (2003) p. 444.

Given a candidate sequence $s\; =\; s(n)\_\{n\; \backslash ge\; 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$ and proving that all elements of the form $(s(k^r\; n\; +\; e))\_\{n\; \backslash ge\; 0\}$ with $r$ sufficiently large and 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 $\backslash mathbb\{Z\}$-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))\_\{n\; \backslash ge\; 0\}$ is 2-regular. We claim that the elements $g(2^k\; n)$ for $n\; \backslash ge\; 1$ and $k\; \backslash ge\; 0$ of the 2-kernel of $g$ are linearly independent over $\backslash mathbb\{Z\}$. The function $n\; \backslash 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))\_\{n\; \backslash ge\; 0\}$, there exist $b\; \backslash ge\; 0$ and constants $c\_i$ such that for each $n\; \backslash ge\; 0$,

:$\backslash sum\_\{0\; \backslash le\; i\; \backslash le\; b\}\; c\_i\; g(2^i\; n)\; =\; 0.$

Let $a$ be the least value for which $c\_a\; \backslash ne\; 0$. Then for every $n\; \backslash ge\; 0$,

:$g(2^a\; n)\; =\; \backslash sum\_\{a+1\; \backslash le\; i\; \backslash le\; b\}\; -(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,

:$\backslash sum\_\{a+1\; \backslash le\; i\; \backslash le\; b\}\; -(c\_i/c\_a)|m+i|.$

It follows that for every integer $m$,

:$|m+a|\; =\; \backslash sum\_\{a+1\; \backslash le\; i\; \backslash le\; b\}\; -(c\_i/c\_a)\; |m+i|.$

But for $m\; \backslash 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))\_\{n\; \backslash ge\; 0\}$ is not 2-regular.Allouche and Shallit (1993) p. 168–169.

{{reflist}}

• {{citation | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | title = The ring of k-regular sequences | journal = Theoret. Comput. Sci. | volume = 98 | issue = 2 | year = 1992 | pages = 163–197 | doi=10.1016/0304-3975(92)90001-v| doi-access = free }}.
• {{citation | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | title = The ring of k-regular sequences, II | journal = Theoret. Comput. Sci. | volume = 307 | year = 2003 | pages = 3–29 | doi=10.1016/s0304-3975(03)00090-2| doi-access = free }}.
• {{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 | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}

Category:Combinatorics on words

Category:Automata (computation)

Category:Integer sequences

Category:Recurrence relations