On positivity and minimality for second-order holonomic sequences
An infinite sequence ⟨u_n⟩_n of real numbers is holonomic (also known as P-recursive or P-finite) if it satisfies a linear recurrence relation with polynomial coefficients. Such a sequence is said to be positive if each u_n ≥ 0, and minimal if, given any other linearly independent sequence ⟨v_n⟩_n s...
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2021
|
| _version_ | 1797110906319011840 |
|---|---|
| author | Kenison, G Klurman, O Lefaucheux, E Luca, F Moree, P Ouaknine, J Whiteland, MA Worrell, J |
| author_facet | Kenison, G Klurman, O Lefaucheux, E Luca, F Moree, P Ouaknine, J Whiteland, MA Worrell, J |
| author_sort | Kenison, G |
| collection | OXFORD |
| description | An infinite sequence ⟨u_n⟩_n of real numbers is holonomic (also known as P-recursive or P-finite) if it satisfies a linear recurrence relation with polynomial coefficients. Such a sequence is said to be positive if each u_n ≥ 0, and minimal if, given any other linearly independent sequence ⟨v_n⟩_n satisfying the same recurrence relation, the ratio u_n/v_n → 0 as n → ∞.
<br>
In this paper we give a Turing reduction of the problem of deciding positivity of second-order holonomic sequences to that of deciding minimality of such sequences. More specifically, we give a procedure for determining positivity of second-order holonomic sequences that terminates in all but an exceptional number of cases, and we show that in these exceptional cases positivity can be determined using an oracle for deciding minimality.
|
| first_indexed | 2024-03-07T08:01:18Z |
| format | Conference item |
| id | oxford-uuid:ef030a64-babd-45f2-920b-94c31151f17c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:01:18Z |
| publishDate | 2021 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:ef030a64-babd-45f2-920b-94c31151f17c2023-09-26T16:01:50ZOn positivity and minimality for second-order holonomic sequencesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:ef030a64-babd-45f2-920b-94c31151f17cEnglishSymplectic ElementsSchloss Dagstuhl - Leibniz-Zentrum für Informatik2021Kenison, GKlurman, OLefaucheux, ELuca, FMoree, POuaknine, JWhiteland, MAWorrell, JAn infinite sequence ⟨u_n⟩_n of real numbers is holonomic (also known as P-recursive or P-finite) if it satisfies a linear recurrence relation with polynomial coefficients. Such a sequence is said to be positive if each u_n ≥ 0, and minimal if, given any other linearly independent sequence ⟨v_n⟩_n satisfying the same recurrence relation, the ratio u_n/v_n → 0 as n → ∞. <br> In this paper we give a Turing reduction of the problem of deciding positivity of second-order holonomic sequences to that of deciding minimality of such sequences. More specifically, we give a procedure for determining positivity of second-order holonomic sequences that terminates in all but an exceptional number of cases, and we show that in these exceptional cases positivity can be determined using an oracle for deciding minimality. |
| spellingShingle | Kenison, G Klurman, O Lefaucheux, E Luca, F Moree, P Ouaknine, J Whiteland, MA Worrell, J On positivity and minimality for second-order holonomic sequences |
| title | On positivity and minimality for second-order holonomic sequences |
| title_full | On positivity and minimality for second-order holonomic sequences |
| title_fullStr | On positivity and minimality for second-order holonomic sequences |
| title_full_unstemmed | On positivity and minimality for second-order holonomic sequences |
| title_short | On positivity and minimality for second-order holonomic sequences |
| title_sort | on positivity and minimality for second order holonomic sequences |
| work_keys_str_mv | AT kenisong onpositivityandminimalityforsecondorderholonomicsequences AT klurmano onpositivityandminimalityforsecondorderholonomicsequences AT lefaucheuxe onpositivityandminimalityforsecondorderholonomicsequences AT lucaf onpositivityandminimalityforsecondorderholonomicsequences AT moreep onpositivityandminimalityforsecondorderholonomicsequences AT ouakninej onpositivityandminimalityforsecondorderholonomicsequences AT whitelandma onpositivityandminimalityforsecondorderholonomicsequences AT worrellj onpositivityandminimalityforsecondorderholonomicsequences |