See bottom. --Rich Quoting Allan Wechsler <acwacw@gmail.com>:
For a polynomial P with coefficients in Z, it's trivial that P(n) is integer if n is.
The converse is not true. There are lots of polynomials that always give integer answers to integer questions, but whose coefficients are not integers. For example, n(n+1)/2 = (1/2)n + (1/2)n^2 always takes integer values for integer n, even though the coefficients aren't integers.
Is there a way to quickly eyeball a polynomial in general to see if it is Z -> Z?
If the coefficients are rational, one can find K = the LCM of the denominators, multiply through by K, and test it for all the integers from 0 to K-1 to see if the result is always divisible by K. But I am hoping there is a simpler way.
If any of the coefficients are irrational, my intuition is that the polynomial is never Z->Z, but I haven't been able to think of an easy proof.
The map from polynomials with integer (or rational, or anything) coefficients to the values at particular integers n is the dot product of the coefficient vector with the power vector [n^d, n^(d-1), ..., n^2, n, 1]. If you know the values at d+1 places, you can write an equation [values] = [coeffs]x[[powers]], where [values] and [coeffs] are vectors, and [[powers]] is a matrix built from the power vectors. As long as there are no duplicated values, the powers matrix is non-singular, so you can solve for the coeffs by inverting [[powers]]. The matrix contains a bunch of fractions, so if the values are rational, so are the coefficients. Rich