Tag Archive

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

Some links

1 May, 2010 in non-technical, polymath | Tags: , , | by | 3 comments

Michael Nielsen has posted a draft of his article “Introduction to the Polymath Project and “Density Hales-Jewett and Moser Numbers”” for comments, which will precede our own polymath article in the Szemerédi birthday conference proceedings.

As an unrelated link, Jordan Ellenberg has just written a piece for the Washington Post on statistical sampling and how it could make the US census more accurate.  (Whether this is politically viable is, of course, a different matter.)

DHJ Polymath paper accepted

22 April, 2010 in non-technical, polymath, update | Tags: | by | 20 comments

Ordinarily, I only mention my research papers on this blog when they are first submitted, or if a major update is required.  With the paper arising from the DHJ Polymath “Low Dimensions” project, though, the situation is a little different as the collaboration to produce the paper took place on this blog.

Anyway, the good news is that the paper has been accepted for the Szemerédi birthday conference proceedings.  The referee was positive and recommended only some minor changes (I include the list of changes below the fold).  I have incorporated these changes, and the new version of the paper can be found here.  Within a few days I need to return the paper to the editor, so this is the last chance to propose any further corrections or changes (though at this stage any major changes are unlikely to be feasible).

The editor asked a good question: should we have a list of participants for this project somewhere?  If so, it seems to make more sense to have this list as a link on the wiki, rather than in the paper itself. But making a list opens the can of worms of deciding what level of participation should be the threshold for inclusion in the list – should someone who only contributed, say, one tangential comment to one of the blog posts be listed alongside a substantially more active participant?

One possibility is that of self-reporting; we could set up a page for participants on the wiki and let anyone who felt like they contributed add their name, and rely on the honour code to keep it accurate.    This might be feasible as long as the page is kept unofficial (so, in particular, it will not be used as the formal list of authors for the paper).

A related question is whether to add an explicit link to the timeline for progress on this project and on the sister “New proof” project.  If so, this should also be kept unofficial (there was no formal guidelines as to what was included in the timeline and what was not).

These decisions do not necessarily have to be taken quickly; one can simply point to the wiki in the paper (as is already done in the current version), and update the wiki later if we decide to add these sorts of acknowledgments on that site.

Incidentally, if we have another successful Polymath project to write up, I would now strongly recommend using version control software (such as Subversion or git) to organise the writing process, both at the informal notes stage and also at the drafting stage.  It is certainly far superior to our improvised solution of putting the raw TeX files on a wiki…

Read the rest of this entry »

Density Hales-Jewett and Moser numbers

4 February, 2010 in math.CO, paper | Tags: | by | 7 comments

I’ve just uploaded the D.H.J. Polymath article “Density Hales-Jewett and Moser numbers” to the arXiv, submitted to the Szemeredi birthday conference proceedings.

This article investigates the Density Hales-Jewett numbers c_{n,3}, defined as the largest subset of the n-dimensional cube [3]^n containing no combinatorial line, as well as the related Moser numbers c'_{n,3}, defined as the largest subset of the n-dimensional cube containing no geometric line.  We compute the first six numbers in each sequence in this paper.  For the DHJ numbers, they are 1,2,6,18,52,150,450 and for the Moser numbers they are 1,2,6,16,43,124,353.  The last two elements of both sequences are new; the computation c'_{6,3}=353 was the hardest and required a non-trivial amount of computer assistance.

We also establish the asymptotic lower bounds

c_{n,3} \geq 3^n \exp( - O(\sqrt{\log n}) )

and

c'_{n,3} \geq (2 \sqrt{\frac{9}{4\pi}} + o(1)) \frac{3^n}{\sqrt{n}}.

In contrast, the best known upper bound to these quantities is O(3^n / \log^{1/3}_* n), obtained by the sister project to this Polymath project.

We also show a counterexample to a certain “hyper-optimistic conjecture” which would have generalised the Lubell-Yamamoto–Meshalkin (LYM) inequality to this setting.

Thanks to all the participants for this interesting experiment in collaborative mathematics.  This is certainly a different type of project from the ones I normally am involved in, but I found it to be an enjoyable and educational experience.

There is still some time to make further (minor) corrections; I think the deadline for the final submission should be in April.

A new proof of the density Hales-Jewett theorem

22 October, 2009 in math.CO, paper, polymath | Tags: , , | by | 11 comments

The polymath1 project has just uploaded to the arXiv the paper “A new proof of the density Hales-Jewett theorem“, to be submitted shortly.  Special thanks here go to Ryan O’Donnell for performing the lion’s share of the writing up of the results, and to Tim Gowers for running a highly successful online mathematical experiment.

I’ll state the main result in the first non-trivial case k=3 for simplicity, though the methods extend surprisingly easily to higher k (but with significantly worse bounds).  Let c_{n,3} be the size of the largest subset of the cube [3]^n = \{1,2,3\}^n that does not contain any combinatorial line.    The density Hales-Jewett theorem of Furstenberg and Katznelson shows that c_{n,3} = o(3^n).  In the course of the Polymath1 project, the explicit values

c_{0,3} = 1; c_{1,3} = 2; c_{2,3} = 6; c_{3,3} = 18; c_{4,3} = 52; c_{5,3} =150; c_{6,3} = 450

were established, as well as the asymptotic lower bound

c_{n,3} \geq 3^n \exp( - O( \sqrt{ \log n } ) )

(actually we have a slightly more precise bound than this).  The main result of this paper is then

Theorem. (k=3 version) c_{n,3} \ll 3^n / \log^{1/2}_* n.

Here \log_* n is the inverse tower exponential function; it is the number of times one has to take (natural) logarithms until one drops below 1.  So it does go to infinity, but extremely slowly.  Nevertheless, this is the first explicitly quantitative version of the density Hales-Jewett theorem.

The argument is based on the density increment argument as pioneered by Roth, and also used in later papers of Ajtai-Szemerédi and Shkredov on the corners problem, which was also influential in our current work (though, perhaps paradoxically, the generality of our setting makes our argument simpler than the above arguments, in particular allowing one to avoid use of the Fourier transform, regularity lemma, or Szemerédi’s theorem).   I discuss the argument in the first part of this previous blog post.

I’ll end this post with an open problem.  In our paper, we cite the work of P. L. Varnavides, who was the first to observe the elementary averaging argument that showed that Roth’s theorem (which showed that dense sets of integers contained at least one progression of length three) could be amplified (to show that there was in some sense a “dense” set of arithmetic progressions of length three).  However, despite much effort, we were not able to expand “P.” into the first name.  As one final task of the Polymath1 project, perhaps some readers with skills in detective work could lend a hand in finding out what Varnavides’ first name was? Update, Oct 22: Mystery now solved; see comments.

DHJ: Writing the second paper III.

9 July, 2009 in math.CO, polymath | Tags: | by | 24 comments

This is a continuation of the preceding two threads here on the polymath1 project, which are now full.  We are closing on on the computation of the sixth Moser number – the size of the largest subset of the six-dimensional cube \{1,2,3\}^6 that does not contain any lines: it is either 353 or 354, and 354 looks close to being eliminated soon.

Besides this, the nominal purpose of this thread is to coordinate the writing of the second paper of the project.  In addition to incorporating whatever results we get from the six-dimensional Moser problem, a lot of work still has to be done on other sections of the paper, notably the higher k component and the component on Fujimura’s problem, as well as the appendices.

DHJ: Still writing the second paper

14 June, 2009 in math.CO, polymath | Tags: | by | 104 comments

This is a continuation of the previous thread here in the polymath1 project, which is now full.  Ostensibly, the purpose of this thread is to continue writing up the paper containing many of the things achieved during this side of the project, though we have also been spending time on chasing down more results, in particular using new computer data to narrow down the range of the maximal size of  6D Moser sets (currently we can pin this down to between 353 and 355).   At some point we have to decide what results to put in in full detail in the paper, what results to summarise only (with links to the wiki), and what results to defer to perhaps a subsequent paper, but these decisions can be taken at a leisurely pace.

I guess we’ve abandoned the numbering system now, but I suppose that if necessary we can use timestamps or URLs to link to previous comments.

DHJ: Writing the second paper

22 May, 2009 in math.HO, polymath | Tags: | by | 110 comments

Now that the quarter is nearing an end, I’m returning to the half of the polymath1 project hosted here, which focussed on computing density Hales-Jewett numbers and related quantities.  The purpose of this thread is to try to organise the task of actually writing up the results that we already have; as this is a metathread, I don’t think we need to number the comments as in the research threads.

To start the ball rolling, I have put up a proposed outline of the paper on the wiki.   At present, everything in there is negotiable: title, abstract, introduction, and choice and ordering of sections.  I suppose we could start by trying to get some consensus as to what should or should not go into this paper, how to organise it, what notational conventions to use, whether the paper is too big or too small, and so forth.  Once there is some reasonable consensus, I will try creating some TeX files for the individual sections (much as is already being done with the first polymath1 paper) and get different contributors working on different sections (presumably we will be able to coordinate all this through this thread).   This, like everything else in the polymath1 project, will be an experiment, with the rules made up as we go along; presumably once we get started it will become clearer what kind of collaborative writing frameworks work well, and which ones do not.

Polymath1 and three new proofs of the density Hales-Jewett theorem

2 April, 2009 in math.CO, polymath | Tags: | by | 16 comments

This week I gave a talk at UCLA on some aspects of polymath1 project, and specifically on the three new combinatorial proofs of the density Hales-Jewett theorem that have been obtained as a consequence of that project. (There have been a number of other achievements of this project, including some accomplished on the polymath1 threads hosted on this blog, but I will have to postpone a presentation of those to a later post.) It seems that at least two of the proofs will extend to prove this theorem for arbitrary alphabet lengths, but for this talk I will focus on the {k=3} case. The theorem to prove is then

Theorem 1 ({k=3} density Hales-Jewett theorem) Let {0 < \delta \leq 1}. Then if {n} is a sufficiently large integer, any subset {A} of the cube {[3]^n = \{1,2,3\}^n} of density {|A|/3^n} at least {\delta} contains at least one combinatorial line {\{ \ell(1), \ell(2), \ell(3)\}}, where {\ell \in \{1,2,3,x\}^n \backslash [3]^n} is a string of {1}s, {2}s, {3}s, and {x}‘s containing at least one “wildcard” {x}, and {\ell(i)} is the string formed from {\ell} by replacing all {x}‘s with {i}‘s.

The full density Hales-Jewett theorem is the same statement, but with {[3]} replaced by {[k]} for some {k \geq 1}. (The case {k=1} is trivial, and the case {k=2} follows from Sperner’s theorem.)

This theorem was first proven by Furstenberg and Katznelson, by first converting it to a statement in ergodic theory; the original paper of Furstenberg-Katznelson argument was for the {k=3} case only, and gave only part of the proof in detail, but in a subsequent paper a full proof in general {k} was provided. The remaining components of the original {k=3} argument were later completed in unpublished notes of McCutcheon. One of the new proofs is essentially a finitary translation of this {k=3} argument; in principle one could also finitise the significantly more complicated argument of Furstenberg and Katznelson for general {k}, but this has not been properly carried out yet (the other two proofs are likely to generalise much more easily to higher {k}). The result is considered quite deep; for instance, the general {k} case of the density Hales-Jewett theorem already implies Szemerédi’s theorem, which is a highly non-trivial theorem in its own right, as a special case.

Another of the proofs is based primarily on the density increment method that goes back to Roth, and also incorporates some ideas from a paper of Ajtai and Szemerédi establishing what we have called the “corners theorem” (and which is also implied by the {k=3} case of the density Hales-Jewett theorem). A key new idea involved studying the correlations of the original set {A} with special subsets of {[3]^n}, such as {ij}-insensitive sets, or intersections of {ij}-insensitive and {ik}-insensitive sets. Work is currently ongoing to extend this argument to higher {k}, and it seems that there are no major obstacles in doing so.

This correlations idea inspired a new ergodic proof of the density Hales-Jewett theorem for all values of {k} by Austin, which is in the spirit of the triangle removal lemma (or hypergraph removal lemma) proofs of Roth’s theorem (or the multidimensional Szemerédi theorem). A finitary translation of this argument in the {k=3} case has been sketched out; I believe it also extends in a relatively straightforward manner to the higher {k} case (in analogy with some proofs of the hypergraph removal lemma ).

Read the rest of this entry »

DHJ(k): 1200-1299 (Density Hales-Jewett type numbers)

30 March, 2009 in math.CO, polymath | Tags: | by | 91 comments

This is a continuation of the 1100-1199 thread of the polymath1 project, which is now full.  The focus has now mostly shifted to generalisations of the previous problems being studied to larger alphabet sizes k, so I am changing the title here from DHJ(3) to DHJ(k) to reflect this.

The discussion is evolving rapidly, but here are some of the topics currently being discussed:

Note that much of the most recent progress has not yet been ported to the wiki.  In order to help everyone else catch up, it may useful if authors of comments (particularly comments with lengthy computations, or with corrections to previous comments) put their work on the relevant page of the wiki (not necessarily in the most polished format), and perhaps only place a summary of it on the thread itself.

[Incidentally, for the more casual followers of this project, a non-technical introduction to this project can be found at this post of Jason Dyer.]

Comments here should start from 1200.

DHJ(3): 1100-1199 (Density Hales-Jewett type numbers)

14 March, 2009 in math.CO, polymath | Tags: | by | 118 comments

This is a continuation of the 900-999 thread of the polymath1 project, which is now full.  We’ve made quite a bit of progress so far on our original mission of bounding density Hales-Jewett numbers.  In particular, we have shown

  • c_6=450: Any subset of [3]^6 with 451 points contains a combinatorial line; and there is exactly one example with 450 points with no combinatorial line.  (We have two proofs, one by a large integer program, and the other being purely human-verifiable; the latter can be found here.)
  • c'_5=124: Any subset of [3]^5 with 125 points contains a geometric line; and we have several examples with 124 points with no geometric line.  (The proof is partly computer-assisted; details are here.)
  • 353 \leq c'_6 \leq 361: A genetic algorithm has constructed 353-point solutions in [3]^6 with no geometric line; in the other direction, linear and integer programming methods have shown that any set with 362 points must have a geometric line.
  • \overline{c}^\mu_{12} = 40: In the triangular grid \{(a,b,c) \in {\Bbb N}^3:a+b+c=12\}, any set of 41 points contains an upwards-pointing equilateral triangle (a+r,b,c),(a,b+r,c),(a,b,c+r) with r>0; and we have 40-point examples without such triangles.  This was conducted by an integer program.

This timeline shows the history of these and other developments in the project.

There are still several numbers that look feasible to compute.  For instance, the bounds on c'_6 should be able to be narrowed further.  Work is slowly progressing also on the equal-slices Hales-Jewett numbers c^\mu_n, which are hyper-optimistically conjectured to equal the Fujimura numbers \overline{c}^\mu_n; this has been verified by hand up to n=3 and by integer programming up to n=5.  We are also looking at trying to reduce the dependence on computer assistance in establishing the c'_5 = 124 result; the best human result so far is 124 \leq c'_5 \leq 125.

Some progress has recently been made on some other related questions.  For instance, we now have a precise description of the lower bound on c_n coming from the Behrend-Elkin construction, namely

c_n > C 3^{n - 4\sqrt{\log 2}\sqrt{\log n}+\frac 12 \log \log n}

for some absolute constant c.

Also, it is probably a good time to transport some of the discussion in earlier threads to the wiki and make it easier for outsiders to catch up.  (Incidentally, we need a logo for that wiki; any suggestions would be welcome!)

Comments on this thread should be numbered starting at 1100.

Archives