> <\body> <\hide-preamble> >> >>> \; ||<\author-affiliation> CNRS, École polytechnique, Institut Polytechnique de Paris Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) 1, rue Honoré d'Estienne d'Orves Bâtiment Alan Turing, CS35003 91120 Palaiseau, France |>>|<\doc-note> > Many sequences that arise in combinatorics and the analysis of algorithms turn out to be holonomic (note that some authors prefer the terminology D-finite). In this paper, we study various basic algorithmic problems for such sequences |)>\>>: how to compute their asymptotics for large ? How to evaluate > efficiently for large and/or large precisions ? How to decide whether \0> for all ? We restrict our study to the case when the generating function \>f*z> satisfies a Fuchsian differential equation (often it suffices that the dominant singularities of be Fuchsian). Even in this special case, some of the above questions are related to long-standing problems in number theory. We will present algorithms that work in many cases and we carefully analyze what kind of oracles or conjectures are needed to tackle the more difficultcases. > Let > be a subfield of >. A sequence |)>\>\\>> is said to be over > if it satisfies a difference equation <\equation> \*f+\+\*f=0, where =\*\+\+\\\|]>> is a linear difference operator in :n\n+1>> with\0>>. (Note that some authors prefer the terminology D-finite or P-finite instead of holonomic.) Many interesting sequences from combinatorics, the analysis of algorithms, and number theory are holonomic. We say that |)>> is >-holonomic> if \\> for all \>>. We say that the equation() is if \0> for all \>. In that case, the sequence is entirely determined by its first coefficients and |)>> is >-holonomic if and only if ,\,f|)>\\>>. Throughout this paper, we assume that =\> is the field of algebraic numbers. Given a non-degenerate >-holonomic sequence |)>\\>>, one may raise several natural questions: <\description-aligned> >How to compute the asymptotic expansion of > when \>? >What kind of constants coefficients can occur in the asymptotic expansion of >? >How to compute terms > of the sequence efficiently as a function of ? >How to decide whether \0> or \0> for large, all, or infinitely many \>? (Forthis question, we assume that \\\\> for all .) These questions are related and can be further refined. For instance, it is natural to compute terms > as elements of >. However, if becomes large, then the bit-size of > is generally at least proportional to . When that happens, it may be preferable to switch to a floating point representation. If we have an asymptotic expansion of > with suitable error bounds, then we may exploit that to quickly compute floating point approximations of the > forlarge. Similarly, if the dominant term of the expansion of > is positive and provably dominates the other terms, then we may deduce that \0> for large . Assuming that the generating function <\equation*> f\\>f*z is analytic at the origin, it is well known that the asymptotic behavior of the sequence|)>> is closely related to the behavior of near its dominant singularities ( the singularities of smallest absolute value). As will be recalled in section, the generating function is again holonomic in the sense that it satisfies a non-trivial linear differential equation with polynomial coefficients. Holonomic functions can be evaluated extremely efficiently and their singularities are well understood. In this paper we will restrict our attention to the special case when at least the dominant singularities of are Fuchsian (see section for a definition). In that case, the behavior of near its dominant singularities becomes much simpler and the evaluation of near these singularities even more efficient. In their full generality, the questions, , and turn out to be very difficult, even in the Fuchsian case. Indeed, if is actually a rational function, then the last question is related to Skolem's problem, which asks whether =0>> for some \>. Now if is a rational function, then so is \-\>f*z> and =0\g\0> for all \>. The hard cases for Skolem's problem occur when has several dominant singularities. One archetype example is <\eqnarray*> >||*cos*n|)>+\*cos*n|)>+\*cos*n|)>,>>>> with *\>,\*\>,\*\>,\,\,\\\\\>. A variant of this problem is also relevant for the question: if certain terms of this sequence() can become \Pabsurdly small\Q, then the computation of floating point approximations for these terms may take much longer than expected, since we need to compute with a precision that exceeds the order of cancellation. We refer to for more information on Skolem's problem and to for some recent related progress in the context of hypergeometric sequences. On the positive side, examples like() are fairly pathological, so it remains reasonable to hope answering our questions for most practical examples from combinatorics or the analysis of algorithms. One interesting concrete example was studied in. The authors exploit the fact that the then open problem about the uniqueness of the Canham model for biomembranes reduces to proving the positivity of a certain holonomic sequence. They solve the latter problem using singularity analysis and techniques for reliable numerical computations with holonomic functions. In the present paper, among other things, we will extend this approach to more general holonomic sequences. Independently of this work, the implementations from were further extended in. Note that other approaches to automatically prove the positivity of sequences were proposed in. In fact, the main purpose of this paper is to provide the best possible answers to questions\U as long as we do not run into number theoretic trouble. We will also identify the precise nature of possible trouble, thereby clarifying which problems need to be overcome if we want to give even better answers. Most of our results rely on well known techniques. Our main contribution is therefore a detailed analysis of how to answer the questions\U as well as possible using these techniques. Let us briefly outline the structure of this paper. Section contains reminders about holonomic functions, Fuchsian singularities, and holonomic constants. In section, we start with questions and. In order to obtain asymptotic expansions, we use Cauchy's classical contour integral formula for > and deform the contour into afinite number of loop integrals around the smallest singularities of (section). Each of these loop integrals is a truncated Mellin-style integral, whose asymptotic expansion can be computed using classical formulas(section). (In the context of difference equations, note that some authors use the terminology \PPincherle transform\Q instead of \PMellin transform\Q.) Adding up the contributions from each of the singularities, we obtain an asymptotic expansion for> (Theorem). The coefficients of this asymptotic expansion can be computed explicitly and expressed in terms of (non-singular) holonomic constants and values of higher derivatives of =\> at points in>. Using reliable numeric techniques from, one may also compute explicit bounds for the error of the asymptotic expansion(section). Unfortunately, Theorem is imperfect in the sense that some of the terms in the\Pasymptotic expansion\Q for > may cancel out (in which case the bound for the error becomes larger than the expansion itself). This may actually happen in three different ways that will be analyzed in detail in section. First of all, consider a holonomic function that converges on the closed unit disk|\>>. Its value > at is a holonomic constant (and any non-singular holonomic constant can be obtained in this way). Now > is also a holonomic function and the first term of the asymptotic expansion of > is given by \g>> if and only if \0>. This shows that we need a zero-test for holonomic constants in order to detect cancellations of terms in the asymptotic expansion of >. A second kind of cancellation may occur between distinct terms in the asymptotic expansion and only for certain values of . Consider for example <\eqnarray*> |>||++>>|>||++2.>>>> Then the dominant terms > and > cancel out for odd values of . We call this phenomenon \Presonance\Q and the good news is that it can be entirely eliminated by considering a finite number of cases in which > is replaced by a subsequence *n+\>> with\\>> and \,\-1|}>> (see section). A non-periodic variant of resonance is \Pquasi-resonance\Q. Consider for instance the sequence |)>\>> from(). We say that this sequence is quasi-resonant if, for every 0>> and \\>, there exist an infinite number of 0> with |\|>\C*n>>. In fact, we conjecture that quasi-resonance implies resonance (Conjecture), but a proof seems currently out ofreach. Assuming a zero-test for holonomic constants and the absence of quasi-resonance, it is possible to automatically compute the asymptotic expansion of > in a strong sense, without suffering from uncontrolled cancellations(Theorem). Under these hypotheses, we also show in section that -bit floating point approximations for > can be computed in smoothly linear time *log *log log n|)>>: see Theorem. This bound is uniform as long as >. In section we turn to question. Whenever we can compute an asymptotic expansion > of > for which the error -f|\|>> is strictly smaller than |\|>> for n>, the positivity of > can be deduced from the positivity of > for n> and the positivity of ,\,f-1>>>. However, for a sequence |)>\>> like() and \2>, it can be hard decide whether +|\|>+|\|>+|\|>\n>> for all n>: what we need here is an even more precise version of Conjecture. Nevertheless, this example is fairly pathological. For any \0> and \0>>, we always have +|\|>+|\|>+|\|>+\\n>> for all sufficiently large . Conversely, if >, >, >, and > are >-linearly independent, then +|\|>+|\|>+|\|>-\\n>> for infinitely many . In section, we will show that something similar holds in general, by relying on sequence counterparts of results from. For our partial answers to questions\U, we only need the dominant singularities of to be Fuchsian, except in the case of cancellations that also require the examination of subdominant singularities. In the last section, we finally mention a few interesting results that hold if is globally Fuchsian. From bases of local solutions of the differential equation for, it is then classical that we may construct abasis of solutions to the difference equation() using Mellin transforms based at the corresponding singularities. We show that this theory can be made fully effective and also develop a difference counterpart for the concept of transition matrices from. The Mellin transforms can still be applied in the case when is replaced with a complex variable such that is sufficiently large. This can be used for the construction and efficient evaluation of meromorphic solutions to the difference equation *\+\+\*\=0>. One obvious limitation of the present paper is that we only consider the case when the dominant singularities of are Fuchsian. The irregular case has been studied extensively from a theoretical point of view. In a forthcoming work, we intend to investigate this case from a similar perspective as in this paper. A minor restriction of this paper is that we assumed > to be the field of algebraic numbers. This enables us to prove a softly optimal uniform complexity bound for the computation of a -bit floating point approximation of >. For more general subfields of\\>, the results in this paper still go through, using ideas from, but the uniform complexity bounds in section have to be replaced by *log n|)>>. A function > is said to be over > if it satisfies a differential equation <\equation> L*f>+\+L*f=0, where *\+\+L\\|]>> is a linear differential operator in =\/\ z> with \0>. Without loss of generality, we may assume that we normalized so that ,\,L|)>>=1>>. We say that is >-holonomic> if \,\,f>|)>\\> at acertain non-singular point \>. It is not hard to see that a sequence |)>\>\\>> is holonomic over > if and only if its generating function is holonomic over >. Indeed, using the dictionary <\eqnarray*> |>|>>|>|>|>>>> and modulo normalization, any non-zero operator \\|]>>> can be rewritten as anon-zero operator \|]>> and . Then() holds if and only if() holds. <\example> The harmonic numbers =1++\+> satisfy the difference equation <\equation*> *H-*H+*H=0 for all \> and the equation <\equation*> **H-**H+*H=0 for all \>. According to the above dictionary, this yields the equation <\eqnarray*> +1|)>*+2|)>*H|)>-+3|)>*H|)>++1|)>*H|)>>||>>> which can be rewritten as <\eqnarray*> *\**\ H+*H|)>>||>>> Taking =*\-\+n+1>, we thus get *\+3**\+1>. <\remark> In the above example, we multiplied the equation by to make it hold for all \> instead of all \>. In general, given a difference equation() that holds for all \>, we can transform it into a difference equation that holds for all \> through multiplication by *\*>>. From an analytic perspective, if is holomorphic at the origin, then we may retrieve the coefficients > using the Cauchy integral <\equation> f=*\>*|z>*\ z, where we integrate over a circle with center and a sufficiently small radius. Consider a holonomic function that satisfies(). The only possible singularities of are located at the roots of > or at infinity. Modulo a change of variables z+\>> with \\>> or z> (for a singularity at infinity), the study of near such singularities can be reduced to the case of a singularity at the origin. If =0> and if (modulo multiplication by a power of ) we can rewrite the equation() as an equation <\equation*> *|)>+\+A|)>=0 with ,\,A\\> and \0>, then we say that is or at >. If this is the case at all singularities (modulo the above changes of variables), then we say that is . Sometimes, we will also apply this terminology to solutions of the equation or to the sequence |)>\>> instead of . If is holomorphic at the origin and the non-zero singularities of smallest absolute value of are all Fuchsian<\footnote> If has no singularities in >, then the assumption that is Fuchsian at infinity implies that is actually a polynomial. In what follows, we will discard this trivial case and assume that has at least one singularity in >. , then we say that (as well as the sequence|)>\>>) is . If is Fuchsian at the origin, then it is well known that() has a fundamental system of local solutions |)>i\p,0\j\\>> of the form <\equation*> h\z>*+z*\|}>|)>, where \\>, >=>\\\\|}>>, +\+\=r>, and |}>> denotes the ring of convergent power series in . Moreover, there exists a unique such system of solutions (up to apermutation of indices) with the property that the coefficient of >*> in ,j>> vanishes whenever ,j|)>\>. We call it the of solutions at . We call >*> with \> a for . If is Fuchsian at a point \\>, we thus have a corresponding canonical system of solutions >,\,h>> with <\equation*> h>\|)>>*\|}>|}>|)>|]>. If is Fuchsian at infinity, then we also have a corresponding canonical system of solutions >,\,h>> with <\equation*> h>\z>*\|}>|}>. Let >> be the row vector with entries >,\,h>>. Given a local solution to at \\\|}>>, there exists a unique column vector|)>\\> such that >*F|)>>. We call |)>> the initial condition or of at >. This definition still makes sense at non-singular points, in which case |)>> is simply the column vector with entries |)>,f|)>,\,f>|)>/!>. For a precise answer to question , it is important to first introduce various relevant classes of \Pholonomic constants\Q that can be obtained as values of holonomic functions. We will follow4.4 and appendixB>, while restricting us to non-singular and regular-singular holonomic constants. Let > and > denote the sets of monic \|]>> whose coefficients are respectively defined on |\>\\\\1|}>> and \\\\1|}>>. Let > be the set of \> such that is at worst regular-singular at . We also define > to be the set of monic operators \|]>> whose coefficients are defined on |\>\>> and such that is at worst regular-singular at . We define >, >, and > to be the sets of solutions \|}>> to an equation , where \>, \>, or \>, respectively, and such that 1> f> exists. Then we define <\eqnarray*> >|>|\f\\|}>>>|>|>|1> f>\f\\|}>>>|>|>|\f\\|}>>>>> We call > the set of and > the set of . Each of these three sets actually forms a ringB.1>. Moreover, these three rings turn out to be closely related (see also): <\theorem> B.5>> We have <\equation*> \\\\\\\*\, where <\eqnarray*> >|>|*\*\>|)>*\**\*\>|)>\\,\,\\\\|)>\\|}>.>>>> Now consider a holonomic sequence |)>\>\\>> whose generating function belongs to >. So for some \>. Assume that has a Fuchsian singularity at \\>> and let >,\,h>> be the canonical system of local solutions at >. In particular, there exist unique ,\,\\\> with *h>+\+\*h>>. In fact, we have,\,\\\>> (seeB.3>) and we can compute ,\,\> using the algorithms from. Here \Pcomputing\Q is understood in the following sense: for any \\>> and ,r>>, we can compute an approximation |~>\\|]>> of > with |~>-\|\|>\\>. Note that this does not imply the existence of a zero-test for the constants ,\,\>. The zero-test problem for holonomic constants will be discussed in section below. The traditional method to determine the asymptotics of a sequence > whose generating function is holomorphic at the origin is based on the Cauchy contour integral(): <\eqnarray*> >||*\>*|z>*\ z.>>>> If is holonomic, then has only a finite number of singularities ,\,\>>, which are all in>>. For some 0> and ,\|}>>, assume that |\|>\R> for ,m> and |\|>\R> for ,\>. Then we may deform the contour from() into a contour that consists of truncated Hankel contours ,\,\>> and residual arcs ,\,\> on the circle with center and radius : see Figure. Then() becomes: <\eqnarray*> >||*\>*>|z>*\ z+>|z>*\ z|)>.>>>> We may chose the truncated Hankel contours > to depart radially from the origin toward infinity. In the degenerate case when the arguments of certain singularities \\> coincide, we turn the contours clockwise by a fixed sufficiently small angle: see Figure.<\float|float|thb> <\big-figure||gr-frame|>|gr-geometry||gr-grid||gr-grid-old||1>|gr-edit-grid-aspect|||>|gr-edit-grid||gr-edit-grid-old||1>|gr-grid-aspect|||>|gr-grid-aspect-props|||>|gr-text-at-valign|center|gr-dash-style|10|||>>|||>>||||>>||>>||>>|||||>>|||>>||>>||>>||>>|||>>|||>>|||>>||>>||>>||>>||>>||>>||>>||>>||>>||>>||>>||>>||>>>>> Deformation of a Cauchy contour into acontour of radius that avoids a finite number of singularities. Since > and > are aligned with the origin, we slightly modified the directions of the corresponding truncated Hankel contours > and > to avoid collisions. Integrals of the form <\equation> *\>*>|z>*\ z are called <\footnote> The classical Mellin transform uses a straight integration path from to > instead of a Hankel contours around >. We will say that our Mellin integral is \Pbased at >\Q. The use of a Hankel contours extends the definition to the case when is not integrable at >. In the context of difference equations, certain authors prefer the terminology \PLaplace transform\Q, \PPincherle transform\Q, or \PNörlund transform\Q instead of \PMellin transform\Q. . As to the residual integral on \\\\\\>>, we have <\eqnarray*> *\>*>|z>*\ z|\|>>|>|*R|2*\*\>\|f|\<\|\|\>>>|R>|\|>=|f|\<\|\|\>>>|R>,>>>> where |f|\<\|\|\>>>\max\> |\|>>. Note that an upper bound for |f|\<\|\|\>>>> can be computed efficiently using the algorithms from. Most of the remainder of this section is dedicated to determining the asymptotics of integrals of the form() in the case when is Fuchsian at >. The integrals for which|\|>> is smallest typically dominate the other ones, but cancellations may sometimes occur, in which case we will also need to examine the subdominant singularities. Let us consider one simple example of this phenomenon. <\example> The rational function <\eqnarray*> ||++>>>> from the introduction is certainly holonomic, with singularities at =-1>, =1>, and =2>. We have <\eqnarray*> >||+1+2,>>>> where we note that +1=0> for odd values of . In other words, the asymptotics of> depends on the parity of : <\eqnarray*> >|>||)>2*\|)>>>|>|>|2*\+1|)>>>>> Let us first study the very special case when <\eqnarray*> ||-z|)>>*-z|)>|)>>>>> with \\>>, \\>, and \>. Explicit formulas for the asymptotics of the Taylor coefficients > are well known in this case, \ but it is convenient to recall the details of this computation. Modulo a change of variables *z>, we may assume assume without loss of generality that =1>. In this special case, for -Re \>, the contour integral() can rewritten into the full Mellin integral <\eqnarray*> >||*\>*>>>*|)>|z>*\ z,>>>> where >> is a Hankel contour that starts at >, then turns clockwise around , and finally returns to >. Setting >>, this formula becomes <\eqnarray*> >||*\>*>>>|)>>*>|)>|)>|\*n>>*\ \,>>>> where >> is a Hankel contour that starts at =-\>, then turns clockwise around=0>>, and finally returns to =-\>. We regard >|)>>*>|)>|)>>> as an element of >*|)>+\*\|}>|}>|]>m>|)>>, where |}>|}>|]>m>> denotes the set of polynomials in |}>|}>|]>> of degree m> in>: <\eqnarray*> >|)>>*>|)>|)>>||>*m>\>\*\*|)>,>>>> with =\> (Kronecker delta) and =0> for all 0>. Then <\eqnarray*> >||*\>*>>m>\>\*\>*|)>*\*n>*\ \.>>>> Let <\eqnarray*> |)>>|>||)>>>>>> From the classical formula12.22> <\eqnarray*> |)>>||*\>*>>\>*\>*\ \,>>>> we deduce <\eqnarray*> >|)>>|||2*\*\>*>>|)>*\>*\>*\ \,>>>> whence <\eqnarray*> *\>*>>|)>*\>*\*n>*\ \>|||2*\*\>***n-1>*>>|)>*\>*\>*\ \>>|||***n-1>*\>|)>.>>>> When plugging this identity into(), we obtain an asymptotic expansion <\eqnarray*> >|>||\|)>>*n-1>*+m>\>c*n-1-i>*,>>>> where \\|)>,\|)>,\,\>|)>|]>> can be computed explicitly. Note that the series that underlies this expansion usually diverges. It will be useful to introduce <\eqnarray*> |)>>|)>|]>>|>||)>,\|)>,\|)>,\|]>>>||)>>|)>|]>>|>|\\>\|)>>|)>|]>.>>>> Assume now that has a Fuchsian singularity at \\>> and consider a local solution of the form <\eqnarray*> |>|-z|)>>*\|}>|}>|)>|]>,>>>> where \\>>, \\>. We recall that general local solutions to are linear combinations of local solutions of this special form. For some \0> sufficiently small, consider <\eqnarray*> ,\>>|>|*\>*>*|)>>>|z>*\ z,>>>> where >*|)>>> is a Hankel contour from *|)>> around and then back to *|)>>. Our aim is to determine both the asymptotics of ,\>> and an effective bound for the remainder. As in section, we first reduce to the case when =1>> and then perform the change of variables >>. Let |)>=f>|)>\\>*\|}>|}>|]>> and \log|)>>, so that <\eqnarray*> *\>*>>|z>*\ z>||*\>*>>\|)>*\*n>*\ \>>>> Let \> be a truncation order and let <\eqnarray*> |~>>||>*|)>+\+\|)>*\|)>>>>> be the truncation of > modulo >|)>>, with ,\,\\\|]>>. Using(), we can explicitly compute <\eqnarray*> >>|>|*\>*>>|~>|)>*\*n>*\ \>>>> as an element of -1>*\|)>>|)>|]>|]>>. Given \>, let us now study the difference <\eqnarray*> >|>|*\>*>>\>*|)>*\*n>*\ \-*\>*>>\>*|)>*\*n>*\ \.>>>> We have <\eqnarray*> >|>|*|\|>>|\>*>>\>*+|\|>|)>*\*n>*\ \.>>>> Moreover, assuming that \1>, we have |\|>\2/\>, *\>|\|>\\>, and +|\|>|)>*\>|\|>\5+|\|>> for \,\|)>>, so <\eqnarray*> >|>|*n>*\*|\|>>*>|)>-i>*|\|>|)>*|)>Re \|)>>>|>|>|*n>*\*|\|>+Re \-i>*|\|>|)>*|)>+i+j>Re \|)>>>>> Since |~>> is a linear combination of functions >*|)>> with \>, this allows us to compute an explicit bound <\eqnarray*> *\>*>>\|)>*\*n>*\ \-*\>*>>|~>|)>*\*n>*\ \|\|>>|>||)>,>>>> for a suitable constant 0>. Since is Fuchsian at , by taking > sufficiently small, we can use the algorithms from to compute a bound <\eqnarray*> |)>-|~>|)>|\|>>|>|*|\|>>*|\|>>>>> for all > with |\|>\|]>> and |\|>\\>. Given \T-Re \+1>, we may further transform this into a bound <\eqnarray*> |)>-|~>|)>|\|>>|>||\|>-1>.>>>> If \0>, then <\eqnarray*> *\>*>>|)>-|~>|)>|)>*\*n>*\ \|\|>>|>|>*>\-1>*\*n>*\ \>>||>|>*\|)>*n>.>>>> Altogether, we may compute constants ,C\0> and polynomials ,\,c\\|)>>|)>|]>> such that <\eqnarray*> >-+\+c*n>|)>*n-1>|\|>>|>|*n>+C*|)>,>>>> for all 0>. Such a bound can also be proved without the assumption \0>, by doing |1-\|\>> partial integrations before estimating the left-hand side of(). We omit the details, since the case when \0> suffices for the proof of our main Theorem below. To conclude this section, let us finally consider a solution to with \\> for all \>. Let >,\,h>> be the fundamental system of local solutions to with <\eqnarray*> >>|>|-z|)>>*\|}>|}>|)>|]>>>>> for ,r>. Using the algorithms from, we may compute the unique constants ,\,\\\> such that *h>+\+\*h>>. Let \0> and let ,\,T> be minimal integers with \T-Re \+1> for ,r>. We have shown above how to compute polynomials ,\,c-1>\\|)>>|)>|]>> and constants,C>> such that <\eqnarray*> >|)>,\>-+\+c-1>*n-1|)>>|)>*n-1>*\|\|>>|>|*n>*|\|>+C*+\*\|\|>,>>>> for all 0>. Setting >=|\|>*B+\+|\|>*B> and >=|\|>*C+\+|\|>*C>, it follows that <\eqnarray*> ,\>-T>c*n-1-j>*\|\|>>|>|>*n>*|\|>+C>*+\*\|\|>,>>>> for all 0>. Let us now return to the general setting from subsection: for some 0> and ,\|}>>>, we assume that |\|>\R> for ,m> and |\|>\R> for ,\>. We also assume that each of the singularities > with ,m|}>> is Fuchsian. In the previous subsection, we have seen how to compute asymptotic expansions with effective error bounds for the truncated Hankel integrals <\equation*> *\>*>*|)>>>|z>*\ z, for ,m>. Assuming that |\|>*|)>\R>, the truncated Hankel contour > consists of >*|)>>> and two straight stretches between *|)>> and *|\|>|)>>. Using the algorithms from, we may compute a bound |f|\<\|\|\>>> for > on these two stretches. Then we have <\eqnarray*> *\>*>|z>*\ z-*\>*>*|)>>>|z>*\ z|\|>>|>|>*|\|>*|)>>|f|\<\|\|\>>|z>*\ z|\|>>>||>||f|\<\|\|\>>|\*+\*\|\|>>.>>>> Combining this with the bounds for the residual integrals, this gives a first answer to questions and : <\theorem> Let , , >, , >, and ,\,\>> be as in the text above. For any ,\,\\\>, we can compute an asymptotic expansion > for > in |)>>|)>|]>>|)>,n>,log n|]>> together with bounds ,C,E\\>> and \\> such that <\eqnarray*> -f|\|>>|>||n>*|\|>>+|+\*\|\|>>+>,>>>> for all n>. <\remark> In principle, the error at the right hand side of() can be replaced by asingle term of the form >*|\|>>, where |\|>> is smallest among |\|>,\,|\|>>>. However, from a numerical point of view, some of the > and > may be very small (or even zero), in which case it may be preferable to use the error bound from the theorem. We will return to this issue in section below. In Example, we have seen that the contributions of more than one dominant singularity may cancel out in a periodic fashion. Is it possible to predict when this phenomenon occurs? As demonstrated by Example, this is already an interesting question in the case when is a rational function. In that case, exact cancellations can actually be predicted, as we will recall now. In section, we will deal more generally with approximate cancellations as in Example. So consider a sequence |)>\>\\>> whose generating function is is rational. Then the classical Skolem-Mahler-Lech theorem tells us that the zero-set \\f=0|}>> is ultimately periodic. This was first proved by Skolem in the case when =\>, next by Mahler for =\>, and finally by Lech for general fields > of characteristic zero: <\theorem> > Let > be a field of characteristic zero and let |)>\>\\>> be asequence whose generating function is rational. Then there exists a period \\>> and finite sets \,\-1|}>>> and \\> such that <\eqnarray*> \\f=0|}>>||+\*\|)>\\.>>>> The periodic part +\*\> in the above decomposition is actually computable , whereas the computability of the exceptional part > is currently an open problem. Let ,\,\>> be the singularities of and let \exp *\*\|)>>. We say that is if /\\\> for some j>. Setting <\eqnarray*> >|>|\/\=\*\*p/q>,gcd=1|}>,>>>> this is the case if and only if \1>. Berstel and Mignotte proved the following: <\theorem> > Let > be a field of characteristic zero and let |)>\>\\>> be asequence whose generating function is rational. Assume that =0> for infinitely many \> and let > be defined as in )>. Then is resonant and we may compute a finite set \,\-1|}>> such that)> holds for some finite set \\>. It is instructive to detail the computability statements. Let \\,\,\>|)>> and \\|]>>>. Consider j> for which /\=\*\*p/q>> with =1>>. Since /\|)>> is asubfield of >, we must have /\|)>|]>=\\d>. Using that \n/>*log log n+|)>> for 2> , it follows that >\|log log max>|)>|\>>>. This allows us to compute as the smallest ,>|}>> with /\|)>=1>. We conclude that > is computable. Now for every \,\-1|}>>, the generating function |]>>> of +\>>|)>\>> satisfies <\eqnarray*> |]>>>|)>>||i\\>f*z|)>*\*z>,>>>> where =\*\/\>>. This allows us in particular to test whether |]>>=0> and to compute the set >. If needed, we may also deduce the minimal period > and corresponding > for which() holds. Let us now consider an arbitrary holonomic sequence |)>\>\\>> whose generating function is convergent at the origin. Let ,\,\>> be the non-zero singularities of . We define > as in() and say that is if\1>. Note that the arguments at the end of the previous subsection still allow us to compute >. As in the algebraic case, the coefficients of a resonant holonomic sequence can vanish in a periodic manner, or become disproportionally small on aregular basis. This problem can be removed through the consideration of subsequences and case separation, as in Example: <\proposition> With the above notations, the subsequence +\>>|)>\>> is holonomic and non-resonant for any\,\-1|}>>. <\proof> The generating function |]>>> of +\>>|)>\>> satisfies(). Using standard closure properties, it follows that +\>>|)>\>> is holonomic. The singularities of the right-hand side of() are contained in the set \*\\i\,\|}>,j\,\-1|}>|}>>. Therefore the singularities of are contained in the set >=>,\,\>>|}>>. So it suffices to show that >/\>\\> whenever >\\>>. Assume for contradiction that >\\>>, but >=\>> for some 2>. Without loss of generality, we may assume that is minimal with this property. But then we have /\=\*\*p/|)>>> for some \> with |)>=1>, which implies \\> by(): a contradiction. The above proposition has an operator counterpart. Let \z*\> and consider a monic operator |)>\\|]>> of order with . Let ,\,\>> now be the singularities of ( the zeros of the dominators of its coefficients). We define > as in() and say that is if\1>. Let us show how to compute annihilators for the generating functions |]>>>. First of all, for each ,\-1|}>>>, we observe that > f*z|)>=0> for the monic operator >|)>\L*z,\|)>>. Itfollows that \lcm>,\,L-1|}>>|)>> is an annihilator for >>|)>,\,g-1|]>>>|)>>>. For each ,\-1|}>>, we next observe that >>|)>=g>*z|)>>|)>>, so \gcd,\>,\,\-1|}>>|)>>> is still a monic annihilator of >>|)>>. Furthermore, since >=gcd>,\,\|}>>|)>=\>, we must have \\>|)>|]>>. Setting >> and =u*\/\ u>>, we finally note that =\*\>. This allows us to rewrite \\*\> as a monic operator in |]>> with g|]>>=0> for all \,\-1|}>>. We note that the sets of non-zero singularities of > and > ( the zeros of their denominators) both coincide with the set> from the proof of Proposition. Consequently, the set of non-zero singularities of > is >>. In other words, > is non-resonant. <\remark> We may regard the transformation that maps to > as a differential counterpart of the Graeffe transform. Indeed, if is a rational function, then the denominator of |]>>> must be the >-fold Graeffe transform of for each \,\-1|}>>, up to constant multiples. Even for a non-resonant holonomic sequence, the contributions of the dominant singularities to its asymptotics may occasionally cancel out. For instance, theoretically speaking, the sequence > from() might occasionally become small, although this would necessarily happen in a non-periodic manner. Let us make this unlikely phenomenon more precise in the case when |)>\>> is dominant-Fuchsian. Let ,\,\> be the dominant singularities for this sequence (we assume that 1>). We say that |)>\>> is if for any constants 0> and \\>, there exist infinitely many 0> with <\eqnarray*> |\|>>|>||\|>*n>>.>>>> In fact, we conjecture that this never happens: <\conjecture> Assume that |)>\>> is a non-resonant dominant-Fuchsian holonomic sequence. Then |)>\>> is not quasi-resonant. Although Conjecture is far beyond the current state of knowledge in number theory, let us provide meager evidence why we believe that it might hold. The conjecture is already interesting in the case when \>f*z> is a rational function. Even more specifically, assume that <\eqnarray*> >||*\-\*\,>>>> where ,\,\,\\\>> are such that |\|>=|\|>>, but /\\\>. If |\|>\|\|>>, then we clearly have |\|>\|\|>-|\|>|\|>\|\|>> for all . Assume that |\|>=|\|>> and that /\|)>>, /\|)>>, and *\> are >linearly independent. Then Baker's theorem implies the existence of a (computable) constant 0> such that <\eqnarray*> |\>+log |\>+2*k*\*\|\|>>|>|>>>> for all but a finite number of \\\\>. Taking exponentials, it follows that <\eqnarray*> *\|\*\>-1|\|>>|>||2>>>>> and <\eqnarray*> |\|>>|>||\|>|2*n>*|\|>>>>> for all but a finite number of \>. If /\|)>=\*log /\|)>> with \\>, then Baker's theorem implies the existence of a constant 0> with <\eqnarray*> |)>*log |\>+2*k*\*\|\|>>|>|>>>> for all but a finite number of \\\\>. Using a similar reasoning as above, we deduce that our conjecture again holds in this particular case. Of course, our general conjecture is far more ambitious and we have no convincing further evidence for it yet. It may be interesting to consider the slightly weaker conjecture for which() is replaced by <\eqnarray*> |\|>>|>||\|>*\*>>>>>>> for some fixed constant \1>. Using Proposition, we can generalize the technique from Example and reduce the determination of the asymptotic expansion of a holonomic sequence |)>\>\\>> to the non-resonant case, modulo a finite number of case separations. In order to detect periodic cancellations we still need a way to decide whether aparticular solution to the equation in section is actually analytic at a given regular singularity > of . Now we may write *h>+\+\*h>> as a >-linear combination of the canonical basis of local solutions >,\,h>> at >. Let ,r|}>> be the subset of indices for which >> is singular at >. Then is analytic at > if and only if =0> for every I>. In other words, if we have a way to decide whether a given Fuchsian holonomic constant > is zero, then can determine the actual dominant singularity of . By Theorem, it actually suffices to be able to decide whether a holonomic constant in > is zero. We will denote by an oracle to do this. Here we assume an exact representation for elements as > as the value at of a holonomic function in > that is given avanishing operator in |]>> and a finite number of initial conditions in >. It is interesting to point out that if we can determine the dominant singularity of aholonomic function that is analytic at the origin, then we also have an algorithm to test whether holonomic constants in > are zero. Indeed, given \>, let \> be such that >. Then is the dominant singularity of the holonomic function >> if and only if . The above considerations lead to the following variant of Theorem: <\theorem> Let , , >, , >, and ,\,\>> be as in section. Assume that we have an oracle>, that is non-resonant, and that is singular at > for some ,m|}>>. Modulo re-ordering indices, assume that , |\|>=\=|\|>>, and |\|>\|\|>> for p>. Then, for any \\>, we can compute an asymptotic expansion > for > in |)>>|)>|]>,\,\,n>,log n|]>> together with \>> and \\> such that <\eqnarray*> -f|\|>>|>|>*|\|>>,>>>> for all n>. Moreover, if Conjecture holds, then we may require in addition that <\eqnarray*> |\|>>|>|>*|\|>>>>>> for all sufficiently large . In this section, we investigate question . We assume that |)>\>\\>> satisfies the difference equation(). We also assume that its generating function is convergent at the origin and that it satisfies a holonomic equation() that is Fuchsian at the origin. Our goal is to compute > for large using aprecision of bits, with a good uniform complexity in both and . Before we proceed, let us briefly recall some notations and basic facts about fast arithmetic. We define > to be the time that is needed to multiply two -bit integers and we make that customary assumption that /p> is non-decreasing. It was shown recently in that we may take =O>. Approximate computations with real and complex numbers can be done using either fixed point or floating point arithmetic. Let \\*2>> be the set of numbers. A bit of a complex number \> is a number \\> with -z|\|>\2>. A -bit of \> is a number =m*2> with \|]>*2>, \>, -z|\|>\2>, \1>, and either \2> or =0>. It is well known that -bit approximations of bounded exponentials and logarithms can be computed in time *log p|)>>, both for fixed point and floating point representations. Here a bounded exponential is a number > with \|]>> and \B> for some fixed constant0>. Similarly, a bounded logarithm is a number with \\B>. For non-zero \>, this allows us to convert between -bit floating point approximations of and -bit fixed point approximations of . We also observe that, given \\*2> with |\|>\2>>, we can compute a -bit approximation of *\>> in time *log p|)>>. Indeed, it suffices to compute |\/|)>|\>> and \\-2*\*k> with |\|>\\> and then use the fact that*\>=\*\>>. We will finally need the following result that was essentially proved in. <\proposition> Let +L*\+\+L\\|]>> be Fuchsian at the origin. Let|)>i\\,0\j\\>> be the canonical solutions of at the origin and let >*> be the dominant monomial of >. Let ,\,\>> be the non-zero singularities of , let \min |\|>,\,>|\|>|}>>>, and let max max\\> |\|>>, where *z>=h+\+h*>. Let > be the total bit-size of the operator and let \|]>*2> with \\>. Then we may compute a -bit fixed point approximation of > using +log p|)>*p*log p|)>|)>> bit-operations, for all >. This complexity is uniform in and >, provided that ,\,\>>, ,\,\>>, ,\,\>> remain fixed and =O>. <\proof> We approximate > using the technique from3>. The matrices > from(3.10) and(3.12) in that section have size +log k|)>>. Since =O>, it suffices to evaluate *\*A> for > in order to obtain -bit approximations for the values>. Using binary splitting, this requires +log p|)>*p*log p|)>|)>> bit operations. Since -bit approximations of >*> can be computed using *log p|)>> bit operations for all \>>, this allows us to compute a -bit fixed point approximation of > in time +log p|)>*p*log p|)>|)>>. If >, then the most efficient strategy is to compute> exactly as an element of> and convert the result into a fixed point or floating point approximation. In fact, as in>, it suffices to compute in the algebraic number field > generated by the coefficients of> and the initial conditions ,\,f> with \\k\s\\=0|)>>. Let us recall from how to compute > using binary splitting. For each \>, let > be the column vector with entries ,\,f>. If t>, then <\eqnarray*> >||N+1>*F,>>>> where <\eqnarray*> N+1>>|||||>|||>|>||||>||\>>||\>>|>||\>>>>>>.>>>> More generally, for \> and N+k>\\N+k>*\*\N+1>>, we have <\eqnarray*> >||N+k>*F>>>> and N+k>> can be computed efficiently using binary splitting: <\eqnarray*> N+k>>|||k/2|\>\N+k>*\N+|k/2|\>>.>>>> Since is Fuchsian at the origin, the bit-size of the entries of N+k>> is bounded by |)>>. Using a classical complexity analysis, it follows that N+k>> can be computed in time |)>*log k|)>>. In particular, we may compute > in time n|)>|)>>. Converting the result into -bit fixed point or floating point notation can be done in time |)>>. Having dealt with the case when > in the previous subsection, let us now assume that > and >. If has a dominant singularity at >, then > typically grows like >, in first approximation. Consequently, a -bit fixed point approximation of > typically requires > bits if |\|>\1>. In particular, unless >, then it is hopeless to compute such approximations in smoothly linear time in . From now on, we will focus on the computation of a -bitfloating point approximation of>. Under the assumption that |)>\>> is not quasi-resonant, we will show that such an approximation can be computed in uniform smoothly linear time. So assume that |)>\>> is not quasi-resonant and let ,\,\>> be the singularities of. Assume that ,\,\> are the dominant singularities of with 1>. We compute>using <\eqnarray*> >||*\>*\\\\\\\\>|z>*\ z,>>>> where > is an axial truncated Hankel contour around > until |)>*\> and > is acircular arc around from |)>*\> to |)>*\> (or to |)>*\> if ), for ,m>>. Let p> be a temporarily increased working precision with > and >. We will specify later. For some sufficiently small \0> with \> and any q/\>, we take <\eqnarray*> >|>|.>>>> Since is Fuchsian at ,\,\>, we may compute positive constants >, , and > suchthat <\eqnarray*> |\|>>|>|>>>>> for all \\\\\> (uniformly, for all \\>). It follows that <\eqnarray*> *\>*\\\\>|z>*\ z|\|>>|>|>*|)>||\|>>\2*C*>*\||\|>>.>>>> For ,m>, we have <\eqnarray*> *\>*>|z>*\ z>|||)>-\*\*\>|)>|)>*\=-\*\*\>|)>*\,>>>> where <\eqnarray*> >|>|*\>*>*\|)>|>*\ w.>>>> We note that the integrand *\|)>*>> satisfies a holonomic equation whose total size is bounded by >. Consequently, the same holds for >. Since >>> is analytic at and bounded by |)>=\>> for \\>, the uniformity assumptions of Proposition are satisfied. It follows that we may compute a bit fixed point approximation of *\*\>|)>> using |)>> bit operations. We may also compute a -bit fixed point approximation of /\|)>> using |)>> bit operations. Altogether, this allows us to compute a number \\|]>*2>> with <\eqnarray*> -\*\*\>|)>*/\|)>|\|>>|>|>>>> using |)>> bit operations. By construction, it follows that <\eqnarray*> *\-+\+v|)>|\|>>|>|+2*C*\>*\,>>>> provided that q/\>. Since |)>\>> is not quasi-resonant, there also exist constants 0>>, \\>, and \0> such that <\eqnarray*> *\|\|>>|>|>>>>> for all n>. In order to obtain -bit floating point approximations of *\> and then >, it suffices to chose in such a way that <\eqnarray*> +2*C*\>*\>|>|*M*n>*2.>>>> Using that +2*C*\>*\\2**n>*2>, this is certainly the case if we take <\eqnarray*> |>|+\|)>*log n+log +2.>>>> Note that we have indeed have > for this choice of . In fact, we even have p> as soon as >. In combination with the results from section, we have proved the following: <\theorem> Let |)>\>> be a dominant-Fuchsian holonomic sequence that is not quasi-resonant. Then there exists an algorithm to compute a -bit floating point approximation of> using |)>|)>> bit operations. This bound is uniform in and , provided that>>. <\corollary> Let |)>\>> be a holonomic sequence and assume Conjecture. Then there exists an algorithm to compute a -bit floating point approximation of> using |)>|)>> bit operations. This bound is uniform in and , provided that>>. <\remark> Note that the operator with may have singularities > with |\|>\|\|>>>, as long as the particular solution remains analytic at>. Assuming that |)>\>> is Fuchsian and that we have an oracle , we may verify whether this is the case by checking that the coefficients of the singular canonical solutions >> in all vanish. Note that our theorem and its corollary only claim the of an efficient algorithm to compute >; for this, we do not need the oracle . <\remark> In practice, for the fast evaluation of a Fuchsian holonomic sequence |)>\>>, we first make it non-resonant using the pre-treatment from section, then apply the algorithm from the previous subsection for the evaluation of >, while falling back on the slower algorithm from section whenever we detect massive cancellation. In particular, this mixed strategy takes care of exceptional values of for which > vanishes. Whenever this algorithm does not run in time |)>|)>> when \>, we note that |)>\>> would actually provide an explicit counterexample to Conjecture. <\remark> If we replace() by() for some fixed constant \1>, then the theorem and its corollary still hold, but the complexity bound becomes>*log |)>|)>>. In this section, we study question . We assume that |)>\>\\\|)>>> is a holonomic sequence whose generating function is convergent at the origin. Modulo the pre-treatment from section, we may assume without loss of generality that |)>\>> is non-resonant. We also assume that is dominant-Fuchsian. Our aim is to decide whether \0> or \0> for all \> or for all sufficiently large . Our positivity test will rely on a way to compute limsups and liminfs of certain oscillating sequences. For this, we will adapt results from. Recall that a is a field of germs of differentiable real functions at infinity that is closed under differentiation. In particular, > and \\>,log x|)>> are Hardy fields. The following is adirect consequence of3>. <\theorem> Let ,\,g> be real functions whose germs at infinity belong to a Hardy field and such that \\\g>, =o|)>,\,g=o|)>>. For each ,k|}>>, let ,\,\>> be >-linearly independent numbers in >. Consider the function <\eqnarray*> >|>|*x|)>*\>,\,\>*x|)>*\>,\,\*x|)>*\>,\,\>*x|)>*\>|)>>>>> from > into the torus \*\>|)>> of dimension +\+r>. Then ,\|)>|)>> is dense in> for any \\>. What we really need is a counterpart of this theorem for sequences: <\corollary> With the notations of the theorem, assume that =x> and that ,\,\>,2*\>> are >-linearly independent. Then ,n+1,\|}>|)>> is dense in > for all \\>. <\proof> For ,\,w|)>,w=,\,w|)>\\>, let <\eqnarray*> -w|\|>>|>|-w|\|>,\,-w|\|>|)>.>>>> We also define <\eqnarray*> >>|>|*x|)>*\>,\,\>*x|)>*\>,\,\*x|)>*\>,\,\>*x|)>*\>,\*x*\>|)>.>>>> Let \\> and let > be any constant with \max|\|>,\,>|\|>,2*\|)>>. If > is sufficiently large, then >|)>-\>|\|>\\*-x|\|>> for all x\n>. By the theorem, the image >,\|)>|)>>> is dense in >. Given \0> and \>, we may thus find an n> such that <\eqnarray*> >-w>|\|>>|>||2*\>,>>>> where >\>. Let n> be an integer with minimal distance to . Since >-w>|\|>\\/|)>>, we have in particular >-w>|\|>=>-1|\|>=*x*\>-1|\|>\\/|)>>, whence \\/|)>>. It follows that <\eqnarray*> >-\>|\|>>|>|*\|2>,>>>> whence <\eqnarray*> -w|\|>>|>|>-w>|\|>>>||>|>-\>|\|>+>-w>|\|>>>||>||2>+|2*\>\\.>>>> This shows that ,n+1,\|}>|)>> is indeed dense in >. We will also need the following counterpart of5>: <\theorem> Let ,\,g\\\|)>\\>,log x|)>> be real functions with \\\g>. For each ,k|}>>, let ,\,\>\\\\>. Consider the function <\eqnarray*> >|>|*x|)>*\>,\,\>*x|)>*\>,\,\*x|)>*\>,\,\>*x|)>*\>|)>>>>> from >> into the torus \*\>|)>> of dimension +\+r>. Let <\equation*> P\\>,\,Z>>>,\,>,\,Z>>>|]> be a Laurent polynomial that takes only real values on >. Then \> P|)>> and \> P|)>> are both computable numbers in \\>. <\proof> Using the rewriting techniques from the proof of 5>, we first reduce the general case to the case when ,\,\>> are >-linearly independent for ,k>>. (Note that there exists an algorithm to find >-linear dependencies between algebraic numbers, so we do not need the general oracle to find >-linear dependencies between exp-log constants.) We next reduce to the case when ,\,\>,2*\>> are >-linearly independent. Assume on the contrary that *\+\+c>*\>+2*\*c=0> with ,\,c>\\> and \0>. Without loss of generality, we may assume that >\0>. Taking =\/c>> for ,r-1>, we may rewrite *x*\>=*x*\>|)>>>> and >*x*\>=\*2*\*\/c>>**x*\>|)>>*\*-1>*x*\>|)>-1>>> as Laurent polynomials in *x*i>,\,\-1>*x*i>|]>>, while performing the corresponding corresponding substitutions in . We repeat this procedure with ,\,\-1>> in the role of,\,\>> until ,\,\>,2*\>> are >-linearly independent. After the above reductions, we are in a position to apply Corollary. Thisyields <\eqnarray*> \> P|)>>||\> P>>|\> P|)>>||\> P.>>>> Now \> P\\> and \> P\\> can be computed using classical algorithms from effective real algebraic geometry. Let ,\,\\\> be the dominant singularities of . By Theorem, we may compute constants ,\,t\\>, \\\\>, \\>, \\>, 0>, \\>, and \\\\> such that <\eqnarray*> -i\m>j\t>c*n>*\*>|\|>>|>|>*\*-1>>>>> for all n> and =\> for all . Setting <\eqnarray*> >||i\m>j\t>c*n-\>*||\|>>|)>,>>>> we may rewrite() as <\eqnarray*> -\*|\|>*n>*>|\|>>|>|>*\*-1>.>>>> Now observe that > can be interpreted as a polynomial <\eqnarray*> >|>|*\>|)>,*n*\>|)>|]>.>>>> Since \\> for all \>, this allows us to apply Theorem and compute >\limsup\> \> and \ >\liminf\> \>. If >\0>, then() yields \0> for all \>>>. If >\0>, then \\>/2> for infinitely many . For any \>>> with \\>/2>, the relation() then yields \0>. The only remaining case is when >=0>. In lucky cases, we may look at the next subdominant term of the asymptotic expansion of > and prove the positivity of -\*|\|>*n>*>> in a similar way as above. However, in general, the positivity of > can be hard to decide. In fact, a general decision procedure would allow us to answer difficult questions about diophantine approximability. For instance, given a real algebraic number >>, the positivity of the holonomic sequence <\equation*> log n-cos|)>*log n-> is related to a rate of diophantine approximability of > by \> of the form <\eqnarray*> p,q\\>,-|\|>>|>|*log q>.>>>> We do not know of a general decision procedure for this kind of inequalities. Let be the generating function of a holonomic sequence |)>\>>. So far, we have mainly been interested in the case when is convergent at the origin and dominant-Fuchsian (possibly modulo a reduction to the non-resonant case as in section). This is indeed sufficient for obtaining information about |)>\>> through its asymptotic properties. In this section, we assume that is globally Fuchsian and study nice additional properties that hold in this case. For simplicity, we assume that |)>\>> satisfies a non-degenerate difference equation(). We normalize > to make it divisible by *\*>> and we let *\+\+L\\|]>> be the corresponding differential operator with , as constructed in section. We let ,\,\>> be the singularities of. First of all, for Fuchsian , the truncated Mellin integrals from() tend to a limit <\equation> *\>*>|z>*\ z when tends to infinity and is sufficiently large. This leads to the exact representation <\eqnarray*> ||*\>*>>|z>*\ z.>>>> We call() a full that is based at >. <\remark> We may take > to be the contours from infinity to a point |~>> close to >, which next performs a complete circular turn around >, and then goes back to infinity along the same direction where it came from. Then we have <\eqnarray*> *\>*>|z>*\ z>||*\>*>|z>*\ z+*\>*|~>>>> f|)>|z>*\ z,>>>> where > denotes the circle around > and > f> denotes the difference between the analytic continuations of that get around > on the left and right, respectively. Note that > f> is a solution of the same differential equation as , > f=0>. The formula() is convenient for machine computations due to the fact that we only have asingle stretch going to infinity. More generally, for an analytic function > on > and with =O>|)>> at infinity, we define <\eqnarray*> \|)>>|>|*\>*>|z>*\ z.>>>> Then we note that <\eqnarray*> \|)>>|| *\|)>|)>>>| \|)>>|| |)>|)>,>>>> where the second relation is proved using integration by parts. Consequently, the sequence f|)>|)>\>> satisfies the same recurrence relation() as |)>\>>. We observe that() only depends on the behavior of at the singularity >. Expressing in terms of the canonical basis >,\,h>> of local solutions to at >, <\eqnarray*> ||*h>+\+c*h>,c,\,c\\,>>>> and setting <\eqnarray*> >>|>| h>,i=1,\,r,>>>> it follows that <\eqnarray*> f>||*\>+\+c*\>.>>>> Here we note that >=0> whenever >> is analytic at >. Moreover, we recallthat <\equation*> h>\|)>>*|)>|)>+z*\|}>|}>|)>|]>|)>, for some \\> and \>. If \\> or 0>, then the sequence>> has anon-zero formal transseries in *n-1>*\|)>>|)>|]>*|]>|]>> as its asymptotic expansion, by the formulas from subsection. We will sometimes identify>> with this transseries. Let >,\,\>>> be the collection of all non-zero >> with ,\|}>> and ,r|}>>>. Since the dominant monomials of >,\,\>>> are pairwise distinct when considering them as transseries, these sequences are >-linearly independent. From() and(), we also know that any sequence solution of() can be written as a >-linear combination of>,\,\>>>>. Conversely, we noted at the end of subsection that each >> is actually a solution of(). This shows that >,\,\>>> forms basis of the solution space of() in >>. Since we assumed > to be non-degenerate, this space has dimension , so =s>>. We denote by >> the row vector with entries >,\,\>>. We have shown that() has a basis of formal transseries solutions <\equation*> \>,\,\>\\*n>*\|)>>|)>|]>|]>|]>. In fact, it is well known that we may compute a canonical system of formal solutions in *n>*\|]>|]>>, similar to the ones that we saw in the differential case in subsection. Let us briefly describe how to do this. We have seen that for any singularity > of , there exists at least one formal solution of the form >|)>\\*n>*\|)>>|)>|]>|]>|]>>. Modulo a transformation \\*\>, we may assume without loss of generality that =1>. We next replace > by *\|)>> in>, where =n*\/\ n>. After multiplication by a suitable power of , this yields an operator <\eqnarray*> >*\>||\>n*\|)>\\|]>|]>|]>>>>> with |)>\0>. Whenever we have a formal solution >> with >|)>\n>*>, then this implies that > is divisible by -\|)>>. Inversely, if \\> is a root of multiplicity> of > in >, then for any \>, there exists a unique formal solution n>*+n-1>*\|]>|]>> to(). Indeed, writing =n>*\>\*n> with \\>, we have <\eqnarray*> >* f|)>=n>*\>n*\+\-j|)>|)>>||>>> which yields the recurrence relation <\eqnarray*> +\-m|)>|)>>||i\m>\+\-m+i|)>|)>>>>> for the computation of the coefficients >. The solution is unique when requiring that => and that > is divisible by > whenever is a root of multiplicity of > in >. Let >,\,\>> be the collection of all formal solutions of() in *n>*\|]>|]>> that we obtain in the way that we just described, with >\\>>. Since the dominant monomials of these solutions are pairwise distinct, this again forms a fundamental system of solutions; we call it the of() at infinity and we denote by>> the row vector with entries >,\,\>>. Since >> and >> are both fundamental systems of solutions, there exists a matrix \\s>> with <\eqnarray*> >>||>*\.>>>> Since >> has coefficients in |)>>|)>|]>> and > has coefficients in >, the matrix > must actually be in |)>>|)>|]>r>>. For machine computations, the recurrence relation() is not very efficient if we want to compute a large number of terms. In that case it is better to rewrite the original equation() with respect to >, which transforms the shift operator > into>>. Compositions of a power series with > can be computed efficiently in a relaxed manner using the algorithm from3.4.2>. The equation() is not necessarily \Precursive\Q, so it is not always possible to directly solve it using the techniques from. Nevertheless, it can always be rewritten as a recursive equation using the algorithms from. Altogether, this allows us to compute the first coefficients of the canonical solutions >,\,\>> in time *log N|)>|)>>, which is softly optimal in the bit-size of the result. <\remark> The equation() can be used to map formal transseries solutions of() to actual holonomic sequences. It is interesting to note that this association actually preserves all difference ring operations, in a similar way as accelero-summation in the differential setting. Let us briefly recall the concept of a transition matrix, which forms an important ingredient for the efficient evaluation of holonomic functions in. We will use the notations >> and |)>> from section for canonical systems of local solutions and generalized values at >. Given a non-singular path \\>> between two non-singular points ,\\\\|}>>>, the analytic continuation of the canonical solutions at > can be expressed as linear combinations of the canonical solutions at>. In other words, there exists amatrix \\>\\r>>>with <\eqnarray*> >>||>*\\\>.>>>> We call \\>> the along the path \\>. We naturally have the relation <\eqnarray*> \\\\>>||\\>*\\\>>>>> for composed paths. In terms of generalized values of a solution to(), we also obtain <\eqnarray*> |)>>||\\>*F|)>.>>>> These notions extend to the case when the paths start and/or end at singular points, modulo the precaution that we specify the angles that are used to approach the singularities (in order to determine the branch of the logarithm). Let us now study the analogue of transition matrices for sequences. Given \> and ,s-1|}>>>, assume that() has a unique solution |)>\>> with =1> and =0>> for ,s-1|}>\>>. Then we will denote this solution by|)>\>>. We denote by> the row vector with entries ,\,\> if these solutions are all defined and call it the canonical system of solutions at . Given a general solution |)>\>> to(), we call the column vector > with entries ,\,f> the generalized value of |)>\>> at , so that <\eqnarray*> ||*F.>>>> By definition, the > satisfy a recurrence relation <\eqnarray*> >||N+1>*F,>>>> where N+1>> was defined in(). More generally, for \> and N+k>\\N+k>*\*\N+1>>, we have <\eqnarray*> >||N+k>*F.>>>> Setting N+k>\\N>>, this relation extends to the case when \>. Dually, we also have <\eqnarray*> >||*\N+k>.>>>> We call N+k>> the between and . We have seen in section how to compute N+k>> in time *log k|)>|)>> using binary splitting. In section, we introduced the canonical system of solutions >> of() at infinity. Given a solution |)>\>> of(), this leads to the corresponding notion of generalized value >\\> at infinity with <\eqnarray*> ||>*F>.>>>> For any \>, the matrix \>> with <\eqnarray*> >>||\>*F,>>|>||>*\\>>>>> is called the between and >, whenever it exists. Using a combination of the techniques so far, we may compute the transition matrix\>> as follows. Consider one of the canonical solutions |)>\>=|)>\>> of() at and the corresponding power series solution \|}>> of() at the origin. Given one of the singularities > of , we may use the algorithms from to compute the transition matrix\>> for and then re-express as a >-linear combination of the canonical solutions>,\,h>>> at>. The collection of these relations yields as a >-linear combination of the canonical solutions >,\,\>>. Using the methods from sections and, we finally obtain as a |)>>|)>|]>>-linear combination of >,\,\>>. Doing this for each > with ,s>>, this yields the transition matrix \>\\|)>>|)>|]>s>>. For fixed and large, we may compute >-approximations of the entries of \>> in time p|)>|)>>, using the algorithms from. Our main focus in this paper is on the study of sequence solutions to holonomic equations(). Yet, it is interesting to note that the definition of Mellin transforms of the canonical solutions \h>> generalizes to complex numbers for which > decreases sufficiently fast on >: <\eqnarray*> \|)>>|>|*\>*>|z>*\ z.>>>> Applying this to the theory from section, this yields a fundamental system of analytic solutions to the difference equation <\equation*> \*f+\+\*f=0 that extends our fundamental system of sequence solutions. For \>, we also note that the integrand of() is still holonomic over > and Fuchsian. Consequently, we may evaluate it with a precision of bits in time p|)>|)>>, using the algorithms from. For general \>, the evaluation can be done in time |)>> using the baby-step-giant-step technique from. It is also possible to extend the uniform complexity analysis from section to this setting, but additional care is needed for the treatment of non-real arguments . We intend to carry out the detailed analysis in a forthcomingpaper. <\acknowledgments*> We are grateful to Marc Mezzarobba and Ruiwen Dong for some references and helpful discussions. <\bibliography|bib|tm-plain|> <\bib-list|46> A.Baker. Linear forms in the logarithms of algebraic numbers (III). , 14(2):220\U228, 1967. M.A.Barkatou. . , Institut National Polytechnique de Grenoble, 1989. S.Basu, R.PollackM.-F.Roy. , 10. Springer-Verlag, 2006. 2-nd edition to appear. J.BerstelM.Mignotte. Deux propriétés décidables des suites récurrentes linéaires. , 104:175\U184, 1976. G.D.Birkhoff. Formal theory of irregular linear difference equations. , 54:205\U246, 1930. M.D.Boshernitzan. Uniform distribution and Hardy fields. , 62:225\U240, 1994. N.Bourbaki. . Éléments de Mathématiques (Chap. 5). Hermann, 2-nd, 1961. R.P.Brent. Fast multiple-precision evaluation of elementary functions. , 23(2):242\U251, 1976. D.V.ChudnovskyG.V.Chudnovsky. Computer algebra in the service of mathematical physics and number theory (Computers in mathematics, Stanford, CA, 1986). , 125, 109\U232. New-York, 1990. R.Dong. Computing error bounds for asymptotic expansions of regular p-recursive sequences. , École polytechnique, 2021. Unpublished. Supervised by S.Melczer and M.Mezzarobba. A.Duval. . , IRMA, Strasbourg, France, 1984. S.FischlerT.Rivoal. On the values of G-functions. , Arxiv, 2011. Philippe FlajoletRobert Sedgewick. . Cambridge University Press, 2009. L.Fuchs. Zur Theorie der Linearen Differentialgleichungen mit veränderlichen Coefficienten. , 66(2):121\U160, 1866. H.Galbrun. Sur la représentation des solutions d'une équation linéaire aux différences finies pour les grandes valeurs de la variable. , 36:1\U68, 1913. H.Galbrun. Sur certaines solutions exceptionnelles d'une équation linéaire aux différences finies. , 49:206\U241, 1921. S.GerholdM.Kauers. A procedure for proving special function inequalities involving a discrete parameter. , 156\U162. ACM, 2005. D.HarveyJ.vander Hoeven. Integer multiplication in time >. , 193(2):563\U617, 2021. J.vander Hoeven. On the computation of limsups. , 117/118:381\U394, 1996. J.vander Hoeven. Fast evaluation of holonomic functions. , 210:199\U215, 1999. J.vander Hoeven. Fast evaluation of holonomic functions near and in singularities. , 31:717\U743, 2001. J.vander Hoeven. Relax, but don't be too lazy. , 34:479\U542, 2002. J.vander Hoeven. Efficient accelero-summation of holonomic functions. , 42(4):389\U428, 2007. J.vander Hoeven. From implicit to recursive equations. , 30(3):243\U262, 2018. J.vander Hoeven. . Scypress, 2020. J.vander Hoeven. Efficient accelero-summation of holonomic functions. , HAL, 2021. , corrected version of. AlstonS.Householder. Dandelin, Lobacevskii, or Graeffe. , 66(6):464\U466, 1959. G.K.Immink. On the relation between global properties of linear difference and differential equations with polynomial coefficients, I. , 113:201\U233, 1994. G.K.Immink. On the relation between global properties of linear difference and differential equations with polynomial coefficients, II. , 128:168\U205, 1996. G.K.Immink. On the relation between global properties of linear difference and differential equations with polynomial coefficients. , 200:59\U76, 1999. M.KauersV.Pillwein. When can we detect that a p-finite sequence is positive? , 195\U201. ACM, 2010. G.Kenison, R.Lipton, J.OuaknineJames Worrell. On the Skolem problem and prime powers. , 289\U296. ACM, 2020. C.Lech. A note on recurring series. , 2:417\U421, 1953. K.Mahler. Eine arithmetische Eigenschaft der Taylor-koeffizienten rationaler Funktionen. , 38:50\U60, 1935. S.MelczerM.Mezzarobba. Sequence positivity through numeric analytic continuation: uniqueness of the canham model for biomembranes. 2011.08155, Arxiv, 2020. M.Mezzarobba. Rigorous multiple-precision evaluation of D-Finite functions in SageMath. , HAL, 2016. . M.Mezzarobba. . , École polytechnique, Palaiseau, France. N.E.Nörlund. Fractions continues et différences réciproques. , 34:1\U108, 1910. N.E.Nörlund. . Springer Verlag, Berlin, 1924. K.Nosan, A.Pouly, M.ShirmohammadiJ.Worrell. The membership problem for hypergeometric sequences with rational parameters. , 381\U389. 2022. J.OuaknineJ.Worrell. Decision problems for linear recurrence sequences. , 7550, 21\U28. Bordeaux, France, September 2012. Springer-Verlag. S.Pincherle. Sur la génération de systèmes récurrents au moyen d'une équation linéaire différentielle. , 16:341\U363, 1892. J.B.RosserL.Schoenfeld. Approximate formulas for some functions of prime numbers. , 6(1):64\U94, 1962. Th.Skolem. Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit anwendung auf diophantische Gleichungen. , 1(6), 1933. E.T.WhittakerG.N.Watson. . Cambridge University Press, 4, 1996. D.Zeilberger. A holonomic systems approach to special functions identities. , 32:321\U368, 1990. <\initial> <\collection> <\attachments> <\collection> <\associate|bib-bibliography> <\db-entry|+byKiFsUoTc7rBN|book|TeXmacs:vdH:book> <|db-entry> > <\db-entry|+qYhUkmR1lNMNvBm|article|Zeil90> <|db-entry> > <\db-entry|+qYhUkmR1lNMNuzg|book|FS09> <|db-entry> Robert > <\db-entry|+6nR2EeZ2WtApxqe|inproceedings|KLOW20> <|db-entry> R. J. James > <\db-entry|+6nR2EeZ2WtApxqf|inproceedings|NPSW22> <|db-entry> A. M. J. > <\db-entry|+1x7DTJmS2D77lxv9|techreport|MM20> <|db-entry> M. > <\db-entry|+1CQ02y1d169CJ0pg|inproceedings|CC90> <|db-entry> G. V. > <\db-entry|+qYhUkmR1lNMNvCL|article|vdH:hol> <|db-entry> > <\db-entry|+qYhUkmR1lNMNvCR|article|vdH:singhol> <|db-entry> > <\db-entry|+1CQ02y1d169CJ0px|phdthesis|Mezza:phd> <|db-entry> > <\db-entry|+2TBM2uQj20Lpoc1m|techreport|Mezza16> <|db-entry> > > <\db-entry|+6nR2EeZ2WtApxqh|mastersthesis|Dong21> <|db-entry> > Melczer and M.Mezzarobba> <\db-entry|+2TBM2uQj20Lpoc1i|inproceedings|GK05> <|db-entry> M. > <\db-entry|+2TBM2uQj20Lpoc1j|inproceedings|KP10> <|db-entry> V. > <\db-entry|+2TBM2uQj20Lpoc1y|article|Pin1892> <|db-entry> > <\db-entry|+qYhUkmR1lNMNvCB|article|vdH:limsup> <|db-entry> > <\db-entry|+2TBM2uQj20Lpoc28|article|Nor10> <|db-entry> > <\db-entry|+2TBM2uQj20Lpoc20|article|Gal1913> <|db-entry> > <\db-entry|+2TBM2uQj20Lpoc29|book|Nor24> <|db-entry> > <\db-entry|+2TBM2uQj20Lpoc21|article|Gal1921> <|db-entry> > <\db-entry|+2TBM2uQj20Lpoc26|phdthesis|Duv:phd> <|db-entry> > <\db-entry|+2TBM2uQj20Lpoc25|phdthesis|Bar:phd> <|db-entry> > <\db-entry|+1x7DTJmS2D77lxv6|article|Imm94> <|db-entry> > <\db-entry|+1x7DTJmS2D77lxv7|article|Imm96> <|db-entry> > <\db-entry|+1x7DTJmS2D77lxv8|article|Imm99> <|db-entry> > <\db-entry|+28fKGNvA1Suxj1mt|article|Fuchs1866> <|db-entry> > <\db-entry|+16HIDukw8D184fV|techreport|vdH:reshol-corrected> <|db-entry> > , corrected version of> <\db-entry|+1GlSanJG2BTnBMZS|techreport|FR11> <|db-entry> T. > > <\db-entry|+6nR2EeZ2WtApxqg|book|WW96> <|db-entry> G. N. > <\db-entry|+16HIDukw8D184fe|article|Sko33> <|db-entry> > <\db-entry|+28fKGNvA1Suxj1n0|article|Mah35> <|db-entry> > <\db-entry|+16HIDukw8D184fa|article|Lech53> <|db-entry> > <\db-entry|+16HIDukw8D184fg|article|BM76> <|db-entry> M. > <\db-entry|+16HIDukw8D184fh|inproceedings|OW12> <|db-entry> J. > <\db-entry|+28fKGNvA1Suxj1n7|article|RS62> <|db-entry> L. > <\db-entry|+2TBM2uQj20Lpoc1o|article|Hou59> <|db-entry> > <\db-entry|+2TBM2uQj20Lpoc1g|article|Bak67> <|db-entry> > <\db-entry|+Oyo7B0N11pDKjsi|article|vdH:nlogn> <|db-entry> J. van der > >> <\db-entry|+qYhUkmR1lNMNuw1|article|Br76b> <|db-entry> > <\db-entry|+6nR2EeZ2WtApxqc|article|Bos94> <|db-entry> > <\db-entry|+qYhUkmR1lNMNuvu|book|Bour61> <|db-entry> > <\db-entry|+qYhUkmR1lNMNuvz|book|BPR06> <|db-entry> R. M.-F. > <\db-entry|+2TBM2uQj20Lpoc1r|article|Birk30> <|db-entry> > <\db-entry|+UxLEI9PJlFl3Ur|article|vdH:relax> <|db-entry> > <\db-entry|+qYhUkmR1lNMNvDk|article|vdH:newimpl> <|db-entry> > <\db-entry|+qYhUkmR1lNMNvD1|article|vdH:reshol> <|db-entry> > <\references> <\collection> > > > > > > > > > |math-font-series||Q1>|1>> |math-font-series||Q2>|1>> |math-font-series||Q3>|1>> |math-font-series||Q4>|1>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> TeXmacs:vdH:book Zeil90 FS09 KLOW20 NPSW22 MM20 FS09 CC90 vdH:hol vdH:singhol Mezza:phd Mezza16 MM20 Dong21 GK05 KP10 Pin1892 vdH:singhol MM20 vdH:limsup Pin1892 Nor10 Gal1913 vdH:singhol Nor24 Gal1921 Duv:phd Bar:phd Imm94 Imm96 Imm99 CC90 Fuchs1866 vdH:reshol-corrected vdH:reshol-corrected FR11 vdH:reshol-corrected vdH:reshol-corrected vdH:singhol vdH:hol WW96 vdH:singhol vdH:singhol vdH:hol Sko33 Mah35 Lech53 BM76 OW12 BM76 RS62 Hou59 Bak67 vdH:nlogn Br76b vdH:singhol vdH:singhol vdH:hol vdH:singhol CC90 vdH:singhol CC90 vdH:singhol Bos94 vdH:limsup Bour61 vdH:limsup vdH:limsup vdH:limsup BPR06 Birk30 vdH:relax vdH:relax vdH:newimpl vdH:reshol CC90 vdH:hol vdH:singhol vdH:singhol vdH:reshol vdH:singhol CC90 vdH:reshol <\associate|figure> |3.1>|> Deformation of a Cauchy contour into a |->|-0.3em|>|0em||0em|>>contour of radius |R> that avoids a finite number of singularities. Since |\> and |\> are aligned with the origin, we slightly modified the directions of the corresponding truncated Hankel contours |\> and |\> to avoid collisions. |> <\associate|toc> |math-font-series||font-shape||1.Introduction> |.>>>>|> |1.1.Statement of the problems |.>>>>|> > |1.2.Overview of our contributions |.>>>>|> > |math-font-series||font-shape||2.Preliminaries> |.>>>>|> |2.1.Holonomic functions |.>>>>|> > |2.2.Fuchsian singularities |.>>>>|> > |2.3.Holonomic constants |.>>>>|> > |math-font-series||font-shape||3.Asymptotic expansions> |.>>>>|> |3.1.Decomposing Cauchy contour integrals into Mellin integrals |.>>>>|> > |3.2.Elementary Mellin integrals |.>>>>|> > |3.3.Effective local error bounds |.>>>>|> > |3.4.Asymptotic expansions with effective error bounds |.>>>>|> > |math-font-series||font-shape||4.Periodic or quasi-periodic cancellations> |.>>>>|> |4.1.Classical results for rational functions |.>>>>|> > |4.2.Removing resonance |.>>>>|> > |4.3.Quasi-resonance |.>>>>|> > |4.4.Asymptotic expansions |.>>>>|> > |math-font-series||font-shape||5.Uniformly fast evaluation> |.>>>>|> |5.1.Preliminaries |.>>>>|> > |5.2.Exact computation of the terms of a holonomic sequence |.>>>>|> > |5.3.Fast computation of floating point approximations |.>>>>|> > |math-font-series||font-shape||6.Positivity testing> |.>>>>|> |6.1.A density theorem for sequences |.>>>>|> > |6.2.Positivity testing |.>>>>|> > |math-font-series||font-shape||7.Fuchsian holonomic sequences> |.>>>>|> |7.1.Full Mellin integrals |.>>>>|> > |7.2.Canonical solutions via Mellin transforms |.>>>>|> > |7.3.Canonical formal solutions at infinity |.>>>>|> > |7.4.Transition matrices |.>>>>|> > |7.5.Transition matrices for sequences |.>>>>|> > |7.6.Transition matrices at infinity |.>>>>|> > |7.7.Analytic solutions to the difference equation |.>>>>|> > |math-font-series||font-shape||Bibliography> |.>>>>|>