Uniform bound for the number primes $p$ s.t. a polynomial has a root modulo $p$

It is well known that for a given polynomial $f \in \mathbb{Z}[x]$ the number of primes $p$ s.t. $f$ has a root modulo $p$ is infinite. In fact, one can even write down a formula for the density of such primes (e.g. D. Berend, Y. Bilu "Polynomials with roots modulo every integer").

Now suppose that $f = \sum_{i=0}^d a_ix^i$ is irreducible, the degree $d$ is fixed and all $a_i \leq N^C$ for some constant $C$. Is it possible to prove the uniform bound (e.g. whith the constant depending only on $d$ and $C$ and $N$ large) $$\pi(N, f) = \Omega_{d, C}(\frac{N}{\log N}),$$ where $\pi(N, f)$ means the number of primes less than $N$ s.t. $f$ has a root modulo $p$?

The aforementioned paper cites a general density formula due to Lagarias and Odlyzko which seem to provide such a bound assuming GRH. It's of course highly desirable to drop this assumption.

As Joel has pointed out this kind of question is delicate, and in fact even in the case $d=2$ no such result is known (for any fixed $C>0$). To see this, suppose that $p$ is a prime for which the quadratic character $\chi(n) = (\frac{n}{p})$ has a Siegel zero. That is there is a $\beta >1-\epsilon/\log p$ with $L(\beta,\chi)=0$. Of course we expect that there is no such character, but this is an important open problem.

Now by the proof of the prime number theorem in arithmetic progressions (see Davenport's book on multiplicative number theory; this is called Page's theorem I think) we have $$\psi(N,\chi) \sim - \frac{N^{\beta}}{\beta},$$ where $\psi(N,\chi) =\sum_{\ell \le N} \chi(\ell) \Lambda(\ell)$. Thus $$\sum_{\ell \le N, \chi(\ell)=1} \Lambda(\ell) \sim \frac 12 \Big( N- \frac{N^{\beta}}{\beta}\Big).$$ If $N\le p^{1/C}$ then the RHS is $\ll \epsilon N$.

To see the implication for your question, take $f(x)= x^2-p$ if $p\equiv 1\pmod 4$, and $f(x)=x^2+p$ if $p \equiv 3\pmod 4$. Then by quadratic reciprocity, if $f(x)\equiv 0 \pmod{\ell}$ has a solution, then $(\frac{\ell}{p})=1$. We have just shown that there are few primes $\ell$ below $N$ for which this happens.

• Thanks a lot. So I accept your answer as now I can safely say that without GRH the problem is hard and wide open. – DmitryZ Apr 9 '14 at 22:09
• @DmitryZ: Note that the obstruction of Siegel zeros mentioned above does not exist for odd degrees $d$, and it is conceivable that something could be proved if $C$ is small enough. I think for $d=3$ and small $C$ this can be done, but would need some work (and I haven't checked all details). – Lucia Apr 10 '14 at 3:39

What you are looking for is probably the effective Chebotarev theorem that B. Winckler made completely explicit.

Since the paper is in French, here are the two main theorems. Let $L/K$ be a Galois extension of number fields, $d_L$ the absolute discriminant of $L$, $n_L$ the degree of $L$ over $\mathbb{Q}$. Let $G$ be the Galois group of this extension and $C$ a subset of $G$ that is stable under conjugation. For all $x>1$, let $\pi_C(x)$ denote the number of prime ideals $\mathfrak{p}$ of $K$ of norm less than or equal to $x$, that do not ramify in $L$ and such that $\bigl(\frac{L/K}{\mathfrak{p}}\bigr)\in C$. Let $\beta$ denote the possible positive zero of $\zeta_L$ such that $0<1-\beta<\frac{1}{4\ln(d_L)}$.

Winckler proves the following unconditional result.

Theorem 1 (Effective Chebotarev theorem) For all $x\ge \exp\bigl(8n_L(\ln(150867d_L^{44/5}))^2\bigr)$, $$\left|\pi_C(x)-\frac{|C|}{|G|}\mathrm{Li}(x)\right| \le \frac{|C|}{|G|}\mathrm{Li}(x^\beta) + C_0 x \exp\left(-\frac{1}{99}\sqrt{\frac{\ln(x)}{n_L}}\right)$$ where $C_0 = 783846699796966 < 7.84\cdot 10^{14}$.

He also gives a conditional version.

Theorem 2 Assume that the Riemann hypothesis holds for $\zeta_L$. Then for all $x\ge 2$, $$\left|\pi_C(x)-\frac{|C|}{|G|}\mathrm{Li}(x)\right| \le \frac{|C|}{|G|}\sqrt{x}\left[\left(32+\frac{181}{\ln(x)}\right)\ln(d_L)+\left(28\ln(x)+330+\frac{1655}{\ln(x)}\right)n_L\right]\text{.}$$

A bound on the coefficients will give you a bound on the discriminant.

EDIT: as remarked by Joël, this does not solve the problem.

• Wow, I did not know about this paper! The guy should get a medal for cleaning this up! – Igor Rivin Apr 9 '14 at 13:07
• I know this paper because the author is a friend of mine. Should I translate the main results in the post ? The paper is in French but I guess it should not be too hard to read. – Aurel Apr 9 '14 at 13:13
• I think just stating the main conditional and unconditional theorems would be useful. By the way, I notice he does NOT thank Oesterle, who claims to still have the notes of his '75(?) unpublished work, and since he is not really interested in working on it, maybe he can share them with Winckler -- his claimed (conditional) constants are a bit better than Winckler's... – Igor Rivin Apr 9 '14 at 13:21
• Correct me if I am wrong but it seems that the unconditional version of the Chebotaryov density is just not strong enough to provide the desired bound (and the conditional version does give it), since the power beta goes to 1 as N is large. – DmitryZ Apr 9 '14 at 18:02
• Actually I take it back: Winckler also mentions the fact that $\beta < 1-1/(cd_L^{1/n_L})$ for some absolute, effectively computable constant $c$. For this result he cites H. M. Stark, Some effective cases of the Brauer-Siegel theorem, Inventiones math., 23 (1974), p. 135–152. This makes the bound completely effective. – Aurel Apr 9 '14 at 18:34

That's a very interesting question and I'd like to know the answer.

Unfortunately, I don't think the unconditional version of Effective Chebotarev will give you anything for your particular problem. The problem is not the chebotarev formula itself, which gives you the desired bound all right, but with the restriction on the range, which in your case gives you that the formula you want is true over a range that is empty. Indeed, the range of the formula for $\pi(f,x)$ is $$x>\exp(8 n_L \log(150867 d_L^{44/5})^2),$$ according to the paper quoted by Aurel (the explicit values of the constants don't matter here, so one could as well quote Lagarias-Odlyzko, or Serre's IHES paper on Chebotarev). Here $L$ is the splitting field of your polynomial $f$, $n_L$ is degree, $d_L$ its absolute discriminant. Now $n_L$ is bounded by $d!$ if $d$ is $deg(f)$ which you suppose constant, so that is no problem. However with your hypothesis on the size of coefficients the best bound that you can expect for $d_L$ is $d_L=O(N^{C'})$ where $C'$ is a constant depending of $C$ and $d$. This gives you a range of the form $x > \exp (c (\log N)^2))$ where $c$ is a constant (depending on $C$ and $d$). You want to apply the theorem for $x=N$, hence you have to assume that $N> exp(c (\log N)^2))$ which is true for at most finite many values of $N$ (possibly none). Hence the Chebotarev approach doesn't work.

(Edited:) For an other approach, besides trying and proving GRH, I would suggest looking at sieve methods. But I'm really no expert...

• Oh right, thanks! I did not check what Chebotarev gave on the actual question... – Aurel Apr 9 '14 at 19:49
• @Aurel, But I am very happy to have heard about this paper by Winckler. I wonder if he can also find values for the constants in the effective version of Chebotarev that you get assuming not only GRH, but also Artin's conjecture (which can be found in the book by Murty and Murty, or in my recent paper "Theoreme de Chebotarev et densite de Littlewood"). – Joël Apr 9 '14 at 20:02
• that would be interesting too! I am no expert on this, but I am certain Bruno would be happy to discuss this if you wrote to him. – Aurel Apr 9 '14 at 20:15
• Je vais le faire. – Joël Apr 9 '14 at 20:16
• The results of Oesterle (as quoted by Serre) and Lagarias-Odlyzko were conditional only (on the GRH for the appropriate Dedekind L-functions), I thought. – Igor Rivin Apr 9 '14 at 21:43