Fagprojekt

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.

Keywords: continued fractions, rational approximations

Prerequisites: None

The current rule for leap years is that year \(N\) is a leap year if 4 divides \(N\), except if 100 but not 400 divides \(N\). What is the rationale behind this rule? Could a better, more precise rule be made up?

The secret behind solving this problem is to approximate a real number, here the exact number of days it takes Earth to orbit the sun, by a fraction with a relatively small denominator. This is called rational approximation, and can be done by using continued fractions, which is, surprisingly, computable by the Euclidean algorithm.

A more complicated example comes from the “tempered” musical scale that was introduced in the 17th century. To fit the ear, tone frequencies should be related by exact fractions with small denominators. But to allow playing in multiple scales without retuning the instrument, one should use the same ratio between all consecutive notes. The latter requirement means that certain tonal intervals will be slightly off, and might sound bad to the trained ear. The 12 tones of our tonal system was chosen solely to minimise this error! But could we get a better system by choosing 10, 15 or 19 notes? Solving this problem requires simultaneous approximation of multiple real numbers by fractions all having the same denominator!

In this project you will be investigating the mathematics behind continued fractions and rational approximation, and you will derive a better leap year system than what we currently have. If time permits, you can investigate the tonal system problem.

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

Keywords: modules, linear algebra, normal forms

Prerequisites: (01018: Discrete Mathematics 2)

Description coming soon

Keywords:

Prerequisites: (01018: Discrete Mathematics 2)

Description coming soon