This post was written as a follow-up on Hillel Wayne’s newsletter: You can cheat a test suite with a big enough polynomial [1] which you should definitely check first.

Indeed, his post refers to a well-known mathematical problem: interpolation. More specifically, he is interpolating using polynomials. It turns out there is a great tool for polynomial interpolation: Lagrange polynomial.

Lagrange interpolation

Given inputs and outputs , we want to build a polynomial such that .

The Lagrange interpolating polynomial is built as follows:

This way, it is clear that the property stands:

Okay, but how do we define as a polynomial?
Hopefully, we know the roots of this polynomial. And we also have some information on how to normalize it (). The following meets these two requirements1:

Thus, we can entirely compute our Lagrange interpolating polynomial! But, wait… Hillel’s newsletter was considering functions of multiple variables.

Higher dimensions

Using straightforward Lagrange interpolation

Given input vectors and output scalars2 , we want to build a polynomial such that . Beware, s are now vectors, so is a multivariate polynomial now. Using the idea of Lagrange interpolation, we can come up with:

Simple, right? …right?
The thing is we no longer have a polynomial. Alright, let’s apply a quick fix:

Ta-daaa! We somehow won, but at what cost? Well, now this is a multivariate polynomial, but we lost an important property along the way: this polynomial is not of minimal degree.

A more sophisticated Lagrange interpolation

Hopefully, we are not the first ones working on this problem: see the paper by Kamron Saniee [2] to do some clean work, which I won’t do today.

Experimental results

Now, time to code and compute some polynomials!

You can check the source code here. The code itself is ugly as hell, but it does work (and will be forgotten forever after this hopefully).

I used the same set of inputs as in Hillel’s post:

inputs = [(1, 2, 3), (4, 2, 2), (1, 1, 1), (3, 5, 4)]
outputs = [max(g) for g in inputs]
 
p = lagrange(inputs, outputs)
 
print(p.eval(inputs[0]))
# Should be 3, outputs 2.9999999999999254
 
print(p.eval(inputs[1]))
# Should be 4, outputs 3.9999999999998908
 
print(p.eval(inputs[2]))
# Should be 1, outputs 0.9999999999999887
 
print(p.eval(inputs[3]))
# Should be 5, outputs 4.999999999999659
 
print(p)
# This one I'm not writing here

Yeay! Apart from floating point errors, we’re good! So, we found a polynomial which appears to be equivalent to the max function if looking only at this 4-test-long test suite.

What is this polynomial, you may ask?

We are pretty far from minimal degree here. But this just adds more chaos to the gag I guess.

References

Footnotes

  1. Of course, when doing Lagrange interpolation, the s are supposed to be unique.

  2. Here we consider some scalars, but it also could be some vectors without any loss of generality.