Computing Characteristic Polynomials of p-Curvatures in Average Polynomial Time
This addresses computational bottlenecks in number theory and algebraic geometry for researchers working with differential operators and p-curvatures, though it appears incremental as it builds on existing methods for efficiency.
The authors developed a fast algorithm that computes characteristic polynomials of p-curvatures for linear differential operators with integer polynomial coefficients for all primes below N, achieving asymptotically quasi-linear bit complexity in N, with implementations showing quickly visible performance improvements.
We design a fast algorithm that computes, for a given linear differential operator with coefficients in $Z[x ]$, all the characteristic polynomials of its p-curvatures, for all primes $p < N$ , in asymptotically quasi-linear bit complexity in N. We discuss implementations and applications of our algorithm. We shall see in particular that the good performances of our algorithm are quickly visible.