Polymath1 - Revision history

Teorth: /* End notes */

2010-04-23T20:58:27Z

End notes

← Older revision		Revision as of 13:58, 23 April 2010
Line 154:		Line 154:
	[["New Proof" grant acknowledgments]]		[["New Proof" grant acknowledgments]]

	[["Low Dimensions" grant acknowledgments]]		[["Low Dimensions" grant acknowledgments]] (and contact information)

Rweba: /* Write-up repositories */ Pointer to April draft of "Low Dimensions" Project

2010-04-22T17:38:19Z

Write-up repositories: Pointer to April draft of "Low Dimensions" Project

← Older revision		Revision as of 10:38, 22 April 2010
Line 7:		Line 7:
	[[TeX files for first paper\|Write-up page for the "New Proof" project]]. The most recent draft is [http://www.cs.cmu.edu/~odonnell/papers/dhj.pdf here], tentatively titled "A new proof of the density Hales-Jewett theorem".		[[TeX files for first paper\|Write-up page for the "New Proof" project]]. The most recent draft is [http://www.cs.cmu.edu/~odonnell/papers/dhj.pdf here], tentatively titled "A new proof of the density Hales-Jewett theorem".

	[[outline of second paper\|Write-up page for the "Low Dimensions" project]]. The most recent draft is [http://terrytao.wordpress.com/~~files/2009~~/07/~~polymath1~~.pdf here], tentatively titled "Density Hales-Jewett and Moser numbers in low dimensions".		[[outline of second paper\|Write-up page for the "Low Dimensions" project]]. The most recent draft is [http://terrytao.files.wordpress.com/2010/04/polymath.pdf here], tentatively titled "Density Hales-Jewett and Moser numbers in low dimensions".

	==Basic definitions==		==Basic definitions==

Teorth: /* Threads and further problems */

2010-01-26T03:30:57Z

Threads and further problems

← Older revision		Revision as of 20:30, 25 January 2010
Line 50:		Line 50:
	* [http://terrytao.wordpress.com/2009/05/22/dhj-writing-the-second-paper/ DHJ: writing the second paper] (inactive)		* [http://terrytao.wordpress.com/2009/05/22/dhj-writing-the-second-paper/ DHJ: writing the second paper] (inactive)
	* [http://terrytao.wordpress.com/2009/06/14/dhj-still-writing-the-second-paper/ DHJ: still writing the second paper] (inactive)		* [http://terrytao.wordpress.com/2009/06/14/dhj-still-writing-the-second-paper/ DHJ: still writing the second paper] (inactive)
	* [http://gowers.wordpress.com/2009/06/25/dhj-write-up-and-other-matters/ DHJ write-up and other matters] (~~'''active'''~~)		* [http://gowers.wordpress.com/2009/06/25/dhj-write-up-and-other-matters/ DHJ write-up and other matters] (inactive)
	* [http://terrytao.wordpress.com/2009/07/09/dhj-writing-the-second-paper-iii/ DHJ: writing the second paper III.] (inactive)		* [http://terrytao.wordpress.com/2009/07/09/dhj-writing-the-second-paper-iii/ DHJ: writing the second paper III.] (inactive)
	* [http://terrytao.wordpress.com/2010/01/15/density-hales-jewett-and-moser-numbers-nearing-the-final-draft DHJ and Moser numbers: nearing the final draft.] ('''active''')		* [http://terrytao.wordpress.com/2010/01/15/density-hales-jewett-and-moser-numbers-nearing-the-final-draft DHJ and Moser numbers: nearing the final draft.] ('''active''')

Teorth: /* Threads and further problems */

2010-01-26T03:27:00Z

Threads and further problems

← Older revision		Revision as of 20:27, 25 January 2010
Line 51:		Line 51:
	* [http://terrytao.wordpress.com/2009/06/14/dhj-still-writing-the-second-paper/ DHJ: still writing the second paper] (inactive)		* [http://terrytao.wordpress.com/2009/06/14/dhj-still-writing-the-second-paper/ DHJ: still writing the second paper] (inactive)
	* [http://gowers.wordpress.com/2009/06/25/dhj-write-up-and-other-matters/ DHJ write-up and other matters] ('''active''')		* [http://gowers.wordpress.com/2009/06/25/dhj-write-up-and-other-matters/ DHJ write-up and other matters] ('''active''')
	* [http://terrytao.wordpress.com/2009/07/09/dhj-writing-the-second-paper-iii/ DHJ: writing the second paper III.] ('''active''')		* [http://terrytao.wordpress.com/2009/07/09/dhj-writing-the-second-paper-iii/ DHJ: writing the second paper III.] (inactive)
			* [http://terrytao.wordpress.com/2010/01/15/density-hales-jewett-and-moser-numbers-nearing-the-final-draft DHJ and Moser numbers: nearing the final draft.] ('''active''')

	[http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=polymath1&btnG=Search+Blogs Here is a further list of blog posts related to the Polymath1 project]. [http://en.wordpress.com/tag/polymath1/ Here is wordpress's list].		[http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=polymath1&btnG=Search+Blogs Here is a further list of blog posts related to the Polymath1 project]. [http://en.wordpress.com/tag/polymath1/ Here is wordpress's list].

Ryanworldwide at 13:46, 19 October 2009

2009-10-19T13:46:58Z

← Older revision		Revision as of 06:46, 19 October 2009
Line 5:		Line 5:
	==Write-up repositories==		==Write-up repositories==

	[[TeX files for first paper\|Write-up page for the "New Proof" project]]. The most recent draft is [http://www.cs.cmu.edu/~odonnell/dhj~~-june-25~~.pdf here], tentatively titled "A new proof of the density Hales-Jewett theorem".		[[TeX files for first paper\|Write-up page for the "New Proof" project]]. The most recent draft is [http://www.cs.cmu.edu/~odonnell/papers/dhj.pdf here], tentatively titled "A new proof of the density Hales-Jewett theorem".

	[[outline of second paper\|Write-up page for the "Low Dimensions" project]]. The most recent draft is [http://terrytao.wordpress.com/files/2009/07/polymath1.pdf here], tentatively titled "Density Hales-Jewett and Moser numbers in low dimensions".		[[outline of second paper\|Write-up page for the "Low Dimensions" project]]. The most recent draft is [http://terrytao.wordpress.com/files/2009/07/polymath1.pdf here], tentatively titled "Density Hales-Jewett and Moser numbers in low dimensions".

Teorth: /* Write-up repositories */

2009-07-25T23:17:11Z

Write-up repositories

← Older revision		Revision as of 16:17, 25 July 2009
Line 7:		Line 7:
	[[TeX files for first paper\|Write-up page for the "New Proof" project]]. The most recent draft is [http://www.cs.cmu.edu/~odonnell/dhj-june-25.pdf here], tentatively titled "A new proof of the density Hales-Jewett theorem".		[[TeX files for first paper\|Write-up page for the "New Proof" project]]. The most recent draft is [http://www.cs.cmu.edu/~odonnell/dhj-june-25.pdf here], tentatively titled "A new proof of the density Hales-Jewett theorem".

	[[outline of second paper\|Write-up page for the "Low Dimensions" project]]. The most recent draft is [http://terrytao~~.files~~.wordpress.com/2009/06/~~polymath2~~.pdf ~~perhaps~~ here], tentatively titled "Density Hales-Jewett and Moser numbers in low dimensions".		[[outline of second paper\|Write-up page for the "Low Dimensions" project]]. The most recent draft is [http://terrytao.wordpress.com/files/2009/07/polymath1.pdf here], tentatively titled "Density Hales-Jewett and Moser numbers in low dimensions".

	==Basic definitions==		==Basic definitions==

Teorth: New page: == The Problem == Initially, the basic problem to be considered by the Polymath1 project was to explore a particular [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-de...

2009-07-24T22:22:25Z

New page: == The Problem == Initially, the basic problem to be considered by the Polymath1 project was to explore a particular [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-de...

New page

== The Problem ==

Initially, the basic problem to be considered by the Polymath1 project was to explore a particular [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ combinatorial approach] to the [[density Hales-Jewett theorem]] for k=3 (DHJ(3)), suggested by Tim Gowers. The [[Furstenberg-Katznelson argument|original proof of DHJ(3) used arguments from ergodic theory]]. Fairly soon, the scope of the project expanded and forked. Two projects emerged. The first project, "New Proof", had as its aim that of discovering any combinatorial argument for the theorem. The second project, "Low Dimensions", aimed to calculate precise bounds on density Hales-Jewett numbers and [[Moser's cube problem|Moser numbers]] for low dimensions n = 3, 4, 5, 6, 7, etc. Both projects appear to have been successful, and are in the writing-up stage.

==Write-up repositories==

[[TeX files for first paper|Write-up page for the "New Proof" project]]. The most recent draft is [http://www.cs.cmu.edu/~odonnell/dhj-june-25.pdf here], tentatively titled "A new proof of the density Hales-Jewett theorem".

[[outline of second paper|Write-up page for the "Low Dimensions" project]]. The most recent draft is [http://terrytao.files.wordpress.com/2009/06/polymath2.pdf perhaps here], tentatively titled "Density Hales-Jewett and Moser numbers in low dimensions".

==Basic definitions==

*[[line|Algebraic line]]

*[[line|Combinatorial line]]

*[[Combinatorial subspace]]

*[[corners|Corner]]

*[[Density]]

*[[line|Geometric line]]

*[[Slice]]

== Useful background materials ==

Here is [http://gowers.wordpress.com/2009/01/30/background-to-a-polymath-project/ some background to the project.] There is also a [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ general discussion on massively collaborative "polymath" projects.] This is [http://meta.wikimedia.org/wiki/File:MediaWikiRefCard.png a cheatsheet for editing the wiki.] Here is a [http://michaelnielsen.org/blog/?p=582 python script] which can help convert sizeable chunks of LaTeX into wiki-tex. Finally, here is the general [http://meta.wikimedia.org/wiki/Help:Contents Wiki user's guide].

== Threads and further problems==

* [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?] (inactive)
* (1-199) [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ A combinatorial approach to density Hales-Jewett] (inactive)
* (200-299) [http://terrytao.wordpress.com/2009/02/05/upper-and-lower-bounds-for-the-density-hales-jewett-problem/ Upper and lower bounds for the density Hales-Jewett problem] (inactive)
* (300-399) [http://gowers.wordpress.com/2009/02/06/dhj-the-triangle-removal-approach/ The triangle-removal approach] (inactive)
* (400-499) [http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity Quasirandomness and obstructions to uniformity] (inactive)
* (500-599) [http://gowers.wordpress.com/2009/02/13/dhj-possible-proof-strategies/#more-441/ Possible proof strategies] (inactive)
* (600-699) [http://terrytao.wordpress.com/2009/02/11/a-reading-seminar-on-density-hales-jewett/ A reading seminar on density Hales-Jewett] (inactive)
* (700-799) [http://terrytao.wordpress.com/2009/02/13/bounds-for-the-first-few-density-hales-jewett-numbers-and-related-quantities/ Bounds for the first few density Hales-Jewett numbers, and related quantities] (inactive)
* (800-849) [http://gowers.wordpress.com/2009/02/23/brief-review-of-polymath1/ Brief review of polymath1] (inactive)
* (850-899) [http://gowers.wordpress.com/2009/03/02/dhj3-851-899/ DHJ(3): 851-899] (inactive)
* (900-999) [http://terrytao.wordpress.com/2009/03/04/dhj3-900-999-density-hales-jewett-type-numbers/ DHJ(3): 900-999 (Density Hales-Jewett type numbers)] (inactive)
* (1000-1049) [http://gowers.wordpress.com/2009/03/10/problem-solved-probably/ Problem solved (probably)] (inactive)
* [http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics/ Polymath1 and open collaborative mathematics] (inactive)
* (1050-1099) [http://gowers.wordpress.com/2009/03/16/dhj3-and-related-results-1050-1099/ DHJ(3) and related results: 1050-1099] (inactive)
* (1100-1199) [http://terrytao.wordpress.com/2009/03/14/dhj3-1100-1199-density-hales-jewett-type-numbers/ DHJ(3): 1100-1199 (Density Hales-Jewett type numbers)] (inactive)
*(discussion) [http://gilkalai.wordpress.com/2009/03/25/an-open-discussion-and-polls-around-roths-theorem/ An Open Discussion and Polls: Around Roth’s Theorem] (inactive)
* (1200-1299) [http://terrytao.wordpress.com/2009/03/30/dhjk-1200-1299-density-hales-jewett-type-numbers/ DHJ(k): 1200-1299 (Density Hales-Jewett type numbers)] (inactive)
* [http://terrytao.wordpress.com/2009/05/22/dhj-writing-the-second-paper/ DHJ: writing the second paper] (inactive)
* [http://terrytao.wordpress.com/2009/06/14/dhj-still-writing-the-second-paper/ DHJ: still writing the second paper] (inactive)
* [http://gowers.wordpress.com/2009/06/25/dhj-write-up-and-other-matters/ DHJ write-up and other matters] ('''active''')
* [http://terrytao.wordpress.com/2009/07/09/dhj-writing-the-second-paper-iii/ DHJ: writing the second paper III.] ('''active''')

[http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=polymath1&btnG=Search+Blogs Here is a further list of blog posts related to the Polymath1 project]. [http://en.wordpress.com/tag/polymath1/ Here is wordpress's list].

A spreadsheet containing the latest upper and lower bounds for <math>c_n</math> can be found [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg here]. Here are the proofs of our [[upper and lower bounds]] for these constants, as well as the [[higher-dimensional DHJ numbers|counterparts for higher k]].

We are also collecting bounds for [[Fujimura's problem]], motivated by a [[hyper-optimistic conjecture]]. We are additionally investigating [[higher-dimensional Fujimura]].

There is also a chance that we will be able to improve the known bounds on [[Moser's cube problem]] or the [[Kakeya problem]].

Here are some [[unsolved problems]] arising from the above threads.

Here is a [[tidy problem page]].

== Proof strategies ==

It is natural to look for strategies based on one of the following:

* [[Szemerédi's original proof of Szemerédi's theorem]].
* [[Szemerédi's combinatorial proof of Roth's theorem]].
* [[Ajtai-Szemerédi's proof of the corners theorem]].
* The [[density increment method]].
* The [[triangle removal lemma]].
* [[Ergodic-inspired methods]].
* The [[Furstenberg-Katznelson argument]].
* Use of [[equal-slices measure]].

== Related theorems ==

* [[Carlson's theorem]].
* The [[Carlson-Simpson theorem]].
* [[Folkman's theorem]].
* The [[Graham-Rothschild theorem]].
* The colouring [[Hales-Jewett theorem]].
* The [[Kruskal-Katona theorem]].
* [[Roth's theorem]].
* The [[IP-Szemerédi theorem]].
* [[Sperner's theorem]].
* [[Szemerédi's regularity lemma]].
* [[Szemerédi's theorem]].
* The [[triangle removal lemma]].

All these theorems are worth knowing. The most immediately relevant are Roth's theorem, Sperner's theorem, Szemerédi's regularity lemma and the triangle removal lemma, but some of the others could well come into play as well.

==Important concepts related to possible proofs==

* [[Complexity of a set]]
* [[Concentration of measure]]
* [[Influence of variables]]
* [[Obstructions to uniformity]]
* [[Quasirandomness]]

==Complete proofs or detailed sketches of potentially useful results==

*[[Sperner's theorem|The multidimensional Sperner theorem]]
*[[Line-free sets correlate locally with complexity-1 sets]]
*[[Correlation with a 1-set implies correlation with a subspace]] (Superseded)
*[[Fourier-analytic_proof_of_Sperner|A Fourier-analytic proof of Sperner's theorem]]
*[[A second Fourier decomposition related to Sperner's theorem]]
*[[A Hilbert space lemma]]
*A [[Modification of the Ajtai-Szemerédi argument]]
*An [[abstract regularity lemma]]
*[[A general result about density increments]]

==Attempts at proofs of DHJ(3)==

*[[An outline of a density-increment argument]] (ultimately didn't work)
*[[A second outline of a density-increment argument]] (seems to be OK but more checking needed)
*[[Proof of DHJ(3) via density-increment|Another outline of the whole argument]] (attempts to be more detailed)
*[[Furstenberg-Katznelson argument]] (very sketchy)
*[[Austin's proof]] (very sketchy)
*[[Austin's proof II]] (mostly complete, though more explanation and motivation needed)
*A [[timeline]] of some of the progress on the "New Proof" project.

==Generalizing to DHJ(k)==

*[[DHJ(k) implies multidimensional DHJ(k)]]
*[[Line free sets correlate locally with dense sets of complexity k-2]]
*[[A general partitioning principle]]

== Bibliography ==

Here is a [[Bibliography]] of relevant papers in the field.

== How to help out ==

There are a number of ways that even casual participants can help contribute to the Polymath1 project:

* Expand the [[bibliography]]
* Join the [http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics metadiscussion thread]
* Join the [http://gilkalai.wordpress.com/2009/03/25/an-open-discussion-and-polls-around-roths-theorem open discussion] thread (about these mathematical problems; not about the open collaboration), and participate in the polls.
* Add some more Ramsey theorems to this wiki; one could hope to flesh out this wiki into a Ramsey theory resource at some point.
* Suggest a logo for this wiki!
* Suggest a way to speed up our [[genetic algorithm]]
* Point out places where the exposition could be improved
* Jump in to the technical discussion; find some nice new angles to the discussed problems.
* Add to this list

== End notes ==

[["New Proof" grant acknowledgments]]

[["Low Dimensions" grant acknowledgments]]