# Least prime $p$ such that an irreducible polynomial of degree $n$ has no root modulo $p$?

This question is inspired by an old question of Greg Kuperberg, about how small is the first prime $p$ which makes a given monic polynomial $P$ with integral coefficient have a (simple) root modulo $p$. Now "small" makes sense w.r.t. something, some notion of size of polynomials. In Greg's question the size is measured by the degree $n$ of $P$ and the $L^1$-norm (or $L^\infty$-norm of its coeffcients, but I will rather use as measure of size the degree $d$ and the product $M$ of the primes $p$ dividing the discriminant of $P$ (in short $M$ is the radical of the discriminant of $P$): this is essentially equivalent to Greg's notions but more in line with the literature on the subject.

This being said the result of Weinberger alluded to by Greg is, under GRH, the following:

Theorem : For any $\epsilon>0$, and for any monic polynomial $P$ with integral coefficients, of degree $n$ and radical of discriminant $M$, there is always a prime $p = O(n^{2+\epsilon} (\log M)^{2+\epsilon})$ not dividing $M$ such that $P$ mod $p$ has a root (necessarily simple).

The theorem is proven in this paper of Weinberger (though not stated this way -- near the end of the argument the author stops calculating and just says that the bound is polynomial. I hope my calculation of his bound is correct), and the proof is surprisingly simple. In fact it is so simple that it puzzles me, avoiding all the complications of Lagarias-Odlyzko's effective Chebotarev's theorem (to which the result is closely related, as Greg says) by working with the field $K=\mathbb Q[X]/(P(x))$ even if it is nor Galois (assuming $P$ is irreducible, which one can of course do) rather than its normal closure $L$, which is Galois but can have degree as large as $n!$, which is bad for the polynomial estimate.

To understand better the scope of the method, I ask the following, kind of opposite, question:

Is it true (under GRH or any standard conjecture) that for any monic irreducible polynomial $P$ with integral coefficients, of degree $n$ and radical of discriminant $M$, there is always a prime $p$ not dividing $M$ less than a fixed polynomial in $n$ and $\log M$, such that $P$ mod $p$ has no simple roots ?

(or at least less than a function of $n$ and $\log M$, polynomial in $n$ - I don't really care about the dependence in $M$)?

Let $K$ be the number field obtained by adjoining some root of $f(x)$ to ${\Bbb Q}$, and let $d_K$ be its discriminant. Let $k$ be the degree of $K$, and let $\zeta_K(s) = \sum_{n=1}^{\infty} a(n) n^{-s}$ denote the Dedekind zeta function, and write $-\frac{\zeta_K^{\prime}}{\zeta_K}(s) = \sum_{n=1}^{\infty} \Lambda_K(n)n^{-s}$ so that $\Lambda_K(n)$ is supported on prime powers, and we have $\Lambda_K(p) = a(p) \log p$, and $\Lambda_K(p^{\ell}) \ll k \log p$ for all $\ell\ge 1$. The problem observes that bounding the least prime $p$ for which $a(p)$ is non-zero can be solved on GRH without passing to the normal closure of $K$ (a result of Weinberger) and asks for other properties of $a(p)$ that can be obtained similarly (that is with a polynomial bound in $k$ rather than a $k!$ type bound). The method below shows that any property that can be identified using a polynomial in $a(p)$ of small degree can be studied in such a way. This is illustrated by solving the specific example in the question of bounding the least prime $p$ for which $a(p)$ equals zero.

From GRH for $\zeta_K$ it follows that $$\sum_{n\le x} \Lambda_K(n) (2-2n/x) = x+ O(x^{\frac 12} \log d_K ).$$ This is a mild smoothing, so that I don't have to worry about $\log \log$ powers in the remainder term, but one could also deal just with $n\le x$ without the weight $(2-2n/x)$. As observed in the problem, the method of Weinberger in finding non zero value of $a(p)$ proceeds in this manner, omitting the prime powers which make a smaller contribution (no more than $\ll k\sqrt{x}$): thus $$\sum_{p\le x} a(p)\log p (2-2p/x) = x+ O(x^{\frac 12} (k+ \log d_K)).$$

We now wish to evaluate $\sum_{p\le x} a(p)^2 \log p (2-2p/x)$. This is a Rankin-Selberg type problem, which could be understood by studying the Rankin-Selberg function for $\zeta_K(s)$. Since we are assuming the Artin conjecture, we may write $$\zeta_K(s) = \prod_{j=1}^{r} L(s,\rho_j)$$ where the $\rho_j$ are irreducible representations of the Galois group of the normal closure of $K$ (occurring possibly with multiplicity) and $\sum_{j} \text{dim}(\rho_j) = k$.
Then the Rankin-Selberg $L$-function is $$\zeta_{K\times K}(s) = \prod_{1\le j , \ell \le r} L(s,\rho_j \otimes \overline{\rho_\ell}).$$ Note that the tensor product $\rho_j\otimes \overline{\rho_\ell}$ may be decomposed in terms of irreducible representations of the Galois group, and so by Artin's conjecture the $L(s,\rho_j \otimes{\overline \rho_\ell})$ have a meromorphic continuation (holomorphic except for a pole at $1$) and functional equation, and there is a simple pole at $1$ precisely when $\rho_j$ and $\rho_\ell$ are the same. Thus if the $\rho_j$ consist of $t$ distinct representations occurring with multiplicities $m_1$, $\ldots$, $m_t$ (so that $r=m_1+ \ldots+m_t$) then $\zeta_{K\times K}(s)$ has a pole of order $\sum m_i^2 =R \ge r$ at $s=1$. Further, we may bound the conductor of $\zeta_{K\times K}$ by $d_K^k$. Thus applying GRH we find that $$\sum_{n\le x} \Lambda_{K\times K}(n) (2-2n/x) = Rx + O( kx^{\frac 12} \log d_K).$$ Here $\Lambda_{K\times K}(n)$ denotes the Dirichlet series coefficients of $-\frac{\zeta_{K\times K}^{\prime}(s)}{\zeta_{K\times K}(s)}$, and note that $\Lambda_{K\times K}(p) = a(p)^2 \log p$, and $0\le \Lambda_{K\times K}(p^j) \le k^2 \log p$.
Thus from the above estimate we find that $$\sum_{p\le x} a(p)^2 \log p (2-2p/x) = Rx + O(kx^{\frac 12} (k+\log d_K)).$$

Now suppose that $a(p) \ge 1$ for all $p\le x$. From our first estimate we see that $$\sum_{p\le x} (a(p)-1)\log p (2-2p/x) = O(x^{\frac 12 } (k+\log d_K)).$$ Since $a(p)\le k$ for all $p$ (and $a(p)\ge 1$ by assumption) it follows that $$\sum_{p\le x} a(p)(a(p)-1) \log p (2-2p/x) = O(kx^{\frac 12} (k+\log d_K)).$$ But we also know that $$\sum_{p\le x} a(p)(a(p)-1) \log p (2-2p/x) = (R-1) x + O(kx^{\frac 12} (k+\log d_K)).$$ It follows that $$x\ll \Big(\frac{k(k+\log d_K)}{R-1}\Big)^2.$$

• Thanks a lot Lucia. Actually, shortly after I asked this question and got no answer, I found one myself which is very similar to yours. It is in my paper on arxiv 1308.1022, section 5.2. – Joël Oct 24 '13 at 15:47
• Dear Joel: Thanks very much for the reference to your nice paper. Since the paper is quite long, I don't fully appreciate how close these two arguments are; certainly they seem related. Let me also point out that the argument I gave above of taking Rankin-Selberg would also apply to your results in Section 5.4 (Theorems 22 & 23) and would remove the log log factors you have there (and improve the dependence on $k$ in Theorem 23). That seems different from your argument, in that one does not make any use of Chebotarev here. – Lucia Oct 24 '13 at 21:17
• Dear Lucia, you're right our arguments are not identical. But since they use the same conjectures, a similar use of representations, and arrive at a very close result, I think that a closer analysis (that I will try to look) will show that after unwinding everything they are close. Anyway thanks for the proof, and also for what you say with the log log term in theorem 22 and 23. Actually I recently realize that, as you say, they can be removed using a Rankin-Selberg method and I removed these theorems from the version of my paper I have submitted. This is related to another question of mine... – Joël Oct 25 '13 at 0:42
• on this site, namely mathoverflow.net/questions/129433/… The accepted answer refers to Cojoacru's paper, which does a sort of survey on this question in her introduction, but fails to mention any bound better than the one obtains by Serre in his paper on Chebotarev. Or, as you say, these bound can be improved by removing a log log factor with Rankin-Selberg method. I plan to write an answer to my own question along those line, but feel free to do it if you wish. – Joël Oct 25 '13 at 0:48
• Anyway, thanks again for your comments. It is difficult for an outsider in a field (lime me for the field of analytic number theory) to be sure when one's argument is well-known, or not so well-known but quite easy, or hard, or genuinely new, and your comments and answers help a lot. – Joël Oct 25 '13 at 0:52