Vol. 2, 2019

Download this article
Download this article For screen
For printing
Recent Volumes
2: ANTS XIII
1: ANTS X
The Open Book Series
About the Series
Ethics Statement
Other MSP Publications
Fast coefficient computation for algebraic power series in positive characteristic

Alin Bostan, Xavier Caruso, Gilles Christol and Philippe Dumas

Vol. 2 (2019), No. 1, 119–135
Abstract

We revisit Christol’s theorem on algebraic power series in positive characteristic and propose yet another proof for it. This new proof combines several ingredients and advantages of existing proofs, which make it very well-suited for algorithmic purposes. We apply the construction used in the new proof to the design of a new efficient algorithm for computing the N-th coefficient of a given algebraic power series over a perfect field of characteristic p. It has several nice features: it is more general, more natural and more efficient than previous algorithms. Not only is the arithmetic complexity of the new algorithm linear in logN and quasilinear in p, but its dependency with respect to the degree of the input is much smaller than in the previously best algorithm. Moreover, when the ground field is finite, the new approach yields an even faster algorithm, whose bit complexity is linear in logN and quasilinear in p.

Keywords
algebraic power series, Christol's theorem, algorithm, complexity
Mathematical Subject Classification 2010
Primary: 11Y16, 11YXX, 12Y05, 68W30
Milestones
Received: 2 March 2018
Revised: 13 June 2018
Accepted: 11 September 2018
Published: 13 February 2019
Authors
Alin Bostan
Inria Saclay
Palaiseau
France
Xavier Caruso
Université de Rennes
CNRS
Campus de Beaulieu
Rennes
France
Gilles Christol
Institut de Mathématiques de Jussieu
Paris
France
Philippe Dumas
Inria Saclay
Palaiseau
France