15
$\begingroup$

(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.)

In 2013 Zhang showed that there are infinitely many pairs of primes which are less that 70,000,000 apart. Since then, this result has been significantly improved. (See here for the state-of-the-art.) Let $z_n$ denote the $n$th "Zhang prime", that is the $n$th prime $p$ such that the next prime is not more than $p + 70,000,000$. My question is as follows.

Does Zhang's proof or any of its improvements establish a primitive recursive upper bound on the $n$th Zhang prime, that is a primitive recursive function $f(n)$ such that $z_n \leq f(n)$?

A few (trivial) comments for those who don't regularly think about primitive recursive functions:

  • Zhang's result (regardless of the proof) gives a recursive (a.k.a. computable) upper bound, since one just needs to search for the $n$th Zhang prime until it is found. Zhang's result says this search will eventually terminate!

  • By well-known facts of primitive recursive functions, if such a primitive recursive upper bound $f(n)$ exists, then the function $n \mapsto z_n$ is itself primitive recursive.

  • The function $p(n)$, which returns the $n$th prime, is primitive recursive since Euclid's proof shows that there is a prime somewhere between $p(n) + 1$ and $p(n)! + 1$.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ In its most bland form, I think Zhang's original result was ineffective, in that it relied on bounds on Siegel zeros via Bombieri-Vinogradov. However, it is well known how to modify the large sieve in such a way to effectively skirt around a possible exceptional modulus -- see for instance Section 12 of "Primes in tuples II" by Goldston, Pintz, and Yildirim. $\endgroup$
    – NAME_IN_CAPS
    Commented Dec 13, 2014 at 3:30

1 Answer 1

Reset to default
14
$\begingroup$

One does not have to dig too deep into the arguments to answer this. Maynard's formulation (see his preprint here) shows that if $x$ is sufficiently large, there is a Zhang prime (or even a prime $p$ so that $p+k$ is prime with $k \leq 600$) between $x$ and $2x$. It follows that there is a constant $C$ so that $z_{n} \leq C \cdot 2^{n}$, which is primitive recursive. Often in analytic number theory, it's difficult to show that something happens without showing that it happens "a lot".

Improve this answer
$\endgroup$
4
  • $\begingroup$ That was a much better bound than I expected! $\endgroup$
    – Jason Rute
    Commented Dec 13, 2014 at 3:18
  • 3
    $\begingroup$ Does Maynard tell us how "sufficiently large" $x$ must be, or is the result ineffective as stated (one can peel away the exceptional modulus from the large sieve mechanism, but my guess is that Maynard does not do this explicitly)? Or to rephrase more in terms of the original question/answer: is your $C$ effectively computable, or have you just shown the existence of $f(n)$ w/o an explicit function? $\endgroup$
    – NAME_IN_CAPS
    Commented Dec 13, 2014 at 3:35
  • $\begingroup$ Also, I think Zhang had instead of $[x,2x]$, an interval something like $[x,x+x/L(x)]$ where $L(x)$ was some power of $\log\log x$ IIRC. Likely Maynard's argument can show the same. $\endgroup$
    – NAME_IN_CAPS
    Commented Dec 13, 2014 at 4:34
  • 2
    $\begingroup$ Existence of $C$ (effective or not) is enough to answer the OP's question as posed. $\endgroup$
    – Christian Remling
    Commented Dec 13, 2014 at 6:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .