An integer-valued polynomial is a polynomial with real coefficients mapping integers to integers. It is well known that all such polynomials $h(x)$ are generated as an additive group by the binomial coefficients $\binom{x}{n}$. My question concerns the problem of approximating an arbitrary polynomial $f$ with real coefficients on a skillfully chosen interval $I$ of length 1 by means of a skillfully chosen non-zero integer-valued polynomial $h$. Specifically, for $f\in\mathbb{R}[x]$ let $$N(f)=\inf\_{I,h}\,\,\,\, ||f-h||\_{I},$$ where $||\cdot ||\_I$ means sup norm, $h$ runs through all non-zero integer-valued polynomials, and $I$ runs through all intervals of length 1. I am looking for a way to compute $N(f)$, and I have a conjecture (a guess really) that makes this computation very simple. 


$\textbf{Conjecture:}$ Let $D(x)$ be the distance from the real number $x$ to the nearest integer. Then $$N(f)=\inf\_{x\in\mathbb{Z}} \,\,\, D(f(x)).$$


My question is: Can anyone provide a proof or counter-example or some helpful references?
In particular, as a simple test-case, can anyone compute $N(\frac{1}{2}x)$? Maybe the problem is impossibly difficult or ridiculously easy for some reason I don't see, and someone can put me out of my misery.


$\textbf{Remarks:}$


1. It is clear that $N(f)\ge\inf\_{x\in\mathbb{Z}}D(f(x))$, because the closure of every interval of length 1 contains an integer.
2. I suspect that the conjecture is false if one defines $N$ so that $h$ ranges over polynomials with INTEGER coefficients, but I don't have an example to prove this.
3. It is easy to check that $N(0)$=0, and in general $N(c)=D(c)$ for any constant $c$, using the fact that the polynomial $\binom{x}{n}$ tends to 0 uniformly on $[0,1]$ as $n$ tends to infinity.
4. I'm already stuck on the computation of $N(\frac{1}{2}x)$, which is 0 according to the conjecture. One would naturally consider intervals $I$ of the form $[2n-\frac{1}{2},2n+\frac{1}{2}]$, and look at polynomials of the form $h(x):=\sum\_{k}c\_{k}\binom{x}{k}$, such that all the $c\_{k}$ are integers and $h(2n)=n$.



Approximating polynomials in R[x] using integer-valued polynomials

> 
> I would be grateful if you could spell out some details in an answer. 
> 
> 
> 


OK, let's do the details. 


Start with any continuous function $f$ on $[-0.9,0.9]$ that is $0$ in some open neighborhood of the origin. Let $g$ be its even part. Then $f-g$ is odd and also vanishes near the origin. Thus, we can write it as $xh$ where $h$ is even and vanishes near the origin. So, the problem of approximating an arbitrary such $f$ by a polynomial with integer coefficients is reduced to the even case.


Now, every even $f$ of this form can be written as $F(x^2)$ for some continuous $F$ on $[0,0.81]$ vanishing in some neighborhood of the origin, so it is enough to do the approximation of $F$ on $[0,0.81]$. Extend $F$ to a continuous function on $[0,1]$ so that it vanishes in some neighborhood of $1$ too. Now write the Bernstein polynomial $P(x)=\sum\_{k=0}^n f(\frac kn){n\choose k}x^k(1-x)^{n-k}$. For large $n$, the difference between $F$ and $P$ is small. Note that $f(\frac kn)=0$ for $k/n$ close to $0$ and $1$. 


Let $N\_k=\lfloor f(\frac kn){n\choose k}\rfloor$. Let $Q(x)=\sum\_{k=0}^n N\_k x^k(1-x)^{n-k}$. The difference between $P$ and $Q$ is also small (because $\sum\_{k=1}^{n-1} x^k(1-x)^{n-k}\le n^{-1}\sum\_{k=0}^n {n\choose k}x^k(1-x)^{n-k}=n^{-1}$).


Moral: every continuous $f$ vanishing in some neighborhood of the origin can be approximated by polynomials with integer coefficients on $[-0.9,0.9]$.
Thus, every continuous $f$ vanishing at the origin can be approximated too. 


Now take your original function $f$. Without loss of generality, $D(f)=f(0)$. Approximate $f-f(0)$ and you are done. 


