Networks Hold the Key to a Decades-Old Problem About Waves

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.

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 💬. 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.

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 −N^1/10. For any realistic value of N, −N^1/10 doesn’t differ too much from Ruzsa’s decades-old bound. But for huge values of N, like 10²⁰, the difference starts to be noticeable: Jin, Milojević, Tomon, and Zhang show that a sum of 10²⁰ 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 −N^1/7. For 10²⁰, 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⚡$ is equivalent to −N^1/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.”

Correction: January 29, 2026
An earlier version of the text implied that Benjamin Sudakov was the sole author of a 2003 conjecture about the MaxCut of certain graphs. He was in fact one of four authors.