Solve Polynomial Riddle: Find Coefficients & Rank

[dislect]

Hi guys,

My boss gave me a riddle.
He says that you have a "black box" with a polynomial inside it like f(x)=a0+a1x+a2x^2+a3x^3 ...
you don't know the rank of it or the coefficients a0, a1, a2 ...
You do know:
all of the coefficients are positive
you get to input two x numbers and their f(x) value


How can you find all of the coefficients a0,a1,a2 ... and the rank?

Thanks !

 

[hilbert2]

Knowing f(x) for two values of x is not enough to determine the coefficients if the polynomial is of higher than first order.

 

[economicsnerd]

It can be done if you know the polynomial has nonnegative integer coefficients, and if the second input is allowed to depend on the first output.

Put in $1$. The output gives you the sum $s$ of the coefficients.
- If $s=0$, you know $f=0$.
- If $s>0$, put in any integer $k>s$. Then there is a unique integer solution, which is especially easy to read off if you express the output in base-$k$.

 

[dislect]

Hi economicsnerd,

Couldn't follow "put in any integer k>s. Then there is a unique integer solution, which is especially easy to read off if you express the output in base-k."
Could you give me an example? let's say f(x)=5+2x+4x^2 is in the 'black box'.
i put in x=1 and receive f(x)=s=a0+a1+a2=11 > 0 so i put in x=k=15 and get f(x)=a0+15a1+900a2=935
organize:
1. a0+a1+a2=11 2. a0+15a1+900a2=935
2 equations with 3 unknowns.

Whats the rational behind putting a k > s, and how can i find all coefficients with just 2 equations ?

 

[economicsnerd]

Okay. So you know $f(1)=11$ and $f(15)=935$.
- First note that $15^3 > 935$, so that the polynomial can't be of degree $>2$. That is, $f(x)=a_0 + a_1 x + a_2 x^2$ for some $a_0,a_1, a_2\in\mathbb Z_+$.
- Next, note that $a_0,a_1\in\mathbb Z_+$ with $a_0+ a_1 \leq 11 < 15$, so that $a_0 + a_1(15)<15^2$. This means that $935 - 15^2< a_2 (15)^2 \leq 935$. It's easy to check that there's a unique integer $a_2$ that accomplishes this, namely $a_2 = 4$.
- Substituting the solution for $a_2$ in, we now know that: $a_0+a_1 < 15$ and $a_0 + a_1 (15) = 15 35$. [Of course, you have two equations and two unknowns now, but we don't actually need to know that $a_0 + a_1 =7$, because knowing they're integers gives us enough information.] Now we can do the same trick again. $35 - 15< a_1 (15) \leq 35$, which pins down $a_1=2$.
- Then substitution yields $a_0 = 5$.

We can always work backward in this way.

To get some better intuition for why, consider the following question:
Say I tell you I have a polynomial $g$ such that every coefficient of $g$ is a nonnegative integer $<10$. If I tell you $g(10)$, will you then be able to tell me what $g$ is?

For example:
- If $g(10)=5021$, then do we know $g(x) = 5x^3 + 2x + 1$?
- If $g(10)=60007$, then do we know $g(x) = 6x^4 + 7$?

Nothing is magical about $10$ that makes this trick work. It's just that we usually express numbers in a way (base-10) that makes it easy to answer this question. All the first question is needed for is to find a $k$ such that we can be sure that every coefficient of the polynomial is a nonnegative integer $<k$.

 

[D H]

Hi economicsnerd,

Couldn't follow "put in any integer k>s. Then there is a unique integer solution, which is especially easy to read off if you express the output in base-k."
Could you give me an example? let's say f(x)=5+2x+4x^2 is in the 'black box'.

Whats the rational behind putting a k > s, and how can i find all coefficients with just 2 equations ?

The rationale behind using asking for f(k) where k>f(1) is because otherwise the magic might not work. Suppose the function in the black box is f(x)=5+2x+4x². The black box cranks out 11 as a response to f(1). Suppose I use 4 next. The black box churns out f(4)=77, which is 1031 when expressed base 4. That suggests the polynomial is 1+3x+5x³, which is wrong.

To see what's going on, here are f(k) from k=2 to 16, expressed in base 10 and in base k:

 k f(k)  base k  Polynomial
 2   25   11001  1+x^3+x^4
 3   47    1202  2+x^2+x^3
 4   77    1031  1+3x+x^3
 5  115     430  3x+4x^2
 6  161     425  5+2x+4x^2
 7  215     425  5+2x+4x^2
 8  277     425  5+2x+4x^2
 9  347     425  5+2x+4x^2
10  425     425  5+2x+4x^2
11  511     425  5+2x+4x^2
12  605     425  5+2x+4x^2
13  707     425  5+2x+4x^2
14  817     425  5+2x+4x^2
15  935     425  5+2x+4x^2
16 1061     425  5+2x+4x^2

Can you see the pattern? It appears that f(k) when expressed in base k is 425 for all k>5. This is indeed the case. You might want to try proving it.

Note that in this case reading off the polynomial from the base-k representation of f(k) works for all k>5. That's because the largest coefficient is five. Using k=f(1)+1 (or higher) ensures that k is larger than the largest possible coefficient.

Suppose the black box function was instead f(x)=11x³. Once again you'll get f(1)=11, but now the base k representation of f(k) keeps changing until you reach k=12, at which point it becomes b00 ('b' means 11) and stays that way for all k>11. The black box knows what the largest coefficient is. You don't, but you do know that it cannot be larger than 11.

 

[dislect]

Thank you all :)