Minimum Number of Values to Guess a Polynomial with Non-Negative Coefficients [duplicate]

This question already has an answer here:

My math teacher claimed that he could guess any polynomial with non-negative coefficients given two values that he asked for. For example, he asked me to write down a function of which I wrote down (x^5 + 3x^2) and didn't tell him. Simply by knowing the values of f(1) and f(5), he was able to guess the function with accuracy. Is this pure guessing or is there a mathematical explanation for it? Need to know a minimum of two values to guess a polynomial with non-negative coefficients.

marked as duplicate by Watson, hardmath, Jonas Meyer, M. Vinay, LeucippusJun 8 '16 at 0:30

• Did he ask you for $f(1)$ first, then ask about $f(5)$ only after you answered the first? – Will Jagy Nov 20 '14 at 23:45
• He asked for f(5) after f(1). So its possible that f(5) was conditional on f(1) – Mario James Nov 20 '14 at 23:48
• Seems possible that, given $f(1) = k,$ you then ask for $f(1+k)$ to leave very few possibilities. No matter what, there are few possibilities with coefficient sum $4,$ as long as one may rule out large exponents. – Will Jagy Nov 20 '14 at 23:52
• – Watson Jun 7 '16 at 11:27

Just for the record, I thing it may be described this way: being told $f(1) = A,$ ask for $f(1+A) = B$ and then write $B$ in base $(A+1).$

So, $$3200_{\mbox{base ten}} \equiv 100300_{\mbox{base five}}$$

• And it can be noticed that in base $1+A$, the value $f(1+A)$ is just the coefficients written out in order (since every coefficient is between $0$ and $A$ and hence won't "roll over") – Milo Brandt Nov 21 '14 at 0:37

Yes, it is possible to guess the polynomial with only two queries. The trick here is that the second query depends on the first (otherwise, if all queries are independent, then by polynomial interpolation, we'd need at least as many queries as one plus the degree of the polynomial). The algorithm is as follows:

• Ask for $f(1)$, and call it $A$.
• Ask for $f(A + 1)$, and call it $B$.
• Initialize $i := 0$.
• While $B \neq 0$, do the following:
• Set $c_i := B \pmod {A+1}$.
• Set $B := \frac{B - c_i}{A+1}$.
• Increment $i := i + 1$.

For your example, we have:

• $A = f(1) = 4$
• $B = f(A + 1) = f(5) = 3200$
• $c_0 = 3200 \pmod 5 = 0$
• $c_1 = \frac{3200 - 0}{5} \pmod 5 = 640 \pmod 5 = 0$
• $c_2 = \frac{640 - 0}{5} \pmod 5 = 128 \pmod 5 = 3$
• $c_3 = \frac{128 - 3}{5} \pmod 5 = 25 \pmod 5 = 0$
• $c_4 = \frac{25 - 0}{5} \pmod 5 = 5 \pmod 5 = 0$
• $c_5 = \frac{5 - 0}{5} \pmod 5 = 1 \pmod 5 = 1$

Putting it together, we obtain $f(x) = \sum_{i=0}^5c_ix^i = 3x^2 + x^5$, as desired.

The reasoning here is that: $$B = c_0 + c_1(A + 1) + c_2(A + 1)^2 + \cdots + c_d(A + 1)^d$$ So modding out by $A + 1$ will make all of the powers of $A + 1$ vanish and leave behind the smallest coefficient. Modding $c_0$ by $A + 1$ won't affect the coefficient, since all coefficients are nonnegative and $A$ is the sum of all coefficients, so each coefficient is guaranteed to be in the range $[0, A]$.

• I think what you have done is take a number in base ten and re-write it in base $(A+1).$ Does that seem correct? Either way, left an answer to that effect. – Will Jagy Nov 21 '14 at 0:29
• Yeah I guess that's correct! Never thought of it like that. – Adriano Nov 21 '14 at 0:34

Here is a fascinating way of finding the polynomial with two questions!

Ask for $f(1)$. Say it's around $500$.

Ask for $f(0.001)$ (Add an appropriate number of zeroes after the decimal point depending on how large $f(1)$ is).

The coefficients will all separate in the decimal expansion.

Example : $f(x)=x^5 + 3x^2$

$f(1) = 4$

Ask for $f(0.1) = 0.03001$

It seems foolproof (of course, provided that coefficients are non-negative integers.)