# 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 '11 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 '11 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 '11 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 '11 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 '11 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 '11 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 '11 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 '11 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 '11 at 0:17
• @Greg Yes, you are probably right. Without GRH we can't do much. – Felipe Voloch Nov 14 '11 at 14:36

I am sorry to parasite this venerable question with something which is less an answer than another question, but is the theorem of Lagarias, Odlyzko, Weinberger you mention even proved under GRH ? (you ask if it is true without GRH).

I assume the paper of Pascal Koiran you refer to is this one. One finds indeed in section 5 the theorem you state, and the proof is essentially a reduction to Lemma 3 of this article by Adleman and Odlyzko (and not by Lagarias and Odlyzko). Now there seems to be a problem in the proof of Lemma 3, already in the first six lines of that proof. There a prime-counting function $S(x)$ (it counts the primes $p$ up to $x$ with multiplicity $1$ if $P$ has no root mod $p$, $0$ if $P$ has one root mod $p$, $-1$ if $P$ has 2 roots, etc.) and it is said without further justification that the bound $S(x) = x^{1/2} (n \log x + \log D_P)$ (where $n$ is the degree of $P$ and $D_P$ its discriminant) follows from Theorem 1.1 of Lagarias-Odlyzko (that is the famous effective Chebotarev under GRH). But I don't see to which Galois extension of number fields this theorem is applied. It has to be an extension of $\mathbb Q$ since the result is counting prime numbers, not prime ideals in some extension. Let $K$ denotes the field generated by a root of $P$, and $L$ its splitting field; then the theorem would give more or less what is stated if applied to $K/\mathbb Q$, but it can't be applied to that extension because in general it is not Galois. If instead applied to $L/\mathbb Q$, which is Galois, then the degree $n$ has to be replaced by the degree of $L$ which my be as large as $n!$, ruining the estimate.

So I am perplexed... Since there are at least two people here having thought on this kind of results, what am I missing?

• Okay, la nuit porte conseil. I kind of see the arguments now, but their writing is very very sketchy. They apply Effective Chebotarev to the extension $K/K$ which is Galois since trivial. So in other words they just get an effective error term for the prime number theorem for $K$. Then what they must do (without saying a word) is to replace the prime counting function of K by the function counting just prime of degree 1. The error term made by this change is smaller than the error term of the prime number theorem, so that doesn't change anything. But then, one observes that primes... – Joël Jul 10 '13 at 12:26
• of degree 1 in K of norm up to x are of same cardiniality as prime numbers p up to x such that the polynomial P has a linear factors mod p counted with multiplicity equal to the number of linear factor, and we're done. But really, it was too sketchy for me and it took me the reading of Weinberger (which gives independently his own argument, sketchy as well but in a different way) and a good night's sleep to understand it. – Joël Jul 10 '13 at 12:30