5
$\begingroup$

Given a single variable real polynomial $p(x)$ of degree $n$ that maps integers to integers, show that $n!\cdot p(x)$ has integer coefficients.

I prefer an elementary solution if possible. It seems like some big machinery to take care of this should exist as well but I don't know any names.

For example, if $n=4$, some polynomial like $p(x)=\frac{(x-3)(x-8)(x-50)(x-13)}{24}$ works since $3,8,50,13$ are congruent to $3,0,2,1$ mod $4$. Any integer linear combinations of polynomials of this form works. But I can't say that these are the only possibilities.

What I typed earlier in the preceding paragraph is not correct. I meant polynomials such as $p(x)=\frac{(x-4)(x-5)(x-6)(x-7)}{24}$ works since the product of any $k$ consecutive integers is divisible by $k!$.

$\endgroup$
2
  • 1
    $\begingroup$ I just found the following which is related but gives no proof. math.stackexchange.com/questions/455041/… $\endgroup$
    – domoremath
    Sep 5, 2013 at 0:38
  • $\begingroup$ The claim made in the third sentence of that post would, if I'm not mistaken, imply this result. That might be the applicable "big machinery". $\endgroup$ Sep 5, 2013 at 1:16

2 Answers 2

7
$\begingroup$

Two words: Finite differences.

If $q$ is a polynomial, define another polynomial $\Delta q$ via: $(\Delta q)(x) = q(x+1)-q(x)$. Clearly, $\Delta^k p(0)$ is an integer for all $k$.

Then we know that $$p(x)=\sum_{k=0}^n \frac{\Delta^k p(0)}{k!}(x)_k$$

Where:

$$(x)_k = x(x-1)\cdots(x-k+1)$$


A similar proof, but with some proof of the finite difference result, is to note that the polynomial $(x)_k$ is of degree $k$, and we have $(x+1)_k-(x)_k=k(x)_{k-1}$. So every polynomial can be written uniquely as:

$$p(x)=\sum_{k=0}^{n} a_k(x)_k$$ where $n=\deg p(x)$. We then prove by induction that $a_k \cdot k!$ must be an integer.

If $p:\mathbb Z\to\mathbb Z$, we always have $a_0=p(0)\in\mathbb Z.$

Now $\Delta p:\mathbb Z\to\mathbb Z$, and:

$$\Delta p(x)=p(x+1)-p(x)=\sum_{k=0}^{n} ka_k(x)_{k-1}.$$

Since $p$ is smaller degree, by induction, you have that $k!a_k=(k-1)!ka_k\in\mathbb Z$ for each $k>0.$

$\endgroup$
1
$\begingroup$

I can prove the $n=2$ case with elementary math.

We're saying that $p$ maps integers to integers. That means that $f=2!\cdot p$ maps integers to multiples of $2$. Let's write $f(n)=\frac{r_1}{s_1}n^2 + \frac{r_2}{s_2}n + \frac{r_3}{s_3}$, and we can assume that each fraction has been written in lowest terms. We want to show that $s_1, s_2, s_3$ all equal $1$.

Since $f(0)$ is an integer, we immediately have that $s_3=1$.

Since $f(1)$ is an integer, we have that $\frac{r_1}{s_1} + \frac{r_2}{s_2}$ is an integer, so $s_1=s_2$. Let's just call it $s$.

Since $f(1)$ and $f(2)$ are both even integers, we have that $r_1 + r_2$ and $4r_1 + 2r_2$ are both multiples of $2s$. Subtracting twice the first expression from the second one, we obtain that $2s$ also divides $2r_1$, which implies that $s|r_1$. However, $r_1$ and $s$ are relatively prime, so $s=1$, q.e.d..

I don't immediately see how this type of argument would gracefully extend to higher degree polynomials, but it might.

$\endgroup$
2
  • $\begingroup$ I suppose if I want to be very rigorous, I would need to show that the $\frac{r_i}{s_i}$ coefficients can't be irrational. $\endgroup$
    – domoremath
    Sep 5, 2013 at 1:18
  • 2
    $\begingroup$ That's clear by solving a linear system. You can solve for the coefficients of a degree $n$ polynomial by knowing $n+1$ values of it. Cramer's rule show's that the solutions of this system, i.e. the coefficients of your polynomial, are rational. $\endgroup$ Sep 5, 2013 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.