Abstract 1 Introduction 2 Results 3 Proof of the Results References

The Ultimate Signs of Second-Order Holonomic Sequences

Fugen Hagihara ORCID Graduate School of Science, Kyoto University, Japan Akitoshi Kawamura Research Institute for Mathematical Sciences, Kyoto University, Japan
Abstract

A real-valued sequence f={f(n)}n is said to be second-order holonomic if it satisfies a linear recurrence f(n+2)=P(n)f(n+1)+Q(n)f(n) for all sufficiently large n, where P,Q(x) are rational functions. We study the ultimate sign of such a sequence, i.e., the repeated pattern that the signs of f(n) follow for sufficiently large n. For each P, Q we determine all ultimate signs that f can have, and show how they partition the space of initial values of f. This completes the prior work by Neumann, Ouaknine and Worrell, who have settled some restricted cases. As a corollary, it follows that when P, Q have rational coefficients, f either has an ultimate sign of length 1, 2, 3, 4, 6, 8 or 12, or never falls into a repeated sign pattern. We also give a partial algorithm that finds the ultimate sign of f (or tells that there is none) in almost all cases.

Keywords and phrases:
Holonomic sequences, ultimate signs, Skolem Problem, Positivity Problem
Category:
Track B: Automata, Logic, Semantics, and Theory of Programming
Copyright and License:
[Uncaptioned image] © Fugen Hagihara and Akitoshi Kawamura; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Mathematics of computing Discrete mathematics
Acknowledgements:
We thank Kohki Baku at Faculty of Science, Kyoto University, for helping us find the explicit formula (8) in Example 5. We also thank the anonymous referees for knowledgeable comments, which helped us clarify the explanation on previous works and our results.
Funding:
This work was supported by JSPS KAKENHI Grant Numbers JP18H03203, JP23K28036, JP25KJ1559 and by JST SPRING Grant Number JPMJSP2110.
Related Version:
Full Version: https://arxiv.org/abs/2506.14751
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

Let ={0,1,2,} be the set of all natural numbers. A sequence f={f(n)}n of real numbers is called a holonomic sequence (of order r) if there are real-coefficient rational functions P0,,Pr1(x) such that f satisfies the linear recurrence

f(n+r)=Pr1(n)f(n+r1)++P0(n)f(n) (1)

for all sufficiently large n. Holonomic sequences arise in various areas of mathematics [4]. For example, solutions of linear differential equations with polynomial coefficients are generating functions of holonomic sequences [25], and for a “proper hypergeometric term” F(n,k), which consists of binomials (nk) and so on, the sum f(n)=kF(n,k) is holonomic if it converges for all n [21].

An important computational problem about holonomic sequences is the Ultimate Sign Problem [16]: Given (rational-coefficient) rational functions P0,,Pr1(x) without poles in and (rational-valued) initial values f(0), …, f(r1), find an ultimate sign, defined as follows, of the unique sequence f having these initial values and satisfying (1) for all n, and an index N at which this ultimate sign is reached. Although we assume that f satisfies the recurrence (1) not only for nI for some I but also for all n, it is not different in computability from the problem of finding the ultimate sign and the index N from the coefficients P0,,Pr1, initial values f(I), …, f(I+r1) and I.

Definition 1.

A sequence f is said to have an ultimate sign (s0,,sτ1){+,,0} at N if sgnf(n)=snmodτ for all nN, where sgn:{+,,0} is the function that maps each real number to its sign.

For instance, the sequence {(1)n(n2)}n=2,1,0,1,2,3, has the ultimate sign (+,) at 3. Note that if f has the ultimate sign s at N, then it also has any repetition of s as an ultimate sign, and it does so at any index N; but we could of course ask for the shortest ultimate sign s and the least index N without changing the computability of the problem.

The Ultimate Sign Problem is a generalization of several important problems about signs of holonomic sequences. One of the most famous problems is the Skolem Problem, which asks whether f(n)=0 for some n. (We note that this reduces to the Ultimate Sign Problem by a similar discussion in [19, § 4].) Its decidability has been studied for almost 90 years [7]. Positivity Problem asking whether f(n)>0 for all n and Ultimate Positivity Problem asking whether f has the ultimate sign (+) are also famous and applied to automated inequality proving [6]; see also subsequent works [9, 22, 23] and a SageMath implementation [18].

When the coefficients P0,,Pr1 are constant, f is called a C-finite sequence (or a linear recurrence sequence). Skolem Problem for C-finite sequences with order r4 [26, 27] and (Ultimate) Positivity Problem for C-finite sequences with order r5 [20] are known to be decidable, whereas the decidability for higher order C-finite sequences is open.

For holonomic sequences, when r=1 (i.e., when f is a hypergeometric sequence), the Ultimate Sign Problem is easy since for given P0(x), an index N such that P0(n) has a constant sign for nN can be effectively computed. When r=2, i.e., when f satisfies the recurrence of form

f(n+2)=P(n)f(n+1)+Q(n)f(n), (2)

the decidability of Skolem and (Ultimate) Positivity Problem for some subclasses is known in the context of the Membership Problem [17] and the Threshold Problem [10], respectively. [16, Theorem 7] shows that the Ultimate Sign Problem for another subclass is computable. However, the computability for general second-order holonomic sequences is not known. To make a progress on this open problem, we study the ultimate signs of all second-order holonomic sequences.

Our first main contribution is to classify all pairs (P,Q)(x)2 by the ultimate signs f can have, and show how the ultimate signs partition the space of initial values of f (Theorem 4). This result resolves all remaining cases in [16, Theorem 1], which handles the restricted case where P, Q are polynomials, P is non-constant and degQdegP. In addition, this result implies that when P, Q have rational coefficients, the shortest ultimate sign of f, if it has one, is either of length 1, 2, 3, 4, 6, 8 or 12 (Corollary 6).

Our second contribution is to give a partial algorithm that solves the Ultimate Sign Problem for second-order holonomic sequences and halts on almost all input (Theorem 10). This is an extension of [16, Theorem 3] that handles the restricted case mentioned above. This result can be also stated as a reduction theorem: for second-order holonomic sequences, the Ultimate Sign Problem Turing-reduces to the Minimality Problem, which asks the minimality of a given f, i.e., whether f(n)/g(n)0 for all linearly independent solution g of the same recurrence. In this sense this result extends [11], which shows that the Positivity Problem Turing-reduces to the Minimality Problem. Note that, unfortunately, the decidability of Minimality Problem is unknown whereas many researchers numerically calculate minimal holonomic sequences and apply them to numerical analysis of some special functions (for example [5, 3]).

As a byproduct of our arguments, we found and amended some gaps in the proof of [16], slightly modifying its Theorem 7. We discuss this in Section 2.3.

Related work

A lot of previous works describe their results in terms of continued fractions, which have a strong connection to second-order holonomic sequences. We illustrate the connection between those works and one of our main theorems in Sections 2.1.1 and 2.1.2.

Not only the ultimate sign, but also other periodicities of signs of holonomic (or C-finite) sequences are investigated. Closely related to the Skolem Problem, the periodicity of the zeros of C-finite (and for some holonomic) sequences is well-known as the Skolem-Mahler-Lech theorem [2]. Almagor et al. [1] give some sufficient conditions for C-finite sequences to have an “almost periodic sign”, a loose property of sign periodicity.

Kooman [13] studies the asymptotic behaviour of complex solutions of the recurrence (2), where P and Q are not necessarily rational functions. His results helped us see the big picture of our main theorems.

2 Results

The Ultimate Sign Problem asks about the ultimate signs of f that satisfies (2) for all n. Such f is identified by the coefficient pair (P,Q) and the initial value (f(0),f(1)).

Definition 2.

Let P, Q(x) be rational functions without poles in . A sequence f is (P,Q)-holonomic if it satisfies (2). The pair (f(0),f(1))2 is called the initial value of f.

The Ultimate Sign Problem for (0,Q)- or (P,0)-holonomic sequences is easy, so we assume P0 and Q0. By shifting the index by finitely many terms, we may assume that P, Q have no zeros in . This shifting changes the ultimate sign and the initial value of f in such a simple way that it does not affect the computability of the Ultimate Sign Problem. We adopt this assumption in all the following theorems.

2.1 Ultimate signs

Our first main theorem lists the ultimate signs that (P,Q)-holonomic sequences f can have, and shows how the ultimate signs partition the space of initial values of f for each of the following types (Definition 3) of (P,Q). For R(x){0}, let degR denote d satisfying |R(x)|=Θ(xd) and call the ultimate sign of {R(n)}n that of R.

Definition 3.

We classify (P,Q)((x){0})2 into the following types. Let d:=degQ(x)P(x)P(x1) and (s)(s{+,}) be the ultimate sign of Q(x)P(x)P(x1).

  • If s=+ and d>2, then we say that (P,Q) is of -O loxodromic type.

  • If s=+ and d2, then we say that (P,Q) is of -Ω loxodromic type.

  • If s= and d0, then let α0,α1,α2 be real numbers satisfying

    Q(x)P(x)P(x1)=α0+α1x+α2x2+O(x3). (3)
    • If (α0,α1,α2)(14,0,116) in lexicographic order, then we say that (P,Q) is of hyperbolic type.

    • Otherwise, α014, so there is a real number θ[0,12) such that α0=14cos2θπ.

      1. (1)

        If θ is a positive rational number and α1=0, then we say that (P,Q) is of θ-O elliptic type.

      2. (2)

        Otherwise, we treat (P,Q) together with the next case.

  • If s= and d=1,2, or it is the case of (2) above, then we say that (P,Q) is of -Ω elliptic type.

  • If s= and d3, then we say that (P,Q) is of 12-O elliptic type.

This classification consists of the distinctions between loxodromic type (-O loxodromic type and -Ω loxodromic type), hyperbolic type and elliptic type (θ-O elliptic type and -Ω elliptic type), and between O type (-O loxodromic type and θ-O elliptic type) and Ω type (-Ω loxodromic type and -Ω elliptic type).

The terminologies of “O” and “Ω” come from big O and Ω notations. They represent whether Q(x)P(x)P(x1) is near or apart from a certain value ( for loxodromic type, 14cos2θπ for θ-O elliptic type and 14cos2qπ with any q(0,12] for -Ω elliptic type).

The terminologies of loxodromic, hyperbolic and elliptic come from the classification of linear fractional transformations. If P and Q are constant, the linear fractional transformation z1P+Qz maps the ratio f(n)/f(n+1) between the two neighbouring terms of the (P,Q)-holonomic sequence to the next ratio f(n+1)/f(n+2), and is said to be elliptic, parabolic, hyperbolic and loxodromic when QP2 is in (,14), {14}, (14,0) and (0,), respectively (with slight variations among authors – some (cf. [14, §4.1.3]) treat hyperbolic as a subclass of loxodromic, while some (cf. [24, § 4.7]) treat loxodromic as a subclass of hyperbolic).

This classification is a little complicated, but considering the case of constant P, Q, it is reasonable that the boundary between hyperbolic type and elliptic type is about 14 and that θ-O elliptic type and -Ω elliptic type are distinguished in such a way. If P and Q are constant, we can explicitly solve the recurrence (2) for f:

f(n)={αnαβ(f(1)βf(0))+βnαβ(f(1)+αf(0))ifαβ,nαn(α1f(1)f(0))+αnf(0)ifα=β, (4)

where α and β are the roots of the quadratic polynomial x2PxQ. When QP214, we have α,β and f has an ultimate sign of length 1 or 2. On the other hand, when QP2<14, the roots α and β are conjugate imaginary numbers. Then we can rewrite the formula (4) into f(n)=Arnsin(nθπ+B), where A,B,r are constants independent of n and θ(0,12) is a constant satisfying QP2=14cos2θπ. f has an ultimate sign of length τ for τ(4) such that τθ2 if θ, whereas f has no ultimate signs if θ. Our first main result (Theorem 4) is an extension of this fact, although we do not have explicit formulas like (4) for non-constant P, Q.

Since the set IP,Q(s) of initial values (f(0),f(1)) leading f to the ultimate sign s is closed under linear combinations with positive coefficients, it is a convex linear cone and thus specified by an (open, closed or half-open) interval p(IP,Q(s)) on the unit circle S1, where

p:2{(0,0)}S1;(x,y)(x,y)/x2+y2 (5)

is the projection. Thus, we will state the theorem by describing how S1 is partitioned into intervals p(IP,Q(s)). It is also obvious that flipping the sign of the initial value flips each element of the ultimate sign, so that IP,Q(s) is just IP,Q(s) flipped around the origin.

We omit the parentheses and write IP,Q(+,), say, for IP,Q((+,)).

Rather than considering all P,Q(x), we state the theorem assuming the ultimate sign of P is (+) because otherwise the ultimate sign of f can be obtained easily from that of the (P,Q)-holonomic sequence {(1)nf(n)}n with initial value (f(0),f(1)).

Theorem 4.

Let P, Q(x) be rational functions without zeros or poles in , and suppose that the ultimate sign of P is (+). For each s{+,,0}, we write p(IP,Q(s)) for the set of f0S1 such that the (P,Q)-holonomic sequence with initial value f0 has the ultimate sign s.

  1. (I)

    If (P,Q) is of -O loxodromic type, S1 is partitioned into closed intervals
    p(IP,Q(+,)), p(IP,Q(,+)) which have non-empty interiors and non-empty open intervals p(IP,Q(+)), p(IP,Q()).

  2. (II)

    If (P,Q) is of -Ω loxodromic type, S1 is partitioned into singletons p(IP,Q(+,)),
    p(IP,Q(,+)) and non-empty open intervals p(IP,Q(+)), p(IP,Q()).

  3. (III)

    If (P,Q) is of hyperbolic type, S1 is partitioned into half-open intervals p(IP,Q(+)), p(IP,Q()).

  4. (IV)

    If (P,Q) is of kr-O elliptic type, where r and k are coprime positive integers, let

    sj =(sgnsinjik+0.5rπ)i=0,,2r1, tj =(sgnsinjikrπ)i=0,,2r1 (6)

    for each j=0, …, 2r1.

    • If Q(x)P(x)P(x1) is constant, S1 is partitioned into p(IP,Q(t0)), p(IP,Q(s0)),,p(IP,Q(t2r1)), p(IP,Q(s2r1)), arranged in this order (clockwise or anticlockwise), of which p(IP,Q(tj)) are singletons and p(IP,Q(sj)) are non-empty open intervals.

    • Otherwise, S1 is partitioned into non-empty half-open intervals p(IP,Q(s0)),,p(IP,Q(s2r1)), arranged in this order, where for each j=0, …, 2r1, the intersection of the closures of p(IP,Q(sj)) and p(IP,Q(sj+1)) (where s2r=s0) belongs to p(IP,Q(sj+1)) if Q(x)P(x)P(x1) is eventually increasing, and to p(IP,Q(sj)) if it is eventually decreasing.

  5. (V)

    If (P,Q) is of -Ω elliptic type, then no non-zero (P,Q)-holonomic sequence has an ultimate sign.

In Part (IV), the value 0.5 can be replaced by any value between 0 and 1. If (P,Q) is of 12-O elliptic type, then Q(x)P(x)P(x1) necessarily decreases eventually.

In Parts (I), (II), (III) and (IV), the union of the boundaries of the sets I(s) is a finite union of lines. Following [16], which handles restricted cases of (II) and (III) with degQ(x)P(x)P(x1)1, we call these lines the critical lines.

Example 5.

Let P(x)=x+2x+1 and Q(x)=x+3x+1, so that Q(x)P(x)P(x1)=1+2x2+3x+2 is decreasing and (P,Q) is 13-O elliptic. Part (IV) of Theorem 4 states that non-zero (P,Q)-holonomic sequences f in this case have ultimate signs

s0 =(+,,,,+,+), s1 =(+,+,,,,+), s2 =(+,+,+,,,),
s3 =(,+,+,+,,), s4 =(,,+,+,+,), ors5 =(,,,+,+,+), (7)

and that the set IP,Q(sj) of initial values that result in each ultimate sign sj is the area between two halves of critical lines and includes the boundary facing IP,Q(sj+1) (where we write s6=s0). For this particular example, we can verify this by finding IP,Q(sj) explicitly, as we see by induction n that the solution of (2) is

f(n)={(1)m((72m+1)f(0)mf(1))ifn=3m,(1)m(mf(0)+(m+1)f(1))ifn=3m+1,(1)m+1((52m+3)f(0)2(m+1)f(1))ifn=3m+2, (8)

so that IP,Q(s0), …, IP,Q(s5) are as depicted in Figure 1.

Figure 1: The set of initial values (f(0),f(1)) of (x+2x+1,x+3x+1)-holonomic sequences f having each of the ultimate signs in (5).

Restricting Theorem 4 to rational-coefficient (P,Q), we obtain the following:

Corollary 6.

Suppose that P, Q(x) have no zeros or poles in . Then every (P,Q)-holonomic sequence has an ultimate sign of length 1, 2, 3, 4, 6, 8 or 12, if it has an ultimate sign at all.

Proof.

We may assume that P has the ultimate sign (+), because, as mentioned immediately before Theorem 4, a (P,Q)-holonomic sequence f for P having () can be written as f={(1)nf(n)}n for a (P,Q)-holonomic sequence f, and hence, if f has ultimate sign of length τ, f has an ultimate sign of length τ if τ is even, and 2τ if τ is odd.

Of the five cases in Theorem 4, the only one that does not immediately imply our claim is (IV), namely when (P,Q) is of kr-O elliptic type for some coprime positive integers r and k. If (r,k)=(2,1), we are done. Otherwise, 14cos2krπ=limxQ(x)P(x)P(x1). Since cos2krπ=12(cos2krπ+1), we have cos2krπ, and thus cos2rπ since r and k are coprime. The corollary follows from (a version of) Niven’s theorem, which states that the only possibilities for such r are 2, 3, 4, 6, since f will then have an ultimate sign of length 2r{4,6,8,12} by (IV).

We can derive from Theorem 4 another corollary (Corollary 20 in Section 3.2). Appropriate subsequences of second-order holonomic sequences are again second-order holonomic sequences. That corollary describes the types of the coefficients of the recurrence which the subsequences satisfy.

2.1.1 Connection to continued fractions

In this section, we discuss the connection between Theorem 4 and continued fractions

Kk=0nQ(k)P(k)=Q(0)P(0)+Q(1)P(1)++Q(n)P(n)

with some important previous works. Note that continued fractions take values in ^={} with x/=0 for x and x/0= for x{0}. See [14] about their deep theory and application . Continued fractions are closely related to second-order holonomic sequences through the next proposition, which can be verified by induction on n (simultaneously for all P and Q):

Proposition 7.

Let P,Q(x) have no poles in and A and B be the (P,Q)-holonomic sequences with initial values (1,0) and (0,1) respectively. Then

Kk=0nQ(k)P(k)=A(n+2)B(n+2) (9)

in ^ for all n.

For this reason, A(n) and B(n) are called the nth canonical numerator and denominator, respectively. We explain that Theorem 4 can be interpreted as a convergence theorem of subsequences {p(A(n),B(n))}ni(modτ), i=0,,τ1, of p(A(n),B(n)) where p is the projection (5) and τ1 is a suitable integer below.

All (P,Q)-holonomic sequences f satisfy

f(n)=A(n)f(0)+B(n)f(1)=A(n)2+B(n)2p(A(n),B(n))(f(0),f(1)). (10)

Let τ be 2, 1, 1, 2r in Theorem 4 (I), (II), (III), (IV) respectively. Then the the set Ii(+) of initial values of f such that {f(n)}ni(modτ) has the ultimate sign (+) is a half plane on 2. It follows from Equation 10 that {p(A(n),B(n))}ni(modτ) converges to the midpoint of the interval p(Ii(+)). Similarly, it can be derived that, for any τ1, one of {p(A(n),B(n))}ni(modτ) must diverge in the case of Theorem 4 (V). In this sense, Theorem 4 is a convergence theorem of p(A(n),B(n)).

By the discussion above, the slopes of critical lines can be represented by the limits of {Kk=0nQ(k)P(k)}ni(modτ)={A(n)B(n)}ni(modτ), i=0,,τ1, and thus the convergence of subsequences of Kk=0nQ(k)P(k) follows.

Theorem 8.

Let P, Q(x) be rational functions without zeros or poles in . First, in Part (I), (II), (III) and (IV) of Theorem 4, the slopes of critical lines are exactly the accumulation points of the continued fraction {Kk=0nQ(k)P(k)}n. Second, the accumulation of the continued fraction is:

  1. (1)

    If (P,Q) is of -O loxodromic type, the subsequences {Kk=0nQ(k)P(k)}ni(mod2), i=0, 1, converge in ^ to distinct values.

  2. (2)

    If (P,Q) is of -Ω loxodromic or hyperbolic type, the sequence {Kk=0nQ(k)P(k)}n converges in ^.

  3. (3)

    If (P,Q) is of kr-O elliptic type, where r and k are coprime positive integers, the sequences {Kk=0nQ(k)P(k)}ni(modr), i=0, …, r1, converge in ^ to distinct values.

  4. (4)

    If (P,Q) is of -Ω elliptic type, then for no positive integer τ and no i{0,,τ1} does the sequence {Kk=0nQ(k)P(k)}ni(modτ) converge in ^.

Part (1) of this theorem is included in [14, Theorems 3.12 and 3.13]. Part (3) is similar to [14, Lemma 4.28]. Part (2) can be derived from the following well-known convergence theorem. Although Parts (1), (2) and (3) follow from Theorem 4, Part (4) does not follow from it alone since it states divergence instead of convergence. We prove (4) in a full version of this paper using the convergence theorem below and Corollary 20 (2) (in Section 3.2), which is derived from Theorem 4.

Theorem 9 ( [12, Theorem 7.1]).

Let P, Q(x) be rational functions without zeros or poles in . The continued fraction {Kk=0nQ(k)P(k)}n converges in ^ if and only if (P,Q) is of -Ω loxodromic or hyperbolic type.

2.1.2 Connection to monotonic convergence of continued fractions

If we identify the ultimate sign of B, we can extend the convergence of subsequences of A(n)B(n) to that of p(A(n),B(n)). But this is not enough to prove each part of Theorem 4. Since it even describes the ultimate signs of holonomic sequences with initial values on the critical lines, it figures out not only the convergence of subsequences of p(A(n),B(n)), but also from which direction the subsequences of p(A(n),B(n)) converge to their limits. To obtain this detailed information, we need monotonic convergence theorems of subsequences of continued fractions rather than simple convergence theorems.

[14, Theorems 3.12 and 3.13] and [11, Lemma 3.4] are monotonic convergence theorems for (P,Q) of -O, -Ω loxodromic type and of hyperbolic type, respectively, and both literature identify the ultimate sign of B in their case. Hence Theorem 4 (I) and (II) can be derived from the former literature, and (III) can be derived from the latter.

2.2 Computing the ultimate sign

The partial algorithm in the following theorem tells us, for given (P,Q)(x)2 and f02, the index N at which the (P,Q)-holonomic sequence with initial value f0, whenever it terminates. Note that once we get N, we can obtain the ultimate sign itself by looking at the signs of a finite number of terms f(N), f(N+1), …according to Theorem 4.

Theorem 10.

There exists a partial algorithm that,

  • given P,Q(x) without zeros or poles in , together with a pair f02,

  • terminates if and only if the (P,Q)-holonomic sequence f with initial value f0 has an ultimate sign and it is stable in the sense that there is a neighbourhood 𝒩2 of f0 such that all (P,Q)-holonomic sequences with initial value in 𝒩 have the same ultimate sign, and

  • whenever it terminates, outputs an index at which f has its ultimate sign.

Note that the type of (P,Q) can be computed from P and Q, and hence, although the partial algorithm does not terminate when f0=(0,0) or when (P,Q) is -Ω elliptic (because of Theorem 4 (V)), we could make it terminate also on these inputs and declare the non-existence of an ultimate sign in the latter case.

This partial algorithm terminates on “most” inputs since, for (P,Q) of -O, -Ω loxodromic, hyperbolic and θ-O type, the (P,Q)-holonomic sequence f with initial value f0 has an unstable ultimate sign if and only if f0 is on the finitely many critical lines delimiting the areas IP,Q(s) in Theorem 4. For a small but substantial class of (P,Q), it is known that all f02{(0,0)} lead f to a stable ultimate sign, or in terms of critical lines, the slopes of the critical lines are irrational, which is the main topic of Section 2.3. However there is no known general method to determine whether f has a stable ultimate sign, or in other words, whether a given f02 is on the critical lines, even though we obtained representations of their slopes in Theorem 8. Hence it is a wide-open problem whether we can make the algorithm terminate on all inputs [11, 8, 16].

Theorem 10 is stated for rational-coefficient P, Q and rational-valued f0, so that the problem is computationally meaningful. By studying the proofs in some detail we could, however, modify the statement appropriately so that the partial algorithm accepts inputs involving real numbers presented as infinite sequences of approximations, in a way analogous to the discussion in [15] about signs of C-finite sequences.

Example 11.

Let us compare the values of the sums

0kn+12,k2k(n+1kk)and0kn+12,k2+1k(n+1kk)

using the partial algorithm in Theorem 10. It suffices to identify the ultimate sign of the difference f(n):=k=0(n+1)/2(1)kk(n+1kk) of the two sums and at which index f has it. By creative telescoping [21, Chapter 6], we find that f is the (P,Q)-holonomic sequence with initial value (0,1), where (P,Q) is as in Example 5. Now we can input this into our partial algorithm and it tells that f has the ultimate sign (+,,,,+,+) at 1, i.e., when n1, the former sum is greater than and less than the latter sum if n0,4,5(mod6) and if n1,2,3(mod6), respectively.

Unlike the above case, for the same (P,Q), the partial algorithm never terminates with initial values on the critical lines in Figure 1, such as (1,1), (4,5) and (2,7).

Let us consider another example: compare

0kn,k2k(nk)3and0kn,k2+1k(nk)3.

Taking a similar process, we find that the difference g(n):=k=0n(1)kk(nk)3 is the (R,S)-holonomic sequence with initial value (0,1), where

(R(x),S(x))=(18x2+36x+12(x+1)(x+2)(6x2+4x+1),3(3x+2)(3x+1)(6x2+16x+11)(x+1)(x+2)(6x2+4x+1)).

Note that (R,S) is of 12-O elliptic type. Our partial algorithm proves that g has the ultimate sign (+,,,+) at 1, i.e., when n1, the former sum is greater than and less than the latter sum if n0,3(mod4) and if n1,2(mod4), respectively.

However, for this (R,S), we do not know how to identify the critical lines. Algorithm Hyper [21, Chapter 8] declared that there is no explicit formula like (8) (more precisely, “closed form”). By numerical analysis using our partial algorithm, we find that the slope of the critical line between IR,S(+,,,+) and IR,S(+,+,,) is in the interval (2.452,2.434), and the one between IR,S(+,+,,) and IR,S(,+,+,) is in (4.8094,4.816).

Theorem 10 can be described in a reduction form:

Theorem 12.

For second-order holonomic sequences, the Ultimate Sign Problem Turing-reduces to the Minimality Problem.

2.3 Input set admitting a total algorithm

The main predecessor to our work [16, Theorem 1, 3 and 7] relies on a lemma [16, Lemma 14] whose proof contained an error in the calculation of an inverse image. Their classification and the partial algorithm [16, Theorem 1 and 3] analogous to our Theorems 4 and 10 are correct after all, as our theorems imply. In this section, we state Theorem 13, an amendment of [16, Theorem 7]. Note that our theorem is slightly weaker than the original one due to one more gap in the proof. We mention this in detail after proving Theorem 13 in Section 3.3.

Theorem 13 gives a sufficient condition on P,Q(x) for all non-zero (P,Q)-holonomic sequences f{0} to have a stable ultimate sign. This gives a nontrivial input set on which the Ultimate Sign Problem is solvable by the partial algorithm in Theorem 10.

The restriction of P and Q to [x] instead of (x) is no essential loss of generality: For P, Q(x), we can let P1,P2,Q1,Q2[x] be such that P=P1P2 and Q=Q1Q2 and apply the theorem on P and Q, where P(x)=P1(x+1)Q2(x+1) and Q(x)=Q1(x+1)Q2(x)P2(x+1)P2(x), because the ultimate sign of a (P,Q)-holonomic sequences f is stable if that of the (P,Q)-holonomic sequence {f(n+1)k=0n1P2(k)Q2(k)}n is stable.

Theorem 13.

Let P(x)=p0xd+p1xd1++pd[x] and Q(x)=q0xd+q1xd1++qd[x] be polynomials without zeros in . Suppose that p0>0 and d1 ( where q0 might be zero). Then, if P and Q satisfy either of the following condition, any (P,Q)-holonomic sequences f{0} have a stable ultimate sign.

  1. (1)

    |q0|<p0

  2. (2)

    |q0|=p0 and the two conditions below hold for s:=sgnq0{1,1}:

    • Q(x)sP(x)1 in [x],

    • {sq1p1s<p0if d=1,sq1p1<p0if d2.

3 Proof of the Results

In this section, we prove our results. For the lemmas used in this section, we provide only some explanation. See a full version of this paper for the whole proof.

3.1 Proof of Theorem 4

Let us first focus on identifying the lengths of the ultimate signs that (P,Q)-holonomic sequences can have and get an overview of the proof of Theorem 4. Lemmas 14 and 15 below, by types of (P,Q), characterize (P,Q) admitting (P,Q)-holonomic sequences with ultimate signs of lengths 1 and 2, respectively. Then only lengths τ3 are left. For each τ3, we will introduce a special recurrence such that we can decide if F satisfying the recurrence has a (shortest) ultimate sign of length τ (Lemma 16). Next, by types of (P,Q), we characterize (P,Q) and τ admitting that all (P,Q)-holonomic sequences f can be transformed to F satisfying the special recurrence and having the same ultimate sign as f (Lemma 18). Finally we show that, for the other (P,Q) and τ3, any non-zero (P,Q)-holonomic sequences do not have the shortest ultimate sign of length τ in the proof of Theorem 4 (V). Note that some lemmas below are excessive in identifying the length of ultimate signs, but required to identify the ultimate signs themselves and how they partition the space of the initial values.

Lemma 14.

Let P,Q(x) have no zeros or poles in and P have the ultimate sign (+).

  1. (1)

    IP,Q(+) (P,Q) is of loxodromic type or hyperbolic type.

  2. (2)

    If (P,Q) is of hyperbolic type, then IP,Q(+)IP,Q()=2{(0,0)}.

Similar results to the above lemma appear in, e.g., [11].

The following lemma is relatively easy and similar propositions appear in context of continued fractions.

Lemma 15.

Let P,Q(x) have no zeros or poles in and P have the ultimate sign (+).

  1. (1)

    IP,Q(+,) (P,Q) is of loxodromic type.

  2. (2)

    p(IP,Q(+,)) is a closed interval.

  3. (3)

    If (P,Q) is of loxodromic type, then IP,Q(+)IP,Q()IP,Q(+,)IP,Q(,+)=2{(0,0)}.

A part of the proof.

Let us show only (1). () If a (P,Q)-holonomic sequence f has the ultimate sign (+,), then Q has (+) by comparing the signs of three terms in the recurrence (2). () Let In be the set of initial values ((0,0)) with which the (P,Q)-holonomic sequence f satisfies f(2n)0 and f(2n+1)0. Since p(In) is a closed interval that shrinks as n, we have p(IP,Q(+,))=np(In), where p is the projection (5).

Now we introduce the special recurrence mentioned in the first paragraph of this section. For a (not necessarily holonomic) sequence F, consider a single-term-feedback recurrence

F(n+τ)F(n)=R(n)F(n+1), (11)

where τ is an integer 2 and R. This recurrence expresses the difference between two neighbouring terms in the gap-τ subsequences {F(n)}ni(modτ), i=0,,τ1, as a single term in the next subsequence {F(n)}ni+1(modτ) multiplied by the coefficient R. By the discussion below the next lemma, F has an ultimate sign of length τ if |R(n)| rapidly decreases (specifically, R(n)=O(n1ε) for some ε>0), and does not have one (except for repetition of an ultimate sign of length 2) if |R(n)| does not rapidly decrease (specifically, |R(n)|=Ω(n1)) and R has an ultimate sign (+) or ().

Lemma 16.

Let F satisfy the single-term-feedback recurrence (11) for a coefficient R and an integer τ2.

  1. (1)

    (restricted case of [12, Theorem 6]) Suppose R(n)=O(n1ε) for some ε>0.

    1. (1a)

      Each of the gap-τ subsequences {F(n)}ni(modτ), i=0,,τ1, converges.

    2. (1b)

      If F0, then there is i{0,,τ1} for which {F(n)}ni(modτ) does not converge to 0.

  2. (2)

    Suppose that |R(n)|=Ω(n1) and R has an ultimate sign (+) or (). If F has an ultimate sign of length τ, then F also has an ultimate sign of length 2.

  3. (3)

    Suppose that R has an ultimate sign (q), q{+,,0}. Let i{0,,τ1}. If a subsequence {F(n)}ni+1(modτ) of F has the ultimate sign (s), s{+,,0} and {F(n)}ni(modτ) converges to 0, then {F(n)}ni(modτ) has the ultimate sign (qs).

Summary of the proof.

(1) We give only an intuitive explanation. By the recurrence (11), we have

(F(n+2τ1)F(n+τ))=(I+MR(n))(F(n+τ1)F(n)),

where I is the identity matrix and MR(n) is a matrix with MR(n)=O(n1ε) in some norms. Then n=0(I+MR(n)) seems to converge to a regular matrix by the analogy of convergence of n=0(1+r(n)) with r(n)=O(n1ε). The statement follows from this convergence.

(3) By the recurrence (11), you can find that {F(n)}ni(modτ) is eventually increasing, eventually decreasing or constant. Then it has (), (+) or (0), respectively.

(2) By comparing the signs of three terms of the recurrence (11), each {F(n)}ni(modτ) is eventually monotonic if f has an ultimate sign of length τ. Let its limit αi{±}. Since |R(n)|=Ω(n1), it follows that α0==ατ1=0 or α0,,ατ1{±}. A discussion of increasing or decreasing as in the proof of (3) leads to the conclusion.

If |R(n)| rapidly decreases (i.e., in the case of (1)), F has an ultimate sign of length τ as follows. If F=0, it is obvious. If F0, then by (1a) and (1b), there is i such that {F(n)}ni(modτ) has ultimate sign (+) or () . Then {F(n)}ni1(modτ) also has (+) or () if it converges to a non-zero real number. This is true even if it converges to zero by (3). Thus, by induction, every gap-τ subsequence of F has ultimate sign of length 1, meaning that F has an ultimate sign of length τ. On the other hand, if |R(n)| does not rapidly decrease (and τ3), F does not have the shortest ultimate sign of length τ3 by (2).

Part (1) of Lemma 16 is known for a larger class of recurrences [12, Theorem 6]. Our restriction to the single-term-feedback recurrence allows (2) and (3) to hold.

Now we want to find a sequence T with ultimate sign (+) and a sequence R, such that for each (P,Q)-holonomic sequence f, the transformed sequence F(n):=T(n)f(n) satisfies the recurrence (11). Note that f and F have the same ultimate sign if and only if T has (+). To find T and R, we use A(τ),B(τ)(x) below.

Definition 17.

For P,Q(x) without zeros or poles in , there uniquely exist A(τ),B(τ)(x) such that any (P,Q)-holonomic sequences f satisfy the recurrence

f(n+τ)=B(τ)(n)f(n+1)+A(τ)(n)f(n) (12)

for all n. Let us call A(τ) and B(τ) the generalized τth canonical numerator and denominator (of (P,Q)) respectively.

These are generalizations of the notions of τth canonical numerator A and denominator B in Proposition 7 since (A(τ)(0),B(τ)(0))=(A(τ),B(τ)). We can generalize Equation 9 to Kk=nn+τQ(k)P(k)=A(τ+2)(n)B(τ+2)(n). Equation 12 is a generalization of the equation f(τ)=B(τ)f(1)+A(τ)f(0) that A and B satisfy for any (P,Q)-holonomic sequence f.

Let τ2 and T,R. For each n, by Equation 12, F(n)=T(n)f(n) satisfy Equation 11 for all (P,Q)-holonomic sequences f if and only if

T(n+τ)A(τ)(n)=T(n),R(n)T(n+1)=B(τ)(n)T(n+τ). (13)

To allow T to have the ultimate sign (+), we want A(τ) to have (+). In addition, to apply Lemma 16 (1) for F(n)=T(n)f(n), the absolute value of the coefficient |R(n)| has to decrease rapidly. The lemma below shows that there exists τ satisfying these conditions if and only if (P,Q) is of O type.

Lemma 18.

Let P,Q(x) have no zeros or poles in , and P have the ultimate sign (+). Let τ2 be an integer and A(τ) and B(τ) be the τth generalized canonical numerator and denominator, respectively.

  1. (1)

    Assume that T,R satisfy (13) and T(n)0 for all sufficiently large n. Then |T(n+1)T(n)|=Θ(|A(τ)(n)|1/τ). Especially, |R(n)|=Θ(|B(τ)(n)||A(τ)(n)|1+1/τ).

  2. (2)

    The following are equivalent.

    1. (2a)

      A(τ) has the ultimate sign (+) and |B(τ)(n)|A(τ)(n)1+1/τ=O(n1ε) for some ε>0.

    2. (2b)

      (P,Q) is of θ-O elliptic type and τθ2, or (P,Q) is of -O loxodromic type and τ2.

A summary of the proof.

(1) This is intuitively correct by the left equation of (13).

(2) We can check A(τ)(x)=Q(x)B(τ1)(x+1) by a simple calculation, so it suffices to determine degB(τ) and the ultimate sign of B(τ). Find a recurrence that the sequence {B(τ)}τ satisfies. Then you can explicitly obtain bτ:=limxB(τ)(x) for any τ by solving the recurrence after letting x. Moreover, you can explicitly obtain cτ(x) such that limxcτ(x)=0 and B(τ)(x)=bτ+cτ(x)+O(x1cτ(x)). Now we know degB(τ) and the ultimate sign of B(τ) even in the case of bτ=0.

Now we are ready to show Theorem 4.

Proof of Theorem 4 (I) and (II).

By Lemma 14, it remains to prove that p(IP,Q(+,)) has width if (P,Q) is of -O loxodromic type and does not if (P,Q) is of -Ω loxodromic type. In other words, we should prove the existence of a (P,Q)-holonomic sequence with the stable ultimate sign (+,) in the former case and the non-existence in the latter case.

Define T,R as they satisfy T(n),R(n)>0 and Equation 13 with τ=2 for all sufficiently large n (Note that A(2)=Q and B(2)=P). Then, for all (P,Q)-holonomic sequences f and sufficiently large n, the transformed sequences F(n):=T(n)f(n) satisfy the single-term-feedback recurrence (11) with τ=2, i.e.

F(n+2)F(n)=R(n)F(n+1). (14)

Since A(2)(n)=Q(n)>0 for all sufficiently large n, (1) and (2) of Lemma 18 implies R(n)=O(n1ε) for some ε>0 if (P,Q) is of -O loxodromic type and R(n)=Ω(n1) if (P,Q) is of -Ω loxodromic type.

If (P,Q) is of -O loxodromic type and so R(n)=O(n1ε), we can define a linear map L that maps a (P,Q)-holonomic sequence f to

L(f):=(limn0(mod2),nT(n)f(n),limn1(mod2),nT(n)f(n))2

by Lemma 16 (1a). By Lemma 16 (1b), L is injective. Since the domain and range of L are both two-dimensional, L is bijective. Hence, for example, L1(1,1) is a (P,Q)-holonomic sequence that has the stable ultimate sign (+,).

If (P,Q) is of -Ω loxodromic type, take a (P,Q)-holonomic sequence f that has the ultimate sign (+,). Let us show that this is unstable. It suffices to show that T(n)f(n)=O(1) and limnT(n)g(n)= where g is a (P,Q)-holonomic sequence having (+) (because it follows that, for any δ{0}, the perturbations f+δg of f have the ultimate sign (+)). For all sufficiently large n, since R(n)>0 and F(n)=T(n)f(n) satisfies Equation 14, F(2n)(>0) is monotonically decreasing and F(2n+1)(<0) is monotonically increasing. So F(n)=O(1). On the other hand, F(n):=T(n)g(n)(>0), a sequence satisfying the same recurrence, eventually increasing. Especially F(n)=Ω(1). Since R(n)=Ω(n1), we have F(n+2)F(n)=Ω(n1). Thus limnF(n)=.

Proof of Theorem 4 (III).

IP,Q(+), IP,Q() are both connected and IP,Q(+)=IP,Q(). The statement follows from this and Lemma 14 (2).

Proof of Theorem 4 (V).

Suppose, for a contradiction, that a non-zero (P,Q)-holonomic sequence f has an ultimate sign (s0,,sτ1).

Let τ3 first. Let A(τ) and B(τ) be the generalized τth canonical numerator and denominator. It follows from Lemma 18 (2) that A(τ) has the ultimate sign (+) or (0), or that |B(τ)(n)|A(τ)(n)1+1/τ=Ω(n1). Let us first consider the former case. Let (b)(b{+,,0}) be the ultimate sign of B(τ). By Equation 12 we have si=bsi+1 for all i=0,,τ1, where sτ:=s0, and so f has an ultimate sign of length 2. Next, let us consider the case where A(τ) has () and |B(τ)(n)||A(τ)(n)|1+1/τ=Ω(n1). In this case we can choose T,R satisfying T(n)>0 and the relation (13) for all sufficiently large n, and we have |R(n)|=Ω(n1). The transformed sequence F(n):=T(n)f(n) satisfies the recurrence (11) for all sufficiently large n. It follows from Lemma 16 (2) that F has an ultimate sign of length 2, and so does f.

Now it suffices to consider the case τ=1,2. By Lemma 14 (1) and Lemma 15 (1), f does not have ultimate signs of length 1 or 2.

It remains to show (IV). Let (P,Q) be of θ-O elliptic type. As already mentioned, for τ such that τθ2, all (P,Q)-holonomic sequences f have ultimate signs of length τ. Now we need to find which ultimate signs (of length τ) f can have. This will be derived from the lemma below.

Lemma 19.

Take (P,Q) as in Lemma 18 and assume that it is of kr-O elliptic type.

  1. (1)

    The generalized 2rth canonical denominator B(2r) has the ultimate sign (+) if Q(x)P(x)P(x1) is eventually increasing, () if eventually decreasing, and (0) if constant, respectively.

  2. (2)

    By Lemma 18 (2), we can choose T such that T(n)>0 and the relation (13) with τ=2r hold for all sufficiently large n. Then, for each j=0,,τ1, there exists a (P,Q)-holonomic f(j) such that for all i{0,,τ1}, {T(n)f(j)(n)}ni(mod2r) converges to a real number of sign sgnsinjikrπ.

Proof of Theorem 4 (IV).

Take T and f(0),,f(2r1) as in Lemma 19 (2). Let f(2r):=f(0). (P,Q)-holonomic sequences of the form f=af(j)+bf(j+1)(a,b>0) have the ultimate sign sj since {T(n)f(n)}ni(mod2r)(i=0,,2r1) converge to a real number of sign sgnsinjik+0.5rπ. Then we have {initial values of af(j)+bf(j+1)a,b>0}IP,Q(sj). It remains to prove that f(j) has the ultimate sign sj if Q(x)P(x)P(x1) is eventually increasing, sj1 if eventually decreasing and tj if constant, respectively.

For i,j{0,,2r1} and q{0,±1}, let ui,j,q:=sgnsinjik+q/2rπ. Then what we want to prove is that f(j) has the ultimate sign (ui,j,q)i=0,,2r1, where (sgnq) is the ultimate sign of B(2r) in Lemma 19 (1). We will show that the subsequence {T(n)f(j)(n)}ni(mod2r) has the ultimate sign ui,j,q for each i.

If jik0(modr), then this subsequence converges to a real number of sign ui,j,0(0). Therefore it has the ultimate sign (ui,j,0)=(ui,j,q). If jik0(modr), then this subsequence converges to 0. Define R by the relation (13). R has the ultimate sign (sgnq) and F(n)=T(n)f(j)(n) satisfies (11). It follows from Lemma 16 (3) that this subsequence has the ultimate sign (sgnqui+1,j,0)=(sgnq(1)jikr)=(ui,j,q).

3.2 Proof of Theorems 10 and 12

Theorems 10 and 12 are algorithmic claims stating that the ultimate signs classified in Theorem 4 can be partially computed in each sense. We could prove them by analyzing the proof of Theorem 4 quantitatively. But instead of carrying out such analysis for all cases of Theorem 4 separately, we choose to do so just for the hyperbolic type (Lemma 21 below), and argue that all other types (having ultimate signs) reduce to it in the sense of the following Corollary 20.

From the original recurrence (2), we can obtain, for each positive integer τ, a “gap-τ recurrence”

f(n+2τ)=Pτ(n)f(n+τ)+Qτ(n)f(n), (15)

where Pτ and Qτ are rational functions. Specifically, they can be written as

Pτ =B(2τ)B(τ), Qτ =A(2τ)B(2τ)B(τ)A(τ) (16)

using the generalized canonical numerators A(0), A(1), …and denominators B(0), B(1), …for (P,Q) (see Definition 17), assuming that B(τ) is non-zero (note that if B(τ)=0, we have f(n+τ)=A(τ)(n)f(n), in which case the ultimate sign of f can be found easily). Thus, the subsequence {f(τn+N)}n of f, for any number N greater than all zeros of B(τ), is the (Pτ(τx+N),Qτ(τx+N))-holonomic sequence with initial value (f(N),f(N+τ)). The following corollary to Theorem 4 says that with a right choice of τ, this (Pτ(τx+N),Qτ(τx+N)) is of hyperbolic type, unless (P,Q) is of -Ω elliptic type.

Corollary 20.

Suppose that P, Q(x) have no zeros or poles in . Let A(0), A(1), …and B(0), B(1), …be the generalized canonical numerators and denominators, respectively.

  1. (1)

    Suppose that (P,Q) is either of loxodromic type or of kr-O elliptic type for some coprime positive integers r and k. Let τ=2 in the former case, and τ=2r in the latter case. Suppose that B(τ) and B(2τ) are non-zero. Then Pτ and Qτ defined by (16) are non-zero, and (Pτ(τx+N),Qτ(τx+N)) is of hyperbolic type for all N.

  2. (2)

    Suppose that (P,Q) is of -Ω elliptic type. Then B(τ) is non-zero, Pτ and Qτ defined by (16) are also non-zero, and (Pτ(τx+N),Qτ(τx+N)) is of -Ω elliptic type for all N and τ1.

Proof.

(1) Pτ0 by B(2τ)0, and Qτ0 by B(τ)0. Since the type of (Pτ(τx+N),Qτ(τx+N)) does not depend on N, it suffices to prove this corollary only for N which is larger than any zeros and poles of Pτ, Qτ, B(τ). Since B(τ)(N)0, the dimension of {(f(N),f(N+τ))f is a (P,Q)-holonomic sequence} is 2. Therefore when f runs on the set of all (P,Q)-holonomic sequences, {f(τn+N)}n runs on the set of all (Pτ(τx+N),Qτ(τx+N))-holonomic sequences. By Theorem 4, any {f(τn+N)}n has an ultimate sign (+), (), or (0). Hence, again by Theorem 4, (Pτ(τx+N),Qτ(τx+N)) is of hyperbolic type.

(2) By Theorem 4 (V), no non-zero (P,Q)-holonomic sequence has any ultimate sign. Therefore B(τ)0 for any τ. Since the type of (Pτ(τx+N),Qτ(τx+N)) does not depend on N, it suffices to prove this corollary for one N. Non-zero (P,Q)-holonomic sequences do not have ultimate signs, so there exists at least one N such that the subsequence {f(τn+N)}n does not have any ultimate signs. Therefore Pτ,Qτ0, and it follows from Theorem 4 that (Pτ(τx+N),Qτ(τx+N)) is of -Ω elliptic type.

Lemma 21 (A quantitative version of Lemma 14).

Let P,Q(x) have no zeros or poles in .

  1. (1)

    The following are equivalent.

    1. (1a)

      (P,Q) is of loxodromic or hyperbolic type.

    2. (1b)

      There exists q with ultimate sign (+) that satisfies

      q(n)(1q(n+1))Q(n)P(n)P(n1) (17)

      for all sufficiently large n.

  2. (2)

    If (1b) holds, then it holds with the sequence q defined by q(0)=q(1)=1 and q(n)=12+14n+14nlogn, n2.

  3. (3)

    Let (P,Q) be of hyperbolic type and P have the ultimate sign (+). Take any q in (1b). Take N such that P, q, Q have the ultimate sign at N and the condition (17) is satisfied for any nN. Let f be a (P,Q)-holonomic sequence. Then if

    f(n)0 and f(n+1)f(n)>q(n)P(n1) (18)

    holds for some nN, this condition also holds for n+1,n+2,. Especially, f has an ultimate sign (+) or () at n.

The sequence q in Lemma 21 (2) is what appears in the proof of [11, Lemma 3.4].

Proof of Theorem 10.

The desired partial algorithm simply diverges when the input (P,Q) is of -Ω elliptic type. For the input (P,Q) of hyperbolic type together with f02, define q as in Lemma 21 (2) and execute the following procedure:

  1. 1.

    If P has the ultimate sign (), then write f0=(a,b), and let P:=P and f0:=(a,b).

  2. 2.

    Calculate any N as in Lemma 21 (3).

  3. 3.

    Let f be the (P,Q)-holonomic sequence with initial value f0. For n=N,N+1,, check the condition (18), and if it is satisfied then output n.

Let us show that if this procedure halts, then the output is correct and the (P,Q)-holonomic sequence f with initial value f0 has a stable ultimate sign. Without loss of generality, we can assume that P has the ultimate sign (+). It follows from Lemma 21 (3) that f has an ultimate sign at the output n when the procedure halts. Moreover, since sgnf(n) and the condition (18) for each n are robust under small perturbations of the initial value of f, the ultimate sign of f is stable.

Conversely, let us assume that the (P,Q)-holonomic sequence f with initial value f0 has a stable ultimate sign. By Lemma 14 (2), f has (+) or (). Without loss of generality, we can assume it is (+). Let N be the one obtained in step 2 of the procedure with input P, Q, f0. It follows from the stability of the ultimate sign of f that there exists a (P,Q)-holonomic sequence g such that

  • g(N)>0,

  • g satisfies the condition (18) for n=N, where f is replaced by g,

  • A small perturbation fg of (the initial value of) f has the same ultimate sign (+) as f.

We want to show that F(n):=g(n)/k=Nn1q(k)P(k1)(n) since then we have limnf(n)/k=Nn1q(k)P(k1)= and the condition (18) holds for some n. By the assumption of g and Lemma 21 (3), g (and so F) has the ultimate sign (+) at N. The recurrence of g as a (P,Q)-holonomic sequence and the condition (17) yeild that F(n+2)F(n+1)(q(n+1)11)(F(n+1)F(n)) for all nN. Note F(N+1)F(N)>0. Then we have F(n+2)F(n+1)=Ω(k=0n(q(k+1)11)). Since q(k+1)11=11k1klogk+O(k2), it follows that k=0n(q(k+1)11)=Θ(1nlogn). (Herein we used k=2n(1+αk+βklogk)=Θ(nα(logn)β) for arbitrary a,b.) Thus F(n+2)F(n+1)=Ω(1nlogn), and so F(n)=Ω(loglogn), which proves F(n).

Finally, when the input (P,Q) is of loxodromic type or kr-O elliptic type, define τ as in Corollary 20. If the τth generalized canonical denominator B(τ) or the 2τth one B(2τ) is 0, it is easy to make our partial algorithm behave as in Theorem 10. Assume that B(τ),B(2τ)0, and define Pτ, Qτ as in Corollary 20. Let N0 be larger than any poles of Pτ and Qτ. Since all (Pτ(τx+N),Qτ(τx+N)) for N=N0,,N0+τ1 are of hyperbolic type, we can execute the aforementioned procedure with inputs (Pτ(τx+N),Qτ(τx+N)) and (f(N),f(N+τ)) for each N, which each halts if and only if {f(τn+N)}n has a stable ultimate sign of length 1. All of these τ executions thus halt if and only if f has a stable ultimate sign of length τ.

Proof of Theorem 12.

Take inputs f02 and (P,Q)(x)2 for the Ultimate Sign Problem for second-order holonomic sequences. Let f be the (P,Q)-holonomic sequence with initial value f0. Without loss of generality, we can assume that P, Q are non-zero, (P,Q) is not of -Ω type and f0(0,0) (otherwise the problem is easy). We can also assume that P, Q have no zeros in . As in the proof of Theorem 10, we only have to consider the case of (P,Q) of hyperbolic type, by taking a suitable subsequence.

Assume that one has an oracle for the Minimality Problem for second-order holonomic sequences. This oracle tells us whether f has an unstable ultimate sign, since it is equivalent to the minimality of f for (P,Q) of hyperbolic type.

If f has a stable ultimate sign, execute the partial algorithm in Theorem 10. If f has an unstable ultimate sign, take q as in Lemma 21 (2), and calculate and output N of (3) in the same lemma. Let us show that this output is correct. If f(n)=0 for some nN, then f(n+1)0 and f(n+2)f(n+1)=P(n)>q(n+1)P(n), which is the condition (18) for n+1. This implies that f has a stable ultimate sign at n+1, which is a contradiction. If f has no zeros N and satisfies f(n+1)f(n)<0 for some nN, then f(n+2)f(n+1)=P(n)+Q(n)f(n)f(n+1)>P(n)>q(n+1)P(n), resulting in the same as above. Thus, f(n+1)f(n)>0 for all nN.

3.3 Proof of Theorem 13

Let us take (P,Q)-holonomic sequence g whose ultimate sign is unstable, and show g=0. Since by assumption degQ(x)P(x)P(x1)1, (P,Q) is of -Ω loxodromic type or hyperbolic type. This implies, by Theorem 4, the set of all (P,Q)-holonomic sequences f whose ultimate signs are unstable forms a one-dimensional linear subspace in the linear space of all (P,Q)-holonomic sequences. Therefore f(n+1) and f(n) must satisfy a linear relation as shown below. To keep the statement simple, let R(x):=Q(x)P(x)P(x1) and consider (1,R)-holonomic sequence f(n)=g(n)P(n1)P(1) with an unstable ultimate sign instead of g.

Lemma 22.

Let R(x) have no zeros or poles in and satisfy degR1. Then, for all sufficiently large n, there exists h(n)[1R(n+1)3R(n+1)2,1R(n+1)+3R(n+1)2] such that any (1,R)-holonomic sequences f whose ultimate sign is unstable satisfy the relation

f(n+1)=R(n)h(n)f(n). (19)

The relation (19) corresponds to the equation (6) in [16], which is derived from [16, Lemma 14], whose proof contains a gap. Without using that lemma, we can show Lemma 22 by using Theorem 4 and some lemmas used to prove Theorem 4. See a full version of this paper for a complete proof.

A summary of the proof of Lemma 22.

Let A(0), A(1), …and B(0),B(1), be the generalized canonical numerators and denominators of (1,R). Let f be a (1,R)-holonomic sequence whose ultimate sign is unstable. We can check A(τ)(x)=R(x)B(τ1)(x+1) by a simple calculation. Then, dividing Equation 12 (with its Q replaced by R) by B(τ)(n), we obtain f(n+τ)B(τ)(n)=f(n+1)+R(n)B(τ1)(n+1)B(τ)(n)f(n). Hence showing the existence and estimate of

h(n):=limτB(τ1)(n+1)B(τ)(n) (20)

and limτf(n+τ)B(τ)(n)=0 completes this proof.

Since we investigated B(τ) in the proof of Lemma 18, we can establish the existence and estimate of h(n).

To show limτf(n+τ)B(τ)(n)=0, we use (II) and (III) of Theorem 4, degR(n)1 and the recurrence (2) (with its Q replaced by R).

We are now ready to prove Theorem 13.

Proof of Theorem 13.

Without loss of generality, we can assume P(1)0. Let us take g is a (P,Q)-holonomic sequence whose ultimate sign is unstable, and show g=0. By multiplying a positive integer by the initial value of g, we assume g. By applying Lemma 22 to R(x):=Q(x)P(x)P(x1) and f(n):=g(n)P(n2)P(1), we obtain

g(n+1)=Q(n)h(n)P(n)g(n). (21)

(1) |Q(n)h(n)P(n)|<1 holds for all sufficiently large n since limnh(n)=1. Then |g(n+1)|<|g(n)| or g(n)=0, which leads to g(n)=0 for sufficiently large n. Q has no natural number zeros, so g=0.

(2) Let us first show g(n)/n0. Since h(n)=1Q(n+1)P(n+1)P(n)+O(n2), the absolute value of the coefficient in (21) is estimated as

|Q(n)|h(n)P(n)=1+|Q(n)|P(n)|Q(n)|Q(n+1)P(n+1)P(n)P(n)+O(n2).

If d=1, then this estimate turns out to be 1+sq1p1sp0n1+O(n2), and if d2, then 1+sq1p1p0n1+O(n2). Since k=1n(1+αk1+O(k2))=O(nα) for all α, it follows from (21) that

g(n)={O(nsq1p1sp0)(d=1)O(nsq1p1p0)(d2).

By the assumption on p0, p1, q1, we have g(n)/n0.

Since g(n)/n0 and d1, it follows that 0=limng(n+2)/nd=limn(P(n)g(n+1)+Q(n)g(n))/nd=limn(p0g(n+1)+q0g(n)). Since p0g(n+1)+q0g(n), we have p0g(n+1)+q0g(n)=0 for all sufficiently large n. Then g(n+1)=sg(n) follows from this and sq0=p0. Substituting this in (2), we get g=0, by the assumption of Q(x)sP(x)1.

This proof is essentially same as the original one in [16, § 3.3]. However, the assumption of the theorem is changed from sq1p1s<3p0 (if d=1) and sq1p1<(d+2)p0 (if d2) to our stronger one in order to fill in the gap on top of page 13 in [16] as shown in the last paragraph of the proof above.

References

  • [1] Shaull Almagor, Toghrul Karimov, Edon Kelmendi, Joël Ouaknine, and James Worrell. Deciding ω-regular properties on linear recurrence sequences. Proceedings of the ACM on Programming Languages, 5(POPL):1–24, January 2021. doi:10.1145/3434329.
  • [2] Jason P. Bell, Stanley N. Burris, and Karen Yeats. On the set of zero coefficients of a function satisfying a linear differential equation. Mathematical Proceedings of the Cambridge Philosophical Society, 153(2):235–247, September 2012. doi:10.1017/S0305004112000114.
  • [3] Alfredo Deaño, Javier Segura, and Nico M. Temme. Computational properties of three-term recurrence relations for Kummer functions. Journal of Computational and Applied Mathematics, 233(6):1505–1510, January 2010. doi:10.1016/j.cam.2008.03.051.
  • [4] Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge Univ. Press, Cambridge, 4th pr edition, 2013.
  • [5] Walter Gautschi. Computational aspects of three-term recurrence relations. SIAM Review, 9(1):24–82, 1967. doi:10.1137/1009002.
  • [6] Stefan Gerhold and Manuel Kauers. A procedure for proving special function inequalities involving a discrete parameter. In Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation - ISSAC ’05, pages 156–162, Beijing, China, 2005. ACM Press. doi:10.1145/1073884.1073907.
  • [7] Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki. Skolem’s problem - on the border between decidability and undecidability. Technical Report 683, Turku Centre for Computer Science, 2005.
  • [8] Alaa Ibrahim and Bruno Salvy. Positivity certificates for linear recurrences. In David P. Woodruff, editor, Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 982–994. Society for Industrial and Applied Mathematics, 2024.
  • [9] Manuel Kauers and Veronika Pillwein. When can we detect that a P-finite sequence is positive? In Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation - ISSAC ’10, page 195, Munich, Germany, 2010. ACM Press. doi:10.1145/1837934.1837974.
  • [10] George Kenison. The threshold problem for hypergeometric sequences with quadratic parameters. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (Lipics), pages 145:1–145:20, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2024.145.
  • [11] George Kenison, Oleksiy Klurman, Engel Lefaucheux, Florian Luca, Pieter Moree, Joël Ouaknine, Markus A. Whiteland, and James Worrell. On positivity and minimality for second-order holonomic sequences. In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 67:1–67:15, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.MFCS.2021.67.
  • [12] Robert J. Kooman. Convergence Properties of Recurrence Sequences. Number 83 in CWI Tract. Centrum voor Wiskunde en Informatica, Amsterdam, 1991.
  • [13] Robert-Jan Kooman. An asymptotic formula for solutions of linear second-order difference equations with regularly behaving coefficients. Journal of Difference Equations and Applications, 13(11):1037–1049, November 2007. doi:10.1080/10236190701414462.
  • [14] Lisa Lorentzen and Haakon Waadeland. Continued Fractions. Atlantis Studies in Mathematics for Engineering and Science. North-Holland ; World Scientific, Amsterdam : [Singapore ; Hackensack, NJ], 2nd ed edition, 2008.
  • [15] Eike Neumann. Decision problems for linear recurrences involving arbitrary real numbers. Logical Methods in Computer Science, Volume 17, Issue 3:6880, August 2021. doi:10.46298/lmcs-17(3:16)2021.
  • [16] Eike Neumann, Joël Ouaknine, and James Worrell. Decision problems for second-order holonomic recurrences. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 99:1–99:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2021.99.
  • [17] Klara Nosan, Amaury Pouly, Mahsa Shirmohammadi, and James Worrell. The Membership Problem for Hypergeometric Sequences with Rational Parameters. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, pages 381–389, Villeneuve-d’Ascq France, July 2022. ACM. doi:10.1145/3476446.3535504.
  • [18] Philipp Nuspl. C-finite and C2-finite Sequences in SageMath. Technical report, Research Institute for Symbolic Computation (RISC), Johannes Kepler University Linz, June 2022. doi:10.35011/RISC.22-06.
  • [19] Joël Ouaknine and James Worrell. Decision problems for linear recurrence sequences. In Alain Finkel, Jérôme Leroux, and Igor Potapov, editors, Reachability Problems, pages 21–28, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. doi:10.1007/978-3-642-33512-9_3.
  • [20] Joël Ouaknine and James Worrell. Positivity Problems for Low-Order Linear Recurrence Sequences. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 366–379. Society for Industrial and Applied Mathematics, January 2014. doi:10.1137/1.9781611973402.27.
  • [21] Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger. A=B. A K Peters, Wellesley, Mass, 1996.
  • [22] Veronika Pillwein. Termination conditions for positivity proving procedures. In Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, pages 315–322, Boston Maine USA, June 2013. ACM. doi:10.1145/2465506.2465945.
  • [23] Veronika Pillwein and Miriam Schussler. An efficient procedure deciding positivity for a class of holonomic functions. ACM Communications in Computer Algebra, 49(3):90–93, November 2015. doi:10.1145/2850449.2850458.
  • [24] John G. Ratcliffe. Foundations of Hyperbolic Manifolds, volume 149 of Graduate Texts in Mathematics. Springer International Publishing, Cham, 2019. doi:10.1007/978-3-030-31597-9.
  • [25] R. P. Stanley. Differentiably Finite Power Series. European Journal of Combinatorics, 1(2):175–188, 1980. doi:10.1016/S0195-6698(80)80051-5.
  • [26] Mignotte Tijdeman, R. The distance between terms of an algebraic recurrence sequence. Journal für die reine und angewandte Mathematik, 349:63–76, 1984.
  • [27] N. K. Vereshchagin. Occurrence of zero in a linear recursive sequence. Mathematical Notes of the Academy of Sciences of the USSR, 38(2):609–615, August 1985. doi:10.1007/BF01156238.