Factorization of differential systems in characteristic p

ABSTRACT

We present an algorithm for factoring differential systems with coefficients in Fp(z). Such an algorithm has already been given by van der Put in [20], [24, 13.1] and [22]. We recast his ideas to handle systems directly and we add some comparisons of strategies, an implementation in Maple¹ and a complexity analysis. The central tool for factoring in characteristic p is the p curvature. We prove the links between the p-curvature and the eigenring and we show how to use these to obtain another algorithm following the exposition of Barkatou in [1].

REFERENCES

• 1: M. A. Barkatou. On the reduction of matrix pseudo-linear equations. Technical Report RR 1040, Rapport de Recherche de l'institut IMAG, 2001.
• 2: M. A. Barkatou , E. Pflügel, On the equivalence problem of linear differential systems and its application for factoring completely reducible systems, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.268-275, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281633]
• 3: D. V. Chudnovsky and G. V. Chudnovsky. Applications of Padé approximations to the Grothendieck conjecture on linear equations. In Lecture Notes in Mathematics, Number Theory, volume 1135, pages 52--100. 1985.
• 4: R. C. Churchill and J. J. Kovacic. Cyclic vectors. In Differential Algebra and Related Topics, Proceedings of the International Workshop, Rutgers University, Newark, November 2--3 2002. River Edge, NJ, World Scientific Publishing Co.
• 5: T. Cluzeau and M. van Hoeij. A modular algorithm to compute the exponential solutions of a linear differential operator. In preparation, 2003.
• 6: F. R. Gantmacher. Théorie des matrices, Tome 1. Dunot, Paris, 1966.
• 7: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 8: Mark Giesbrecht , Yang Zhang, Factoring and decomposing ore polynomials over F_q(t), Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.127-134, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860888]
• 9: D. Y. Grigoriev, Complexity of irreducibility testing for a system of linear ordinary differential equations, Proceedings of the international symposium on Symbolic and algebraic computation, p.225-230, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96932]
• 10: T. Honda. Algebraic differential equations. Symp. Math., 24:169--204, 1981.
• 11: Mark van Hoeij, Rational solutions of the mixed differential equation and its application to factorization of differential operators, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.219-225, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.237078]
• 12: Mark Van Hoeij, Factorization of differential operators with rational functions coefficients, Journal of Symbolic Computation, v.24 n.5, p.537-561, Nov. 1997 [doi>10.1006/jsco.1997.0151]
• 13: Mark Van Hoeij, Formal solutions and factorization of differential operators with power series coefficients, Journal of Symbolic Computation, v.24 n.1, p.1-30, July 1997 [doi>10.1006/jsco.1997.0110]
• 14: M. van Hoeij. Factoring polynomials and the knapsack problem. Journal of Number Theory, 95:167--189, 2002.
• 15: N. Jacobson. Basic Algebra I, Second Edition. W.H. Freeman and Compagny, New York, 1985.
• 16: N. Jacobson. Basic Algebra II. W.H. Freeman and Compagny, San Francisco, 1980.
• 17: N. Katz. Nilpotent connections and the monodromy theorem: Applications of a result of Turritin. Technical Report 39, Publ. Math. I. H. E. S., 1970.
• 18: N. Katz. A conjecture in the arithmetic theory of differential equations. Bull. Soc. Math. France, 110:203--239, 1982.
• 19: T. Mulders , A. Storjohann, On lattice reduction for polynomial matrices, Journal of Symbolic Computation, v.35 n.4, p.377-401, April 2003 [doi>10.1016/S0747-7171(02)00139-6]
• 20: M. van der Put. Differential equations in characteristic p. Compositio Mathematica, 97:227--251, 1995.
• 21: M. van der Put. Reduction modulo p of differential equations. Indag. Math.N.S., 7(3):367--387, 1996.
• 22: M. van der Put. Modular methods for factoring differential operators. Unpublished manuscript (Preliminary Version), 1997.
• 23: M. van der Put. Grothendieck's conjecture for the rish equation y'=ay+b. Indag. Mathem., 12(1):113--124, 2001.
• 24: M. van der Put and M. F. Singer. Galois Theory of Linear Differential Equations, volume 328. Grundlehren der mathematischen Wissenschaften, Springer, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Experimentation, Theory

Keywords:
characteristic p, differential systems, eigenring, factorization, p-curvature