Re: ranges of integer polynomials

On Sat, 06 Oct 2007 00:57:13 -0400, quasi <quasi@xxxxxxxx> wrote:

Let f be an integer polynomial, possibly multivariate, and let
range(f) denote the range of f for all integer inputs.

problem (6):

Must at least one of the sets

(range(f) intersect N)

(range(-f) intersect N)

be recursive?

No, not necessarily.

Let P(x_1,...,x_n) be an integer polynomial such that it's undecidable
whether or not the diophantine equation P = 0 has integer solutions.
Such a polynomial must exist by the results of Matiyasevich.

Let Q(y_1,...,y_n) be identical to P except Q has the variables
y_1,...,y_n instead of x_1,...,x_n. Then of course, the equation Q = 0
is also undecidable.

Let g = 2P^2 + (Q^2 + 1)*z^2

Consider the separate equations g = 0 and g = 1.

g = 0 <=> P = 0 and z = 0 which is undecidable since P = 0 is
undecidable.

g = 1 <=> P = 0 and Q = 0 and (z = 1 or -1), which is undecidable
since P = 0 and Q = 0 are both undecidable.

Now let f = 2g - 1.

Is 1 in range(f)?

f = 1 <=> g = 1 which is undecidable.

It follows that (range(f) intersect N) is not recursive.

Is 1 in range(-f)?

-f = 1 <=> g = 0 which is undecidable.

It follows that (range(-f) intersect N) is not recursive.

Therefore the answer to problem (6) is "no".

quasi
.

Relevant Pages