Positivity Proofs for Linear Recurrences through Contracted Cones

Alaa Ibrahim and Bruno Salvy · 2024

Read Positivity Proofs for Linear Recurrences through Contracted Cones by Alaa Ibrahim and Bruno Salvy (2024) 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-2412-08576.txt.

Introduction

Alaa Ibrahim and Bruno Salvy give a way to prove that recurrence-made number lists stay positive, in a 2024 arXiv paper. Such lists grow by a rule that reuses past terms with polynomial weights. Telling if all terms stay above zero is hard in general. For fixed weights, a full answer is known only for short rules.

Their method works for a wide class of rules of any length. It builds a cone that the rule shrinks into itself, so positivity follows step by step. Starts outside one flat set can thus be proved positive. The cone build leans on a classic result on maps that keep a cone in place.

Catalog record

CREATORAlaa Ibrahim and Bruno Salvy
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-08576

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 through Contracted Cones Alaa Ibrahim and Bruno Salvy Abstract . Deciding the positivity of a sequence defined by a linear recurrence with polynomial coefficients and initial condition is difficult in general. Even in the case of recurrences with constant coefficients, it is known to be decidable only for order up to 5. We consider a large class of linear recurrences of arbitrary order, with polynomial coefficients, for which an algorithm decides positivity for initial conditions outside of a hyperplane. The underlying algorithm constructs a cone, contracted by the recurrence operator, that allows a proof of positivity by induction. The existence and construction of such cones relies on the extension of the classical Perron-Frobenius theory to matrices leaving a cone invariant. 1. Introduction A sequence (u_{n})_{n\in\mathbb{N}} of real numbers is called P-finite if it satisfies a linear recurrence (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] and p_{d}\neq 0 . The sequence is moreover called C-finite when the polynomials p_{i} are constant. The problem of positivity is to determine whether u_{n}\geq 0 for all n\in\mathbb{N} or not. When p_{d}(n)\neq 0 , Eq. 1 defines u_{n+d} in terms of the previous ones. As p_{d} can only have finitely many zeros, up to checking n_{0} elements of the sequence first and considering the shifted sequence v_{n}=u_{n+n_{0}} , one can assume without loss of generality that p_{d}(n)\neq 0 for all n\in\mathbb{N} and thus that the sequence is entirely determined by its initial conditions u_{0},\dots,u_{d-1} . By the same argument one can also assume that p_{0}(n)\neq 0 for all n\in\mathbb{N} , which is a hypothesis in our Theorem 1 . For reasons of effectivity, it is necessary to restrict to a subfield of \mathbb{R} . For simplicity, we state our algorithms and results over the rationals; real number fields can be handled similarly. Thus, we focus on the following. Definition 1 (Positivity problem for P-finite sequences) . Given p_{0},\dots,p_{d} in \mathbb{Q}[n] such that 0\not\in p_{0}p_{d}(\mathbb{N}) and given u_{0},\dots,u_{d-1} in \mathbb{Q} , decide whether the sequence (u_{n}) defined by Eq. 1 satisfies u_{n}\geq 0 for all n\geq 0 . P-finite and C-finite sequences are closed under addition, product, Cauchy product ((u_{n}),(v_{n}))\mapsto(\sum_{k=0}^{n}u_{k}v_{n-k}) and the operation of taking subsequences (u_{\ell n+q}) for fixed \ell\in\mathbb{N}_{>0} and q\in\mathbb{N} . These operations are all effective: algorithms produce recurrences for these sequences given recurrences for the input [ 34 , §6.4] . This implies that if (u_{n}) is a P-finite sequence, 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} ) are all problems that reduce to the positivity problem for P-finite sequences. For applications of the positivity problem of C-finite sequences, we refer to the numerous references in the work of Ouaknine and Worrell [ 26 ] . Motivations for studying positivity in the more general context of P-finite sequences also come from various areas of mathematics and its applications, including number theory [ 35 ] , combinatorics [ 32 ] , special function theory [ 29 ] , or even biology [ 21 , 40 , 2 ] . In computer science, the verification of loops allowing multiplication by the loop counter leads to P-finite sequences [ 12 , 13 ] . Positivity questions for such recurrences also occur in the floating-point error analysis of simple loops obtained by discretization of linear differential equations [ 1 ] and in the numerical stability of the computation of sums of convergent power series [ 33 ] . Several examples come from diagonals of multivariate rational functions (see for instance [ 5 ] ). This is the case of the sequence (2) s_{n}=\sum_{k=0}^{n}{(-27)^{n-k}2^{2k-n}\frac{(3k)!}{k!^{3}}\binom{k}{n-k}}, whose positivity was proved by Straub and Zudilin [ 35 ] using properties of hypergeometric series, but that can also be proved from the recurrence 2(n+2)^{2}s_{n+2}=(81n^{2}+243n+186)s_{n+1}-81(3n+2)(3n+4)s_{n}, although not in an immediate way. Also, a family of diagonals comes from the sequences (3) u_{n}^{(k)}=\sum_{j=0}^{n}(-1)^{j}\frac{(kn-(k-1)j)!k!^{j}}{(n-j)!^{k}j!} whose positivity for k\geq 4 was a long-standing conjecture by Gillis, Reznick and Zeilberger [ 10 ] , proved only recently by Yu [ 41 ] . In our setting, this gives a family of tests of increasing size, as the sequences (u_{n}^{(k)}) satisfy linear recurrences. Empirically, the k th one has order k and coefficients of degree k(k-1)/2 , see also [ 28 ] . Decidability Issues Even in the case of C-finite sequences (when the recurrences have constant coefficients), the positivity problem is not completely understood. If \chi(x)=x^{d}-\frac{p_{d-1}}{p_{d}}x^{d-1}-\dots-\frac{p_{0}}{p_{d}} is the characteristic polynomial of the recurrence and \lambda_{1},\dots,\lambda_{k} are its distinct roots, then it is classical that the solution takes the general form u_{n}=C_{1}(n)\lambda_{1}^{n}+\dots+C_{k}(n)\lambda_{k}^{n}, with polynomial C_{i} that can be computed from the initial conditions u_{0},\dots,u_{d} . Still, the positivity problem is difficult in this situation. It is only known to be decidable for order d\leq 5 and the case d=6 is related to open problems in Diophantine approximation [ 26 ] . Moreover, by the closure properties for sum and product, the famous Skolem problem , which asks whether a C-finite sequence has a 0 or not and is only known to be decidable for order d\leq 4 , reduces to the positivity problem (in higher order) [ 26 ] . For special classes of C-finite recurrences (simple, or reversible), positivity has been proved decidable for slightly larger order [ 20 , 17 , 19 ] . There is one subclass of C-finite recurrences of arbitrary order for which deciding the sign is easy: it is when one of the roots \lambda_{i} , say \lambda_{1} , dominates the other ones, in the sense that |\lambda_{1}|>|\lambda_{i}| for i\neq 1 and moreover the corresponding polynomial C_{1}(n) is not zero. Then asymptotically the term C_{1}(n)\lambda_{1}^{n} dominates u_{n} and one can bound effectively the other ones [ 25 ] . The work presented here is a generalization of this favorable situation in the case of polynomial coefficients. Previous Work In computer algebra, an important method was developed by Gerhold and Kauers [ 7 , 9 ] . The principle is to look for m such that the formula \forall n\geq 0,\forall u_{n}\geq 0,\forall u_{n+1}\geq 0,\dots,\forall u_{n+d-1}\geq 0,\\ u_{n+d}\geq 0\wedge\dotsb\wedge u_{n+m}\geq 0\Rightarrow u_{n+m+1}\geq 0 can be proved by quantifier elimination and to increase m until the method succeeds or a prescribed bound has been reached. While there is no guarantee of success in general [ 16 ] , this method is very powerful, giving for instance an automatic proof of Turán’s inequality for Legendre polynomials [ 8 ] . Kauers and Pillwein refined this method for the special case of P-finite sequences. In particular, they observed that it is easier to prove the stronger property \exists\mu>0,u_{i+1}\geq\mu u_{i} and proved termination of the method for cases with a unique dominant eigenvalue (see Definition 2 ) and order d=2 , under a genericity assumption on the initial conditions; they also extended their analysis to a subclass of recurrences of order d=3 [ 15 , 16 , 30 ] . For an appropriate choice of \mu , this is also sufficient to prove the positivity of the sequences ( 3 ) for k=4,\dots,17 [ 28 ] . Our approach can be viewed as extending this idea of introducing extra inequalities (the

Read the complete text