# How to find the polynomial with integer (positive and/or negative coefficients) exactly satisfying 4 given points

I want to find polynomial (of whatever degree) with integer (positive and/or negative coefficients) exactly satisfying 4 given points:

$\{x=6,y=6670\},\{x=2,y=55\},\{x=1,y=10\},\{x=0,y=1\}$

Anyone ?

-

There are none. The last point gives the constant term to be $1$. For the first point, all the powers of $x$ are even, so the value of the whole polynomial will be odd.

-

The unique (Lagrange interpolating) degree-$3$ polynomial passing exactly through the four given points with integer coordinates is \eqalign{ f(x)&=& 6670\frac{(x-0)(x-1)(x-2)}{(6-0)(6-1)(6-2)}+ 55\frac{(x-0)(x-1)(x-6)}{(2-0)(2-1)(2-6)}\\&&+ 10\frac{(x-0)(x-2)(x-6)}{(1-0)(1-2)(1-6)}+ \frac{(x-1)(x-2)(x-6)}{(0-1)(0-2)(0-6)}\\&=& \frac{6670}{6\cdot5\cdot4}x(x-1)(x-2)- \frac{ 55}{2\cdot4}x(x-1)(x-6)\\&&+ \frac{ 10}{5}x(x-2)(x-6)- \frac{ 1}{2\cdot6}(x-1)(x-2)(x-6)\\&=& \frac{405}{8}x^3 - \frac{1071}{8}x^2 + \frac{369}{4}x + 1\\&=& \frac18\left(405x^3 - 1071x^2 + 738x + 8\right)\,. } It has rational, but in general not ingegral coefficients, as one expects for data points $(x_i,y_i)\in\mathbb{Z}^2$. Since the it is unique, there is no polynomial of degree $3$ with integer coefficients that exactly passes through these data points. One could, however, find the "closest" approximation in $\mathbb{Z}[x]$, given a suitable definition of closeness, for example with Bernstein polynomials.

Thanks to an astute reader (@YongyiChen) for pointing out that we can always search for a higher degree polynomial. And as @RossMillikan already argued, this is impossible, for if $$f(x)=\sum_{i=0}^na_ix^i\in\mathbb{Z}[x]$$ were such a polynomial, then we would have $a_0=1$ and $$y_k-1 = \sum_{i=1}^na_ix_k^i$$ for the $k^{\text{th}}$ data point, which necessarily entails that $x_k|y_k-1$ for each data point with $x_k\ne0$. However, this is not true for $(6,6670)$ since $6669\equiv3\pmod6$.

-
There is more than one polynomial if we don't restrict its degree to one less than the number of given points. –  Yongyi Chen Apr 17 '12 at 16:18
@YongyiChen: thanks, you're spot on! –  bgins Apr 17 '12 at 16:23
@YongyiChen: But it still won't work over the integers. –  Ross Millikan Apr 17 '12 at 16:43
Any closed form function then ? –  Alex Apr 17 '12 at 17:01
What do you mean? There's a polynomial, just with rational coefficients. –  bgins Apr 17 '12 at 17:14

Are we expected to construct polynomials in $x$ only, or can we consider powers of $y$ as well? Because the following polynomial equation does satisfy all of your points: $$36576-322659x+651393x^2-36581y+5y^2=0.$$ It is an ellipse.

-
Which could be solved over radicals with regards to y - that is good ! –  Alex Apr 17 '12 at 17:21
Could you maybe explain how you obtained this ellipse? –  Guess who it is. Apr 17 '12 at 17:23
@J.M. It is embarassingly simple: I just analytically solved the system of four equations in Maple. The only "know how" here, I suppose, was to assume that the question must make sense somehow and, after seeing Ross Millikan's argument, it was clear that more general form is likely to be assumed. –  Aleksey Pichugin Apr 17 '12 at 17:29
Do I need to put more details of the solution? –  Aleksey Pichugin Apr 17 '12 at 17:31
Oh, it's an axis-aligned ellipse; I only noticed it now... –  Guess who it is. Apr 17 '12 at 17:31

If you don't mind broadening your attention to real coefficients, check out Lagrange interpolation: http://en.wikipedia.org/wiki/Lagrange_polynomial . For $n$ points, there is a polynomial of degree $n$ which interpolates those points, given by the formula on the Wikipedia page.

-
Unfortunately, this does not force the coefficients to be integers. For $n$ points, it is the polynomial of degree $n-1$ that is unique. –  Ross Millikan Apr 17 '12 at 15:55
Oh, argh, integer coefficients. Question reading fail. –  Neal Apr 17 '12 at 15:55
Any closed form function then ? –  Alex Apr 17 '12 at 16:52