# Massive Open Collaboration In Math Declared a Success

#### timothy posted more than 5 years ago | from the you-count-the-feet-we'll-count-the-toes dept.

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."*

## I Didnt RTFA (-1, Troll)

## jellomizer (103300) | more than 5 years ago | (#27246239)

So did the train A make it to Kingston at 11:35 am and intersected Train B from Albany at 4:30pm

## Re:I Didnt RTFA (-1, Offtopic)

## Anonymous Coward | more than 5 years ago | (#27246647)

## Does anyone else see the pot of gold . . . . (-1, Offtopic)

## Veni Vidi Dormi (975178) | more than 5 years ago | (#27246489)

Endof thisRainbow's?Hollah @ Vernor Vinge!

## halp! (1, Insightful)

## Anonymous Coward | more than 5 years ago | (#27246605)

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! (5, Informative)

## Anonymous Coward | more than 5 years ago | (#27247205)

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:halp! (1)

## teacher_dude (959208) | more than 5 years ago | (#27257015)

## Re:halp! (1)

## OwnedByTwoCats (124103) | more than 5 years ago | (#27260445)

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:halp! (1, Interesting)

## jd (1658) | more than 5 years ago | (#27247227)

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 through possibilities thrown out by the combinatorial logic), to determine if a solution must exist (or must not exist) to a given problem given constraints, we can use the same approach to solve quite a number of "there exists"-type problems herustically.

In the case of Linux, this would suggest that if you can define tight enough constraints on a given module (the equivalent of the constraints imposed in the original problem), it should be possible to prove whether or not an arc exists through that module which would violate the constraints.

without having to find that arcIf an arc exists that would violate the constraint, that would be the same as finding a "good reason" why the constraints will not work in the original problem addressed in TFA.

This would seem to offer an approach to verification of even fairly complex software, without having to clear all of the hurdles raised by formal software proofs. If you don't have to find the buggy arc, only show that such an arc must exist, then you can use this to identify areas in the code which need fixing.

Since you can bisect any code and then test each of the subcomponents, you can narrow down which blocks of code are faulty without having to be able to prove why, how or where. That part can then be addressed manually.

This would semi-automate at least some elements of bug-hunting and quality control. Even if you could only use the approach in a subset of kernel modules, due to the complexities of interactions, I see no reason why you couldn't use this to perform far more rigorous checks than things like the Stanford Checker or Klokwork are currently capable of.

## Re:halp! (2, Insightful)

## Anonymous Coward | more than 5 years ago | (#27248827)

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 of code in the Linux kernel.

Exactly what is an "arc through a module" supposed to mean, anyway, and how does knowing the existence of a "buggy arc" give you even the slightest idea of where it is?

## Re:halp! (2, Informative)

## snorb (109422) | more than 5 years ago | (#27247375)

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 (3, Interesting)

## bendytendril (1281160) | more than 5 years ago | (#27246615)

What he really needed is a threaded message board ala Slashdot.

## Re:Too bad he used a blog (2, Funny)

## morgan_greywolf (835522) | more than 5 years ago | (#27246689)

How about Subversion or GIT?

## Re:Too bad he used a blog (0)

## Anonymous Coward | more than 5 years ago | (#27255843)

## Re:Too bad he used a blog (1)

## Simetrical (1047518) | more than 5 years ago | (#27263603)

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:Too bad he used a blog (0)

## Anonymous Coward | more than 5 years ago | (#27247961)

Wordpress can nest comments like slashdot too. The option is there, just not active by default.

## Re:Too bad he used a blog (1)

## Sheafification (1205046) | more than 5 years ago | (#27250591)

## Re:Too bad he used a blog (1)

## Secret Rabbit (914973) | more than 5 years ago | (#27265449)

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.

## So who gets credit? (0)

## Anonymous Coward | more than 5 years ago | (#27246635)

Is the paper going to contain 50 pages of acknowledgements, including screen names?

## Hmm (0)

## Anonymous Coward | more than 5 years ago | (#27246667)

The open-collaboration Wikipedia makes no mention of this, therefore it didn't happen.

## Massive open collaboration in math (5, Funny)

## morgan_greywolf (835522) | more than 5 years ago | (#27246677)

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! (1)

## JoeDuncan (874519) | more than 5 years ago | (#27248135)

## Re:Oh come on! (0)

## Anonymous Coward | more than 5 years ago | (#27251119)

why?

## Re:Oh come on! (1)

## F34nor (321515) | more than 5 years ago | (#27252793)

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:Massive open collaboration in math (0)

## Anonymous Coward | more than 5 years ago | (#27253175)

What an idea! We could take it even further! How about we make a community of developers that would share code and improve upon it in a friendly collaborative environment? We could also develop our own software license that would support others in collaborating with us!

Nah, that would never work. People would never invest time in anything without profit.

## Re:Massive open collaboration in math (1)

## somersault (912633) | more than 5 years ago | (#27253685)

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 (4, Insightful)

## pimpimpim (811140) | more than 5 years ago | (#27246697)

## Re:List of authors (1)

## Barryke (772876) | more than 5 years ago | (#27248393)

Make it a regular expression.

## Re:List of authors (1)

## kramulous (977841) | more than 5 years ago | (#27249713)

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 (4, Informative)

## Sheafification (1205046) | more than 5 years ago | (#27250605)

## Re:List of authors (1)

## Secret Rabbit (914973) | more than 5 years ago | (#27265457)

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 (3, Funny)

## D Ninja (825055) | more than 5 years ago | (#27246721)

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?

## Re:Prior Art (0)

## Anonymous Coward | more than 5 years ago | (#27253987)

You're modded as funny (and rightfully so), but your comment is actually a perfect example of why school fails at properly preparing people for life, especially life as researchers and scientists.

In real life, collaboration is not only good; being able to collaborate efficiently is a very valuable skill. Schools, in their ignorant attempts to make you learn by heart a long laundry list of facts rather than teaching you how to THINK, declare it as a problem that needs to be stamped out and don't even realise how absurdly stupid this actually is.

## Surprise result (2, Funny)

## Hwatzu (89518) | more than 5 years ago | (#27246767)

It turns out that 2 + 2 actually = 5.

I know; I'm surprised, too. Well, I'm off to patch my calculator.

## Re:Surprise result (1)

## Asmor (775910) | more than 5 years ago | (#27247183)

For sufficiently large values of 2 [straightdope.com] . ;)

## Re:Surprise result (0)

## Anonymous Coward | more than 5 years ago | (#27247647)

## Why now? (2, Interesting)

## Anonymous Coward | more than 5 years ago | (#27246853)

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:Why now? (2, Insightful)

## Anonymous Coward | more than 5 years ago | (#27247869)

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:Why now? (1)

## Anonymous Coward | more than 5 years ago | (#27249005)

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 hand, don't have nearly enough background to contribute anything to this particular problem.

## It's about n-dimensional tic-tac-toe. (4, Informative)

## bcrowell (177657) | more than 5 years ago | (#27247077)

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:It's about n-dimensional tic-tac-toe. (0)

## Anonymous Coward | more than 5 years ago | (#27247423)

Yes, I believe you are correct sir, the proved it for some particular case, but believe they could generalize it.

Actually it was already proven, they were simply looking for an alternative (combinatorial) proof.

## Re:It's about n-dimensional tic-tac-toe. (2, Interesting)

## kramulous (977841) | more than 5 years ago | (#27247485)

If that is the interpretation, then where is the crossover point between lower dimensional and higher dimensional space where the draws stop?

## Re:It's about n-dimensional tic-tac-toe. (1)

## bcrowell (177657) | more than 5 years ago | (#27247695)

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 true, because it's possible for normal tic-tac-toe to end in a tie. It sounds like nobody knows how to prove the exact conditions on (H,c,n,delta) for which the theorem holds. For a given (c,n,delta), there may be some crossover point for H, but I don't think anybody knows what it is, except in certain special cases.

## Re:It's about n-dimensional tic-tac-toe. (2, Funny)

## psnyder (1326089) | more than 5 years ago | (#27247507)

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:It's about n-dimensional tic-tac-toe. (3, Informative)

## snorb (109422) | more than 5 years ago | (#27247873)

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.

## Massive? (3, Informative)

## Anonymous Coward | more than 5 years ago | (#27247317)

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:Massive? (1, Troll)

## retchdog (1319261) | more than 5 years ago | (#27248129)

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:Massive? (1)

## Duncan3 (10537) | more than 5 years ago | (#27249231)

To be fair, this is much more then "somewhat remarkable" for any academic discipline.

## Re:Massive? (1)

## Secret Rabbit (914973) | more than 5 years ago | (#27265469)

This is somewhat remarkable.LOL. This happens all the time. LOL.

## Re:Massive? (1)

## retchdog (1319261) | more than 5 years ago | (#27275147)

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:Massive? (1)

## Secret Rabbit (914973) | more than 5 years ago | (#27282801)

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 longer term. Because, I really don't. It's human nature. Once people get used to it, it'll fall into the same time frame that the current research goes at.

In other words, they applied how they talk to each other during black-board meetings to an email/forum/etc postings in the public. So, the medium may have changed for these "off the cuff" conversations, but nothing was actually new.

## Re:Massive? (1)

## retchdog (1319261) | more than 5 years ago | (#27335023)

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 (1)

## epine (68316) | more than 5 years ago | (#27251089)

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 "peer review" and a working definition of "expert" as as someone who has perfected the art of taking credit. I also number myself among the lunatic fringe more concerned with the flow of ideas than the flow of dollars.

Maybe I should update Truman for the 21'st century:

That's another good working definition of expert: a person excessively encumbered by formal roles and obligations.

## Re:Fielder's choice (1)

## Secret Rabbit (914973) | more than 5 years ago | (#27265475)

You have a very interesting definition of the word, "confirmed." Well, at least you can admit to being on the lunatic fringe.

## Obligatory (1)

## rossdee (243626) | more than 5 years ago | (#27250299)

The aswer they came up with was 42

## Massive collaboration (0)

## Anonymous Coward | more than 5 years ago | (#27251411)

I guess any number of mathematicians greater than 2 would be considered a "massive" collaboration.

Looking at the original thread I see that there are approximately 5-10 unique posters. I wonder what we call it when 100 mathematicians get together?

## Re:Massive collaboration (1)

## kramulous (977841) | more than 5 years ago | (#27252299)

Chaos

## Re:Massive collaboration (0)

## Anonymous Coward | more than 5 years ago | (#27252403)

I wonder what we call it when 100 mathematicians get together?

All of them.

## This was NOT massive!!! (1)

## Secret Rabbit (914973) | more than 5 years ago | (#27252621)

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

## All things are relative... (0)

## Anonymous Coward | more than 5 years ago | (#27253109)

In the mathematical study on n dimensional tic-tac-toe, a handful is pretty massive.

## Re:All things are relative... (1)

## Secret Rabbit (914973) | more than 5 years ago | (#27263091)

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 slide due to relatives is _not_ even remotely acceptable.