[FOM] Prime values of polynomials (fixed text encoding)

[Grant Olney Passmore]

[My following reply to a query by JP is echoed with his permission, in 
case others might find it useful.]
[Notes to moderator:
  (i) Please only accept if you think it might be useful to others! 
  (ii) Text encoding should be fixed, hopefully!]

Dear JP,

Absolutely.  One quick note, in Hilbert's Tenth Problem work, we make
the convention that we separate variables into two sets: ``unknowns''
and ``parameters.''  The parameters are the members of a Diophantine set
being defined by a (partially) existentially quantified Diophantine
equation, and the unknowns are the existentially quantified variables in
a Diophantine definition.

So, in the case of defining the Diophantine set

 S = {a \in N |
         Exists x_0, ..., x_{m-1} \in N s.t. D(a, x_0,...,x_{m-1}) = 0}

 `a' would be the sole parameter and the `x_i's the unknowns.


Theorem: The Diophantine equation

 D(a, x_0, ..., x_{m-1}) = 0

in m unknowns has a solution in x_0, ..., x_{m-1} iff the equation

 (x_m + 1)(1 - D^2(x_m, x_0, ..., x_{m-1})) - 1 = a

has a solution in the m+1 unknowns x_m, x_0, ..., x_{m-1}, provided that
all variables and unknowns are given non-negative integer values.


Proof:

(=>) Let a be s.t. D(a, x_0, ..., x_{m-1}) has a solution in x_0, ...,
x_{m-1}.  Now, consider the equation

 (x_m + 1)(1 - D^2(x_m, x_0, ..., x_{m-1})) - 1 = a

with x_m = a.  That is, as we have

  D(a, x_0, ..., x_{m-1}) = 0

by assumption (for some fixed values of the unknowns), we have

  D^2(a, x_0, ..., x_{m-1}) = 0

and thus

   (a + 1)(1 - D^2(a, x_0, ..., x_{m-1})) - 1
 = (a + 1)(1 - 0) - 1
 = a + 1 - 1
 = a

as desired.

(<=) On the other hand, consider a solution to the equation

 (x_m + 1)(1 - D^2(x_m, x_0, ..., x_{m-1})) - 1 = a.

Clearly, the factor (1 - D^2(x_m, x_0, ..., x_{m-1})) must be positive,
as all unknowns and parameters are assumed to be non-negative (e.g., if
(1 - D^2(x_m, x_0, ..., x_{m-1})) was negative, then a would be
negative, and if (1 - D^2(x_m, x_0, ..., x_{m-1})) was 0, then a would
be negative as well (-1 in particular), which all violate the fact that
a is non-negative).  But, this is possible only when D(x_m, x_0, ...,
x_{m-1}) = 0.  So, we have:

 (x_m + 1)(1 - 0) - 1 = a

yielding

 (x_m + 1 - 1) = a

and thus x_m = a.

--

Please let me know if you have any more questions.

very best wishes,
Grant



pax0 at seznam.cz wrote:
> Hi,
> could you please explain me how one passes from (1) to (2) and back?
> Thank you,JP
>
>>   Let D be a polynomial with integer coefficients s.t.
>>   S = {a \in N |
>>         Exists x_0, ..., x_{n-1} \in N s.t. D(a, x_0,...,x_{n-1}) = 0}.
>>  
>>  
> (1)
>>   Then, D(a, x_0, ..., x_{n-1}) has a solution in x_0, ..., x_{n-1}
>>  
>>     iff
>>  
> (2)
>>     (x_n + 1)(1 - D^2(x_n, x_0, ..., x_{n-1})) - 1 = a
>>  
>>   has a solution in x_0, ..., x_n.
>>  
>