Most polynomials of degree n have Galois group equal to the full symmetric group S_n. Suppose now that we want to verify this for an individual polynomial. A probabilistic algorithm was proposed in the 1970´s. Rigorous upper bounds on the running time were first obtained in the 1990´s. We re-cast the problem in terms of random permutations, then again in terms of the following problem involving random sumsets, which we solve.

Sumset problem: 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? JOINT WORK WITH YUVAL PERES AND IGOR RIVIN