Bachelor

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.

Keywords: coding theory, decoding, polynomials

Prerequisites: 01018: Discrete Mathematics 2, (01405: Algebraic Coding Theory)

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.

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.

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.

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!

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)}\).

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.