[FOM] 317: Polynomials and PA
pax0@seznam.cz
pax0 at seznam.cz
Fri Feb 1 09:56:02 EST 2008
Theorem B should read
THEOREM B. For all k,r,t >= 1 and polynomials P:Z^k into Z^r, there exist
distinct positive integers x_1,...,x_r+t-1 such that |P^-1(x_1,...,x_r)| <=
... <= |P^-1(x_t,...,x_r+t-1)|.
* k was replaced by r for 3 times*
And a question follows:
what is the status of modified theorem B, stated as follows
THEOREM C. For all k,r,t >= 1 there is a function g:N into N such that
for all polynomials P:Z^k into Z^r, there exist distinct positive integers x_1,...,x_r+t-1 with
|x_1,...,x_r+t-1| < g("code for P") and such that |P^-1(x_1,...,x_r)| <= ... <= |P^-1(x_t,...,x_r+t-1)|.
> #316 uses arbitrary functions on the integers. Here we use polynomials on
> the integers.
>
> Let P:Z^k into Z^r be a polynomial and x in Z^r. We write |P^-1(x)| for the
> Euclidean distance from 0 in Z^k to the pre image of x. I.e., the minimum
> Euclidean norm of the y with P(y) = x. If P^-1(x) is empty, then we take
> |P^-1(x)| to be infinity.
>
> THEOREM A. For all k >= 1 and polynomials P:Z^k into Z^k, there are distinct
> positive integers x_1,...,x_k+2 such that |P^-1(x_1,...,x_k)| <=
> |P^-1(x_2,...,x_k+1)| <= |P^-1(x_3,...,x_k+2)|.
>
> THEOREM B. For all k,r,t >= 1 and polynomials P:Z^k into Z^r, there exist
> distinct positive integers x_1,...,x_k+t-1 such that |P^-1(x_1,...,x_k)| <=
> ... <= |P^-1(x_t,...,x_k+t-1)|.
>
> THEOREM 1. Theorems A,B are provable in ACA but not in ACA_0. In particular,
> not in PA.
More information about the FOM
mailing list