Projects

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.