The Polymath project harnesses the power of the Internet to use massive collaboration to solve a major problem in record time

By Julie Rehmeyer

Web edition: December 8, 2009

Enlarge

Tic-tac-toe many times over

The Density Hales-Jewett Theorem concerns a high-dimensional version of tic-tac-toe on large grids. This video game for an iPod uses a three-dimensional tic-tac-toe board with a grid of size 4.

Credit: http://www.agileapps.ca/

Late last January, University of Cambridge mathematician Tim Gowers decided to run a little experiment. Was it possible, he wondered, for a large number of mathematicians to collaborate openly on the Internet, pooling their ideas around a single problem? If it were possible, would it be easier, more efficient, more fun? Could the mathematicians together solve a problem they might not be able to solve individually?

So he posed a problem on his blog, one that was important and challenging and that lots of people had already worked on, including himself. To get the conversation started, he told people about ideas he’d had that he thought might work — but, he said, he’d never quite managed to push the ideas through on his own, nor to convince himself that the approach was fatally flawed.

The theorem Gowers asked everyone to collaborate on is a special case of the “Density Hales-Jewett” theorem. To understand it, imagine removing just enough squares from a tic-tac-toe board to make it impossible for either player to win. Deleting three squares along a diagonal would be sufficient. Now imagine doing the same thing on a much bigger tic-tac-toe board, with as many squares on a side as you like and with as many dimensions as you like. The Density Hales-Jewett Theorem says that as the number of dimensions gets higher, you have to remove a higher and higher percentage of squares to block a win. For very high dimensions, you have to remove practically all of the squares. (Strictly speaking, it uses a more general kind of line called a “combinatorial line.” Every ordinary line is a combinatorial line, but not vice versa.)

The theorem had already been proved, but mathematicians have found the proof a bit wanting. A good proof is a key that can unlock understanding, but this proof was long and complicated and used a difficult branch of math called ergodic theory. The result was that most mathematicians (including Gowers) couldn’t even follow it. More direct proofs had been found for many similar problems, so it seemed likely one existed for this one too.

There was another reason to be excited about finding a new proof: If it were fully general, it would imply a result known as Szemerédi’s theorem, which is a cornerstone of combinatorics. And while Szemerédi’s theorem had already had a number of proofs, each new proof so far had provided key insights that had opened up new areas of math.

But the “Density Hales-Jewett” theorem problem was known to be hard, and because this collaborative way of solving it was a novel experiment, Gowers set a modest criterion for success: He didn’t aim to solve the problem, just to know whether the particular strategy he proposed was workable. Furthermore, he limited their goal to proving the theorem for grids with three squares on a side (but any number of dimensions). Past experience suggested that four or more squares would be much harder to prove. That limitation meant they wouldn’t prove Szemerédi’s theorem, but it seemed like a reasonable place to start.

Gowers set a few simple ground rules: comments should be short and as easy to understand as possible, incomplete ideas were particularly welcome, technical work should be delayed until clearly needed, etc. He was partly codifying rules he tried to follow when doing research on his own, but he was also hoping to shape the discussion to maximize the value of the collaboration. So, for example, he discouraged highly polished posts because, he wrote in his blog, “the ideal outcome would be a solution of the problem with no single individual having to think all that hard. The hard thought would be done by a sort of super-mathematician whose brain is distributed amongst bits of the brains of lots of interlinked people.”

Gowers christened it the “Polymath Project” and opened his blog for comments from anyone around the world, with mathematical training or not.

Within a day, the comments had started coming in. Jason Dyer, a high-school mathematics teacher from Arizona, was the first to chime in (he eventually got his students working on the problem, too). Soon the blog attracted a heavy hitter: Terence Tao, a Fields-medal winner and mathematician at the University of California, Los Angeles. Within a few days, traffic on the blog was sufficiently heavy that Gowers found he was consumed by it. “It was extremely enjoyable,” he says, “but somewhat addictive.”

At first, the team had many more questions than answers, and no one was confident that the group was going to get anywhere. But over time, a promising approach emerged — one almost totally different from the one that Gowers had proposed.

Over the course of the project, 27 people participated, contributing more than 800 comments. But once a particular, promising approach emerged, the team narrowed down to a handful of people — far more than in a typical mathematical collaboration, but far fewer than the dozens that Gowers had initially imagined.

Just 37 days after Gowers began the project, the team found the solution. “It was a genuinely new type of solution with surprising aspects and ingredients,” says Gil Kalai of Hebrew University. Most astonishingly, the Polymath Project proved a far bigger result than it had originally been aiming for: It turns out their proof for the case of a grid with three squares on a side generalized to any number of squares. So they had a simple proof of the full density Hales-Jewett theorem and, along with it, a new proof of Szemerédi’s theorem.

Ryan O'Donnell, a theoretical computer scientist at Carnegie Mellon University, has written up a first draft of the result, and the Polymath team is working on a final version to submit for publication.

Ironically, despite the startling success of the proof, the project in some ways didn’t live up to Gowers’ initial imaginings. The relatively small number of participants was one part, but there also didn’t seem to be any emergent “super-mathematician,” and the participants reported working quite hard indeed. “It was very hectic,” O’Donnell says. “I had to think for four or five hours a day to come up with some small idea or question to ask. Eventually, after it was over, Gowers said that he spent a lot of time too, so then I felt better.”

An ordinary collaboration, however, almost certainly wouldn’t have come up with a solution so quickly. “It felt like the difference between driving a car and pushing it,” Gowers says.