[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.
>>
>
More information about the FOM
mailing list