ACO The ACO Seminar (2014–2015)

Apr. 30, 3:30pm, Wean 8220
Robin Pemantle, UPenn
Permutations and sumsets of a random Poisson-Zipf set

Abstract:

Let M be a random set of integers greater than 1, containing each integer n independently with probability 1/n. Let S(M) be the sumset of M, that is, the set of all sums of subsets of M. How many independent copies of S must one intersect in order to obtain a finite set? This problem arises from the analysis of an algorithm in computational Galois theory. The relevant question there is, how many random permutations chosen uniformly from the symmetric group Sn must you sample before there is at least an epsilon probability that these permutations generate Sn even when an adversary replaces each one with a conjugate (another permutation of the same cycle type)? Dixon showed in 1992 that C (log n)1/2 sufficed, and conjectured that O(1) was good enough, which was proved shortly thereafter by Luczak and Pyber. Their constant was 2100 has not been improved until now, though various guesses have been made as to the actual number: 13, 12, 5, 4. We show in fact that 4 permutations suffice (equivalently, four copies of S have finite intersection).

Joint work with Yuval Peres and Igor Rivin


Back to the ACO home page