Graduate Student’s Side Project Proves Prime Number Conjecture

Jared Duker Lichtman, 26, has proved a longstanding conjecture relating prime numbers to a broad class of “primitive” sets. To his adviser, it came as a “complete shock.”

As the atoms of arithmetic, prime numbers have always occupied a special place on the number line. Now, Jared Duker Lichtman, a 26-year-old graduate student at the University of Oxford, has resolved a well-known conjecture, establishing another facet of what makes the primes special — and, in some sense, even optimal. “It gives you a larger context to see in what ways the primes are unique, and in what ways they relate to the larger universe of sets of numbers,” he said.

The conjecture deals with primitive sets — sequences in which no number divides any other. Since each prime number can only be divided by 1 and itself, the set of all prime numbers is one example of a primitive set. So is the set of all numbers that have exactly two or three or 100 prime factors.
Primitive sets were introduced by the mathematician Paul Erdős in the 1930s. At the time, they were simply a tool that made it easier for him to prove something about a certain class of numbers (called perfect numbers) with roots in ancient Greece. But they quickly became objects of interest in their own right — ones that Erdős would return to time and again throughout his career.

That’s because, though their definition is straightforward enough, primitive sets turned out to be strange beasts indeed. That strangeness could be captured by simply asking how big a primitive set can get. Consider the set of all integers up to 1,000. All the numbers from 501 to 1,000 — half of the set — form a primitive set, as no number is divisible by any other. In this way, primitive sets might comprise a hefty chunk of the number line. But other primitive sets, like the sequence of all primes, are incredibly sparse. “It tells you that primitive sets are really a very broad class that’s hard to get your hands on directly,” Lichtman said.

To capture interesting properties of sets, mathematicians study various notions of size. For example, rather than counting how many numbers are in a set, they might do the following: For every number n in the set, plug it into the expression 1/(n log n), then add up all the results. The size of the set {2, 3, 55}, for instance, becomes 1/(2 log 2) + 1/(3 log 3) + 1/(55 log 55).

Erdős found that for any primitive set, including infinite ones, that sum — the “Erdős sum” — is always finite. No matter what a primitive set might look like, its Erdős sum will always be less than or equal to some number. And so while that sum “looks, at least on the face of it, completely alien and vague,” Lichtman said, it’s in some ways “controlling some of the chaos of primitive sets,” making it the right measuring stick to use.

With this stick in hand, a natural next question to ask is what the maximum possible Erdős sum might be. Erdős conjectured that it would be the one for the prime numbers, which comes out to about 1.64. Through this lens, the primes constitute a kind of extreme.

Over the decades, mathematicians made partial progress toward a proof. They showed, for instance, that the conjecture was true for particular types of primitive sets.

Still, “it felt like we weren’t really all that close to it before Jared started working on it,” said Greg Martin, a mathematician at the University of British Columbia who has worked on related problems. András Sárközy, a mathematician at Eötvös Loránd University in Hungary and a frequent collaborator of Erdős, concurred. “It certainly seemed beyond reach,” he said.

Lichtman started working on the primitive set conjecture in 2018, during his last year as an undergraduate at Dartmouth College. “I was immediately fascinated with this question. It was just very mysterious how anything like this would be true,” he said. “It’s been my constant companion for the past four years.”

In 2019, he and Carl Pomerance, his adviser at Dartmouth — who, according to Lola Thompson, a mathematician at Utrecht University and a former student of Pomerance, essentially “came out of retirement to work with him” — found that a primitive set’s Erdős sum could be no greater than around 1.78. “It’s not too far off,” Martin said. “Only about 10% bigger than the conjecture for the primes.”

Lichtman and Pomerance obtained this constant by associating a new sequence of multiples to each number in a given primitive set. Consider again the primitive set {2, 3, 55}. Associated to the number 2 would be the sequence of all even numbers. Associated to the number 3 would be all multiples of 3 that are not also multiples of 2. And associated to the number 55 (5 × 11) would be all multiples of 55 whose smallest prime factor is 11 (therefore excluding all multiples of 2, 3, 5 and 7). Lichtman likens it to how words are indexed in a dictionary — only with primes used instead of letters to organize each sequence.

Merrill Sherman/Quanta Magazine

He and Pomerance then thought about how “dense” these sequences of multiples were — that is, how much of the number line they occupied. (For instance, the sequence of all even numbers has a density of 1/2, since even numbers make up half of all numbers.) They observed that if the original set was primitive, then its associated sequences of multiples wouldn’t overlap, and therefore their combined density was at most 1 — the density of all the whole numbers.

This observation was relevant because a 19th-century theorem by the mathematician Franz Mertens essentially allowed Lichtman and Pomerance to reinterpret the Erdős sum of a primitive set in terms of these densities. According to Mertens’ theorem, a special constant (roughly equal to 1.78), when multiplied by a term equivalent to the combined densities of these multiples, gave a maximal value for what the Erdős sum of a primitive set could be. And since the combined density was at most 1, Lichtman and Pomerance proved that the Erdős sum of a primitive set was at most around 1.78.

“It was a variation of Erdős’ original ideas, but it was a very slick, neat way … of getting a not-tight but not-too-bad upper bound,” said James Maynard, a mathematician at Oxford.

And for a few years, that seemed like the best mathematicians could do. It wasn’t clear how to drive that maximum down to 1.64. In the meantime, Lichtman graduated and moved to Oxford to do his doctorate with Maynard, where he’s mainly been working on other problems related to the primes.
“I knew he’d been thinking about this problem quite a lot on the side,” Maynard said, “but it was a complete shock when he suddenly, seemingly out of the blue, came up with a complete proof.”

Lichtman first realized that for numbers with relatively small prime factors, his earlier argument with Pomerance could still work: It was relatively straightforward to show that in this case, the constant 1.78 could be driven down to well below 1.64.

But numbers with relatively large prime factors — which are “close” to the primes in some sense — were another story. To deal with them, Lichtman found a way to associate not just one sequence of multiples to each number, but several sequences. As before, the combined density of all those sequences was at most 1. But this time, “these other multiples will kind of grow like weeds and take over some of the space,” Lichtman said.

Take the number 618 (2 × 3 × 103). Typically, you might associate to it all multiples of 618 whose smallest prime factor is 103. But sequences could instead be constructed using some of the smaller prime factors that were omitted. For instance, a sequence might consist of all the original multiples, while also permitting multiples of 618 that are divisible by 5. (Some constraints dictate which smaller prime factors can be used.)

The presence of these additional multiples meant that the combined density of the original multiples — the quantity that gets used in Mertens’ theorem — was actually less than 1. Lichtman found a way to put a more precise bound on what that density might be.

He then carefully determined what the worst-case scenario for a primitive set might look like: what balance it would strike between numbers with large prime factors and numbers with small prime factors. By patching together the two parts of his proof, he was able to show that the Erdős sum for such a scenario comes out to a value that’s less than 1.64.

“There’s this numerical moment of truth,” Maynard said. “I don’t know if it’s luck or what, that this is numerically just enough.”

Lichtman posted his proof online in February. Mathematicians noted that the work is particularly striking because it relies entirely on elementary arguments. “It wasn’t like he was waiting for all this crazy machinery to develop,” Thompson said. “He just had some really clever ideas.”

Those ideas have now cemented the primes as exceptional among the primitive sets: Their Erdős sum reigns supreme. “We all think of the primes as special,” Pomerance said. “And this just adds to their luster.”

Source