Nearly Optimal Algorithms for the Decomposition of Multivariate Rational Functions and the Extended Lüroth's Theorem
arXiv:1004.5285 · doi:10.1016/j.jco.2010.05.001
Abstract
The extended Lüroth's Theorem says that if the transcendence degree of $\KK(\mathsf{f}_1,\dots,\mathsf{f}_m)/\KK$ is 1 then there exists $f \in \KK(\underline{X})$ such that $\KK(\mathsf{f}_1,\dots,\mathsf{f}_m)$ is equal to $\KK(f)$. In this paper we show how to compute with a probabilistic algorithm. We also describe a probabilistic and a deterministic algorithm for the decomposition of multivariate rational functions. The probabilistic algorithms proposed in this paper are softly optimal when is fixed and tends to infinity. We also give an indecomposability test based on gcd computations and Newton's polytope. In the last section, we show that we get a polynomial time algorithm, with a minor modification in the exponential time decomposition algorithm proposed by Gutierez-Rubio-Sevilla in 2001.