Ben Green and collaborators discover that the well-known "birthday paradox" has its equivalent in the divisors of a typical integer.

"The well-known "birthday paradox'' states that if you have 23 or more people in a room - something difficult to achieve nowadays without a very large room - then the chances are better than 50:50 that some pair of them will share a birthday. If we could have a party of 70 or more people, the chance of this happening rises to 99.9 percent.

It turns out that there is a similar phenomenon for the divisors of a "typical'' integer. Let $X$ be large, select an integer $n$ at random from the numbers $\{1,\dots, X\}$, and write down its divisors. These are distinct numbers, so no two of them will be the same, but it turns out that with high probability some pair of them will be close together. (The same caveat is necessary in the birthday problem if you look at the precise time the people in the room were born, rather than just the day.)

What do we mean by "close together''? One interpretation is that there are two divisors $d$ and $d'$ of $n$ lying within a factor two of one another, say $d < d' < 2d$.

Whilst the analysis of the birthday paradox is quite elementary, this turns out to be a very difficult result to prove. In fact, the statement that a random integer almost surely has two distinct divisors within a factor of two of one another is a celebrated result of Maier and Tenenbaum, published in 1985. It had been an open question of Erdős for over thirty years when they solved it.

It turns out that the divisors of a random integer are much more bunched together than the birthdays of random people in a room. Recently, in joint work with Kevin Ford and Dimitris Koukoulopoulos, I investigated just how many near coincidences there must be. Given a number $n$, the Hooley $\Delta$-function $\Delta(n)$ is defined to be the maximum number of divisors of $n$, all within a factor of two of one another. The result of Maier and Tenenbaum is that $\Delta(n) \geq 2$ with high probability.

We obtained a new lower bound for $\Delta(n)$, valid for almost every integer $n$, and assembled a good deal of evidence (but so far no proof) that it is also the correct upper bound. This bound has one of the most complicated exponents I have ever seen in a number theory problem: $\Delta(n) \geq (\log \log n)^{\eta}$, where $\eta \approx 0.35332277270132346711$ is defined to be $\frac{\log 2}{\log(2/\rho)}$, where $\rho$ satisfies the equation \[ \frac{1}{1 - \rho/2} = \log 2 + \sum_{j = 1}^{\infty} \frac{1}{2^j} \log \Big(\frac{a_{j+1} + a_j^{\rho}}{a_{j+1} - a_j^{\rho}} \Big),\] where the sequence $a_j$ is defined by $a_1 = 2$, $a_2 = 2 + 2^{\rho}$ and $a_j = a_{j-1}^2 + a_{j-1}^{\rho} - a_{j-2}^{2\rho}$ for $j \geq 3$.

In fact, the definition of $\rho$ is so complicated that it's a nontrivial analysis exercise to confirm that a number satisfying the equations here even exists.

Our paper, which is 88 pages long, takes us to some surprising areas of maths -  we begin by removing most of the number theory from the problem, turning it into a question about Poisson random variables. Then, we convert that into a curious optimisation problem involving measures on the discrete cube in $\mathbb{R}^n$ and their distribution on linear subspaces. To solve this, we use a lot of properties of entropy."

Please contact us with feedback and comments about this page. Created on 17 Jun 2020 - 15:44.