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

ttt

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”.

ttt3

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

multitictactoe

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

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 c'_5, 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

labeltt

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:

labeltt2

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

ex1

or *4* is

141
242
343
444

ex2

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:

geo

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:

ex3

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 c_n 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 (c_n) to total spaces (3^n) 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.]

About these ads

20 Responses

  1. I hope most of this is understandable to those without any mathematics background, but I was unable to come up with a substitute for the end piece with the limit. Any suggestions to clarify that are appreciated.

  2. FWIW, I found it pretty understandable. (I have some mathematics background but not quite enough to follow the Polymath project directly.)

    One small note: it felt like you accidentally missed a “These are called combinatoric lines” statement somewhere between describing them and then starting to use the term.

    For that last bit, if you really wanted to un-mathify it, maybe something like this would work?

    “We then want to prove that as the number of dimensions increases towards infinity, the ratio of empty spaces to total spaces approaches zero.”

    (Or “gets really close to” instead of approaches, maybe.)

  3. Fixed as suggested. Thanks!

  4. Very interesting explanation — thanks! I’ve been reading some of the Polymath posts, but got glassy-eyed very quickly. it’s great to have a more human-readable explanation of the background.

  5. [...] who want to know more about the problem Jason Dyer has a beautifully simple explanation up at the Number Warrior. This is exactly the sort of work that I find most exciting in the polymath project and heartily [...]

  6. This is awesome; I was intrigued by the collaborative project, but the topic/terminology was beyond me. You have a gift for clear explanations!

  7. Great explanation, thanks!

  8. [...] Dyer gives a “simple as possible” overview of Timothy Gowers’ initiatives in A gentle introduction to the Polymath project. The post gives the background to the density Hales-Jewett problem. The line that caught my eye was [...]

  9. [...] [Incidentally, for the more casual followers of this project, a non-technical introduction to this project can be found at this post of Jason Dyer.] [...]

  10. [...] There is a new blog dedicated to polymath projects like the one I wrote about here. [...]

  11. [...] A gentle introduction to the Polymath project – Jason Dyer [...]

  12. [...] (תחת הכותב הראשי D.H.J Polymath). למתעניינים בהוכחה, הנה קישור להסבר לא מתמטי [...]

  13. [...] mathematical problems,” Gowers and commenters on his blog looked for a simpler proof for the density Hales-Jewett problem, (which asks, in a more complicated way than I am about to, how many squares can be removed from a [...]

  14. [...] 2010/06/26 While I was revisiting Gowers‘ “Mathematics: A Very Short Introduction” my mind wandered to the first Polymath project (essentially a massively collaborative effort to solve certain mathematics problems where participation seemed to follow the 90-9-1 principle). Anyone who wants to learn more about Polymath can from “A gentle introduction to the Polymath project“ [...]

  15. Jason, you and your readers may be interested in my new book The New Polymath.

    While it catalogs several modern day tech/science individual polymaths and several from history it is about the “enterprise polymath” – those that are taking 3,5, 10 strands of infotech, biotech, cleantech, nanotech and creating brand new solutions and leveraging multiple talent pools to solve some of our Grand Challeges. Over 150 innovative companies, products, people, places cataloged.

    the book website is at http://www.thenewpolymath.com and amazon is starting to ship in N. America and will follow in Europe in early July. Thanks

  16. [...] tackling large and difficult problems collaboratively via blog comments. I have written about them here and [...]

  17. I work for an organization that solves social problems through collaborative efforts: http://www.changemakers.com

    It could be interesting to compare best practices for sourcing solutions from the world and facilitating collaborative problem solving.

    This is a great project you have!

    Darlene

  18. [...] postmodern context of highly efficient nontraditional communication. One prime illustration is the Polymath Project initiated by Tim Gowers at Cambridge University which productively tackled the development of novel [...]

  19. [...] enforced by the authorities, but was a completely voluntary effort of mathematicians called the Polymath project. The initiative came from Timothy Gowers and has already resulted in a “probably [...]

  20. [...] on open science and the polymath project at TEDxWaterloo: GA_googleAddAttr("AdOpt", "1"); GA_googleAddAttr("Origin", "other"); [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 131 other followers

%d bloggers like this: