Heuberger Clemens, Krenn Daniel
Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Universitätsstraße 65-67, 9020 Klagenfurt am Wörthersee, Austria.
Algorithmica. 2020;82(3):429-508. doi: 10.1007/s00453-019-00631-3. Epub 2019 Oct 25.
In this article, -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ölder 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 -ary expansion of the input;the amount of esthetic numbers in the first natural numbers; andthe number of odd entries in the rows of Pascal's rhombus. For these examples, very precise asymptotic formulæ are presented. In the latter two examples, prior to this analysis only rough estimates were known.
在本文中，对阿卢什（Allouche）和沙利特（Shallit）意义下的(\beta)-正则序列进行了渐近分析。结果表明，正则序列的求和函数在渐近意义下可分解为有限个周期波动项乘以一个缩放因子的和。这些项中的每一项都对应于该序列线性表示的矩阵和的一个特征值；只有绝对值大于矩阵联合谱半径的特征值所对应的项增长速度快于误差项。本文特别关注周期波动的傅里叶系数：它们被表示为相应狄利克雷生成函数的留数。这使得能够以一种有效的方式计算它们。渐近分析涉及梅林 - 佩龙求和，并使用两个论据来克服收敛问题，即波动的赫尔德正则性以及一个伪陶伯型论据。除了这个非常一般的结果外，还更详细地讨论了三个例子：定义为传感器读取输入的(\beta)进制展开时输出之和的序列；前(n)个自然数中美观数的数量；以及帕斯卡菱形各行中奇数项的数量。对于这些例子，给出了非常精确的渐近公式。在后两个例子中，在此分析之前仅知道粗略的估计。
