Autumn 2021 Projects

Analyzing Weak Cryptographic Keys

Faculty Mentor: Daniel Shumow

Project Description: Public Key Cryptography is the basis of security on the internet. Public key cryptosystems include asymmetric Encryption (where encrypt and decrypt keys are distinct) and digital signatures. The oldest and most widespread of these algorithms is RSA, with security based on the hardness of factoring. RSA keys are large (> 1024 bit) numbers that are the product of two equal sized primes. RSA was revolutionary, but it is slowly diminishing in popularity. This is mainly due to the advent of quantum computers, which can theoretically solve factoring faster than classical computers. However, RSA has historically had many problems.

This project is to survey factoring algorithms and other attacks against RSA. Using knowledge of the attacks, students will work to generate the “worst case” possible RSA keys for each type of attack. That is, keys that are the most likely to succumb to given factoring algorithms or other attacks.

The goal of the project is to show the wide range of ways that RSA keys can be weak. Lessons include the difficulty of finding “average case” instances of hard mathematical problems, learning about public key cryptography and generating a data set that can be used to evaluate the efficacy of factoring algorithms.

The scope of this project can be adjusted to the size and experience level of the students.

Project Level: Advanced: students who have taken multiple upper-level mathematics courses
Additional Course Requirements: Math 301 (Number Theory) or Math 402 (Intro to Modern Algebra – Rings)
Programming Requirements: Python/Sage

Constructing Quantum Theories

Faculty Mentor: Dr. Benjamin Feintzeig

Project Description: This project investigates the properties of so-called deformation quantizations that model the relationship between classical and quantum physics. We will analyze various differential equations representing distributions of matter in space. Deformation quantization considers algebras of complex-valued functions on the space of solutions to such differential equations, and defines a non-commutative product capturing the fundamental features of quantum physics. Since the deformed non-commutative product approximates a classical commutative algebra in a precise sense, one can use this structure to investigate the “classical limit” of aspects of quantum physics. We will be especially concerned with analyzing the classical limit of quantities associated with energy and particle content in physics.

Project Level: Advanced: students who have taken multiple upper-level mathematics courses
Additional Course Requirements: Some background in linear algebra, analysis, and abstract algebra will be helpful for this project. No background in physics is required.
Programming Requirements:

ImPaCT Improving Panel Consensus Tool

Faculty Mentor: Dr. Marina Meila

Project Description: This project aims to build a visualisation and analysis software to assist in collective decision making. Imagine a student project competition, with n projects, and a jury (sometimes called a *panel*) consisting of m members. Each of the m jury members ranks the n projects. These m rankings may differ from each other, even though one hopes they will have something in common. Sometimes the jury members also “grade” the projects with numerical grades. After independently ranking and grading, the experts need to find some form of consensus. For example, what is the “consensus ranking”, i.e. the ranking that all members of the jury can most easily agree with? If the jury must choose k winners from the n projects, which should these be?

Where is the mathematics? Each ranking is a permutation of n objects. Sometimes the jury members only give you part of the permutation (a partial order). You will have to learn about distances between permutations, and about distributions over the space of all permutations. With clever combinatorics we can calculate probabilities from these distributions very efficiently. Algorithms for finding consensus ranking exist, and some of them are implemented.

This project is mainly about helping a jury (of non-matematicians) use the algorithms. Part I: The team will develop code that visualizes the m rankings, as well as the grades given by the experts, in a way that highlights the amount of consensus and disagreement between them. Part II: Further, the team will use different methods to calculate a consensus ranking, and to “measure” how good is the consensus between experts. Some of these methods are already implemented, other will be the task of the current project. Part III: Finally, all that was calculated in Part II must be displayed to the jury in an intuitive way, to help them make their decision.

Project Level: Intermediate: students who have taken Math 300
Additional Course Requirements: Combinatorics, algebra, probability
Programming Requirements: very good python skills, especially visualization and plotting, numpy, scipy, file management, strings

Guessing with feedback

Faculty Mentor: Dr. Andrea Ottolini

Project Description: Consider the following game between the two of us: from a shuffled deck of cards with consisting of n different types of cards, each appearing m times (think of n=13 and m=4), I pick the first card and ask you to guess its type. Then, I show you the card, and you score one point if your guess was correct. After disregarding the first card, the game continues the same way and stops when there are no cards left in the deck.

This game is an example of sequential experiment with complete feedback. A general goal is to understand how well you can perform, say if your goal is to maximize the expected score. Let me mention that generalizations abound, where other types of feedback — e.g., what if only tell you whether your guess was correct or not, instead of showing the cards? — as well as decks that are not well-shuffled, are considered. Needless to say, talking about “cards” makes everything friendlier, but the game has other interpretation as well. In particular, there is a close connection with the classical birthday problem.

A lot is known, but many questions are open. For instance, when n=m is large, what is (approximately) the expected score under the optimal strategy? We may try to address something more/less accessible, and combine conjectures (supported by heuristic and/or numerical simulations) with some rigorous results.

Project Level: Advanced: students who have taken multiple upper-level mathematics courses
Additional Course Requirements: Discrete probability (ask me for more details!)
Programming Requirements: Some Python would be a plus

Codes and Designs

Faculty Mentor: Dr. Rekha Thomas

Project Description: Graphical designs were introduced by Steinerberger as a discrete analog of the famous spherical designs which are quadrature rules on the sphere. Catherine Babecki has established several basic results about graphical designs in her recent paper “Codes, Cubes and Graphical Designs” https://arxiv.org/abs/2012.12376. One of her main results is that Hamming codes are good designs on the cube graphs that admit them.

The goal of this project is to examine several more Boolean codes and understand their power as designs. A nice byproduct would be to prove that some of them are optimal designs on the Boolean cube.

Project Level: Advanced: students who have taken multiple upper-level mathematics courses
Additional Course Requirements:
Programming Requirements:

Counting spanning trees on the Kagome lattice

Faculty Mentor: Dr. Harry Richman

Project Description: The problem of counting spanning trees on a graph is of interest in combinatorics, probability, and statistical physics. On a regular 2-dimensional lattice, the number of spanning trees is known to grow exponentially. The exponential rate is known for the square and triangular lattices, but not for other lattices. The goal of this project is to calculate the asymptotic growth of the number of spanning trees on the Kagome lattice. Students will learn about graph Laplacians, Kirchhoff’s matrix-tree theorem, asymptotic analysis, and random walks on graphs. Computational tools may also be used.

Project Level: Intermediate: students who have taken Math 300
Additional Course Requirements: 208 (linear algebra)
Programming Requirements: programming experience preferred but not required

Counting stable spheres in K3 surfaces

Faculty Mentor: Dr. Heather Lee

Project Description: A torus (or as a 1D complex manifold, it is called an elliptic curve) admits a nowhere vanishing holomorphic vector field, so it is a Calabi-Yau manifold. In 1 complex dimension, torus is the only Calabi-Yau manifold. For 2 complex dimensional manifolds (i.e. 4 real dimensions), there are a lot more, and K3 surfaces are such manifolds.

In this project, we would like to study the counting function N(A) of the number of 2 real dimensional spheres (a special kind of spheres known as special Lagrangians), of surface area at most A , in a K3 surface. There is a characterization of such spheres by their cohomology classes, meaning that they can be viewed as certain integer points in R^{2+p}, where p is the Picard rank of the K3 surface. We will be focusing on the case where p=1.

Project Level: Advanced: students who have taken multiple upper-level mathematics courses
Additional Course Requirements: Math 224/324 and 208/308 are required. It is also very preferable to have Math 402, 427, and 442, but not strictly necessary.
Programming Requirements: Programming will not be needed. However, if anyone likes programming, I have a possible exercise in mind that might help with this project.