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

Question

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$)?

Answer 1

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