Computing the n-th coefficient of an algebraic power series modulo p in O(log n) operations

2016/05/19 by Klazar, Martin
#05A15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1605.06087

Abstract

This is an exposition, for pedagogical purposes, of the formal power series proof of Bostan, Christol and Dumas [3] of the result stated in the title (a corollary of the Christol theorem).

Related

• Coefficients in powers of the log series
• A sharper multivariate Christol's theorem with applications to diagonals and Hadamard products
• A refinement of Christol's theorem for algebraic power series
• A note on Christol's theorem
• Logarithms of a binomial series: A Stirling number approach