{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q753496","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q753496","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q753496","kernelVersion":"v1","immutable":true,"modified":"2026-01-07T04:28:26Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q753496","name":"Functional decomposition of polynomials: the tame case","headline":"Functional decomposition of polynomials: the tame case","description":"scientific article; zbMATH DE number 4180807","url":"https://portal.mardi4nfdi.de/entity/Q753496","datePublished":"1990-00-00","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q165879"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q99061"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/S0747-7171(08)80014-4","url":"https://doi.org/10.1016/S0747-7171(08)80014-4"},"sameAs":["https://doi.org/10.1016/S0747-7171(08)80014-4"],"comment":"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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q5903274"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5659665"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4190138"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4170245"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1186518"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1845911"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3470109"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5779460"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2532430"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2536266"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3231245"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3216142"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1083191"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4725742"},{"@id":"https://portal.mardi4nfdi.de/entity/Q755793"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3826660"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5772619"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3783550"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5893804"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5844266"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4062638"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1240012"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3899517"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3036703"}]},"provenance":{"prov:generatedAtTime":"2026-01-07T04:28:26Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}