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.
... continue reading