Functional decomposition of polynomials: the wild case (Q755793)

Let \(F\) be a field, \(g,h\in F[x]\) and \(f=g\circ h=g(h)\in F[x]\). Then \((g,h)\) is said to be a decomposition of \(f\). For every \(f\) there exists an essentially unique complete decomposition in indecomposable polynomials, given that the characteristic \(p\) of \(F\) does not divide the degree of \(f\). The authors consider the following decomposition problem: given \(f\) of degree \(n\) and \(r,s\in \mathbb{N}\) with \(n=rs\), decide whether there exist \(g,h\in F[x]\) of degrees \(r,s\) respectively, such that \(f=g\circ h\). There exists an exponential-time algorithm if \(\text{char}(F)=0\) and in general for the ``tame'' case (\(p\) does not divide \(r\)) [the author [J. Symb. Comput. 9, No. 3, 281-299 (1990; Zbl 0716.68053)]. For the ``wild'' case, there is an algorithm over fields with a factorization procedure for univariate polynomials, given by \textit{D. Kozen} and \textit{S. Landau} [J. Symb. Comput. 7, No. 5, 445--456 (1989; Zbl 0691.68030)], polynomial-time for \(f\) irreducible and \(F\) finite; a complete decomposition is found in time \(O(n^{\log n})\) for \(F\) arbitrary with a polynomial-time factorization and \(f\) irreducible. Uniqueness is provided by Ritt's First Theorem. The present paper extends Kozen and Landau's work of directly solving the equations obtained from comparing coefficients in \(f=g\circ h\) to the wild case, where \(p\leq r<n\). An algorithm is obtained for the special case: Let \(\deg g=r=qt\) with \(q\) a power of \(p\), \(p\) does not divide \(t\), and \(q\geq p\). \(g\) is called simple if \(g=x^ r+b_{r-i}x^{r-i}+b_{r-i- 1}x^{r-i-1}+\ldots+b_ 0\), where \(b_{r-i}\neq 0\) and either \(p\) does not divide \(i\) or \(i\geq q\). The author provides a polynomial-time reduction from simple decompositions \(f=g\circ h\) with \(g\) simple to factorization of polynomials with degree less than \(n\). This gives a deterministic polynomial-time algorithm over finite fields. This can be viewed as exhibiting a further significant case of polynomial decomposition which is reasonably easy to solve; the general case still awaits a polynomial-time solution.