# About the prime divisors of values of polynomials

Let $P$ be a polynomial having integer coefficients (and degree $\geq 3$), and let $\mathscr P_P$ be the set of prime numbers dividing some value $P(n)$ with $n \in \mathbb Z$.

Is it true that $\sum_{p \in \mathscr P_P} \frac1 p$ diverges?

The case of polynomials with degree $2$ can be studied by Dirichlet's theorem on arithmetic progressions (I suppose a quadratic-residue argument can be applied for every case), but I am not sure how to study the cases of greater degree.

Any reference or proof (or disproof, which, by the way, would be very surprising) would be appreciated.

• When $P$ is irreducible (which you may assume), it diverges like $\frac{1}{\deg{P}} \log{\log{X}} + \mathrm{const} + o(1)$. While this is "elementary" (modulo some very basic algebraic number theory), you may look up the Chebotarev density theorem for a much more precise result. – Vesselin Dimitrov Jun 6 '15 at 17:18
• @VesselinDimitrov could you provide me a link for the elementary arguments? – Konstantinos Gaitanas Jun 6 '15 at 17:56
• The constant is $1 / \deg P$ only when $P$ is Galois, right? In general it's $n_1/|G|$ where $n_1$ is the number of elements of the Galois group that have at least one fixed point. – Noam D. Elkies Jun 6 '15 at 18:49
• Until I read the answers, I could not understand, or even quite guess, the precise meaning of the question. Is it just me? :) Would it be accurate to say that the first sentence could be helpfully rewritten as "Let $P$ be a polynomial with integer coefficients... and $\{p_i\}$ the prime divisors of its values $P(n)$ for integers $n$"? If so, perhaps it would have archival value to rewrite the question in some such form. – paul garrett Jun 6 '15 at 22:10
• @GHfromMO, I haven't sufficient reputation to edit without approval, so can merely propose (which I did); but it was approved, so (at least from my perspective) all is well. – LSpice Nov 13 '16 at 17:07

We will assume that $f$ is irreducible over $\mathbb{Q}$. Let $\gamma$ be a root of $f$, and let $K = \mathbb{Q}(\gamma)$. By Chebotarv's density theorem, the set $P_f$ of primes $p$ with the property that $f(x) \equiv 0 \pmod{p}$ has at least one root in $\mathbb{F}_p$ has positive relative density in the set of rational primes, and the set of integers with at least one prime factor in $P_f$ has positive density. For each prime in $P_f$, we can solve the congruence $f(x) \equiv 0 \pmod{p}$ in the integers; hence $P_f$ is precisely the set of primes you are looking for. Since $P_f$ has positive relative density in the primes, the sum of their reciprocals will diverge, with the constant as predicted by Chebotarv's density theorem.

I don't think one needs to invoke the Chebotareev Density Theorem here.

Assume that the given sum converges, and let $K$ be a number field generated by any root of $P(x)$. Then, by assumption, the sum of $\mathrm{Norm}(\mathfrak{p})^{-1}$ over the degree $1$ prime ideals $\mathfrak{p}$ in $K$ converges, hence the same holds for the sum of $\mathrm{Norm}(\mathfrak{p})^{-1}$ over all prime ideals $\mathfrak{p}$ in $K$. This implies that the Dedekind zeta function of $K$, $$\zeta_K(s)=\prod_{\mathfrak{p}}\frac{1}{1-\mathrm{Norm}(\mathfrak{p})^{-s}},\qquad \Re(s)>1,$$ tends to a finite limit as $s\to 1+$, while it is known that $\zeta_K(s)$ has a simple pole at $s=1$.

• @VesselinDimitrov: I don't think you can prove the Chebotareev Density Theorem without the zeta function and analysis. In fact, as you point out, this theorem lies deeper as it needs the nonvanishing of Hecke $L$-functions at $s=1$ and more algebraic number theory as well. – GH from MO Jun 6 '15 at 22:49
• @VesselinDimitrov: On the other hand, I agree that my argument could be explained without mentioning $\zeta_K(s)$, namely by operating directly with the reciprocal sum of the norms of prime ideals and the norms of integral ideals. – GH from MO Jun 6 '15 at 22:53
• Certainly not the Chebotarev density theorem. But for $\sum_{p \in S_K(X)} 1/p \leq [K:\mathbb{Q}]^{-1} \, \log{\log{X}} + \mathrm{const} + O_K(1/\log{X})$, with equality when $K/\mathbb{Q}$ is Galois, this is possible. – Vesselin Dimitrov Jun 6 '15 at 23:23
• @VesselinDimitrov: I am somewhat surprised that one can establish such good quantitative results by elementary means, thanks for sharing this information. At any rate, I think the OP was looking for an argument as simple as possible, and I tried to point out that Chebotareev's theorem was an overkill for answering his original question. – GH from MO Jun 6 '15 at 23:27
• I think this type of argument originated in Selberg's paper "An elementary proof of the prime-number theorem for arithmetic progressions" from 1950 (page 71), though he only applies it for a quadratic field, as part of his (long) elementary proof of the prime number theorem in arithmetic progressions. Anyway, it only yields a rather poor lower bound on $L(1,\chi)$ and hence no information on class numbers of quadratic imaginary fields. (Similarly to Mertens's elementary proof, presented on pages 36-37 in Iwaniec-Kowalski, of Dirichlet's theorem.) – Vesselin Dimitrov Jun 6 '15 at 23:47

Assume without loss of generality that $P$ is irreducible, and denote by $S_P(X)$ the set of primes $p < X$ that divide some value $P(n)$. Let $G$ be the Galois group of $P$ and $n_1 > 0$ the number of its elements that have at least one fixed point.

Then, as Noam Elkies says, $$\sum_{p \in S_P(X)} \frac{1}{p} = \frac{n_1}{|G|} \, \log{\log{X}} + \mathrm{const} + O_P\Big( 1 \big/ \log{X} \Big).$$ Here is a sketch of a simple proof in the case that $P$ is Galois (so that $n_1 = 1$ and $|G| = \deg{P}$), yielding the lower bound $|G|^{-1} \log{\log{X}} + O_P(1)$ for the general case.

By partial summation (assume $P$ is Galois here...), this is equivalent to $$\sum_{p \in S_P(X)} \frac{\log{p}}{p} = \frac{1}{\deg{P}} \, \log{X} + O_P(1).$$ Adapt the argument for the variant of Selberg's proof I outlined here of Dirichlet's theorem: Shortest/Most elegant proof for $L(1,\chi)\neq 0$, replacing $\mathbb{Z}[\zeta_N]$ with $A = \mathbb{Z}[\alpha]$ and $V(X)$ by $\prod_{n_i < X^{1/d}} (n_1\alpha^0 + \cdots + n_d \alpha^{d-1})$, where $d := \deg{P}$ and $\alpha \in \mathbb{C}$ is a root of $P$ multiplied (to clear denominator) by the leading coefficient of $P$.

The key point is that the non-zero ideals of $A$, viewed as lattices in the real vector space $A \otimes \mathbb{R}$ and then scaled to have unit volume, belong to a compact subset of the space of unimodular lattices. This is not too hard to see, and can be used by a standard argument to prove that every non-zero ideal $I \subset A$ contains $X/\mathcal{N}(I) + O_P\Big( (X/\mathcal{N}(I))^{1-\frac{1}{d}} \Big)$ of the factors from $V(X)$. (The exponent $1-1/d$ in the error term here is the same as the "trivial" exponent in the $d$-dimensional extension of Gauss's circle problem.) Since $\sum_{p < X} (\log{p})/p^2$ and $\frac{1}{X} \sum_{p < X} (X/p)^{1-\frac{1}{d}}\log{p}$ are bounded as $X \to \infty$, while it is easy to evaluate $\frac{1}{X} \log{|V(X)|} = \frac{1}{d} \log{X} + O_P(1)$, we may conclude a la Chebyshev and Mertens the desired estimate $\sum_{p \in S_P(X)} \frac{\log{p}}{p} = \frac{1}{d} \log{X} + O_P(1)$. (The assumption that $P$ is Galois is used in the relation of rational primes to prime ideals: each sufficiently big prime $p \in S_P(X)$ is contained by exactly $d$ degree-one prime ideals.)

Nonetheless, showing that $\zeta_K(s)$ has a simple pole at $s=1$ and following GH's answer is probably easier than verifying the two claims in my previous paragraph.

• Two comments: Let $N_p(f)$ be the number of roots of $f$ modulo $p$. The better phrasing of the result is $\sum_{p \leq X} N_p(f) \frac{\log p}{p} = \log X + (1)$. This is right for any $f$, Galois or not. The Galois case is special because $N_p(f)$ is always either $0$ or $\deg f$. – David E Speyer Sep 27 '15 at 11:02
• Here is one way to fill in the details on lattice compactness. Write $N$ for the norm function $A \to \mathbb{Z}$. Since $f$ is irreducible, $N(u) \neq 0$ for all $u \in A \setminus \{ 0 \}$. Therefore, if $I$ is an ideal with norm $N(I)$, then $|N(u)| \geq N(I)$ for all $u \in I \setminus \{ 0 \}$. Choosing some positive definite bilinear form on $A \otimes \mathbb{R}$, we deduce that $|u| \geq N(I)^{1/\deg A}$. Minkowski's second theorem en.wikipedia.org/wiki/Minkowski's_second_theorem then tells us that the succesive minima of $I$ are all $\sim N(I)^{1/\deg f}$. (continued) – David E Speyer Sep 27 '15 at 11:10
• Writing $I^{\vee}$ for the dual lattice, we see that all nonzero vectors in $I^{\vee}$ have norm at least $\sim N(I)^{-1/\deg f}$. Evaluate the sum over $I$ by Poisson summation, this fact allows you to ignore all of the terms from nonzero vectors in $I^{\vee}$. – David E Speyer Sep 27 '15 at 11:14
• @David: Thank you for these comments. Indeed, the non-normal case shows the natural statement and proof work "upstairs" - in terms of the degree one prime ideals of a number field $K$ rather than the rational primes $p$. (Or we could use the language of local fields and say that $K \otimes \mathbb{Q}_p$ has exactly one $\mathbb{Q}_p$ factor on average.) I did not think of Poisson summation. Instead I used the Gauss packing argument from his $O(\sqrt{X})$ bound on the circle problem: estimate the number of parallelotopes crossing the boundary of our region, and use the boundedness of lattices. – Vesselin Dimitrov Sep 28 '15 at 0:21
• Namely: The fractional ideals scaled to unit volume partition over the class group of $O_K$ into packets with geometrically nice closures, which should equidistribute in Haar measure on $\mathrm{SL}_d(\mathbb{R}) / \mathrm{SL}_d(\mathbb{Z})$ as $|D_{K/\mathbb{Q}}| \to \infty$ as $K$ runs over all number fields of a fixed degree $d$. This has been proved in the totally real case in [Einsiedler, Lindenstrauss, Michel, Venkatesh, Distribution of periodic torus orbits on homogeneous spaces]. For $d = 2$ this is Duke's equidistribution theorem on CM points and closed geodesics on modular surface. – Vesselin Dimitrov Sep 28 '15 at 0:46