You are currently browsing the monthly archive for February 2009.

This is a continuation of several threads from Tim Gowers’ massively collaborative mathematics project, “A combinatorial approach to density Hales-Jewett“, which I discussed in my previous post.

For any positive integer n, let ${}[3]^n$ be the set of strings of length n consisting of 1s, 2s, and 3s, and define a combinatorial line to be a triple of such strings arising by taking a string in $\{1,2,3,x\}^n$ with at least one wildcard x, and substituting x=1, x=2, x=3 in that string (e.g. xx1x3 would give the combinatorial line $\{11113, 22123, 33133\}$).  Call a set $A \subset [3]^n$ of strings line-free if it contains no combinatorial lines, and let $c_n$ be the size of the largest set A which is line-free.  We then have

Density Hales-Jewett theorem (k=3): $c_n = o(3^n)$, i.e. $\lim_{n \to \infty} c_n/3^n = 0$.

This theorem implies several other important results, most notably Roth’s theorem on length three progressions (in an arbitrary abelian group!) and also the corners theorem of Ajtai and Szemeredi (again in an arbitrary abelian group).

Here are some of the questions we are initially exploring in this thread (and which I will comment further on below the fold):

1. What are the best upper and lower bounds for $c_n$ for small n?  Currently we know $c_0=1, c_1=2, c_2=6, c_3=18, c_4=52$, with some partial results for higher n.    We also have some relationships between different $c_n$.
2. What do extremal or near-extremal sets (i.e. line-free sets with cardinality close to $c_n$) look like?
3. What are some good constructions of line-free sets that lead to asymptotic lower bounds on $c_n$?  The best asymptotic lower bound we have currently is $c_n \geq 3^{n - O( \sqrt{\log n} )}$.
4. Can these methods extend to other related problems, such as the Moser cube problem or the capset problem?
5. How feasible is it to extend the existing combinatorial proofs of Roth’s theorem (or the corners theorem), in particular the arguments of Szemeredi, to the Density Hales-Jewett theorem?

But I imagine that further threads might develop in the course of the discussion.

As with the rest of the project, this is supposed to be an open collaboration: please feel free to pose a question or a comment, even if (or especially if) it is just barely non-trivial.  (For more on the “rules of the game”, see this post.)

The notion of what it means for a subset E of a space X to be “small” varies from context to context.  For instance, in measure theory, when $X = (X, {\mathcal X}, \mu)$ is a measure space, one useful notion of a “small” set is that of a null set: a set E of measure zero (or at least contained in a set of measure zero).  By countable additivity, countable unions of null sets are null.  Taking contrapositives, we obtain

Lemma 1. (Pigeonhole principle for measure spaces) Let $E_1, E_2, \ldots$ be an at most countable sequence of measurable subsets of a measure space X.  If $\bigcup_n E_n$ has positive measure, then at least one of the $E_n$ has positive measure.

Now suppose that X was a Euclidean space ${\Bbb R}^d$ with Lebesgue measure m.  The Lebesgue differentiation theorem easily implies that having positive measure is equivalent to being “dense” in certain balls:

Proposition 1. Let $E$ be a measurable subset of ${\Bbb R}^d$.  Then the following are equivalent:

1. E has positive measure.
2. For any $\varepsilon > 0$, there exists a ball B such that $m( E \cap B ) \geq (1-\varepsilon) m(B)$.

Thus one can think of a null set as a set which is “nowhere dense” in some measure-theoretic sense.

It turns out that there are analogues of these results when the measure space $X = (X, {\mathcal X}, \mu)$  is replaced instead by a complete metric space $X = (X,d)$.  Here, the appropriate notion of a “small” set is not a null set, but rather that of a nowhere dense set: a set E which is not dense in any ball, or equivalently a set whose closure has empty interior.  (A good example of a nowhere dense set would be a proper subspace, or smooth submanifold, of ${\Bbb R}^d$, or a Cantor set; on the other hand, the rationals are a dense subset of ${\Bbb R}$ and thus clearly not nowhere dense.)   We then have the following important result:

Theorem 1. (Baire category theorem). Let $E_1, E_2, \ldots$ be an at most countable sequence of subsets of a complete metric space X.  If $\bigcup_n E_n$ contains a ball B, then at least one of the $E_n$ is dense in a sub-ball B’ of B (and in particular is not nowhere dense).  To put it in the contrapositive: the countable union of nowhere dense sets cannot contain a ball.

Exercise 1. Show that the Baire category theorem is equivalent to the claim that in a complete metric space, the countable intersection of open dense sets remain dense.  $\diamond$

Exercise 2. Using the Baire category theorem, show that any non-empty complete metric space without isolated points is uncountable.  (In particular, this shows that Baire category theorem can fail for incomplete metric spaces such as the rationals ${\Bbb Q}$.)  $\diamond$

To quickly illustrate an application of the Baire category theorem, observe that it implies that one cannot cover a finite-dimensional real or complex vector space ${\Bbb R}^n, {\Bbb C}^n$ by a countable number of proper subspaces.  One can of course also establish this fact by using Lebesgue measure on this space.  However, the advantage of the Baire category approach is that it also works well in infinite dimensional complete normed vector spaces, i.e. Banach spaces, whereas the measure-theoretic approach runs into significant difficulties in infinite dimensions.  This leads to three fundamental equivalences between the qualitative theory of continuous linear operators on Banach spaces (e.g. finiteness, surjectivity, etc.) to the quantitative theory (i.e. estimates):

1. The uniform boundedness principle, that equates the qualitative boundedness (or convergence) of a family of continuous operators with their quantitative boundedness.
2. The open mapping theorem, that equates the qualitative solvability of a linear problem Lu = f with the quantitative solvability.
3. The closed graph theorem, that equates the qualitative regularity of a (weakly continuous) operator T with the quantitative regularity of that operator.

Strictly speaking, these theorems are not used much directly in practice, because one usually works in the reverse direction (i.e. first proving quantitative bounds, and then deriving qualitative corollaries); but the above three theorems help explain why we usually approach qualitative problems in functional analysis via their quantitative counterparts.

My good friend Tim Gowers has just started an experimental “massively collaborative mathematical project” over at his blog.  The project is entitled “A combinatorial approach to density Hales-Jewett“, and the aim is to see if progress can be made on this problem by many small contributions by a large number of people, as opposed to the traditional model of a few very large contributions by a small number of people (see this article for more on the “rules of the game”, and this article for why this particular project was picked as a test project).  I think this is an interesting experiment, and hopefully a successful one, though it is far too early to tell as yet.

I can describe the problem here.  Let n be a large integer, and let ${}[3]^n$ be the set of all strings of length n using the alphabet $\{1,2,3\}$, thus for instance $13323 \in [3]^5$.  A combinatorial line in ${}[3]^n$ is a triple of points in ${}[3]^n$ that can be formed by taking a string of length n using the alphabet $\{1,2,3,x\}$ with at least one occurrence of the “wildcard” x, and then substituting the values of 1, 2, 3 for the wildcard.  For instance, the string $1xx2x$ would lead to the combinatorial line $\{11121, 12222, 13323\}$ in ${}[3]^5$.  The (k=3) case of the density Hales-Jewett theorem of Furstenberg and Katznelson asserts:

Density Hales-Jewett theorem. Let $0 < \delta < 1$.  Then if n is sufficiently large depending on $\delta$, every subset of ${}[3]^n$ of density at least $\delta$ contains a combinatorial line.

[Furstenberg and Katznelson handled the case of general k in a subsequent paper.  The k=1 case is trivial, and as pointed out in this post by Gil Kalai, the k=2 case follows from Sperner’s theorem.]

Furstenberg and Katznelson’s proof uses ergodic theory, and in particular does not obviously give any bound as to how large n has to be depending on $\delta$ before the theorem takes effect.  No other proofs of this theorem are currently known.  So it would be desirable to have a combinatorial proof of the k=3 density Hales-Jewett theorem.  Since this theorem implies Roth’s theorem, and Roth’s theorem has a combinatorial proof based 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 based on something similar to the triangle removal lemma.  This is basically the question being explored in the above project. (Some further motivation for this problem can be found here.)