pith. sign in

arxiv: 2403.06542 · v3 · submitted 2024-03-11 · 💻 cs.SC · math.NT· math.OA

Factoring Linear Differential Operators in Positive Characteristic by means of Solving a Norm Equation

Rapha\"el Pag\`es (UB , IMB , MATHEXP , JKU) This is my paper

Pith reviewed 2026-05-24 02:57 UTC · model grok-4.3

classification 💻 cs.SC math.NTmath.OA
keywords linear differential operatorspositive characteristicnorm equationRiemann-Roch spacesdivisor class groupfactorizationalgebraic function fieldssymbolic computation
0
0 comments X

The pith

Algorithms test and compute solutions to the equation f^{(p-1)} + f^p = h^p over algebraic function fields of characteristic p in polynomial time in the size of h and linear time in p.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes algorithms that solve a specific norm equation whose solutions determine the factorizations of linear differential operators whose coefficients lie in algebraic function fields of positive characteristic p. Prior to this work no general method existed for solving the equation even over fields with rational coefficients, limiting factorization procedures. One algorithm decides existence of solutions in time polynomial in the size of h. A second algorithm computes solutions whose size is polynomial in the size of h, running in time polynomial in the size of h and linear in the characteristic p, by computing Riemann-Roch spaces and selecting suitable elements from the divisor class group. These procedures are shown to support direct factorization of the associated differential operators.

Core claim

The solutions of the equation f^{(p-1)} + f^p = h^p in an algebraic function field of characteristic p are closely linked to the structure and factorizations of linear differential operators with coefficients in function fields of characteristic p. An algorithm tests the existence of solutions in polynomial time in the size of h. A second algorithm, based on the computation of Riemann-Roch spaces and the selection of elements in the divisor class group, computes solutions of size polynomial in the size of h in polynomial time in the size of h and linear in the characteristic p. The methods are applied to the factorization of linear differential operators in positive characteristic p.

What carries the argument

The norm equation f^{(p-1)} + f^p = h^p, solved via explicit computation of Riemann-Roch spaces and selection of elements in the divisor class group.

If this is right

  • Factorization of linear differential operators over function fields of positive characteristic p reduces to solving the given norm equation.
  • The computed solutions have size polynomial in the size of h.
  • The running time of both algorithms is polynomial in the size of h and linear in p.
  • The methods apply even when the coefficients of the operators are rational functions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same computational primitives (Riemann-Roch spaces and divisor class group operations) may be reusable for related norm equations that arise in other factorization or decomposition problems over function fields.
  • An implementation would allow symbolic computation systems to handle differential operators in positive characteristic at scales previously inaccessible.
  • The linear dependence on p suggests the method remains practical for moderate primes even when the base field is large.

Load-bearing premise

Riemann-Roch spaces and elements of the divisor class group can be computed fast enough that the overall running time remains polynomial in the size of h with only linear dependence on p.

What would settle it

For a concrete input h of known size, run the existence test and solution algorithm and verify whether every returned f satisfies the original equation and whether the running time stays within the stated polynomial and linear bounds.

read the original abstract

The solutions of the equation $f^{(p-1)} + f^p = h^p$ in the unknown function $f $over an algebraic function field of characteristic $p$ are very closely linked to the structure and factorisations of linear differential operators with coefficients in function fields of characteristic $p$. However, while being able to solve this equation over general algebraic function fields is necessary even for operators with rational coefficients, no general resolution method has been developed. We present an algorithm for testing the existence of solutions in polynomial time in the ``size'' of h and an algorithm based on the computation of Riemann-Roch spaces and the selection of elements in the divisor class group, for computing solutions of size polynomial in the ``size'' of h in polynomial time in the size of h and linear in the characteristic $p$, and discuss its applications to the factorisation of linear differential operators in positive characteristic $p$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript presents algorithms for solving the equation f^{(p-1)} + f^p = h^p over algebraic function fields of characteristic p. It gives a polynomial-time (in the size of h) procedure to test existence of solutions, and an algorithm that computes solutions of polynomial size via Riemann-Roch space computations and divisor-class-group element selection; the latter runs in polynomial time in |h| and linear time in p. Applications to factorization of linear differential operators with coefficients in such fields are discussed.

Significance. If the stated complexity bounds are established with explicit analysis, the result would be significant for symbolic computation in positive characteristic: it supplies the first general method for a norm equation that is directly tied to factorization of linear differential operators, using only standard algebraic-geometry primitives whose costs are already studied in the literature.

major comments (1)
  1. [Abstract] Abstract: the headline claim of overall polynomial time in |h| with only linear dependence on p rests on the assumption that Riemann-Roch space computation and divisor-class-group element selection each run in time polynomial in |h| and at most linear in p. No explicit complexity analysis, reduction to known bounds, or references confirming that the relevant matrix sizes and group operations remain within these limits when genus or pole orders grow with p are supplied.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and the constructive comment on the complexity analysis. We address the point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the headline claim of overall polynomial time in |h| with only linear dependence on p rests on the assumption that Riemann-Roch space computation and divisor-class-group element selection each run in time polynomial in |h| and at most linear in p. No explicit complexity analysis, reduction to known bounds, or references confirming that the relevant matrix sizes and group operations remain within these limits when genus or pole orders grow with p are supplied.

    Authors: We agree that the abstract's complexity claim would benefit from explicit justification. In the revised manuscript we will add a dedicated subsection (or appendix) that reduces the costs of the Riemann-Roch space computation and of the divisor-class-group element selection to standard polynomial-time algorithms in the literature (e.g., the matrix-based methods of Hess and the class-group algorithms of Enge et al.), and we will verify that the matrix dimensions and group-operation costs remain polynomial in the bit-size of h and at most linear in p even when the genus or pole orders are allowed to grow with p. The input size |h| already encodes the relevant degrees, so the bounds continue to hold. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation relies on independent algebraic-geometry primitives

full rationale

The paper's algorithm for solving the norm equation f^(p-1) + f^p = h^p and its application to factoring differential operators is constructed explicitly from the standard, externally defined operations of computing Riemann-Roch spaces and selecting elements from the divisor class group. These are independent computational primitives whose existence and complexity are not derived from the paper's own outputs or self-citations; the claimed polynomial-in-|h| and linear-in-p runtime is stated as a composition of those primitives rather than a self-referential reduction. No equations or steps reduce by construction to fitted parameters, renamed results, or load-bearing self-citations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the computability of Riemann-Roch spaces and divisor class group operations in the stated time bounds over algebraic function fields of characteristic p; these are standard but non-trivial assumptions in the domain.

axioms (1)
  • domain assumption Riemann-Roch spaces and divisor class group elements can be computed efficiently enough to achieve the claimed overall time bounds.
    Invoked when the abstract describes the solution algorithm based on these computations.

pith-pipeline@v0.9.0 · 5699 in / 1233 out tokens · 22634 ms · 2026-05-24T02:57:32.546873+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    A refined laser method and faster matrix multiplication

    Alman, J., and V assilevska Williams, V. A refined laser method and faster matrix multiplication. In Pro- ceedings of the 2021 ACM-SIAM Symposium on Discrete Algorit hms (SODA) (2021), [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, pp. 522 –539

    work page 2021

  2. [2]

    BaNaSt12, J.-D., Nart, E., and Stainsby, H. D. Complexity of OM factorizations of polynomials over local fields. LMS J. Comput. Math. 16 (2013), 139–171

    work page 2013

  3. [3]

    A generalization of Baker’s theorem

    Beelen, P. A generalization of Baker’s theorem. Finite Fields Appl. 15 , 5 (2009), 558–568

    work page 2009

  4. [4]

    Computing in Picard groups of projective curves over finite fi elds

    Bruin, P. Computing in Picard groups of projective curves over finite fi elds. Math. Comp. 82 , 283 (2013), 1711–1756

    work page 2013

  5. [5]

    G., and Kaltofen, E

    Cantor, D. G., and Kaltofen, E. On fast multiplication of polynomials over arbitrary algeb ras. Acta Inform. 28, 7 (1991), 693–701

    work page 1991

  6. [6]

    Symbolic-numeric factorization of differential operators

    Chyzak, F., Goyer, A., and Mezzarobba, M. Symbolic-numeric factorization of differential operators . In Proceedings of the 2022 International Symposium on Symboli c and Algebraic Computation (New York, NY, USA, 2022), ISSAC ’22, Association for Computing Machinery , p. 73–82

    work page 2022

  7. [7]

    Factorization of differential systems in characteristic p

    Cluzeau, T. Factorization of differential systems in characteristic p. In Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation (2003), ACM, New York, pp. 58–65

    work page 2003

  8. [8]

    Edixhoven, B., and Couveignes, J.-M. , Eds. Computational aspects of modular forms and Galois represen - tations, vol. 176 of Annals of Mathematics Studies . Princeton University Press, Princeton, NJ, 2011. How one can compute in polynomial time the value of Ramanujan’s tau a t a prime

    work page 2011

  9. [9]

    Central Simple Algebras and Galois Cohomology

    Gille, P., and Szamuely, T. Central Simple Algebras and Galois Cohomology . Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2006

    work page 2006

  10. [10]

    Complexity of factoring and calculating the gcd of linear or dinary differential operators

    Grigor’ev, D. Complexity of factoring and calculating the gcd of linear or dinary differential operators. Journal of Symbolic Computation 10 , 1 (1990), 7–37

    work page 1990

  11. [11]

    Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields

    Gu`ardia, J., Montes, J., and Nart, E. Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields. Journal de th´ eorie des nombres de Bordeaux 23, 3 (2011), 667–696

    work page 2011

  12. [12]

    Integer multiplication in time O(n log n)

    Harvey, D., and van der Hoeven, J. Integer multiplication in time O(n log n). Ann. of Math. (2) 193 , 2 (2021), 563–617. SOL VING THE p-RICCATI EQUATION 19

    work page 2021

  13. [13]

    On the complexity of computing determinants

    Kaltofen, E., and Villard, G. On the complexity of computing determinants. Comput. Complex. 13 , 3–4 (Feb. 2005), 91–130

    work page 2005

  14. [14]

    Local polynomial factorisation: Improving the montes algo rithm

    Poteaux, A., and Weimann, M. Local polynomial factorisation: Improving the montes algo rithm. In Pro- ceedings of the 2022 International Symposium on Symbolic an d Algebraic Computation (New York, NY, USA, 2022), ISSAC ’22, Association for Computing Machinery, p. 1 49–157

    work page 2022

  15. [15]

    Fast integral basis computation

    Poteaux, A., and Weimann, M. Fast integral basis computation

    work page

  16. [16]

    Corps locaux

    Serre, J. Corps locaux. Actualit´ es scientifiques et industrielles. Hermann, 200 4

    work page

  17. [17]

    Algebraic Function Fields and Codes , 2nd ed

    Stichtenoth, H. Algebraic Function Fields and Codes , 2nd ed. Springer Publishing Company, Incorporated, 2008

    work page 2008

  18. [18]

    High-order lifting and integrality certification

    Storjohann, A. High-order lifting and integrality certification. vol. 36. 2003, pp. 613–648. International Sym- posium on Symbolic and Algebraic Computation (ISSAC’2002) (Lille)

    work page 2003

  19. [19]

    Counting points on curves using a map to P1, II

    Tuitman, J. Counting points on curves using a map to P1, II. Finite Fields Appl. 45 (2017), 301–322

    work page 2017

  20. [20]

    Differential equations in characteristic p

    van der Put, M. Differential equations in characteristic p. vol. 97. 1995, pp. 227–251. Special issue in honour of Frans Oort

    work page 1995

  21. [21]

    Reduction modulo p of differential equations

    van der Put, M. Reduction modulo p of differential equations. Indag. Math. (N.S.) 7 , 3 (1996), 367–387

    work page 1996

  22. [22]

    Modular methods for factoring differential operators

    van der Put, M. Modular methods for factoring differential operators. Unpu blished manuscript (Preliminary Version)

    work page

  23. [23]

    van der Put, M., and Singer, M. F. Galois theory of linear differential equations , vol. 328 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles o f Mathematical Sciences] . Springer-Verlag, Berlin, 2003

    work page 2003

  24. [24]

    Factorization of differential operators with rational func tions coefficients

    V an Hoeij, M. Factorization of differential operators with rational func tions coefficients. Journal of Symbolic Computation 24 , 5 (1997), 537–561

    work page 1997