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

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$.

-
stupid comment to 4): there is no difference between [2n-1/2,2n+1/2] and [-1/2,1/2] by some trivial change of variables reasons –  Fedor Petrov Dec 28 '10 at 10:52
and I do not understand 2): does not (x(1-x))^n tend to 0 uniformly on [0,1]? –  Fedor Petrov Dec 28 '10 at 11:53
Fedor, Thanks for the corrections. I did some editing. (Sadly, the edit box cuts off my question at Remark 3.) –  SJR Dec 28 '10 at 12:05
First, use Bernstein polynomials to approximate any continuous on $[0,1]$ function $f$ with $0$ boundary values and replace ${n\choose k}f(k/n)$ by the nearest integer. Second, replace $x$ by $x^2$ to take care of all even functions $f$ on $[-0.9,0.9]$ vanishing at $0$. Third, odd functions are essentially $x$ times even. Last, adjust the value at $0$ by an integer constant. –  fedja Dec 28 '10 at 13:59
For an explicit proof that $N(f) = 0$ for $f(x) = \frac12 x$ consider the polynomials $\frac12(x^n+x)$ on the interval $[-1(2,1/2]$ –  Franz Lemmermeyer Dec 29 '10 at 10:46

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.

-
@fedja: In the second-to-last sentence, I assume you mean $\inf_{x\in\mathbb{Z}}\,\,D(f(x))=f(0)$. But what about $f(x)=(1/2)x+(1/3)$, in which case $\inf_{x\in\mathbb{Z}}\,\,D(f(x))=1/6$? –  SJR Dec 28 '10 at 16:53
@fedja: In any case there must be a problem here, because if $f(x)=(1/2)x+(1/3)$ and if $h(x)$ is any polynomial with integer coefficients, then $|h(0)-f(0)|\ge (1/3)$`, so no polynomial with integer coefficients can be used on the interval [0,1] to prove my conjecture. –  SJR Dec 28 '10 at 17:30
Come on! I wouldn't dream in my worst nightmares that replacing $f(t)$ by $f(t-x)$ with integer $x$ could constitute a highly non-trivial step. OK, let's spell it out. Suppose that $D(f)\approx |f(x)-n|$ for some integer $x,n$. Then we can find an approximant $P(t)$ on $[-0.9,0.9]$ to $g(t)=f(t+x)-n$. But then $P(t-x)+n$ is an integer coefficient approximant to $f$ on $[x-0.9,x+0.9]$ –  fedja Dec 28 '10 at 19:15
OK, This makes sense to me, and quite contradicts my expectations. I might add, we could all have done without your scornful little "in my wildest dreams" comment. I was trying to understand your writing, not baiting you –  SJR Dec 29 '10 at 6:32
Sorry, I often write (and speak) more emotionally than needed. I apologize if that offended you. The phrase can be restated as "I'm often so incredibly stupid that I fail to realize that other people could miss some simple steps" (like noticing that the problem is shift invariant in this case). The meaning is exactly the same, though all the words are now completely different. Anyway, let's see if I can be less emotional and you can be less sensitive to the form of the message :). –  fedja Dec 29 '10 at 13:20

Drawing some consequences from Franz Lemmermeyer's comment above, i.e. that the integer-valued polynomials $f_n:=\frac 1 2(x+x^n)$ converge to $\frac x 2$ uniformly on closed sub-intervals of $]-1,1[$. Then, in the same convergence, we also have that the $k$-fold iteration $f_n\circ\dots\circ f_n$ converges to $x/2^k$ as $n\to\infty$. But then we can reach this way any dyadic rational multiple of $x$; any real multiple of $x$; any polynomial with $0$ constant term; and in turn any continuous function on $]-1,1[$ with an integer value at $0$ is uniform limit on compact sets of a sequence of integer valued polynomials (whence in particular the conjecture follows).

-
Very nice. This gives me lots to think about. –  SJR Dec 30 '10 at 2:50
I took the liberty of posting another question about a natural generalization of your problem mathoverflow.net/questions/50657/… Actually it seems that it is not so difficult as I initially thought, and hopefully, the same trick with Franz's polynomials works –  Pietro Majer Dec 30 '10 at 8:49