Solved!

Last June, when Daniel Spielman, Adam Marcus and Nikhil Srivastava posted their paper on the Kadison-Singer Conjecture online, the mathematical world did a double take. It seemed like the 54-year-old conjecture, first proposed by mathematicians Richard Kadison and Isadore Singer in 1959, had been solved. Comments started pouring in, fellow mathematicians began sharing it, scores of talks were organised — the proof was going viral. This July, Spielman, Marcus and Srivastava were awarded the George Polya Prize, given every two years for work in combinatorics or graph theory

What Kadison and Singer had asked back then was whether “pure states on abelian von Neumann algebras could be extended uniquely to pure states on non-abelian algebras”. That’s a mouthful, but in quantum physics it asks a vital question: The state of an electron is represented by observable quantities like position, spin or momentum. But according to Heisenberg’s Uncertainty Principle, observable quantities such as position and velocity can’t be measured simultaneously. So, can the value of one observable quantity be extrapolated to others that can’t be measured alongside? “The original question was motivated by the desire for a rigorous mathematical foundation for quantum mechanics,” says Srivastava, 35, working for the last two years with Microsoft Research in Bangalore.

It was 2008. Spielman, who is a professor of applied mathematics and computer science at Yale and a 2012 MacArthur fellow, was solving a different problem on the sparsification of graphs. Srivastava, then a graduate student at Yale, was working with him. They were looking at models to explain complex networks like Facebook, how they formed, interacted and how to ‘compress’ them. When Gil Kalai, an adjunct professor at Yale and a former Polya Prize winner, observed that the problem looked similar to the K-S Conjecture, they decided to go after it. What began as a side problem in 2009 took five years to complete. During the first two, Spielman, Srivastava and Marcus were at Yale. Then Srivastava moved for a post-doctorate to Princeton, meeting the co-authors “intermittently”. In the last year, they relied on email and Skype, for Srivastava had moved to Bangalore. There were “many spurts of hope and disappointment”. But when the solution came together, Srivastava says: “I started laughing. It fit so beautifully, you knew it was the ‘right’ proof. It combined ideas we had generated over five years.”

After posting the paper ‘Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem’, the trio was invited to hold talks, from Boston to Bordeaux and Bangalore. One of the key achievements of the trio’s proof is their new approach to the solution. While the averaging argument remains a nifty tool in math to prove conjectures, it applies to real numbers. For them, the challenge lay in applying it to a polynomial. “It’s like trying to find an average for colours,” says Srivastava. What they proved then was that the roots of the average polynomial are less than 0.9 — or, there’d be one specific polynomial with that property in the case of polynomials that interlace (their new technique). While the physical, that is, the quantum mechanical interpretation remains unproven and the proof doesn’t have algorithms yet, the conjecture has been proved true. The idea has wide-ranging applications, from quantum physics to graph theory for ‘compressing networks’ and finite dimensional geometry. Which means if, a decade later, your cellphones work better, you can thank the trio for solving the K-S problem.