Complexity of factoring and GCD calculating for linear ordinary differential operators
D. Yu. Grigor'ev
Abstract:
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)<d$,
$\mathrm{deg}_Z(\varphi)<d_1$;
$\mathrm{deg}_{T_1,\dots,T_\varepsilon}(\varphi)$, $\mathrm{deg}_{T_1,\dots,T_\varepsilon}(f_k)<d_2$
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)}$.
UDC:
518.5 + 512.46