Algebraicity and transcendence of power series: combinatorial and computational aspects

Alin Bostan (1)

1 SPECFUN - Symbolic Special Functions : Fast and Certified

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.

Domaines: Calcul formel [cs.SC]; Combinatoire [math.CO]; Théorie des nombres [math.NT]

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⟩