You are currently browsing the tag archive for the ‘polymath1’ tag.

This is a continuation of the 700-799 thread of the polymath1 project, which is now full.  During the course of that thread, we have made significant progress on the three problems being focused on:

1.  Upper and lower bounds for c_n for small n.

Let c_n be the largest size of a set in [3]^n without a combinatorial line.   We now have both human and computer-assisted proofs of the first few values of this sequence:

c_0=1; c_1=2; c_2=6; c_3=18; c_4=52; c_5 = 150; c_6 = 450.

The current best-known bounds for c_7 are 1302 \leq c_7 \leq 1348.  Given the gap involved here, and the rate at which the complexity of the problem has increased with n, it seems unlikely that we will be able to compute c_7 exactly any time soon, but it is possible that some improvement can still be made here.

2. A hyper-optimistic conjecture

Consider a variant of the above problem in which each element of [3]^n with a 1s, b 2s, and c 3s is weighted by the factor \frac{a! b! c!}{n!}; this gives [3]^n a total weight of \frac{(n+1)(n+2)}{2}. Let c^\mu_n be the largest weight of a line-free set of [3]^n, and let \overline{c}^\mu_n be the largest size of a subset of

\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}

which contains no upward-pointing equilateral triangles (a+r,b,c), (a,b+r,c), (a,b,c+r) with r>0. It is known that c^\mu_n \geq \overline{c}^\mu_n; the “hyper-optimistic conjecture” is that one in fact has c^\mu_n = \overline{c}^\mu_n. This would imply density Hales-Jewett for k=3.

Currently, the conjecture is verified for n \leq 5, where the values of c^\mu_n = \overline{c}^\mu_n for n=0,1,2,3,4,5 are 1,2,4,6,9,12 respectively; see this page and this page for details.  It seems feasible to handle n=6.  Currently we know that 15 \leq \overline{c}^\mu_6 \leq 17 and \overline{c}^\mu_6 \leq c^\mu_6 \leq 28.

3.  Asymptotics for Moser’s cube problem

Moser’s cube problem asks to compute the largest size c'_n of a subset of the cube [3]^n without geometric lines.  The first few values of c'_n are known:

c'_0=1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43.

The best asymptotic lower bound known is still of the order of 3^n/\sqrt{n}.  Improving this bound seems related to the well-known problem of improving the bounds in Behrend’s construction of an AP-3 free set of integers.

We are quite close now to pinning down c'_5; we know that it is equal to either 124 or 125, and it is looking increasingly unlikely that it is 125.

Comments on this thread should start at 900.

This thread is a continuation of the previous thread here on the polymath1 project.  Currently, activity is focusing on the following problems:

1.  Upper and lower bounds for c_n for small n.

Let c_n be the largest size of a set in {}[3]^n without a combinatorial line.  Thanks to efforts from previous threads, we have the first five values of c_n:

c_0=1; c_1=2; c_2=6; c_3=18; c_4=52.

We also know that 150 \leq c_5 \leq 154, and are working to narrow this further.  The arguments justifying these bounds can be found here.  The latest bounds for the next few values of c_n can be found here.

2.  A hyper-optimistic conjecture

Consider a variant of the above problem in which each element of {}[3]^n with a 1s, b 2s, and c 3s is weighted by the factor \frac{a! b! c!}{n!}; this gives {}[3]^n a total weight of \frac{(n+1)(n+2)}{2}.  Let c^\mu_n be the largest weight of a line-free set of {}[3]^n, and let \overline{c}^\mu_n be the largest size of a subset of

\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}

which contains no upward-pointing equilateral triangles (a+r,b,c), (a,b+r,c), (a,b,c+r) with r>0.  It is known that c^\mu_n \geq \overline{c}^\mu_n; the “hyper-optimistic conjecture” is that one in fact has c^\mu_n = \overline{c}^\mu_n.  This would imply density Hales-Jewett for k=3.

Currently, we know the following values for these sequences:

c^\mu_0 = 1; c^\mu_1 = 2; c^\mu_2 = 4

and

\overline{c}^\mu_0 = 1; \overline{c}^\mu_1 = 2; \overline{c}^\mu_2 = 4; \overline{c}^\mu_3 = 6; \overline{c}^\mu_4 = 9; \overline{c}^\mu_5 = 12.

There are also some further upper and lower bounds known; see this spreadsheet for the latest bounds, and this page for proofs of the bounds.  The data so far is consistent with the conjecture, but more work would be needed to obtain a more convincing case for it.

3.  Asymptotics for Moser’s cube problem

Moser’s cube problem asks to compute the largest size c'_n of a subset of the cube {}[3]^n without geometric lines.  The first few values of c'_n are known:

c'_0=1; c'_1 = 2; c'_2 = 6; c'_3 = 14; c'_4 = 43.

The best asymptotic lower bound known is c'_n \gg 3^n/\sqrt{n}.  Given that we have a significantly superior lower bound of c_n \geq 3^{n-O(\sqrt{\log n})} for c_n, one might hope to similarly improve the lower bound for Moser’s problem.  But there seems to be a technical snag, based on the observation that between two slices \Gamma_{a,b,c} and \Gamma_{a',b',c'} with the c-a=c'-a', there are in fact quite a few combinatorial lines connecting them, and so it is not obvious how to create a geometric line-free set that involves more than one slice per value of c-a.

It is also of interest to work out what asymptotic lower bound for c_n one can get for larger values of k than 3.

Comments on this thread should start at 700.  We will also try to record progress made at the polymath1 wiki and at the polymath1 spreadsheet, as appropriate.

As part of the polymath1 project, I would like to set up a reading seminar on this blog for the following three papers and notes:

  1. H. Furstenberg, Y. Katznelson, “A density version of the Hales-Jewett theorem for k=3“, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–241.
  2. R. McCutcheon, “The conclusion of the proof of the density Hales-Jewett theorem for k=3“, unpublished.
  3. H. Furstenberg, Y. Katznelson, “A density version of the Hales-Jewett theorem“, J. Anal. Math. 57 (1991), 64–119.

As I understand it, paper #1 begins the proof of DHJ(3) (the k=3 version of density Hales-Jewett), but the proof is not quite complete, and the notes in #2 completes the proof using ideas from both paper #1 and paper #3.  Paper #3, of course, does DHJ(k) for all k.  For the purposes of the polymath1 project, though, I think it would be best if we focus exclusively on k=3.

While this seminar is of course related in content to the main discussion threads in the polymath1 project, I envision this to be a more sedate affair, in which we go slowly through various sections of various papers, asking questions of each other along the way, and presenting various bits and pieces of the proof.  The papers require a certain technical background in ergodic theory in order to understand, but my hope is that if enough other people (in particular, combinatorialists) ask questions here (and “naive” or “silly” questions are strongly encouraged) then we should be able to make a fair amount of the arguments here accessible.  I also hope that some ergodic theorists who have been intending to read these papers already, but didn’t get around to it, will join with reading the papers with me.

This is the first time I am trying something like this, and so we shall be using the carefully thought out protocol known as “making things up as we go along”.  My initial plan is to start understanding the “big picture” (in particular, to outline the general strategy of proof), while also slowly going through the key stages of that proof in something resembling a linear order.  But I imagine that the focus may change as the seminar progresses.

I’ll start the ball rolling with some initial impressions of paper #1 in the comments below.  As with other threads in this project, I would like all comments to come with a number and title, starting with 600 and then incrementing (the numbers 1-599 being reserved by other threads in this project).

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

Read the rest of this entry »

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

Further articles on this project are collected at this page.

Archives

RSS Google+ feed

  • An error has occurred; the feed is probably down. Try again later.
Follow

Get every new post delivered to your Inbox.

Join 3,867 other followers