Equal sums in random sets and the concentration of divisors

Abstract

We study the extent to which divisors of a typical integer n are concentrated. In particular, defining Δ(n):=maxt#{d|n,logd∈[t,t+1]}, we show that Δ(n)⩾(loglogn)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.