[FOM] Definable sets of primes

[joeshipman@aol.com]

Thanks for the reference. I had thought my conjecture might fail with a 
non-abelian Galois group -- but I'd like to see an actual proof that 
there is a specific polynomial, such that the primes mod which it has a 
linear factor can not be characterized by congruences.

Of course this set of primes is decidable for any polynomial by simply 
trying all residues. So it is an interesting foundational question what 
Langlands could have meant by "regularity" in the quote below. Is it 
fair to say that the question whether a prime belongs to the set can be 
answered in time polynomial in log p because of the "regularity" 
Langlands noted?

What worries me is that later in the same paper Langlands says

**
Icosahedral equations, however, remain intractable in general, and even 
for specific examples verifying numerically the validity of the 
regularity suggested is a task that requires great skill and ingenuity 
and is by no means assured of success.
**

For elliptic curves and more complicated equations, there are sweeping 
conjectures about the behavior of the solutions mod p, but I had hoped 
that in my simpler example (a curve that is simply of the form y=f(x) 
for a polynomial f, with no higher powers of y involved) the answer 
would be known unconditionally.

So let me refomulate and sharpen my question:

Does there exist an algorithm to determine whether a given polynomial 
has a root modulo a given prime, which runs in polynomial time? (The 
prime and the coefficients of the polynomial are assumed to be written 
in ordinary decimal notation, including 0 coefficients [no sparse 
polynomials]).

-- JS

-----Original Message-----
From: Timothy Y. Chow <tchow at alum.mit.edu>

    x^5 + 10 x^3 - 10 x^2 + 35 x - 18.

Quoting Langlands: "It is irreducible modulo p for p = 7, 13, 19, 29,
43, 47, 59, ... and factors into linear factors modulo p for p = 2063,
2213, 2953, 3631, ... .  These lists can be continued indefinitely, but 
it
is doubtful that even the most perspicacious and experienced 
mathematician
would detect any regularity.  It is none the less there."

In particular, if you're hoping that the primes p for which that
polynomial has a linear factor modulo p can be described in terms of
congruences, you're out of luck.