Identifying a polynomial

A tweet has got me musing again. @ColinTheMathmo sent out a tweet making a seemingly audacious claim that from just two data points he could deduce all the coefficients and powers in a polynomial that you had defined as long as the coefficients and powers were zero or positive integers

You pick a polynomial with coeffs in Z & >=0. I give you x, you tell me the value. We do that again. Then I can name your poly. How?

— Colin Wright (@ColinTheMathmo) October 31, 2012

i.e. you pick a polynomial of the form:

\begin{equation} y = \sum {a_i \cdot x^i} \qquad for \qquad i \in Z^*, a_i \in Z^* \qquad (1)\end{equation}

He then supplies an \(x\) value, you return the corresponding \(y\) value, this procedure is repeated once only and then he can tell you all the \(a_i\) values in your polynomial.

I looked at this tweet on the way to work one day and starting thinking about it. I wondered whether you cleverly supplied some complex numbers for the \(x\) values which could indicate the powers of x in use, but Colin assured me that the \(x\) values could be in \(Z\) too. In my head, I started drawing graphs. Let’s call the first number asked for \(x_1\). I could see that, given \(y_1\) for that value, there are a finite number of graphs for polynomials satisfying \((1) \) that go through that point and that for the constraints given, these graphs were all monotonically increasing in \(x\).

I could see all this in my mind’s eye, but couldn’t quite work out how that would let me uniquely identify each one – i.e. at what point all those lines no longer cross. So, when I had a minute, I wrote a little python program to spit some graphs out. Below is one graph for a particular sample pair (\(x_1=2\),\(y_1=41\)) showing all the possible polynomials satisfying \((1)\) that go through that point. For those who would like to look at the graphs in a bit more detail – there’s a gallery at the end of the post with various \(x,y\) pairs and zoom levels. Scrappy Python code to generate these is also available on request.

Click the graph to see a full size, better resolution, image

From the picture above and a bit of reasoning that any higher powers of \(x\) will cross all curves at lower values of \(x\), I’m pretty convinced that for any point you ask for, if you work out the shallowest polynomial of order 2 through the point and the steepest straight line and then find their intersection, all the graphs beyond that point are distinct, will never cross and are monotonically increasing in \(x\).

With this insight, if I define
\begin{aligned}
b & ={\lfloor}{\frac{y_1}{x_1}}{\rfloor} \\
c & = y_1-{x_1}^2 – (y_1 mod x_1)
\end{aligned}
The intersection is at
\begin{equation}x = \frac{b + \sqrt{b^2 – 4c}}{2} \end{equation}
So, we ask for \(x_2\) greater than that value and the polynomial is uniquely identified. For instance, in the example above, this works out to \(x_2 \geq 18\) How to then get back to each co-efficient is interesting, but basically a search problem.

Now, Colin has reliably informed me that this is way too complicated and also challenged me as to whether I can prove it will always work – which I’m not sure I can, but I think the above sort of shows it.

I’m going to have a think about a few of my other ideas, which are (in no particular order)

• ask for 1 as the first x (\(x_1 = 1\)), thus giving you at least the sum of all co-efficients. I have a feeling this might be useful
• put in the value that you get back from the first answer as the second value you ask for (not sure why I think that might be good – I doubt it really)
• find a value of \(x_2\) which is \(f(x_1)\) but lower than the value outlined above which can similarly always have the graphs distinct. I’m not hopeful.