Prime numbers are the central characters in mathematics, the indivisible elements from which all other numbers are constructed. Around 300 B.C., Euclid proved that there’s an infinite number of them. Millennia later, in the late 19th century, mathematicians refined Euclid’s result and proved that the number of prime numbers over any very large interval between 1 and some number, x, is roughly x/log(x).
This estimate, called the prime number theorem, has only been proved to hold when x is really big, which raises the question — does it hold over shorter intervals?
Kaisa Matomäki, 32, grew up in the small town of Nakkila in western Finland, where she was a math star from an early age. She left home to attend a boarding school that specialized in math instruction, and as a senior she won first prize in a national mathematics competition. When she began serious mathematical research as a graduate student, she was drawn to prime numbers and, in particular, to questions about how they behave on smaller scales.
In 1896 mathematicians proved that roughly half of all numbers have an even number of prime factors and half have an odd number. In 2014 Matomäki, now a professor at the University of Turku in Finland, and her frequent collaborator, Maksym Radziwill of McGill University, proved that this statement also holds when you look at prime factors over short intervals. The methods they developed to accomplish this have been adopted by other prominent mathematicians, leading to a number of important results in the study of primes. For these achievements, Matomäki and Radziwill shared the 2016 SASTRA Ramanujan Prize, one of the most prestigious awards for young researchers in number theory.
But Matomäki’s results have only deepened the mystery surrounding primes. As she explained to Quanta Magazine, mathematicians had long assumed that a proof about even and odd numbers of prime factors over short intervals would lead inexorably to a proof about the prime number theorem over short intervals. Yet, when Matomäki achieved a proof of the first question, she found that a proof of the latter one moved even further out of reach — establishing once again that primes won’t be easily cornered.
In a pair of phone conversations, Quanta Magazine caught up with Matomäki to ask about the study of primes and the methods behind her breakthroughs. An edited and condensed version of our conversations follows.
Your work has dealt with two prominent related problems about prime numbers. Could you explain them?
One of the most fundamental theorems in analytic number theory is the prime number theorem, which says that the number of primes up to x is about x/log(x).
This is known to be equivalent to the fact that roughly half of the numbers up to x have an even number of prime factors and half of the numbers have an odd number of prime factors. It’s not obvious that the two are equivalent, but it’s known that they are equivalent because of facts related to the zeros of the Riemann zeta function.
So these two problems have been known to be equivalent for a long time. Where does your work on them begin?
I’ve been interested in questions about prime numbers and the prime number theorem, and that’s really related to this thing on the number of even and odd prime factors. So what Maksym Radziwill and I have studied is the local distribution of this thing. So even if you take a short sample of numbers, then typically about half of them have an even number of prime factors and half of them have an odd number of prime factors. This doesn’t only work from 1 to x, it also works in almost all very short segments.
Let’s talk about the methods you used to prove something about these very short segments — a way of working with something called multiplicative functions. These are a class of functions in which f(m x n) is the same thing as f(m) x f(n). Why are these functions interesting?
One can use them, for instance, to study these numbers that have an even number of prime factors or an odd number of prime factors. There is a multiplicative function that takes the value –1 if n has an odd number of prime factors and the value +1 if n has an even number of prime factors. This is sort of the most important example of a multiplicative function.
And you take these multiplicative functions and do a “decomposition” on them. What does that mean?
We take out a small prime factor from the number n. It’s a bit difficult to explain over the phone. We are looking at a typical number, n, in our desired interval, and we notice the number n has a small prime factor, and then we consider this small prime factor separately. So we write it as p x m where p is a small prime factor.
You started this work when you were looking at sign changes of multiplicative functions. These are situations where the sign (positive or negative) of the output of a function can tell you something about the input. Like, for example, a function that outputs a –1 when the input number has an odd number of prime factors and a +1 when the input number has an even number of prime factors. What were some especially significant moments along the way?
Originally, starting in 2013, Maksym and I worked on sign changes of another sequence that’s not related to this, but then we started to think about the more general question of sign changes of multiplicative functions. Then we both spent autumn 2014 in Montreal, where we worked intensively on this problem of sign changes of multiplicative functions and got into shorter and shorter intervals for these sign changes, and eventually at the end of the semester we realized we also get this result about half the numbers in very short intervals having an even number of prime factors and half having an odd number of prime factors.
That wasn’t the result you were after all along?
No, no, we didn’t think about that at all. We were thinking about sign changes of multiplicative functions, then later on we realized there were more interesting applications than this original problem we were thinking about.
What was it like when you realized the work had this implication?
Of course it was very nice. It doesn’t really tell you anything about the primes in the end; it only tells you about even and odd numbers of prime factors. But it is related to the primes, and of course we were very happy to realize that we had more applications, but it was a gradual process to get there. There was no single moment.
You use “sieve” methods in a lot of your work, though not for this prime number result we’ve been talking about. “Sieve” is such an evocative name for a math technique. Can you try to capture for people what it’s about?
It’s meant to sieve some numbers. If you want to get only primes you use some sort of sieve which only lets primes go, and all the composite numbers are held in the sieve. But it’s pretty technical to actually do it.
What kinds of things in math act as a sieve?
Essentially what one does is one cooks up a function, which is, say, positive with primes and zero or negative with other numbers.
So you have a function and if the input is a prime, it outputs a positive value?
Yeah, and if the input is not a prime it outputs a zero or a negative value. Instead of primes you study this function, and if you can show this function is positive for some set, say, then you know there are some primes. The point is that the function is easier to handle than the primes themselves.
How long have sieving methods been around?
The first sieve is the sieve of Eratosthenes, an ancient Greek, so very old. He noticed that if you want to generate all the primes, it’s enough to make a big table of numbers and cross out all the multiples of 2, then 3, then 5 and so on. You end up with only primes on your table.
When you and Radziwill won the 2016 SASTRA Ramanujan Prize, the citation noted that the methods you’ve developed have “revolutionized” number theory. What have been some of the most exciting consequences of the work?
We got these averages of multiplicative functions from very short intervals, and it has turned out to be very useful for other things. Terry Tao has worked on problems including the Erdős discrepancy problem using our work.
As a result of the discoveries you’ve made, do you have a different perspective on prime numbers than you used to?
I guess the surprising thing about the primes is that over short intervals, the fact that we can show that half the numbers have an even number of prime factors and half have an odd number doesn’t tell us anything about the number of primes.
Could you explain that?
Over long intervals, the prime number theorem is equivalent to half the numbers having an even number of prime factors and half having an odd number of prime factors. But in the very short intervals we are considering, it turns out it’s not equivalent.
So it’s surprising that over short intervals the two theorems are not equivalent?
What’s surprising is that we are able to do this thing about the even number of prime factors and odd number of prime factors, but we are not able to do the prime [number theorem]. It was thought that they are morally equivalent, having the same difficulty, but it turns out they are not.
Was there a moment where you thought this work would give you the prime number theorem over short intervals?
I think we were never optimistic about it. We’ve been trying it, but we haven’t been optimistic. We are still trying it, but it seems that this approach doesn’t really work for it, so we have to invent something new.
Is that disappointing?
Certainly it’s disappointing. I’ve been dreaming of doing primes in very short intervals for a long time and still would love to do it.
Correction: This article was published with a footnote that used a base-10 logarithm. The correct logarithm is the natural logarithm, base-e. The footnote has been removed.