Decision problems for second-order holonomic sequences
We study decision problems for sequences which obey a second-order holonomic recurrence of the form f(n + 2) = P(n)f(n + 1) + Q(n)f(n) with rational polynomial coefficients, where P is non-constant, Q is non-zero, and the degree of Q is smaller than or equal to that of P. We show that existence of i...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl – Leibniz Center for Informatics
2021
|
| _version_ | 1826293219939319808 |
|---|---|
| author | Neumann, E Ouaknine, J Worrell, J |
| author_facet | Neumann, E Ouaknine, J Worrell, J |
| author_sort | Neumann, E |
| collection | OXFORD |
| description | We study decision problems for sequences which obey a second-order holonomic recurrence of the form f(n + 2) = P(n)f(n + 1) + Q(n)f(n) with rational polynomial coefficients, where P is non-constant, Q is non-zero, and the degree of Q is smaller than or equal to that of P. We show that existence of infinitely many zeroes is decidable. We give partial algorithms for deciding the existence of a zero, positivity of all sequence terms, and positivity of all but finitely many sequence terms. If Q does not have a positive integer zero then our algorithms halt on almost all initial values (f(1), f(2)) for the recurrence. We identify a class of recurrences for which our algorithms halt for all initial values. We further identify a class of recurrences for which our algorithms can be extended to total ones. |
| first_indexed | 2024-03-07T03:26:44Z |
| format | Conference item |
| id | oxford-uuid:b94a3be0-b7eb-4fa2-97f9-54101f89fefc |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:26:44Z |
| publishDate | 2021 |
| publisher | Schloss Dagstuhl – Leibniz Center for Informatics |
| record_format | dspace |
| spelling | oxford-uuid:b94a3be0-b7eb-4fa2-97f9-54101f89fefc2022-03-27T05:02:03ZDecision problems for second-order holonomic sequencesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:b94a3be0-b7eb-4fa2-97f9-54101f89fefcEnglishSymplectic ElementsSchloss Dagstuhl – Leibniz Center for Informatics2021Neumann, EOuaknine, JWorrell, JWe study decision problems for sequences which obey a second-order holonomic recurrence of the form f(n + 2) = P(n)f(n + 1) + Q(n)f(n) with rational polynomial coefficients, where P is non-constant, Q is non-zero, and the degree of Q is smaller than or equal to that of P. We show that existence of infinitely many zeroes is decidable. We give partial algorithms for deciding the existence of a zero, positivity of all sequence terms, and positivity of all but finitely many sequence terms. If Q does not have a positive integer zero then our algorithms halt on almost all initial values (f(1), f(2)) for the recurrence. We identify a class of recurrences for which our algorithms halt for all initial values. We further identify a class of recurrences for which our algorithms can be extended to total ones. |
| spellingShingle | Neumann, E Ouaknine, J Worrell, J Decision problems for second-order holonomic sequences |
| title | Decision problems for second-order holonomic sequences |
| title_full | Decision problems for second-order holonomic sequences |
| title_fullStr | Decision problems for second-order holonomic sequences |
| title_full_unstemmed | Decision problems for second-order holonomic sequences |
| title_short | Decision problems for second-order holonomic sequences |
| title_sort | decision problems for second order holonomic sequences |
| work_keys_str_mv | AT neumanne decisionproblemsforsecondorderholonomicsequences AT ouakninej decisionproblemsforsecondorderholonomicsequences AT worrellj decisionproblemsforsecondorderholonomicsequences |