[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