Archive for February, 2009

Brief review of polymath1

February 23, 2009

I don’t have much to say mathematically, or rather I do but now that there is a wiki associated with polymath1, that seems to be the obvious place to summarize the mathematical understanding that arises in the comments on the various blog posts here and over on Terence Tao’s blog (see blogroll). The reason I am writing a new post now is simply that the 500s thread is about to run out.

So let me quickly make a few comments on how things seem to be going. (At some point in the future I will do so at much greater length.) Not surprisingly, it seems that we have reached a stage that is noticeably different from how things were right at the beginning. Certain ideas that emerged then have become digested by all the participants and have turned into something like background knowledge. Meanwhile, the discussion itself has become somewhat fragmented, in the sense that various people, or smaller groups of people, are pursuing different approaches and commenting only briefly if at all on other people’s approaches. In other words, at the moment the advantage of collaboration is that it is allowing us to do things in parallel, and efficiently because people are likely to be better at thinking about the aspects of the problem that particularly appeal to them. (more…)

To thread or not to thread

February 21, 2009

The 500s thread of polymath1 is going to run out soon. Before I start what I think will be the 800s thread, I would like to ask whether the general view is that threaded comments would be a good idea for this, because I have recently learned from Luca Trevisan that WordPress now allows them. At the beginning of the experiment there appeared to be a clear view that threaded comments would be highly desirable. Now that things have quietened down somewhat, I find it less obvious. The simple numbering system has served us well (though one could have a numbering system like 8.13.2 for the second comment on the 13th comment of what would have been the 800s thread) and with a more tree-like structure one would lose the easily viewed chronological order of the comments. But perhaps a very limited amount of threading would be helpful, e.g. for quick comments such as “There’s an easy counterexample to that: just take …” or “I have now seen how to prove this: more details can be found in comment 8.27 below.” So the choices are to go the whole hog and allow many levels of nested comments, to leave things as they are, or to allow limited threading (up to a maximum depth of 1, say, counting a comment itself as level 0) with a general agreement that it will be used sparingly. (The last option sounds potentially good, but would depend on people adhering to this agreement, and I can’t tell at this stage whether they would.)

Must an “explicitly defined” Banach space contain c_0 or ell_p?

February 17, 2009

I do not know how to make this question fully precise (except in ways that make the answer uninteresting), but I have wondered about it for a long time, and it has arisen again in the discussion following my recent post on the Banach space constructed by Spiros Argyros and Richard Haydon. Here I would like to say enough to enable others to think about it. One could think of this post as the beginning of polymath2, but I expect polymath2 to be somewhat different from polymath1 for various reasons: it will involve different people, it may well go much more slowly than polymath1 (I would like to think of it quietly chugging away in the background), and I am not comfortable with some of the mathematics that will be essential to formulating a good conjecture. On a more practical level, I think that having a wiki for polymath 1 (see my blogroll for a link) has worked very well as a way of organizing our collective thoughts on the density Hales-Jewett theorem, and if polymath2 gets off the ground then I would expect an accompanying wiki to be part of it from the very beginning. (more…)

DHJ — possible proof strategies

February 13, 2009

I will give only a rather brief summary here, together with links to some comments that expand on what I say.

If we take our lead from known proofs of Roth’s theorem and the corners theorem, then we can discern several possible approaches (each one attempting to imitate one of these known proofs). (more…)

DHJ — quasirandomness and obstructions to uniformity

February 8, 2009

This post is one of three threads that began in the comments after the post entitled A combinatorial approach to density Hales-Jewett. The other two are Upper and lower bounds for the density Hales-Jewett problem , hosted by Terence Tao on his blog, and DHJ — the triangle-removal approach, which is on this blog. These three threads are exploring different facets of the problem, though there are likely to be some relationships between them.


Many proofs of combinatorial density theorems rely in one way or another on an appropriate notion of quasirandomness. The idea is that, as we do, you have a dense subset of some structure and you want to prove that it must contain a substructure of a certain kind. You observe that a random subset of the given density will contain many substructures of that kind (with extremely high probability), and you then ask, “What properties do random sets have that cause them to contain all these substructures?” More formally, you look for some deterministic property of subsets of your structure that is sufficient to guarantee that a dense subset contains roughly the same number of substructures as a random subset of the same density. (more…)

A remarkable recent result in Banach space theory

February 7, 2009

This post is about a result that has recently been proved in my old stamping ground of the theory of Banach spaces. When I set up this blog, I wasn’t expecting to write a post about Banach spaces, but the result I want to talk about is one of those rare and delightful events when a problem that you thought you might well never live to see solved is solved. And since Banach space theory is one of the less fashionable areas of mathematics, the result may well not get the publicity it deserves: this is an attempt to counteract that to a small extent. (more…)

DHJ — the triangle-removal approach

February 6, 2009

The post, A combinatorial approach to density Hales-Jewett, is about one specific idea for coming up with a new proof for the density Hales-Jewett theorem in the case of an alphabet of size 3. (That is, one is looking for a combinatorial line in a dense subset of \null [3]^n.) In brief, the idea is to imitate a well-known proof that uses the so-called triangle-removal lemma to prove that a dense subset of \null [n]^2 contains three points of the form (x,y), (x,y+d) and (x+d,y). Such configurations are sometimes called corners, and we have been referring to the theorem that a dense subset of \null [n]^2 contains a corner as the corners theorem.

The purpose of this post is to summarize those parts of the ensuing discussion that are most directly related to this initial proposal. Two other posts, one hosted by Terence Tao on his blog, and the other here, take up alternative approaches that emerged during the discussion. (Terry’s one is about more combinatorial approaches, and the one here will be about obstructions to uniformity and density-increment strategies.) I would be very happy to add to this summary if anyone thinks there are important omissions (which there could well be — I have written it fast and from my own perspective). If you think there are, then either comment about it or send me an email. (more…)

Quick question

February 4, 2009

The discussion about the density Hales-Jewett theorem is now getting quite long. What do you think we should do about it?

We could continue with the discussion just as it is, or we could summarize it and start again, or we could summarize each thread and continue with lots of separate discussions, one for each thread. What do you think would be best? I don’t promise to do what the majority says, but I will be interested to know what the majority opinion is.

Update: I have gone with the majority, but the vote was close, so as a small compromise the discussion is not divided into “lots of separate discussions” but only three. I hope this will make the discussion easier to follow without making it too fragmented. Technically the polls have not closed: there is still a chance to register a vote to show your approval or disapproval of this decision. Thanks to all those who have already voted: maybe the wisdom of crowds could be incorporated into mathematical research somehow …

Why this particular problem?

February 1, 2009

Let me briefly try to defend my choice of problem. I wanted to choose a genuine research problem in my own area of mathematics, rather than something with a completely elementary statement or, say, a recreational problem, just to show that I mean this as a serious attempt to do real mathematics and not just an amusing way of looking at things I don’t really care about. This means that 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 Szemerédi’s regularity lemma is essential. So I’m not expecting a collaboration between thousands of people, but I can think of far more than three people who are suitably qualified in the above way. (more…)

A combinatorial approach to density Hales-Jewett

February 1, 2009

Here then is the project that I hope it might be possible to carry out by means of a large collaboration in which no single person has to work all that hard (except perhaps when it comes to writing up). Let me begin by repeating a number of qualifications, just so that it is clear what the aim is. (more…)