# [FOM] Prime values of polynomials

Grant Olney Passmore grant at math.utexas.edu
Wed Mar 5 13:19:24 EST 2008

Dear Joe and Vladik,

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

> 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