[FOM] Definable sets of primes
joeshipman@aol.com
joeshipman at aol.com
Tue Jun 9 18:51:27 EDT 2009
It is very interesting when a class of sets with a "logical" definition
turns out to be the same as can be obtained by a "mathematical"
definition. (For example, the enumerable sets are the diophantine
sets.) Here is another possible example of this:
Call a set of integers additively definable if it can be defined (in
the language of arithmetic) using only addition. Such a set must (I
think) consist of a fixed set of residue classes for some modulus, up
to finite modifications.
Call a set of PRIMES additively definable (as a set of primes) if it
consists of the primes in an additively definable set of integers.
(These are themselves expressible as the primes in a fixed set of
residue classes for some modulus even without allowing finite
modifications, because each prime is in such a class by itself).
This is a strong restriction -- for example, by Dirichlet and de la
Vallee Poussin, additively definable sets of primes have a density.
But there is another famous condition on a set of primes that forces it
to have a density: by Frobenius and Chebotarev, the set of primes
modulo which a given polynomial has a root has a density. Call such a
set of primes "polynomially definable".
By quadratic reciprocity, one can show that sets of primes definable by
QUADRATIC polynomials are additively definable. But is this true for
all polynomials? In other words, are the classes of additively
definable and polynomially definable sets of primes the same?
Is this either known, or known to follow from some famous conjecture?
-- JS
More information about the FOM
mailing list