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.
Complete list of metadatas

https://hal.inria.fr/cel-01391907
Contributor : Alin Bostan <>
Submitted on : Friday, November 4, 2016 - 1:18:57 AM
Last modification on : Saturday, February 18, 2017 - 1:14:43 AM
Long-term archiving on : Sunday, February 5, 2017 - 1:01:40 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

304

Files downloads

471