An amusing argument on determining polynomials

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 f : \mathbb{Z} \rightarrow \mathbb{Z} 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 n into a machine, which knows exactly what f is, and it will output f(n). Then what is the minimum number of test values m such that there exist integers n_1, \cdots, n_m such that the pairs (n_1, f(n_1)), \cdots, (n_m, f(n_m)) will allow you determine f? 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 S \subset \mathbb{Z}^2 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 f(1). Since we know the coefficients of f are non-negative, it follows that f(1) is an upper bound for each coefficient. Thus after inputing f(1) + 1 into the machine and considering the base f(1) + 1 expansion, we obtain that

f(f(1)+1) = a_d (f(1) + 1)^d + \cdots + a_1 (f(1) + 1) + a_0

and the digits of this number in the base f(1) + 1 expansion are the coefficients of f.

This problem further illustrates the notoriety of the problem of finding lower bounds for algorithms.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s