Divide-and-conquer. 2-rational sequences.

Divide-and-conquer
2-rational sequences

Philippe Dumas's home page
Divide-and-conquer | Maple
Publications | Address | Version française

Introduction
A fundamental idea
Complexity and recurrences
2-rational sequences
Asymptotic behavior
References

Among the Mahlerian sequences, we distinguish a particular class, namely the class of sequences that are rational with respect to the radix 2 or, for brevity, 2-rational sequences. One defines a 2-rational sequence (u_n) by a linear representation. Such a representation consists of a row matrix $\lambda$ , a column matrix $\gamma$ and two square matrices A₀ and A₁ whose sizes are respectively $1\times N$ , $N\times 1$ and $N\times N$ for a certain integer N. If an integer has as binary expansion

$\begin{displaymath} n=(n_{\ell}\ldots n_0)_2,\end{displaymath}$

the value of the sequence for this integer n is

$\begin{displaymath} u_n=\lambda A_{n_{\ell}}\dotsb A_{n_0}\gamma.\end{displaymath}$

The concept of a 2-rational sequence or more generally a B-rational sequence (the definition is easy to write up) is a direct extension of the concept of a rational sequence, i.e. of sequence whose generating series is a rational function (not admitting 0 as a pole). This concept appears in [4] where one speaks about 2-regular sequence, but this terminology appears to be too fuzzy, the word regular having multiple meanings. One finds in [4] many examples of 2-rational sequences. The simplest one is certainly the sequence $(\nu_n)$ which gives the number of 1s in the binary writing of n. This sequence admits the linear representation

$\begin{displaymath} \lambda=\left(\begin{array} {cc} 0&1 \end{array}\right),\qquad \gamma=\left(\begin{array} {c} 1\\ 0 \end{array}\right),\end{displaymath}$

$\begin{displaymath} A_0=\left(\begin{array} {cc} 1&0\\ 0&1 \end{array}\right),... ...d A_1=\left(\begin{array} {cc} 0&-1\\ 1&2 \end{array}\right).\end{displaymath}$

Characterization of the sequences which are rational with respect to the radix 2. We defined a 2-rational sequence by a linear representation; in real life examples are not given in this way and one must thus prove the 2-rationality. Often a divide-and-conquer recurrence is given and one can then apply the following result [12]. If the formal series f(z) satisfies the equation

$\begin{displaymath} z^af(z)+\sum_{k=1}^Nc_k(z)f(z^{2^k})=b(z),\end{displaymath}$

in which a is an integer and b(z) is a 2-rational series, then f(z) is 2-rational. For sequences, recurrences of the form

$\begin{displaymath} f_{n-a}+\sum_{k=1}^N\sum_{\ell}c_{k,\ell}f_{(n-\ell)/2^k}=b_n\end{displaymath}$

provide 2-rational sequences if (b_n) is 2-rational. One notes that in this recurrence the only term wich depends directly on n, f_n-a, is determined by the terms which depend on n/ 2, n/ 4, etc. It is convenient to give a result a little more general because one frequently encounters recurrences defined according to the residue modulo a power of 2. For example in [35] the study of an algorithm of Euclidean matching leads to consider a sequence (c_n) which satisfies

$\begin{displaymath} \left\{ \begin{array} {lcl} c_{4n} & = & a(c_{2n+1}+c_{2n-1}... ...+1})+1 \\ c_{4n+3} & = & a(c_{2n+2}+c_{2n+1})\end{array}\right.\end{displaymath}$

The generating series f₀₀(z), f₀₁(z), f₁₀(z), f₁₁(z) respectively associated with the sequences (c_4n), (c_4n+1), (c_4n+2), (c_4n+3) and the vector of formal series

$\begin{displaymath} F(z)=\left(\begin{array} {c} f_{00}(z)\\ f_{01}(z) \\ f_{10}(z) \\ f_{11}(z) \end{array}\right)\end{displaymath}$

satisfy the equation

$\begin{displaymath} z\,F(z)=a\,C_1(z)F(z^2)+E(z)\end{displaymath}$

with

$\begin{displaymath} C_1(z)=\left(\begin{array} {cccc} 0 & z(1+z) & 0 & z^2(1+z) ... ...in{array} {c} z/(1-z) \\ 0 \\ z/(1-z) \\ 0 \end{array}\right).\end{displaymath}$

One can show that a vector of formal series F(z) satisfying an equation of the form

$\begin{displaymath} z^aF(z)+\sum_{k=1}^NC_k(z)F(z^{2^k})=B(z),\end{displaymath}$

in which a is an integer, C_k(z) are square matrices whose entries are polynomials, and B(z) is a vector of 2-rational formal series, has 2-rational components. Again it should be noticed that the associated sequences satisfy a recurrence which provides the term of index n from the terms of index n/ 2, n/ 4, etc. One concludes thus that the sequence (c_n) is 2-rational.

In the same way the sequence defined by [21, p. 25]

$\begin{displaymath} f(n)=\max_k\left\{f(k)+f(n-k)+\min(k,n-k)\right\},\end{displaymath}$

which appears in an algorithm on permutations, satisfies

$\begin{displaymath} f(2m)=2f(m)+m,\qquad f(2m+1)=f(m)+f(m+1)+m\,;\end{displaymath}$

it is thus 2-rational. In fact it may be expressed by the formula

$\begin{displaymath} f(n)=\sum_{0\leq k<n}\nu_k,\end{displaymath}$

where $\nu_k$ is again the number of 1s in the binary expansion of an integer k.

Linear representation. Knowing that a sequence is 2-rational, it is natural to look for a linear representation of it. The 2-regularity of a sequence (u_n) expresses the fact that the sequences (u_n), (u_2n), (u_2n+1), (u_4n), (u_4n+1), (u_4n+2), (u_4n+3), etc, all live in a space of finite dimension. To emphasize this point one associates with the sequence a binary tree. Its root is labelled by the sequence (u_n) itself, and more generally the nodes are labelled by the subsequences (u_2^kn+r), with $0\leq r<2^k$ . The childrens of the node labelled with (u_2^kn+r) are labelled by (u_2^k+1n+r) and (u_2^k+1n+2^k+r). Moreover sequences which label the internal nodes of the tree are linearly independent and the sequences which label the leaves of the tree may be expressed as linear combinations of the previous ones.

Applying this algorithm one obtains for the sequence (T_n) which gives the cost of mergesort in the worst case the following tree and relations of recurrences.

$\begin{displaymath} \begin{array} {rcl} T_{4n+1} & = & 4T_n-5 T_{2n}+ T_{2n+1}+2... ...& -36T_n +48T_{2n} -16T_{2n+1} -16T_{4n} +11T_{4n+2}\end{array}\end{displaymath}$

These relations of recurrence may be translated into a linear representation of dimension N= 5.

Indeed 2-rational series are the translation via the positional binary notation of the rational series on the alphabet $\{0,1\}$ of formal language theory [7]; with the 2-rational series

$\begin{displaymath} f(z)=\sum_{n\geq0}f_nz^n\qquad\text{is associated the series}\qquad S=\sum_{n\geq0}f_n(n_{\ell}\ldots n_0)_2\end{displaymath}$

with support in the rational language of binary expansions $\varepsilon+1\{0,1\}^*$ . A consequence is that for a 2-rational series f(z) the so called condensate series

$\begin{displaymath} Kf(t)=\sum_{\ell\geq0}\sum_{2^{\ell}\leq n<2^{\ell+1}}f_nt^{\ell}\end{displaymath}$

is a rational series in the ordinary meaning.

2-automatic sequences. Another demonstration of the link with the theory of formal languages is the concept of a 2-automatic sequence, which predates the concept of a 2-rational sequence [8]. 2-automatic sequences are 2-rational sequences which take only a finite number of values. An example will make clear which kind of automaton is under consideration. The sequence of paper folding is defined as follows [10]. One folds a paper tape an infinite number of times and always in the same direction. Then one unfolds the tape and one observes the folds. They can be entering or outgoing and by suitably coding these folds by 0 or 1, one obtains a sequence which starts with 1101100. This sequence is 2-rational because it satisfies the recurrence

$\begin{displaymath} \left\{ \begin{array} {rcl} u_{4k} & = & 1, \\ u_{4k+2} & = & 0, \\ u_{2k+1} & = & u_k.\end{array}\right.\end{displaymath}$

This recurrence immediately gives the 2-automaton of paper folding, represented below.

$\begin{picture} (400,200) \put(100,150){\circle{20}} \put(200,150){\circle{20}} ... ... \put(170,70){$1$} \put(255,55){\vector(1,1){15}} \put(270,70){$0$}\end{picture}$

One computes the value of the sequence on a given integer by using the 2-automaton. One starts from the initial state i indicated by an entering arrow and one follows the arrows according to the bits of the integer, starting with the least significant bit; one then looks at the value associated with the final state; it is the sought value. If one search for the value of the sequence for the integer thirteen, whose binary expansion is 1101, one successively goes through states i, i, a, c, and c while following the arrows labelled 1, 0, 1 and eventually 1. The output function gives the value 0. One will find in [1] a presentation of the various problems involved in automatic sequences.

Previous page:	Complexity and recurrences
Next page:	Asymptotic behavior