0
$\begingroup$

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 ?

4 Answers 4

8

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.

2

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

  • 0
    There is more than one polynomial if we don't restrict its degree to one less than the number of given points.2012-04-17
  • 0
    @YongyiChen: thanks, you're spot on!2012-04-17
  • 0
    @YongyiChen: But it still won't work over the integers.2012-04-17
  • 0
    Any closed form function then ?2012-04-17
  • 1
    What do you mean? There's a polynomial, just with rational coefficients.2012-04-17
  • 0
    Not polynomial, I meant2012-04-17
  • 0
    But with integral coefficients?? @AlekseyPichugin has a nice quadratic form for an ellipse passing through your points.2012-04-17
  • 0
    Yes, Alexey offered very nice answer, where y could be resolved (as quadratic equation solution) over x - in radicals over integral values - that is great !, how did you arrive to it ?2012-04-17
2

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.

  • 0
    Which could be solved over radicals with regards to y - that is good !2012-04-17
  • 0
    Could you maybe explain how you obtained this ellipse?2012-04-17
  • 0
    @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.2012-04-17
  • 0
    Do I need to put more details of the solution?2012-04-17
  • 0
    Oh, it's an axis-aligned ellipse; I only noticed it now...2012-04-17
1

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.

  • 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.2012-04-17
  • 0
    Oh, argh, integer coefficients. Question reading fail.2012-04-17
  • 0
    Any closed form function then ?2012-04-17