Asymptotic analysis of regular sequences

DOI10.1007/S00453-019-00631-3MaRDI QIDQ2292859zbMATH OpenOpenAlexWikidataFDO

Publication date 6 February 2020

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1810.13178

esthetic numbers Mellin-Perron summation Pascal's rhombus regular sequence summatory function Tauberian theorem transducer

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Radix representation; digital problems (11A63) Formal languages and automata (68Q45) Combinatorics in computer science (68R05)

Abstract: In this article,

q

-regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices contribute terms which grow faster than the error term. The paper has a particular focus on the Fourier coefficients of the periodic fluctuations: They are expressed as residues of the corresponding Dirichlet generating function. This makes it possible to compute them in an efficient way. The asymptotic analysis deals with Mellin--Perron summations and uses two arguments to overcome convergence issues, namely H"older regularity of the fluctuations together with a pseudo-Tauberian argument. Apart from the very general result, three examples are discussed in more detail: sequences defined as the sum of outputs written by a transducer when reading a

q

-ary expansion of the input; the amount of esthetic numbers in the first~

N

natural numbers; and the number of odd entries in the rows of Pascal's rhombus. For these examples, very precise asymptotic formulae{} are presented. In the latter two examples, prior to this analysis only rough estimates were known.

Review text

Given a -- possibly -- irregular sequence \((a_k)_k\), its summatory function \(F(x) := \sum_{0 \leq k \leq n} a_n\) can behave in a ``better way. The authors of this nice paper study the case where the sequence \((a_k)_k\) is \(q\)-regular (see [\textit{J.-P. Allouche} and \textit{J. Shallit}, Theor. Comput. Sci. 98, No. 2, 163--197 (1992; Zbl 0774.68072); Theor. Comput. Sci. 307, No. 1, 3--29 (2003; Zbl 1058.68066)]). One of the most cited paper on a sequence of this kind is probably a 1975 paper of \textit{H. Delange} [Enseign. Math. (2) 21, 31--47 (1975; Zbl 0306.10005)] where \(a_k\) is the sum of digits of \(k\) in a fixed integer base \(q\ge 2\). Since then, many papers have been devoted to the subject, as can be seen in the large bibliography given in the paper under review. Here, the authors propose a general approach of the question, proving that \textit{the summatory function of a \(q\)-regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor.} Methods and results involve eigenvalues of sums of matrices, joint spectral radius, Fourier coefficients, Dirichlet series, Mellin-Perron summations, etc. While classical papers on the subject (such as Delange's) look at the (non-)differentiability (almost-)everywhere, of the oscillatory terms, the authors here are rather interested in the Hölder regularity of these terms. In the last part of the paper two explicit examples are addressed in detail, namely the number of esthetic numbers less than a given integer and the number of odd entries in the rows of Pascal's rhombus. It is of course not possible to give \textit{all} references related to the subject: one might add to the list given by the authors, e.g., the doctoral thesis of \textit{E. Cateland} (available at \url{https://tel.archives-ouvertes.fr/tel-00845511}) where particular regular sequences -- called ``digital -- are studied, and the paper of \textit{G. Tenenbaum} [Algorithms Comb. 13, 117--128 (1997; Zbl 0869.11019)], where a general method for studying derivability of the oscillatory terms is developed on particular examples, as well as references in Cateland's work and in Tenenbaum's work. One could also cite a paper by \textit{M. Coons} [J. Théor. Nombres Bordx. 22, No. 2, 339--352 (2010; Zbl 1223.11115)], where Theorem~3.1 can be compared with Theorem~D in the paper under review, and a paper by \textit{J. P. Bell} et al. [Bull. Aust. Math. Soc. 90, No. 2, 195--203 (2014; Zbl 1348.11023)], where a lower gap property for the growth of an unbounded \(k\)-regular sequence is given, which could be compared with the results in the present paper (since the summatory function of a regular sequence is also regular). To conclude, it is quite clear that this paper is definitely a must-read.

Recommendations

Cites work

Cited in

(14)

Describes a project that uses

Uses Software

This page was built for publication: Asymptotic analysis of regular sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2292859)