Equal sums in random sets and the concentration of divisors

We study the extent to which divisors of a typical integer n are concentrated. In particular, defining Δ (n) : = max _t# { d| n, log d∈ [t, t+ 1] } , we show that Δ (n) ⩾ (log log n) ^{0.35332277 …} for almost all n, a bound we believe to be sharp. This disproves a conjecture of Maier and Tenenbaum. We also prove analogs for the concentration of divisors of a random permutation and of a random polynomial over a finite field. Most of the paper is devoted to a study of the following much more combinatorial problem of independent interest. Pick a random set A⊂ N by selecting i to lie in A with probability 1/i. What is the supremum of all exponents β_k such that, almost surely as D→ ∞, some integer is the sum of elements of A∩[Dβk,D] in k different ways? We characterise β_k as the solution to a certain optimisation problem over measures on the discrete cube { 0 , 1 } ^k, and obtain lower bounds for β_k which we believe to be asymptotically sharp.