{"entities":{"Q2071768":{"pageid":2082510,"ns":120,"title":"Item:Q2071768","lastrevid":57625071,"modified":"2026-03-31T16:21:26Z","type":"item","id":"Q2071768","labels":{"en":{"language":"en","value":"Primitive normalisers in quasipolynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7466647"}},"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":"Q2071768$AA5E4FF0-C1F9-4277-9291-5D0BF7791019","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"71e09cfa68652963039237b25d1705f5fcf1132a","datavalue":{"value":{"text":"Primitive normalisers in quasipolynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2071768$1BCC5058-159D-4BAA-920A-581AEB012212","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"138b62ae3f01d213b9041a0f98a89922a0cbca43","datavalue":{"value":{"entity-type":"item","numeric-id":2048147,"id":"Q2048147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$DFBF679C-0A05-4FE9-BF35-D123FF81BCAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"09c9e677f467581a4964486a64603d264b546435","datavalue":{"value":{"entity-type":"item","numeric-id":375518,"id":"Q375518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$A0A2D107-73CF-469A-90E3-85307031E021","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"db22232807c795272dc3a83fabf3be514df44f25","datavalue":{"value":{"entity-type":"item","numeric-id":166039,"id":"Q166039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$F7202865-09EA-4A58-8FCD-A1BA85505991","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d1b4ac6feb318cea63805454939b27fbbefe0311","datavalue":{"value":{"time":"+2022-01-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2071768$57E4A0E3-B810-4E3B-90E2-CD278F802F1B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b45e7099f5b785733c9e329d8133dbbb46e2e44c","datavalue":{"value":"https://arxiv.org/abs/2106.01886","type":"string"},"datatype":"url"},"type":"statement","id":"Q2071768$40EE4058-240E-4A12-A464-FC3E3AC0B50A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"16134c912c46eed9484e49fee2d4f544312be6f1","datavalue":{"value":"The \\textit{normaliser problem} asks for generators of \\(N_K(H)\\) given generating sets of subgroups \\(H\\) and \\(K\\) of the symmetric group \\(S_n\\). The best known algorithm is due to [\\textit{D. Wiebking}, Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 230--238 (2020; Zbl 07304037)] and runs in simply exponential time \\(2^{O(n)}\\). It was shown in [\\textit{C. M. Roney-Dougal} and \\textit{S. Siccha}, Bull. Lond. Math. So. 52, 358--366 (2020; Zbl 07206657) that the normaliser problem may be solved in quasipolynomial time \\(2^{O(\\log^3(n))}\\) when \\(H\\) is primitive. The paper under review shows that whether \\(N_{S_n}(H)\\) is primitive or not may be determined in quasipolynomial time \\(2^{O(\\log^3(n))}\\), and the normaliser problem may be solved in quasipolynomial time \\(2^{O(\\log^3(n))}\\) when \\(N_{S_n}(H)\\) is primitive.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2071768$4FC400AD-694E-4ED6-9D61-CB2BEE59E9EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0da8a0ae39ec16bf06e86cd23430c4f0aa6576dd","datavalue":{"value":"20-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2071768$37C2DFFE-9FCB-4190-AAA0-A6E8126B6248","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"99162f665c9ec138d28e4bea8a477540421995b7","datavalue":{"value":"20B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2071768$B2D5DB80-4153-44D3-A4E2-329D40472A37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2071768$BB8DA2B8-F1FE-4E01-B3A5-860677AA0472","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c8f9543b504b2bdc6544626588d5077f3166f030","datavalue":{"value":"7466647","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2071768$BB8FAD89-D756-4D96-AA92-3F2B75BCF7F3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90b2ed3c130c30bac7174fa9b54a06645cc1227f","datavalue":{"value":"computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2071768$530AB1D6-D4D2-44F0-BCFB-F8D0D6B4823C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8e3f7e0d18e9c7e5b9f5b19131aa549a1a707c3","datavalue":{"value":"permutation groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2071768$D89BAE11-191C-4E65-889F-612BE98A131C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cfce2832a863226d5007a61f1cadb5cb8053f6c","datavalue":{"value":"primitive groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2071768$3574E7E0-F1B4-4A88-A63F-3370CA41944D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dad093387c12fdb02b8019267fd899d3a600d46a","datavalue":{"value":"quasipolynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q2071768$927EE5D2-3C13-4B50-8978-87B07208D2B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4b5e3166b1a8def6d7f01e6f7748beadb875899","datavalue":{"value":"normaliser problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2071768$B288A77C-5BF5-4689-A891-667565713A51","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0d6da4d139a9a0efb8c324f335b2d6b5baddc45","datavalue":{"value":{"entity-type":"item","numeric-id":897577,"id":"Q897577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$6D1A8598-942C-4742-A4EF-6A7C66E9F966","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":"Q2071768$7EF1453E-BBD0-4836-9EC3-52B0649AC898","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f0b35bd812f352fcc4e93353dbcf619c1afd877d","datavalue":{"value":"W3210334118","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2071768$5AFB12B5-9A0F-47A8-92CA-1F08372698DE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c80ff9b6aba9b771609ee53cd6aed17b5740d2e","datavalue":{"value":{"entity-type":"item","numeric-id":5361871,"id":"Q5361871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$FA18F1EE-E4B6-4289-8D3E-67A82FA940D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"644beee13e04c9a4d84b983b0ef27c2097dbc8eb","datavalue":{"value":{"entity-type":"item","numeric-id":4882944,"id":"Q4882944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$E6AEA232-BFE7-4306-BDCC-09A1E266EE63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c7e7db3e2329ab994204e4d3a3e5ba2485968b0","datavalue":{"value":{"entity-type":"item","numeric-id":4650358,"id":"Q4650358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$9B561072-B4E9-425A-8DD1-ABD1E4E55E06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d7a73a3880b357c42a71c5181af5e9ec6f53be1","datavalue":{"value":{"entity-type":"item","numeric-id":2438897,"id":"Q2438897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$5811FF1C-44B3-417D-BC18-1272050CF8E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dfbb8de8ebe678649cccab00d03a5d557f26b9c","datavalue":{"value":{"entity-type":"item","numeric-id":3791327,"id":"Q3791327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$29687861-875E-49F6-A2F7-0DFCACD38AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"067e393b8b4356a444ebb86fe4868b077a480748","datavalue":{"value":{"entity-type":"item","numeric-id":4273608,"id":"Q4273608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$B0E6CE63-1137-4F9F-BF37-C620A3AAB55D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b5ebd654f0fbd35fe8594735387a7be03a9ca8","datavalue":{"value":{"entity-type":"item","numeric-id":5414560,"id":"Q5414560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$758E9897-4DFA-480D-8011-14A36D149BA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"927e5a6f71ba697f46388b1fafa56b7e57c9bac7","datavalue":{"value":{"entity-type":"item","numeric-id":1858295,"id":"Q1858295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$867D444C-2A5C-4108-B249-6C0366D9E10C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86fff182e9743ae13faae1c7ee668f3ec6c8339f","datavalue":{"value":{"entity-type":"item","numeric-id":2139198,"id":"Q2139198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$B6D23BBB-451E-4AF0-AD08-5B90F746124B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a4425747b421789c0c81adea9ed166c1907a8bf","datavalue":{"value":{"entity-type":"item","numeric-id":5112525,"id":"Q5112525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$C7BA317D-2139-475C-9777-7D5C396B7091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1c62ada788f3ca01a4c6f8156af507942db5d91","datavalue":{"value":{"entity-type":"item","numeric-id":4787523,"id":"Q4787523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$8148D220-7141-444B-848B-6C35D6BC40C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2842731d01d96da2372e3fd8766a27c1261ab35c","datavalue":{"value":{"entity-type":"item","numeric-id":5146779,"id":"Q5146779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$B4811379-E9C9-47F7-AC7D-A72D58390EC4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fc43cc970a011ca110c3eac83c307184d44d631c","datavalue":{"value":"10.1007/S00013-021-01670-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2071768$C76863D9-A606-4BEA-B04C-5E9E34F8F3DF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79ad4809a4f428d742e70c83e0353040992478a7","datavalue":{"value":{"entity-type":"item","numeric-id":2142483,"id":"Q2142483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b3c074bd8e9c16e5f1bf7a15b24ec16655947e7","datavalue":{"value":{"amount":"+0.839239776134491","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":"Q2071768$515717A3-167D-49BF-91EC-A3D0CFFF8318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f3012170373bc0b9b04e4bf4ef29f6964e33928","datavalue":{"value":{"entity-type":"item","numeric-id":5039561,"id":"Q5039561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cb64a0218dd2b647c0d6057a821167f0e55f009","datavalue":{"value":{"amount":"+0.8340696692466736","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":"Q2071768$AB6FBE33-CCFD-48F6-B95B-2F8D182DB91F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f8e6c486b9352bdcd6ed53d96a6076d31207b05","datavalue":{"value":{"entity-type":"item","numeric-id":4020767,"id":"Q4020767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c5ee5a26c14d4dcfd2a8a6d8508a4ae845a2470","datavalue":{"value":{"amount":"+0.8268795013427734","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":"Q2071768$7DC22F4F-C865-4721-89DC-5A34737B6DD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb65bc12e0d6360d1f0cca3292d85e9976b1fbb5","datavalue":{"value":{"entity-type":"item","numeric-id":3356508,"id":"Q3356508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e653295ea467c7f73d272d89fd4a8fec8748266b","datavalue":{"value":{"amount":"+0.8045212626457214","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":"Q2071768$A3BF123E-D2D1-40F7-BC25-5EC33BFE7899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9392cee91c32834bdf079fa324592b03382ed86","datavalue":{"value":{"entity-type":"item","numeric-id":4660701,"id":"Q4660701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce55598bae353c4bbe5f2d083a09fcf156cc8467","datavalue":{"value":{"amount":"+0.7842772006988525","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":"Q2071768$FB0F2AEB-75F6-46C5-96C1-5254FC723015","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2071768$71FDC06A-1C04-49CF-A3BA-C679A1DB0455","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2071768","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2071768"}}}}}