{"entities":{"Q5919604":{"pageid":8051293,"ns":120,"title":"Item:Q5919604","lastrevid":58625523,"modified":"2026-04-06T01:47:32Z","type":"item","id":"Q5919604","labels":{"en":{"language":"en","value":"The probability of generating the symmetric group"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7101330"}},"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":"Q5919604$94357620-5BF0-408B-A2CA-7554E07BE609","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7be1e11b8262a078d082d9869e61d2a4acb84b01","datavalue":{"value":{"text":"The probability of generating the symmetric group","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5919604$40881603-E61D-4A45-A0D2-CB7E0FD610A4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"60374ec8e2f8d0a0891b1dab7da147ac0cbbeb2e","datavalue":{"value":"1438.20003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919604$814E07B7-86EF-4ED0-9D50-6A99710C3E77","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a126e8b5530d99f0b836d0c84f3d0bc8609bf43","datavalue":{"value":{"entity-type":"item","numeric-id":742909,"id":"Q742909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5919604$377D9CE0-D213-47A7-9433-973B2AFFAE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2013767dfce9bd1f89438c1505f7fb602b87dbf9","datavalue":{"value":{"entity-type":"item","numeric-id":2322502,"id":"Q2322502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5919604$C087A7A3-BA05-40AD-8DEB-56AEBA076C8E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5919604$755E0B48-C5A0-44F3-ABE3-C98D6B5DC34A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"761866c458b823deb2476ea286c91321ef138424","datavalue":{"value":{"time":"+2019-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5919604$F6184017-00F4-4024-A46B-F32454100F60","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1e445b7697b71e14831429aaa14c5147c78d1d3f","datavalue":{"value":"https://arxiv.org/abs/1611.02501","type":"string"},"datatype":"url"},"type":"statement","id":"Q5919604$6B4D45A0-B5F4-499C-897A-6010087D728F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5cd3aea39561ad4f610dffe6182d5c7eec0635d0","datavalue":{"value":"A classical conjecture of \\textit{E. Netto} [The theory of substitutions and its applications to algebra. New York M. S. Bull. II. 83--106, Anzeige v. O. Bolza. (1892; JFM 24.0134.02)] on the random generation of groups is that a pair of random permutations in \\(S_n\\) generate \\(S_n\\) or \\(A_n\\) with a probability \\(p_n\\) such that \\(p_n\\to 1\\) as \\(n\\to\\infty\\). This was proven in \\textit{J. D. Dixon} [Math. Z. 110, 199--205 (1969; Zbl 0176.29901)] with an estimate \\(p_n \\ge 1-2(\\log\\log n)^{-2}\\) for sufficiently large \\(n\\) and \\(p_n\\le 1-n^{-1}+{\\mathcal{O}}(n^{-2})\\) (with a conjecture that the upper bound is the correct probability). This conjecture, i.e. \\(p_n= 1-n^{-1}+{\\mathcal{O}}(n^{-2})\\) was proven in \\textit{L. Babai} [J. Comb. Theory, Ser. A 52, No. 1, 148--153 (1989; Zbl 0685.60012)] using the classification of finite simple groups.\\par Using ideas from \\textit{J.-C. Schlage-Puchta} [Combinatorica 32, No. 3, 309--323 (2012; Zbl 1299.05166)] and the Murnaghan-Nakayama rule, the authors give a classification-free proof of this result. Specifically, they prove that for any \\(\\varepsilon>0\\) and for sufficiently large \\(n\\) the probability is \\(1-n^{-1}+{\\mathcal{O}}(n^{-2+\\epsilon})\\) for both \\(S_n\\) and \\(A_n\\).\\par Note that \\textit{A. Mar\u00f3ti} and \\textit{M. C. Tamburini}, Arch. Math. 96, No. 2, 115--121 (2011; Zbl 1222.20003)] give explicit bounds \\(1-1/n-13/n^2\\le p_n\\le1-1/n+2/(3n^2)\\), and \\textit{J. D. Dixon} [Electron. J. Comb. 12, No. 1, Research paper R56, 5 p. (2005; Zbl 1086.20045)] gives an asymptotic power series for \\(p_n\\) (with coefficients given in OEIS sequence A113869).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5919604$A6D7ACFD-2AF1-4807-A020-65CF43CEBC44","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9d1b22c512cf981f74352b0d894ac3ba97318e0e","datavalue":{"value":{"entity-type":"item","numeric-id":237007,"id":"Q237007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5919604$8B9A95C6-2C7A-45E6-A746-61FB0DB94C47","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa3a0cd38ea582d702916ee49599e832f201d954","datavalue":{"value":"20B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919604$479DC9B2-0B1B-4C2B-90DB-322F25A52545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bb5d1e694a0c88d435d98289c9ff9b7eb400d6bb","datavalue":{"value":"20C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919604$38B396E9-BD9B-4725-B099-A1EFE61C2B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ef9852cdcd91e46926999d497f49e0eb30ab1aec","datavalue":{"value":"20P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919604$1077ACA1-01CE-41BF-B212-D006977144B8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5c28dca2dd84bdd611769edc58c61286c921b7e","datavalue":{"value":"7101330","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919604$A20FCFDB-D448-453C-83CE-0AACACB3EA7B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f1f2d0ac666fcdd661844ef9a394903274fedf1","datavalue":{"value":"symmetric groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q5919604$67DCC8F6-B236-41AD-BA96-AF7ED93DF7EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63607f1dff36c8c4398c0136420b854ad4059d85","datavalue":{"value":"alternating groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q5919604$AC2EE2EA-B9BF-4399-8640-2595169C5A0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73b4c65f1932723e758d611f0e45f29f11ae5669","datavalue":{"value":"probability","type":"string"},"datatype":"string"},"type":"statement","id":"Q5919604$D8D385CD-5923-4E93-BB4C-C1DD5C925A8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6302409ec09fdeadc6bb9a580f9aea6765769730","datavalue":{"value":"random generation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5919604$19BFBA29-7E01-4364-9F38-E18E6AF82624","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"548796835ddaa91078e30ed3d046b36ef4c3c401","datavalue":{"value":"random permutations","type":"string"},"datatype":"string"},"type":"statement","id":"Q5919604$319EF0B9-4664-4E76-BEA6-CAF4AFEF1A46","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"650e761a5f418c574655712b35b1fe882f756011","datavalue":{"value":{"entity-type":"item","numeric-id":19297,"id":"Q19297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5919604$FA3609DE-E13F-43F5-95C9-A1AEA8D81BFC","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":"Q5919604$8FD175D1-7174-46F9-93C8-B8FF3B53BFE3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f9a5263cdd980a473b27d2293e02ce132bc3ea1e","datavalue":{"value":"W2963559975","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919604$FE511DBB-5944-462C-A133-F649326E43E3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dafe3384a02fc94c38f798813995ff3a956c182a","datavalue":{"value":"10.1007/S00493-017-3629-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5919604$E520E01D-0737-4686-B129-0035AC01C583","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce355fe3ed63ca754541fc0f79314af6ebbdad79","datavalue":{"value":{"entity-type":"item","numeric-id":5916480,"id":"Q5916480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2ae0222a44c1be7451cef3410627eadbe4a045e","datavalue":{"value":{"amount":"+0.9263837933540344","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":"Q5919604$BF43FF8D-9B13-428C-9250-7340F772D6DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ba48d7e2e703f0cbb3821a27802cf8cc0935132","datavalue":{"value":{"entity-type":"item","numeric-id":633172,"id":"Q633172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58dc6051471ab63fd460bdc89fbfbc13f3f0f55f","datavalue":{"value":{"amount":"+0.9082106947898864","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":"Q5919604$76C2290B-AB2C-4C94-B639-47B78A301BF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75797573d3b356a0b67286071a38c5f0d4d326e4","datavalue":{"value":{"entity-type":"item","numeric-id":3436059,"id":"Q3436059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7f2cab2b9b325df7df5578d703bc500ac271d59","datavalue":{"value":{"amount":"+0.8968262076377869","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":"Q5919604$BF78E3B8-D729-46D0-9E2D-B123624FB212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b47d3d2faf0ec0f5e8046a254f889b1e062ee7d7","datavalue":{"value":{"entity-type":"item","numeric-id":4288275,"id":"Q4288275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abe6a68e6eae4a8e6946787890c8245943649897","datavalue":{"value":{"amount":"+0.8899682760238647","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":"Q5919604$4577E227-4D5F-41CD-B61C-A1105502E562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abcd3644da5cd451064c07d627ab50246b139711","datavalue":{"value":{"entity-type":"item","numeric-id":2639170,"id":"Q2639170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"548f8c543d4eaaa566d57263f44956b95863f34c","datavalue":{"value":{"amount":"+0.8878211975097656","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":"Q5919604$65B11749-1DD3-4105-9F71-1F7FEE2FF283","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5919604","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5919604"}}}}}