(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

For any natural number $k_0$, an admissible $k_0$-tuple is a finite set ${\mathcal H}$ of integers of cardinality $k_0$ which avoids at least one residue class modulo $p$ for each prime $p$. (Note that one only needs to check those primes $p$ of size at most $k_0$, so this is a finitely checkable condition. Let $H(k_0)$ denote the minimal diameter $\max {\mathcal H} - \min {\mathcal H}$ of an admissible $k_0$-tuple. As part of the Polymath8 project, we would like to find as good an upper bound on H(k_0) as possible for given values of k_0. (To a lesser extent, we would also be interested in lower bounds on this quantity.

## Upper bounds

Upper bounds are primarily constructed through various "sieves" that delete one residue class modulo $p$ from an interval for a lot of primes $p$. Examples of sieves, in roughly increasing order of efficiency, are listed below.

### Zhang sieve

The Zhang sieve uses the tuple

${\mathcal H} = \{p_{m+1}, \ldots, p_{m+k_0}\}$

where $m$ is taken to optimize the diameter $p_{m+k_0}-p_{m+1}$ while staying admissible (in practice, this basically means making $m$ as small as possible). Certainly any $m$ with $p_{m+1} \gt k_0$ works, but this is not optimal.

### Hensley-Richards sieve

The Hensley-Richard sieve uses the tuple

${\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0+1/2-1}\}$

where m is again optimised to minimize the diameter while staying admissible.

### Asymmetric Hensley-Richards sieve

The asymmetric Hensley-Richard sieve uses the tuple

${\mathcal H} = \{-p_{m+\lfloor k_0/2\rfloor - 1-i}, \ldots, -p_{m+1}, -1, +1, p_{m+1},\ldots, p_{m+\lfloor k_0+1/2-1+i}\}$

where $i$ is an integer and $i,m$ are optimised to minimize the diameter while staying admissible.

## Lower bounds

There is a substantial amount of literature on bounding the quantity $\pi(x+y)-\pi(x)$, the number of primes in a shifted interval $[x+1,x+y]$, where $x,y$ are natural numbers. As a general rule, whenever a bound of the form

$\pi(x+y) - \pi(x) \leq F(y)$ (*)

is established for some function $F(y)$ of $y$, the method of proof also gives a bound of the form

$k_0 \leq F( H(k_0)+1 ).$ (**)

Indeed, if one assumes the prime tuples conjecture, any admissible $k_0$-tuple of diameter $H$ can be translated into an interval of the form $[x+1,x+H+1]$ for some $x$. In the opposite direction, all known bounds of the form (*) proceed by using the fact that for $x\gty$, the set of primes between $x+1$ and $x+y$ is admissible, so the method of proof of (*) invariably also gives (**) as well.

Examples of lower bounds are as follows;

### Brun-Titchmarsh inequality

The Brun-Titchmarsh theorem gives

$\pi(x+y) - \pi(x) \leq (1 + o(1)) \frac{2y}{\log y}$

which then gives the lower bound

$H(k_0) \geq (\frac{1}{2}-o(1)) k_0 \log k_0$.

Montgomery and Vaughan deleted the o(1) error from the Brun-Titchmarsh theorem, giving the more precise inequality

$k_0 \leq 2 \frac{H(k_0)+1}{\log (H(k_0)+1)}.$

### First Montgomery-Vaughan large sieve inequality

The first Montgomery-Vaughan large sieve inequality gives

$k_0 (\sum_{q \leq Q} \frac{\mu^2(q)}{\phi(q)}) \leq H(k_0)+1 + Q^2$

for any $Q \gt 1$, which is a parameter that one can optimise over (the optimal value is comparable to $H(k_0)^{1/2}$).

### Second Montgomery-Vaughan large sieve inequality

The second Montgomery-Vaughan large sieve inequality gives

$k_0 \leq (\sum_{q \leq z} (H(k_0)+1+cqz)^{-1} \mu(q)^2 \prod_{p|q} \frac{1}{p-1})^{-1}$

for any $z \gt 1$, which is a parameter similar to $Q$ in the previous inequality, and $c$ is an absolute constant. In the original paper of Montgomery and Vaughan, $c$ was taken to be $3/2$; this was then reduced to \sqrt{22}/\pi and then to $3.2/\pi$. It is conjectured that $c$ can be taken to in fact be $1$.