The number of certain integral polynomials and nonrecursive sets of integers, Part 1

Abstract:

Given $r > 2$, we establish a good upper bound for the number of multivariate polynomials (with as many variables and with as large degree as we wish) with integer coefficients mapping the “cube” with real coordinates from $[-r,r]$ into $[-t,t]$. This directly translates to a nice statement in logic (more specifically recursion theory) with a corresponding phase transition case of 2 being open. We think this situation will be of real interest to logicians. Other related questions are also considered. In most of these problems our main idea is to write the multivariate polynomials as a linear combination of products of scaled Chebyshev polynomials of one variable.