# Student Projects

We supervise exciting projects on all levels: “Fagprojekt”, Bachelor thesis, Master thesis or PhD.

A project with us will have emphasis on the mathematical essence. It will often be natural to include algorithms or implementations. It can span widely from being purely theoretical to very applied, as long as there is a strong mathematical content.

Below follow ideas for projects you can carry out with us, at various levels. Any of these can be tailored to your preferences, and you are of course very welcome to suggest your own projects.

# Fagprojekter

#### How to guess a sparse function from its values

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.

#### Reforming the leap-year system and the tempered musical scale

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.

#### Normal forms in module theory

Keywords: modules, linear algebra, normal forms
Prerequisites: (01018: Discrete Mathematics 2)

Description coming soon

#### Möebius Inversion

Keywords:
Prerequisites: (01018: Discrete Mathematics 2)

Description coming soon

# Bachelor Projects

#### How do you check if $$10^{23423} + 1$$ is a prime?

Keywords: number theory, prime numbers, algorithms
Prerequisites: (01018: Discrete Mathematics 2)

How do you check whether, say 73 is prime? You could try dividing with all primes greater than 1 and up to $$\sqrt{73} < 9$$ and verify that none of them divides. This has the advantage of helping you factor 73 as well as answering the primality question. It has the disadvantage that if 73 was a much, much larger number, you would never finish the exciting task of testing potential divisors.

To the best of our current knowledge, it is much easier to check for primality, than it is to actually factor a number. Case in point: my computer algebra system answered within 1 second that $$10^{23423}+1$$ is not prime, but it is still busy attempting to find a factorization.

This project is about those clever algorithms for primality testing. The famous, and shockingly simple, Rabin–Miller test is a randomized algorithm which can only prove non-primality: it answers either “definitely not prime” or “perhaps prime”. It works well for almost all non-primes, though, so it can usually be quite well trusted. The project might also touch upon the landmark paper of Agrawal et. al that can prove both primality and non-primality in polynomial time.

The project would involve implementing one or more of the investigated methods in a computer algebra system or a favourite programming language.

#### How to hide a needle everywhere in the haystack

Keywords: coding theory, decoding, polynomials

Locally decodable codes are a type of error-correcting code for encoding and storing information in a reliable way and such that you can “locally” get the information back: you can retrieve just a single symbol of the original information at a time by looking at only very few symbols of the encoded data, and those symbols can be chosen basically randomly! Even more, we still have error-correction so even if some of the retrieved symbols were wrong, we still correctly obtain the information symbol we were looking for.

These codes are useful for privacy services in distributed storage, and have also had a huge theoretical impact in proof theory as enablers of probabilistically checkable proofs.

The constructions are algebraic and rely on evaluation and interpolation of multivariate polynomials over finite fields. The proofs that they exhibit “random” local reconstruction draw on algebraic geometry.

The project could be purely theoretic, by studying the basic constructions and more recent proposals in research papers, or it can be made more practical by implementing one or more of the schemes.

#### How many pearl necklaces could my niece make me?

Keywords: combinatorics
Prerequisites: 01018: Discrete Mathematics 2

Combinatorics is the art of counting things. Pólya’s Enumeration Theorem is a powerful theorem for counting many types of recursively defined objects. A prime example, lending the suggested title to this project, is how many circular neclaces can you make with, say, 10 beads on it, each one red, green or blue? Of course, two neclaces are considered the same if I can roll the pearls around on the string on one and obtain the other, or if I can turn over the necklace and do the same.

In this project, you will become familiar with and prove Pólya’s Enumeration Theorem, and you will apply it to several concrete counting problems.

#### How often do you step on a prime?

Keywords: number theory, prime numbers
Prerequisites: 01018: Discrete Mathematics 2

The prime numbers are the most enigmatic objects of number theory: countless volumes of fascinating mathematics have been produced in the search for truly understanding their nature. Though we are still far from having achieved that lofty goal, we now know quite a bit.

This project deals with how prime numbers are distributed: if you choose a random number with 10 digits, what are the odds that it is prime?

Apart from being a central question in number theory, it is important in computer-driven application of discrete mathematics, e.g. cryptography and coding theory, where huge primes often needs to be generated on the fly.

#### Finding roots in polynomials of one variable over a finite field

Keywords: root finding, polynomials, algorithm
Prerequisites: 01018: Discrete Mathematics 2

Given a polynomial $$p \in \mathbb{F}_q[X]$$, where $$\mathbb{F}_q$$ is the finite field with $$q$$ elements, we can find all the roots of $$p$$ by trying the $$q$$ possibilities. If $$p$$ has low degree while $$q$$ is big, that seems like an inefficient way of doing it. In this project you will work with a very clever algorithm, the Cantor–Zassenhaus algorithm, for finding the roots in roughly $$\deg p\log(q)$$ computational steps!

#### Rational Function Reconstruction

Keywords: computer algebra, polynomial approximation, algorithm
Prerequisites: None

Imagine that I give you any decimal number, say 2.3834296, and I ask you to find me a fraction $$\frac a b$$, where both $$a$$ and $$b$$ are small integers, and such that $$\frac a b \approx 2.3834296$$. This problem might at first seem contrived, but it has many applications in a broad range of practical and theoretical problems. It can, surprisingly, be solved extremely efficiently using the Euclidean algorithm for computing the greatest common divisor.

There is a completely analogous problem over polynomial rings. Here I give you a power series (infinite degree polynomial) $$S(x) = 2 + 3x + 8x^2 + \ldots$$, and I ask you to give me a polynomial fraction $$\frac {a(x)}{b(x)}$$ such that
$$\frac {a(x)}{b(x)} \equiv S(x) \mod x^{8} \ ,$$ or, put another way, that $$a(x)$$ and $$b(x)S(x)$$ agree all the way up to $$x^8$$. The coefficients of $$a, b$$ might be over $$\mathbb{Q}$$ or over e.g.~a finite field $$\mathbb{F}_q$$. The Euclidean algorithm works for polynomials as well and solves the problem very well.

The problem has a natural vectorial generalisation: I give you $$\ell$$ power series at the same time $$S_1(x), \ldots, S_\ell(x)$$, and I ask for $$\ell$$ simultaneous approximations which share the same denominator, i.e. $$\frac {a_1(x)}{b(x)}, \ldots, \frac {a_\ell(x)}{b(x)}$$.

#### How to solve the 4th degree equation

Keywords: number theory, groebner bases, galois theory
Prerequisites: 01018: Discrete Mathematics 2

In high-school you learned how to solve a 2nd degree equation with a closed expression: if $$ax^2 + bx + c = 0$$ then $$x = \frac {-b}{2a} \pm \frac {\sqrt{d}}{2a}$$, where $$d = b^2 – 4ac$$. You might even have learned how to derive that equation. What happens if we start with a 3rd degree equation, 4th degree or even higher? Mathematicians spent hundreds of years searching for similar closed expressions, and finally succeeded, after enormous amounts of experimentation and clever tricks, in finding such closed expressions for the 3rd and 4th degree. The 5th degree — the quintic — resisted all attacks, and it was finally proved by Abel in 1823 that such an expression is impossible to obtain!

This project is about deriving the expression for the 2nd, 3rd and 4th degree equations in a systematic manner. This is possible using a pinch of Galois theory and a huge helping of Gröbner basis computation. The project involves using a computer algebra system for performing the computations.

# Master Projects

#### Number Field Sieve

Keywords: factorization, prime numbers, number theory
Prerequisites: 01018: Discrete Mathematics 2

The security of the RSA cryptosystem depends on the hardness of the integer factoring problem. In general this is a hard problem for which no fast algorithms are known. More precisely, given a natural number $$N \le 10^n$$ there currently does not exist an algorithm that would for any such $$N$$ finds all its prime factors in time polynomial in n.

While naïve algorithms such as finding prime factors of n by trial and error, have exponential running time in $$n$$, there also exist factoring algorithms that have so-called subexponential running time in $$n$$. One example of such an integer factoring algorithm is the quadratic sieve.

The currently fastest integer factoring algorithm is the famous number field sieve. The name of this algorithm comes from number fields: finite dimensional algebraic extension fields of $$\mathbb{Q}$$. In this project you will learn about number fields and several rings contained in them as well as their relation to the number field sieve.

#### Highly optimized 5-error-correcting BCH codes

Keywords: coding theory, root finding, decoding, fast algorithms
Prerequisites: 01405: Algebraic Coding Theory

In hardware implementations of BCH decoders, error location is bottleneck, i.e. finding the error-locator polynomial and afterwards, the roots of the error locator polynomial. In high-density optical transmission, one would like to be able to correct up to 5 errors as fast as possible. In this project we will consider the following question:

How can we perform decoding for a 5-error-correcting BCH code as fast as possible?

A strategy to answer this question is the following: To speed up finding the error-locator polynomial, one can precompute a so-called generic error-locator polynomial, i.e. one can find an expression containing the syndromes as additional variables, such that for each actual value of the syndromes one obtains the correct error-locator polynomial from the generic error-locator polynomial by substituting the syndrome values.

Such expressions are too lengthy in general, but if the number of errors one needs to correct is modest this is more feasible.. To find the roots of the polynomial of degree 5, the strategy is to use suitably chosen transformations to bring any given polynomial in a standard form. Tricks similar (but algebraically more interesting) to completing the square are generalized and used for this purpose. Afterwards a strategy will be developed to solve the remaining standard cases, among others using table lookup for special cases.

Keywords: factorization, prime numbers, number theory
Prerequisites: 01018: Discrete Mathematics 2

Description coming soon.

#### Origami Arithmetics

Mathematics of Origami

Keywords: origami, galois theory, algorithms, group theory, graph theory
Prerequisites: 01018: Discrete Mathematics 2

Origami is the art of paper folding: starting with a square piece of paper, one can make wondrous shapes simply by folding the paper. Many intriguing mathematical questions naturally present themselves. Here are a few examples, but searches on Google reveal many more, and there are even conferences devoted to the topic.

• It is common to use only exact folding, i.e. where e.g. a fold is defined by a know point be sent on top of another known point. A point is “known” when it is the intersection of two exact folds that were made. A natural question in
this context is therefore:

What set of points can become known by a finite sequence of exact folds?

This question is similar to classical geometric questions such as “Using only compass and straight-edge, can you double the square or trisect an angle?”. To answer it, one delves into beautiful algebraic theory initiated by Galois.

• If one completely unfolds an origami shape, the folds left on the paper is called a crease pattern. A natural question is therefore, given a crease pattern, is it possible to fold along exactly those lines and end up with a flat figure? If so, what sequence of folds should one perform? These questions turn out to be computationally hard! In fact, it is often posed to Origami enthusiast as interesting puzzles. A necessary, known condition for flat-foldability, however, is e.g. Kawasaki’s Theorem. Inquiries such as these lead one into combinatorics, discrete algorithms and perhaps meta-heuristics.
• Modular Origami is the practice of using many simple units, each folded from one pieces of paper, together to form a large, complex shape, e.g. stars and bucky balls. A classical example is the Sonobe star made of 30 pieces of paper. Here, 20 small triangular pyramids are arranged on an icosahedron to make the star. Each pyramid is composed of three halves of units.Classical geometric–algebraic questions arise in new light in this setting: if I take 3 colours, and fold 10 units of each colour, is it possible to assemple the Sonobe star such that each pyramid has exactly those three colours? The answer is yes, but it is tricky to accomplish. One can therefore ask how many solutions there are, or perhaps which one is *best* (e.g. most symmetrical). These questions are group theoretic in nature.