## Given an integer polynomial, is there a small prime modulo which it has a root?

I am looking at a paper by Pascal Koiran on the computational complexity of certifying the solvability of integer polynomial equations in several variables. With the aid of some important theorems in algebraic geometry, Koiran reduces everything to the following univariate question: Suppose that $f \in \mathbb{Z}[x]$ is a polynomial of degree $D$, and suppose that the $\ell_1$ norm of the coefficients (or the $\ell_\infty$ norm or anything in between; they are all equivalent for this purpose) is bounded by $R$. Then it is a theorem of Lagarias, Odlyzko, and Weinberger that there is a prime $$p = \exp(\text{poly}(\log D,\log R))$$ modulo which $f$ has a root. The only catch is that they assume the generalized Riemann hypothesis. It could be somewhat easier to prove that there is a prime power $q$ of this size and a root in $\mathbb{F}_q$. That seems just as good in context, but in any case there is a prime $p$ that does the job. This theorem is closely related to the "effective Chebotarev density theorem" of Lagarias, Odlyzko, et al.

Koiran needs an ample supply of such primes, but my question is about just finding one. My hunch at the moment is that it is still an open problem to find a $p$ in the range given above unconditionally, in particular without GRH. What is the current status of the question? Could it be easier just to find a root than to establish full effective existential Chebotarev (rather than the density result), or are these equivalent results? Is it viewed as difficult for the same reasons that GRH is difficult, or is GRH just one possible approach?

(By the way, you can get an interesting but inadequate bound unconditionally as follows: $f(x)$ only attains a unit value at most $2D$ times, so choose some other $x$ with $|x| \le D$ and then pick a prime divisor of $f(x)$.)

-
I don't know what to make of any of your ideas, including whether they truly are naive, because I hardly know this material. And while I have nothing against kibbutzing in the comments, what I would really like is an accessible posted answer. – Greg Kuperberg Nov 13 2011 at 4:10
@Timothy Foo: if $G$ acts on itself by translation then only the identity has fixed points, so the obvious lower bound $1/|G|$ is attained. – Noam D. Elkies Nov 13 2011 at 5:15
@Will what I meant was, is there a small prime modulo which $f$ has a root, not really necessarily the first one. – Greg Kuperberg Nov 13 2011 at 8:03
Excuse my naivety, but when you say "is there" don't you mean "can one compute"? Otherwise I don't see what's wrong with taking the smallest prime divisor of the constant coefficient (or another evaluation should that coefficient be invertible). – Marc van Leeuwen Nov 13 2011 at 11:09
@Marc That is a way to get a bound, but you may need a lot of evaluations, so it's not a competitive bound. I refer to this at the end of the post. – Greg Kuperberg Nov 13 2011 at 13:26

My paper Chebyshev's method for number fields, J. de Théorie des Nombres de Bordeaux, 12 (2000) 81-85. has some elementary bounds that can be made effective and also some references. Lagarias and Odlysko also have a version of their theorem without using GRH which is, as expected, much weaker than the version with GRH. I don't think this kind of problem is equivalent to GRH but is certainly much easier with it.

You mention obliquely that it might be enough for your purposes to have just prime powers. Depending on what you are after, it might be a much easier problem.

-
I am happy with any small finite field $\mathbb{F}_q$, not just $\mathbb{Z}/p$. However, the polynomial in Koiran's construction is not usually Galois as assumed in your paper. – Greg Kuperberg Nov 13 2011 at 18:58
As long as you stay away from the few primes that divide the discriminant of the polynomial, what happens depends on the splitting field, so you can take the minimal polynomial of an element that generates that and estimate degree and height of the new polynomial in terms of the old. As for an arbitrary finite field, what's wrong with the splitting field of the original polynomial modulo $2$? Maybe you want to formulate a precise statement you'd like to have. – Felipe Voloch Nov 13 2011 at 20:31
If you work modulo 2 then you do not get the estimate needed for Koiran's theorem, $q = \exp(\text{poly}(\log R,\log D))$. – Greg Kuperberg Nov 13 2011 at 23:33
You do for $R$ large enough and fixed $D$. That's why I am asking for a precise statement. – Felipe Voloch Nov 14 2011 at 0:17
@Greg Yes, you are probably right. Without GRH we can't do much. – Felipe Voloch Nov 14 2011 at 14:36