Finding narrow admissible tuples

From Polymath1Wiki
Revision as of 10:45, 9 June 2013 by Teorth (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

Zhang sieve

The Zhang sieve uses the tuple

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

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

Hensley-Richards sieve

The Hensley-Richard sieve uses the tuple

[math]{\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]{\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]i[/math] is an integer and [math]i,m[/math] are optimised to minimize the diameter while staying admissible.


Schinzel sieve

Greedy-greedy sieve

Further refinements

Lower bounds

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

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

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

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

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

which then gives the lower bound

[math] 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, giving the more precise inequality

[math] 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 gives

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

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

Second Montgomery-Vaughan large sieve inequality

The second Montgomery-Vaughan large sieve inequality gives

[math] 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]z \gt 1[/math], which is a parameter similar to [math]Q[/math] in the previous inequality, and [math]c[/math] is an absolute constant. In the original paper of Montgomery and Vaughan, [math]c[/math] was taken to be [math]3/2[/math]; this was then reduced to \sqrt{22}/\pi and then to [math]3.2/\pi[/math]. It is conjectured that [math]c[/math] can be taken to in fact be [math]1[/math].


Benchmarks