[math-fun] Rational-coefficient polynomial, applied to integers
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.
Allan, The theorem is as follows: for a positive integer n define f_n(x) = x(x-1)...(x-n+1)/n!, and f_0(x) = 1. These are clearly is integer valued at all integers. Every polynomial with rational coefficients which is integer valued at all integers is an linear combination of the f_n(x) with integer coefficients. The forward direction is obvious. To get the converse, use the difference operater: (Delta g)(x) = g(x+1) - g(x). We have (Delta f_n)(x) = ((x+1) x (x-1) ...(x-n+2) - x(x-1) ...(x-n+1))/n! = (x+1 - (x-n+1)) x (x-1) ... (x-n+2))/n! = f_{n-1}(x). So (Delta^j f_n)(0) = 1 if j=n and 0 otherwise. If g(x) is an integer valued polynomial, then so is (Delta g)(x) Since every polynomial with rational coefficients can be written as sum_j a[j] * f_j(x), applying Delta^r and evaluating at 0, yields a[r]. On Thu, Nov 15, 2018 at 6:08 PM Allan Wechsler <acwacw@gmail.com> wrote:
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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A very old theorem is that a polynomial has the property you want iff it is an integer linear combination of the binomial coefficient polynomials (x choose n). That property can be tested easily by solving a linear system. On 11/15/18 6:06 PM, Allan Wechsler wrote:
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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thank you, Victor, Dan, and Jeffrey. That is a satisfying answer to a question that I think has been stewing in my brain since I first learned the general formula for triangular numbers. On Thu, Nov 15, 2018 at 7:24 PM Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
A very old theorem is that a polynomial has the property you want iff it is an integer linear combination of the binomial coefficient polynomials (x choose n). That property can be tested easily by solving a linear system.
On 11/15/18 6:06 PM, Allan Wechsler wrote:
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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
So, apparently, any polynomial P with P(Z) is uniquely identified by the integer coefficients a[n] in Victor's notation above. You can read off the leading coefficient by multiplying the leading coefficient of P by n!. Then, you can subtract off a[n]F[n] and repeat to get successive coefficients. Starting with an arbitrary polynomial, you can run this algorithm and signal failure if you ever pull out a non-integral a[k]. On Fri, Nov 16, 2018 at 2:22 PM <rcs@xmission.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Allan Wechsler -
Jeffrey Shallit -
rcs＠xmission.com -
Victor Miller