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

Grant Olney Passmore grant at math.utexas.edu
Fri Mar 7 07:49:10 EST 2008

[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.
>>
>