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.
1. It is not the case that the aim of the project is to find a combinatorial proof of the density Hales-Jewett theorem when \(k=3\). I would love it if that was the result, but the actual aim is more modest: it is either to prove that a certain approach to that theorem (which I shall soon explain) works, or to give a very convincing argument that that approach cannot work. (I shall have a few remarks later about what such a convincing argument might conceivably look like.)
2. I think that the chances of success even for this more modest aim are substantially less than 100%. So let me be less fussy still. I will regard the experiment as a success if it leads to anything that could count as genuine progress towards an understanding of the problem. However, that success has a quantitative aspect to it: what I am really interested in is progress that results from multiple collaboration. If what actually happens is that several people make intelligent remarks, but without building on each other’s remarks, then what will have been gained will still be worthwhile but it will be less interesting from the point of view of this experiment.
3. I’ve thought of one more ground rule, and also a general guideline that clarifies a couple of the existing rules. The extra rule is that there needs to be some possibility for the experiment to be declared to have finished. What I suggest here is that if a consensus emerges that no further progress is likely, I (or perhaps somebody else) will write a summary of the main conclusions that have been reached, and it will then become public property in the way that a conventional mathematics preprint would be. That is, others would be welcome to make use of it in their own publications if they wanted to. Probably the summary would be posted on the ArXiV (after people had had a chance to suggest changes) but not conventionally published. The guideline, which is designed to stop people going away and doing a lot of work in private — the whole point is that we should all display our thought processes — is that you should not write anything that requires you to go away and do some calculations on a piece of paper. As I said in the other guidelines, if all goes well there will eventually be a place for detailed working out of ideas, but people should do that only after first establishing that that would be welcomed.
In order to encourage the style I’m hoping for, I shall practise what I preach, in a sense anyway, by giving my initial thoughts on the problem in small chunks. That is, I’ll write them as though they were a lot of comments that could in theory have been made by several different people instead of just one. I’ll number them with letters of the alphabet (so that they don’t get confused with the numbered comments on this post).
A. Might it be possible to prove the density Hales-Jewett theorem for \(k=3\) by imitating the triangle-removal proof that dense subsets of \(\null [n]^2\) contain corners?
B. If one were going to do that, what would the natural analogue of the tripartite graph associated with a dense subset be? To put that question more precisely, if we’ve got a dense subset \(A\) of \(\null [3]^n\), then how might we define a tripartite graph \(G\) in such a way that triangles in \(G\) correspond to (possibly degenerate) combinatorial lines?
C. It’s perhaps worth pointing out that there is a natural definition of a degenerate combinatorial line: it’s one where the set of coordinates that vary from 1 to 3 is empty.
D. If we just look at the vertex sets \(X\) and \(Y\) in the case of subsets \(A\subset [n]^2\), we have a very simple definition for an edge: it’s a pair \((x,y)\) that belongs to \(A\).
E. Does \(\null [3]^n\) split up nicely as a Cartesian product?
F. Well, you can write it as \(\null [3]^r\times [3]^s\), but that doesn’t help much.
G. Why doesn’t it help?
H. Because if we represent a typical point as \((x,y)\) with \(x\in [3]^r\) and \(y\in [3]^s\), then a Hales-Jewett line is not a triple of the form \((x,y)\), \((x+d,y)\), \((x,y+d)\). That’s partly because we can’t even make sense of adding \(d\), but more fundamentally because even if we could invent a useful definition of addition in this context, we still wouldn’t get a Hales-Jewett line.
I. It was clear in advance that that was not going to work, because the splitting up as a Cartesian product was completely non-canonical.
J. By the way, there’s a nice way of deducing the corners result from density Hales-Jewett. Let me quickly explain it, omitting a few details. Suppose we take a set \(A\subset [3]^n\) with the special property that whether or not a sequence \(x\) belongs to \(A\) depends only on the numbers of \(1\)s, \(2\)s and \(3\)s in \(x\). That is, let \(T\) be the set of all triples \((r,s,t)\) of non-negative integers such that \(r+s+t=n\), let \(S\) be some subset of \(T\), and let \(A\) be the set of sequences \(x\) such that \((n_1(x),n_2(x),n_3(x))\in S\), where \(n_i(x)\) stands for the number of \(i\)s in \(x\). Now suppose you have a combinatorial line \(L\). If \(d\) is the number of variable coordinates in \(L\), then \(S\) must contain a triple of points of the form \((r+d,s,t),\) \((r,s+d,t),\) \((r,s,t+d)\) (where \(r\), \(s\) and \(t\) are the numbers of \(1\)s, \(2\)s and \(3\)s amongst the fixed coordinates of \(L\)).
Now \(T\) is a large triangular subset of a triangular grid, and one can (if one really feels like it) shear it so that it becomes a right-angled triangle instead of an isosceles triangle. In this way it is not hard to show that the assertion that every dense subset of \(T\) contains the vertices of an equilateral triangle of the form \((r+d,s,t)\), \((r,s+d,t)\), \((r,s,t+d)\) is equivalent to the corners result.
Unfortunately it’s not the case that dense subsets of \(T\) correspond to dense subsets of \(\null [3]^n\) (because almost every point in \(\null [3]^n\) has similar numbers of \(1\)s, \(2\)s and \(3\)s) but there are dodges for getting round that.
K. That’s very helpful, because we almost certainly want whatever definition we come up with for the graph \(G\) to give rise to the definition that we used for \(\null [n]^2\) when the subset of \(\null [3]^n\) is of the special kind that depends only on the numbers of coordinates with the three possible values.
L. All right then. That tells us that for subsets of \(\null [3]^n\) that just depend on numbers of different types of coordinates, we want edges of the \(XY\) graph to correspond in some sensible way to points in \(A\) that have a particular number of \(1\)s and a particular number of \(2\)s.
M. That suggests that in the general case we want some data about the \(1\)s and \(2\)s in \(x\) to determine \(x\), just as the number of \(1\)s and \(2\)s determines the numbers of all three types of coordinates. And of course this is trivial: instead of looking at the numbers of the three types, look at the sets where they occur.
N. Indeed, there is an obvious tripartite graph we can define. Let its vertex sets, which I’ll call \(X\), \(Y\) and \(Z\), all be copies of the power set of \(\null [n]\): i.e., in each vertex set the vertices are subsets of \(\null [n]\). Given two disjoint sets \(U\in X\) and \(V\in Y\), there is a unique point \(x\in[3]^n\) that takes the value \(1\) in \(U\), the value \(2\) in \(V\), and the value \(3\) everywhere else. Join \(U\) to \(V\) if that point \(x\) belongs to the given subset \(A\subset [3]^n\). And do the obviously corresponding things for the \(YZ\) and \(XZ\) graphs.
O. Does that work? That is, if we have a triangle in that graph, does it correspond to a combinatorial line?
P. Yes. Here’s a quick proof. Suppose we have \(U\in X\), \(V\in Y\) and \(W\in Z\), and suppose that they form a triangle in the graph. By the way we defined the edges, the sets \(U\), \(V\) and \(W\) are disjoint. For \(i=1,2,3\) let’s write \(\phi_i(x)\) for the set of \(j\) such that \(x_j=i\). Then in the set \(A\) we can find a point \(a\) such that \(\phi_1(a)=U\) and \(\phi_2(a)=V\), and also a point \(b\) in \(A\) with \(\phi_2(b)=V\) and \(\phi_3(b)=W\), and finally a point \(c\) in \(A\) with \(\phi_1(c)=U\) and \(\phi_3(c)=W\). Now let \(T=[n]\setminus (U\cup V\cup W)\). Since for every point \(x\) we have \(\phi_1(x)\cup\phi_2(x)\cup\phi_3(x)=[n]\), we find that \(\phi_3(a)=W\cup T\), \(\phi_1(b)=V\cup T\) and \(\phi_2(c)=U\cup T\). In other words, the three sequences \(a\), \(b\) and \(c\), which all lie in \(A\), all take values \(1\) on \(U\), \(2\) on \(V\) and \(3\) on \(W\), and \(b\) is \(1\) everywhere on \(T\), \(c\) is \(2\) everywhere on \(T\) and \(a\) is \(3\) everywhere on \(T\). This gives us a combinatorial line except in the degenerate case \(T=\emptyset\).
Q. Wow. That means we’re done by triangle removal doesn’t it?
R. Unfortunately it doesn’t. The problem is that that tripartite graph is not dense. In fact, it’s not even close to dense. To see why not, just pick a random pair of subsets \(U\) and \(V\). They cannot be joined in the \(XY\) graph unless they are disjoint, and the probability of that happening is absolutely tiny.
S. That sounds a bit bad, but aren’t there sparse versions of Szemerédi’s regularity lemma?
T. I’m not sure it’s all that likely that there’s a version that applies when the density is exponentially small.
U. That’s a misleading way of putting it when the graph itself is exponentially large. If we let \(N=2^n\), so that there are \(N\) vertices in each of the three vertex sets, then the density of the graph is going to be of the form \(N^{-\alpha}\) for some constant \(\alpha\). But that’s still pretty sparse, it has to be said.
V. Here’s another problem. The existing sparse regularity lemmas tend to assume that you’re sitting inside a highly random sparse graph, but are dense relative to that graph. In our case, the natural graph \(\Gamma\) that we’re sitting inside is the one where you join two sets if and only if they are disjoint and ignore whether they define a sequence that belongs to \(A\). It’s possible that the graph defined above will turn out to be dense relative to this graph. However, \(\Gamma\) is not by any stretch of the imagination random, or quasirandom. For example, if you look at the \(XY\) part, you can define \(X'\) to be the subset of \(X\) where all sets have size at most \(n-C\sqrt n\), and the same for \(Y'\), and it’s not hard to check that the density of the part of the graph from \(X'\) to \(Y'\) is substantially greater. (Basically, conditioning on sets being a bit smaller than average makes them quite a lot more likely to be disjoint.)
W. Yes, but at least the graph \(\Gamma\) is very concretely defined. Perhaps one could do some kind of regularity argument relative to \(\Gamma\) that exploited the fact that it has a nice simple definition.
X. Here’s a small and slightly encouraging observation. What does a typical \(XY\) edge look like? Well, there’s a one-to-one correspondence between \(XY\) edges and sequences in \(\null [3]^n\). Since a typical sequence in \(\null [3]^n\) has roughly equal numbers of \(1\)s, \(2\)s and \(3\)s, a typical edge in the \(XY\) graph consists of two disjoint sets of size about \(n/3\).
Y. Unfortunately it’s still very sparse if we somehow weight our sets so that almost all of them have size about \(n/3\), since two sets of size \(n/3\) have a tiny probability of being disjoint.
Z. Aren’t there tricks we could do to find dense bits of the graph \(\Gamma\)? For example, we know that if \(U\) and \(V\) are random small sets (of size \(n^{1/3}\), say) then with high probability they are disjoint. Might there be some way of restricting to “the small part of \(\Gamma\)“?
AA. How could one do that when almost all sequences have roughly equal numbers of \(1\)s, \(2\)s and \(3\)s? The dense set \(A\) might consist just of well-balanced sequences.
BB. It’s not as impossible as it sounds, because we can use an averaging trick. Suppose we want to restrict \(X\), \(Y\) and \(Z\) to small sets. What we can do is this. First we randomly choose a very small subset \(P\) of \(\null [n]\). Then for every \(m\in [n]\setminus P\) we randomly choose an element of \(\{1,2,3\}\). Finally, we do everything we want inside \(P\). That is, we define a graph by joining two subsets \(U\) and \(V\) of \(P\) if they are disjoint, and define associated sequences by letting \(U\) and \(V\) determine the values inside \(P\) and the random choice of values outside \(P\) give us the rest. This gives us a structure of the kind we are talking about, and the average density of points in \(A\) in this structure will be close to the density of \(A\) if \(P\) is small enough, because random sequences that are unbalanced inside a random small set \(P\) will not be especially unbalanced globally.
CC. That’s an interesting thought, but I think it leads to a problem. Suppose our \(XY\) graph consists of pairs \((U,V)\) of disjoint small subsets of \(P\), and similarly for our \(YZ\) graph and our \(XZ\) graph. Where are the degenerate triangles? You can’t have a sequence with very few \(1\)s in \(P\), very few \(2\)s in \(P\) and very few \(3\)s in \(P\) all at the same time.
DD. That’s a serious objection, but I still think the averaging trick could be quite useful for this problem.
EE. Here’s a different idea. The big problem is not so much that \(\Gamma\) is sparse as that it is not quasirandom. But perhaps we could make it quasirandom by putting weights on the edges (and perhaps if necessary the vertices as well, since the averaging trick above will enable us to get sets of positive density even with funny vertex weights). The basic idea would be to penalize edges that joined small sets together, because somehow those sets were “cheating” by being small. Is there some natural set of weights that one can just write down?
[The history of this idea is that earlier this afternoon I had got up to Y when I had to go and fetch my daughter from school. While walking there I couldn’t help thinking about the problem and this idea, which I have not explored, occurred to me. So even the effort of writing down my thoughts has been quite stimulating. Because I haven’t yet thought about this idea properly, I’m still in that delicious state of thinking it might be the key to the whole problem. But I’ve also been in this game long enough to know that the chances of that are very small. It’s tempting to investigate it, but I’m not going to as this is also an ideal opportunity to throw out an idea and wait for somebody else to destroy it (or, just perhaps, to develop it) instead.]
FF. A natural way to find such weights would be to start by trying to make every vertex have constant (weighted) degree.
GG. It’s easy to see that you can’t make \(\Gamma\) quasirandom by weighting the edges. For example, suppose you let \(\mathcal{A}\subset X\) and \(\mathcal{B}\subset Y\) both be the set of all subsets of \(\null [n]\) that contain \(1\). These two sets have density \(1/2\) and yet there is no edge of \(\Gamma\) between them.
[The history of this idea is that although I resolved not to think about the idea put forward in EE., I was on a car journey and I just couldn’t help it. That goes for the next couple of responses to it too, which I could help even less because at that point I was starting to get worried that the whole thing was indeed hopeless.]
HH. That sounds pretty bad.
II. Is it really as bad as all that? I can see that it’s a problem if you have very dense parts of the graph, because then you don’t have a global upper bound for the density of subgraphs when you are trying to prove a regularity lemma. But if you have parts of the graph that are very sparse, or even entirely free of edges, it’s not so obviously a problem because there could still be an upper bound. In other words, perhaps it’s enough for \(\Gamma\) to be “upper quasirandom” rather than quasirandom.
JJ. Another idea is that you just try to do everything relative to \(\Gamma\). That is, you define the density of an induced subgraph of \(G\) to be the number of edges in that subgraph divided by the number of edges in the corresponding induced subgraph of \(\Gamma\). Could that work?
KK. Going back to vertex weights, here are two remarks. First, the averaging trick shows that for more or less any weighting on the vertices, if you can prove the theorem with that weighting (which affects which sets count as dense) then you can prove the theorem with the uniform weighting. I could write a formal lemma to this effect if anybody wanted, but for now I think the informal statement is enough.
The second remark is that a natural weighting on sets is to make the weight of a set \(U\) equal to \((1/3)^{|U|}(2/3)^{n-|U|}\). Then the size of a typical set is \(n/3\), and the probability distribution on the collection of all subsets of \(\null [n]\) is the same as the probability distribution of the set of places where a random sequence in \(\null [3]^n\) takes any given value.
LL. In response to II, I don’t think it’s possible to make \(\Gamma\) even upper quasirandom by introducing edge weights. The idea to do so was roughly that one should penalize edges that join small sets because those were more likely to be disjoint. But making sets small is not the only way to make them more likely to be disjoint. For example, you could make \(\mathcal{A}\) consist of all sets that are slightly biased towards the first half of \(\null [n]\) (meaning that their intersection with the first \(n/2\) integers is slightly bigger than their intersection with the second \(n/2\) integers) and \(\mathcal{B}\) could consist of all sets that are slightly biased towards the second half of \(\null [n]\). Of course, one could legislate against that particular example, but the same trick can be played for any partition of \(\null [n]\) into two equal-sized subsets. It seems to be impossible to legislate against this, since, for trivial reasons, every set will be biased with respect to some partitions.
[The history of that idea was that I was sitting in the car waiting for a bus to arrive that had my daughter in it. Once again I just couldn’t help my mind wandering in a Hales-Jewetty direction.]
How might one completely kill off the above approach?
The tripartite graph that we form out of \(A\) has few triangles in the following sense: every edge \((U,V)\) in the \(XY\) graph is contained in just one triangle (the other vertex of which is \(\null [n]\setminus (U\cup V)\)). If one is to prove the theorem by means of an adaptation of the triangle-removal lemma, one would want the following graph-theoretic statement to be true: let \(G\) be any subgraph of \(\Gamma\) such that each edge is contained in at most one triangle. Then it is possible to remove \(o(3^n)\) edges from \(G\) to make it triangle free. A counterexample to this more general statement would almost certainly make the approach hopeless. (I say “almost certainly” because one might just be able to use some extra structural property of the graph derived from \(A\). But that would change the nature of the approach quite a bit.)
Perhaps there could be convincing arguments that described the most general possible iterative approach to proving regularity lemmas and then proved that no iterative approach could give a regularity lemma that had any chance of helping with this problem. The seeming impossibility of making \(\Gamma\) quasirandom would undoubtedly be a part of such an argument.
That’s all I have to suggest at the moment.
This entry was posted on February 1, 2009 at 1:43 pm and is filed under polymath1. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.