## Abstract

We prove a conjecture dating back to a 1978 paper of D.R. Musser [11], namely that
four random permutations in the symmetric group

*S*_{n}generate a transitive subgroup with probability*p*_{n}>*ε*for some*ε*> 0 independent of*n*, even when an adversary is allowed to conjugate each of the four by a possibly different element of*S*_{n}. In other words, the cycle types already guarantee generation of a transitive subgroup; by a well known argument, this implies generation of*A*_{n}or*S*_{n}except for probability 1 +*o*(1) as*n*→ ∞. The analysis is closely related to the following random set model. A random set M ⊆ Z + is generated by including each n ≥ 1 independently with probability 1/n. The sumset sumset(*M*) is formed. Then at most four independent copies of sumset(*M*) are needed before their mutual intersection is no longer infinite.Original language | English |
---|---|

Pages (from-to) | 409-428 |

Number of pages | 20 |

Journal | Random Structures and Algorithms |

Volume | 49 |

Issue number | 3 |

Early online date | 24 Dec 2015 |

DOIs | |

Publication status | Published - Oct 2016 |

## Keywords

- Sumset
- Cycle
- Poisson
- Dimension
- Galois group

## Fingerprint

Dive into the research topics of 'Four random permutations conjugated by an adversary generate*S*

_{n}with high probability'. Together they form a unique fingerprint.