Finding narrow admissible tuples

For any natural number [math]\displaystyle{ k_0 }[/math], an admissible [math]\displaystyle{ k_0 }[/math]-tuple is a finite set [math]\displaystyle{ {\mathcal H} }[/math] of integers of cardinality [math]\displaystyle{ k_0 }[/math] which avoids at least one residue class modulo [math]\displaystyle{ p }[/math] for each prime [math]\displaystyle{ p }[/math]. (Note that one only needs to check those primes [math]\displaystyle{ p }[/math] of size at most [math]\displaystyle{ k_0 }[/math], so this is a finitely checkable condition. Let [math]\displaystyle{ H(k_0) }[/math] denote the minimal diameter [math]\displaystyle{ \max {\mathcal H} - \min {\mathcal H} }[/math] of an admissible [math]\displaystyle{ k_0 }[/math]-tuple. As part of the Polymath8 project, we would like to find as good an upper bound on [math]\displaystyle{ H(k_0) }[/math] as possible for given values of [math]\displaystyle{ k_0 }[/math]. (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 [math]\displaystyle{ p }[/math] from an interval for a lot of primes [math]\displaystyle{ p }[/math]. Examples of sieves, in roughly increasing order of efficiency, are listed below.

Zhang sieve

The Zhang sieve uses the tuple

[math]\displaystyle{ {\mathcal H} = \{p_{m+1}, \ldots, p_{m+k_0}\} }[/math]

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

Hensley-Richards sieve

The Hensley-Richard sieve uses the tuple

[math]\displaystyle{ {\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}\} }[/math]

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

Asymmetric Hensley-Richards sieve

The asymmetric Hensley-Richard sieve uses the tuple

[math]\displaystyle{ {\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}\} }[/math]

where [math]\displaystyle{ i }[/math] is an integer and [math]\displaystyle{ i,m }[/math] are optimised to minimize the diameter while staying admissible.

Lower bounds

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

[math]\displaystyle{ \pi(x+y) - \pi(x) \leq F(y) }[/math] (*)

is established for some function [math]\displaystyle{ F(y) }[/math] of [math]\displaystyle{ y }[/math], the method of proof also gives a bound of the form

[math]\displaystyle{ k_0 \leq F( H(k_0)+1 ). }[/math] (**)

Indeed, if one assumes the prime tuples conjecture, any admissible [math]\displaystyle{ k_0 }[/math]-tuple of diameter [math]\displaystyle{ H }[/math] can be translated into an interval of the form [math]\displaystyle{ [x+1,x+H+1] }[/math] for some [math]\displaystyle{ x }[/math]. In the opposite direction, all known bounds of the form (*) proceed by using the fact that for [math]\displaystyle{ x\gt y }[/math], the set of primes between [math]\displaystyle{ x+1 }[/math] and [math]\displaystyle{ x+y }[/math] 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

[math]\displaystyle{ \pi(x+y) - \pi(x) \leq (1 + o(1)) \frac{2y}{\log y} }[/math]

which then gives the lower bound

[math]\displaystyle{ H(k_0) \geq (\frac{1}{2}-o(1)) k_0 \log k_0 }[/math].

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

[math]\displaystyle{ k_0 \leq 2 \frac{H(k_0)+1}{\log (H(k_0)+1)}. }[/math]

First Montgomery-Vaughan large sieve inequality

The first Montgomery-Vaughan large sieve inequality [MV1973, Theorem 1] gives

[math]\displaystyle{ k_0 (\sum_{q \leq Q} \frac{\mu^2(q)}{\phi(q)}) \leq H(k_0)+1 + Q^2 }[/math]

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

Second Montgomery-Vaughan large sieve inequality

The second Montgomery-Vaughan large sieve inequality [MV1973, Corollary 1] gives

[math]\displaystyle{ k_0 \leq (\sum_{q \leq z} (H(k_0)+1+cqz)^{-1} \mu(q)^2 \prod_{p|q} \frac{1}{p-1})^{-1} }[/math]

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

Benchmarks

[math]\displaystyle{ k_0 }[/math]	3,500,000	34,429	26,024
Upper bounds
Zhang sieve	59,093,364	411,932	303,558
Hensley-Richards sieve	57,554,086	402,790	297,454
Asymmetric Hensley-Richards		401,700	297,076
Lower bounds
MV with [math]\displaystyle{ c=1 }[/math]		234,642
MV with [math]\displaystyle{ c=3.2/\pi }[/math]		234,322
MV with [math]\displaystyle{ c=\sqrt{22}/\pi }[/math]		227,078
Second Montgomery-Vaughan		226,987
Brun-Titchmarsh		211,046
First Montgomery-Vaughan		196,729