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

```