Possible future Polymath projects

I am still very busy at the moment and do not expect to be able to get down to any serious polymathematics for a few weeks, at least. And in any case, there are two Polymath projects going on at the moment, so I am not in a huge hurry to start another. (The projects are Gil Kalai’s on the polynomial Hirsch conjecture and Terence Tao’s on finding primes deterministically.)

Having said that, a common complaint about the first Polymath project was that it got started so rapidly that it was very easy to get left behind. So for my next project I would like to do two things. First, I want to get a sense of which, out of many potential projects I have in mind, would appeal to enough other people for there to be a good chance of finding a core of people ready to put in an effort similar to the effort that some people put into DHJ. (A similar core of regular contributors has developed for Terry’s polymath4: I wonder if this will happen for all projects that get off the ground.) And secondly, having chosen a new project, I want to write several introductory posts to give people a chance to get up to speed before the project properly starts. The way things are looking at the moment, I think it’s unlikely that I’ll start a project before November, but the preliminary posts might come out earlier.

In this post, I will say very briefly what some of these possible projects are, and will also report on a conversation I had recently with Jordan Ellenberg, during which he told me some thoughts about Polymath that I found extremely interesting. In fact, let me do that first.

Jordan is interested in the question of what it is that motivates people to check websites regularly, and his answer is that the websites need to be constantly changing (like a blog that gets lots of posts and comments) rather than static (like a wiki or a home page). Of course, this is not a new observation, and of course Jordan wasn’t claiming that it was, but it does have some consequences for Polymath projects. For instance, Jordan’s view was that, however regularly a Polymath wiki is updated, people are far less likely to spend time reading it carefully than they are to check a Polymath blog, even if they are interested in finding out about the problem being tackled. The reason is that we all have 101 bits of mathematics that it would be good to learn about, and as soon as reading the wiki begins to feel like hard work, we won’t really have a strong reason for doing that piece of hard work rather than any other. This doesn’t invalidate the wiki, since it is very useful when making blog comments to be able to refer to the wiki for basic definitions and results rather than having to explain them every time, and it is also useful to put arguments on the wiki once they start to become more precise and technical. But I think I agree with Jordan that it is unrealistic to suppose that if there are good explanations on the wiki, then that will enable people to get up to speed and join a Polymath project at a late stage.

I myself would draw another conclusion, which is partly based on my experience of following polymath4 and making occasional casual contributions. On the Polymath blog, a very high level of threading is allowed, with the result that the order of comments is very different from their chronological order. This makes it substantially harder to check what has been added recently than it would be if there were no threading. It’s not impossible, since one has a list of recent comments, but it does reduce the feeling of a polymathematical thought process unfolding over time. I know that there is disagreement about this, but I am going back to the view that there should be no threading at all, though I might be ready to compromise and have threading down to depth 1, with the understanding that it should be used for brief local replies only.

There was plenty more to our conversation, but the take-home message was that we should think very carefully about the psychology of what one might call website addiction, that quality that some websites have that cause one to check them obsessively, and should try to harness it as efficiently as possible. It could be that it is this that really distinguishes a Polymath collaboration from a conventional collaboration, where it is all too easy to be lazy and take ages. Certainly, I experienced something of this addiction during polymath1 (as my wife will testify).

To state the requirement precisely, what a successful Polymath project needs is to be appealing in a fairly addictive way to enough people for the benefits of multiple collaboration to be truly felt. From the experience of Polymath1, I think it could be enough to have a nucleus of four or five people who are enthused by the project, keep up with what is going on, and maintain the momentum by making regular contributions.

I also had an interesting correspondence with Michael Nielsen in which I suggested that one reason for Polymath1 not fizzling out might have been that I started with a fairly detailed plan of attack, even though the eventual proof turned out to be quite different. He said that that was certainly a factor in the success of Linux: Linus Torvalds didn’t start by saying, “Hey guys, wouldn’t it be nice to develop a free operating system collaboratively,” but rather he got things started with a rudimentary system. And apparently there are many other examples like that. However, he also noted that Terry Tao’s mini-polymath was remarkably successful despite almost no initial input from Terry (since he already knew a solution). Despite this example, I think it is probably an advantage, even if not a necessity, for a project to start with a clear plan.

What then are the possible projects that I have in mind? I have two 20-page documents describing them, but here I will just give a quick digest of some of them, in the hope of narrowing down the possibilities (even though I think all of them have the potential to be good projects, and I would probably return to the ones that were weeded out) and getting some sort of feedback.

1. Littlewood’s conjecture and related problems.

Littlewood’s conjecture is a major open problem, about which there are some highly non-trivial results. It states that if and are any two real numbers, and , then there exists a positive integer such that . Here, denotes the difference between and the integer closest to . The usual pigeonhole argument implies that for every there exists such that , so the conjecture is asking for just a tiny improvement to this trivial bound if instead of looking at one real number we look at two simultaneously. For the conjecture to be false, there would have to be a pair such that whenever threatened to get close to an integer, was safely far away, and vice versa.

Polymath seems suited to problems that can be tackled in an elementary way, which, given the non-elementary nature of the progress that has been made so far on Littlewood’s conjecture (the highlight of which is a proof by Einsiedler, Katok and Lindenstrauss that the Hausdorff dimension of the set of counterexamples to the conjecture is zero), might make it seem as though it was an unsuitable problem. Briefly, my reasons for nevertheless wanting to tackle it are (i) I have formulated a number of related problems that seem easier, and (ii) I have ideas for how to tackle the problem in an elementary way, and I believe that we could learn a lot from trying to get them to work, even if we failed.

An advantage of this project is that I already have quite a bit of material that could quickly be turned into initial posts, plenty of ideas to explore, etc. The fact that the problem itself is notoriously hard is not, in my view, a reason for not attempting it, since there are lesser goals, such as thinking about the related problems and improving our understanding of the main problem, that it would still be very good to be able to attain.

2. A DHJ-related project.

I will say very little about this project, except that its main advantage (which not everybody would consider an advantage) is that it is sufficiently closely related to DHJ that some of the expertise built up during that project could well be useful to this one. And it is an extremely interesting problem, so interesting that I am reluctant to put it in the public domain unless there is a real chance that it will be chosen as a polymath project. (Sorry, that’s a bit of my traditional possessive monomathic personality coming out there.) On the negative side, I don’t have much in the way of preliminary attacks on the problem, though this would I think be compensated for by the closeness to DHJ. (I should stress, however, that it is different enough from DHJ that a solution would be a serious mathematical advance.)

3. Four Erdös-style combinatorial problems.

Apologies for the non-Hungarian umlaut—I don’t know how to do Hungarian ones in WordPress. I am going to lump the next four projects together, since they are all beautiful problems of an extremal-combinatorics flavour. I will do little more than state the problems. I do not have plans of attack for these, though I have a few small ideas and preliminary observations about 3a that could provide some kind of starting point. However, for each problem I have a hunch that Polymath could really get its teeth into it.

3a. Erdös’s discrepancy problem.

Let be a sequence of s and let be a positive integer. Must there exist positive integers and such that ?

This is such a weak thing to ask, and seems so likely to be true, that I have the feeling that the reason the problem is still open is that people have not pushed quite hard enough. So perhaps a multipush is what is required. Having said that, I know various observations that show that there probably isn’t a truly easy solution to the problem. (For instance, it is possible to construct sequences where has to be exponentially large in terms of , so many styles of argument that would tend to give quadratic bounds are ruled out. I could expand on this in a future post.)

3b. The Erdös-Hajnal conjecture.

This is a gorgeous problem in Ramsey theory. As is well-known, the Ramsey number is exponential in . However, the graphs that demonstrate this are random graphs, and therefore they contain induced copies of all small graphs. By how much does the bound improve if one disallows this? More precisely, let be a positive integer and let be a graph. Erdös and Hajnal conjecture that there is a constant such that if is any graph with at least vertices that does not contain any induced copy of , then either or contains a clique of size .

The usual bounds for off-diagonal Ramsey numbers prove the result when is a clique, and it is also known for certain classes of graphs. The simplest open case is where is a pentagon. In other words, if has vertices and does not contain five vertices such that each is joined to but not to (mod 5), then it is not known whether the largest clique in or must have size at least .

3c. Frankl’s union-closed conjecture.

This is a notorious question, and possibly the least likely to yield to a Polymath approach (it feels as though there might be a burst of ideas, none of which would work, followed by disillusionment, or else, if we were very lucky, a single bright idea from one person that essentially solved the problem, but I could be wrong). Let be a collection of sets that is closed under taking unions. Must there be an element that is contained in at least half the sets? (The extremal case is if consists of all subsets of a -element set, in which case there are sets and no element is contained in more than of them.)

3d. The delta-systems problem.

This question is due to Erdös and Rado. A delta system is a collection of sets such that all the sets (with ) are equal. Equivalently, there exists some set such that for every , and the sets are disjoint.

Delta systems appear quite often in extremal combinatorics, and it would be good to know how many sets of size you need before you are guaranteed to find a delta system of size . However, this is another notorious problem. Even when , it is wide open, and Erdös offered 1000 dollars for a solution to the following problem: does there exist a constant such that for every and every system of at least sets of size , there must exist three of them that form a delta system? (The best known upper bound is more like .)

4. Non-mathematical projects.

There are many fascinating questions that are not strictly speaking mathematics but that nevertheless appeal to many people who are mathematically inclined. It occurs to me that some of these could be ideal for Polymath, since one of the difficulties of Polymath — the need to communicate complicated mathematical ideas — is lessened. I will give two examples of the kind of thing I have in mind. I don’t expect either of these to be the next Polymath project, but I might be interested in tackling one or other of them in the future.

4a. Developing a non-boring chess-playing program.

I have great respect for the achievements of Deep Blue and similar programs, but I cannot avoid being disappointed by the heavy use that such programs make of brute-force searches. It feels to me as though the real problem — how do good chess players do what they do — remains unanswered. So I am interested in the following question: how good a chess-playing program is possible if the amount of memory space allowed is very restricted, and the amount of calculation is also limited?

What might a Polymath project devoted to this question be like? Well, it could start by trying to frame the question in a more abstract way. One would like to find a method of programming that applied to all games of a certain type (things like Othello, Go, etc.) and not just chess. The sort of method that I find exciting is an evolutionary strategy: one just sets the computer playing against itself, or perhaps against itself and against humans, and tries to set things up so that there is an evolutionary pressure that selects for good tactics. The major problem there is to come up with a notion of game-playing program that splits up into smaller bits (which one can think of as “genes”) that can be modified without just wrecking the whole program. And one wants to do that without imposing serious limitations on what the program can end up looking like. These are formidable challenges, and issues that many people have thought about. But I’m not sure that pure mathematicians have thought about them all that much, and perhaps some interesting new ideas could come out of a Polymath project on the subject.

4b. The origin of life.

This is even more absurdly ambitious than 4a, but why not? One of the major open problems in science is to give a plausible explanation of how life started: it seems to be much easier to explain how complex life forms evolved from simple ones than it is to explain how the simple ones evolved (if that is the right word) from nothing.

I think there is the potential for mathematicians to shed light on this problem, by coming up with a mathematical model and proving (not necessarily rigorously — perhaps one would be satisfied with convincing heuristic arguments and computer simulations) that it had a tendency to lead to extremely complex behaviour.

What about Conway’s game of Life, one might ask? Well, that is clearly a huge step in the direction I am talking about. But it doesn’t quite do what I said in the previous paragraph: what it does is demonstrate that some initial configurations lead, under some very simple rules, to complex behaviour. What I would find more convincing would be a somewhat randomized dynamic model, such as the kinds of models one sees in statistical physics, that not only can get very complex, but does so with some positive probability (which one could quite easily convert into a probability very close to 1). I recently attended a fascinating talk by Stanislav Smirnov in which he talked about sandpile models. These are models of the process where one drops sand on a pile, which grows but also gives rise to avalanches of various sizes. Apparently, statistical physicists find these models exciting because they naturally seem to give rise to complicated fractal patterns, whereas most models seem to be stable in the ordered regime or the completely chaotic regime and not at the boundary between them.

So a more precise question is this: can one devise some simple model that people could run on their computers that would start from virtually nothing and almost always lead to an interesting artificial eco-system? Such a model would provide powerful support for the hypothesis that life is a high-probability event rather than an extraordinary miracle that defies scientific explanation.

Of course, there must already have been a great deal of work on this question, and there are many variants on the game of Life. So a preliminary task would be to find out about that in order to see what would count as an important advance. (I suppose it is even worth thinking about whether a suitable choice of random starting position for the game of Life, with perhaps a very slight randomization of the game itself, would do the job.)

The reason I think this might make a good Polymath project is that whereas one person’s wild speculation can often be just that — wild speculation — if a large number of people made speculations and criticized and refined other people’s speculations, the result could perhaps be much more interesting.

5. A tentative approach to complexity lower bounds.

This has emerged only very recently as a suitable project. One of the features of the P versus NP problem that is rather intimidating is that theoretical computer scientists have proved a number of rigorous results that say “No proof that P does not equal NP could look like this.” And it seems to be hard to come up with a sketch of an argument that doesn’t “look like this” (though there is at least one serious proposal, due to Ketan Mulmuley).

Recently, however, I thought of an approach that could conceivably avoid some of these “barriers in computational complexity”. At the moment I’m almost sure (but not quite certain) that it wouldn’t be able to prove that P does not equal NP, but I haven’t yet managed to rule out its being able to solve another major problem in the area: to find a function in NP that has superpolynomial formula size. This is still a very long shot of course, but the nature of the subject is such that even reaching a good understanding of why an approach doesn’t work is cause for celebration, so I think the ideas are worth investigating. And I think that reaching this kind of good understanding would be quicker and more enjoyable if done polymathematically. I should say that I’ve tried reasonably hard to demolish the approach myself, but each time I think I’ve succeeded I find some desperate way of rescuing it. However, at least one of these demolition attempts does make it look highly likely that a certain measure of complexity that I have looked at can be large for polynomially computable functions. I shall continue to attack the approach, so it may be that by the time I would have been ready to start the project it won’t exist any more.

[UPDATE 19/9/09: I have now had a further realization that makes me extremely pessimistic about the idea. I will continue to think about it, but if your preference is/was for 5, it would still be good to think carefully about your second choice.]

There is a tiny tiny chance that the approach actually works, and a further minuscule chance that, despite the strong evidence to the contrary, it could then lead to a proof that PNP. This conjunction of two miracles is so unlikely that it is scarcely worth bringing up a difficult issue that would arise, but it is an amusing issue that will have occurred to almost anyone reading this, so let me do so. That is the question of what would happen to the Clay million dollars if one of their problems was solved polymathematically. I can think of a few possible answers. One might be simply to declare in advance that if that happened then Polymath would give the money to charity, or come up with ten 100,000-dollar problems, or in some other way not try to distribute the money to the individual participants. But then there might be a strong temptation for people to break off and work individually. Another answer might be just to rely on the Clay Foundation to solve the problem of apportioning credit — in their small print they already have something about possibly sharing prizes if the ideas that go into a solution are spread amongst different papers by different authors.

I don’t know if either of these solutions would work, but I do think that it would be a terrible pity if the existence of the Clay prize provided a disincentive to work on their problems in a potentially productive way.

From the point of view of suitability for Polymath, I think this project is a good one, since, as with the Littlewood problem, I have some detailed posts already written, in the form of a five-part dialogue between three mathematicians, one of whom specializes in proposing ideas, one in criticizing them, and the third in asking for fuller explantions from time to time. There is a good chance that complexity experts will be able to shoot it down almost immediately (indeed, the one thing that bothers me about this as a project is that it could be slightly embarrassing — it’s somewhat embarrassing even to admit to thinking about it): if so, nothing much is lost and we can move straight on to another project. But if the approach survives the initial scrutiny of the TCS crowd, then one thing it has going for it is that it is of a kind that would appeal to additive combinatorialists. Since there are already many people interested in both theoretical computer science and additive combinatorics, there is an excellent pool of potential participants: perhaps one or two of them could become addicted in the Ellenberg sense.

I have a disclaimer similar to the one I had at the start of DHJ: the official aim of this project would be to see whether one particular idea for proving complexity lower bounds has anything going for it. Of course, it would be great if the answer was provably yes, but there are many lesser outcomes that would still be interesting. (I would even be interested, if disappointed, to be told that the approach has already been tried.) I would also like to have my argument that it cannot prove that P=NP made rigorous: it seems to be quite an interesting and purely mathematical problem to do that.

Conclusion.

A few weeks ago, the Littlewood project was the one that appealed to me most. Now I am moving towards the one on complexity lower bounds (despite simultaneously feeling a bit uneasy about even mentioning it, and despite the fair chance that it’s based on an idea that will rapidly be seen to get nowhere). But all of them appeal to me quite a bit, or I wouldn’t have suggested them. I think the two non-mathematical projects are perhaps best left alone for the time being — I just mention them to raise the possibility that Polymath could be used for broader projects that are not completely mathematical. Amongst the projects in 2 and 3, I think my not terribly strong order of preference is 2 and 3a (equal first), followed by 3d, 3b, 3c. Funnily enough, or perhaps not so funnily, my order of preference is basically the same as the order of how many preliminary thoughts I have about the problems — i.e., on how well they do by the clarity-of-initial-plan criterion.

So now I’d like to get some feedback. I’m particularly interested in getting a sense not just of which projects people would like to see tackled, but which projects people feel they could make a serious contribution to and would be prepared to devote plenty of time to. I realize I haven’t given enough information for it to be easy to judge, but I hope I’ve at least said enough for people to decide their approximate level of enthusiasm.