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."
halp! (Score:1, Insightful)
Can someone explain this problem in terms that an engineering grad would understand?
Also, what does the solution means in that framework? I kind of want to understand the why/how/what now...
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
Re: (Score:1)
Re: (Score:2)
If you have a 3 dimensional cube, divided into 27 cubelets, and two players playing tic-tac-toe, the first player can always win by choosing the center square. No matter where the second player goes, the first player can get two in a row (with the open space not lining up with the second player's first move), and then make a triangle.
x2 | |
----+----+---
x3 | x1 |
----+----+---
| | o2
Re: (Score:2, Interesting)
Not sure about the density Hales-Jewett theorum, but the method used seems simple enough. The problem he is trying to tackle is not one of determining a proof for the problem, but rather establishing that there either exists a proof for the problem given a set of parameters or does not exist a proof given those same parameters.
To me, it is this problem which seems to be the more useful, at least in general. Basically, if it is possible, through herustics (which is essentially all you're doing by hunting thr
Re: (Score:2, Insightful)
Your first paragraph is wrong (of course they're trying to prove a theorem, one that asserts that parameters exist for which the result they want is true), the method isn't "simple enough" unless you're a Ph.D.-level expert in combinatorics, and the rest of your post is absolute nonsense. Linux doesn't have the same rigid structure as the combinatorial objects being studied, and even if it did the constants involved in this theorem would very quickly get much bigger than the number of modules or even lines
Re: (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]
Too bad he used a blog (Score:3, Interesting)
What he really needed is a threaded message board ala Slashdot.
Re: (Score:2, Funny)
How about Subversion or GIT?
Re: (Score:1)
Why does everyone keep capitalizing all the letters in Git? It's not an acronym. Doing this just makes you look silly.
Like a git, you mean?
Re: (Score:2)
Re: (Score:2)
That wouldn't work. The indentation needed would go too deep. It's the same problem with "threads" on wordpress, except much more so. A different post management technique is needed.
Massive open collaboration in math (Score:5, Funny)
I wonder if you could do massive open collaboration for software? You could probably write an OS kernel, maybe even an entire operating system!
Oh come on! (Score:1)
Re: (Score:2)
On the Insert tab, the galleries include items that are designed to coordinate with the overall look of your document. You can use these galleries to insert tables, headers, footers, lists, cover pages, and other document building blocks. When you create pictures, charts, or diagrams, they also coordinate with your current document look.
This post was created in Word with the command =rand(1)
Re: (Score:2)
People would never invest time in anything without profit.
Not all profit is silver and gold, mate! Think of all the babes looking for some hot open source developer lovin!
List of authors (Score:5, Insightful)
Re: (Score:1)
Make it a regular expression.
Re: (Score:2)
I really think that the beauty of this sort of thing is that all contributors are there in front of you.
I love this sort of thing. These sort of guys (the fields winners) don't have to worry about getting publications and instead can just concentrate with getting on with the job. Everybody else can tag along for the ride. Beautiful.
Re:List of authors (Score:5, Informative)
Re: (Score:2)
Except that no-one will. Which is a major problem. As in, how do you gain a reputation without the use of your name? How will HR departments be able to check it. It's intractable. The HR department hasn't the time or expertise to determine who much was contributed by an individual and anyone on a hiring committee in the Maths department certainly won't have the time either. So, how do you choose who to get in for an interview?
And you thought lying on CV's was bad now. Just wait.
Prior Art (Score:4, Funny)
I totally tried "Massive Open Collaboration" on my homework and tests in high school. I most definitely came up with this idea first.
And, no, I still don't understand basic algebra? Why do you ask?
Surprise result (Score:2, Funny)
It turns out that 2 + 2 actually = 5.
I know; I'm surprised, too. Well, I'm off to patch my calculator.
Re: (Score:2)
For sufficiently large values of 2 [straightdope.com]. ;)
Why now? (Score:2, Interesting)
It would have been nice, had this been posted before they declared success.
Now all we have is a blog post with a gazillion comments, and all the interesting work has already been done.
Maybe next time we can all join the fun?
Re: (Score:2, Insightful)
Well, given that as far as I can tell everyone involved was a research mathematician, that is, a professor of mathematics, and that it included a few Fields medalists, that is the equivalent of Nobel Prize winners in maths, I would say that for this problem slashdot noise would have been highly counterproductive.
This is something for the cathedral, not the bazaar. That said he did mention intending to try to make the next problem more accessible.
Re: (Score:1)
To quote one of Gowers's original posts [wordpress.com] on the collaboration, "in order to have a reasonable chance of making a substantial contribution, you probably have to be a fairly experienced combinatorialist. In particular, familiarity with Szemeredi's regularity lemma is essential."
Gowers and Tao both mentioned this on their blogs at the beginning, so mathematicians who follow them and actually know what they're talking about had plenty of chances to get involved. The unwashed masses on Slashdot, on the other han
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: (Score:3, Interesting)
If that is the interpretation, then where is the crossover point between lower dimensional and higher dimensional space where the draws stop?
Re: (Score:1)
In the notation used in the wikipedia article, H is the number of dimensions, c is the number of symbols, n is the number of squares along each dimension, and delta is the fraction of the squares that are filled in. E.g., for normal tic-tac-toe, H=2, c=2, n=3, and delta=1 at the end of the game. For that particular set of parameters, we know that the theorem isn't tru
Re: (Score:3, Funny)
I postulate that with enough dimensions, my opponent's king will be in checkmate before I even make a move. If said number of dimensions are found to be within the confines of string theory, I would not owe my friend 20 bucks nor the sexual favors agreed upon in the rematch. Finally! A useful implication of string theory [xkcd.com].
Re: (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 cha
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: (Score:2, Troll)
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?
Well, a group of mathematicians from different institutions formed and managed, within a few weeks, to stop grandstanding for long enough to accomplish and exceed a pre-determined goal. This is somewhat remarkable.
Re: (Score:2)
To be fair, this is much more then "somewhat remarkable" for any academic discipline.
Re: (Score:2)
This is somewhat remarkable.
LOL. This happens all the time. LOL.
Re: (Score:2)
Not really. Partnerships emerge, but they tend to be medium-to-long term and toward the goal of developing a theory to mine for papers (not that there's anything wrong with this). This is different from forming a spontaneous "team" to solve a single problem in combinatorics.
My comment wasn't meant to be taken seriously; I was going for a bitter "funny". I don't understand "troll"; how many real working mathematicians are there on slashdot anyway? Ten at most?
Re: (Score:2)
Actually, it does happen all the time. It happens when people meet at conferences. This will happen to this sort of "team" as well. After all, everyone that actually contributed something knew each other. So, hardly spontaneous. That makes this thing spectacularly unremarkable.
The only difference here is that everyone was excited enough, because it was a "new" way of doing things, to remain relatively focused for a shorter period of time. Are you sure that this mentality is going to continue in the lo
Re: (Score:2)
Yeah, I suspect that a Fields medalist-combinatorist being involved just might have had more to do with it, than the fact that it was on a blog. Hell, everyone involved was already "world-class", which is frankly a bit unusual for a blog (not unique, just not representative) and definitely not what most people associate with "open collaboration"...
Fielder's choice (Score:2)
So a bunch of guys who all knew each other from the failed Nupedia project got together and wrote 50 articles in one week. Why is this newsworthy?
It is amazing what you can accomplish if you do not care who gets the credit. — Harry S Truman
I find it quite interesting to see the first law of collaboration confirmed among a small group of experts, after Nupedia so abjectly failed to do so. Bear in mind that I number myself among the lunatic fringe with a rather low regard for "pee
Re: (Score:2)
You have a very interesting definition of the word, "confirmed." Well, at least you can admit to being on the lunatic fringe.
Obligatory (Score:2)
The aswer they came up with was 42
Re: (Score:2)
Chaos
This was NOT massive!!! (Score:2)
From the blog post linked in the summery:
"""
but instead the number [of contributors] settled down to a handful, all of whom I knew personally.
"""
When did a couple people mean massively, again?
So, essentially, it was largely a couple guys who know each other, who decided to discuss the problem in public view, instead of solely through email. [sarcasm]Wow. Ground breaking stuff.[/sarcasm]
I'd hate to say I told you so...
Re: (Score:2)
No not really. A handful, though not necessarily common, isn't unheard of for Math Collaborations. Maybe instead of assuming things, you should actually look things up.
Also, massive is a fairly well defined term. So, saying that even a couple hundred is massive isn't being honest. That might be a lot, but certainly not massive.
I should also point out that if this sort of thing becomes common, then those couple hundred aren't going to be a lot. Seriously, this is about Maths. Choosing definitions that