Positivity Proofs for Linear Recurrences with Several Dominant Eigenvalues

Alaa Ibrahim · 2025

Read Positivity Proofs for Linear Recurrences with Several Dominant Eigenvalues by Alaa Ibrahim (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-14264.txt.

Introduction

Alaa Ibrahim tackles the positivity question for a sequence defined by recurrences with varying coefficients in a 2025 paper. To tell whether such a sequence stays positive is notoriously hard. Even for the constant case the answer is known only up to order five. Trouble lies where several largest eigenvalues tie in size.

An earlier method builds one cone that the recurrence squeezes inward. It proves the claim when a single dominant eigenvalue rules. This paper swaps in a chain of cones, each mapped into the next. So induction can proceed without contraction. For several simple dominant eigenvalues, a stated condition makes sure the chain inclusions hold. Examples, including a double dominant eigenvalue, show the method at work. The result widens the class that can be certified to stay above zero.

Catalog record

CREATORAlaa Ibrahim
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-14264

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Positivity Proofs for Linear Recurrences with Several Dominant Eigenvalues Alaa Ibrahim Abstract . Deciding the positivity of a sequence defined by a linear recurrence and initial conditions is, in general, a hard problem. When the coefficients of the recurrences are constants, decidability has only been proven up to order 5. The difficulty arises when the characteristic polynomial of the recurrence has several roots of maximal modulus, called dominant roots of the recurrence. We study the positivity problem for recurrences with polynomial coefficients, focusing on sequences of Poincaré type, which are perturbations of constant-coefficient recurrences. The dominant eigenvalues of a recurrence in this class are the dominant roots of the associated constant-coefficient recurrence. Previously, we have proved the decidability of positivity for recurrences having a unique, simple, dominant eigenvalue, under a genericity assumption. The associated algorithm proves positivity by constructing a positive cone contracted by the recurrence operator. We extend this cone-based approach to a larger class of recurrences, where a contracted cone may no longer exist. The main idea is to construct a sequence of cones. Each cone in this sequence is mapped by the recurrence operator to the next. This construction can be applied to prove positivity by induction. For recurrences with several simple dominant eigenvalues, we provide a condition that ensures that these successive inclusions hold. Additionally, we demonstrate the applicability of our method through examples, including recurrences with a double dominant eigenvalue. Conference: International Symposium on Symbolic and Algebraic Computation; 2025; Guanajuato, Mexico International Symposium on Symbolic and Algebraic Computation (ISSAC ’25), 2025, Guanajuato, Mexico 1. Introduction A sequence (u_{n})_{n\in\mathbb{N}} of real numbers is called P-finite of order d if it satisfies a linear recurrence of the form (1) p_{d}(n)u_{n+d}=p_{d-1}(n)u_{n+d-1}+\dots+p_{0}(n)u_{n},\qquad n\in\mathbb{N}, with coefficients p_{i}\in\mathbb{R}[n] . The sequence (u_{n})_{n} is said to be positive if each term of the sequence is non-negative, i.e., u_{n}\geq 0 for all ~n\in\mathbb{N} . When the coefficients p_{i} are constants in \mathbb{R} , the sequence is called C-finite. In this work, we take the assumption 0\not\in p_{d}(\mathbb{N}) . Then, the sequence is completely defined by the recurrence relation and the first d terms of the sequence, (u_{0},u_{1},\dots,u_{d-1}) . The Positivity Problem consists in deciding whether a sequence (u_{n})_{n} is positive, given the polynomials (p_{i})_{i=1}^{d} and initial conditions. In this work, we consider the positivity problem over rationals: p_{i}\in\mathbb{Q}[n] and (u_{0},\dots,u_{d-1})\in\mathbb{Q}^{d} . For instance, the following inequality on hypergeometric functions ( 1 ) f(x)={}_{2}F_{1}(\frac{1}{2},\frac{1}{2};1;x^{2})-(1+x)~{}_{2}F_{1}(\frac{1}{2},\frac{1}{2};1;x)\geq 0,~x\in(0,1), follows from the positivity of the coefficients (a_{n})_{n} of the Taylor expansion of f(x)=\sum_{n\geq 0}a_{n}x^{n} . Thus, proving the inequality reduces to deciding the positivity of a P-finite sequence whose order can be further reduced to 2, as shown in Section 7 . This reduction is partially due to closure properties of P-finite sequences under addition, product and Cauchy product. Furthermore, for any \ell\in\mathbb{N}_{>0} and q\in\{0,\dots,\ell-1\} , the subsequence (u_{\ell n+q})_{n\in\mathbb{N}} satisfies a linear recurrence of order at most d . All these operations are effective, meaning that recurrences for the resulting sequences can be computed given recurrences for the input ( 26 ) . Thus, various problems can be reduced to positivity. For example, proving monotonicity ( u_{n+1}\geq u_{n} ), convexity ( u_{n+1}+u_{n-1}\geq 2u_{n} ), log-convexity ( u_{n+1}u_{n-1}\geq u_{n}^{2} ) or more generally an inequality with another P-finite sequence ( u_{n}\geq v_{n} ), can be interpreted as instances of the positivity problem. Moreover, the reduction of the famous Skolem problem to Positivity ( 12 ) highlights the hardness of the positivity problem. The Positivity Problem arises in multiple domains. In mathematics, it appears in numerous inequalities within combinatorics ( 19 , 24 ) , number theory ( 27 ) and the theory of special functions ( 22 ) . In computer science, positivity occurs in several areas such as the study of numerical stability in computations involving sums of power series ( 25 ) and the verification of loop termination ( 9 , 10 ) . Other applications can be found in floating-point error analysis ( 2 ) and in biology ( 17 , 29 , 3 ) . Decidability: The dominant eigenvalues of the recurrence play a fundamental role in deciding positivity. For C-finite sequences, the starting point for proving positivity is the closed-form expression of the sequence. Given the characteristic polynomial of the recurrence \chi(x)=x^{d}-\frac{p_{d-1}}{p_{d}}x^{d-1}-\dots-\frac{p_{0}}{p_{d}}, with distinct roots \lambda_{1},\dots,\lambda_{k} , it is well known that the sequence takes the form u_{n}=C_{1}(n)\lambda_{1}^{n}+\dots+C_{k}(n)\lambda_{k}^{n}, where each C_{i}(n) is a polynomial determined by the initial conditions u_{0},\dots,u_{d-1} . In this representation, the roots \lambda_{i} with the largest modulus govern the asymptotic behavior of the sequence; they are also called the dominant eigenvalues . In all previous works, deciding positivity for C-finite sequences has been addressed through discussions on the dominant eigenvalues. First, Ouaknine and Worrell proved the decidability for recurrences of order up to 5. This limitation is related to the number of dominant eigenvalues. Furthermore, for d=6 positivity is reduced to open problems in Diophantine approximation ( 21 ) . For C-finite recurrences with one dominant eigenvalue, decidability is established for arbitrary order. Moreover, when the characteristic polynomial of the sequence does not have multiple roots, decidability extends to order up to 9 ( 20 ) . For reversible recurrences of integers (reversible means that unrolling the recurrence backwards produces only integers for negative indices), decidability of positivity is known for order up to 11 and this goes up to 17 if the recurrence is both reversible and with square-free characteristic polynomial ( 16 ) . In summary, even in the case of C-finite sequences, the positivity problem is not fully understood. Moreover, for P-finite sequences, the situation is further complicated since their is no “simple” basis of solutions, and it is difficult to relate the asymptotic behavior of the sequence with its initial conditions even for small orders ( 15 ) . Previous works: In a very general setting, including P-finite sequences, the first algorithmic work is due to Gerhold and Kauers ( 6 ) . Their method consists in looking iteratively for the first integer m such that the following implication holds u_{n}\geq 0\wedge u_{n+1}\geq 0\wedge\dots\wedge u_{n+m}\geq 0\Rightarrow u_{n+m+1}=\sum_{i=0}^{m}q_{i}(n)u_{n+i}\geq 0. This implication is handled as a decision problem in the existential theory of the reals, and it is tested using cylindrical algebraic decomposition ( 5 ) . This method leads to automatic proofs for many important inequalities ( 7 ) , though the termination of this procedure remains unclear. Later, Kauers and Pillwein have adapted that method to control its termination for P-finite sequences. Positivity is concluded by proving u_{n+1}>\beta u_{n} for some positive \beta using the same approach ( 13 , 14 ) . This yields the decidability for recurrences of order d=2 , with a unique simple dominant eigenvalue , under a genericity assumption on the initial conditions. Under the same constraints, decidability also extends to a subclass of recurrences of order d=3 ( 23 ) . More recently, this decidability result was extended to arbitrary order using a cone-based approach. For recurrences having a unique simple dominant eigenvalue, positivity is proven, generically , by constructing a positive cone contracted by the recurrence operator ( 11 ) . Later, the construction of the cone was refined using the theory of Perron-Frobenius for cones ( 12

Read the complete text