A fast algorithm for computing the characteristic polynomial of the p-curvature

Abstract : We discuss theoretical and algorithmic questions related to the $p$-curvature of differential operators in characteristic $p$. Given such an operator~$L$, and denoting by $\Chi(L)$ the characteristic polynomial of its $p$-curvature, we first prove a new, alternative, description of $\Chi(L)$. This description turns out to be particularly well suited to the fast computation of $\Chi(L)$ when $p$ is large: based on it, we design a new algorithm for computing $\Chi(L)$, whose cost with respect to~$p$ is $\softO(p^{0.5})$ operations in the ground field. This is remarkable since, prior to this work, the fastest algorithms for this task, and even for the subtask of deciding nilpotency of the $p$-curvature, had merely slightly subquadratic complexity $\softO(p^{1.79})$.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [31 references]  Display  Hide  Download

Contributor : Alin Bostan <>
Submitted on : Tuesday, May 20, 2014 - 8:26:02 PM
Last modification on : Thursday, November 15, 2018 - 11:56:35 AM
Document(s) archivé(s) le : Wednesday, August 20, 2014 - 12:20:40 PM


Explicit agreement for this submission



Alin Bostan, Xavier Caruso, Éric Schost. A fast algorithm for computing the characteristic polynomial of the p-curvature. ISSAC - 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. ⟨10.1145/2608628.2608650⟩. ⟨hal-00994033⟩



Record views


Files downloads