Excellent Reads

...certain fundamental questions about the Fourier transform have remained stubbornly, and mysteriously, unanswerable.

In 1965, the mathematician Sarvadaman Chowla(opens a new tab) 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.

...

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.

...

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