Functional decomposition of polynomials: the wild case
type: Item
instance of: scholarly article
title: Functional decomposition of polynomials: the wild case
zbMATH Open document ID: 0722.12003
DOI: 10.1016/S0747-7171(08)80054-5
author: Joachim von zur Gathen
published in: Journal of Symbolic Computation
publication date: 1990-01-01T00:00:00Z
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 significan…
reviewed by: Geert Molenberghs
Mathematics Subject Classification ID: 12E05
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 11T06
zbMATH DE Number: 4189864
zbMATH Keywords: functional decomposition
zbMATH Keywords: exponential-time
zbMATH Keywords: wild case
zbMATH Keywords: tame case
zbMATH Keywords: complete decomposition
zbMATH Keywords: polynomial-time algorithm
MaRDI profile type: Publication
cites work: Polynomial decomposition algorithms
cites work: Q4747509
cites work: Prime and composite polynomials
cites work: On curves with separated variables
cites work: Effective procedures in field theory
cites work: Hensel and Newton Methods in Valuation Rings
cites work: Parallel Algorithms for Algebraic Problems
cites work: Functional decomposition of polynomials: the tame case
cites work: Q3826660
cites work: Q3856844
cites work: Fast multiplication of polynomials over fields of characteristic 2
cites work: Fast multiplication of large numbers
description: scientific article; zbMATH DE number 4189864