Re: ranges of integer polynomials

Below is the requested construction of:

A Positive Polynomial whose Range is not Recursive


Let E be a recursively enumerable set of positive integers. For any
non-negative n, let g(n) be the n-th prime.

Let P(x, y_1, y_2, \dots) be a "Matijasevic" polynomial for g(E), that
is, a polynomial such that x is in g(E) if and only if there exist
y_1, y_2, and so on such that P(x, y_1, y_2, \dots) = 0.

Let Q(x_1, x_2, x_3, x_4, y_1, y_2, \dots) be the polynomial

(x_1^2 + x_2^2 + x_3^2 + x_4^2 + 1))(1-3P)^2.


The polynomial Q is positive. If n is in g(E), there are values of
the variables such that P=0, and therefore that Q=n.

For all other values of the variables, (1-3P)^2 is divisible by a
(varying) square greater than 1, and therefore so is Q.

Suppose now that E is non-recursive. The g(E) is non-recursive.
But g(E) is the intersection of the range of Q with the set of primes.
Thus the range of Q cannot be recursive.

A Remark on Density

Variants of this idea can be used to deal with density questions. We
don't want to map to the primes, a thicker set is useful, like the
square-free positive integers. The uninteresting part of the range of
Q will be thin, so, if we are working with g(E) of positive density,
it will not affect the density of the range of Q.



.

Relevant Pages