A function asymptotical equivalent with the prime counting function?

Question

Let $p_n$ be the $n$-th prime number and $Q_a(N)$ be the number of primes of the form $p_n^2+a$ where $1\leq n\leq N$ and $a$ is positive and even. For some $a$ like $26,56$ it seems that no solutions to $p_n^2+a\in\mathbb P$ exist, for some $a$ like $2,8$ there seems to be a unique solution and for some $a$ like $4,12$ there seems to be an unlimited number of solutions. The diagrams below is of $Q_4(N)$ (blue) and the function $\frac{N}{\ln N}$ (red).

My question, is it possible to prove that $Q_4(N)\sim\frac{N}{\ln N}$?

Answer 1

This is closely connected to Schinzel's Hypothesis H and the Bateman-Horn conjecture. A slightly different way to phrase this question would be to consider the two polynomials $(x, x^2 + 4)$, and look for values $x \leq X$ such that both polynomials are simultaneously prime.

Our current understanding of number theory is insufficient to answer this question. In fact, we don't currently know whether the polynomial $x^2 + 4$ takes on infinitely many prime values, let alone simultaneously prime values as $x$. More broadly, we don't know any example of a quadratic polynomial that is prime infinitely often.

Schinzel's Hypothesis H gives certain conditions about when to expect sets of polynomials to take on infinitely many prime values, and the Bateman-Horn conjecture suggests an expected density.

For the pair $(x, x^2 + 4)$, the Bateman-Horn conjecture would suggest that the number of $x \leq N$ giving simultaneous primes (which I'll call $P_4(N)$) should be about $$ P_4(N) \approx \frac{2.2106}{2} \int_2^N \frac{1}{\log^2 t} dt \sim 1.105 \frac{N}{\log^2 N}. $$

This differs from what you call $Q_4(N)$ in the following important way: $P_4(N)$ considers values $x$ and $x^2 + 4$ with $x \leq N$, but $Q_4(N)$ considers values $x$ and $x^2 + 4$ with $x \leq p_n \approx N \log N$. So we should expect that $Q_4(N) \approx P_4(N \log N)$, or that $$ Q_4(N) \approx 1.105 \frac{N \log N}{(\log (N \log N))^2} \approx 1.105 \frac{N \log N}{(\log N + \log \log N)^2} \approx 1.105 \frac{N \log N}{\log^2 N} \approx 1.105 \frac{N}{\log N}. $$

If you note closely, you can see that many of my approximations are overestimates that become closer to true as $N \to \infty$.

But we are very far from proving that this actually occurs.

Answer 2

Let $S(x,z)$ denote the number of integers $1\le n\le x$ such that $n$ and $n^2+a$ is free of prime factors $<z$. Then it is certain that for all $2\le z\le x$,

$$ Q_a(x)\le z+S_a(x,z) $$

If a prime $p$ divides neither $n$ nor $n^2+1$, then $p$ will not divide $n(n^2+1)$ either. By Euclid's lemma, we can see that the opposite is also true. As a result, let $\nu_d$ denote the number of solutions of

$$ n(n^2+a)\equiv0\pmod d $$

in $\mathbb Z_d$. Then we know that $\nu_d$ is multiplicative and $\nu_p$ is bounded. Thus, by the fundamental lemma of sieve theory we know that there exists a bounded constant $\theta$ such that

$$ S_a(x,z)\ll x\prod_{p<z}\left(1-{\nu_p\over p}\right)+z^\theta $$

The remaining task is to estimate the product in the first term. By the elementary inequality that $1+y\le e^y$ and the basic estimate $\nu_p$, we have

$$ \prod_{p<z}\left(1-{\nu_p\over p}\right)\le\exp\left\{-\sum_{p<z}\frac1p\right\}\ll{1\over\log z} $$

This indicates that

$$ S_a(x,z)\ll{x\over\log z}+z^\theta $$

Setting $z=x^{1/(\theta+1)}$, we find that as $x\to+\infty$, the following bound

$$ Q_a(x)\ll{x\over\log x} $$

holds for all fixed $a$. When $a$ is properly chosen, this estimate might be improved to $O(x/\log^\kappa x)$ for some $\kappa>1$.