Mathematicians Outwit Hidden Number Conspiracy

Intuition tells mathematicians that adding 2 to a number should completely change its multiplicative structure — meaning there should be no correlation between whether a number is prime (a multiplicative property) and whether the number two units away is prime (an additive property). Number theorists have found no evidence to suggest that such a correlation exists, but without a proof, they can’t exclude the possibility that one might emerge eventually.

“For all we know, there could be this vast conspiracy that every time a number n decides to be prime, it has some secret agreement with its neighbor n + 2 saying you’re not allowed to be prime anymore,” said Tao.

No one has come close to ruling out such a conspiracy. That’s why, in 1965, Sarvadaman Chowla formulated a slightly easier way to think about the relationship between nearby numbers. He wanted to show that whether an integer has an even or odd number of prime factors — a condition known as the “parity” of its number of prime factors — should not in any way bias the number of prime factors of its neighbors.

This statement is often understood in terms of the Liouville function, which assigns integers a value of −1 if they have an odd number of prime factors (like 12, which is equal to 2 × 2 × 3) and +1 if they have an even number (like 10, which is equal to 2 × 5). The conjecture predicts that there should be no correlation between the values that the Liouville function takes for consecutive numbers.

Many state-of-the-art methods for studying prime numbers break down when it comes to measuring parity, which is precisely what Chowla’s conjecture is all about. Mathematicians hoped that by solving it, they’d develop ideas they could apply to problems like the twin primes conjecture.

Dispersing Clusters

Radziwiłł and Kaisa Matomäki of the University of Turku in Finland didn’t set out to solve the Chowla conjecture. Instead, they wanted to study the behavior of the Liouville function over short intervals. They already knew that, on average, the function is +1 half the time and −1 half the time. But it was still possible that its values might cluster, cropping up in long concentrations of either all +1s or all −1s.

In 2015, Matomäki and Radziwiłł proved that those clusters almost never occur. Their work, published the following year, established that if you choose a random number and look at, say, its hundred or thousand nearest neighbors, roughly half have an even number of prime factors and half an odd number.

“That was the big piece that was missing from the puzzle,” said Andrew Granville of the University of Montreal. “They made this unbelievable breakthrough that revolutionized the whole subject.”

It was strong evidence that numbers aren’t complicit in a large-scale conspiracy — but the Chowla conjecture is about conspiracies at the finest level. That’s where Tao came in. Within months, he saw a way to build on Matomäki and Radziwiłł’s work to attack a version of the problem that’s easier to study, the logarithmic Chowla conjecture. In this formulation, smaller numbers are given larger weights so that they are just as likely to be sampled as larger integers.

Tao had a vision for how a proof of the logarithmic Chowla conjecture might go. First, he would assume that the logarithmic Chowla conjecture is false — that there is in fact a conspiracy between the number of prime factors of consecutive integers. Then he’d try to demonstrate that such a conspiracy could be amplified: An exception to the Chowla conjecture would mean not just a conspiracy among consecutive integers, but a much larger conspiracy along entire swaths of the number line.

He would then be able to take advantage of Radziwiłł and Matomäki’s earlier result, which had ruled out larger conspiracies of exactly this kind. A counterexample to the Chowla conjecture would imply a logical contradiction — meaning it could not exist, and the conjecture had to be true.

But before Tao could do any of that, he had to come up with a new way of linking numbers.

A Web of Lies

Tao started by capitalizing on a defining feature of the Liouville function. Consider the numbers 2 and 3. Both have an odd number of prime factors and therefore share a Liouville value of −1. But because the Liouville function is multiplicative, multiples of 2 and 3 also have the same sign pattern as each other.

That simple fact carries an important implication. If 2 and 3 both have an odd number of prime factors due to some secret conspiracy, then there’s also a conspiracy between 4 and 6 — numbers that differ not by 1 but by 2. And it gets worse from there: A conspiracy between adjacent integers would also imply conspiracies between all pairs of their multiples.

“For any prime, these conspiracies will propagate,” Tao said.

To better understand this widening conspiracy, Tao thought about it in terms of a graph — a collection of vertices connected by edges. In this graph, each vertex represents an integer. If two numbers differ by a prime and are also divisible by that prime, they’re connected by an edge.

For example, consider the number 1,001, which is divisible by the primes 7, 11 and 13. In Tao’s graph, it shares edges with 1,008, 1,012 and 1,014 (by addition), as well as with 994, 990 and 988 (by subtraction). Each of these numbers is in turn connected to many other vertices.

Taken together, those edges encode broader networks of influence: Connected numbers represent exceptions to Chowla’s conjecture, in which the factorization of one integer actually does bias that of another.

To prove his logarithmic version of the Chowla conjecture, Tao needed to show that this graph has too many connections to be a realistic representation of values of the Liouville function. In the language of graph theory, that meant showing that his graph of interconnected numbers had a specific property — that it was an “expander” graph.

Expander Walks

 An expander is an ideal yardstick for measuring the scope of a conspiracy. It’s a highly connected graph, even though it has relatively few edges compared to its number of vertices. That makes it difficult to create a cluster of interconnected vertices that don’t interact much with other parts of the graph.

If Tao could show that his graph was a local expander — that any given neighborhood on the graph had this property — he’d prove that a single breach of the Chowla conjecture would spread across the number line, a clear violation of Matomäki and Radziwiłł’s 2015 result.

“The only way to have correlations is if the entire population sort of shares that correlation,” said Tao.

Proving that a graph is an expander often translates to studying random walks along its edges. In a random walk, each successive step is determined by chance, as if you were wandering through a city and flipping a coin at each intersection to decide whether to turn left or right. If the streets of that city form an expander, it’s possible to get pretty much anywhere by taking random walks of relatively few steps.

But walks on Tao’s graph are strange and circuitous. It’s impossible, for instance, to jump directly from 1,001 to 1,002; that requires at least three steps. A random walk along this graph starts at an integer, adds or subtracts a random prime that divides it, and moves to another integer.

It’s not obvious that repeating this process only a few times can lead to any point in a given neighborhood, which should be the case if the graph really is an expander. In fact, when the integers on the graph get big enough, it’s no longer clear how to even create random paths: Breaking numbers down into their prime factors — and therefore defining the graph’s edges — becomes prohibitively difficult.

“It’s a scary thing, counting all these walks,” Helfgott said.

When Tao tried to show that his graph was an expander, “it was a little too hard,” he said. He developed a new approach instead, based on a measure of randomness called entropy. This allowed him to circumvent the need to show the expander property — but at a cost.

He could solve the logarithmic Chowla conjecture, but less precisely than he’d wanted to. In an ideal proof of the conjecture, independence between integers should always be evident, even along small sections of the number line. But with Tao’s proof, that independence doesn’t become visible until you sample over an astronomical number of integers.

“It’s not quantitatively very strong,” said Joni Teräväinen of the University of Turku.

Moreover, it wasn’t clear how to extend his entropy method to other problems.

“Tao’s work was a complete breakthrough,” said James Maynard of the University of Oxford, but because of those limitations, “it couldn’t possibly give those things that would lead to the natural next steps in the direction of problems more like the twin primes conjecture.”

Five years later, Helfgott and Radziwiłł managed to do what Tao couldn’t — by extending the conspiracy he’d identified even further.

Enhancing the Conspiracy

Tao had built a graph that connected two integers if they differed by a prime and were divisible by that prime. Helfgott and Radziwiłł considered a new, “naïve” graph that did away with that second condition, connecting numbers merely if subtracting one from the other yielded a prime.

The effect was an explosion of edges. On this naïve graph, 1,001 didn’t have just six connections with other vertices, it had hundreds. But the graph was also much simpler than Tao’s in a key way: Taking random walks along its edges didn’t require knowledge of the prime divisors of very large integers. That, along with the greater density of edges, made it much easier to demonstrate that any neighborhood in the naïve graph had the expander property — that you’re likely to get from any vertex to any other in a small number of random steps.

Helfgott and Radziwiłł needed to show that this naïve graph approximated Tao’s graph. If they could show that the two graphs were similar, they would be able to infer properties of Tao’s graph by looking at theirs instead. And because they already knew their graph was a local expander, they’d be able to conclude that Tao’s was, too (and therefore that the logarithmic Chowla conjecture was true).

But given that the naïve graph had so many more edges than Tao’s, the resemblance was buried, if it existed at all.

“What does it even mean when you’re saying these graphs look like each other?” Helfgott said.

Hidden Resemblance

While the graphs don’t look like each other on the surface, Helfgott and Radziwiłł set out to prove that they approximate each other by translating between two perspectives. In one, they looked at the graphs as graphs; in the other, they looked at them as objects called matrices.

First they represented each graph as a matrix, which is an array of values that in this case encoded connections between vertices. Then they subtracted the matrix that represented the naïve graph from the matrix that represented Tao’s graph. The result was a matrix that represented the difference between the two.

Helfgott and Radziwiłł needed to prove that certain parameters associated with this matrix, called eigenvalues, were all small. This is because a defining characteristic of an expander graph is that its associated matrix has one large eigenvalue while the rest are significantly smaller. If Tao’s graph, like the naïve one, was an expander, then it too would have one large eigenvalue — and those two large eigenvalues would nearly cancel out when one matrix was subtracted from the other, leaving a set of eigenvalues that were all small.

But eigenvalues are tricky to study by themselves. Instead, an equivalent way to prove that all the eigenvalues of this matrix were small involved a return to graph theory. And so, Helfgott and Radziwiłł converted this matrix (the difference between the matrices representing their naïve graph and Tao’s more complicated one) back into a graph itself.

They then proved that this graph contained few random walks — of a certain length and in compliance with a handful of other properties — that looped back to their starting points. This implied that most random walks on Tao’s graph had essentially canceled out random walks on the naïve expander graph — meaning that the former could be approximated by the latter, and both were therefore expanders.

A Way Forward

Helfgott and Radziwiłł’s solution to the logarithmic Chowla conjecture marked a significant quantitative improvement on Tao’s result. They could sample over far fewer integers to arrive at the same outcome: The parity of the number of prime factors of an integer is not correlated with that of its neighbors.

“That’s a very strong statement about how prime numbers and divisibility look random,” said Ben Green of Oxford.

But the work is perhaps even more exciting because it provides “a natural way to attack the problem,” Matomäki said — exactly the intuitive approach that Tao first hoped for six years ago.

Expander graphs have previously led to new discoveries in theoretical computer science, group theory and other areas of math. Now, Helfgott and Radziwiłł have made them available for problems in number theory as well. Their work demonstrates that expander graphs have the power to reveal some of the most basic properties of arithmetic — dispelling potential conspiracies and starting to disentangle the complex interplay between addition and multiplication.

“Suddenly, when you’re using the graph language, it’s seeing all this structure in the problem that you couldn’t really see beforehand,” Maynard said. “That’s the magic.”