Equal sums in random sets and the concentration of divisors

Abstract

Abstract We study the extent to which divisors of a typical integer n are concentrated. In particular, defining $$\Delta (n) := \max _t \# \{d | n, \log d \in [t,t+1]\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Δ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>:</mml:mo> <mml:mo>=</mml:mo> <mml:msub> <mml:mo>max</mml:mo> <mml:mi>t</mml:mi> </mml:msub> <mml:mo>#</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:mi>d</mml:mi> <mml:mo>|</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mo>log</mml:mo> <mml:mi>d</mml:mi> <mml:mo>∈</mml:mo> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>t</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>]</mml:mo> </mml:mrow> <mml:mo>}</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , we show that $$\Delta (n) \geqslant (\log \log n)^{0.35332277\ldots }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Δ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>⩾</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mn>0.35332277</mml:mn> <mml:mo>…</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> 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 $${\textbf{A}} \subset {\mathbb {N}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>⊂</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> by selecting i to lie in $${\textbf{A}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>A</mml:mi> </mml:math> with probability 1/ i . What is the supremum of all exponents $$\beta _k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>β</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> such that, almost surely as $$D \rightarrow \infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>D</mml:mi> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi> </mml:mrow> </mml:math> , some integer is the sum of elements of $${\textbf{A}} \cap [D^{\beta _k}, D]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>∩</mml:mo> <mml:mo>[</mml:mo> <mml:msup> <mml:mi>D</mml:mi> <mml:msub> <mml:mi>β</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:msup> <mml:mo>,</mml:mo> <mml:mi>D</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> in k different ways? We characterise $$\beta _k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>β</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> as the solution to a certain optimisation problem over measures on the discrete cube $$\{0,1\}^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> <mml:mi>k</mml:mi> </mml:msup> </mml:math> , and obtain lower bounds for $$\beta _k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>β</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> which we believe to be asymptotically sharp.

Locations

• Inventiones mathematicae - View - PDF