AI crossed long-standing limits in multiplication and Fourier transforms

Transcript

Transcribed by machine (Whisper) from the episode’s audio, so a word may be off here and there.

1. 14:17

   you know, we, I mean, it was only a month ago or a little more that we saw a solution of the Navier-Stokes problem, right, which was one of the seven millennium problems that have chosen as the seven most important problems in all of math, you know, and this showed that, you know, these standard differential equations that govern the motion of a fluid like water in three dimensions you know can produce you know just starting from smooth initial conditions can produce a singularity in finite time right that's you know i mean you know it's very arcane how they constructed it but i think the statement itself is not that arcane right it's uh you know it just said it's saying if water were an infinitely you know divisible continuous substance uh then there would be some, you know, smooth initial conditions for water. We're just following the laws of

2. 15:16

   classical physics. In finite time, some of the water would get accelerated to an infinite speed, right? That's kind of an amazing property to know of these, you know, very classical equations that we've, you know, had for hundreds of years, okay? So, you know, we've seen, you know, in just the open ai drop from last week you know some really really surprising new algorithms okay there's now a way to multiply two uh n digit integers in time that is less than n log n right which had stood as a barrier for half a century, okay?

3. 16:00

   You know, and many of us believed that that was going to be the ultimate limit for how fast you could multiply two numbers. Okay, now we know it's not. You know, for, there's a better algorithm for the Fourier transform. You know, probably not a practical one, okay, but, you know, eventually, for big enough, right, the Fourier transform is one of the workhorses of all of computation. I mean, your phone, you know, all your electronics are just using it constantly, right, to process signals.

4. 16:31

   And we have not known what is the fastest way to do a Fourier transform. And we just learned that what we thought was the limit, you know, again, n log n is not the limit. We saw, you know, progress on the Riemann hypothesis, okay, that, you know, probably, you know, the best progress toward proving the Riemann hypothesis that there has been in many decades, right? The Riemann hypothesis, you know, many mathematicians would call that the greatest open problem in all of math. You know, I would personally vote for P versus NP. They can fight me about that. But the Riemann hypothesis is basically a statement about how many prime numbers are there up to a given number, right? You know, and that's a basic thing that I mean, you know like almost anyone could could could wonder about even as a kid it's like you know

5. 17:23

   as you count you you you you list the prime numbers up to 10 up to 100 up to a thousand you know you see that they're thinning out right but but they're only thinning out kind of gradually right there's still plenty of prime numbers you know once you get above a thousand or ten thousand okay so you know it was only uh around the year 1900 that we finally proved you know, the basic rate at which the prime numbers thin out, that basically the number of primes up to n is about n divided by the log of n, okay? You know, that this is called the prime number theorem, you know, one of the crowning achievements of all of number theory, okay? But what we don't know is how accurate of an estimate that is, okay? And the Riemann hypothesis says it actually is a very accurate estimate you know the the error is sort of only the the square root of n type of

6. 18:18

   error that you would expect from kind of ordinary random fluctuations uh and you know that's been you know one of the great questions of number theory since since the 1800s right uh um um david hilbert was asked i think you know what what what would he ask if he were woken up 500 years in the future. He said, first thing I'll ask, has the Riemann hypothesis been proved? Okay. And, you know, we, so, so it still hasn't been, but, but we, we now, you know, a lot of the consequences of it, actually, we now know from the, one of the results that OpenAI proved a week ago, which was called the quasi Riemann hypothesis. Okay. So, I mean, you know, I could, I could go on and on you know some some of the results really are arcane you know some of them are you know especially in places like algebraic geometry I don't understand the statements of you

7. 19:17

   know it would it would take me some time to understand uh the statements of what was proved but especially in areas like theoretical computer science you know combinatorics number theory some of them are really not that hard to understand if if someone uh just you know knows like a little bit you know like high school level college level math and they want to go understand it yeah the