Session III.6 - Symbolic Analysis
Tuesday, June 20, 14:30 ~ 15:00
Fast computation of coefficients of algebraic power series over finite fields
Alin Bostan
Inria, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
We address the following algorithmic question: given an algebraic power series with coefficients in a finite field, either univariate or multivariate, how fast can one compute a selected coefficient in its expansion? After revisiting several classical algorithms, we describe a new method, based on Christol’s 1979 theorem that connects algebraicity of power series and automaticity of their coefficients sequences. We provide new proofs of Christol’s theorem, both in the univariate and in the multivariate cases. These proofs are elementary, effective, and allow for rather sharp estimates. In particular, they are the basis for faster algorithms for computing coefficients of algebraic power series over finite fields. The talk is based on two joint works: one with Xavier Caruso, Gilles Christol and Philippe Dumas, the other with Boris Adamczewski and Xavier Caruso.