Re: ranges of integer polynomials

On Sun, 07 Oct 2007 01:37:54 -0400, quasi <quasi@xxxxxxxx> wrote:

On Sun, 07 Oct 2007 04:56:16 -0000, galathaea <galathaea@xxxxxxxxx>
wrote:

On Oct 6, 4:46 pm, quasi <qu...@xxxxxxxx> wrote:
On Sat, 06 Oct 2007 15:23:03 -0700, adler.m...@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.

earlier
i had defined "elliptic" polynomials
as a polynomial E suchThat

#_n := #{X | |P(X)| <= n}
is finite for all n
with convexDiameter({X | |P(X)| <= n}) <= N(n)

( ie. there is a bounded closed set
which contains all possible points )

these have recursive ranges

for any such E(x1, x2, ..., xn)
there are dimensional inflations
like E(a y1 - b x1, g(x2, z1, z2, z3), ...)
which are not elliptic
but have the same recursive ranges

which of these other, "hyperbolic", polynomials
have recursive ranges?

are they always these ones that have dimensional reducibility
in the manner illustrated?

or are there recursive ranges not covered
by reducibility to an elliptic form?

Good question.

This gets at the heart of the undecidability issue.

In essence, it appears that you are trying to identify the boundary
between the decidable equations and the undecidable ones.

It would be surprising if the boundary were itself decidable, since if
it was, you would know which side you were on.

I think we simply have to settle for fencing in regions of
decidability, regions not ruled by Matiyasevich.

For example, your "elliptic" polynomials.

We may be able to extend the recursive region to include some
recursive non-elliptic ("hyperbolic"?) polys, thus saving them from
the badlands where non-recursive polys run amok.

I should be careful about terminlogy here.

Every integer polynomial is a recursive function.

Every integer polynomial has a recursively enumerable range.

Not every integer polynomial has a recursive range, not even the ones
for which the range values are all nonnegative.

So when I called some polys "non-recursive" above, I meant that they
had non-recursive _ranges_.

Perhaps the terminolgy "range-recursive" or "range-non-recursive"
would prevent possible confusion.

Perhaps start with some examples, then try to bring in whole classes.

quasi
.

Relevant Pages

  • Re: ranges of integer polynomials
    ... Note that if A is a set of positive integers, ... but have the same recursive ranges ... which of these other, "hyperbolic", polynomials ... This gets at the heart of the undecidability issue. ...
    (sci.math)
  • Re: ranges of integer polynomials
    ... Note that if A is a set of positive integers, ... which of these other, "hyperbolic", polynomials ... This gets at the heart of the undecidability issue. ... the badlands where non-recursive polys run amok. ...
    (sci.math)
  • Re: polynomial diophantines and derivatives ?
    ... non-solutions in one variable of a polynomial diophantine equation. ... Does that undecidability always comes from undecidable polynomial diophantine ... radius of convergeance, and we cant decide wheither or not a potential E ... when you're talking about polynomials in one variable. ...
    (sci.math)
  • Re: polynomial diophantines and derivatives ?
    ... A sequence of integers has property T if all the ... Let that diophantine equation be E. ... Does that undecidability always comes from ... so the polynomials are not restricted to one variable. ...
    (sci.math)
  • Re: question on complexity theorem proposition
    ... terminates on all input) than of course the property is undecidable. ... yielding a predicted execution time. ... Here is the idea of the proof of undecidability: ... polynomials. ...
    (comp.theory)