# Finding polynomials with their values at points

Is there any way I can find a polynomial given any 2 points (with x coordinate OF MY CHOICE): Let's say there's some polynomial I don't know(p(x)=2x3+x2+3), but my machine will give me an output. I give one x value of my choice, and it returns p(x), where p(x) is the polynomial function. I give another value of my choice., x+h, and get the output p(x+h). Given these outputs, I have to find p(x) as a polynomial.

What I've done is plugged in 0, which gives me the final term of the polynomial that is not multiplied by any power of x. Then I plug in 1, getting another output. When I find the "slope" of the two points, I get the sum of all the coefficients of all the terms that are powers of x. If I do this for the given p(x), I get 3, which is the sum of 2 and 1. However, I can't figure out what powers of x there are and what specific coefficients there are. Does anyone know how to solve this?

@GerryMyerson and @Shash said I can find the polynomial given the bound of the coefficients. I am confused as to what that means. There is only one number that is the sum of the coefficients. How is there a bound? Also, how do I find this sum of coefficients with just one value? I need to use one more value, M+1, as Shash said, so I can't use 2 values to find the max/sum, as I won't be able to ask for a value that is M+1. Can anyone help? Thanks.

EDIT: Non-negative integer coefficients are assumed.

• Hmmm. So there's no way I can strategically choose my numbers to get an output I can use? – bob the pie Nov 28 '14 at 16:22
• @Winther: If you know that all the coefficients are non-negative integers, then two points are enough. Perhaps this was the original question, and the OP mangled it a bit. – TonyK Nov 28 '14 at 17:26
• @Winther: No it doesn't! See Shash's answer and Gerry Myerson's comment. $M = f(1)$ is a upper bound of each coefficient, so $f(M+1)$ lets you read off the coefficients in base $M+1$. – TonyK Nov 28 '14 at 17:32
• If all the coefficients $a_n,...,a_0$ are non-negative, then each of them must be $\le a_n+\cdots+a_0 = f(1)$. (Yes, @ notifies them.) – TonyK Nov 28 '14 at 17:59
• This has been asked before (I know that I have answered this before), but it's been a while – Hagen von Eitzen Nov 28 '14 at 19:59

If all the coefficients are non-negative integers and if we know the max of all the coefficients, then it is easy to find the coefficients with just ${one\ point}$ of choice. Let's say the max is $M$. Then evaluate the polynomial at $M+1$. The output will be equal to the decimal number system representation of a number whose base $M+1$ number has digits as the coefficients of the polynomial. So, given the output, just get the base $M+1$ representation.

So, even if have just an upper bound (can be very lose upper bound), just set that as $M$ and proceed as above.

As Gerry Myerson points out in the comments, if you do not have an upper bound, you can use $M = p(1)$. Then only two evaluations will be required to determine the coefficients.

• Note that we don't need to know the degree here :) – Shash Nov 28 '14 at 8:16
• And if you don't have a bound for the coefficients, you can get one by evaluating at $x=1$. So (if the coefficients are nonnegative integers) you can get the whole polynomial by 2 evaluations. – Gerry Myerson Nov 28 '14 at 8:44
• @GerryMyerson Myerson: how do I only use x=1 to find the bound? I thought I need to use both $x=0$ and $x=1$. – bob the pie Nov 28 '14 at 16:27
• Wait, so I can start with $x=0$, then ask $x=1$? This gives me a bound, and I then use that bound? Or do you mean something else – bob the pie Nov 28 '14 at 16:47
• @VardaanBhat: what is meant here is that if your polynomial is $p(x)=2x^3+x^2+3$, you can read the coefficients in $p(10)=2103$; if the coefficients can have at most, say three digits, then evaluate $p(1000)$. Like $p(x)=234x^2+15x$, and $p(1000)=234 015 000$. And so on. – Yves Daoust Nov 28 '14 at 17:26

With two points you can only uniquely determine $p(x)$ if it has degree one. In general if $p(x)$ has degree $n$, you will need the computer give $(n+1)$ outputs, each for a different input.

For example if $p(x)$ has degree 2 and you input $0$ and $1$ and get outputs $a$ and $b$ respectively, there are an infinite number of parabolas which pass through these points. Here are some:

$p(x) = (b-a)x^2+a$

$p(x) = bx^2-ax+a$

$p(x) = 2bx^2-(b+a)x+a$

$p(x) = -3ax^2+(b+2a)x+a$

• This is not true in this special case because of the non-negative integers clause. First evaluate the polynomial at $p(1)$ to find an upper bound for all the coefficients, $M$. Then evaluate at $p(M+1)$ and refer to Shash's answer. – 6005 Nov 29 '14 at 6:10
• I think this answer needs more explanation. It is of course well-known that in the case of real numbers two points will not suffice. This is also true in the integers, I think, as well as in the nonnegative real numbers, but not in the nonnegative integers. By just referring to $p(x)$ without talking about where its coefficients lie at all, you are avoiding the crux of the problem. – 6005 Nov 29 '14 at 6:12
• (Although, I notice now that the non-negative integers edit was added after you posted this answer.) – 6005 Nov 29 '14 at 6:18
• Yes, the question was modified after I answered – David Peterson Nov 29 '14 at 6:30

No. You would a minimum of $n$ points, where $n$ is the dimension of the polynomial. For instance, let's try to find a cubic polynomial $p$ where $p(0)=0$ and $p(1)=1$. Notice that $p_1(x)=x^3-x^2+1$ and $p_2(x)=x^3-x+1$ both satisfy the given criteria.

A polynomial of degree $n$ has $n+1$ coefficients. If you know the degree but don't know anything about those coefficients, you'll need $n+1$ values of the polynomial to determine them. If you don't know the degree, no amount of values of the polynomial will suffice.

• True from a pure math sense. However, if you get enough (way more than 2 points), you could use curve-fitting techniques to guess the original polynomial. Also, if the polynomial is quadratic, and you have 5 points (thus assume a quartic), the leading coefficients will be zeros. ($0x^4+0x^3+cx^2+dx+e=y$). – FundThmCalculus Nov 29 '14 at 3:51