4
$\begingroup$

The theorem of Yitang Zhang states that there exist a finite $k \in \mathbb{N}$ such that there exist infinitely pairs of primes $(p,q)$ such that $|p - q| \leq k$. The statement that $k$ can be taken to be 2 is the twin primes conjecture. Currently, a polymath project was able to attain the value $k = 4680$.

Heuristically, based on the twin prime conjecture, one should obtain an estimate of the following type: let $\pi_k(x)$ be the counting functions of primes $p \leq x$ such that $p + k$ is also prime. Then Zhang's theorem implies the existence of some even $k \leq 4680$ such that $$\displaystyle \pi_k(n) \rightarrow \infty$$ and $\pi_k(x)$ should satisfy $$\displaystyle \pi_k(x) \gg \frac{x}{\log^2(x)}.$$

More should be true; indeed we should have an asymptotic of the form

$$\displaystyle \pi_k(x) \sim C \frac{x}{\log^2(x)}$$

for some constant $C > 0$. If $k = 2$, then $C = C_2$, the twin-prime constant.

My question is regarding the existence of efficient algorithms to search for large primes counted by $\pi_k(x)$. My understanding is that the current algorithm used to search for Mersenne primes of the form $2^p - 1$ (due to Lehmer) is efficient mostly because one simply needs to search for large $p$, then run a relatively efficient algorithm to determine the primality of $2^p - 1$. Obviously one does not expect the same level of efficiency with searching for primes counted by $\pi_k(x)$. Nonetheless, has anyone taken on this project? Specifically, has anyone been able to generate a list of large primes of Zhang-type other than existing lists made for twin primes?

$\endgroup$
3
  • 1
    $\begingroup$ My understanding is that Zhang's proof does not convert into an efficient algorithm. To find large twin primes or close-neighbor primes, the best way is probably to repeatedly choose numbers at random (biasing against having small prime factors) and simply test the two numbers for primality. $\endgroup$ Oct 25, 2013 at 13:26
  • $\begingroup$ Is there a nice writeup of the following problem? Given positive integers k and n, count the number of residue classes c such that gcd(c,n)=gcd(c+k,n)=1? Even if n were restricted to primorials, I would be happy to read such a writeup. Gerhard "Will Look At Small Pieces" Paseman, 2013.10.25 $\endgroup$ Oct 25, 2013 at 15:28
  • $\begingroup$ It might be more challenging find a prime $P$ with a proof that there are no more before $P+4860.$ Is one known? It certainly seems likely that all the largest Mersenne primes have this property, however we are only able to discover their primality because of their special form. Testing $P+2310$ might be totally beyond out abilities at this point in time. So are there P small enough to let us check $(P,P+4680)$ for primes yet large enough that there is any reasonable chance that there might not be any there to find? $\endgroup$ Oct 26, 2013 at 6:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.