Complexity of factoring and GCD calculating for linear ordinary differential operators

D. Yu. Grigor'ev

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 4, Tome 176 (1989), pp. 68-103

Résumé

Let $L=\sum\limits_{0\leqslant k\leqslant n}f_k(X)\frac{d^k}{dX^k}\in F(X)\left[\frac d{dX}\right]$ be a linear ordinary differential operator, where the field $F\simeq\mathbb{Q}(T_1,\dots,T_\varepsilon)[Z]/(\varphi)$, here $T_1,\dots,T_\varepsilon$ are algebraically independent over $\mathbb{Q}$ and the polynomial $\varphi\in\mathbb{Q}[T_1,\dots,T_\varepsilon][Z]$ is irreducible. Assume that $\mathrm{deg}_X(f_k)$, $\mathrm{deg}_Z(\varphi)$; $\mathrm{deg}_{T_1,\dots,T_\varepsilon}(\varphi)$, $\mathrm{deg}_{T_1,\dots,T_\varepsilon}(f_k)$ and the bit-size of each rational coefficient occurring in $L$ and in $\varphi$ is less than $M$. Define an integer $N$ such that for any representation $L=Q_1Q_2Q_3$, where $Q_1$, $Q_2$, $Q_3\in\overline{F}(X)\left[\frac d{dx}\right]$ and $Q_2$, $Q_3$ are monic, holds $\mathrm{deg}_X(Q_2)\leqslant N$. THEOREM. 1) One can factor $L=L_1\dots L_s$ in a product of irreducible in the ring $\overline{F}(X)\left[\frac d{dx}\right]$ operators $L_1,\dots,L_s\in F_1(X)\left[\frac d{dx}\right]$ and construct an irreducible polynomial $\varphi_1\in\mathbb{Q}(T_1,\dots,T_\varepsilon)[Z]$ such that $F\simeq\mathbb{Q}(T_1,\dots,T_\varepsilon)[Z]/(\varphi_1)$ in time $(M((Ndn)^{n^2\log(n)}d_1^{\,\log(n)}d_2)^{n^2+\varepsilon})^{O(1)}$; 2) $N\leqslant\exp((M+\varepsilon d_2)(d2^n)^{o(d2^{2n})}d_1^{\,o(2^n)})$. Define the greatest common right divisor $G=GCRD(Q_1,\dots,Q_s)$ of a family $Q_1,\dots,Q_s\in F(X)\left[\frac d{dx}\right]$ in such a way that $Q_1=\widetilde{Q}_1G,\dots,Q_s=\widetilde{Q}_sG$ and $G$ is of the maximal possible order. Assume that $Q_1,\dots,Q_s$ satisfy the same bounds as Li above. THEOREM 3). One can yield $GCRD(Q_1,\dots,Q_s)$ in time $(Md(d_1nsd_2)^{\varepsilon+1})^{O(1)}$.