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)$.)
Best Answer
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.