# Open problem

Talks about or related to problems that have not yet been solved. Some open problems are known by a famous guess, often called a conjecture.

There have been 1 completed talk and 7 topic suggestions tagged with open problem.

## Completed Talks

### Inverse Galois Theory

Delivered by David Liu on Friday March 17, 2017

Almost 200 years after Évariste Galois's death, there is still one question about Galois groups — the symmetries of the roots of polynomials, that still remains unsolved. This is the Inverse Galois Problem — whether every group is a Galois group of a Galois extension of the rational numbers. In this talk, I will give an overview of the progress that has been made, the approaches that mathematicians are making, and directions for further research.

A note on the requirements for this talk: It is recommended that you be comfortable with groups, fields, field extensions, automorphisms, and basic Galois theory. This requirement can be met by any of the following suggested alternatives:

• having taken PMATH 347, and currently taking PMATH 348;

• having taken PMATH 347, and coming for the prerequisite knowledge presentation (see below);

• having equivalent knowledge to PMATH 347 and PMATH 348;

• otherwise, if you are currently taking or have taken MATH 146, this talk is still accessible, but it is highly recommended that you read An Introduction to Galois Theory by Dan Goodman, and watch this 18-minute lecture by Matthew Salomone (after reading the article) and optionally also come for the prerequisite knowledge presentation

A prerequisite knowledge presentation about Galois theory will be given at 17:00, prior to the beginning of the talk at 17:30. This presentation will last about 20 minutes. If you are unfamiliar with the material, it is recommended that you read some of the linked material above in addition to attending this presentation. Attending this presentation is optional. The reference material used for this presentation is the Galois Theory document.

## Talk Suggestions

### Complexity of Matrix Multiplication

Volker Strassen showed that $n^3$ matrix multiplication was not optimal in 1969. Since then, new algorithms such as Coppersmith-Winograd have further improved the time complexity of matrix multiplication. It is conjectured that matrix multiplication is possible in $O(n^{2+ɛ})$ for any $ɛ>0$, however small. This is one of the few remaining open problems in finite-dimensional linear algebra.

Possible reference materials for this topic include

### Distribution of Primes Modulo p

Possible reference materials for this topic include

### P vs. NP

Possible reference materials for this topic include

• Arora, Bazak: Computational Complexity

### Plausible Conjectures

Possible reference materials for this topic include

### Separating Words Problem

Given two strings, we can write a computer program to tell them apart. A special kind of very simple computer program that accepts or rejects strings, using only a finite number of states while reading the string, is called a deterministic finite automaton. (These deterministic finite automata can also be expressed as a regular expression.) For any two strings of length $n$, there is some deterministic finite automaton (or regular expression) that recognizes one and not the other, and there is some smallest one. In the worst case, it is known (Robson 1989) that any two strings of length $n$ can be separated by an automaton of size $O(n^{2/5} (\log n)^{3/5})$, but this is not known to be optimal. The optimal upper bound remains an open problem.

Possible reference materials for this topic include

### The Riemann Hypothesis

Possible reference materials for this topic include