[FOM] Prime values of polynomials

zahidi@logique.jussieu.fr zahidi at logique.jussieu.fr
Thu Mar 6 03:37:01 EST 2008

Sorry to contradict

The set of prime numbers is NOT the range (as the variables range over the
natural numbers - or integers, that is the same) the of a polynomial with
integer coefficients. However, according to the MDPR-theorem there does
exist a polynomial such that the positive numbers in its range are the
prime numbers.

It is ofourse true that this polynomial has infinitely many prime values.
So Joe's statement is not correct.


Karim Zahidi

Le Mar 4 mars 2008 18:52, Kreinovich, Vladik a écrit :
> According to Matiyasevich's theorem, every recursively enumerable set of
> natural numbers is a range of some polynomial with integer coefficients.
> This means that, in particular, the set of all prime numbers can be
> represented as such an image. There are explicit examples of such
> polynomials, e.g., in the latest Notices of the AMS. Such polynomials take
> infiitely many prime values. So, contrary to what you read, such
> polynomials are well known.
> -----Original Message-----
>> From joeshipman at aol.com
> I have read that no integer-coefficient polynomials of degree >1 are
> known to take infinitely many prime values.
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom

More information about the FOM mailing list