The starting point for this question is the following (false) statement



> 
> 
> > 
> > $\forall n\in \mathbb{N} (n^2 + n + 41 \text{ is prime}).$
> > 
> > 
> > 
> 
> 
> 


Given a polynomial function $p:\mathbb{N} \to \mathbb{N}$ we define $$\text{prime}(p) = \{n\in\mathbb{N}: p(n) \text{ is prime}\}.$$


For $A\subseteq \mathbb{N}$ we define the upper density by $$\operatorname{ud}(A)=\limsup\_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n}.$$


Is there a non-constant polynomial $p$ such that $\operatorname{ud}(\text{prime}(p)) > 0$? 


If yes, what is $\sup\{\operatorname{ud}(\text{prime}(p)): p:\mathbb{N}\to\mathbb{N} \text{ is a non-constant polynomial}\}$?



Upper density of the set of $n$'s such that $p(n)$ is prime, where $p$ is polynomial
The density will always be $0$.


Using the [sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) and the [Chebotarev density theorem](https://en.wikipedia.org/wiki/Chebotarev%27s_density_theorem) we can prove that for any positive irreducible polynomial $F\in\mathbb{Z}[X]$, $$\#\left\{ n\leq x:\ F(n)\text{ is prime}\right\} \ll\_F\frac{x}{(\log\log x)^{1-o(1)}}.$$ This can be improved to $\ll\_F\frac{x}{\log x}$ by using either the [fundamental lemma of the Sieve](https://en.wikipedia.org/wiki/Fundamental_lemma_of_sieve_theory), or the [Selberg Sieve](https://en.wikipedia.org/wiki/Selberg_sieve).




---


*Proof:* Lets sieve out by $P(z)=\prod\_{p\leq z}p$. Define $$\mathcal{A}=\left\{ F(n):\ n\leq x\right\},$$
and $$S(\mathcal{A},z)=\left|\left\{ a\in\mathcal{A}:\ \gcd(a,P(z))=1\right\} \right|.$$
 Then $$\#\left\{ n\leq x:\ F(n)\text{ is prime}\right\} \leq z+S(\mathcal{A},z).$$
Set $\mathcal{A}\_{d}=\left\{ a\in\mathcal{A}:\ a\equiv0\text{ mod }d\right\}$. Then since $$\sum\_{d|n}\mu(d)=\begin{cases}
1 & \text{if }n=1\\
0 & \text{otherwise}
\end{cases}$$
 we may write $$S(\mathcal{A},z)=\sum\_{\begin{array}{c}
a\in\mathcal{A}\\
(a,P(z))=1
\end{array}}1=\sum\_{a\in\mathcal{A}}\sum\_{d|a,\ d|P(z)}\mu(d)=\sum\_{d|P(z)}\mu(d)\sum\_{\begin{array}{c}
a\in\mathcal{A}\\
d|a
\end{array}}1=\sum\_{d|P(z)}\mu(d)|\mathcal{A}\_{d}|.$$
 Now let $$v\_{F}(d)=\left|\left\{ m\in\mathbb{Z}/d\mathbb{Z}:\ F(m)\equiv0\ (\text{mod}\ d)\right\} \right|.$$
 Then $$|\mathcal{A}\_{d}|=v\_{F}(d)\left(\frac{x}{d}+O(1)\right)=x\frac{v\_{F}(d)}{d}+O(v\_{F}(d)),$$
 and so $$S\left(\mathcal{A},z\right)=x\sum\_{d|P(z)}\mu(d)\frac{v\_{F}(d)}{d}+O\left(\sum\_{d|P(z)}v\_{F}(d)\right).$$
 Since $v\_{F}(d)\leq(\deg F)^{\omega(n)},$
 we have that $$S\left(\mathcal{A},z\right)\leq x\prod\_{p\leq z}\left(1-\frac{v\_{F}(p)}{p}\right)+O\left((2\deg F)^{\pi(z)}\right).$$
 Now, by the [Chebotarev density theorem](https://en.wikipedia.org/wiki/Chebotarev%27s_density_theorem) $$\frac{1}{\pi(x)}\sum\_{p\leq x}v\_{F}(p)=1+o(1),$$ which implies that $$\prod\_{p\leq z}\left(1-\frac{v\_{F}(p)}{p}\right)\ll \frac{1}{(\log z)^{1-o(1)}},$$
 and so $$S\left(\mathcal{A},x\right)\ll\_{F}\frac{x}{(\log z)^{1-o(1)}}+(2\deg F)^{\pi(z)}.$$
 Choosing $z=\log x/2,$
we obtain the desired result $$\#\left\{ n\leq x:\ F(n)\text{ is prime}\right\} \ll\frac{x}{(\log\log x)^{1-o(1)}}.$$


