Re: ranges of integer polynomials

On Sun, 07 Oct 2007 08:06:34 -0700, adler.math@xxxxxxxxx wrote:

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.

Looks good.

Some very reusable ideas as well.

Thanks.

Thus, as you suggest, it looks like the density problems can also be
resolved by a modified version of the same method.

But let me point out that once again, you replied to the wrong message
in the thread, and of course, you also failed to quote the relevant
parts of the message you should have replied to. Most newsreaders have
an option for automatically quoting the prior message. You can then
manually delete the parts that are not relevant. Also, as a minimum,
the username of prior poster should show at the top, and if there were
nested prior replies (that are relevant), the other usernames should
also show, in reverse time order. If you read a few replies by the
regular posters, you'll see how it's supposed to look.

In any case, if you refer back to the message that you were supposed
to reply to, the one where I asked for your construction, I also gave
a solution of my own for problem (8). Mine seems a lot simpler than
yours, but is it correct?

quasi
.

Relevant Pages

  • Re: How to Generator Prime Numbers in a short time ?
    ... In the time it took you to post that here you could've found all the primes ... This is not so much beating a dead horse as beating the dead ...
    (sci.crypt)
  • Re: How to Generator Prime Numbers in a short time ?
    ... Now I initialize a mucher larger table which contains 4202 primes, ... that once you have found a probable prime you verify it with log/2 MR ... with a base of 2, then verify it with random bases for another 2 times, ...
    (sci.crypt)
  • Re: San Juan Hotels
    ... Louie wrote: ... were looking for a hotel for 1 maybe 2 days prior. ... group bring up replies from 1999- 2007, trying to find some from a ...
    (rec.travel.cruises)
  • Re: pls help calculate previous 10th , 11thand 20th working days from given day
    ... prior date:- yesterdays date ... two replies, one of them being from me. ... as what you have given in your original post is not enough ... please post in the original thread. ...
    (microsoft.public.vb.general.discussion)
  • Re: Active Directory and backup DCs
    ... "Richard G. Harper" wrote in message ... Please check for replies to your prior ... Funny, but there's nothing on the cable company server either. ...
    (microsoft.public.windowsxp.network_web)