Complexity of factoring and calculating the GCD of linear ordinary differential operators

Abstract

Let

$$L={\displaystyle \sum _{0\le k\le n}(f_k/f)\frac{d^k}{d^{k}x}}$$

be a linear differential operator with rational coefficients, where $f_k,f\in \overline{\mathbb{Q}}[X]$ and $\overline{\mathbb{Q}}$ is the field of algebraic numbers. Let

$${\mathrm{deg}}_x(L)=\underset{0\le k\le n}{\max }\left\{{\mathrm{deg}}_x\left(f_k\right),{\mathrm{deg}}_x\left(f\right)\right\}$$

and let N be an upper bound on deg_x(L_j) for all possible factorizations of the form L = L₁ L₂ L₃, where the operators L_j are of the same kind as L and L₂, L₃, are normalized to have leading coefficient 1. An algorithm is described that factors L within time (N ℒ)⁰⁽ⁿ⁴⁾ where ℒ is the bit size of L. Moreover, a bound N ≤ exp((ℒ2ⁿ)²ⁿ) is obtained. We also exhibit a polynomial time algorithm for calculating the greatest common (right) divisor of a family of operators.