How can one find all polynomials of degree k that map integers to integers? In other words, how to get all combinations of coefficients

$a_0,...,a_k \in \Bbb R$

sucht that

$n \in \Bbb Z \implies p_k(n) = \sum _{i=0}^{k} a_i n^i \in \Bbb Z$


For example $(n^2 + n)/2$ maps integers to integers and I think

$\{ p_2(n) \space | \space n \in \Bbb Z \implies p_2(n) \in \Bbb Z \} = \{q(n^2+2rn)/2 \space | \space q,r \in \Bbb Z\}$

  • $\begingroup$ See also this. The link in Marty Cohen's answer is what you want I think. Well, lhf gives another way of looking at it. $\endgroup$ Oct 2 '17 at 16:40
  • $\begingroup$ This is called an "arithmetic polynomial" IIRC, and probably many algebraic geometry textbooks for example would have a discussion of them. (There, they arise in the definition of the arithmetic genus of a projective scheme.) $\endgroup$ Oct 2 '17 at 19:26
  • $\begingroup$ The book by Cahen, Chabert, Integer-valued polynomials, American Mathematical Society (1997) is related to your question. $\endgroup$
    – Watson
    Oct 3 '17 at 12:22

Also $n\mapsto \binom{n}k$ is integer valued for each $k$, and so is any integer linear combination of these: $\sum_{k=0}^m a_k\binom{n}k$. Indeed these are all the integer-valued polynomials. The key to proving this is to note that if $f$ is integer-valued, then $n\mapsto f(n+1)-f(n)$ is also integer-valued.

  • $\begingroup$ could you expand on how $f(n+1) - f(n)$ being integer helps? I dont get it $\endgroup$ Oct 2 '17 at 17:07
  • 1
    $\begingroup$ Think about what this operation does to $f(n)=\binom nk$. $\endgroup$ Oct 2 '17 at 17:08
  • 1
    $\begingroup$ @tobi303: What the answers haven't brought up is that the degree of the polynomial $f(x+1)-f(x)$ is at least one less than the degree of $f(x)$, enabling an inductive argument reducing to the base case of constant polynomials. $\endgroup$
    – user14972
    Oct 3 '17 at 4:29
  • $\begingroup$ @Hurkyl tbh I am not too much interested in a formal proof but mainly how those polynomial look like. In particular I find it interesting that the non-integer factor of a polynomial of degree $k$ is $1/k!$ which completely makes sense, as you need eg at least two terms in $\prod (n+o_i)$ to always get an integer that is divisible by two (in general at least $k$ terms get a result that is divisible by $k$). $\endgroup$ Oct 3 '17 at 17:34

Hint. A polynomial $P(x)$ always takes integer value iff

  1. $P(0) \in \Bbb{Z}$.
  2. $Q(x)$ always takes integer value, where $Q(x) = P(x) - P(x-1)$.

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.