5
$\begingroup$

I have 2 questions, but I'll put both of them here since they are closely related:

An integer valued polynomials $P(x)$ is a polynomial whose value $P(n)\in\mathbb{N}$ for every $n\in\mathbb{N}$.

1-I'm given a set of points with integer coordinates, I know it's possible to construct a Lagrange polynomial passing through them, but is it possible to construct an integer-valued polynomial passing through them? If yes, how? (I'm interested in a generic solution, not in one for a specific set of points)

2-I'm given a set of points with coordinates $(x_i,y_i)$ but this time some or all the $x_i$ are rational numbers, is it still possible to construct an integer valued polynomials passing through these points?

Edit: I reposted on MO this question, where it was answered.

$\endgroup$
  • 2
    $\begingroup$ The answer to your first question is yes. This is discussed on Math Overflow, in a very accessible way. $\endgroup$ – André Nicolas Mar 30 '14 at 20:36
  • $\begingroup$ For the second question, we need additional conditions. For example, there is no integer-valued polynomial $P$ such that $P(0)=1$ and $P(\pi)=0$. For an integer-valued polynomial has rational coefficients, and $\pi$ is transcendental. $\endgroup$ – André Nicolas Mar 30 '14 at 21:10
  • $\begingroup$ Thanks for the link, I'm reading it right now. For the second question let's say all the given points have rational coordinates, since it isn't always possible with real ones $\endgroup$ – Alessandro Codenotti Mar 30 '14 at 21:25
  • 1
    $\begingroup$ If $x_i$'s are rational numbers and $y_i$'s are integers, then it is a simple corollary of the first question: there exists a nonzero integer $n$, such that $nx_i$'s are integer, so there exists integer valued polynomial $Q$, s.t. $Q(nx_i)=y_i$. Then $P(x):=Q(nx)$ is a solution. $\endgroup$ – user104254 Apr 2 '14 at 15:51
  • $\begingroup$ Nice answer! I am also interested in the case where both the $x_i$ and the $y_i$ are rational though, any idea about that one? $\endgroup$ – Alessandro Codenotti Apr 2 '14 at 16:30
2
$\begingroup$

1 given arbitrary values $y_0,y_1,y_2,\ldots,y_n$ we can compute the values $p(k)$ of the degree $\le n$ polynomial with $p(j)=y_j$, $0\le j\le n$ with the method of repeated differences. As a consequence, if all $y_i$ are integers, $p(x)$ will be an integer whenever $x$ is an integer. But can we (possibly by switching to a higher degree) ensure that $p(x)$ will be natural for natural $x$? Yes! Just use $m=1$ in the following

Proposition. Given $y_0,\ldots, y_n\in\mathbb Z$ and $m\in\mathbb Z$ there exists a polynomial $P(X)$ such that $P(k)\in\mathbb Z$ for $k\in \mathbb Z$, $P(k)=y_i$ for $0\le k\le n$, and $P(k)\ge m$ for $k>n$.

Proof. The case $n=0$ is easy: If $y_0\ge m$ take $P(x)=y_0$; and if $y_0< m$, take $P(x)=(m-y_0)x-y_0$. For the induction step, consider $y_0'=y_1-y_0,\ldots, y_{n-1}'=y_n-y_{n-1}$ and $m'=\max\{m-y_n,0\}$, find a polynomial $Q$ accordingly and consider $P(k)=y_0+\sum_{i=0}^{k-1}Q(i)$, which is indeed a polynomial (with $Q(x)=P(x+1)-P(x)$ as difference polynomial). The desired properties are readily checked. $_\square$


2 No. Any integer-valued polynomials necessarily have rational coefficients, hence cannot pass through $(\pi,\frac12)$, for example.

$\endgroup$
  • $\begingroup$ Thanks for the answer, however for the second question I was interested in the case where all the coordinates are rational, I wrote it in a comment, but I forgot to edit the question $\endgroup$ – Alessandro Codenotti Apr 9 '14 at 5:10
  • $\begingroup$ Hm, that would translate (in the language of the first proposition) to an additional requirement of the form $q|P(qk)$ for all $qk>n$. This seems to be tricky if $q\not|y_n$ ... $\endgroup$ – Hagen von Eitzen Apr 9 '14 at 6:15

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.