{"entities":{"Q755793":{"pageid":757642,"ns":120,"title":"Item:Q755793","lastrevid":77931551,"modified":"2026-05-06T10:23:29Z","type":"item","id":"Q755793","labels":{"en":{"language":"en","value":"Functional decomposition of polynomials: the wild case"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4189864"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$B5711CC0-910D-4D29-9431-D82E009AB5AE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e306732e171bbdc2dc16308a6e973aba0895e2bf","datavalue":{"value":{"text":"Functional decomposition of polynomials: the wild case","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q755793$6350A0ED-3100-4F88-BD5D-F236B9DED83E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e1bb4037e1398eb31f00f19d093f789e8a1d5dbd","datavalue":{"value":"0722.12003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q755793$6BCE715E-3360-4DDE-B96D-32E625B7CCF8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bdf51cd95d054450d97e1d9bd84e578283e26489","datavalue":{"value":"10.1016/S0747-7171(08)80054-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q755793$C3BC9021-4552-492D-9A5C-64063B9B5BDF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7429c710692d5d0c38830d08277242d2066f38db","datavalue":{"value":{"entity-type":"item","numeric-id":165879,"id":"Q165879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$A196C6ED-344C-4097-95A1-CD060192B70E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$B34B458B-E487-4E5A-B453-4EAD77A7DFE4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q755793$F5373D34-1EA1-44FB-896B-5729592FA37A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fb25e53468fbeebbca1004d44b026c95ebf9e679","datavalue":{"value":"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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q755793$76F66B4B-AEFF-4685-AB01-66D88B75347D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c359134049d387de49bd767fdcc67a793b1facdc","datavalue":{"value":{"entity-type":"item","numeric-id":197074,"id":"Q197074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$21D20D81-D3F2-4653-97DA-FB7DD67BCFBB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"56c7f76923b29a06e5df502ec9e72c901e9849fe","datavalue":{"value":"12E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q755793$34986563-9BFF-4E98-8107-FF81463F9300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"661c831991cdebd51f9465b74d929024bd00f373","datavalue":{"value":"12Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q755793$FD64A7A3-8D1A-4F7E-9E68-73E3DDC62AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q755793$F32BBAE1-21F1-43AF-B88C-6792655B0381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q755793$4D96F6E6-2F92-49C5-9B9B-8BD37D4EB20D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q755793$B95D3A37-6573-4922-A0F1-969541ABBECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5005488ac12471348bfecb95099a57fd4da722ac","datavalue":{"value":"11T06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q755793$E0852798-4A4F-4B8E-894C-4E0DF3FC03B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"00043410eacaccac63f03186ed982cfa0852b5c4","datavalue":{"value":"4189864","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q755793$5634B983-E9A3-4397-AC63-3830A346FAA1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"45324fe2a9ef970893f6718c7580b06f94064225","datavalue":{"value":"functional decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q755793$F7FCDC03-AE31-47AF-B2D7-200462CC819F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6b16fea0e1891916026f4db2ddf294457ac6f75","datavalue":{"value":"exponential-time","type":"string"},"datatype":"string"},"type":"statement","id":"Q755793$CD7A7D88-7E04-4F04-9BC8-D3D32DC207CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd4fd2e0ff460c04c2ef7a321cfab890193d1b4f","datavalue":{"value":"wild case","type":"string"},"datatype":"string"},"type":"statement","id":"Q755793$EB47086D-8038-425C-83CD-CAC16F91B3EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29423eb261b48887be3bc32b7319f00ebbedd3ff","datavalue":{"value":"tame case","type":"string"},"datatype":"string"},"type":"statement","id":"Q755793$E9948696-6215-4722-8165-F080F9BB13C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e4c536c8b8576592f6bda8dbe5c24c71da7644f","datavalue":{"value":"complete decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q755793$D6D9859D-B24D-4D58-8E71-3EEB9D1EB0C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q755793$70E356E8-0AA6-40F1-B141-710861A0A0D7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$E9BA19A2-A65C-43CA-8F02-1B97403BB898","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bafb7194e44cfc712bfc44cb5c7951031751daa7","datavalue":{"value":{"entity-type":"item","numeric-id":5903274,"id":"Q5903274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$C3DD3D25-978E-4831-B75D-790FFA3EB9CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c21355d631011ed037f0c70ab644c2ea5c134703","datavalue":{"value":{"entity-type":"item","numeric-id":4747509,"id":"Q4747509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$24429813-ACBD-443E-9E08-49B85EFE9173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db5aaadc1bc7552f8418ed464ce0b2ccec39c59f","datavalue":{"value":{"entity-type":"item","numeric-id":1845911,"id":"Q1845911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$231381DF-4D2B-4323-B46A-F22282966441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a25e191ae3270272868f09b298cfbe530325a30","datavalue":{"value":{"entity-type":"item","numeric-id":2536266,"id":"Q2536266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$06C1605C-63AB-4502-94F7-1CE59463EED8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c13d8c4f9b6f2d65debfe54d1f367b84b9c0238f","datavalue":{"value":{"entity-type":"item","numeric-id":3231245,"id":"Q3231245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$DEEBFAD6-F481-4C5C-8B16-760E276CBE30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4151d797d60d17f1b5ba31ccf3e9063259641a53","datavalue":{"value":{"entity-type":"item","numeric-id":3703974,"id":"Q3703974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$0E78900E-D63C-444F-900D-A134911CDEA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd6868580e9d86d3166189e1095f94e7772623b8","datavalue":{"value":{"entity-type":"item","numeric-id":3216142,"id":"Q3216142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$D3C25ABD-1401-4BFE-80F9-A859FBF074B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa9d74fed92074cc90157e94abdbe5dcf3b20977","datavalue":{"value":{"entity-type":"item","numeric-id":753496,"id":"Q753496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$F9AAE3C0-EAD4-4921-96F0-E4982B54CA99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbf97dcb242745ff2f25f6073d13e0ab155373be","datavalue":{"value":{"entity-type":"item","numeric-id":3826660,"id":"Q3826660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$81082164-B888-4C94-8A50-9505CB74FF55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32f2335f385d28ca8fef850b2a5270514f57dc65","datavalue":{"value":{"entity-type":"item","numeric-id":3856844,"id":"Q3856844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$D9466450-9FBB-4BD2-8A14-AE0B3A48BB8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55671e87319c03a503219a2b4948488361c95655","datavalue":{"value":{"entity-type":"item","numeric-id":5893804,"id":"Q5893804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$1CA788B0-C9A4-45C9-AE63-0C6A75AB8368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9610640ae5f3e1975ae1a3bd22825e6cc16676b","datavalue":{"value":{"entity-type":"item","numeric-id":1240012,"id":"Q1240012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$20592C2F-A22A-4A8B-8580-9FF8232CBA1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d864ecf0887e3285d5a657ecba76076407dae52","datavalue":{"value":{"entity-type":"item","numeric-id":2548172,"id":"Q2548172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q755793$126B2887-D043-47AA-8292-41646ADDB8B1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a70c3ccbf3751c38532e2c0a88d2877c41c5f212","datavalue":{"value":{"entity-type":"item","numeric-id":753496,"id":"Q753496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0bbe6fa6a7db9e8d24cfc49ff8c309d5215973c","datavalue":{"value":{"amount":"+0.8826660513877869","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q755793$A2BFFE4B-B960-44BC-907A-140CEC883E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbfd054005e183fe719f11e4edceb67980fe396e","datavalue":{"value":{"entity-type":"item","numeric-id":4239577,"id":"Q4239577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"665db8f1895e2549a04bd2603c57aeac06078ab3","datavalue":{"value":{"amount":"+0.8817527890205383","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q755793$B7D404C6-F1EF-4188-B835-EFAA1D984A3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b7c577f480d4daa896a82777407acb5e109a8cc","datavalue":{"value":{"entity-type":"item","numeric-id":674743,"id":"Q674743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abf9ee8c59b7b0b280d70c9483506f13853bd2e6","datavalue":{"value":{"amount":"+0.8469688296318054","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q755793$2ACF268E-7182-466C-A0E2-4E084BC11A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38d0eb99e4d901dbc40a25ea0faf0a64d7645617","datavalue":{"value":{"entity-type":"item","numeric-id":4237364,"id":"Q4237364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abf9ee8c59b7b0b280d70c9483506f13853bd2e6","datavalue":{"value":{"amount":"+0.8469688296318054","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q755793$640F3F3B-5D78-412D-9BD2-614972B7012B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"887d1de01e6165de6d2a50ec0b3c1eaeec6882cd","datavalue":{"value":{"entity-type":"item","numeric-id":1930181,"id":"Q1930181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7d1cec046428169b60a8f916a81088b183e04c6","datavalue":{"value":{"amount":"+0.8409290313720703","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q755793$4253A52D-1C02-43CF-9121-2409E9567D98","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Functional decomposition of polynomials: the wild case","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Functional_decomposition_of_polynomials:_the_wild_case"}}}}}