This morning’s list of new submissions to the mathematics section of the arXiv brings a paper signed by “D. H. J. Polymath.” The name is too good to be true, of course. The paper is the first fruit of a project instigated by Timothy Gowers of Cambridge. In a blog post last January, Gowers asked “Is massively collaborative mathematics possible?” and proposed a problem that might serve as a test case. There were more than 100 responses, and soon the game was on. Discussion began in the comments section of Gowers’s blog and was later supplemented and summarized in a Wiki maintained by Michael Nielsen.
The problem under attack is known as the density Hales-Jewett theorem (hence Dr. Polymath’s initials). The ordinary version of the Hales-Jewett theorem states that if you play tic-tac-toe on a board of high enough dimension, the game can never end in a draw. When you have filled in all the boxes, some row or column or diagonal in the multidimensional grid must consist entirely of x‘s or o‘s—even if you’ve been trying to reach a stalemate position. The theorem also holds with more than two players and more than two symbols, provided the dimension of space is high enough. The “density” version of the theorem says that sometimes you can’t avoid a winning play even if you stop before filling in all the boxes: A grid-spanning line of solid x‘s or o‘s is certain to appear as soon as the density, or fraction of filled boxes, reaches a threshold level.
The density version of the Hales-Jewett theorem was proved almost 20 years ago by Hillel Furstenberg and Yitzhak Katznelson, so this is not an open problem. But the Furstenberg-Katznelson proof drew on some results from ergodic theory, a branch of mathematics that seems slightly exotic for a problem stated in such simple, finite terms. Gowers asked if there might be a purely combinatorial proof. And he focused attention specifically on the case where each row and column of the tic-tac-toe board has three positions and there are three players. In other words, the grid is a 3 × 3 × 3 × . . . × 3 hypercube where each vertex is to be marked with one of three symbols.
The combinatorial proof is given in the Polymath paper, which also puts a bound on how high a dimension is needed. The bound is 2 ↑↑ O(1/δ3), where δ is the density and the double-arrow notation indicates an “exponential tower” of 2s — namely O(1/δ3) of them.
A collective pseudonym such as Polymath immediately brings to mind the famous Nicolas Bourbaki. As in the writings of that French group, the Polymath paper includes no listing of contributors. But there’s a difference: The Bourbakists were a secretive bunch, a sort of sleeper cell within mathematics, and historians have pieced together who did what only in retrospect. The Polymath group describes their style of work as “open source” mathematics. It’s all there on the web.
I participated in one of the polymaths in a small way when I wrote a program, a genetic algorithm based optimizer. Others were approaching the problem from the direction of linear programming. For a while there, it was a fun three way race between the human solvers, the linear programmers and my genetic algorithm of which I was running as many as 19 instances at a time.
I don’t want to set off the spam filter otherwise I would link to some of my solutions which are on my blog. However, anybody who is interested can go see them.
Speaking from the inside, it was a very fun experience with a sense of being at the cutting edge. Some people think this will be a major way of doing mathematics in the future. Supplemented with more everyday ways of doing mathematics, this would be a welcome development.