Algebraicity and transcendence of power series: combinatorial and computational aspects

Abstract : From ancient times, mathematicians are interested in the following question: is a given real number "algebraic" (that is, a root of a nonzero univariate polynomial with rational number coefficients), or is it "transcendental"? Although almost all real numbers are transcendental, it is notoriously difficult to actually prove, or disprove, the transcendence of a given constant. More recently, and especially with the advent of computers, different related questions arose: What is the "complexity" of a real number? How fast can one compute the first digits, or one single digit, of a (computable) real number? Can digits of algebraic numbers be computed faster than those of (computable) transcendental numbers? In this series of lectures, we will consider the (simpler) functional analogues of these questions: given a formal power series with rational number coefficients, decide whether it is algebraic (root of a nontrivial bivariate polynomial) or transcendental, and determine how fast can one compute its coefficients? We will first motivate these questions by presenting some examples of algebraic power series coming from combinatorics, with a focus on enumeration of lattice walks. Then we will discuss several methods that allow to discover and prove the nature (algebraic or transcendental) of a generating function, with an emphasis on an experimental mathematics approach combined with algorithmic methods such as Guess'n'Prove and Creative Telescoping. Finally, we will overview efficient algorithms for various operations on algebraic power series, including the computation of one or several selected terms.
Type de document :
Cours
Doctoral. 3rd Algorithmic and Enumerative Combinatorics Summer School, Hagenberg, 2016 Austria. 2016
Liste complète des métadonnées

https://hal.inria.fr/cel-01391907
Contributeur : Alin Bostan <>
Soumis le : vendredi 4 novembre 2016 - 01:18:57
Dernière modification le : samedi 18 février 2017 - 01:14:43
Document(s) archivé(s) le : dimanche 5 février 2017 - 13:01:40

Identifiants

  • HAL Id : cel-01391907, version 1

Collections

Citation

Alin Bostan. Algebraicity and transcendence of power series: combinatorial and computational aspects. Doctoral. 3rd Algorithmic and Enumerative Combinatorics Summer School, Hagenberg, 2016 Austria. 2016. 〈cel-01391907〉

Partager

Métriques

Consultations de la notice

253

Téléchargements de fichiers

412