## View abstract

### 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. document.getElementById('cloakdfdc997b9322d9af4a0598e9b4eba749').innerHTML = ''; var prefix = '&#109;a' + 'i&#108;' + '&#116;o'; var path = 'hr' + 'ef' + '='; var addydfdc997b9322d9af4a0598e9b4eba749 = '&#97;l&#105;n.b&#111;st&#97;n' + '&#64;'; addydfdc997b9322d9af4a0598e9b4eba749 = addydfdc997b9322d9af4a0598e9b4eba749 + '&#105;nr&#105;&#97;' + '&#46;' + 'fr'; var addy_textdfdc997b9322d9af4a0598e9b4eba749 = '&#97;l&#105;n.b&#111;st&#97;n' + '&#64;' + '&#105;nr&#105;&#97;' + '&#46;' + 'fr';document.getElementById('cloakdfdc997b9322d9af4a0598e9b4eba749').innerHTML += '<a ' + path + '\'' + prefix + ':' + addydfdc997b9322d9af4a0598e9b4eba749 + '\'>'+addy_textdfdc997b9322d9af4a0598e9b4eba749+'<\/a>';

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.