The Probability of Generating the Symmetric Group

Sean Eberhard; Stefan-Christoph Virchow

doi:10.1007/s00493-017-3629-5

The Probability of Generating the Symmetric Group

Sean Eberhard^*, Stefan-Christoph Virchow

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

We consider the probability p(S_n) that a pair of random permutations generates either the alternating group A_n or the symmetric group S_n. Dixon (1969) proved that p(S_n) approaches 1 as n→∞ and conjectured that p(S_n) = 1 − 1/n+o(1/n). This conjecture was verified by Babai (1989), using the Classification of Finite Simple Groups. We give an elementary proof of this result; specifically we show that p(S_n) = 1 − 1/n+O(n^−2+ε). Our proof is based on character theory and character estimates, including recent work by Schlage-Puchta (2012).

Original language	English
Pages (from-to)	273-288
Number of pages	16
Journal	Combinatorica
Volume	39
Issue number	2
DOIs	https://doi.org/10.1007/s00493-017-3629-5
Publication status	Published - 01 Apr 2019
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2018, János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-017-3629-5Licence: Unspecified

Cite this

@article{4224e6e8a6bf4c44a526a1d0a317bbfb,

title = "The Probability of Generating the Symmetric Group",

abstract = "We consider the probability p(Sn) that a pair of random permutations generates either the alternating group An or the symmetric group Sn. Dixon (1969) proved that p(Sn) approaches 1 as n→∞ and conjectured that p(Sn) = 1 − 1/n+o(1/n). This conjecture was verified by Babai (1989), using the Classification of Finite Simple Groups. We give an elementary proof of this result; specifically we show that p(Sn) = 1 − 1/n+O(n−2+ε). Our proof is based on character theory and character estimates, including recent work by Schlage-Puchta (2012).",

author = "Sean Eberhard and Stefan-Christoph Virchow",

note = "Publisher Copyright: {\textcopyright} 2018, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.",

year = "2019",

month = apr,

day = "1",

doi = "10.1007/s00493-017-3629-5",

language = "English",

volume = "39",

pages = "273--288",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - The Probability of Generating the Symmetric Group

AU - Eberhard, Sean

AU - Virchow, Stefan-Christoph

PY - 2019/4/1

Y1 - 2019/4/1

N2 - We consider the probability p(Sn) that a pair of random permutations generates either the alternating group An or the symmetric group Sn. Dixon (1969) proved that p(Sn) approaches 1 as n→∞ and conjectured that p(Sn) = 1 − 1/n+o(1/n). This conjecture was verified by Babai (1989), using the Classification of Finite Simple Groups. We give an elementary proof of this result; specifically we show that p(Sn) = 1 − 1/n+O(n−2+ε). Our proof is based on character theory and character estimates, including recent work by Schlage-Puchta (2012).

AB - We consider the probability p(Sn) that a pair of random permutations generates either the alternating group An or the symmetric group Sn. Dixon (1969) proved that p(Sn) approaches 1 as n→∞ and conjectured that p(Sn) = 1 − 1/n+o(1/n). This conjecture was verified by Babai (1989), using the Classification of Finite Simple Groups. We give an elementary proof of this result; specifically we show that p(Sn) = 1 − 1/n+O(n−2+ε). Our proof is based on character theory and character estimates, including recent work by Schlage-Puchta (2012).

U2 - 10.1007/s00493-017-3629-5

DO - 10.1007/s00493-017-3629-5

M3 - Article

AN - SCOPUS:85044437279

VL - 39

SP - 273

EP - 288

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 2

ER -

The Probability of Generating the Symmetric Group

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this