Slashdot Mirror

← Back to Stories (view on slashdot.org)

Massive Open Collaboration In Math Declared a Success

Posted by timothy on from the you-count-the-feet-we'll-count-the-toes dept.

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

45 of 60 comments (clear)

  1. halp! by Anonymous Coward · · 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...

    1. Re:halp! by Anonymous Coward · · 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

    2. Re:halp! by jd · · Score: 1, 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 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 arc .

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

      --
      It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
    3. Re:halp! by snorb · · 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/

    4. Re:halp! by Anonymous Coward · · 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 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?

    5. Re:halp! by teacher_dude · · Score: 1

      Glad you finished with "IANAM", cause the way I look at it, if **I** have too much of one thing (balls) then my pants would be tighter.

      --
      What if the hokey-pokey is what it's all about?
    6. Re:halp! by OwnedByTwoCats · · Score: 1

      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

  2. Too bad he used a blog by bendytendril · · Score: 3, Interesting

    I read TFA (I didn't understand it, but at least I read it). The entire discussion was a typical linear blog where they had keep numbering items and referring back to them (i.e. "regarding item #32 I think....")

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

    --
    sig: pv qid
    1. Re:Too bad he used a blog by morgan_greywolf · · Score: 2, Funny

      How about Subversion or GIT?

      --
      My blog
    2. Re:Too bad he used a blog by Sheafification · · Score: 1

      The option to thread comments on Wordpress was only introduced after the project had begun. You can find a post by Gowers that talks about this very issue on his blog.

    3. Re:Too bad he used a blog by Simetrical · · 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?

      --
      MediaWiki developer, Total War Center sysadmin
    4. Re:Too bad he used a blog by Secret+Rabbit · · Score: 1

      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.

  3. Massive open collaboration in math by morgan_greywolf · · 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!

    --
    My blog
    1. Re:Massive open collaboration in math by somersault · · Score: 1

      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!

      --
      which is totally what she said
  4. List of authors by pimpimpim · · Score: 4, Insightful

    I am all in favor of this, as it allows people outside scientific communities to join in with a low barrier (that is, if you happen to be a math wizard). But is, and if so, how is he going to ensure that the right people will be mentioned as co-authors in the paper?

    --
    molmod.com - computing tips from a molecular modeling
    1. Re:List of authors by Barryke · · Score: 1

      Make it a regular expression.

      --
      Hivemind harvest in progress..
    2. Re:List of authors by kramulous · · Score: 1

      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.

      --
      .
    3. Re:List of authors by Sheafification · · Score: 4, Informative

      Gowers mentioned this in one of his early posts about the project. Publishing will probably be under some sort of pseudonym (think Bourbaki), with a link given to the blog entries. If you're curious about how much someone contributed, you can go check it out exactly.

    4. Re:List of authors by Secret+Rabbit · · Score: 1

      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.

  5. Prior Art by D+Ninja · · Score: 3, 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?

  6. Surprise result by Hwatzu · · 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.

    1. Re:Surprise result by Asmor · · Score: 1

      For sufficiently large values of 2. ;)

  7. Why now? by Anonymous Coward · · 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?

    1. Re:Why now? by Anonymous Coward · · 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.

    2. Re:Why now? by Anonymous Coward · · Score: 1

      To quote one of Gowers's original posts 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.

  8. It's about n-dimensional tic-tac-toe. by bcrowell · · Score: 4, 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. 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.

    --
    Find free books.
    1. Re:It's about n-dimensional tic-tac-toe. by kramulous · · Score: 2, Interesting

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

      --
      .
    2. Re:It's about n-dimensional tic-tac-toe. by psnyder · · Score: 2, Funny

      Now they can move onto more important things, like n-dimensional chess.

      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.

    3. Re:It's about n-dimensional tic-tac-toe. by bcrowell · · Score: 1

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

      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.

      --
      Find free books.
    4. Re:It's about n-dimensional tic-tac-toe. by snorb · · 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.

  9. Massive? by Anonymous Coward · · 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?

    1. Re:Massive? by retchdog · · Score: 1, 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.

      --
      "They were pure niggers." – Noam Chomsky
    2. Re:Massive? by Duncan3 · · Score: 1

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

      --
      - Adam L. Beberg - The Cosm Project - http://www.mithral.com/
    3. Re:Massive? by Secret+Rabbit · · Score: 1

      This is somewhat remarkable.

      LOL. This happens all the time. LOL.

    4. Re:Massive? by retchdog · · Score: 1

      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?

      --
      "They were pure niggers." – Noam Chomsky
    5. Re:Massive? by Secret+Rabbit · · Score: 1

      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.

    6. Re:Massive? by retchdog · · Score: 1

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

      --
      "They were pure niggers." – Noam Chomsky
  10. Oh come on! by JoeDuncan · · Score: 1

    Be serious! That would *never* work!

    1. Re:Oh come on! by F34nor · · Score: 1

      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)

  11. Obligatory by rossdee · · Score: 1

    The aswer they came up with was 42

  12. Fielder's choice by epine · · Score: 1

    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?

    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:

    It is amazing what you can accomplish if you aren't trying to pay a mortgage. —

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

    1. Re:Fielder's choice by Secret+Rabbit · · Score: 1

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

  13. Re:Massive collaboration by kramulous · · Score: 1

    Chaos

    --
    .
  14. This was NOT massive!!! by Secret+Rabbit · · Score: 1

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

  15. Re:All things are relative... by Secret+Rabbit · · Score: 1

    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.