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

enter image description here

enter image description here

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


2 Answers 2


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.