How to guess a sparse function from its values

How to guess a sparse function from its values

Johan S. R. Nielsen No Comment
Fagprojekt Projects

Keywords: polynomials, finite fields, implementation

Prerequisites: (01018: Discrete Mathematics 2)

“Interpolation” is when one approximates some unknown function by seeing only its evaluations at certain input. It’s a central concept in countless applications.

If the unknown function is a polynomial then it is not too difficult to see that one can perfectly reconstruct the polynomial using $n+1$ evaluations, where $n$ is the degree of the polynomial. However, what can be done if the polynomial has a huge degree, but only very few non-zero coefficients? The answer here is much less straightforward, and very surprising: if the polynomial has $t$ non-zero coefficients, the $2t+1$ evaluations is all it takes, no matter what the degree of the polynomial is! Even more bizarre, this procedure can be efficiently carried out using the Euclidean algorithm for computing the greatest common divisor.

In this project you will learn about this “sparse interpolation”, and you will investigate and prove how the Euclidean algorithm can solve the problem. You will also implement the algorithm. If time permits, you can investigate other algorithms for solving the problem, or you can consider what one can do if one or more of the evaluations may be wrong!

This project can be scaled to fit one or multiple students.