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.

**The Hales-Jewett theorem.**

The Hales-Jewett theorem is one of the best-known results in Ramsey theory. To state it, we need a couple of definitions. Let us write for the set . We shall be looking at colourings of the set which consists of all sequences , where each is an integer between and .

As with most Ramsey theorems, the idea is now to find a substructure with all elements of the same colour. In this case, the substructure is an object known as a *combinatorial line*. An example will quickly demonstrate what a combinatorial line is. Let and let . Then the following three points form a combinatorial line: To see more clearly what is going on here, let us use the notation . The three earlier points are obtained by substituting , then , and then . In general, you form a combinatorial line by fixing some of the coordinates and letting the others be equal and vary from to .

The Hales-Jewett theorem asserts that for every and every there exists such that if the elements of are coloured with colours, then there is a combinatorial line with all its points of the same colour.

**The Furstenberg-Katznelson theorem.**

The proof of the Hales-Jewett theorem need not concern us here. What we shall be interested in is the *density version* of the statement, which is the following. For every and every there exists such that every subset of of size at least contains a combinatorial line. This is a famous theorem of Furstenberg and Katznelson, who proved it using ergodic theory. As yet, the only known proofs of this theorem either use ergodic theory or are heavily inspired by it, so it would be very nice to have a purely combinatorial proof.

The Hales-Jewett theorem implies van der Waerden’s theorem, and the Furstenberg-Katznelson theorem implies Szemerédi’s theorem, so a new proof of any kind is not likely to be easy to come by. However, Szemerédi’s theorem for progressions of length 3 (due to Roth) is quite a bit easier than the general case, so there ought to be a better chance of finding a combinatorial proof of the Furstenberg-Katznelson theorem at least in the case . The project I’m proposing is to develop an approach to this case of the problem: the approach will be explained in the next post. (If you have an idea about how to find a proof of this case, you should save it up for comments on that post. I’m not expecting many comments on this post, but if you do have them then they should concern the results I briefly describe here, or my presentation of them.)

**Szemerédi’s regularity lemma.**

The second piece of background information needed is Szemerédi’s regularity lemma. This is a fundamental result in graph theory and will play an important role for us. I will give the statement only, even though the project may depend on thinking about, and trying to modify, its proof. Anybody who does not know the proof already is referred to section 7 of this paper, and also to section 1 and the beginnings of sections 2 and 3 (but you can ignore everything about hypergraphs).

In order to state the lemma we shall need some preliminary definitions. Let be a bipartite graph with vertex sets and . Let be a subset of and let be a subset of . The *density* of the pair is defined to be the number of such that is an edge of , divided by . The pair is defined to be -*regular* if whenever and are subsets of and with and . What is useful about -regular pairs is that the induced subgraph of corresponding to such a pair behaves rather like a typical random bipartite graph of the same density (at least when is small).

The statement of the lemma, in the version we shall use, is this. For every there exists such that for every graph with vertex set there is a partition with and with the sets differing in size by at most 1, such that all but at most of the pairs are -regular.

As most people think about this lemma: every graph can be partitioned into a bounded number of pieces, almost all of which behave like random bipartite graphs.

**The triangle-removal lemma.**

Now let me sketch how Szemerédi’s regularity lemma is used to prove a result that is slightly misleadingly called the *triangle-removal lemma. *This states that for every there exists such that if is any graph with vertices and at most triangles, then it is possible to remove at most edges from and end up with no triangles. To prove it, one first applies the regularity lemma to . Let be a fairly small number (that depends in a reasonably simple way on ) and let the partition of the vertex set given by the regularity lemma be . Then remove all edges from all pairs that either fail to be -regular or fail to have density at least . If has been chosen appropriately, the number of edges removed is at most Suppose now that the graph with these edges removed had a triangle . Suppose that , and . Then the pairs , and would not have had their edges removed, so they would have had to be both -regular and of density at least . If is sufficiently small, it is not hard to deduce from these two properties that the number of (labelled) triangles with one vertex in , one in and one in is not much smaller than . Since each cell of the partition contains a constant fraction of all the vertices, this gives us a lot of triangles, contradicting the assumption that there were fewer than triangles, at least if is chosen small enough.

**Finding corners in dense sets.**

Now let us use the triangle-removal lemma to prove that a dense subset of contains a triple of the form with . Such a configuration is sometimes called a *corner*. Suppose then that is a set of size . Form a tripartite graph with vertex sets and , and the following edges. If and , then is an edge if and only if . If and , then is an edge if and only if . Finally, if and , then is an edge if and only if .

Suppose now that is a triangle in this graph . Then the points , , and all belong to . Setting we can write the second and third points as and . Therefore, we have a configuration of the desired kind—except if . If , which happens if , then all we get is a single point repeated three times. Let us call the resulting triangle in the graph *degenerate*.

At any rate, if contains no configurations of the desired kind, then the above argument shows that contains no non-degenerate triangles. Since the number of degenerate triangles is , this proves that contains triangles, which is far fewer than triangles. (Recall that the number of vertices of is .)

The triangle-removal lemma therefore implies, at least when is sufficiently large, that it is possible to remove at most edges from in such a way that no triangles remain. However, this is a contradiction, as it is easy to check that no two degenerate triangles share an edge, and we know that there are of them.

The above very beautiful argument is due to Solymosi, who was generalizing a similarly beautiful argument of Ruzsa and Szemerédi. This result about corners was first proved (I think — but am ready to be corrected if necessary) by Szemerédi, using a different argument. *[Actually it was Ajtai and Szemerédi: many thanks to Matthias Schacht for telling me this — which I now remember once having known.]*

**Sparse regularity lemmas.**

This section assumes familiarity with the proof of Szemerédi’s regularity lemma. A drawback of Szemerédi’s regularity lemma is that the bound on the size of the partition in terms of the parameter is very weak. This means that in practice the lemma is useful only for statements about dense graphs. However, there do exist adaptations that work for sparse graphs (some of which are described in the first couple of sections of this paper). Roughly, the idea is that one can prove a regularity lemma for a sparse graph if it is a dense subgraph of a sufficiently random-like graph . And very roughly, the reason for that is that if has density and has highly quasirandom behaviour, then the upper bound for the density of subgraphs of is not but , which means that the mean-square density of a partition cannot be more than , so the iteration in the proof of the regularity lemma can after all be guaranteed to finish after a constant number of steps (since, if is dense in , the initial mean-square density is within a constant of ). An important difference between the sparse case and the dense case is that if you have a triple of bipartite graphs that are sparse and regular, it is no longer trivial that the resulting tripartite graph contains many triangles. However, there are various ways that this can be done.

**What will happen next.**

I don’t yet have a better place to do things than this blog, so here’s what I plan to do. Within the next day or two I will publish a (now written) post that explains a possible approach to the density Hales-Jewett theorem when . The project is to decide whether this approach works or (more likely) can be convincingly shown not to work. Or at least that is the initial project — it is possible that there could be spin-offs.

As well as the main post that describes the approach, I shall also publish an explanation (also already written) of why I think this project might be a suitable one, as well as a dozen or so subposts, some of which will be empty. The idea of these subposts is to compensate to some extent for the excessive linearity of blog comments by separating out discussion of different aspects of the project. However, I don’t want to dictate too much the form that the discussion should take, so I will also leave several of the subposts empty, and fill them if it becomes clear from the existing discussions that a new thread would be appropriate. (If this happens, I will fill the empty post with an attempted summary of the comments that have led to the new thread.) It’s a bit rough and ready, and won’t work if there are too many comments to deal with, but I’m hoping that the problem is at a level where the number will be manageable. The point of publishing empty posts is that then they will all appear consecutively on the blog.

**Added later:** I have slightly changed my mind about one detail. As planned, I shall publish a large number of extra posts for the purposes of trying to organize the threads of the discussion. However, I will not try to guess in advance what any of these threads might be, so initially *all* these extra posts will be empty. Only when clearly defined subdiscussions emerge will I suggest that they continue on separate threads. This is because I want the whole process to be as democratic as possible: ideally it won’t always be me who decides that a subdiscussion is sufficiently “clearly defined” to deserve its own place.

Tags: Polymath project

January 30, 2009 at 3:41 pm |

[…] scale math, a social […]

January 30, 2009 at 5:12 pm |

Dear Tim,

It might be useful to have a single category for all of the posts related to this project, as this would provide an easy way to view all such posts on a single web page. (In fact, should further work on the project also appear on other wordpress blogs, they can use the same category, so that they can be viewed in a single global wordpress location.)

January 30, 2009 at 6:27 pm |

Terry, that’s an excellent idea and I can’t think why I didn’t think of it (especially as I was puzzling over how I could do what it does so easily).

For some more interesting ideas, in response to some of which my plans have slightly changed, I recommend a look at Michael Nielsen’s response to the proposal.

January 30, 2009 at 7:08 pm |

Dear Terry and Tim,

If the project is given a reasonably unique name, which is then used to tag posts, it should be easy to track across all blogging platforms, not just WordPress:

http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=%22polymath+project%22&btnG=Search+Blogs

A straight up Google search shows a lot of hits for “Polymath project”. But a Google blog search shows only a few blog hits, so maybe it’s a unique enough name already. If there’s a lot of activity on other blogs, perhaps Tim could add a link to the blog search on his blog, so other people are aware of this possibility?

January 31, 2009 at 7:27 am |

Doesn’t the delta in the Furstenberg-Katznelson theorem need to be also less than or equal to 1? Otherwise I’m interpreting something wrong.

In the Quasirandomness, Counting and Regularity paper you link to, on page 32 line 3 Y_j should be |Y_j|.

January 31, 2009 at 8:17 am |

If then the theorem as stated is trivially true … so needs to be less than 1 for the statement to be interesting, but not for it to make sense.

January 31, 2009 at 9:51 am |

[…] a new approach to the “density Hales -Jewett theorem”. A background post apears here. Hillel Furstenberg and Izzy Katznelson’s proof of the density Hales-Jewett theorem was a […]

February 3, 2009 at 6:23 pm |

[…] challenge is to find a purely combinatorial proof of the theorem. More background can be found here. Serious discussion of the problem starts […]

February 6, 2009 at 10:46 am |

[…] lemma in Kneser graphs, vertex 10 is the normal triangle-removal lemma (as described in the background-information post), and we are looking for vertex 11. Since getting from 00 to 10 is by no means a triviality, […]

February 20, 2009 at 1:15 am |

[…] and defined his goal as trying to get to a combinatorial solution for the problem. Gowers wrote a background post about the problem and a post about the procedure, where he incorporated feedback from Michael Nielsen and others. […]

July 27, 2009 at 7:39 am |

[…] on the triangle removal lemma (see e.g. my Simons lecture on the subject, or Tim Gowers’ background article for the project), it is thus natural to ask whether the density Hales-Jewett theorem has a proof […]

July 29, 2009 at 9:39 pm |

[…] helps to make progress on the problem. (similar examples from other mathematicians, such as the polymath project), and a brand new blog for this: […]

December 15, 2009 at 1:55 pm |

[…] Mathematics Possible?” — he proposed an attack on a stubborn math problem called the Density Hales-Jewett Theorem. He encouraged the thousands of readers of his blog to jump in and start proving. Mathematics is a […]

April 8, 2010 at 1:03 pm |

[…] an initial post asking “Is Massively Collaborative Mathematics Possible?”, he posted a description of the problem and invited his readers to have at it in […]

May 1, 2010 at 7:41 pm |

[…] began the Polymath Project with a description of the problem to be attacked (see below), a list of rules of collaboration, and a list of 38 brief observations he’d made […]

July 12, 2010 at 4:45 pm |

[…] that I’m the only person out there who thought that somewhat charmingly naive. Check out the brief descriptions of some mathematics that one would need to know in order to have a realistic chan… the DHJ Polymath project. Oh dear! With my fuzzy recollection of the the Pigeonhole principle and […]

May 24, 2011 at 5:14 pm |

[…] The article highlights eminent mathematician and Cambridge University researcher Timothy Gowers’s efforts to solve a handful of highly complex mathematical problems by crowdsourcing them — inviting other people to weigh in with their own suggestions for resolving them. He dubbed it the Polymath Project, an undertaking that ultimately produced a series of new ideas and insights as well as several collaborative papers published under the collective pseudonym DHJ Polymath. […]

November 4, 2011 at 12:45 pm |

[…] quinze minutos após ele postar o problema no seu blog, um matemático húngaro-canadense publicou um comentário. Um professor americano de uma escola de […]