Networks Hold the Key to a Decades-Old Problem About Waves
Introduction
Two centuries ago, Joseph Fourier gave mathematicians a magical technique. He conjectured that it’s possible to write almost any function as a sum of simple waves, a trick now called the Fourier transform. These days, the Fourier transform is used to understand everything from the chemical makeup of distant stars to what’s happening far beneath the Earth’s crust.
“Fourier series are everywhere in mathematics,” said Mehtaab Sawhney of Columbia University. “It’s part of the faith of mathematicians that Fourier series are important.”
Yet certain fundamental questions about the Fourier transform have remained stubbornly, and mysteriously, unanswerable.
In 1965, the mathematician Sarvadaman Chowla posed one such question. He wanted to know how small an extremely simple type of Fourier transform — a sum of cosine waves — could get. His problem sounded straightforward. But somehow, it wasn’t.
“The question is a bit of bait,” Sawhney said; it was designed to illuminate just how little mathematicians know. “Because we can’t show this, we clearly don’t understand the structure of these [sums] at all.”
For decades, mathematicians struggled with Chowla’s cosine problem. It became a benchmark for Fourier analysis techniques, used to explore how well they could detect deeper structure in sequences of numbers. The results were discouraging. “Progress was completely anemic,” said Tom Sanders of the University of Oxford.
In September, that suddenly changed. Four mathematicians — Zhihan Jin, Aleksa Milojević, István Tomon, and Shengtong Zhang — posted the first significant advance on the problem in 20 years. Their strategy had almost nothing to do with traditional Fourier analysis.
In fact, before last summer, the foursome had never even heard of Chowla’s cosine problem.
Feeling Low
In the early 1950s, Chowla and his fellow number theorist Nesmith Ankeny wanted to use the Fourier transform to better understand patterns in sets of numbers. Consider the set consisting of the numbers 2, 3, and 8. First, use each number in the set to define a cosine wave — 2 gives you cos(2x), for instance. Then add up all your waves to get cos(2x) + cos(3x) + cos(8x). This is just another way of writing your original set as a Fourier series. The series is highly structured: All the waves are cosines, and because there are no numbers in front of any of the cosines, all the waves are the same size. “It’s the simplest possible type of Fourier series you can have,” said Benjamin Bedert of the University of Cambridge. “And in general, we know quite a lot about Fourier series.”
The new wave defined by cos(2x) + cos(3x) + cos(8x) has peaks and valleys that reveal interesting properties of the original set of numbers. So Ankeny and Chowla sought to test how much they really understood about such a series. They wondered: For any set of N integers, what is the lowest value that the sum will ever take?
It’s easy to figure out the sum’s maximum. When x is zero, any cosine wave hits its maximum at 1. So our sum of three cosine waves gives us 1 + 1 + 1, or 3. Similarly, a sum of 10 million cosine waves has a maximum of 10 million. For any set of N integers, the maximum is simply N.
Yet understanding the cosine sum’s minimum is surprisingly difficult. While the different waves all hit their maximum simultaneously at least once (when x is zero), this is not true for the minimum. Perhaps the lowest points of the different waves will still align enough to produce a very low sum. Or perhaps the waves will interfere with each other so that it becomes impossible for the sum to get too low.
Zhihan Jin (left), Aleksa Milojević (top right), and István Tomon set out to solve a major problem in graph theory. In doing so, they unwittingly came up with a new approach to a seemingly unrelated problem on the Fourier transform.
From left: Courtesy of Zhihan Jin; Archives of the Mathematisches Forschungsinstitut Oberwolfach; Livia Tomon-Horvath
In 1952, Ankeny and Chowla conjectured that just as the maximum gets higher and higher as the number of integers in the original set gets bigger, the minimum should get lower and lower. This was proved several years later — prompting Chowla to sharpen the question in 1965. He wanted to know exactly how fast the minimum drops as N grows.
He knew of sets of N integers whose cosine sum had a minimum value around −$latex \sqrt{\textit{N}}$. Every other set he could think of dipped even lower, leading him to conjecture that for any set of N positive integers, the minimum of the corresponding cosine sum must be below −$latex \sqrt{\textit{N}}$.
Over the ensuing decades, a few mathematicians chipped away at the problem. But by the mid-2000s, there was still a massive gulf between what they were able to prove and what Chowla had predicted. According to the latest bound, proved in 2004 by Imre Ruzsa of the Alfréd Rényi Institute of Mathematics in Hungary, a sum of 1020 cosines — that’s a 1 with 20 zeros after it, about the number of molecules in a cubic inch of air — must have a minimum value smaller than about −7. By comparison, Chowla had predicted that the minimum would have to dip below −1010.
And yet, for the past 20 years, Ruzsa’s result has represented the pinnacle of progress on Chowla’s cosine problem.
Then an entirely unrelated research program finally broke the barrier.
Bridging the Divide
The program dealt with networks of nodes and edges called graphs.
Last summer, two sets of graph theorists — Jin, Milojević, and Tomon in Europe, and Zhang at Stanford University — were enthusiastically making progress on one of graph theory’s most central questions. The “MaxCut” problem is about the optimal way to cut a graph into two parts so that there are as many edges as possible connecting the parts. It’s a basic question about the structure of a graph, with real-world applications: A graph’s MaxCut might represent an efficient circuit design, for instance, or the lowest-energy state of a system of particles.
Mark Belan/Samuel Velasco/Quanta Magazine
But there’s no one-size-fits-all approach to finding a graph’s MaxCut, at least at the moment. (It’s what’s known as an NP-hard problem.) And so mathematicians instead attempt to estimate the MaxCut for specific classes of graphs.
In 2003, Benjamin Sudakov, a mathematician at the Swiss Federal Institute of Technology Zurich who would later mentor Jin, Milojević, and Tomon, posed a conjecture about the MaxCut of a particular kind of graph. This graph had no cliques — clusters of nodes that are all connected to one another.
A cluster of interconnected nodes forms a clique. This graph has a five-node clique, highlighted in red.
Last July, more than two decades later, Zhang proved a new bound on the MaxCut for such graphs. A few days later, Jin, Milojević, and Tomon improved on his result.
To do this, the researchers investigated important quantities called eigenvalues. Eigenvalues provide information about a graph’s structure. For example, the largest eigenvalue counts the number of edges in the graph; the second-largest measures the graph’s connectivity. Jin, Milojević, Tomon, and Zhang focused on the negative eigenvalues, building on a recent line of research that had linked them to a graph’s MaxCut. Their analysis of these eigenvalues ultimately allowed them to prove their new results.
The mathematicians decided to combine their separate results into a joint paper. But before they could finish, they received an unexpected email about Chowla’s cosine problem.
Cayley’s Graph
The email was from Ilya Shkredov, a mathematician at Purdue University in Indiana. Shkredov, a number theorist, pointed out that Chowla’s cosine problem could be reformulated in terms of graphs. Not the general kinds of graphs that the team was studying, but a special type of graph invented in 1878 by the mathematician Arthur Cayley.
To build a Cayley graph, imagine you’re once again working with the set {2, 3, 8}. Start with a bunch of nodes — it doesn’t really matter how many, so long as the number of nodes is prime and larger than the biggest integer in the set. Next, arrange the nodes in a circle and label each one with an integer. Then place an edge between two nodes if the difference between them is in the original set. So the nodes labeled 1 and 3 will be connected by an edge, because they differ by 2, and 2 is in the set {2, 3, 8}.
By the 1970s, mathematicians had figured out that embedded within the structure of Cayley graphs is information about the Fourier series from Chowla’s problem. A Cayley graph’s eigenvalues, it turns out, correspond exactly to different values that the cosine sum can have. The smallest eigenvalue therefore tells you how low the cosine sum can get.
“It’s a well-known thing,” Milojević said. “The connection is very classical.”
It allowed mathematicians to reframe the problem. If they could show that the smallest eigenvalue of a Cayley graph gets very small, it would mean that the cosine sum has to get very small as well — precisely what Chowla’s cosine problem is all about.
But no one could figure out how to exploit that connection.
“You try to hit a nail with a hammer only once you have a hammer,” Sudakov said. Mathematicians didn’t have a way of analyzing the lowest eigenvalue accurately enough to find out what they wanted to know about the minimum of the cosine sum.
Shengtong Zhang made major progress on the famous “MaxCut” problem, a fundamental question about graphs that has a host of practical applications.
Wanqi Zhu
But in their work on the MaxCut of graphs, Jin, Milojević, Tomon, and Zhang had unwittingly produced a hammer. While studying how the eigenvalues of a graph relate to its structure, they’d discovered that any graph that doesn’t have a low eigenvalue must be dominated by cliques. Shkredov, reading their proof, realized that this meant that the team had actually reframed Chowla’s cosine problem once more: There was no longer any need to analyze the eigenvalue directly. Instead, they just had to prove that the Cayley graphs didn’t have any large cliques. That would imply that the graphs each had a very low eigenvalue, finally enabling them to exploit the link between Chowla’s conjecture and graph theory.
From then on, “I think the main obstacle was believing we can do it,” Tomon said.
The Cliques Click
When Shkredov sent his email, the mathematicians were all on vacation. But Tomon, who was visiting his home city of Budapest, found time to toy with the Cayley graph.
After a bit of thinking, “it just clicked,” he said.
To see how Tomon’s idea works, let’s go back to our Cayley graph for the set {2, 3, 8}. Remember that proving Chowla’s conjecture means showing that the graph’s smallest eigenvalue gets very low. So first assume the opposite: that none of the eigenvalues are low. You’ll want to show that this assumption will eventually lead to a contradiction.
Based on the team’s work on MaxCut, if the Cayley graph has no small eigenvalues, then it must have a large clique — say, five nodes that are all connected to each other. This, in turn, means that if you take any two of those nodes, the difference between their integer labels is 2, 3, or 8.
Using a completely different set of techniques, Benjamin Bedert inched even closer to resolving Chowla’s cosine problem.
Romana Meereis
But now add 1 to each node to get a new set of five nodes. They’ll differ by the same amounts as the first set, meaning that they, too, will form a clique. Keep going, and you’ll generate more and more cliques. But there’s a problem: Cliques have lots of edges, while a Cayley graph, based on how it’s defined, has relatively few edges, which obey a very particular structure. Eventually, you’ll get so many cliques that you’ll have generated more edges than the Cayley graph can hold. This means that the earlier assumption that there was a large clique must have been false. Which, in turn, means that the smallest eigenvalue had to be low.
Once Tomon figured this out, the rest of the proof came together relatively easily. In September, he, Jin, Milojević, and Zhang posted their joint paper online. It mainly focused on how to analyze the lowest eigenvalues of graphs — work that, for one thing, allowed them to strengthen the bounds they’d found a few months earlier on the MaxCut of graphs without cliques.
But their headline result was about Chowla’s cosine problem. They’d proved that for any set of N integers, the corresponding cosine sum attains a value lower than −N1/10. For any realistic value of N, −N1/10 doesn’t differ too much from Ruzsa’s decades-old bound. But for huge values of N, like 1020, the difference starts to be noticeable: Jin, Milojević, Tomon, and Zhang show that a sum of 1020 cosines slides below −100, in comparison to Ruzsa’s bound of −7.
“For me, it’s very surprising,” Sudakov said. The group started with a result about graphs, and out of nowhere, they gained fresh insight on a seemingly unrelated problem.
Just two days after the researchers posted their paper, Bedert, the Cambridge mathematician, posted his own advance on the problem, using a more traditional approach from Fourier analysis. His result edges out the team’s bound by a hair: It says that for any set of N integers, the cosine sum attains a value less than −N1/7. For 1020, this lowers the minimum that Jin, Milojević, Tomon, and Zhang identified from −100 to around −720.
But what mathematicians find most noteworthy is that both of these results mark the first time that a proven estimate has the same form as Chowla’s conjectured bound. That is, the new bounds, like Chowla’s, can be written as a power of N. (Chowla’s bound of −$latex \sqrt{\textit{N}}$ is equivalent to −N1/2.) Ruzsa’s previous estimate cannot be written in this form.
The fog surrounding the Fourier transform is still dense. But these new techniques are a little better at seeing through it.
Though neither proof has fully bridged the gap to prove Chowla’s conjecture, mathematicians are excited. For now, “it is a little bit, I think, like the moon landing or the 4-minute mile,” Sanders said. “It’s not clear ahead of time what this is going to open up.”
The role that graphs played in the story is particularly intriguing. This isn’t the first time that graph theory and Fourier analysis have met. But so far, the links between the two fields have been one-offs. Now, Jin hopes that the specific connection between Chowla’s cosine problem and MaxCut hints at something broader. “Whatever is predicted in the Chowla problem, that phenomenon is more general,” he said. “It works in graphs.”
“We now have more problems that are in the same spheres of influence,” Sawhney said. “Knowing that things are living in the same world is very useful information. It’s very powerful.”
