Big Advance on Simple-Sounding Math Problem Was a Century in the Making
Addition and multiplication are each relatively straightforward operations. But when the two are combined, they lead to deep questions that mathematicians are still working to understand.
Samuel Velasco/Quanta Magazine
Introduction
One morning last November, the mathematician Hector Pasten finally solved the problem that had been dogging him for more than a decade by using a time-tested productivity hack: procrastination.
He was supposed to be writing a final exam for his number theory class at the Pontifical Catholic University of Chile in Santiago. To avoid the task, he started pondering, for the umpteenth time, one of his favorite sequences: 2, 5, 10, 17, 26 and so on, the list of all numbers of the form n2 + 1 (where n is a whole number).
Mathematicians have used this sequence for over a century to probe the fraught relationship between addition and multiplication, a tension that lies at the heart of number theory. Fundamental problems about multiplication — about, say, how numbers factor into primes — suddenly become much deeper and more challenging as soon as addition enters the picture. One of math’s biggest open questions, for example, asks whether every even number larger than 2 is the sum of two primes; another asks whether there are infinitely many pairs of primes that differ by only 2, such as 11 and 13.
The n2 + 1 sequence offers a good starting point for investigating the relationship between addition and multiplication, because it combines one of the simplest types of multiplication (squaring a number) with one of the simplest types of addition (adding 1). That doesn’t mean the sequence itself is simple. Mathematicians still can’t answer elementary questions about it, such as whether it contains infinitely many primes. “It doesn’t take far to get to the boundary of our knowledge,” said Andrew Granville of the University of Montreal. When mathematicians do manage to shift this boundary even a little, the techniques they develop often illuminate much broader questions about addition and multiplication.
Pasten was trying to show that the numbers in the sequence must always have at least one prime factor that is fairly large. On the morning when he should have been writing his final exam, he finally succeeded, by figuring out how to embed information about the prime factors of n2 + 1 in the structure of an equation called an elliptic curve.
Over lunch that day, he described his proof to his wife, the mathematician Natalia Garcia-Fritz. Given the surprising strength of his result, she “told me that I should probably check this many times,” Pasten said. “That afternoon I did so, and the theorems were still there.”
Hector Pasten spent more than a decade trying to solve a math problem at the interface of addition and multiplication. He finally succeeded when he decided to procrastinate on writing a final exam for one of his courses.
Natalia Garcia-Fritz
There was just one wrinkle: Pasten had no exam to give his students. He instead had them write an essay on whatever topic they wanted. “This turned out to result in very high-quality work,” he said.
Pasten submitted his proof to Inventiones Mathematicae, one of math’s preeminent journals, where it was accepted in just over a month — the blink of an eye by the field’s usual publication standards. “It’s a lovely advance on something that hasn’t seen much progress for essentially 100 years,” said Cameron Stewart of the University of Waterloo. Mathematicians hope it will translate into advances on related number sequences, too.
Pasten’s technique also enabled him to make progress on certain cases of the abc conjecture, yet another question that deals with the interplay between addition and multiplication, and one of the most famous — and controversial — unsolved problems in mathematics. “New (and correct) ideas in this area have been scarce,” Granville wrote in an email. “The originality and promise of his methods deserve wide attention.”
Large Primes
If a sequence of numbers gets larger and larger, that’s no guarantee that their largest prime factors will do likewise. Take the sequence n2 — the numbers 1, 4, 9, 16 and so on. It’s easy to find numbers in this sequence whose prime factors are small. For example, any power of 2 on this list (4, 16, 64, 256, 1024 …) has only one prime factor: 2.
But when you add 1 to this sequence, “you completely destroy all the information you had” about prime factors, Pasten said. The “primes behave in a very wild way.”
In 1898, Carl Størmer proved that, unlike in the n2 sequence, the largest prime factors of numbers in the n2 + 1 sequence approach infinity as n gets large. This finding showed that “something interesting is happening, something unusual,” Stewart said.
But Størmer couldn’t figure out how quickly the largest prime factors of n2 + 1 grow — a natural next step in characterizing the behavior of the sequence.
If you start calculating numbers in the sequence, most of them do seem to have at least one very large prime factor. But occasionally there’s a huge dip. For example, one number in the sequence, 586,034,187,508,450, has a prime factor of 67,749,617,053. But the largest prime factor of the next number in the sequence — 586,034,235,924,737 — is just 89. It’s these exceptions that make the problem hard.
In the mid-1930s, Sarvadaman Chowla and Kurt Mahler independently showed that for any value of n, the largest prime factor of n2 + 1 must always be at least as large as about log(log n). But log(log n) grows incredibly slowly — if you graph it, it looks flat to the naked eye. Mathematicians suspected that the largest prime factor of n2 + 1 actually grows much more quickly. But they couldn’t prove it.
In 2001, Stewart and Kunrui Yu of the Hong Kong University of Science and Technology developed a new approach toward studying prime factors in sequences, using an area of mathematics called transcendence theory. Two years later, Julien Haristoy figured out how to apply their method to the n2 + 1 sequence, eking out a small improvement over Chowla and Mahler’s result.
But since then, the subject has been at an impasse. “We’ve needed a new ingredient for a long time,” Granville said.
Small Exponents
Pasten has been cultivating that new ingredient for more than a decade. In 2012, when he was a graduate student at Queen’s University in Kingston, Ontario, his adviser, Ram Murty, suggested that he focus on problems that explore the interplay between addition and multiplication.
One of number theorists’ most potent tools for studying this interplay is to encode numbers into a type of equation called an elliptic curve. For instance, your numbers might appear as solutions to the equation, or in a related calculation called the discriminant. With the right encoding, mathematicians can tap into the rich structure of elliptic curves and make use of associated mathematical objects known as modular forms. “Whenever you can bring in those modular forms, for which there is a whole wonderful theory, it brings a lot of information,” said Marc Hindry of Paris Cité University.
Over the years, Pasten developed a new theory involving modular forms and related entities called Shimura curves, which allowed him to tackle many of the questions Murty had given him. “But I was not able to make any progress on the n2 + 1 problem, absolutely nothing,” he said. “That bothered me for many years.”
On the November morning when Pasten was supposed to be writing his exam, the n2 + 1 problem represented escape in more ways than one. Earlier that year, his father had died, and Pasten found himself turning to math for comfort. “I found mathematics really helpful for that,” he said. “Mathematics is not just about proving theorems — it’s about a way to interact with reality, maybe.”
Getting direct control over the prime factors of the n2 + 1 sequence seemed too hard, so Pasten had long ago set his sights on a more indirect attack: getting control over the exponents in the prime factorization. If you’re factoring a large number, it might consist of small primes raised to large exponents, or large primes raised to small exponents. But it can’t consist of small primes raised to small exponents — that wouldn’t make a large enough number. So if you can show that the exponents are small, then at least one of the primes must be large, exactly what Pasten wanted to prove.
As Pasten stared at some calculations on his blackboard from the previous day, he suddenly realized that he might be able to control the exponents in the prime factorization of n2 + 1 by creating the right kind of elliptic curve. After some experimenting, he found one — the equation y2 = x3 + 3x + 2n — whose discriminant comes out to n2 + 1 times a factor of −108.
Applying his theory of Shimura curves to this particular elliptic curve, he could show that the product of the exponents of n2 + 1 must be fairly small. This didn’t necessarily mean that all the exponents must be small, but it gave him enough control over them to be able to bring in Stewart and Yu’s older method from transcendence theory. By using the two techniques together, he was able to prove that the largest prime factor of n2 + 1 must be at least about (log(log n))2 — the square of the estimate Chowla and Mahler discovered in the 1930s. Pasten’s new growth rate is much higher than the previous record, though mathematicians suspect the true growth rate is higher still.
Even so, “it’s a remarkable improvement,” Hindry said.
Pasten was also able to use his techniques to improve estimates for certain cases of the abc conjecture, which says that if three whole numbers a, b and c (which share no prime factors) satisfy the equation a + b = c, then the product of their prime factors must be large compared to c. The conjecture, one of the most important in number theory, has been at the center of a decade-long controversy: The mathematician Shinichi Mochizuki claims to have proved it, but the majority of the mathematical community disagrees. Pasten’s work represents a completely different approach to the problem. While his result is far from a proof of the full conjecture, by some measures it represents the first significant progress in decades. “I feel the abc conjecture is a very stuck subject,” Granville said.
After Chowla and Mahler came up with their bound 90 years ago, mathematicians gradually established the same bound for an infinite family of related sequences, such as n2 + 3 or n5 + 2. Researchers will likely attempt the same with Pasten’s new bound, while also exploring the ramifications of his method for other problems at the interface of addition and multiplication. “The newness of the attack” makes this an exciting prospect, said Barry Mazur of Harvard University.
Just what will emerge from those explorations is hard to foretell. “That’s the problem with originality,” Granville said. But “he’s definitely got something pretty cool.”
