After a five-year effort, a trio of mathematicians from across the country has solved a problem that has perplexed for more than 50 years.
The problem, the Kadison-Singer conjecture, is a statement about the mathematical foundations of quantum mechanics, more specifically a hypothesis about the mathematical nature of the way physicists can perform measurements in quantum systems. Although physicists have been assuming for years that eventually a positive result would be found, it was not until two papers were published in the journal Annals of Mathematics that proof of the conjecture was found.
“The purpose of these papers is to introduce a new technique to understand situations that mathematics previously could not understand,” said Adam Marcus, visiting researcher at Yale and the papers’ lead author.
At the same time that they released their paper on the Kadison-Singer conjecture, the team published a second paper in a subfield of mathematics called graph theory. The subfield deals with mathematical objects that can be used to model networks, road maps, disease contagion and connections in the brain, in addition to other applications. Within the subfield, graphs are mathematical objects which consist of a set of vertices and lines between them called edges — not the typical X and Y plot encountered in most math courses.
In deriving their results for both papers, the team used a novel technique, the method of interlacing polynomials. The technique takes advantage of certain manipulations one can perform on functions with specific properties. Though these polynomials have been studied and well understood for decades, the team was able to show one could use polynomials to solve a broad class of open problems.
“This was the Hail Mary pass,” said Yale professor of computer science and mathematics, senior author of the paper and MacArthur Fellow Dan Spielman. “We had no idea this was going to be a five-year project.”
After years of trying and failing to prove the Kadison-Singer conjecture, the researchers gave up, and turned their attention to another problem. That problem — in the subfield of graph theory — turned into their second paper, and the method they developed to solve it allowed them to return to and solve the first problem, the Kadison-Singer conjecture.
“In some sense, by going for a slightly lower target, we refined our tools,” said Spielman.
Spielman, whose background is in computer science and pure mathematics, wrote computer programs in the process of working on the proof. All of those programs proved many smaller conjectures, each of which suggested Kadison-Singer is true. Spielman also constructed programs that would come up with random matrices on which to test their mini conjectures.
“We tested them a lot [with computer programs], but not only could we not find counter-examples, but the conjectures looked really tight,” Spielman said.
Network sciences, or the application of graphs and graph theory to real world problems, has been a growing field at Yale. Spielman said that with the creation of the Yale Institute of Network Science in July 2013, the University now has a dedicated space to bring researchers together.
Many other researchers have been interested in the publication of the team’s work, in particular with the method of interlacing polynomials. Although the paper has only been published online, a duo of computer scientists from the University of California at Berkeley has already applied the method to the traveling salesman problem. The traveling salesman problem asks the question, “Given a list of addresses and a map, what is the shortest route one can take to visit each house?” The Berkeley team used the interlacing polynomial method to derive an approximation answer to that problem.
Additionally, the papers crossed boundaries within the mathematical community. The team used techniques from real analysis, linear algebra and probability to arrive at their result. Members of the mathematical community are beginning to ask questions about how exactly these results blur the lines between mathematical subfields, Marcus said.
The Kadison-Singer conjecture was first proposed in 1959.