The number of certain integral polynomials and nonrecursive sets of integers, Part 1 Academic Article uri icon


  • 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. © 2004 American Mathematical Society.

author list (cited authors)

  • Erdélyi, T., & Friedman, H.

citation count

  • 0

publication date

  • October 2004