[FOM] Definable sets of primes

[Timothy Y. Chow]

Joe Shipman wrote:
> what kind of achievement is it to detect a "regularity" concerning 
> membership in a polynmial-time-computable set, if the equivalence is to 
> a set that cannot be computed easily? It would make much more sense to 
> me to regard the description "primes modulo which the polynomial f(x) 
> has a root" as the PRIMARY definition of the set, and say that the OTHER 
> set (involving representations of automorphic forms or some such) is the 
> thing in which a "regularity" was discovered!

It's not that the set involving automorphic representations is hard to 
compute; it's that the *verification* that the two sets are the same 
involves some complicated computations that aren't guaranteed to work out.

Generally speaking, once the correspondence has been established, the 
natural and interesting number-theoretic questions about the solutions to 
the polynomial equation are easier to compute from the representation- 
theoretic side than from the number-theoretic side.  That is why Langlands 
regards the automorphic representation side of the correspondence as being 
more "regular" than the number-theoretic side.

Quadratic reciprocity already gives a small hint of this; if you want to 
know "how many" primes p there are for which x^2 - q has a root, it is 
much easier to see the answer if you know that this set of primes has a 
description in terms of congruences mod p.  Note that this is because 
congruence classes have an intelligible structure; it's not just that it's 
easier to compute what p is mod q than it is to factor x^2 - q mod p.

Tim