Fuchsian holonomic sequences - Département d'informatique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

Fuchsian holonomic sequences

Résumé

Many sequences that arise in combinatorics and the analysis of algorithms turn out to be holonomic (note that some authors prefer the terminology D-finite). In this paper, we study various basic algorithmic problems for such sequences (f_n)_{n∈ℕ} : how to compute their asymptotics for large n? How to evaluate f_n efficiently for large n and/or large precisions p? How to decide whether f_n > 0 for all n? We restrict our study to the case when the generating function f = ∑_{n∈ℕ} f_n z^n satisfies a Fuchsian differential equation (often it suffices that the dominant singularities of f be Fuchsian). Even in this special case, some of the above questions are related to long-standing problems in number theory. We will present algorithms that work in many cases and we carefully analyze what kind of oracles or conjectures are needed to tackle the more difficult cases.
Fichier principal
Vignette du fichier
fuchsianseq.pdf (363.93 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03291372 , version 1 (19-07-2021)
hal-03291372 , version 2 (26-08-2022)

Identifiants

  • HAL Id : hal-03291372 , version 1

Citer

Joris van der Hoeven. Fuchsian holonomic sequences. 2021. ⟨hal-03291372v1⟩
128 Consultations
187 Téléchargements

Partager

Gmail Facebook X LinkedIn More