Talk summary | random number theory generator

This post is based on Ben Green’s talk at YRM 2013, which neatly summarised Yitang Zhang’s proof of the following long-sought result.

Theorem (Zhang, 2013). There exists $H$ such that there are infinitely many pairs $p' > p$ of primes such that $p'-p \le H$ .

Zhang gave $H \le 70,000,000$ . The twin prime conjecture claims that $H=2.$ There’s an ongoing Polymath8 project dedicated to lowering $H$ , with the currently accepted record being $12,006$ .

Zhang’s idea was to marry two large bodies of work. The first, initiated by Selberg in the 1940s and carried on by Goldston-Pintz-Yildirim in 2005, investigates the link between the distribution of primes in arithmetic progression and bounded gaps. The second, whose numerous contributors included Bombieri, A.I. Vinogradov, Linnik, Heath-Brown, Iwaniec, Friedlander and Fouvry, studies how primes behave in APs.

When studying primes via sieves, it is convenient to use the von Mangoldt function $\Lambda$ . The prime number theorem is equivalent to

$\sum_{x \le X} \Lambda(x) \sim X$ .

For primes in AP: we expect that

$\sum_{X \ge x \equiv c \mod d} \Lambda(x) \simeq X/\varphi(d)$ (1)

whenever $d < X^{1-\varepsilon}$ and $(c,d)=1$ . This is only known for $d \le \log^A X$ , where $A$ is any positive number. Roughly speaking GRH is equivalent to (1) holding for $d < X^{1/2 - \varepsilon}$ . Powerful work of Bombieri and Vinogradov from the 1960s establishes (1) for almost all $d<X^{1/2}$ .

Then in 2005, Goldston, Pintz and Yildirim showed that if (1) holds for almost all $d < X^\theta$ (some $\theta > 1/2$ then $H \sim (\theta-1/2)^{-3/2}$ . Motohashi and Pintz adapted this to show that it suffices for almost all smooth $d < X^\theta$ to satisfy (1); Zhang appears to have done this independently.

In the 1980s, Bombieri, Fouvry, Friendlander and Iwaniec demonstrated (1) for almost all smooth $d < X^{4/7}$ , but this required $c$ to be fixed. Zhang removed the technical condition of $c$ needing to be fixed.

To tackle the resulting Kloosterman sums BFFI used estimates from automorphic forms, together with Weil bounds, whereas Zhang used only the latter. We expect square root cancellation of these sums, as if primes were distributed randomly, and indeed for prime $p$ this is obtained via Weil bounds:

$\sum_{n \mod p} e((an+b\bar n)/p) \ll 2 \sqrt p$ .

Crucially, if $p$ is composite then we can surpass square root cancellation just slightly.

The remainder of the talk elaborates on GPY. Let EH( $\theta$ ) be the assertion that (1) holds whenever $d \le X^\theta$ . We briefly recap. The Elliott-Halberstam conjecture is that EH( $\theta$ ) holds for any $\theta <1$ . The Bombieri-Vinogradov theorem is that EH( $\theta$ ) holds whenever $\theta <1/2$ . GPY show that if EH( $\theta$ ) holds for some $\theta >1/2$ then $H < \infty$ . So GPY fell just short of proving bounded prime gaps. GPY also showed, conditionally on EH, that $H \le 16$ .

A set $\mathcal{H} = \{h_1, \ldots, h_k\}$ is admissible if, modulo any prime $p$ , the set $\mathcal{H}$ misses a residue class modulo $p$ . This condition is necessary for it to be possible that for infinitely many $n$ , two of $n+h_1, \ldots, n+h_k$ are prime.

Theorem (GPY, 2005). Assume EH( $\theta$ ) for some $\theta > 1/2$ , and let $\{h_1,\ldots,h_k\}$ be admissible, where $k \ge k_0(\theta)$ . Then, for infinitely many $n$ , two of $n+h_1, \ldots, n+h_k$ are prime.

With Zhang’s work, this shows that improvements in $k_0$ lead to improvements in $H$ ; roughly speaking $H \sim k_0 \log k_0$ . In fact it is clear that $H$ is bounded above by the diameter of any admissible $k_0$ -tuple. Consequently, a lot of effort is being devoted towards the task of finding narrow admissible tuples.

We conclude with a sketch of the proof of the above Theorem of GPY. Define

$T = \frac{\sum_{n \le X} (\Lambda(n+h_1) + \ldots + \Lambda(n+h_k)) \nu(n)} { \sum_{n \le X} \nu(n)}$ ,

where $\nu(n)$ is the indicator function of $(n+h_1) \ldots (n+h_k)$ being almost prime. The idea is that if $T > \log X$ then, reasonably often, two of $n+h_1, \ldots, n+h_k$ would be prime. It remains to estimate the numerator and denominator of $T$ . To this end, we introduce Selberg’s functions $\nu$ which, with judicious weights, approximate our previous $\nu$ . Fix $D$ with $1 < D \ll X$ , and put $\nu = \lambda^2$ , where

$\lambda(n) = \sum_{D \ge d | n} \lambda_d$ ,

where the $\lambda_d$ are real weights with $\lambda_1 = 1$ . Note that $\nu$ majorises the indicator function of the primes, for if $n$ is prime and $D < n \le X$ then $\nu(n) =1$ .

First consider the denominator of $T$ . Our weights can be chosen so that, as well as the two notions of $\nu$ being roughly compatible, we can show that

$\sum_{n \le X} \nu(n) \le \frac{2X}{\log X}$ . (2)

The derivation of (2) proceeds as follows. Note that

$\sum_{n \le X} \nu(n) = \sum_{d,d' \le D} \lambda_d \lambda_{d'} \sum_{[d,d'] | n \le X }1$ ,

where $[d,d']$ denotes the least common multiple. If $D^2 < X$ then the inner sum is roughly $X / [d,d']$ , so

$\sum_{n \le X} \nu(n)\simeq X\sum_{d,d' \le D}\frac{\lambda_d\lambda_{d'}}{[d,d']}$ .

The right hand sum is a quadratic form in $(\lambda(1), \ldots, \lambda(D))$ , which can be minimised using general theory of the Selberg sieve, leading to the inequality (2).

The numerator of $T$ is amenable to a similar treatment. The attendant sum

$\sum_{[d,d']| n \le X} \Lambda(n+h)$

can be controlled providing that (1) holds with $[d,d']$ in place of $d$ . A painful calculation gives

$T \ge \frac{2\theta}{1+1/\sqrt{k}}\log X$ ,

and this exceeds $\log X$ (for large $k$ ) if $\theta > 1/2$ .

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.

random number theory generator

Category Archives: Talk summary

Zhang’s theorem on bounded prime gaps

Grimm’s conjecture