[FOM] 317: Polynomials and PA

[pax0@seznam.cz]

  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.