Let $P(x)$ be a non-constant polynomial with real coefficients.
Can natural density of
$$\{n\ |\ \lfloor P(n)\rfloor \ \text{is prime.}\}$$
be positive?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityLet $P(x)$ be a non-constant polynomial with real coefficients.
Can natural density of
$$\{n\ |\ \lfloor P(n)\rfloor \ \text{is prime.}\}$$
be positive?
No. There are two cases. Firstly, suppose that one of the non-constant coefficients of $P$ is irrational. Then, by the Weyl equidistribution theorem, $\lfloor P(n) \rfloor$ is equidistributed mod $W$ for any modulus $W$, which already limits the natural density of the prime-producing $n$ to be at most $\phi(W)/W$ for any $W$, which implies zero density by taking $W$ to be a product of all the primes less than a large threshold $w$.
If the non-constant coefficients are all rational, then by passing to a suitable arithmetic progression one can make them all integer, at which point one may as well make the constant coefficient integer as well. Then one can sieve using the Chebotarev density theorem (or Landau prime ideal theorem) as in David's answer. (One should probably get an upper bound of $O(x/\log x)$ for the number of $n \leq x$ with $P(n)$ prime by this method, where the implied constants depend on the coefficients of $P$ of course.)
No. Let $\omega(p)$ be the number of roots of $f$ modulo $p$. Clearly, for any finite set $S$, the upper asymptotic density of your set is bounded by $\prod_{p \in S} (1-\omega(p)/p)$. (Because the probability that $p \nmid f(n)$ is $1-\omega(p)/p$, these probabilities are independent for distinct primes, and $f(n)$ only equals $p$ finitely many times.) We have $ \prod_{p \in S} (1-\omega(p)/p) \leq \exp (- \sum_{p \in S} \omega(p)/p)$.
But the Cebotarov (or Frobenius) density theorem gives that $\sum \omega(p)/p$ diverges to $\infty$, so we may take a finite set $S$ large enough to make $\sum_{p \in S} \omega(p)/p$ greater than any specified $N$.
I'll mention how this fits into the Bateman-Horn conjecture. That says that the density should go to $0$ like $\prod \frac{p-\omega(p)}{p-1} \cdot \frac{x}{\log f(x)}$, where the cool thing is that the product converges to a nonzero number if and only (1) $f$ is irreducible and (2) $\omega(p) \neq p$ for any $p$. But all I need to answer your question is an upper bound of $\prod_{p \leq N} \frac{p-\omega(p)}{p} \cdot x$.
The Bateman-Horn conjecture says no. See this paper of Kevin McCurley for related results.