{"entities":{"Q2438377":{"pageid":2449120,"ns":120,"title":"Item:Q2438377","lastrevid":57926226,"modified":"2026-04-03T02:57:31Z","type":"item","id":"Q2438377","labels":{"en":{"language":"en","value":"Fast recognition of alternating groups of unknown degree."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6267892"}},"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":"Q2438377$70E880EA-562E-4926-97E5-EC128C961ED6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f20bf6ad22691935bbe37e13d4622132a4ce1848","datavalue":{"value":{"text":"Fast recognition of alternating groups of unknown degree.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2438377$3F3FD99E-F996-478F-A59B-8EBA302E72EB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d44a49968a39975d9f71ba185cb79b32e41e4d9a","datavalue":{"value":"1293.20004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2438377$31CB3931-DA8F-4448-BD13-E063C3FC69D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a9e61e6a4e7c146ecf3354d6c59f1b4d76b09374","datavalue":{"value":{"entity-type":"item","numeric-id":479796,"id":"Q479796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$9F9A9D44-0361-489F-B134-0D2CA7273849","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"55c0ad82dc4419bd35baebeb67622adda827acf2","datavalue":{"value":{"entity-type":"item","numeric-id":2438376,"id":"Q2438376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$E59E1AD3-9F1B-4817-BA5B-9148C92E30D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ef698262b14fd0be4185b1b4d7056bf1cc3ade0","datavalue":{"value":{"entity-type":"item","numeric-id":307918,"id":"Q307918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$C225962F-54C3-4669-8C20-E45050FD21A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a445aed1a5db4d33c0bd3fd2efe9b7cf2c0d7cb6","datavalue":{"value":{"entity-type":"item","numeric-id":541966,"id":"Q541966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$6D227014-84CD-4EE0-B1A8-268DB24B1A8A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"93541bb195a0809b1f249396bcebe99d047e6b6c","datavalue":{"value":{"entity-type":"item","numeric-id":161561,"id":"Q161561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$368F413E-2176-43F6-8837-476440D808BC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cbea39db51431eeef257c1e81d8127b8e4c94e30","datavalue":{"value":{"time":"+2014-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2438377$EABE911E-1A42-4BA9-BE99-0CC8D9CD87D9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7907a6c5d2ca34082c7a70ddca54b126798dbe7c","datavalue":{"value":"https://arxiv.org/abs/1306.0767","type":"string"},"datatype":"url"},"type":"statement","id":"Q2438377$EAE832EB-9765-4C0F-992F-A2E30D9C7148","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"36baf7acbb873d8d5070362b60303ae833912fea","datavalue":{"value":"There are very effective algorithms to determine whether a black box group \\(G\\) is isomorphic to an alternating group of degree \\(n\\) when the degree is known [see \\textit{R. Beals} et al., Trans. Am. Math. Soc. 355, No. 5, 2097-2113 (2003; Zbl 1022.20004)] but these are inefficient if \\(n\\) is not known. In the present paper the authors present a (one-sided Monte Carlo) algorithm for the following. Let \\(G=\\langle X\\rangle\\) be a black box group, \\(N\\) be a positive integer and \\(\\varepsilon\\) a real number between \\(0\\) and \\(1\\). If \\(G\\cong A_n\\) or \\(S_n\\) for some \\(n\\) with \\(9\\leq n\\leq N\\) then with probability \\(>1-\\varepsilon\\) the algorithm returns an isomorphism from \\(G\\) onto \\(A_n\\) or \\(S_n\\); otherwise it reports failure. The time the algorithm takes is bounded by \\(O(N(\\log N)^{2}\\log(1/\\varepsilon)(|X|\\mu+\\rho))\\) where \\(\\mu\\) bounds the time taken to multiply two elements of \\(G\\) and \\(\\rho\\) bounds the time taken to compute a random element of \\(G\\). The space required is proportional to \\(\\log N\\).   The proof of this result depends on the following facts about permutation groups. Suppose that \\(G=A_n\\) or \\(S_n\\) (\\(n\\geq 9\\)) and \\(s\\) is an involution moving \\(2k\\) points where \\(1\\leq k\\leq\\tfrac{2}{3}\\sqrt n\\). Then: (i) the proportion of elements \\(x\\) of even order satisfying \\(|\\text{supp }x^{|x|/2}|\\leq\\tfrac{4}{3}\\sqrt n\\) is at least \\(1/(13\\log n)\\); (ii) the proportion of elements \\(r\\) in the conjugacy class \\(s^G\\) such that the supports of \\(r\\) and \\(s\\) have exactly one common point is at least \\(10/(3n)\\); (iii) \\((sr)^2\\) is a \\(3\\)-cycle for at least one third of the elements \\(r\\) satisfying the condition in (ii).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2438377$1D9DB77D-CC64-49CB-A769-C06FEF8E1398","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bac883d785667a63a92fc8927c00d4d1184f1321","datavalue":{"value":{"entity-type":"item","numeric-id":590084,"id":"Q590084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$D48EED75-7039-4E2B-9D89-BE774637A4B3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0ac1dafab2cb163643c64b3cf5c7678542cb29be","datavalue":{"value":"20B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2438377$BDCB92C2-DB7E-421F-9FB2-1A1B71B0E1DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa3a0cd38ea582d702916ee49599e832f201d954","datavalue":{"value":"20B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2438377$1259102F-465A-419E-9289-E0ED94C3844B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ef9852cdcd91e46926999d497f49e0eb30ab1aec","datavalue":{"value":"20P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2438377$83B81B29-7571-4096-BD8C-0B4050405DFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f96720fe29e309c34c82deec20bd95823bb71652","datavalue":{"value":"20-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2438377$2ECD3069-76B9-48DC-9F90-51F2337126C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2438377$27E3B341-8617-41A4-A729-281C135CACE0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"66d09d19fb01e14f9b2a8294e9e023ed0826f171","datavalue":{"value":"6267892","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2438377$B92EC4CE-9B7A-4449-BE22-F47BD17192BD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c5efae6c6a6e0657ecd347fc69c73ec0f02267f","datavalue":{"value":"black-box groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2438377$E263789C-458C-4806-8A01-F84AB8AA320C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f54625964106b9c251b314b4f2e4692c882c4e06","datavalue":{"value":"constructive recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2438377$024587FD-0C58-4222-A336-DB7CD1E82523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63607f1dff36c8c4398c0136420b854ad4059d85","datavalue":{"value":"alternating groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2438377$70A9E27E-E125-41E0-92B1-A2437234AC4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f1f2d0ac666fcdd661844ef9a394903274fedf1","datavalue":{"value":"symmetric groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2438377$0DFBC8E2-F95F-4084-803E-DE0998F9AA69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06cae65688d3385aec26afb1fc9e9a3ede5455e6","datavalue":{"value":"probabilistic methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q2438377$0A186F46-C98C-461A-BE58-703B59676706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"995cad84bb298e04849cd8e41f71d8cdd6159b15","datavalue":{"value":"proportions of elements","type":"string"},"datatype":"string"},"type":"statement","id":"Q2438377$E7D9D1D6-FDAE-49E9-A4E2-DEA08FA5EF5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f50b0b8b0bfe6351b7fac21790beb2c5e9b62dd","datavalue":{"value":"Monte Carlo algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2438377$8E8AC99B-CF16-4001-A95E-BCBED3738532","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"dd7f0abef058f8eae97be2e317c30210cbb29e90","datavalue":{"value":{"entity-type":"item","numeric-id":13081,"id":"Q13081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$C00BA85E-6422-4FCC-9EC6-45E840876684","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":"Q2438377$36121147-541D-4694-9C77-ADA9A5AFD7CF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1825ceb4876fc84827377ef6c64199691c98f58e","datavalue":{"value":"W2086692420","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2438377$A5CFB631-7A7B-4B67-8E51-A34A94D5603E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d908991b10224ef6221f7256bf95cc59ae3fdc95","datavalue":{"value":{"entity-type":"item","numeric-id":4796014,"id":"Q4796014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$59C0D913-B9A5-446F-B4D2-00793011259D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44230633dda1d75561ae186d9a63c8103db3e8f3","datavalue":{"value":{"entity-type":"item","numeric-id":4794618,"id":"Q4794618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$F76D5C8F-1569-4764-BAE0-F8CD1AF9E5B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bf7500ce90ef524a0db32bb74b3ebd1007dc0c0","datavalue":{"value":{"entity-type":"item","numeric-id":1971492,"id":"Q1971492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$E5C94509-1F6F-45E1-85CF-543FC99E7983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b7d03acfe694d55b5bfb81a8721b654f11fafd6","datavalue":{"value":{"entity-type":"item","numeric-id":3139838,"id":"Q3139838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$D2488276-ECC3-493E-B961-7A653D5D5FBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3313bc08d273235c44360297f29d369ce85755b","datavalue":{"value":{"entity-type":"item","numeric-id":2759632,"id":"Q2759632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$F8EEF536-5E36-4486-938F-D10503636ED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad99d3b189d46ee8adbf1ab2a3a82c04ec90de01","datavalue":{"value":{"entity-type":"item","numeric-id":2958996,"id":"Q2958996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$2DE5AD28-F1D8-4B19-82EF-595EC5BD84FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9826f69c4dbc06f6e016fdd1a73b286489c26b61","datavalue":{"value":{"entity-type":"item","numeric-id":3117227,"id":"Q3117227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$72417D4D-D869-4FE6-B316-E35ABF9C4AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc3ee510a6b0b5da3a7c11b81a8c90bbc05d1f8e","datavalue":{"value":{"entity-type":"item","numeric-id":3101023,"id":"Q3101023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2438377$ADC17CAD-0614-4E10-B245-DDA3193041D6","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":"Q2438377$F81A9136-6536-456A-937B-051EF5A5DB21","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a60214bd29a5811ea9b10ce4f0b5bb496ce6cf1","datavalue":{"value":"10.1016/J.JALGEBRA.2013.06.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2438377$DAD1E108-8F2E-4CA1-8B65-C728001AEF93","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78903e9119c74dd67a7907cb25e6708b6c5da56e","datavalue":{"value":{"entity-type":"item","numeric-id":4794618,"id":"Q4794618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0d298d633b5cd6ddb15380e4ab9eb8e231fa979","datavalue":{"value":{"amount":"+0.8873870372772217","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":"Q2438377$99C69EA9-08B8-429B-8DC5-A2391BBF6B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"328c07f1ba38419601793228c2693fc954686916","datavalue":{"value":{"entity-type":"item","numeric-id":4376174,"id":"Q4376174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0d298d633b5cd6ddb15380e4ab9eb8e231fa979","datavalue":{"value":{"amount":"+0.8873870372772217","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":"Q2438377$205C89DB-6C6A-4647-BD62-A0E5E5FCB0BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"773474260318b518580dd2181ab736bac4492418","datavalue":{"value":{"entity-type":"item","numeric-id":2577534,"id":"Q2577534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d89d93a09963ea7402aa9f5f73a61b0d616c7312","datavalue":{"value":{"amount":"+0.8461620211601257","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":"Q2438377$C94E7C6B-EA9B-42D2-8DF3-A6BC7E4BFC74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5764ae7d54f077d73d6454966ccc36f66bb83c51","datavalue":{"value":{"entity-type":"item","numeric-id":2746922,"id":"Q2746922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66c06a5a4e6bf9905b6c73e9506e2bb65e3fd942","datavalue":{"value":{"amount":"+0.8188949227333069","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":"Q2438377$61418EB9-2B9C-4FDD-BC79-BDA039CB9E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6580792411f51c62494f66e6526859359aab7154","datavalue":{"value":{"entity-type":"item","numeric-id":2841965,"id":"Q2841965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b24240f43ac94d5da58b6f495441ef1e3ba873fa","datavalue":{"value":{"amount":"+0.8009733557701111","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":"Q2438377$6C76FEC1-E745-4C78-A40C-28ACE13DF8C3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2438377","badges":[]}}}}}