Re: ranges of integer polynomials

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?

the example mentioned earlier
reduces to 1 + x^2
for example

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar

.

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: Things get nicer at some huge number?
    ... If Pis a mathematical statement with one free variable n that ... ranges over the positive integers, then there is a number B_P ... of the length of the statement of the conjecture. ...
    (sci.math.research)
  • Re: Possible results from three variables
    ... For positive integers n,k, let fbe the number of possible ... subgroup of R^m, i.e. a lattice. ... Let K be the polytope ... polynomials in k with rational coefficients. ...
    (sci.math)
  • Re: No Putnam spoilers please!
    ... Canada in 2009 today on Saturday 5 December, ... Also some students may take exams on Sunday because of ... The balanced polynomials of ...
    (sci.math)
  • Re: Possible results from three variables
    ... For positive integers n,k, let fbe the number ... since they have combinatorical meaning in a similar way to the original question here. ... and also some kind of Ehrhart polynomials, but ill stick with euler at first sight. ...
    (sci.math)