2020's Biggest Breakthroughs in Math and Computer Science

In 1935, Albert Einstein was disturbed by an idea in quantum physics. When two particles are quantum entangled, they can interact instantaneously across large distances. Einstein found this phenomenon "spooky." The following year, Alan Turing identified a problem that

computer

s could never solve. Computers normally operate based on inputs and outputs, but sometimes they can get stuck in infinite loops. Turing showed that there is no way to know when this will happen and called it the stopping problem. Today we recognize it in the Spinning Wheel of Death. In the 1930s, quantum entanglement and the detention problem seemed to have nothing to do with each other.

But this year, they were combined in a landmark test that unleashed a cascade of solutions to open problems in

computer

science

, physics, and

math

ematics. This is Henry Yuen. He is one of five co-authors of the test. Yuen: You know, what this article is about is computational complexity theory, which is like a branch of theoretical computer

science

. And he talks about the computational power of a model of what is called interactive testing. An interactive proof is a kind of logical interrogation method that models computation as the exchange of messages between two parties: a prover and a verifier.

To understand how this works, imagine that the tester is a police officer interrogating two subjects: the testers. You can't go out and confirm every detail of the suspect's stories, but by asking the right questions and pitting your subjects against each other, you can catch them in a lie or develop confidence that the facts are confirmed. Yuen: The cops will put these two suspects in different rooms, but it just so happens that these suspects can also share quantum entanglement to coordinate their responses in some spooky quantum-mechanical way. Yuen: The policeman's job is to try to find out what the truth really is.

The main result of this article is that, although these suspects may share quantum entanglement, police officers can actually interrogate them in such a way that they can discover the truth of any

math

ematical statement corresponding to an enormously complicated range of questions. This means that, in theory, a super-powerful quantum computer could verify answers to even unsolvable problems like the Turing stopping problem. Yuen: It's all these really beautiful pieces from different areas. Things from computer science, mathematics and physics, that before we did not think were so related to each other, and yet they are. I think it points to something much more interesting.

I don't know what, but you know there's a feeling that there's something else, you know, there's like a whole new world to discover. This is John Horton Conway. His infamous knot problem eluded mathematicians for half a century. The question was whether the Conway knot was actually a portion of a higher-dimensional knot, a property called division. This question turned out to be the answer to thousands of similar knots, but Conway resisted any attempt to untangle it. Lisa Piccirillo was a graduate student when she first heard about the Conway knot. Piccirillo: Well, I thought it was completely ridiculous that we didn't know if this knot was cut or not.

We have a lot of tools to do this kind of thing, so I didn't understand why for some 11 cross knots this should be so difficult. I think the next day, which was Sunday, I started trying to run the approach for fun and worked on it a little bit in the afternoons just to try to see what's supposed to be so difficult about this problem. And then the next week I had a meeting with Cameron Gordon, a senior surveyor, in my department about something else, and I mentioned it to him there. He said, "Really? You showed that the Conway knot isn't cut?" Like, show me.

And then I started posting it and he started asking detailed questions and then at some point he got really excited. Piccirillo's proof was published in Annals of Mathematics. Piccirillo: It was pretty surprising to me. I mean, it's just a knot. In general, when mathematicians prove things, we like to prove very broad general statements: all objects like this have some property. And I showed that a knot has something. I don't care about the knots. Although I do care about three- and four-dimensional spaces. And it turns out that when you want to study three- and four-dimensional spaces, you find yourself studying knots anyway.

Mathematics can sometimes seem like a messy mosaic. The major areas of study have never been fully written down, and to do so would have required using thousands of other definitions that do not yet exist. Now, imagine that you have a Library of Alexandria that contains all of history and the sum total of mathematical knowledge. With everything catalogued, an AI could be programmed to check increasingly complex tests and hopefully one day create new ones on its own. At Imperial College London, Kevin Buzzard is in the process of digitizing mathematics. He's teaching it to software called Lean, which is based on a growing library of proofs and theorems.

Buzzard: I decided this software was very interesting about three years ago and I've been making a lot of noise about it ever since. We took some very, very modern mathematics and just showed, you know, we taught it to Lean and Lean could handle it. And basically, that's when I realized that, really, I should be able to do anything. Lean has a large math library, 450,000 lines of code. The library just grows all the time every day, you know, 10 more, 10 more pull requests are added to this library. The growth is immense. It's just eating the math slowly. Buzzard: Computers speak a certain language, so there is a rapidly changing language that you have to learn.

And then once you've done that, you just explain the math but in that language. And the big problem is that in mathematics departments around the world we teach people mathematical ideas, but no one teaches them the language that these computers speak. Buzzard: Math isn't exactly what's sold. I mean, we tell college students that mathematics is a completely rigorous theory, you know, built from axioms. And in practice, that's not how math is done. Computers are quite demanding because they want to know what is going on. So one challenge we've faced is that people are slightly inaccurate and computers don't believe it.

Before you can teach something to the computer, you need to understand it perfectly. The act of addressing the details can sometimes clarify the situation. You end up with a test that's a little messy, and then you try to type it on a computer and in the end, you end up with a more clever argument. One of the goals is that we want to see a complete university curriculum in it. And you know, give us a couple more years and then we can honestly say that, in some ways, it's as smart as a bachelor's degree.