7
$\begingroup$

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

Improve this question
$\endgroup$
18
  • 7
    $\begingroup$ See Bateman-Horn conjecture $\endgroup$
    – user9072
    Commented Jul 14, 2015 at 12:12
  • 4
    $\begingroup$ @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 $\endgroup$
    – user9072
    Commented Jul 14, 2015 at 12:16
  • 4
    $\begingroup$ 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.) $\endgroup$
    – Boris Bukh
    Commented Jul 14, 2015 at 12:29
  • 2
    $\begingroup$ @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. $\endgroup$
    – user9072
    Commented Jul 14, 2015 at 13:48
  • 5
    $\begingroup$ 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?). $\endgroup$
    – Terry Tao
    Commented Jul 14, 2015 at 16:21

2 Answers 2

Reset to default
15
$\begingroup$

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

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Terry Tao
    Commented Jul 25, 2015 at 7:46
  • 3
    $\begingroup$ @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$). $\endgroup$
    – Vesselin Dimitrov
    Commented Jul 26, 2015 at 5:54
  • 1
    $\begingroup$ @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$, $\endgroup$
    – Vesselin Dimitrov
    Commented Jul 26, 2015 at 10:31
  • 1
    $\begingroup$ @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}$. $\endgroup$
    – GH from MO
    Commented Jul 26, 2015 at 10:37
  • 1
    $\begingroup$ An alternative is to use some of the theory of Beurling primes. See alpha.math.uga.edu/~pollack/beurling.pdf $\endgroup$
    – so-called friend Don
    Commented Jul 28, 2015 at 2:17
8
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .