Adam Marcus, Dan Spielman, and Nikhil Srivastava Prove 54-year old Kadison-Singer Conjecture

Ameya Mahajan
By Ameya Mahajan December 21, 2013 14:12
Diagram of interlacing polynomials and their alternating roots. Courtesy of Daniel Spielman.

Diagram of interlacing polynomials and their alternating roots. Courtesy of Daniel Spielman.

A team consisting of Adam Marcus, Daniel Spielman, and Nikhil Srivastava has proved the 1959 Kadison-Singer Conjecture. This conjecture, originally posited by Richard Kadison and Isadore Singer as the “Kadison-Singer Problem,” is an important cornerstone in the mathematics underlying quantum physics, relating to measurements of quantum properties and amounts.

A measurable state: the spin of an electron. Courtesy of Soul Physics.

A measurable state: the spin of an electron. Courtesy of Soul Physics.

Professor Daniel Spielman, of the Yale Applied Mathematics and Computer Science Departments, explained that the Kadison-Singer conjecture has a long history intertwined with many other problems. “The Kadison-Singer conjecture…is really very similar to [the work done by] Ackman and Anderson, which looks like a conjecture in linear algebra, you could say,” he explained. Over the years, mathematicians realized that this problem was similar to many other difficult and hitherto unsolved questions. “I got into this problem a little over 5 years ago, [with] a graduate student, Nikhil Srivastava, and an undergraduate, Josh Batson,” said Spielman. A comment from visiting Professor Gil Kalai of Hebrew University sent Spielman in the direction of the Kadison-Singer conjecture, which looked fairly similar to Spielman’s work at the time. “We were wrong,” said Spielman, “It was nothing like our work at the time.”

An exact statement of the Kadison-Singer Conjecture. Courtesy of Gil Kalai.

An exact statement of the Kadison-Singer Conjecture. Courtesy of Gil Kalai.

Upon starting work on the Kadison-Singer conjecture, Spielman and his team quickly realized that the problem would not be easily solved. Spielman said he and his team only came upon a good idea every six months, and only realized they were wrong about their previous idea once a year. However, Spielman maintained that his team made good progress on the problem. “An interesting thing worth mentioning is that the math we were using in this problem is actually very simple…that is, you could understand it after earning an undergraduate degree in mathematics,” said Spielman. The comparatively easy mathematics used in this case relates to special polynomials; the polynomials all have real roots, which is not commonly found in higher-order mathematics, and are part of interlacing families. Interlacing polynomials are two polynomials whose smallest roots alternate as x tends to infinity. Also crucial to Spielman’s work were computer programs. Spielman said, “We ran a lot of computer experiments…they work as something of a sanity check.” Spielman and his team designed computer programs that prove mathematical inequalities autonomously, preventing many missteps that could have extended the work time for this conjecture even further.

Professor Daniel Spielman. Courtesy of the MacArthur Foundation.

Professor Daniel Spielman. Courtesy of the MacArthur Foundation.

After years of work on the conjecture, Spielman and his team were finally able to confirm that the extensions referenced in the Kadison-Singer Conjecture are in fact unique, allowing the Kadison-Singer Conjecture to be used in order to create specific definitions of quantities in quantum physics.

The positive solution referred to here is the key statement confirming the validity of the Conjecture. Courtesy of Professor Daniel Spielman.

The positive solution referred to here is the key statement confirming the validity of the Conjecture. Courtesy of Professor Daniel Spielman.

The Kadison-Singer Conjecture has important consequences for the defining of quantum states. In quantum physics, some quantities, also called states, are definable and measurable, while others are probabilistic and can only be mathematically postulated. The Kadison-Singer Conjecture allows physicists to extend their knowledge about simultaneously measurable quantities and extend this to other potential measurable quantities. Spielman also said the conjecture has connections to theoretical computer science, his own field. “If I have a social network, with any number of people, that network has edges [connections that relate objects to one another] between each person. Our work with this conjecture lets us shave off many, many edges from that situation and still have a clear picture of what’s going on.” Spielman explained that these connections to fields other than mathematics were a driving force behind his decision to continue working on this problematic question.

Richard Kadison. Courtesy of The Mathematisches Forschungsinstitut Oberwolfach.

Richard Kadison. Courtesy of The Mathematisches Forschungsinstitut Oberwolfach.

Spielman and his team have another couple of papers planned in their current series of publications. He and his team would like to use the Kadison-Singer Conjecture to create some very simple proofs of complicated mathematical ideas: “We’d like to get rid of some ambiguity – for example, we like to say ‘a finite number’ – well, I’d like us to say ‘2’ instead,” he explained.

Isadore Singer. Courtesy of University of California, Berkeley.

Isadore Singer. Courtesy of University of California, Berkeley.

Ameya Mahajan
By Ameya Mahajan December 21, 2013 14:12