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 $\mathrm{X}(L)$ the characteristic polynomial of its $p$-curvature, we first prove a new, alternative, description of $\mathrm{X}(L)$. This description turns out to be particularly well suited to the fast computation of $\mathrm{X}(L)$ when $p$ is large: based on it, we design a new algorithm for computing $\mathrm{X}(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})$.

arXiv commentISSAC - 39th International Symposium on Symbolic and Algebraic Computation (2014)

References in corpus (6)

• High order Fuchsian equations for the square lattice Ising model: ${\tilde{\chi }}^{(5)}$
• Singularities of $n$-fold integrals of the Ising class and the theory of elliptic curves
• High order Fuchsian equations for the square lattice Ising model: ${\chi }^{(6)}$
• Globally nilpotent differential operators and the square Ising model
• Some algorithms for skew polynomials over finite fields
• Fast algorithms for differential equations in positive characteristic

Cited by in corpus (6)

• A Fast Algorithm for Computing the p-Curvature
• Computation of the Similarity Class of the p-Curvature
• Guessing with Little Data
• On the denominators of the Taylor coefficients of G-functions
• Fast Computation of the $N$-th Term of a $q$-Holonomic Sequence and Applications
• Transcendence Certificates for D-finite Functions