Re: ranges of integer polynomials

On Sat, 06 Oct 2007 15:23:03 -0700, adler.math@xxxxxxxxx wrote:

quasi wrote:

problem (8):

If range(f) is a subset of N, must range(f) be recursive?

The answer is no, even if the range of a polynomial with integer
coefficients contains only positive integers, the range need not be
recursive.

I expect you will have no trouble finding a proof, the tools are by
now familiar. However, a preliminary transformation along the
following lines might be useful, it was for me:

If n is a positive integer, let g(n) be the n-th prime, or the n-th
square-free number, or the n-th power of 2 (there are a lot of choices
that work). Note that if A is a set of positive integers, then A is
recursive if and only if g(A) is.

I don't quite see it from the hint you gave above -- please show it.

However here's an argument that should work ...

Let P 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.

Then, letting

f = 1 + P^2

it must be undecidable whether or not 1 is in range(f), hence range(f)
is a subset of N, but not recursive.

quasi
.

Relevant Pages

  • Re: Conjecture (FLT related): another karzeddin-like conjecture
    ... If a,b are positive integers greater than 2, and x,y ... Quasi, the strong hand in supporting science ... Do they search mathematics in other Galaxies? ... Are they still working in SECRETS? ...
    (sci.math)
  • Re: common factors of elements of a recursive sequence
    ... Given positive integers u0,u1,a,b. ... Take any urelatively prime to b, and let p be a prime dividing ... there is some k such that M^k = I (the identity matrix) mod p. ...
    (sci.math)
  • Re: -- more factoring
    ... quasi wrote: ... For all POSITIVE integers n, ... counter-conjectures. ... im not going to call that your conjecture thus. ...
    (sci.math)
  • Re: density of the range of an integer polynomial
    ... quasi wrote: ... else then the y^9 term kicks in and gives terms with zero density. ... The polynomial generates the integers that are not squarefree, ... it generates those positive integers that have a square ...
    (sci.math)
  • Re: ranges of integer polynomials
    ... coefficients contains only positive integers, ... square-free number, or the n-th power of 2 (there are a lot of choices ... Note that if A is a set of positive integers, ...
    (sci.math)