[FOM] Prime values of polynomials

[Grant Olney Passmore]

Dear Joe and Vladik,

A few comments.

The very nice flavour of the Davis-Putnam-Robinson-Matiyasevich Theorem
that Vladik is referring to as follows:

Theorem: A set of natural numbers is r.e. iff it is the set of all
non-negative integer values assumed by a polynomial with integer
coefficients when it is given non-negative integer values for its variables.

The proof is straight-forward: Given the standard formulation of the
DPRM Theorem (A set of natural numbers S is r.e. iff it is Diophantine),
one observes the following:

 Let D be a polynomial with integer coefficients s.t.
 S = {a \in N |
       Exists x_0, ..., x_{n-1} \in N s.t. D(a, x_0,...,x_{n-1}) = 0}.


 Then, D(a, x_0, ..., x_{n-1}) has a solution in x_0, ..., x_{n-1}

   iff

   (x_n + 1)(1 - D^2(x_n, x_0, ..., x_{n-1})) - 1 = a

 has a solution in x_0, ..., x_n.


**

Thus, as the set of primes is r.e., one can obtain a polynomial s.t.
every non-negative integer value it takes on is prime *whenever* its
variables are given non-negative integer values.

**

The result that Joe is alluding to is as follows:

Theorem: No *univariate* polynomial (in Q[x]) of degree greater than 0
exists that takes on prime values for all integer values of its variable.

This can be observed by simple modulus arguments.

There is a stronger cofinite result:

Theorem: No *univariate* polynomial (in Q[x]) of degree greater than 0
exists that takes on prime values for all but finitely many integer
values of its variable.

This one is tougher.

very best wishes,
Grant
--
Grant Olney Passmore
LFCS, University of Edinburgh


Kreinovich, Vladik wrote:
> 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