# A function asymptotical equivalent with the prime counting function?

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}$$?

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.

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 $$. 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

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

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$$.