Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question

4 Answers 4

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.

share|improve this answer

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

share|improve this answer
    
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
1  
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.

share|improve this answer
    
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? –  J. M. 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... –  J. M. 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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.