DHJ — possible proof strategies

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

DHJ — quasirandomness and obstructions to uniformity

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.

Quasirandomness.

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.

DHJ — the triangle-removal approach

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 .) 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 contains three points of the form , and . Such configurations are sometimes called corners, and we have been referring to the theorem that a dense subset of 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.

Quick question

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?

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.

A combinatorial approach to density Hales-Jewett

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.

Questions of procedure

As a result of comments on my post Is Massively Collaborative Mathematics Possible? and also as a result of thinking about the proposal a little further I have a few extra remarks to make, and a slight redrafting of the procedural rules. (As I said before, these rules are just my first guess about what would work, and if a consensus emerges that they should change then they can of course be changed.)

Background to a Polymath project

This post contains brief descriptions of some mathematics that one would need to know in order to have a realistic chance of contributing to the collaborative research project I shall suggest in the next post. If you are familiar with the Hales-Jewett theorem, Szemerédi’s regularity lemma, the triangle-removal lemma, and the proof from the triangle-removal lemma that a dense subset of contains a corner, then you do not need to read it.

Is massively collaborative mathematics possible?

Of course, one might say, there are certain kinds of problems that lend themselves to huge collaborations. One has only to think of the proof of the classification of finite simple groups, or of a rather different kind of example such as a search for a new largest prime carried out during the downtime of thousands of PCs around the world. But my question is a different one. What about the solving of a problem that does not naturally split up into a vast number of subtasks? Are such problems best tackled by people for some that belongs to the set ? (Examples of famous papers with four authors do not count as an interesting answer to this question.)

It seems to me that, at least in theory, a different model could work: different, that is, from the usual model of people working in isolation or collaborating with one or two others. Suppose one had a forum (in the non-technical sense, but quite possibly in the technical sense as well) for the online discussion of a particular problem. The idea would be that anybody who had anything whatsoever to say about the problem could chip in. And the ethos of the forum — in whatever form it took — would be that comments would mostly be kept short. In other words, what you would not tend to do, at least if you wanted to keep within the spirit of things, is spend a month thinking hard about the problem and then come back and write ten pages about it. Rather, you would contribute ideas even if they were undeveloped and/or likely to be wrong.