7

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

Eric Naslund
  • 11,255
Dominic van der Zypen
  • 45,374
  • 7
    See Bateman-Horn conjecture –  Jul 14 '15 at 12:12
  • What about 4x+1, half of the primes are of this form... – Per Alexandersson Jul 14 '15 at 12:12
  • 4
    @PerAlexandersson the question is about the number of x for which it is prime, not about the primes attained.// Added: the title of the question is quite misleading –  Jul 14 '15 at 12:16
  • Oops yes - I just corrected the title. Thanks!! – Dominic van der Zypen Jul 14 '15 at 12:20
  • 4
    Sieve of Eratosthenes shows that the density is zero. See any book on sieve theory. (Or Google "Sieve Theory" for less thorough, but adequate treatments.) – Boris Bukh Jul 14 '15 at 12:29
  • @quid: A ok, but that must be almost trivial then, since we know that ALL primes has zero density, so if we restrict to a subset... but on the other hand, we might visit this subset "quicker", so it is no longer trivial... Hmm... – Per Alexandersson Jul 14 '15 at 13:43
  • 2
    @PerAlexandersson as Boris Bukh commented it is not hard to show that the density is zero and for more precise heuristics what the density is see the link I gave. However, it is not completely clear either, since for example the density of primes among numbers of the form $6n-1$ is higher than among all numbers, or simpler among all odd integers there are relatively more primes than among all integers. –  Jul 14 '15 at 13:48
  • 1
    @PerAlexandersson: The set of $n$'s such that $p(n)$ is a prime has zero density. A special case of this statement is that the set of primes has zero density, not the other way (cf. quid's first comment to your earlier comment). For example, the squares also has zero density, yet it is easy to find a polynomial $p$ for which the set of $n$'s such that $p(n)$ is a square has positive density. – GH from MO Jul 14 '15 at 15:56
  • 2
    @BorisBukh: You should give your comment as an answer so that this question can be closed. – GH from MO Jul 14 '15 at 15:58
  • 5
    One may need some fragment of the Chebotarev density theorem in order to guarantee the existence of enough primes that actually sieve out a residue class of $n$'s in the Eratosthenes sieve (maybe the older results of Frobenius are enough for this purpose?). – Terry Tao Jul 14 '15 at 16:21
  • @BorisBukh I agree with GH from MO, please post your comment (along with some explanations) as an answer. – Dominic van der Zypen Jul 15 '15 at 06:34
  • 1
    Does anyone of those who downvoted the question or opted to close it care to tell the reason? To me it seems a reasonable question, and despite some of the comments it seems that an accurate answer isn't that easy. – Peter Mueller Jul 15 '15 at 19:09
  • I agree with Peter Mueller - why was this question downvoted twice? – Eric Naslund Jul 24 '15 at 14:18
  • @EricNaslund I did not downvote the question, but the question as asked is hardly a research-level question. It should be clear to anybody vaguely familiar with this type of problems that the density must be $0$. (How to prove it is a different matter. A question saying: "the density should be $0$ but how can it be proved" would already be better.) –  Jul 24 '15 at 14:55
  • @quid: I mostly agree with you, but many fine questions on math overflow are clear to those familiar with the subject area. For example, here are two good questions that have about $40$ upvotes each and are "hardly research-level": http://mathoverflow.net/questions/96604/exploding-primes/ http://mathoverflow.net/questions/25402/is-the-green-tao-theorem-true-for-primes-within-a-given-arithmetic-progression, – Eric Naslund Jul 24 '15 at 15:40
  • @EricNaslund The fact that OP asked numerous questions of a similar type in the recent past might contribute to a more critical reception. –  Jul 24 '15 at 15:47
  • 2
    @TerryTao: Indeed the older results of Frobenius are sufficient, see my response below. – GH from MO Jul 24 '15 at 16:28
  • @Quid: Fair enough. – Eric Naslund Jul 24 '15 at 16:38

2 Answers2

15

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

Eric Naslund
  • 11,255
  • 1
    A nitpick: the $o(1)$ error term in the Chebotarev estimate only leads to an upper bound of $\ll \frac{1}{\log^{1-o(1)} z}$ rather than $\ll \frac{1}{\log z}$ for the Mertens-type product, which I think worsens the ultimate denominator $\log\log x$ a little to $(\log\log x)^{1-o(1)}$. Not that this makes a difference to the final density, of course. – Terry Tao Jul 25 '15 at 07:46
  • @TerryTao: Thanks for the correction. I would not have guessed that having an asymptotic for $\sum_{p\leq z} v_F(p)$ is not enough to prove that $\sum_{p\leq z}\frac{v_F(p)}{p}=\log \log x+O(1)$, as Mertens proofs don't carry over. – Eric Naslund Jul 25 '15 at 20:41
  • 3
    @TerryTao: Still, going through the explicit formula for the Dedekind zeta function of $K = \mathbb{Q}(\alpha)$ ($\alpha$ a fixed root of $F$), the fact that there are no zeros with $\mathrm{Re}(s) = 1$ yields $\sum_{p < z} v_F(p) \frac{\log{p}}{p} = \log{z} + \mathrm{const} + o(1)$. A partial summation to remove the $\log{p}$ or $1/p$ weights then yields, respectively, the Mertens estimate $\sum_{p < z} \frac{v_F(p)}{p} = \log{\log{z}} + \mathrm{const} + o(1)$, and the quoted $\sum_{p < z}v_F(p) \sim z/\log{z}$ (which is actually Landau's prime number/ideal theorem for $K$). – Vesselin Dimitrov Jul 26 '15 at 05:54
  • @VesselinDimitrov: Good point. On the other hand, I think deriving Landau's prime ideal theorem is a bit more work than applying partial summation on your first display. In fact, your first two displays are analogues of Mertens' theorems, while the prime number theorem lies soewhat deeper. – GH from MO Jul 26 '15 at 10:14
  • 1
    @GHfromMO: Actually Mertens's theorem is at the second display, which is a weakening of the first one. Restricting for simplicity of notation to the rational case, Mertens's $\sum_{p < X} 1/p = \log{\log{X}} + \mathrm{const} + O(1/\log{X})$ is equivalent to $S(X) := \sum_{n < X} \Lambda(n)/n = \log{X} + O(1)$ (which I would say is Chebyshev's theorem). But the fact that the $O(1)$ term here actually converges to a constant (my first display), which turns out to equal $-\gamma$ in this case, is of exactly the same strength as PNT. Both are equivalent to non-vanishing at $\mathrm{Re}(s) = 1$, – Vesselin Dimitrov Jul 26 '15 at 10:31
  • [continued] but the implication $S(X) = \log{X} - \gamma + o(1) \Rightarrow \psi(X) \sim X$ is a single elementary move not passing through the zeros: Partial summation has $\psi(X) = XS(X) - \int_1^X S(t) , dt = X(\log{X} - \gamma+o(1)) - \int_1^X \log{t} , dt + \gamma X + o(X)$, and the constant, whatever it is, cancels (like a constant of integration). – Vesselin Dimitrov Jul 26 '15 at 10:34
  • 1
    @VesselinDimitrov: You are right, I did not notice "const" in your display, I just focused on the asymptotics. Note that your first display without "const" (i.e. in asymptotic form) is Mertens' first theorem when $K=\mathbb{Q}$. – GH from MO Jul 26 '15 at 10:37
  • A quick comment: One can derive the estimate $\sum_{p \le x} \nu_F(p)/p = \log\log{x} + O(1)$ without worrying about zeros of $\zeta_K(s)$ on $\Re(s)=1$; e.g., apply the Tauberian theorem mentioned as Proposition 5 in http://alpha.math.uga.edu/~pollack/eulerprime.pdf to $\log \zeta_K(s)$. Everything needed to check the hypotheses is in Hecke's algebraic number theory book (and goes back to Dedekind, I think). – so-called friend Don Jul 28 '15 at 02:12
  • 1
    An alternative is to use some of the theory of Beurling primes. See http://alpha.math.uga.edu/~pollack/beurling.pdf – so-called friend Don Jul 28 '15 at 02:17
  • Another nitpick: $v_{F}(d)\leq\deg F$ is not exactly right. We can change it to $v_{F}(d)\leq(\deg F)^{\omega(d)}$, where $\omega(d)$ is the number of distinct prime factors of $d$. Now the contribution can be bounded by $(2\deg F)^{\pi(z)}$, which still gives the result. – Dror Speiser Jul 28 '15 at 10:36
  • @DrorSpeiser Thank you, I have made the correction. – Eric Naslund Jul 28 '15 at 14:01
8

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.

GH from MO
  • 98,751