Talk summary

Grimm’s conjecture

This post is based on a Linfoot talk by Shanta Laishram.

Grimm’s conjecture. Let n+1, n+2,\ldots, n+k be consecutive composite numbers. Then there exist distinct primes P_i such that P_i | (n+i) for 1 \le i \le k.

Amazingly, this simple conjecture was not published until 1969. It has been verified for n < 1.9 \times 10^{10}. The calculations were economised through an argument beginning with Hall’s marriage theorem.

Grimm’s function. Let g(n) be the largest integer k such that distinct prime divisors exist for n+1, \ldots, n+k.

Henceforth, let p_i denote the ith smallest prime. Then Grimm’s conjecture is equivalent to the statement that g(p_i) \ge p_{i+1}-p_i for all i. It is this relationship to the prime gap that makes Grimm’s conjecture not only interesting but significant. Indeed, assuming Grimm’s conjecture, upper bounds on Grimm’s function are upper bounds for the prime gap.

Henceforth, we consider the prime gap p_{i+1}-p_i for large i. The best unconditional prime gap (for large i) is p_i^{0.525}, due to Baker, Harman and Pintz. The Riemann hypothesis implies the prime gap bound \ll \sqrt{p_i} \log p_i. This is due to Harald Cramér, who conjectured the bound \ll (\log p_i)^2.

Incredibly, the current conditional result based on Grimm’s conjecture beats the RH one! This follows immediately from recent work of Laishram and Ram Murty based on smooth numbers and the Selberg sieve.

Theorem (Laishram and Ram Murty, 2012). There exists n_0 such that if n \ge n_0 then

g(n) < n^{0.46}.

Thus Grimm’s conjecture also implies Legendre’s conjecture asymptotically. I’d be interested to know if the n_0 can be made explicit in the above Theorem.