Upper density of the set of $n$'s such that $p(n)$ is prime, where $p$ is polynomial 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}\}$?
 A: This is a supplement to Eric Naslund excellent answer, and also an elaboration of Terry Tao's comment above. The crucial asymptotic formula
$$\frac{1}{\pi(x)}\sum_{p\leq x}v_{F}(p)=1+o(1)$$
also follows from two 19th century results: the Frobenius theorem on splitting types and the Cauchy-Frobenius orbit counting lemma (also known as Burnside's lemma). 
Indeed, consider the Galois group $G$ of the splitting field of $F$ over $\mathbb{Q}$ as a permutation group acting on the roots of $F$. The Frobenius theorem implies that the left hand side is asymtotically the average number of fixed points of $G$, which by the Cauchy-Frobenius formula equals the number of orbits of $G$. However, $G$ acts transitively, so the number of orbits equals $1$.
Added 1. As Vesselin Dimitrov pointed out, the above asymptotic formula also follows from Landau's prime ideal theorem (published in 1903).
Added 2. I just learned from the paper Stevenhagen-Lenstra: Chebotarev and his Density Theorem that the above asymptotic formula was originally shown by Kronecker (published in 1880), and this formed the basis of the quoted work of Frobenius of more group theoretic flavor.
A: The density will always be $0$.
Using the sieve of Eratosthenes and the Chebotarev 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, or the 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 $$\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)}}.$$
