A gentle introduction to the Polymath project

[This post is written for the non-mathematician. So if there’s something that needs clarification, please ask!]

About seven weeks ago Timothy Gowers started the Polymath project.

It seems to me that, at least in theory, a different model could work: different, that is, from the usual model of people working in isolation or collaborating with one or two others. Suppose one had a forum (in the non-technical sense, but quite possibly in the technical sense as well) for the online discussion of a particular problem. The idea would be that anybody who had anything whatsoever to say about the problem could chip in. And the ethos of the forum — in whatever form it took — would be that comments would mostly be kept short.

[Source: Is massively collaborative mathematics possible?]

Dr. Gowers chose a problem in mathematics that he thought amenable to an online collaborative approach, then kicked things off with a blog post. Six weeks later, the main problem he proposed was declared (essentially) solved. However, the project still continues apace, especially at threads at Terry Tao’s blog.

I’m going to explain the main idea of what Polymath accomplished in as comprehensible a manner as possible.

I. But first, a related problem

So, Tic-Tac-Toe: X and O alternate turns, and whoever gets 3 of their own symbol in a row wins; if the board is filled there’s a tie. I remember figuring out the “perfect game” strategy when I was 7 and smoking all challengers. Due to its simplicity, people teaching recreational mathematics like to use it as a starting example.

Let’s change the game a little, and say before gameplay begins, some of the squares are “removed”.

You’ll notice it’s still possible to get 3 in a row in the last row or the last column, but it’s not much of a game anymore. However, we aren’t really caring about the game itself, but rather:

Make as few removals as possible so that it is impossible to get 3 in a row. How many empty squares are left?

You might be wondering (after you do a third removal in the lower right corner, and count 6 squares remaining, giving an answer of 6) how this might be a problem worthy of mathematicians. To answer that, we need to take things to the next level…

II. Multi-dimensional tic-tac-toe

Now it gets interesting! Let’s suppose you are playing multi-dimensional tic-tac-toe on the board above (dimensions of 4x4x4).

The As, Bs, and Cs represent possible winning lines for a player

Question #1: After removing the fewest squares possible so there’s no way to win, how many squares are left open?

(Feel free to attempt this and leave your answer in the comments.)

Now, take the same problem to any size board and any dimension. This is known as the Moser’s cube problem. One of the major accomplishments of the Polymath project so far is to obtain a value for , which takes the classic 3×3 tic-tac-toe board into 5 dimensions (so 3x3x3x3x3) and asks how many squares are left after removing the minimum number of squares to prevent a win (which turned out to be 124). Take a look at how elaborate the proof was.

III. Some notation

When doing anything in mathematics, it helps to have a common notation. Notice in the grid above I have numbered the columns from left to right as 1-3, and the rows from bottom to top as 1-3, and write each square as the number of the column followed by the number of the row.

This way when I talk about one possible solution, instead of saying I remove the upper left, center, and bottom right squares, I can talk about removals 13, 22, and 31 leaving behind squares 23, 33, 12, 32, 11, and 21.

(Question #2: How many possible solutions are there?)

Of course this can be extended to further dimensions:

For example, the lower right square in the third grid is the number 413.

IV. Combinatorial lines

What we’ve been using so far are called geometric lines. As I already mentioned, part of the Polymath group worked with (and are still working with) this type of line, but there are others.

Let’s say with the 4x4x4 example above. Call the character * a wild card, sort of the Joker in a card deck. When I say *21, that is shorthand for giving four different numbers:

121
221
321
421

or *4* is

141
242
343
444

Every set formed by the wildcard procedure is called a combinatoric line. There’s a lot of overlap with geometric lines, but there are geometric lines which are not combinatoric lines:

However, all combinatoric lines are also geometric lines. (Side note: geometric lines can be represented by two wildcards: suppose * means 1-2-3, and @ means 3-2-1, then *@ is the geometric line 13-22-31, just as in the diagram above.)

V. The big problem

Once again we’re removing points on the tic-tac-toe grid, but this time we want to avoid any combinatoric lines. Note this can lead to setups which remove all combinatoric lines but not all geometric ones:

13-22-31 would clearly win Tic-Tac-Toe, but it isn’t a combinatoric line because it can’t be represented by using the * wildcard.

Time for the big problem: let’s restrict ourselves to what’s called the k=3 case, meaning our numbers only go 1 to 3, but we can change the dimension to whatever we want (3, 3×3 [normal Tic-Tac-Toe], 3x3x3, 3x3x3x3, etc.) Let n be the dimension of the grid. For each dimension n, get rid of all the combinatorial lines in as few removals as possible; let the number of empty spaces left after this is done. We then want to prove that as the number of dimensions increases towards infinity, the ratio of empty spaces () to total spaces () approaches zero.

This problem is called the density Hales-Jewett problem. There already existed a proof, but it used somewhat indirect and abtruse methods from ergodic theory. The idea of the project is to produce a new proof, using “purely combinatoric” methods, which can be thought of (roughly) as “in a more intuitive way”.

The proof that was discovered was restricted to k=3 as above, but it seems quite possible to take the same method to any k, which the Polymath group is now doing. (UPDATE: Has now done.)

[If you enjoyed this post, you may also like my explanation of the 5th Polymath project.]