Functional decomposition of polynomials: the wild case

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Polynomials in general fields (irreducibility, etc.) (12E05) Parallel algorithms in computer science (68W10) Symbolic computation and algebraic computation (68W30)

Review text

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.

Recommendations

Cites work

Cited in

(32)

This page was built for publication: Functional decomposition of polynomials: the wild case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q755793)