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 $i$th 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.