Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth theorem (Q990817)

Let \(f(X_1,\dots,X_n)=f_1(X_1,\dots,X_n)/f_2(X_1,\dots,X_n) \in \mathbb K(X_1,\dots,X_n)\) be a rational function, where \(\mathbb K\) is a field and \(n\geq 2\). It is said to be composite if it can be written as \(f=u\circ h\), where \(u \in \mathbb K(T)\) such that \(\deg(u)\geq 2\). \textit{J. Moulin-Ollagnier} [Qual. Theory Dyn. Syst. 5, No.~2, 285--300 (2004; Zbl 1121.13301)] has found a multivariate rational function decomposition algorithm which is not optimal and works only for fields of characteristic zero. The author of this paper introduces a probablilistic optimal algorithm that decomposes \(f \in \mathbb K(X_1,\dots,X_n)\) using \(\widetilde{\mathcal O}(d^n)\) arithmetic operations, where \(d=\deg(f)\). Finally, the author shows how to modify the Gutieres-Rubio-Sevilla decomposition algorithm in order to obtain a polynomial time algorithm instead of an exponential time algorithm.