Massive Open Collaboration In Math Declared a Success 60
nanopolitan writes "In late January, Tim Gowers, a Fields Medal winner at Cambridge University, used his blog for an experiment in massive online collaboration for solving a significant problem in math — combinatorial proof of the density Hales-Jewett theorem. Some six weeks (and nearly 1000 comments) later, Gowers has declared the project a success, and some of the ideas have already been written up as a preprint."
It's about n-dimensional tic-tac-toe. (Score:5, Informative)
What you won't be able to figure out from the slashdot summary, or from either of the links (unless you're a specialist) is that this is a theorem about n-dimensional tic-tac-toe. [wikipedia.org] The idea is that you make an n×n×n×...×n in some number of dimensions, and then you fill in some fraction of the boxes with x's and o's (or possibly some set of more than 2 symbols). The theorem says that if the dimension is high enough, and the fraction of the boxes that get filled in is high enough, you're guaranteed to have a line of symbols (possibly diagonal) that wins the tic-tac-toe game. In other words, a tic-tac-toe game in a high-dimensional space can't end in a draw, and can't even go on for very long before someone wins. The definition of "high enough" is what they're trying to pin down. They apparently proved it (or just made some progress toward proving it?) in a particular special case.
Re:halp! (Score:5, Informative)
A good way to think about it is a very abstract and sophisticated version of the "Pigeonhole principle" :
Lets say you have k + 1 balls and only k bins. If you want to put all the bills into those bins then you are going to have to put at least 2 balls into one of the bin.
Ramsey theory deals with general problems of this type where if you have too much of one thing (balls) then something else is bound to happen (two balls forced to share a bin).
e.g if you have at least six friends at a party then they are bound to be a subset of 3 friends who either all know each other or all don't know each other.
The idea is that once you get a certain density or to a certain quantity of something, some other structure is bound to appear.
This Density Hales-Jewett theorem specifically deals with playing tic-tac-toe in high dimensional cubes
i.e if you have a D dimensional hyper cube or whatever and the dimension D is sufficiently large then there is guaranteed to be a win for one player (unlike the regular version which can end in a draw).
Disclaimer: IANAM
Massive? (Score:3, Informative)
How was it massive? In the author's own words:
"There seemed to be such a lot of interest in the whole idea that I thought that there would be dozens of contributors, but instead the number settled down to a handful, all of whom I knew personally."
So a guy had a problem to solve, and batted some ideas back-and-forth amongst a few of his mates. Why is this newsworthy?
Re:halp! (Score:2, Informative)
Terry tao's blog has an explanation that's about as simple as you're going to find. (At least one that actually explains the math without handwaving).
http://terrytao.wordpress.com/2009/02/05/upper-and-lower-bounds-for-the-density-hales-jewett-problem/ [wordpress.com]
Re:It's about n-dimensional tic-tac-toe. (Score:3, Informative)
That's the Hales-Jewett theorem. The density Hales-Jewett(3) is a little different. Suppose you're putting X's on a 3x3x...x3 (n-dimensional) grid. Such a grid has 3^n points. What the theorem says is that if you've put X's on at least, say, 1% of the 3^n points, then you must have made a line somewhere if n is large enough. You can replace the 1% with whatever fraction you please, but that will change how large n has to be. No, the theorem doesn't state exactly how large n has to be, but already it's a challenging problem.
Re:List of authors (Score:5, Informative)