The n-Category Café

New enough that you feel it’s new.

If you just learned a cool theorem by Apollonius, it could be new to you, but you probably wouldn’t call it a “new development in mathematics”.

Here’s something I was excited to learn about, which is new by any reasonable standard. I guess this is my suggestion for “the most exciting new random matrix theory”.

Pick an $n \times n$ matrix $M_n$ at random by letting each of the entries be $\pm 1$ independently with probability $1/2$ each. What is the probability that $M_n$ will be singular?

If the matrix entries were instead picked with, say, a Gaussian distribution, it’s easy to show that the answer is $0$. So all experience with the behavior of large numbers of random variables suggests that it must at least be true that $$\lim_{n \to \infty} \mathbb{P}[M_n \; is \; singular] = 0.$$ This is true, but not easy to prove. It was first proven by Komlós in the 1960s, who showed (if I remember correctly) that $$\mathbb{P}[M_n \; is \; singular] \le \frac{C}{\sqrt{n}}.$$ About thirty years later, this was improved by Kahn, Komlós, and Szemerédi to $$\mathbb{P}[M_n \; is \; singular] \le (0.999)^n,$$ which has the nice consequence (via the Borell–Cantelli theorem) that with probability 1, $M_n$ is nonsingular for all sufficiently large $n$.

What about lower bounds? Well, the most obvious way for a matrix with $\pm 1$ entries to be singular is for two of its rows to be equal. The probability that, say, the second row is equal to the first is $2^{-n}$, so $$\left(\frac{1}{2}\right)^n \le \mathbb{P}[M_n \; is \; singular] \le (0.999)^n.$$ You can improve that lower bound by thinking about more than just the first two rows, or the possibility of one row being $-1$ times another, but you’ll still just get $$\mathbb{P}[M_n \; is \; singular] \ge \left(\frac{1}{2} + o(1)\right)^n$$ out of that kind of reasoning. A long-standing conjecture held that this lower bound was tight; that is, that an upper bound of the same form holds.

Recently, Konstantin Tikhomirov indeed proved that $$\mathbb{P}[M_n \; is\; singular] \ge \left(\frac{1}{2} + o(1)\right)^n.$$ (In fact, he proved a stronger statement about the smallest singular value of random matrices with Bernoulli entries.) This was a culmination of intense work on the smallest singular values of random matrices over the past fifteen years (although still sharper versions of the conjecture remain open), by authors whose names I’ll let you read in the bibliography of the paper (to spare me the embarrassment of failing to mention someone).

As for why I find this exciting, beyond the fact that I’ve been following this story closely for a long time, I like the fact that, by the standards of the field, the statement of the result is extremely accessible. It’s no Fermat’s Last Theorem, but you only need some very basic knowledge of probability and linear algebra to understand not only the statement, but also why it was conjectured. (On that latter point, I think it has FLT beat.) The proof, on the other hand, consists of many layers of technical arguments related to additive combinatorics, geometric functional analysis, numerical linear algebra, and other areas.

I just learned about this new paper by Anwar Irmatov which improves Tikhomirov’s result to the sharper $$\mathbb{P}[M_n \; is \; singular] \sim n^2 2^{1-n},$$ by what appear to me at a glance to be essentially combinatorial arguments. (Tikhomirov will be giving an online talk about this this Saturday.)

Neat! Can you say something about why this is so important that goes beyond what’s in this article?

• Wylie Beckert, Mathematicians bridge finite-infinite divide, Quanta, May 24, 2016.

If I learned about it and wrote about it, I’d feel the need to write something that’s different (and better) than this article in some way. One way would be to dig deeper.

Yes! Anyone curious about that can get some gossip here:

• Scott Aaronson, MIP* = RE, Shtetl-Optimized, January 16, 2020.

By the way: the paper on MIP* = RE cites someone who visits the $n$Café, namely Tobias Fritz, for having helped establish the connection to Connes’ embedding conjecture.

I don’t really understand this stuff, but I could learn it….

I know a bit about topological data analysis and persistent homology. Is there a theorem in this subject, or an application of this method, that you find particularly surprising?

Thanks. Is there some particularly exciting result in this area that I could focus on?

Anonymous Set Theorist:

In order to avoid bias, it might be helpful to divide the question into subareas (i.e., instead of asking for our favorite exciting mathematical results, ask for our favorite exciting results in number theory, set theory, functional analysis, etc.

I’m just looking for a few exciting topics to write about. Ultimately the choices will be completely biased by what I happen to find exciting, and can understand well enough to explain. I don’t have the energy to attempt an even-handed survey of different areas.

Avoid relying on Quanta magazine.

On the contrary, if they write about something I’m less likely to write about it, because that would be “old news”. There are lots of things that have not yet been popularized, I’ll give those get higher priority. (Of course I might be tempted to write about something if I feel they did a really bad job.)

Thanks for listing those set-theoretic results. I’d like to hear more about them.

Thanks! Could you say a bit more about what these are and (just as important) why they are exciting?

I know what a WKB approximation is, and I can imagine that situations where the WKB approximation is exact would be exciting. I don’t know what the Hitchin system is. I have a vague general idea of mirror symmetry in string theory. I don’t know what 3d mirror symmetry is (something about some sort of 3-dimensional field theory?). I don’t know what symplectic duality is.

Saw Huh give a great talk a while ago about matroids (about which I know little). And recently an amazing talk by Adiprasito who explained applications in geometric topology (closer to me; he outlined an approach towards the Singer conjecture). Super exciting.

Thanks for all of these! A lot of interesting things for me to study.