Polymath Wiki - User contributions [en]

Main Page

2011-07-21T13:14:41Z

Gilkalai: /* Discussions about polymath */

{{RightTOC}}
This is the wiki for ''polymath'' projects - massively collaborative online mathematical projects. The idea of such projects originated in Tim Gowers' blog post [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?]

Many polymath projects will be proposed, planned, and run at [http://polymathprojects.org/ this blog].

A Polymath [[logo]] is being trialled. If you have more suggestions, please add them to the [[logo]] page, or add to the discussion at [[Talk:logo]].

== Existing polymath projects ==

* [[Polymath1]]: New proofs and bounds for the density Hales-Jewett theorem. Initiated Feb 1, 2009; research results have now been submitted for publication.
* [[Definable Banach Spaces|Polymath2]]: Must an “explicitly defined” Banach space contain <math>c_0</math> or <math>l_p</math>? Initiated Feb 17, 2009; attempts to relaunch via wiki, June 9 2010.
* [[imo 2009 q6|Mini-polymath1]]: Solving Problem 6 of the 2009 International Mathematical Olympiad. Initiated July 20, 2009; five proofs obtained so far.
* [[The polynomial Hirsch conjecture|Polymath3]]. The polynomial Hirsch conjecture. Proposed July 17, 2009; launched, September 30, 2010.
* [[finding primes|Polymath4]]: A deterministic way to find primes. Proposed July 27, 2009; launched Aug 9, 2009. Research results have been submitted for publication.
* [[The Erdős discrepancy problem|Polymath5]]. The Erdős discrepancy problem. Proposed Jan 10, 2010; launched Jan 19, 2010.
* [[imo 2010|Mini-polymath2]]: Solving Problem 5 the 2010 International Mathematical Olympiad. Proposed Jun 12, 2010; launched Jul 8, 2010; solved, Jul 8 2010.
* [[Improving the bounds for Roth's theorem|Polymath6]]. Improving the bounds for Roth's theorem. Proposed Feb 5, 2011.
* [[imo 2011|Mini-polymath3]]: Solving a problem from the 2011 International Mathematical Olympiad. Proposed Jun 9, 2010.

== Polymath-like projects ==

* Scott Aaronson's "philomath project": "[http://scottaaronson.com/blog/?p=453 Sensitivity vs. Block sensitivity]" (see also [http://mathoverflow.net/questions/31482/the-sensitivity-of-2-colorings-of-the-d-dimensional-integer-lattice this Math Overflow question]). Launched Jul 13, 2010.
* A [[wiki]] page clearinghouse for [[Deolalikar P vs NP paper]]. Launched Aug 10, 2010.

== Proposed polymath projects ==

* [http://gilkalai.wordpress.com/2009/03/25/an-open-discussion-and-polls-around-roths-theorem/ The cap set problem]. Proposed March 25, 2009 (see also these [http://gilkalai.wordpress.com/2009/05/11/around-the-cap-set-problem-b/ two] [http://gilkalai.wordpress.com/2009/05/18/the-cap-set-problem-and-frankl-rodl-theorem-c/ followup] posts).
* [[Boshernitzan’s problem]]. Proposed July 27, 2009.
* [http://gowers.wordpress.com/2009/09/16/possible-future-polymath-projects/ Possible future polymath projects]. Discussion opened September 16, 2009.
* [http://rjlipton.wordpress.com/2011/05/12/a-possible-polymath-project/ A possible polymath project:] Proposal by Richard Lipton to attack a conjecture due to Erdos, about a class of Diophantine equations.

A (partial) list of proposed projects can be found [http://en.wordpress.com/tag/polymath-proposals/ here].

If you have a tentative proposal for a polymath project, you can either make a post on it on your own blog, or place it [[other proposed projects|here]].

== Discussions about polymath ==

* [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?] Tim Gowers, January 27, 2009.
* [http://lucatrevisan.wordpress.com/2009/02/01/a-peoples-history-of-mathematics/ A people's history of mathematics] Luca Trevisan, February 1, 2009.
* [http://michaelnielsen.org/blog/?p=553 The polymath project] Michael Nielsen, February 3, 2009.
* [http://www.neverendingbooks.org/index.php/yet-another-math20-proposal.html Yet another math 2.0 proposal] Lieven le Bruyn, February 11, 2009.
* [http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics/ Polymath1 and open collaborative mathematics] Tim Gowers, March 10, 2009.
* [http://maxwelldemon.com/2009/03/14/polymath/ Polymath] Edmund Harriss, March 14, 2009.
* [http://science.slashdot.org/article.pl?sid=09/03/18/194228 Massive open collaboration in mathematics declared a success] Slashdot, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=581 How changing the technology of collaboration can change the nature of collaboration] Michael Nielsen, March 18, 2009.
* [http://michaelnielsen.org/blog/?p=584 The polymath project: scope of participation] Michael Nielsen, March 20, 2009.
* [http://gowers.wordpress.com/2009/03/24/can-polymath-be-scaled-up/ Can polymath be scaled up?] Tim Gowers, March 24, 2009.
* [http://whatisresearch.wordpress.com/2009/03/24/concluding-notes-on-the-polymath-project-and-a-challenge/ Concluding notes on the polymath project - and a challenge] Vilpulniak, March 24, 2009.
* [http://michaelnielsen.org/blog/on-scaling-up-the-polymath-project/ On scaling up the polymath project] Michael Nielsen, March 25, 2009.
* [http://numberwarrior.wordpress.com/2009/03/25/a-gentle-introduction-to-the-polymath-project/ A gentle introduction to the polymath project] Jason Dyer, March 25, 2009.
* [http://blogs.telegraph.co.uk/technology/iandouglas/9656357/tim_gowers_and_the_polymaths/ Tim Gowers and the polymaths] Ian Douglas (the Telegraph), April 29, 2009
* [http://terrytao.wordpress.com/2009/07/22/imo-2009-q6-mini-polymath-project-impressions-reflections-analysis/ IMO 2009 Q6 as mini-polymath project: impressions, reflections, analysis] Terence Tao, July 22, 2009.
* [http://polymathprojects.org/2009/07/27/selecting-the-next-polymath-project/ Selecting the next polymath project] Terence Tao, July 27, 2009.
* [http://blog.jonudell.net/2009/07/31/polymath-equals-user-innovatio/ Polymath equals user innovation] Jon Udell, July 31, 2009.
* [http://scienceblogs.com/christinaslisrant/2009/08/an_overview_of_the_polymath_pr.php An overview of the polymath project] Christina Pikas, August 1, 2009
* [http://whatisresearch.wordpress.com/2009/08/09/collaborative-mathematics-etc/ Collaborative mathematics etc.] Vipulniak, August 9, 2009
* [http://www.nature.com/nature/journal/v461/n7266/full/461879a.html Massively collaborative mathematics] Tim Gowers, Michael Nielsen, Nature, October 15, 2009
* [http://portonmath.wordpress.com/2009/10/25/collaborative-research-of-filters/ Collaborative math research – a real example] Victor Porton, October 24, 2009
* [http://whatisresearch.wordpress.com/2009/10/26/polymath-again/ Polymath again] Vipulniak, October 26, 2009
* [http://www.kennislink.nl/publicaties/wiskunde-met-zijn-allen Wiskunde met zijn allen] (Dutch), Alex van den Brandhof, Kennislink, November 12, 2009
* [http://www.sciencenews.org/view/generic/id/50532/title/Mathematics_by_collaboration Mathematics by collaboration], Julie Rehmeyer, ScienceNews, December 8, 2009
* [http://www.nytimes.com/projects/magazine/ideas/2009/#m Massively Collaborative Mathematics], Jordan Ellenberg, The Ninth Annual Year in Ideas, New York Times, 2009.
* [http://www.hypios.com/thinking/2010/01/13/massively-collaborative-mathematics-lessons-from-polymath1/ Massively Collaborative Mathematics: lessons from polymath1], Hypios, Jan 13 2010
* [http://ths1104.wordpress.com/2010/02/13/open-reflexions-sur-fond-de-polymaths/ Open réflexions sur fond de Polymaths] (French), ths1104, Feb 13 2010
* [http://www.javiertordable.com/blog/2010/02/25/collaborative-mathematics-future-of-science Collaborative Mathematics and The Future of Science] Javier Tordable, February 26 2010
* [http://www.scientificamerican.com/article.cfm?id=problem-solved-tic-tac-toe-blog Problem Solved, LOL: A Complex Tic-Tac-Toe Puzzle Falls Thanks to Blog Comments] Davide Castelvecchi, Scientific American, March 17 2010
* [http://www.thebigquestions.com/2010/04/08/blogging-tic-tac-toe-and-the-future-of-math/ Blogging, Tic Tac Toe, and the Future of Math] Steve Landsburg, The Big Questions, April 4 2010
* [http://www.siam.org/news/news.php?issue=0043.03 Massively Collaborative Mathematics] Julie Rehmeyer, SIAM News, Volume 43(3), April 2010 (to appear)
* [http://www.princeton.edu/~mbarany/cv.html#WikiSymPolymath `But this is blog maths and we're free to make up conventions as we go along': Polymath1 and the Modalities of `Massively Collaborative Mathematics.'] Michael Barany, Proceedings of the 6th International Symposium on Wikis and Open Collaboration, Gdansk, Poland, 2010.
* [http://www.cs.cmu.edu/~jcransh/papers/cranshaw_kittur.pdf J. Cranshaw and A. Kittur. The Polymath Project: Lessons from a successful online collaboration in mathematics]. In Proceedings of the Conference on Human Factors in Computing Systems, Vancouver, BC, Canada, May 2011.
* [http://www.newscientist.com/article/mg21028113.900-how-to-build-the-global-mathematics-brain.html How to build the global mathematics brain], Jacob Aron, New Scientist, 4 May 2011.
* [http://www.newscientist.com/article/mg21028112.900-mathematics-becomes-more-sociable.html Mathematics becomes more sociable], New Scientist, 5 May 2011.
* [http://polymathprojects.files.wordpress.com/2011/03/polymathias.jpg Mathematical Advances: Lone or Massively Collaborative Endeavors?] from IAS Institute Letter for fall 2010 based on a discussion organized by IAS fall 2010.
Additional links are very welcome.

== Other links ==

* [http://polymathprojects.org/ The polymath blog]
* [http://polymathprojects.org/general-polymath-rules/ General polymath rules]

== Note on anonymous editing ==

To help combat spam, anonymous editing has been disabled, and a captcha system added to hinder automated account creation. If this is causing problems, please email mn@michaelnielsen.org.

Talk:Polymath1

2009-07-25T06:51:24Z

Gilkalai: New page: == Logo == Here is a suggested LOGO http://gilkalai.files.wordpress.com/2009/03/15.jpg

== Logo ==

Here is a suggested LOGO http://gilkalai.files.wordpress.com/2009/03/15.jpg

Main Page

2009-04-23T04:53:11Z

Gilkalai: /* Threads and further problems */

== 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 the main aim became that of discovering any combinatorial argument for the theorem. This aim appears to have been achieved but the proof has not yet been fully written up.

==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] (active)
* (1050-1099) [http://gowers.wordpress.com/2009/03/16/dhj3-and-related-results-1050-1099/ DHJ(3) and related results: 1050-1099] (active)
* (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)] (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]. Here is a [[timeline]] of progress so far.

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)

==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

Main Page

2009-04-04T11:54:33Z

Gilkalai: /* How to help out */

== 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 the main aim became that of discovering any combinatorial argument for the theorem. This aim appears to have been achieved but the proof has not yet been fully written up.

==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] (active)
* (1050-1099) [http://gowers.wordpress.com/2009/03/16/dhj3-and-related-results-1050-1099/ DHJ(3) and related results: 1050-1099] (active)
* (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] (semi-active)
* (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)] (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]. Here is a [[timeline]] of progress so far.

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)
*[[Furstenberg-Katznelson argument]] (very sketchy)
*[[Austin's proof]] (very sketchy)
*[[Austin's proof II]] (mostly complete, though more explanation and motivation needed)

==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

Main Page

2009-04-04T11:42:00Z

Gilkalai: /* How to help out */

== 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 the main aim became that of discovering any combinatorial argument for the theorem. This aim appears to have been achieved but the proof has not yet been fully written up.

==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] (active)
* (1050-1099) [http://gowers.wordpress.com/2009/03/16/dhj3-and-related-results-1050-1099/ DHJ(3) and related results: 1050-1099] (active)
* (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] (semi-active)
* (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)] (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]. Here is a [[timeline]] of progress so far.

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)
*[[Furstenberg-Katznelson argument]] (very sketchy)
*[[Austin's proof]] (very sketchy)
*[[Austin's proof II]] (mostly complete, though more explanation and motivation needed)

==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] (about these mathematical problems; not about the open collaboration) thread, 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

Main Page

2009-04-04T11:41:18Z

Gilkalai: /* How to help out */

== 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 the main aim became that of discovering any combinatorial argument for the theorem. This aim appears to have been achieved but the proof has not yet been fully written up.

==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] (active)
* (1050-1099) [http://gowers.wordpress.com/2009/03/16/dhj3-and-related-results-1050-1099/ DHJ(3) and related results: 1050-1099] (active)
* (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] (semi-active)
* (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)] (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]. Here is a [[timeline]] of progress so far.

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)
*[[Furstenberg-Katznelson argument]] (very sketchy)
*[[Austin's proof]] (very sketchy)
*[[Austin's proof II]] (mostly complete, though more explanation and motivation needed)

==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 (about these mathematical problems; not about the open collaboration) thread, 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

Main Page

2009-04-04T11:40:44Z

Gilkalai: /* How to help out */

== 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 the main aim became that of discovering any combinatorial argument for the theorem. This aim appears to have been achieved but the proof has not yet been fully written up.

==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] (active)
* (1050-1099) [http://gowers.wordpress.com/2009/03/16/dhj3-and-related-results-1050-1099/ DHJ(3) and related results: 1050-1099] (active)
* (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] (semi-active)
* (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)] (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]. Here is a [[timeline]] of progress so far.

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)
*[[Furstenberg-Katznelson argument]] (very sketchy)
*[[Austin's proof]] (very sketchy)
*[[Austin's proof II]] (mostly complete, though more explanation and motivation needed)

==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 (about these mathematical problems; not about the open collaboration)thread, 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

Main Page

2009-04-02T18:57:37Z

Gilkalai: /* Threads and further problems */

== 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 the main aim became that of discovering any combinatorial argument for the theorem. This aim appears to have been achieved but the proof has not yet been fully written up.

==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] (active)
* (1050-1099) [http://gowers.wordpress.com/2009/03/16/dhj3-and-related-results-1050-1099/ DHJ(3) and related results: 1050-1099] (active)
* (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] (semi-active)
* (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)] (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]. Here is a [[timeline]] of progress so far.

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)
*[[Furstenberg-Katznelson argument]] (very sketchy)
*[[Austin's proof]] (very sketchy)
*[[Austin's proof II]] (mostly complete, though more explanation and motivation needed)

==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]
* 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
* Add to this list