Positivity Proofs for Linear Recurrences through Contracted Cones
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910740556808192 |
|---|---|
| author | Ibrahim, Alaa Salvy, Bruno |
| author_facet | Ibrahim, Alaa Salvy, Bruno |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_08576 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Positivity Proofs for Linear Recurrences through Contracted Cones Ibrahim, Alaa Salvy, Bruno Symbolic Computation 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. |
| title | Positivity Proofs for Linear Recurrences through Contracted Cones |
| topic | Symbolic Computation |
| url | https://arxiv.org/abs/2412.08576 |