Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time (Q2431341)

The author proves the following theorem. Let \(D=A(X,Y)\partial_x+B(X,Y)\partial_y\) be a polynomial derivation such that \(A(X,Y), B(X,Y) \in{\mathbb{Z}}[X,Y]\), \(\deg A \leq d\), \(\deg B \leq d\), \(\|A\|_\infty \leq {\mathcal{H}}\) and \(A,B\) are coprime. {\parindent7mm \begin{itemize}\item[(a)] It can be decided if there exists a finite number of irreducible Darboux polynomials with degree smaller than \(N\) in a deterministic way with \(O((dN\log\mathcal H)^{O(1)})\) binary operations, and in the affirmative, one can compute all of these polynomials in a deterministic way with \(O((dN\log\mathcal{H})^{O(1)})\) binary operations. \item[(b)] It can be decided if there exists a rational first integral \(\mathcal F\) of degree smaller than \(N\) in a deterministic way with \(O((dN\log\mathcal{H})^{O(1)})\) binary operations, and in the affirmative, it can be computed in a deterministic way with \(O((dN\log\mathcal{H})^{O(1)})\) binary operations. \end{itemize}} To the author's knowledge, (a) and (b) are the first polynomial-time results on the computation of Darboux polynomials and rational first integrals, respectively.