Equal sums in random sets and the concentration of divisors - Ford, K; Green, B; Koukoulopoulos, D (Springer, 2023)
We study the extent to which divisors of a typical integer n are concentrated. In particular, defining Δ(𝑛):=max𝑡#{𝑑|𝑛,log𝑑∈[𝑡,𝑡+1]}, we show that Δ(𝑛)⩾(loglog𝑛)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 𝐀⊂ℕ by selecting i to lie in 𝐀 with probability 1/i. What is the supremum of all exponents 𝛽𝑘 such that, almost surely as 𝐷→∞, some integer is the sum of elements of 𝐀∩[𝐷𝛽𝑘,𝐷] in k different ways? We characterise 𝛽𝑘 as the solution to a certain optimisation problem over measures on the discrete cube {0,1}𝑘, and obtain lower bounds for 𝛽𝑘 which we believe to be asymptotically sharp.