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 the Erdős-Hooley $\Delta$-function by $\Delta (n):={\max }_t\#\{d|n,\log d\in [t,t+1]\}$, we show that $\Delta (n)\ge (\log \log n{)}^{0.35332277\dots }$ 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\subset \mathbb{N}$ by selecting $i$ to lie in $A$ with probability $1/i$. What is the supremum of all exponents ${\beta }_k$ such that, almost surely as $D\to \infty$, some integer is the sum of elements of $A\cap [D^{{\beta }_k},D]$ in $k$ different ways? We characterise ${\beta }_k$ as the solution to a certain optimisation problem over measures on the discrete cube $\{0,1{\}}^k$, and obtain lower bounds for ${\beta }_k$ which we believe to be asymptotically sharp.

94 pages, minor corrections, to appear in Invent. Math