Functional decomposition of polynomials: the tame case (Q753496)

Let \(n\) and \(r\) be postitive integers with \(r\) dividing \(n\) and \(2\leq r<n\). Let \(F\) be a field such that \(\text{char}(F)\) does not divide \(r\). Then \(\text{DEC}^F_{n,r}\) is the decomposition problem of deciding whether a given polynomial \(f\in F[x]\) of degree \(n\) can be expressed as a composition \(f=g \odot h\) with \(g,h\in F[x]\) and \(\deg (g)=r\), and, in the affirmative case, computing \(g\) and \(h\). The author provides an algorithm which solves this problem and can be implemented with \({\mathcal O}(n \log^2n \log \log n)\) arithmetic operations. This is an improvement on the algorithm presented by \textit{D. Kozen} and \textit{S. Landau} [J. Symb. Comput. 7, No. 5, 445--456 (1989; Zbl 0691.68030)], which required \(\mathcal O(n^2)\) arithmetic operations. Moreover, if \(\varepsilon >0\) is given and \(\text{char}(F)\) does not divide \(n\), the author presents an algorithm which computes a complete decomposition of a given polynomial \(f\in F[x]\) of degree \(n\) into indecomposable polynomials using \({\mathcal O}(n^{1+\varepsilon})\) arithmetic operations. A parallel version with (optimal) depth \({\mathcal O}(\log n)\) is also given, as well as a multivariate generalization. Finally, the following problem is solved. If \(f_ 1,f_ 2\in F[x]\), the polynomial \(f_ 1(x)-f_ 2(y)\in F[x,y]\) is called a separated polynomial. It is well-known by \textit{M. D. Fried} and \textit{R. E. MacRae} [Math. Ann. 180, 220--226 (1969; Zbl 0185.28803)] that finding separated factors of separated polynomials is equivalent to simultaneous decomposition of two polynomials. Let \(n\) and \(r\) be positive integers, and let \(F\) be a field with \(\text{char}(F)\) not dividing \(r\). Then \(\text{SEP}^F_{n,r}\) is the problem of determining for two given polynomials \(f_1,f_2,\in F[x]\) of degree at most \(n\), whether there exists a separated factor \(h_1(x)-h_2(y)\) of \(f_1(x)-f_2(y)\) in \(F[x,y]\) with \(\deg (h_1)=\deg (f_1)/r\). The first polynomial-time (deterministic) algorithm for solving this problem when \(F=Q\) is given. In the case \(F=\mathrm{GF}(q)\) a probabilistic algorithm using time polynomial in \(\log q\) and \(n\) is presented.