Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth Theorem

The extended Lüroth Theorem says that if the transcendence degree of K(f1,…,fm)/K is 1 then there exists f∈K(X¯) such that K(f1,…,fm) is equal to K(f)K(f). In this paper we show how to compute ff 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 nn is fixed and dd 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.