{"entities":{"Q753496":{"pageid":755345,"ns":120,"title":"Item:Q753496","lastrevid":49448974,"modified":"2026-01-07T04:28:26Z","type":"item","id":"Q753496","labels":{"en":{"language":"en","value":"Functional decomposition of polynomials: the tame case"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4180807"}},"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":"Q753496$2E3175BB-8E88-44B5-9C53-9F3E267FF566","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d8483debc2fedd3dcafc4d27960f1ef61541b5ef","datavalue":{"value":{"text":"Functional decomposition of polynomials: the tame case","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q753496$F0EA56DD-4306-4DCA-9604-9A2D605C47D7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e93958547f92d0762e6618c8ce0a20a81586ead8","datavalue":{"value":"0716.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753496$41181B79-3BB5-4BF2-8342-A5CB1E6D9E8D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"82848ea98db33cc6fe883c2598de85d2dfef4495","datavalue":{"value":"10.1016/S0747-7171(08)80014-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753496$69D2FC1C-9E13-43C7-81A1-1B0C069415DB","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":"Q753496$2A3D073E-2AFF-4D15-87F5-BCAE4CBCE263","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":"Q753496$42A82597-A15E-40A0-BBDF-0B0AF1CF5EF0","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":"Q753496$29D96FFB-5E44-4D58-89E2-A764BE9AC1BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a90670aeb876b10be05a5aa17dee2c4fd5fd6436","datavalue":{"value":"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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q753496$87559194-F05F-48B9-82A3-202E6AE61F53","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1f7e1a277c07b3a6d4f148b99c27222344cbe448","datavalue":{"value":{"entity-type":"item","numeric-id":222524,"id":"Q222524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$5DA7E483-F45F-414D-9E98-DACFCC8DB932","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753496$57FBD013-C4D2-4FA2-A0F7-3C0CF781A009","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"661c831991cdebd51f9465b74d929024bd00f373","datavalue":{"value":"12Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753496$5ABE3D82-F6AF-42B6-AA30-F81B8193A75B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753496$B5C16D8F-5E6D-4EC9-987C-140DA5BB1EDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"56c7f76923b29a06e5df502ec9e72c901e9849fe","datavalue":{"value":"12E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753496$8D3E2336-C62E-49DA-81BA-E78C4A910307","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fffe9cdf091d5c0138c281e680ada451f0494ff9","datavalue":{"value":"4180807","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753496$955F0A44-9E81-4E5E-8E20-7A236D0678BD","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":"Q753496$2976FE6D-C90B-4694-B0AC-FB8BF2E1ADFF","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":"Q753496$23E884A1-680E-4C2A-9E76-2078C81C5DC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ceef5307961d7894eb83c6ef5e3560792b4f1dd","datavalue":{"value":{"entity-type":"item","numeric-id":5659665,"id":"Q5659665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$DF3A8D08-2845-402D-811F-748C7BBB9909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7b687389392c3c46c787b88133af21d18744004","datavalue":{"value":{"entity-type":"item","numeric-id":4190138,"id":"Q4190138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$AAFF426E-75DC-4B70-989E-0EE0AB1DA8AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6cabc1e92b122cd8a54b27aae806fe27ccb5241","datavalue":{"value":{"entity-type":"item","numeric-id":4170245,"id":"Q4170245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$617B76C8-C49E-42A6-99C6-BC2AEBE13411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"356f33dddb9638087fb97e96ade9a65b62e404ec","datavalue":{"value":{"entity-type":"item","numeric-id":1186518,"id":"Q1186518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$00A671AB-635D-44A0-B905-ED9EF5AD6246","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":"Q753496$0431C2D7-2A39-4AAA-9A2E-98AC530F2409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d31b9fbcf5b103d19429f8ba43bde08b37cbb29d","datavalue":{"value":{"entity-type":"item","numeric-id":3470109,"id":"Q3470109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$56D14228-1D5F-4EA4-92CE-506234756DFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ee7b0b2e4bbf44b9dcd9e98651ad8d4e8dd5727","datavalue":{"value":{"entity-type":"item","numeric-id":5779460,"id":"Q5779460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$6BB3F6EC-D743-408A-9FAD-31687511F9B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38ddd32a5c56e2e464ef3c7a75efdfee337b9bb5","datavalue":{"value":{"entity-type":"item","numeric-id":2532430,"id":"Q2532430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$63085AFD-9ADE-49A3-B609-0E1D9D592E4C","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":"Q753496$74D67734-5A53-49B3-AC3B-A29DB865F25E","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":"Q753496$9AA28B5D-67F5-4895-93B6-3932B0C72B41","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":"Q753496$38610A45-1699-4024-AEA3-82D5C11790AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46328794cd1313266621d0dfff89ac90e5dbbcab","datavalue":{"value":{"entity-type":"item","numeric-id":1083191,"id":"Q1083191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$E2D32976-90F3-437B-8CF5-C1A2412E6E22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f5771c621898803b98f3d8a7a0d4749a51ec11f","datavalue":{"value":{"entity-type":"item","numeric-id":4725742,"id":"Q4725742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$DD1D3BF1-22CD-4C24-B61E-30389CB0976A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2f7a81f7b25675b22b5e68e225f38ca7adbe782","datavalue":{"value":{"entity-type":"item","numeric-id":755793,"id":"Q755793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$F5A6BC87-BDFB-4130-A215-C3380942A64E","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":"Q753496$835B320B-CC2E-418F-86EF-8C962E7F6F24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb40aa93777a7cd41d54dcf43b55867cf1b75c38","datavalue":{"value":{"entity-type":"item","numeric-id":5772619,"id":"Q5772619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$CFD80B4F-DEDC-4C00-A514-CCA27F9B12A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29111540e6d6ac550dfdce0c5007cb15a1e27575","datavalue":{"value":{"entity-type":"item","numeric-id":3783550,"id":"Q3783550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$5D8D5E09-3408-447B-A6D1-5AEBB00AEF58","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":"Q753496$9814EDD8-459B-4753-B654-6E5B5CFAD12F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb4826e9f665be8a1af46e4c351d00472c7f5bfe","datavalue":{"value":{"entity-type":"item","numeric-id":5844266,"id":"Q5844266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$4F962935-4796-46D3-8699-D24986553C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53714a4528eb05c2af9065b3895242d440c82062","datavalue":{"value":{"entity-type":"item","numeric-id":4062638,"id":"Q4062638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$22596ED4-D28E-43E6-9F38-22F9F6751E5B","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":"Q753496$94D200D4-773C-4667-854F-44EA1AEBBC1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45693627939fec63d2836fa11bb5f307d8dbed5a","datavalue":{"value":{"entity-type":"item","numeric-id":3899517,"id":"Q3899517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$C0D7700D-8DA1-4578-B5EC-335A024353EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da1e2a210a633c08ab99ee4d2a519f4798177e87","datavalue":{"value":{"entity-type":"item","numeric-id":3036703,"id":"Q3036703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753496$77EC1EE9-2467-4546-8790-FD8BF486E31D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10da7603e57d4d453c9bface160d3c0e3c9b1e97","datavalue":{"value":{"entity-type":"item","numeric-id":755793,"id":"Q755793"},"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":"Q753496$7BE568E2-9C7B-402C-9F98-82E020536C45","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":"01771494176999772186a90367ee9b3377cf5050","datavalue":{"value":{"amount":"+0.8533435463905334","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":"Q753496$1333FF28-82AF-4A2F-B7B1-4518E9575B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7480670fc2baa8ccf6c644e2ec508ad5165566e","datavalue":{"value":{"entity-type":"item","numeric-id":1373276,"id":"Q1373276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01771494176999772186a90367ee9b3377cf5050","datavalue":{"value":{"amount":"+0.8533435463905334","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":"Q753496$E93F5F4A-321E-4B73-922B-3768EA154D14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d27d671e338463438ca7384c5b3f8057b91c2f9d","datavalue":{"value":{"entity-type":"item","numeric-id":4366941,"id":"Q4366941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e925adab22c86cdab51790a4d4c9889698082894","datavalue":{"value":{"amount":"+0.8469913601875305","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":"Q753496$42F2290F-98B0-46E7-9E28-584A118697E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db1dd3dca31f45bf826e01638d9a043a1c5bef5e","datavalue":{"value":{"entity-type":"item","numeric-id":4286117,"id":"Q4286117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"534bfcde653989d7fbe56440b94fb3d007b54920","datavalue":{"value":{"amount":"+0.8469913005828857","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":"Q753496$7A44F570-8096-4A0E-9B3C-6ED5781DDC31","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:753496","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:753496"}}}}}