{"entities":{"Q1071803":{"pageid":1082555,"ns":120,"title":"Item:Q1071803","lastrevid":48902983,"modified":"2026-01-06T03:21:21Z","type":"item","id":"Q1071803","labels":{"en":{"language":"en","value":"Solvability by radicals is in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3939444"}},"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":"Q1071803$94C0DA4A-2E0A-4A72-A395-E7D2C82C9A45","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"faf26da82456b096465a49248b2f3fec352519bc","datavalue":{"value":{"text":"Solvability by radicals is in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1071803$58DDD544-763A-4EDF-A8D7-151EA075AF40","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"248ed6907a61e36818a99f8388a72d3e38ec1137","datavalue":{"value":"0586.12002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071803$5BDEB3CD-B0DB-4684-B65F-9F1FF52C0075","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bfdee83a3f2cca9aaed5de49db57d06a48494b1c","datavalue":{"value":"10.1016/0022-0000(85)90013-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071803$DCC0029E-0231-4565-BC2E-5D2711044D03","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce70416108501eda0ba8eadb65bfd784d5c47856","datavalue":{"value":{"entity-type":"item","numeric-id":297494,"id":"Q297494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$0B2F8C25-1C2B-4F59-8978-14C239FBCA7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29373d22cc965afe0313777aac5867e3ef096150","datavalue":{"value":{"entity-type":"item","numeric-id":1071802,"id":"Q1071802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$25D64A4E-280D-4D9A-99C9-E9EDDA63ABD9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$5F5E0C23-9D6F-4DF0-B368-C64ADD30AAF3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1071803$FC58A612-C9A7-400C-AEAD-BA0C2E682A59","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"83576143d28663eb9e3bf335d40d6b07b12e62b5","datavalue":{"value":"The authors present an algorithm to prove that a given polynomial \\(f\\) over the integers is solvable in radicals, and one to write a zero of a solvable polynomial \\(f\\) in radicals. Both algorithms are in polynomial time in the size of \\(f\\). The determination whether \\(f\\) is solvable in radicals is equivalent to the determination whether the Galois group \\(G\\) of \\(f\\) is solvable. The algorithm does not compute \\(G\\), nor does it give the order of it or a set of generators. The algorithm uses the Lenstra, Lenstra and Lov\u00e1sz algorithm to factor polynomials over the integers in polynomial time. It also uses a result of P\u00e1lfy that the order of a primitive solvable group acting on \\(n\\) elements is bounded above by \\(24^{-1/3}n^{3.243999...}\\).    Let \\(\\alpha_1,\\ldots,\\alpha_n\\) be the zeros of \\(f\\). The Galois group of \\(f\\) is defined to be the Galois group of \\(\\mathbb Q(\\alpha_1,\\ldots,\\alpha_n)/\\mathbb Q\\). In order to determine whether \\(G\\) is solvable the extension \\(\\mathbb Q(\\alpha_1,\\ldots,\\alpha_n)/\\mathbb Q\\) will be split up into several small parts of which it is easy to check whether they are solvable. These parts are defined recursively to be the normal closure of some subfield of \\(\\mathbb Q(\\alpha_1)\\) that is defined to be the field of fixpoints of all elements of \\(G\\) that leave a special set (block) of zeros of \\(f\\) fixed. Using the result of P\u00e1lfy, it will then be determined whether the upper extension is solvable, and for the lower extension the problem will be solved recursively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071803$E1C48018-56FE-4944-B336-AA2906BC72C9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4d379f1f3728661c9d77f930d729b891dd925754","datavalue":{"value":"11Y40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071803$33FD540E-8301-4BE7-AAA2-A2BDB4710A1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5da175760837221b1255b8d6d71ae4d17a89f801","datavalue":{"value":"11R32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071803$BCF6FB15-AAD2-42C9-80C5-F519693B9892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071803$51A05650-390B-486A-AAA3-7BE546525B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4d93d730e1666f1434ede9b50e3e8ea943c6a3ad","datavalue":{"value":"68Q40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071803$739D6C13-EC1E-4552-BBD0-12C56E48CBDB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"417e79fcd3fff5d795c400faf98e1560e557b4b6","datavalue":{"value":"3939444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071803$171BA672-1765-4084-B3F1-F06031651E54","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1259869ee1e13bccb05014a20e76642d0f36732","datavalue":{"value":"Lenstra-Lenstra-Lov\u00e1sz algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071803$B653C123-3612-42F7-AE9D-C18194CA32C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"290484385432183f52ff2872083e93fd0902b0c7","datavalue":{"value":"solvable Galois group","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071803$C6109E01-10C2-4715-B604-E421AA0DDFC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5d2fa24c579b2baeef4d0446de7aa9ba4289043","datavalue":{"value":"polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071803$3937A568-BC9B-4BBF-AA00-B98693496CA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c9d2845c9429245c17f33f48ef38a8ea42be4c6","datavalue":{"value":"solvable in radicals","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071803$455E6692-B618-462F-8972-AEF101A9D7BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071803$7C21473E-EEDD-4766-A981-5AE7D689CEC9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8e556925742b09ac315301cf5c32e3fea8255728","datavalue":{"value":"Q55967929","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071803$1E08AE4E-E6D6-4A62-B1B4-CF95A749B477","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":"Q1071803$5284D181-5C65-4A81-A9DC-F69CA2049750","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2f4be8f9b9af6ce6668a36782e9ef7ab9517b9ee","datavalue":{"value":"https://doi.org/10.1016/0022-0000(85)90013-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1071803$F5FBF2A5-80E0-4541-953D-B6DC08DCF830","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e081c31f6011d9b912a6ecd793b11c45e51cdac9","datavalue":{"value":"W1976456789","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071803$7E2152A6-33D4-4CC0-9314-7436B1CC7BF7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"83969f6d3b28492352194d15fb4d49ca427d7e98","datavalue":{"value":{"entity-type":"item","numeric-id":4068903,"id":"Q4068903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$41629754-10B3-46EF-8A1C-679FD9262E65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89114344afb55319f83e26b6ed19450dcb689a11","datavalue":{"value":{"entity-type":"item","numeric-id":3913570,"id":"Q3913570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$521BFC21-2D75-4B2A-B91B-089D7055BF28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2ccaa8b67605d1442f748d22b53e4b3e37cf3a","datavalue":{"value":{"entity-type":"item","numeric-id":5564386,"id":"Q5564386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$2199C8E8-59AF-4460-ADFA-C482372AB2CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1f1626c3060d5aa81a769d5f87fba960c3bd043","datavalue":{"value":{"entity-type":"item","numeric-id":3313943,"id":"Q3313943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$C6666855-FFE0-48DA-A7D1-EB785BA74E0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1a6784b2890935fe040a10bbb3bc8498038646","datavalue":{"value":{"entity-type":"item","numeric-id":3679295,"id":"Q3679295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$B5B0348A-318F-4D73-B67B-750187CA5B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2496d76f7d7fec9d96f39f6e3a59ed93c78d8e95","datavalue":{"value":{"entity-type":"item","numeric-id":1165896,"id":"Q1165896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$C9999A3A-8533-475D-A197-67EA338C4BA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6813c19ceeca169ea23a7c095c0031b3eb04aa4f","datavalue":{"value":{"entity-type":"item","numeric-id":3861515,"id":"Q3861515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$6C5ECA64-AC0B-4407-A6F1-BAF21ABC7107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80a4ade2f382a077468bd8a4449f616c7cde701b","datavalue":{"value":{"entity-type":"item","numeric-id":5833980,"id":"Q5833980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$D864E8EB-F146-41A9-8C81-D35BF5653390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c40e9ff62a54de308e1fa2cf2e8c691f845c3211","datavalue":{"value":{"entity-type":"item","numeric-id":1166603,"id":"Q1166603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$4E98E055-5245-4AAA-B40B-BB3C400C5E69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d545d46281c27f7c22d936768292713b57021712","datavalue":{"value":{"entity-type":"item","numeric-id":5617749,"id":"Q5617749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$04F3EEBA-D897-4E0C-A477-A214CE4EA435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dab12509b8dd498b8e56002e52addeb87c785117","datavalue":{"value":{"entity-type":"item","numeric-id":4767051,"id":"Q4767051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$F932D4FD-02AC-4C10-9C76-22D332CDCF0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff5507321f4a39d62ce8104503bda4cb36d54179","datavalue":{"value":{"entity-type":"item","numeric-id":3963106,"id":"Q3963106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$18E3ADDE-3DC7-4F24-B293-BCE2C71815F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfab59528330d8d2ef59ab52a35bf81e14fa05e4","datavalue":{"value":{"entity-type":"item","numeric-id":2647044,"id":"Q2647044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$4F1210B9-8949-426E-9315-750103F221E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed5cab814cd603492c1673559e52eda9669c1aa7","datavalue":{"value":{"entity-type":"item","numeric-id":5512231,"id":"Q5512231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$9E335DA5-3252-43BA-90BB-86C94D143826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ebe219b97818792838f4ea38ba465654315f927","datavalue":{"value":{"entity-type":"item","numeric-id":4121986,"id":"Q4121986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$7BED45FB-E048-4144-9A10-BFDBFAFF4C68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36933ebee4e64f4429c0b4dd58d192ad12807ba6","datavalue":{"value":{"entity-type":"item","numeric-id":5659661,"id":"Q5659661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071803$19E3FE2B-9842-4CBD-A5D8-0AAD4CB88429","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"4a0fc616641bc681b880edf5af787f1ec79f974c","datavalue":{"value":"journals/jcss/LandauM85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071803$148DEF4B-D703-40A5-A8D4-C4A9E7CE72E0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ea20e64b1da3e9fcfa36663c626b868b629631b","datavalue":{"value":{"entity-type":"item","numeric-id":3698311,"id":"Q3698311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"944c0695651fc502cec7acc788e84c5c6c2039e9","datavalue":{"value":{"amount":"+0.8782294988632202","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":"Q1071803$8B8AAF05-1731-4B7C-BD72-51FD3E2A6919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ce2e41a59987a549d063dc83d274a15ca3e69d8","datavalue":{"value":{"entity-type":"item","numeric-id":2958928,"id":"Q2958928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3621efb2377ab582338f916681dc92c5828c7193","datavalue":{"value":{"amount":"+0.8445359468460083","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":"Q1071803$5ADF8E15-2CF0-4A6C-9C02-ACD243CCC2A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2302b6266251e9a81f378456bad613e92c3e6faf","datavalue":{"value":{"entity-type":"item","numeric-id":5756694,"id":"Q5756694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"654622eff25be7f00530cca35c04ef6571fc293e","datavalue":{"value":{"amount":"+0.8236551880836487","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":"Q1071803$E7424E0D-F2E5-444B-92F5-ED2557B9B2D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3962a1239eeda2142e5d306cb37aece4f0aea532","datavalue":{"value":{"entity-type":"item","numeric-id":3189074,"id":"Q3189074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c87f530b399e77623ac1426ba9c818e3af0cd801","datavalue":{"value":{"amount":"+0.8088915944099426","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":"Q1071803$41063E98-312E-4248-B068-96D30DAED4C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a67810affe42b6a8757b87af32bc28c06c3d8f8","datavalue":{"value":{"entity-type":"item","numeric-id":3481814,"id":"Q3481814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c85f7dbe7eeb740ab8e3ea23735d4f2c61493734","datavalue":{"value":{"amount":"+0.8043310046195984","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":"Q1071803$0D348E0A-152C-4194-BD2D-1469338016F8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1071803","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1071803"}}}}}