This problem was presented to me by my friend Theodore Hui on my visit to Cornell University to speak at their number theory seminar on May 12th. It is amusing because it is ‘obvious’ that the problem should have a negative answer, yet it can be solved extremely easily and in very few steps. The problem is as follows: suppose you are told that the function is a polynomial, but you are not told anything about its degree or coefficients except that its coefficients are non-negative integers. However, you are allowed to input integer values into a machine, which knows exactly what is, and it will output . Then what is the minimum number of test values such that there exist integers such that the pairs will allow you determine ? If no such number exists, then prove that no such number exists.
At first, the answer seems almost surely negative; since for any finite number of pairs there should be infinitely many polynomials that go through these points, since the degree is unbounded. However the above question has an extremely easy solution as follows:
First, input 1 to obtain . Since we know the coefficients of are non-negative, it follows that is an upper bound for each coefficient. Thus after inputing into the machine and considering the base expansion, we obtain that
and the digits of this number in the base expansion are the coefficients of .
This problem further illustrates the notoriety of the problem of finding lower bounds for algorithms.