RADIAL ASYMPTOTICS OF GENERATING FUNCTIONS OF k-REGULAR SEQUENCES

Abstract

We give a new proof of a theorem of Bell and Coons [‘Transcendence tests for Mahler functions’, Proc. Amer. Math. Soc. 145(3) (2017), 1061–1070] on the leading order radial asymptotics of Mahler functions that are the generating functions of regular sequences. Our method allows us to provide a description of the oscillations whose existence was shown by Bell and Coons. This extends very recent results of Poulet and Rivoal [‘Radial behavior of Mahler functions’, Int. J. Number Theory, to appear].

1 Introduction

A Mahler function $F(z)$ is a power series that satisfies a functional equation of the form

$$ \begin{align*}a_0(z)F(z)+a_1(z)F(z^{k})+\cdots+a_d(z)F(z^{k^d})=0,\end{align*} $$

where $d\geqslant 1$ and $k\geqslant 2$ are positive integers, and $a_0(z),\ldots ,a_d(z)$ are polynomials with $a_0(z)a_d(z)\neq 0$ . The minimal such integer d, for a given Mahler function, is called the degree. The radial behaviour of Mahler functions has been studied by several authors, including Mahler [11], de Bruijn [7], Dumas [8], Dumas and Flajolet [9], as well as more recently, by the current first author in collaboration with Bell [3] and Brent et al. [4]. Mahler functions continue to be of interest in both mathematics and theoretical computer science since the generating functions of automatic sequences—sequences output by deterministic finite automata—and regular sequences are Mahler functions. Here, we focus on integer-valued nonnegative k-regular sequences. We take such a k-regular sequence to be a sequence determined by a finite set of matrices and one vector, as follows. Let $\mathbf {A}_0,\ldots ,\mathbf {A}_{k-1}\in \mathbb {Z}^{d\times d}$ and $\mathbf {v}\in \mathbb {Z}^{d\times 1}$ . The sequence f is k-regular if for each $n\geqslant 0$ ,

(1.1) $$ \begin{align}f(n)=\mathbf{e}_1^T \mathbf{A}_{i_0}\mathbf{A}_{i_1}\cdots\mathbf{A}_{i_t}\mathbf{v},\end{align} $$

where the base-k expansion of n is $(n)_k=i_t\cdots i_1 i_0$ and $\mathbf {e}_1$ is the standard elementary column vector having a $1$ in the first entry and zeros elsewhere.

Bell and Coons [3], with the goal of providing a quick transcendence test for Mahler functions, showed that, under mild conditions, as $z\to 1^-$ , Mahler functions satisfy an asymptotic of the form

$$ \begin{align*}F(z)=(1-z)^{-{\log\rho}/{\log k}}C(z)\,(1+o(1))\end{align*} $$

for some real $\rho>0$ . To obtain $\rho $ , using the polynomials $a_i(z)$ from above, they formed the characteristic polynomial $p_F(X)=a_0X^d+\cdots +a_{d-1}X+a_d,$ where $a_i:=a_i(1)$ , and took $\rho $ to be the (assumed) unique root of largest modulus of $p_F(X)$ . The function $C(z)$ is a positive bounded real-differentiable function satisfying $C(z)=C(z^k)$ . While Bell and Coons proved existence of the function $C(z)$ , no further details about it were given. Very recently, Poulet and Rivoal [12] provided an explicit expression for $C(z)$ as an exponential of a Fourier series for all degree-one Mahler functions and then extending the method of Brent et al. [4], they provided an explicit expression for $C(z)$ for a large class of degree-two Mahler functions.

In this paper, we give a method for determining $C(z)$ , for any generating function of a regular sequence, of any degree. In particular, we prove the following theorem.

Theorem 1.1. Let $k\geqslant 2$ be a positive integer, let f be an integer-valued nonnegative k-regular sequence satisfying (1.1) and set $\mathbf {A}=\mathbf {A}_0+\cdots +\mathbf {A}_{k-1}.$ Set $F(z)=\sum _{n\geqslant 1}f(n)z^n$ . If $\mathbf {A}$ is primitive, then, as $s\to 0^+$ , there is an explicitly determinable function $\psi (s)$ satisfying $\psi (s)=\psi (ks)$ , such that

$$ \begin{align*}F(e^{-s})=s^{-{\log\rho}/{\log k}}\,\psi(s)\,(1+o(1)),\end{align*} $$

where $\rho :=\rho (\mathbf {A})$ is the spectral radius of $\mathbf {A}$ .

Our proof uses properties of the Dirichlet series of a regular sequence established more than twenty years ago by Allouche et al. [1]. Their result does not seem to be widely known and, we believe, deserves more attention. For a very current exposition on combinatorics on words and their relation to automatic Dirichlet series, see Allouche et al. [2]. The explicit equation for $\psi (s)$ is recorded in (2.8).

Remark 1.2. The assumptions in the above theorem were chosen to simplify our arguments. The method used in the proof of Theorem 1.1 can be used to determine the leading asymptotics of $F(e^{-s})$ for any k-regular sequence; one only needs to determine enough terms in the asymptotic expansion of the related Dirichlet series $\zeta _f(z)$ . The number of terms depends on the spectral radius $\rho $ of $\mathbf {A}$ . The conditions of Theorem 1.1 ensure that $\rho>1$ . This further ensures that the asymptotics of $\zeta _f(z)$ are determined by a simple pole in the positive half-plane, which simplifies the argument.

Our arguments are essentially modified ideas of de Bruijn [7], which we use to obtain the leading behaviour of $F(e^{-s})$ . Of course, with more specific information, one can extend this method to gain an exact formula for $F(e^{-s})$ , but the necessary information seems specific to the sequence f and will necessarily be more much complex.

2 Radial behaviour of k-regular functions

In this section, we use a result of Allouche et al. [1] on the continuability of automatic and regular Dirichlet series to determine the residues of such Dirichlet series at the poles with largest real part. To this end, set $\mathbf {u}_0=\mathbf {v}$ and for $n\geqslant 1$ , set $\mathbf {u}_n:=\mathbf {A}_{i_0}\mathbf {A}_{i_1}\cdots \mathbf {A}_{i_t}\mathbf {v},$ where, as above, $(n)_k=i_t\cdots i_1 i_0$ is the base-k expansion of n. Then $\mathbf {u}_{kn+i}=\mathbf {A}_i\mathbf {u}_n$ for each n and $i=0,1,\ldots ,k-1$ . Further, let

$$ \begin{align*}\mathbf{G}(z):=\sum_{n\geqslant 1}\frac{\mathbf{u}_n}{n^z}\end{align*} $$

be a vector of Dirichlet series, whose first component is $\zeta _f(z):=\sum _{n\geqslant 1}f(n)n^{-z}$ . Since f is k-regular, the components of $\mathbf {u}_n$ grow at most polynomially in n, and so $\mathbf {G}(z)$ converges for ${\text {Re}\,}(z)$ large enough. We make use of the following result.

Theorem 2.1 (Allouche et al., [1]).

Let $k\geqslant 2$ be an integer and f, $\mathbf {u}_n$ and $\mathbf {G}(z)$ be as defined above. Then $\mathbf {G}(z)$ satisfies the functional equation

(2.1) $$ \begin{align}(\mathbf{I}-k^{-z}\mathbf{A})\,\mathbf{G}(z)=\bigg(\sum_{j=1}^{k-1}j^{-z}\mathbf{A}_j\bigg)\,\mathbf{u}_0+\sum_{j=1}^{k-1}\mathbf{A}_j\sum_{m\geqslant 1}(-1)^m\,{z+m-1\choose m}\,j^m\frac{\mathbf{ G}(z+m)}{k^{z+m}}.\end{align} $$

Moreover, $\mathbf {G}(z)$ has a meromorphic continuation to the whole complex plane, with poles (if any) located at

$$ \begin{align*}z_{n,\ell}(\lambda)=\frac{\log\lambda}{\log k}-\ell+i\frac{2\pi n}{\log k}\end{align*} $$

for $\ell \in \mathbb {N}_0$ and $n\in \mathbb {Z}$ , and for each eigenvalue $\lambda $ of $\mathbf {A}$ .

In what follows, we need only consider the contributions at the poles with largest real part, that is, with $\ell =0$ and $\lambda =\rho =\rho (\mathbf {A})$ . For convenience, set $z_{n}:=z_{n,0}(\rho ).$

Let ${\text {Re}\,}(z)>\log \rho /\!\log k$ , the abscissa of convergence of $\mathbf {G}(z)$ . Here, $\log \rho /\!\log k>0$ , since $\mathbf {A}$ is a primitive integer matrix. We start with (2.1), multiplying each side by $-k^{z-1}$ , and then the classical adjoint $\mathrm {adj}(k^{-1}\mathbf {A}-k^{z-1}\mathbf {I})$ to get

(2.2) $$ \begin{align} &\det(k^{-1}\mathbf{A}-k^{z-1}\mathbf{I})\, \mathbf{G}(z)=-\mathrm{adj}(k^{-1}\mathbf{A}-k^{z-1}\mathbf{I})\, \frac{1}{k}\, \bigg(\sum_{j=1}^{k-1}\bigg(\frac{j}{k}\bigg)^{-z}\mathbf{A}_j\bigg)\,\mathbf{u}_0\nonumber\\ &\quad+\mathrm{adj}(k^{-1}\mathbf{A}-k^{z-1}\mathbf{I})\sum_{j=1}^{k-1}\mathbf{A}_j\sum_{m\geqslant 1}(-1)^{m+1}\,{z+m-1\choose m}\,j^m\frac{\mathbf{G}(z+m)}{k^{m+1}}.\end{align} $$

Allouche et al. [1] made use of (2.2) to find the possible poles of $\mathbf {G}(z)$ in their proof of the above theorem, the point being that the possible poles (and their multiplicities) come from the zeros of the determinant $\det (k^{-1}\mathbf {A}-k^{z-1}\mathbf {I})$ . Since $m\geqslant 1$ , the vector $\mathbf {G}(z+m)$ converges for ${\text {Re}\,}(z)>\log \rho /\!\log k-1$ . Also, for any fixed z, $\mathbf {G}(z+m)$ tends to $\mathbf {u}_1$ as m tends to infinity. Thus, the right-hand side of (2.2) converges for ${{\text {Re}\,}(z)>\log \rho /\!\log k-1}$ . Hence, the (possible) pole of $\mathbf {G}(z)$ at $z=z_{n}$ is cancelled out by the zero of $\det (k^{-1}\mathbf {A}-k^{z-1}\mathbf {I})$ there. Since, by assumption, $\rho =\rho (\mathbf {A})$ is a simple eigenvalue of $\mathbf {A}$ , the zero of $\det (k^{-1}\mathbf {A}-k^{z-1}\mathbf {I})$ at $z=z_{n}$ , and so also the (possible) pole of $\mathbf {G}(z)$ at $z=z_{n}$ , are simple. We can now read off the residue as

(2.3) $$ \begin{align} &{\underset{{{z}={z_{n}}}}{\text{Res}}\, {\zeta_f(z)}}=-c_{f,\,\rho}\,\mathbf{e}_1^T\mathrm{adj}(k^{-1}\mathbf{A}-k^{z_n-1}\mathbf{I})\, \frac{1}{k}\, \bigg(\sum_{j=1}^{k-1}\bigg(\frac{j}{k}\bigg)^{-z_n}\mathbf{A}_j\bigg)\,\mathbf{u}_0\nonumber\\ &\quad+c_{f,\,\rho}\,\mathbf{e}_1^T\mathrm{adj}(k^{-1}\mathbf{A}-k^{z_n-1}\mathbf{I})\sum_{j=1}^{k-1}\mathbf{A}_j\sum_{m\geqslant 1}(-1)^{m+1}\,{z_n+m-1\choose m}\,j^m\frac{\mathbf{G}(z_n+m)}{k^{m+1}},\end{align} $$

where $c_{f,\,\rho }:=\lim _{z\to z_{n}}{(z-z_{n})}/{\det (k^{-1}\mathbf {A}-k^{z-1}\mathbf {I})},$ which exists by the above argument. This residue may very well be equal to zero for some values of n. However, in our situation, the primitivity of $\mathbf {A}$ and nonnegativity of $f(n)$ imply that there are positive constants $c_1$ and $c_2$ such that

(2.4) $$ \begin{align}c_1\, x^{{\log\rho}/{\log k}}\leqslant \sum_{n\leqslant x} f(n)\leqslant c_2 \,x^{{\log\rho}/{\log k}},\end{align} $$

and so the Dirichlet series $\zeta _f(z)$ , and so also the vector $\mathbf {G}(z)$ , have simple poles at $z=z_0$ , as inherited from the related determinant described above. (See [3], or more specifically, [6, Theorem 2], for details concerning the inequality (2.4).)

We are now ready to prove our main result.

Proof of Theorem 1.1.

We start with Mellin’s formula for the exponential function: for any $a>0$ and $w>0$ ,

$$ \begin{align*}e^{-w} = \frac{1}{2\pi i} \int_{a-i\infty}^{a+i\infty} w^{-z}\,\Gamma(z)\,dz.\end{align*} $$

This gives, for $a>\log \rho /\!\log k$ and $s>0$ ,

(2.5) $$ \begin{align}F(e^{-s})=\sum_{n\geqslant 1}f(n)e^{-sn}=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}s^{-z}\,\Gamma(z)\,\zeta_f(z)\,dz.\end{align} $$

The restriction $a>\log \rho /\!\log k$ ensures that

$$ \begin{align*}\sum_{n\geqslant 1}\int_{a-i\infty}^{a+i\infty}|f(n)\,n^{-z}s^{-z}\,\Gamma(z)|\,dz<\infty,\end{align*} $$

so the sum and integral can be exchanged.

For the leading order asymptotics of $F(e^{-s})$ , we move a past $\log \rho /\!\log k$ (but, to avoid complexity in the argument, not too far) and collect the contributions from the residues lying on the line ${\text {Re}\,}(z)=\log \rho /\!\log k$ . To see this, we let $\alpha $ be any fixed real number satisfying $\max \{{\log \rho _2}/{\log k},{\log \rho }/{\log k}-1,0\}<\alpha <{\log \rho }/{\log k}$ , where $\rho _2$ denotes the modulus of the second largest eigenvalue of $\mathbf {A}$ , if it exists. Note that in the case $d=1$ , there will be only one eigenvalue. For each $q\in \mathbb {N}$ , we let $T_q:={\pi (2q+1)}/{\log k}$ . Note that $T_q$ is the imaginary part of the midpoint of consecutive (possible) poles—in the vertical sense. By the residue theorem,

(2.6) $$ \begin{align}&\frac{1}{2\pi i}\bigg(\int_{\alpha-iT_q}^{a-iT_q}+\int_{a-iT_q}^{a+iT_q}+\int_{a+iT_q}^{\alpha+iT_q}+\int_{\alpha+iT_q}^{\alpha-iT_q}\bigg)s^{-z}\,\Gamma(z)\,\zeta_f(z)\,dz\nonumber\\ &\quad=s^{-{\log\rho}/{\log k}}\sum_{n\in\mathbb{Z}\cap[-q,q]}s^{-{2\pi i n}/{\log k}}\,\Gamma(z_n)\,{\underset{{{z}={z_{n}}}}{\text{Res}}\, {\zeta_f(z)}}.\end{align} $$

To show that

(2.7) $$ \begin{align}\lim_{q\to\infty}\frac{1}{2\pi i}\bigg(\int_{\alpha-iT_q}^{a-iT_q}+\int_{a+iT_q}^{\alpha+iT_q}\bigg)s^{-z}\,\Gamma(z)\,\zeta_f(z)\,dz=0,\end{align} $$

we use (2.2) as the analytic continuation of $\mathbf {G}(z)$ on the horizontal parts of our rectangular contour. It is clear that the first term in (2.2) is absolutely uniformly bounded on the horizontal contours, so the work here comes from the second term. For the second term, since, as $m\to \infty $ , we have $\mathbf {G}(z+m)=\mathbf {u}_1(1+O(2^{-m})),$ to show that the above limit is zero, we use a bound as $m\to \infty $ on $\Gamma (z){z+m-1\choose m}$ along those horizontal contours. To this end, we note that for $x\in [\alpha ,a]\subseteq (0,a]$ ,

$$ \begin{align*} \bigg|\Gamma(z){z+m-1\choose m}\bigg|&=\bigg|\frac{\Gamma(x+m\pm iT_q)}{\Gamma(m+1)}\bigg|=\bigg|\frac{\Gamma(x+m)}{\Gamma(m+1)}\bigg|\prod_{j\geqslant 0}\bigg(1+\frac{T_q^2}{(x+m+j)^2}\bigg)^{-1/2}\\ &=m^{x-1}\prod_{j\geqslant 0}\bigg(1+\frac{T_q^2}{(x+m+j)^2}\bigg)^{-1/2}\bigg(1+O\bigg(\frac{1}{m}\bigg)\bigg),\end{align*} $$

where the second equality follows from [10, 8.326 on page 904] and the third equality follows from Stirling’s formula. Thus, on the horizontal intervals of concern,

$$ \begin{align*}&\bigg|\Gamma(z)\sum_{m\geqslant 1}(-1)^{m+1}\,{z+m-1\choose m}\,j^m\frac{\mathbf{G}(z+m)}{k^{m+1}}\bigg|\\ &\quad=\sum_{m\geqslant 1}m^{x-1}\frac{\mathbf{u}_1}{k\cdot \big(\frac{k}{k-1}\big)^m}\bigg(\prod_{j\geqslant 0}\bigg(1+\frac{T_q^2}{(x+m+j)^2}\bigg)^{-1/2}\bigg)\bigg(1+O\bigg(\frac{1}{m}\bigg)\bigg).\end{align*} $$

For each q, the convergence of the sum is clear. The products inside the summation, $\Pi _q:=\prod _{j\geqslant 0}(1+{T_q^2}/{(x+m+j)^2})$ , satisfy $\Pi _q\to \infty $ as $q\to \infty $ , from which (2.7) follows.

In light of (2.7), by (2.5),

$$ \begin{align*}F(e^{-s})=s^{-{\log\rho}/{\log k}}\sum_{n\in\mathbb{Z}}s^{-{2\pi i n}/{\log k}}\,\Gamma(z_n)\,{\underset{{{z}={z_{n}}}}{\text{Res}}\, {\zeta_f(z)}}+O(s^{-\alpha}),\end{align*} $$

since $({1}/{2\pi i}) \int _{\alpha -i\infty }^{\alpha +i\infty }s^{-z}\,\Gamma (z)\,\zeta _f(z)\,dz=O(s^{-\alpha }).$

Note that the restrictions on the real number $\alpha>0$ were chosen for two reasons. First, so that the vertical line ${\text {Re}\,}(z)=\alpha $ avoids any singularities of the integrand $s^{-z}\,\Gamma (z)\,\zeta _f(z)$ , and second, so that as one forms the shifted infinite vertical contour via the limit of the rectangular contour (as above), we ensure that the horizontal contours give a limiting contribution of zero. We now set

(2.8) $$ \begin{align}\psi(s)=\sum_{n\in\mathbb{Z}}s^{-{2\pi i n}/{\log k}}\,\Gamma(z_n)\,{\underset{{{z}={z_{n}}}}{\text{Res}}\, {\zeta_f(z)}}\end{align} $$

and note that $\psi (s)=\psi (ks)$ , since $k^{-{2\pi i n}/{\log k}}=1$ . This proves the theorem.

Remark 2.2. Considering the possible complexities that may be necessary in generalising the above argument, we note that in Theorem 1.1 and our proof, the condition of primitivity of $\mathbf {A}$ is used to obtain $\rho>1$ , which ensures that we obtain an error term of order $\alpha>0$ . This assumption greatly simplifies our argument. If $\rho \leqslant 1$ , then the poles of $\Gamma (z)$ will come into play, and, adding to the complexity, the resulting integrand $s^{-z}\Gamma (z)\zeta _f(z)$ may have poles of higher order that need to be dealt with.

3 Further remarks

If one desired to compute some numerics, the calculation of residues is probably the most difficult part, but the convergence within the sum is extremely fast. Recall, that as m tends to infinity, the vectors $\mathbf { G}(z_n+m)$ tend quickly to $\mathbf {u}_1$ . So, using the above formulae, one can make computations with accuracy.

To see what (2.3) looks like for a particular example, we consider Stern’s diatomic sequence $a(n)$ defined by $a(0)=0$ , $a(1)=1$ , and for $n\geqslant 1$ , by $a(2n)=a(n)$ and ${a(2n+1)=a(n)+a(n+1)}$ . To apply our results, we note that $a(n)$ is $2$ -regular and satisfies (1.1) with

$$ \begin{align*}\mathbf{A}_0=\begin{bmatrix} 1&0\\1&1\end{bmatrix},\quad \mathbf{A}_1=\begin{bmatrix} 1&1\\0&1\end{bmatrix}\quad\mbox{and}\quad \mathbf{v}=\begin{bmatrix} 0\\1\end{bmatrix}.\end{align*} $$

We denote the entries of $\mathbf {G}(z)$ by $\zeta _a(z):=\sum _{n\geqslant 1}{a(n)}/{n^z}$ and $\zeta _{\sigma a}(z):=\sum _{n\geqslant 1}{a(n+1)}/{n^z}.$ We have used $\sigma $ to denote the shift operator, so $\sigma a(n)=a(n+1)$ . Also, $\rho =\rho (\mathbf {A})=3$ and $c_{a,3}=2/(3\log 2)$ . Thus,

$$ \begin{align*} &{\underset{{{z}={z_{n}}}}{\text{Res}}\, {\zeta_a(z)}}\\ &\quad=-\frac{2}{3\log 2}\mathbf{e}_1^T\begin{bmatrix}-1/2 &-1/2\\-1/2 &-1/2\end{bmatrix} \frac{2^{z_n}}{2} \begin{bmatrix}1 &1\\0 &1\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix}\\ &\qquad+\frac{2}{3\log 2}\mathbf{e}_1^T\begin{bmatrix}-1/2 &-1/2\\-1/2 &-1/2\end{bmatrix}\begin{bmatrix}1 &1\\0 &1\end{bmatrix}\sum_{m\geqslant 1}(-1)^{m+1}{z_n+m-1\choose m}\frac{1}{2^{m+1}}\begin{bmatrix}\zeta_a(z_n+m)\\\zeta_{\sigma a}(z_n+m)\end{bmatrix}\\ &\quad=\frac{1}{\log 2} -\frac{1}{3\log 2}\sum_{m\geqslant 1}{z_n+m-1\choose m}\bigg(\frac{-1}{2}\bigg)^{m+1}(\zeta_a(z_n+m)+2\zeta_{\sigma a}(z_n+m)).\end{align*} $$

As mentioned in [5, Remark 2.1], the infinite functional equation (2.1) is classical for $\zeta (z)$ , the Riemann zeta function, though it is much less deep than the usual functional equation for $\zeta (z)$ . However, when one applies it, one finds new proofs of some known, though curious, identities. For example, when one defines the sequence of all ones as the $2$ -regular sequence with $\mathbf {A}_0=\mathbf { A}_1=\mathbf {v}=1$ , we have, for ${\text {Re}\,}(z)>1$ , that

$$ \begin{align*} (1-2^{-z+1})\zeta(z)=1+\sum_{m\geqslant 1}(-1)^m\,{z+m-1\choose m}\frac{\zeta(z+m)}{2^{z+m}}.\end{align*} $$

As $z\to 1^+$ , we have $(1-2^{-z+1})=(z-1)\log 2+O\big ((z-1)^2\big )$ . Since the residue of $\zeta (z)$ at $z=1$ equals one, we obtain

$$ \begin{align*}1-\log 2=\sum_{m\geqslant 1}\zeta(m+1)\,\bigg(\frac{-1}{2}\bigg)^{m+1}.\end{align*} $$