Teenager Solves Stubborn Riddle About Prime Number Look-Alikes
After he posted his proof, Daniel Larsen enrolled at the Massachusetts Institute of Technology as a math major.
Katherine Taylor for Quanta Magazine
Introduction
When Daniel Larsen was in middle school, he started designing crossword puzzles. He had to layer the hobby on top of his other interests: chess, programming, piano, violin. He twice qualified for the Scripps National Spelling Bee near Washington, D.C., after winning his regional competition. “He gets focused on something, and it’s just bang, bang, bang, until he succeeds,” said Larsen’s mother, Ayelet Lindenstrauss. His first crossword puzzles were rejected by major newspapers, but he kept at it and ultimately broke in. To date, he holds the record for youngest person to publish a crossword in The New York Times, at age 13. “He’s very persistent,” Lindenstrauss said.
Still, Larsen’s most recent obsession felt different, “longer and more intense than most of his other projects,” she said. For more than a year and a half, Larsen couldn’t stop thinking about a certain math problem.
It had roots in a broader question, one that the mathematician Carl Friedrich Gauss considered to be among the most important in mathematics: how to distinguish a prime number (a number that is divisible only by 1 and itself) from a composite number. For hundreds of years, mathematicians have sought an efficient way to do so. The problem has also become relevant in the context of modern cryptography, as some of today’s most widely used cryptosystems involve doing arithmetic with enormous primes.
Over a century ago, in that quest for a fast, powerful primality test, mathematicians stumbled on a group of troublemakers — numbers that fool tests into thinking they’re prime, even though they’re not. These pseudoprimes, known as Carmichael numbers, have been particularly difficult to grasp. It was only in the mid-1990s, for instance, that mathematicians proved there are infinitely many of them. Being able to say something more about how they’re distributed along the number line has posed an even greater challenge.
Then along came Larsen with a new proof about just that, one inspired by recent epochal work in a different area of number theory. At the time, he was just 17.
The Spark
Growing up in Bloomington, Indiana, Larsen was always drawn to mathematics. His parents, both mathematicians, introduced him and his older sister to the subject when they were young. (She’s now pursuing a doctorate in math.) When Larsen was 3 years old, Lindenstrauss recalls, he started asking her philosophical questions about the nature of infinity. “I thought, this kid has a mathematical mind,” said Lindenstrauss, a professor at Indiana University.
Then a few years ago — around the time that he was immersed in his spelling and crossword projects — he came across a documentary about Yitang Zhang, an unknown mathematician who rose from obscurity in 2013 after proving a landmark result that put an upper bound on the gaps between consecutive prime numbers. Something clicked in Larsen. He couldn’t stop thinking about number theory, and about the related problem that Zhang and other mathematicians still hoped to solve: the twin primes conjecture, which states that there are infinitely many pairs of primes that differ by only 2.
After Zhang’s work, which showed that there are infinitely many pairs of primes that differ by less than 70 million, others jumped in to lower this bound even further. Within months, the mathematicians James Maynard and Terence Tao independently proved an even stronger statement about the gaps between primes. That gap has since shrunk to 246.
Larsen wanted to understand some of the mathematics underlying Maynard and Tao’s work, “but it was pretty much impossible for me,” he said. Their papers were far too complicated. Larsen tried to read related work, only to find it impenetrable as well. He kept at it, jumping from one result to another, until finally, in February 2021, he came across a paper he found both beautiful and comprehensible. Its subject: Carmichael numbers, those strange composite numbers that could sometimes pass themselves off as prime.
All but Prime
In the mid-17th century, the French mathematician Pierre de Fermat wrote a letter to his friend and confidant Frénicle de Bessy, in which he stated what would later be known as his “little theorem.” If N is a prime number, then bN – b is always a multiple of N, no matter what b is. For instance, 7 is a prime number, and as a result, 27 – 2 (which equals 126) is a multiple of 7. Similarly, 37 – 3 is a multiple of 7, and so on.
Mathematicians saw the potential for a perfect test of whether a given number is prime or composite. They knew that if N is prime, bN – b is always a multiple of N. What if the reverse was also true? That is, if bN – b is a multiple of N for all values of b, must N be prime?
Alas, it turned out that in very rare cases, N can satisfy this condition and still be composite. The smallest such number is 561: For any integer b, b561 – b is always a multiple of 561, even though 561 is not prime. Numbers like these were named after the mathematician Robert Carmichael, who is often credited with publishing the first example in 1910 (though the Czech mathematician Václav Šimerka independently discovered examples in 1885).
When Larsen finished his proof, he sent a draft to some of the top people in number theory. To his surprise, they read it and replied.
Katherine Taylor for Quanta Magazine
Mathematicians wanted to better understand these numbers that so closely resemble the most fundamental objects in number theory, the primes. It turned out that in 1899 — a decade before Carmichael’s result — another mathematician, Alwin Korselt, had come up with an equivalent definition. He simply hadn’t known if there were any numbers that fit the bill.
According to Korselt’s criterion, a number N is a Carmichael number if and only if it satisfies three properties. First, it must have more than one prime factor. Second, no prime factor can repeat. And third, for every prime p that divides N, p – 1 also divides N – 1. Consider again the number 561. It’s equal to 3 × 11 × 17, so it clearly satisfies the first two properties in Korselt’s list. To show the last property, subtract 1 from each prime factor to get 2, 10 and 16. In addition, subtract 1 from 561. All three of the smaller numbers are divisors of 560. The number 561 is therefore a Carmichael number.
Though mathematicians suspected that there are infinitely many Carmichael numbers, there are relatively few compared to the primes, which made them difficult to pin down. Then in 1994, Red Alford, Andrew Granville and Carl Pomerance published a breakthrough paper in which they finally proved that there are indeed infinitely many of these pseudoprimes.
Unfortunately, the techniques they developed didn’t allow them to say anything about what those Carmichael numbers looked like. Did they appear in clusters along the number line, with large gaps in between? Or could you always find a Carmichael number in a short interval? “You’d think if you can prove there’s infinitely many of them,” Granville said, “surely you should be able to prove that there are no big gaps between them, that they should be relatively well spaced out.”
In particular, he and his co-authors hoped to prove a statement that reflected this idea — that given a sufficiently large number X, there will always be a Carmichael number between X and 2X. “It’s another way of expressing how ubiquitous they are,” said Jon Grantham, a mathematician at the Institute for Defense Analyses who has done related work.
But for decades, no one could prove it. The techniques developed by Alford, Granville and Pomerance “allowed us to show that there were going to be many Carmichael numbers,” Pomerance said, “but didn’t really allow us to have a whole lot of control about where they’d be.”
Then, in November 2021, Granville opened up an email from Larsen, then 17 years old and in his senior year of high school. A paper was attached — and to Granville’s surprise, it looked correct. “It wasn’t the easiest read ever,” he said. “But when I read it, it was quite clear that he wasn’t messing around. He had brilliant ideas.”
Pomerance, who read a later version of the work, agreed. “His proof is really quite advanced,” he said. “It would be a paper that any mathematician would be really proud to have written. And here’s a high school kid writing it.”
The key to Larsen’s proof was the work that had drawn him to Carmichael numbers in the first place: the results by Maynard and Tao on prime gaps.
Unlikely — Not Impossible
When Larsen first set out to show that you can always find a Carmichael number in a short interval, “it seemed that it was so obviously true, how hard can it be to prove?” he said. He quickly realized it could be very hard indeed. “This is a problem which tests the technology of our time,” he said.
Larsen established a tighter constraint on Carmichael numbers than what he set out to prove.
Katherine Taylor for Quanta Magazine
In their 1994 paper, Alford, Granville and Pomerance had shown how to create infinitely many Carmichael numbers. But they hadn’t been able to control the size of the primes they used to construct them. That’s what Larsen would need to do to build Carmichael numbers that were relatively close in size. The difficulty of the problem worried his father, Michael Larsen. “I didn’t think it was impossible, but I thought it was unlikely he’d succeed,” he said. “I saw how much time he was spending on it … and I felt it would be devastating for him to give so much of himself to this and not get it.”
Still, he knew better than to try to dissuade his son. “When Daniel commits to something that really interests him, he sticks with it through thick and thin,” he said.
So Larsen returned to Maynard’s papers — in particular, to work showing that if you take certain sequences of enough numbers, some subset of those numbers must be prime. Larsen modified Maynard’s techniques to combine them with the methods used by Alford, Granville and Pomerance. This allowed him to ensure that the primes he ended up with would vary in size — enough to produce Carmichael numbers that would fall within the intervals he wanted.
“He has more control over things than we’ve ever had,” Granville said. And he achieved this through a particularly clever use of Maynard’s work. “It’s not easy … to use this progress on short gaps between primes,” said Kaisa Matomäki, a mathematician at the University of Turku in Finland. “It’s quite nice that he’s able to combine it with this question about the Carmichael numbers.”
In fact, Larsen’s argument didn’t just allow him to show that a Carmichael number must always appear between X and 2X. His proof works for much smaller intervals as well. Mathematicians now hope it will also help reveal other aspects of the behavior of these strange numbers. “It’s a different idea,” said Thomas Wright, a mathematician at Wofford College in South Carolina who works on pseudoprimes. “It changes a lot of things about how we might prove things about Carmichael numbers.”
Grantham agreed. “Now you can do things you never thought of,” he said.
Larsen, meanwhile, just started his freshman year at the Massachusetts Institute of Technology. He’s not sure what problem he might work on next, but he’s eager to learn what’s out there. “I’m just taking courses … and trying to be open-minded,” he said.
“He did all this without an undergraduate education,” Grantham said. “I can only imagine what he’s going to be coming up with in graduate school.”
