During the week 18. April to 22. April, the black board in Mathematicum was filled with algebraic curves and Riemann-Roch spaces as Alain Couvreur from Inria, France, visited us.
Alain Couvreur is a leading expert on algebraic geometry and coding theory, and we spent the week looking into high-performance decoding of Algebraic Geometry codes.
20
Apr
5
Apr
Together with Canadian researcher Arne Storjohann, Johan Nielsen has written the paper “Algorithms for Simultaneous Padé Approximations” which has been accepted to the prestigious conference ISSAC: International Symposium in Symbolic and Algebraic Computation.
ISSAC 2016 will be held in Waterloo, Canada in July. Johan will go there and present the results. In fact, he will spend the entire month of July with the Symbolic Computation group at University of Waterloo.
3
Apr
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.
3
Apr
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.
3
Apr
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.
3
Apr
Keywords: factorization, prime numbers, number theory
Prerequisites: 01018: Discrete Mathematics 2
Description coming soon.
3
Apr
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.
3
Apr
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.
3
Apr
Keywords: modules, linear algebra, normal forms
Prerequisites: (01018: Discrete Mathematics 2)
Description coming soon
3