Apr. 30, 3:30pm, Wean 8220

Robin Pemantle, UPenn

Permutations and sumsets of a random Poisson-Zipf set

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 *S*_{n} must you sample before there is at least an epsilon probability
that these permutations generate *S*_{n} 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 *2*^{100} 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