Tools
Tools
Kenison, G (2024) The Threshold Problem for Hypergeometric Sequences with Quadratic Parameters. In: Leibniz International Proceedings in Informatics, LIPIcs , 297. 145:1-145:20. (51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), 8th Jul - 12th Jul 2024, Tallinn, Estonia).
|
Text
The Threshold Problem for Hypergeometric Sequences with Quadratic Parameters.pdf - Published Version Available under License Creative Commons Attribution. Download (835kB) | Preview |
Abstract
Hypergeometric sequences are rational-valued sequences that satisfy first-order linear recurrence relations with polynomial coefficients; that is, 〈un〉∞n=0 is hypergeometric if it satisfies a first-order linear recurrence of the form p(n)un+1 = q(n)un with polynomial coefficients p, q ∈ Z[x] and u0 ∈ Q. In this paper, we consider the Threshold Problem for hypergeometric sequences: given a hypergeometric sequence 〈un〉∞n=0 and a threshold t ∈ Q, determine whether un ≥ t for each n ∈ N0. We establish decidability for the Threshold Problem under the assumption that the coefficients p and q are monic polynomials whose roots lie in an imaginary quadratic extension of Q. We also establish conditional decidability results; for example, under the assumption that the coefficients p and q are monic polynomials whose roots lie in any number of quadratic extensions of Q, the Threshold Problem is decidable subject to the truth of Schanuel’s conjecture. Finally, we show how our approach both recovers and extends some of the recent decidability results on the Membership Problem for hypergeometric sequences with quadratic parameters.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| Divisions: | Computer Science and Mathematics |
| Publisher: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| SWORD Depositor: | A Symplectic |
| Date Deposited: | 16 Oct 2024 12:22 |
| Last Modified: | 16 Oct 2024 13:04 |
| DOI or ID number: | 10.4230/LIPIcs.ICALP.2024.145 |
| URI: | https://researchonline.ljmu.ac.uk/id/eprint/24530 |
 |
View Item |