Dan Spielman, a Yale computer scientist, wanted to model complex online communities like Facebook, hoping to gain insight into how they form and interact. That's one of the precepts of Science 2.0, understanding how people can participate and scientists can collaborate without being drowned in a lot of 'noise' before being put on the right path to either.
A colleague in Jerusalem observed that aspects of Spielman’s research brought to mind a math problem that had been stumping people since Dwight Eisenhower was in office — the Kadison-Singer math problem. The 1950s? A puzzle that wasn't even from a paper, but from the “Related Questions” section of a paper on extensions of pure states?
It looked low-hanging fruit — but that turned into a five-year journey.
First posed in 1959, the Kadison-Singer problem asks, at its core, if unique information can be extrapolated from a scenario in which not all features can be observed or measured(1). The idea is particularly relevant to abstract fields like quantum physics, operator theory, complex analysis, graph theory, signal processing, and finite-dimensional geometry. In these fields, it is often impossible to quantify every characteristic of a system. You can see why Science 2.0 has been struggling to create a method more robust than a text adventure.
Richard Kadison. Konrad Jacobs, Erlangen, Copyright is MFO - Mathematisches Forschungsinstitut Oberwolfach, used under creative commons. Link: Wikipedia
Its origin was quantum physics, where you might want to know three things about a particle — position, spin, and momentum. It is known that by measuring spin and position, you can calculate the particle’s momentum as well, though its exact value cannot be observed. Proving the Kadison-Singer problem meant confirming that this always happens, for every physical system, making it possible to determine unobservable events from observable events.
For Spielman, it meant an improved ability to model interactions among groups within complex networks. In his original models, the interactions between groups were all equal. By proving that the Kadison-Singer conjecture was correct, he could strengthen or weaken interactions between different communities to more realistically model virtual networks.
So, in June 2013, when Spielman and co-authors Adam Marcus, and Nikhil Srivastava publicly posted a proof of the Kadison-Singer conjecture, it was not only a triumph for them, but also great news for a variety of scholars and technologists, and certainly on Science 2.0.
In the last year, Spielman and collaborators have traveled the world to give more than 100 talks on their work, in cities ranging from Boston to Bordeaux to Bangalore. The Society for Industrial&Applied Mathematics has awarded them George Pólya Prize.
Polynomials and their roots
The work began in 2009, when Adam Marcus was a newly appointed Gibbs Assistant Professor in Applied Mathematics and Nikhil Srivastava was a graduate student working in Spielman’s group. Together, Marcus, Srivastava, and Spielman broke the problem into three parts, all dealing with the roots of certain polynomials, or the values of x when y is equal to zero in a mathematical relationship such as y=3x2+6x+12.
Part 1 required the team to prove that all of the roots for these polynomials are real numbers, and part 2 required that the three prove the roots of certain polynomials interlace, or alternate in ascending order. For example, if one polynomial has roots 1, 4, and 8 and another has roots 0, 2, and 7, then they interlace.
Within a year the team members had worked through the first two parts and felt confident they could tackle the third part as quickly: demonstrating that there are upper bounds limiting the magnitude of the alternating polynomial roots.
“Parts one and two were always easier for us because they were fundamentally qualitative,” said Spielman. “There are fairly general techniques for proving qualitative statements like ‘polynomial p(x) is real-rooted.’ On the other hand, proving bounds on how large the roots of certain polynomials can be involved fairly intricate computations. To solve part three we had to come up with a very novel way of reasoning about where the roots of polynomials can lie.”
Years passed and life changed. Srivastava took a position with Microsoft Research in India. Marcus joined Crisply, a start-up company in Cambridge, Massachusetts, that allowed him to devote an entire day each week to working on the Kadison-Singer problem. And Spielman came to international attention after he was named a MacArthur Fellow. But the Kadison-Singer problem remained a constant for them all.
“We could never get excited on working on other problems,” said Spielman, who at Yale is professor of computer science, mathematics, and applied mathematics. “The Kadison-Singer problem was just too interesting and compelling: Every approach we pursued revealed beautiful structures. When you are following an approach to a math problem and you discover something beautiful, you take it as an indication that you are on the right path. We kept getting that feeling.”
Even though Spielman, Marcus, and Srivastava did not want to stray from their work on the Kadison-Singer problem, the pressure to publish was increasing. The team decided to take a slight detour to investigate Ramanujan graphs, which describe very sparse networks that are still highly connected. These graphs were often counterintuitive, required deep and difficult mathematics, and were only informative for a small subset of networks. Spielman, Marcus, and Srivastava thought the work they’d already done on the Kadison-Singer problem would yield simpler proofs for Ramanujan graphs that would apply to a larger number of networks.
They were correct.
Nikhil Srivastava, Adam Marcus, Dan Spielman. Credit: Yale University
What the team wasn’t expecting was that Ramanujan graphs were, in fact, the key to the frustrating third part of the Kadison-Singer problem. By expanding the applications of Ramanujan graphs, Spielman, Marcus, and Srivastava gained insight on how to approach the challenging third part of the Kadison-Singer problem.
“I just started laughing,” said Srivastava. “The solution fit together so beautifully and sensibly you knew it was the 'right' proof and not something ad hoc. It combined bits of ideas that we had generated from all over the five years we spent working on this.”
Although the proof of the Kadison-Singer problem has received the majority of the attention, the work done by Spielman and his team on the second part of the problem, interlacing polynomials, is driving the team’s future work.
“Adam and Nikhil and I will be writing papers with two more applications of the technique this summer,” said Spielman.
Source: Holly Lauridsen, Yale News
(1) See SoulPhysics.org
Kadison-Singer Conjecture. Let be a discrete maximal abelian subalgebra of , the algebra of bounded linear operators on a separable Hilbert space. Let be a pure state on that subalgebra. Then there exists a pure extension of to all of , and that extension is unique.
- PHYSICAL SCIENCES
- EARTH SCIENCES
- LIFE SCIENCES
- SOCIAL SCIENCES
Subscribe to the newsletter
Stay in touch with the scientific world!
Know Science And Want To Write?
- Ghost Light From Dead Galaxies - A Hubble Halloween
- Greenpeace Says Its GMOs Are Better Than Science's GMOs, Still Hates Golden Rice
- Reduce Prostate Cancer Risk By Sleeping With Lots Of Women - But Not Men
- Homo Floresiensis: Hobbit Species Continues To Provoke Questions About Human Evolution
- Everyone Hates Daylight Savings Time - But It Might Improve Public Health
- Okay With Disgusting Images? You Vote This Way 95 Percent Of The Time
- Supersonic Laser-Propelled Aircraft Get A Step Closer
- "Twelve years in a major urban public school system, and I couldn't once bring myself to eat a school..."
- "Hardly a day goes by without some creative new take on the eternal Evil White Man meme. Without..."
- "There would be no controversy if it were all balloons and ponies stories like that. But I hope..."
- "Let's talk about this disaster: I lost a course at the university where I work and became ineligible..."
- "Partisan nastiness doesn't advance dialogue. We are all in this together. You asked for solutions..."
- Battle of Britain: NGOs and scientists clash over proposal to loosen EU GMO restrictions
- Genetically modified clean energy from bacteria
- Designer babies: You can screen for cystic fibrosis but intelligence is a ways off
- Science as profane: What superstition of 1752 and 2014 share in common
- What’s so “natural” about “natural crop breeding”?
- Worried you have cancer? Take a Google pill!