Output sum of transducers: limiting distribution and periodic fluctuation. (English) Zbl 1338.60068
Summary: As a generalization of the sum of digits function and other digital sequences, sequences defined as the sum of the output of a transducer are asymptotically analyzed. The input of the transducer is a random integer in \([0, N)\). Analogues in higher dimensions are also considered. Sequences defined by a certain class of recursions can be written in this framework.{
}{
}Depending on properties of the transducer, the main term, the periodic fluctuation and an error term of the expected value and the variance of this sequence are established. The periodic fluctuation of the expected value is Hölder continuous and, in many cases, nowhere differentiable. A general formula for the Fourier coefficients of this periodic function is derived. Furthermore, it turns out that the sequence is asymptotically normally distributed for many transducers. As an example, the abelian complexity function of the paperfolding sequence is analyzed. This sequence has recently been studied by Madill and Rampersad.
MSC:
| 60F05 | Central limit and other weak theorems |
| 68R15 | Combinatorics on words |
| 05A16 | Asymptotic enumeration |
| 42A16 | Fourier coefficients, Fourier series of functions with special properties, special Fourier series |
| 68Q45 | Formal languages and automata |
| 11M41 | Other Dirichlet series and zeta functions |
Keywords:
transducers; automatic sequence; central limit theorem; periodic fluctuation; Fourier coefficients; non-differentiabilityReferences:
| [1] | Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences: Theory, applications, generalizations, Cambridge University Press, Cambridge, 2003. · Zbl 1086.11015 |
| [2] | Tom Apostol, Modular functions and Dirichlet series in number theory, Graduate Texts in Mathematics, vol. 41, Springer, New York, 1976. · Zbl 0332.10017 |
| [3] | Guy Barat and Peter J. Grabner, Distribution of binomial coefficients and digital functions, J. London Math. Soc. (2) 64 (2001), no. 3, 523-547. · Zbl 1049.11016 |
| [4] | Nader L. Bassily and Imre Kátai, Distribution of the values ofq-additive functions on polynomial sequences, Acta Math. Hungar. 68 (1995), no. 4, 353-361. · Zbl 0832.11035 |
| [5] | Valérie Berthé and Michel Rigo (eds.), Combinatorics, automata and number theory, Encyclopedia Math. Appl., vol. 135, Cambridge University Press, Cambridge, 2010. · Zbl 1197.68006 |
| [6] | Emmanuel Cateland, Suites digitales et suites k-régulières, Ph.D. thesis, Université Bordeaux, 1992. |
| [7] | Hubert Delange, Sur la fonction sommatoire de la fonction “somme des chiffres”, Enseignement Math. (2) 21 (1975), 31-47. · Zbl 0306.10005 |
| [8] | NIST Digital library of mathematical functions,http://dlmf.nist.gov/, Release 1.0.9 of 2014-08-29, 2010, Online companion to [29]. |
| [9] | Michael Drmota and Peter J. Grabner, Analysis of digital functions and applications, Combinatorics, automata and number theory (Valérie Berthé and Michel Rigo, eds.), Encyclopedia Math. Appl., vol. 135, Cambridge University Press, Cambridge, 2010, pp. 452-504. · Zbl 1216.68205 |
| [10] | Philippe Dumas, Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences, Linear Algebra Appl. 438 (2013), no. 5, 2107-2126. · Zbl 1368.11005 |
| [11] | Philippe Dumas, Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: Algebraic and analytic approaches collated, Theoret. Comput. Sci. 548 (2014), 25-53. the electronic journal of combinatorics 22(2) (2015), #P2.1951 · Zbl 1360.11083 |
| [12] | Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger, and Robert F. Tichy, Mellin transforms and asymptotics: digital sums, Theoret. Comput. Sci. 123 (1994), 291-314. · Zbl 0788.44004 |
| [13] | Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. · Zbl 1165.05001 |
| [14] | Chris D. Godsil and Gordon Royle, Algebraic graph theory, Graduate texts in mathematics, vol. 207, Springer Verlag (New York), 2001. · Zbl 0968.05002 |
| [15] | Peter J. Grabner, Clemens Heuberger, and Helmut Prodinger, Subblock occurrences in signed digit representations, Glasg. Math. J. 45 (2003), 427-440. · Zbl 1049.11084 |
| [16] | , Distribution results for low-weight binary representations for pairs of integers, Theoret. Comput. Sci. 319 (2004), 307-331. · Zbl 1050.94009 |
| [17] | Peter J. Grabner and Hsien-Kuei Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence, Constr. Approx. 21 (2005), 149-179. · Zbl 1088.11063 |
| [18] | Peter J. Grabner and Jörg M. Thuswaldner, On the sum of digits function for number systems with negative bases, Ramanujan J. 4 (2000), no. 2, 201-220. · Zbl 0987.11007 |
| [19] | Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics. A foundation for computer science, second ed., Addison-Wesley, 1994. · Zbl 0836.00001 |
| [20] | Clemens Heuberger, Daniel Krenn, and Sara Kropf, Automata and transducers in the computer algebra system Sage, 2014, arXiv:1404.7458 [cs.FL]. · Zbl 1401.68369 |
| [21] | Clemens Heuberger and Sara Kropf, Analysis of the binary asymmetric joint sparse form, Combin. Probab. Comput. 23 (2014), 1087-1113. · Zbl 1321.11013 |
| [22] | Clemens Heuberger, Sara Kropf, and Helmut Prodinger, Asymptotic analysis of the sum of the output of transducers, 25th International Conference on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA’14), DMTCS-HAL Proceedings Series, vol. BA, 2014, pp. 145-156. · Zbl 1332.68112 |
| [23] | Clemens Heuberger and James A. Muir, Minimal weight and colexicographically minimal integer representations, J. Math. Cryptol. 1 (2007), 297-328. · Zbl 1161.11002 |
| [24] | Hsien-Kuei Hwang, On convergence rates in the central limit theorems for combinatorial structures, European J. Combin. 19 (1998), 329-343. · Zbl 0906.60024 |
| [25] | Tosio Kato, Perturbation theory for linear operators, Springer, 1976. · Zbl 0342.47009 |
| [26] | Peter Kirschenhofer, Subblock occurrences in theq-ary representation of n, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 231-236. · Zbl 0517.05004 |
| [27] | Peter Kirschenhofer and Helmut Prodinger, Subblock occurrences in positional number systems and Gray code representation, J. Inform. Optim. Sci. 5 (1984), no. 1, 29-42. · Zbl 0538.10007 |
| [28] | Blake Madill and Narad Rampersad, The abelian complexity of the paperfolding word, Discrete Math. 313 (2013), no. 7, 831-838. the electronic journal of combinatorics 22(2) (2015), #P2.1952 · Zbl 1260.05002 |
| [29] | Frank W. J. Olver, Daniel W. Lozier, Ronald F. Boisvert, and Charles W. Clark (eds.), NIST Handbook of mathematical functions, Cambridge University Press, New York, 2010. · Zbl 1198.00002 |
| [30] | Manfred Peter, The asymptotic distribution of elements in automatic sequences, Theoret. Comput. Sci. 301 (2003), 285-312. · Zbl 1028.68081 |
| [31] | Marcel-Paul Schützenberger, Sur une variante des fonctions sequentielles, Theoret. Comput. Sci. 4 (1977), no. 1, 47-57. · Zbl 0366.68043 |
| [32] | William A. Stein et al., Sage Mathematics Software (Version 6.4.1), The Sage Development Team, 2014,http://www.sagemath.org. |
| [33] | Gérard Tenenbaum, Sur la non-dérivabilité de fonctions périodiques associées à certaines formules sommatoires, The mathematics of Paul Erdős, I (Ronald L. Graham and Jaroslav Nešetřil, eds.), Algorithms Combin., vol. 13, Springer, Berlin, 1997, pp. 117-128. · Zbl 0869.11019 |
| [34] | Jörg M. Thuswaldner, Summatory functions of digital sums occurring in cryptography, Period. Math. Hungar. 38 (1999), no. 1-2, 111-130. · Zbl 0936.11009 |
| [35] | Edmund T. Whittaker and George N. Watson, A course of modern analysis, Cambridge University Press, Cambridge, 1963, Reprint of the fourth (1927) edition. · Zbl 0108.26903 |
| [36] | Antoni Zygmund, Trigonometric series, vol. I & II combined, Cambridge University Press, Cambridge, 2002. · Zbl 0005.06303 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
