Main Page: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
← Older edit
Shuhari (talk | contribs)
7 edits
No edit summary
 
(329 intermediate revisions by 60 users not shown)
Line 1: Line 1:
== The Problem ==
{{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?]


Let <math>[3]^n</math> be the set of all length <math>n</math> strings over the alphabet <math>1, 2, 3</math>.  A ''combinatorial line'' is a set of three points in <math>[3]^n</math>, formed by taking a string with one or more wildcards <math>x</math> in it, e.g., <math>112x1xx3\ldots</math>, and replacing those wildcards by <math>1, 2</math> and <math>3</math>, respectively.  In the example given, the resulting combinatorial line is: <math>\{ 11211113\ldots, 11221223\ldots, 11231333\ldots \}</math>.  A subset of <math>[3]^n</math> is said to be ''line-free'' if it contains no lines. Let <math>c_n</math> be the size of the largest line-free subset of <math>[3]^n</math>.
Many polymath projects will be proposed, planned, and run at [http://polymathprojects.org/ This Blog].


'''Density Hales-Jewett (DHJ) theorem:''' <math>\lim_{n \rightarrow \infty} c_n/3^n = 0</math>
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]].


The original proof of DHJ used arguments from ergodic theory.  The basic problem to be consider by the Polymath project is to explore a particular [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ combinatorial approach to DHJ, suggested by Tim Gowers.] Some background to this project can be [http://gowers.wordpress.com/2009/01/30/background-to-a-polymath-project/ found here], and general discussion on massively collaborative "polymath" projects can be [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ found here].
The wiki is currently locked down due to a major influx of spam (July 29, 2013).  Please email thomas@asone.ai if you'd like an account set up, and I'll do my best to reply quickly.  


== Threads ==
== Existing polymath projects ==


* (1-199) [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ A combinatorial approach to density Hales-Jewett] (inactive)
* [[Polymath1]]: New proofs and bounds for the density Hales-Jewett theorem.  Initiated Feb 1, 2009; research results have now been published.
* (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] (active)
* [[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.
* (300-399) [http://gowers.wordpress.com/2009/02/06/dhj-the-triangle-removal-approach/ The triangle-removal approach] (inactive)
* [[imo 2009 q6|Mini-polymath1]]: Solving Problem 6 of the 2009 International Mathematical Olympiad. Initiated July 20, 2009; five proofs obtained so far.
* (400-499) [http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity Quasirandomness and obstructions to uniformity] (final call)
* [[The polynomial Hirsch conjecture|Polymath3]].  The polynomial Hirsch conjecture.  Proposed July 17, 2009; launched, September 30, 2010. 
* (500-599) TBA
* [[finding primes|Polymath4]]: A deterministic way to find primes.  Proposed July 27, 2009; launched Aug 9, 2009.  Research results have now been published.
* (600-699) [http://terrytao.wordpress.com/2009/02/11/a-reading-seminar-on-density-hales-jewett/ A reading seminar on density Hales-Jewett] (active)
* [[The Erd&#337;s discrepancy problem|Polymath5]]: The Erd&#337;s discrepancy problem. Proposed Jan 10, 2010; launched Jan 19, 2010. Activity ceased by the end of 2012, but results from the project were used to solve the problem in 2015.
* [[imo 2010|Mini-polymath2]]: Solving Problem 5 the 2010 International Mathematical Olympiad.  Proposed Jun 12, 2010; launched and 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, 2011; launched and solved, Jul 19, 2011.
* [[imo 2012|Mini-polymath4]]: Solving a problem from the 2012 International Mathematical Olympiad. Proposed, Jun 3, 2012; launched, July 12 2012.
* [[The hot spots conjecture|Polymath7]]:  Establishing the Hot Spots conjecture for acute-angled triangles.  Proposed, May 31st, 2012; launched, Jun 8, 2012.
* [[Bounded gaps between primes|Polymath8]]: Improving the bounds for small gaps between primes.  Proposed, June 4, 2013; launched, June 4, 2013.  Research results have now been published.
* [[Discretized Borel Determinacy and P=NP|Polymath9]]: exploring Borel determinacy-based methods for giving complexity bounds. Proposed, Oct 24, 2013; launched, Nov 3, 2013.
* [[The Erdos-Rado sunflower lemma|Polymath10]]: improving the bounds for the Erdos-Rado sunflower lemma.  Launched, Nov 2, 2015.
* [[Frankl's union-closed conjecture|Polymath11]]: proving Frankl's union-closed conjecture. Proposed Jan 21, 2016; launched Jan 29, 2016.  Concluded, Jan 17, 2017.
* [[Rota's conjecture|Polymath12]]: proving Rota's conjecture.  Proposed Feb 28, 2017.
* [[Intransitive dice|Polymath13]]: Intransitive dice.  Proposed Apr 28, 2017.
* [[linear norm|Polymath14]]: Classifying homogeneous norms on groups.  Initiated Dec 16, 2017; solved Dec 21, 2017. Research results have now been published.
* [[De_Bruijn-Newman constant|Polymath15]]: Upper bounding the de Bruin-Newman constant.  Proposed, Jan 24 2018; launched Jan 27 2018.
* [[Hadwiger-Nelson problem|Polymath16]]: Simplifying the lower bound proof for the Hadwiger-Nelson problem.  Proposed, Apr 10, 2018; launched, Apr 14, 2018.


[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].
== Polymath-like projects ==


A spreadsheet containing the latest lower and upper bounds for <math>c_n</math> can be found [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg here].
* 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 the [[Deolalikar P vs NP paper]].  Launched Aug 10, 2010.
* <del>[http://researchtrends.wikia.com/wiki/Main_Page Math Research Trends Wiki] "research in the middle"</del> This project is recommended to be discontinued in favor of <b>[https://conference.portonvictor.org/wiki/Research_in_the_middle Research in the middle project] at [https://conference.portonvictor.org Virtual scientific conference]</b>.
* The page for the [[ABC conjecture]] contains links and information about Mochizuki's claimed proof of this conjecture.
* A [[COVID-19 dataset clearinghouse]].
* Massively Collaborative Theoretical Computer Science Projects at [https://polytcs.wordpress.com/ The PolyTCS Project], by Rupei Xu and Chloe Yang.


== Unsolved questions ==
== Proposed polymath projects ==


'''Gowers.462:''' Incidentally, it occurs to me that we as a collective are doing what I as an individual mathematician do all the time: have an idea that leads to an interesting avenue to explore, get diverted by some temporarily more exciting idea, and forget about the first one. I think we should probably go through the various threads and collect together all the unsolved questions we can find (even if they are vague ones like, “Can an approach of the following kind work?”) and write them up in a single post. If this were a more massive collaboration, then we could work on the various questions in parallel, and update the post if they got answered, or reformulated, or if new questions arose.
* [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.


=== IP-Szemeredi (a weaker problem than DHJ) ===


'''Solymosi.2:''' In this note I will try to argue that we should consider a variant of the original problem first. If the removal technique doesn’t work here, then it won’t work in the more difficult setting. If it works, then we have a nice result! Consider the Cartesian product of an IP_d set. (An IP_d set is generated by d numbers by taking all the <math>2^d</math> possible sums. So, if the n numbers are independent then the size of the IP_d set is <math>2^d</math>. In the following statements we will suppose that our IP_d sets have size <math>2^n</math>.)
A (partial) list of proposed projects can be found [http://polymathprojects.org/category/polymath-proposals/ here].


Prove that for any <math>c>0</math> there is a <math>d</math>, such that any <math>c</math>-dense subset of the Cartesian product of an IP_d set (it is a two dimensional pointset) has a corner.
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]].


The statement is true. One can even prove that the dense subset of a Cartesian product contains a square, by using the density HJ for <math>k=4</math>. (I will sketch the simple proof later) What is promising here is that one can build a not-very-large tripartite graph where we can try to prove a removal lemma. The vertex sets are the vertical, horizontal, and slope -1 lines, having intersection with the Cartesian product. Two vertices are connected by an edge if the corresponding lines meet in a point of our <math>c</math>-dense subset. Every point defines a triangle, and if you can find another, non-degenerate, triangle then we are done. This graph is still sparse, but maybe it is well-structured for a removal lemma.
== Discussions about polymath ==


Finally, let me prove that there is square if <math>d</math> is large enough compare to <math>c</math>. Every point of the Cartesian product has two coordinates, a 0,1 sequence of length <math>d</math>. It has a one to one mapping to <math>[4]^d</math>; Given a point <math>( (x_1,…,x_d),(y_1,…,y_d) )</math> where <math>x_i,y_j</math> are 0 or 1, it maps to <math>(z_1,…,z_d)</math>, where <math>z_i=0</math> if <math>x_i=y_i=0</math>, <math>z_i=1</math> if <math>x_i=1</math> and <math>y_i=0, z_i=2</math> if <math>x_i=0</math> and <math>y_i=1</math>, and finally <math>z_i=3</math> if <math>x_i=y_i=1</math>. Any combinatorial line in <math>[4]^d</math> defines a square in the Cartesian product, so the density HJ implies the statement.
* [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://mbarany.com/publications.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.
* [http://today.uconn.edu/blog/2010/10/will-crowdsourcing-revolutionize-scholarship Will ‘Crowdsourcing’ Revolutionize Scholarship?] An article in UConn Today by Jeremy Teitelbaum, Fall 2010.
* [http://online.wsj.com/article/SB10001424052970204644504576653573191370088.html The New Einsteins Will Be Scientists Who Share] The Wall street journal, October 2011.
* [http://www.nature.com/news/parallel-lines-1.14759?WT.ec_id=NATURE-20140227 Parallel lines], editorial, Nature 506, 407–408 (27 February 2014).
Additional links are very welcome.


'''Gowers.7:'''  With reference to Jozsef’s comment, if we suppose that the <math>d</math> numbers used to generate the set are indeed independent, then it’s natural to label a typical point of the Cartesian product as <math>(\epsilon,\eta)</math>, where each of <math>\epsilon</math> and <math>\eta</math> is a 01-sequence of length <math>d</math>. Then a corner is a triple of the form <math>(\epsilon,\eta)</math>, <math>(\epsilon,\eta+\delta)</math>, <math>(\epsilon+\delta,\eta)</math>, where <math>\delta</math> is a <math>\{-1,0,1\}</math>-valued sequence of length <math>d</math> with the property that both <math>\epsilon+\delta</math> and <math>\eta+\delta</math> are 01-sequences. So the question is whether corners exist in every dense subset of the original Cartesian product.
== Other links ==


This is simpler than the density Hales-Jewett problem in at least one respect: it involves 01-sequences rather than 012-sequences. But that simplicity may be slightly misleading because we are looking for corners in the Cartesian product. A possible disadvantage is that in this formulation we lose the symmetry of the corners: the horizontal and vertical lines will intersect this set in a different way from how the lines of slope -1 do.
* [http://polymathprojects.org/ The polymath blog]
* [http://polymathprojects.org/general-polymath-rules/ General polymath rules]


I feel that this is a promising avenue to explore, but I would also like a little more justification of the suggestion that this variant is likely to be simpler.
== Note on anonymous editing ==


'''Gowers.22:''' A slight variant of the problem you propose is this. Let’s take as our ground set the set of all pairs <math>(U,V)</math> of subsets of <math>[n]</math>, and let’s take as our definition of a corner a triple of the form <math>(U,V), (U\cup D,V), (U,V\cup D)</math>, where both the unions must be disjoint unions. This is asking for more than you asked for because I insist that the difference <math>D</math> is positive, so to speak. It seems to be a nice combination of Sperner’s theorem and the usual corners result. But perhaps it would be more sensible not to insist on that positivity and instead ask for a triple of the form <math>(U,V), ((U\cup D)\setminus C,V), (U, (V\cup D)\setminus C</math>, where <math>D</math> is disjoint from both <math>U</math> and <math>V</math> and <math>C</math> is contained in both <math>U</math> and <math>V</math>. That is your original problem I think.
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 thomas@asone.ai.


I think I now understand better why your problem could be a good toy problem to look at first. Let’s quickly work out what triangle-removal statement would be needed to solve it. (You’ve already done that, so I just want to reformulate it in set-theoretic language, which I find easier to understand.) We let all of <math>X</math>, <math>Y</math> and <math>Z</math> equal the power set of <math>[n]</math>. We join <math>U\in X</math> to <math>V\in Y</math> if <math>(U,V)\in A</math>.
== Note on image uploads ==


Ah, I see now that there’s a problem with what I’m suggesting, which is that in the normal corners problem we say that <math>(x,y+d)</math> and <math>(x+d,y)</math> lie in a line because both points have the same coordinate sum. When should we say that <math>(U,V\cup D)</math> and <math>(U\cup D,V)</math> lie in a line? It looks to me as though we have to treat the sets as 01-sequences and take the sum again. So it’s not really a set-theoretic reformulation after all.
Image uploads have been disabled, as they were causing problems with spam. If you'd like to upload an image, please email thomas@asone.ai
 
 
'''O'Donnell.35:''' Just to confirm I have the question right…
 
There is a dense subset <math>A</math> of <math>\{0,1\}^n x \{0,1\}^n</math>. Is it true that it must contain three nonidentical strings <math>(x,x’), (y,y’), (z,z’)</math> such that for each <math>i = 1…n,</math> the 6 bits
 
<math>[ x_i x'_i ]</math>
 
<math>[ y_i y'_i ]</math>
 
<math>[ z_i z'_i ]</math>
 
are equal to one of the following:
 
<math>[ 0 0 ] [ 0 0 ] [ 0, 1 ] [ 1 0 ] [ 1 1 ] [ 1 1 ]</math>
 
<math>[ 0 0 ], [ 0 1 ], [ 0, 1 ], [ 1 0 ], [ 1 0 ], [ 1 1 ],</math>
 
<math>[ 0 0 ] [ 1 0 ] [ 0, 1 ] [ 1 0 ] [ 0 1 ] [ 1 1 ]</math>
 
?
 
 
'''McCutcheon.469:''' IP Roth:
 
Just to be clear on the formulation I had in mind (with apologies for the unprocessed code): for every <math>\delta>0</math> there is an <math>n</math> such that any <math>E\subset [n]^{[n]}\times [n]^{[n]}</math> having relative density at least <math>\delta</math> contains a corner of the form <math>\{a, a+(\sum_{i\in \alpha} e_i ,0),a+(0, \sum_{i\in \alpha} e_i)\}</math>. Here <math>(e_i)</math> is the coordinate basis for <math>[n]^{[n]}</math>, i.e. <math>e_i(j)=\delta_{ij}</math>.
 
Presumably, this should be (perhaps much) simpler than DHJ, <math>k=3</math>.
 
=== High-dimensional Sperner ===
 
 
'''Kalai.29:''' There is an analogous for Sperner but with high dimensional combinatorial spaces instead of "lines" but I do not remember the details (Kleitman(?) Katona(?) those are ususal suspects.)
 
=== Fourier approach ===
 
 
'''Kalai.29:''' A sort of generic attack one can try with Sperner is to look at <math>f=1_A</math> and express using the Fourier expansion of <math>f</math> the expression <math>\int f(x)f(y)1_{x<y}</math> where <math>x<y</math> is the partial order (=containment) for 0-1 vectors. Then one may hope that if <math>f</math> does not have a large Fourier coefficient then the expression above is similar to what we get when <math>A</math> is random and otherwise we can raise the density for subspaces. (OK, you can try it directly for the <math>k=3</math> density HJ problem too but Sperner would be easier;)
This is not unrealeted to the regularity philosophy.
 
 
'''Gowers.31:''' Gil, a quick remark about Fourier expansions and the <math>k=3</math> case. I want to explain why I got stuck several years ago when I was trying to develop some kind of Fourier approach. Maybe with your deep knowledge of this kind of thing you can get me unstuck again.
 
The problem was that the natural Fourier basis in <math>[3]^n</math> was the basis you get by thinking of <math>[3]^n</math> as the group <math>\mathbb{Z}_3^n</math>. And if that’s what you do, then there appear to be examples that do not behave quasirandomly, but which do not have large Fourier coefficients either. For example, suppose that <math>n</math> is a multiple of 7, and you look at the set <math>A</math> of all sequences where the numbers of 1s, 2s and 3s are all multiples of 7. If two such sequences lie in a combinatorial line, then the set of variable coordinates for that line must have cardinality that’s a multiple of 7, from which it follows that the third point automatically lies in the line. So this set <math>A</math> has too many combinatorial lines. But I’m fairly sure — perhaps you can confirm this — that <math>A</math> has no large Fourier coefficient.
 
 
You can use this idea to produce lots more examples. Obviously you can replace 7 by some other small number. But you can also pick some arbitrary subset <math>W</math> of <math>[n]</math> and just ask that the numbers of 0s, 1s and 2s inside <math>W</math> are multiples of 7.
 
=== DHJ for dense subsets of a random set ===
 
'''Tao.18:''' A sufficiently good Varnavides type theorem for DHJ may have a separate application from the one in this project, namely to obtain a “relative” DHJ for dense subsets of a sufficiently pseudorandom subset of <math>[3]^n</math>, much as I did with Ben Green for the primes (and which now has a significantly simpler proof by Gowers and by Reingold-Trevisan-Tulsiani-Vadhan). There are other obstacles though to that task (e.g. understanding the analogue of “dual functions” for Hales-Jewett), and so this is probably a bit off-topic.
 
== Bibliography ==
 
# H. Furstenberg, Y. Katznelson, “[http://math.stanford.edu/~katznel/hj43.pdf A density version of the Hales-Jewett theorem for k=3]“, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–241.
# R. McCutcheon, “[http://www.msci.memphis.edu/~randall/preprints/HJk3.pdf The conclusion of the proof of the density Hales-Jewett theorem for k=3]“, unpublished.
# H. Furstenberg, Y. Katznelson, “[http://math.stanford.edu/~katznel/dhj12.pdf A density version of the Hales-Jewett theorem]“, J. Anal. Math. 57 (1991), 64–119.
 
 
== Other resources ==
 
* [http://meta.wikimedia.org/wiki/Help:Contents Wiki user's guide]

Latest revision as of 11:25, 1 September 2020

This is the wiki for polymath projects - massively collaborative online mathematical projects. The idea of such projects originated in Tim Gowers' blog post Is massively collaborative mathematics possible?

Many polymath projects will be proposed, planned, and run at 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.

The wiki is currently locked down due to a major influx of spam (July 29, 2013). Please email thomas@asone.ai if you'd like an account set up, and I'll do my best to reply quickly.

Existing polymath projects

  • Polymath1: New proofs and bounds for the density Hales-Jewett theorem. Initiated Feb 1, 2009; research results have now been published.
  • Polymath2: Must an “explicitly defined” Banach space contain [math]\displaystyle{ c_0 }[/math] or [math]\displaystyle{ l_p }[/math]? Initiated Feb 17, 2009; attempts to relaunch via wiki, June 9 2010.
  • Mini-polymath1: Solving Problem 6 of the 2009 International Mathematical Olympiad. Initiated July 20, 2009; five proofs obtained so far.
  • Polymath3. The polynomial Hirsch conjecture. Proposed July 17, 2009; launched, September 30, 2010.
  • Polymath4: A deterministic way to find primes. Proposed July 27, 2009; launched Aug 9, 2009. Research results have now been published.
  • Polymath5: The Erdős discrepancy problem. Proposed Jan 10, 2010; launched Jan 19, 2010. Activity ceased by the end of 2012, but results from the project were used to solve the problem in 2015.
  • Mini-polymath2: Solving Problem 5 the 2010 International Mathematical Olympiad. Proposed Jun 12, 2010; launched and solved, Jul 8 2010.
  • Polymath6: Improving the bounds for Roth's theorem. Proposed Feb 5, 2011.
  • Mini-polymath3: Solving a problem from the 2011 International Mathematical Olympiad. Proposed Jun 9, 2011; launched and solved, Jul 19, 2011.
  • Mini-polymath4: Solving a problem from the 2012 International Mathematical Olympiad. Proposed, Jun 3, 2012; launched, July 12 2012.
  • Polymath7: Establishing the Hot Spots conjecture for acute-angled triangles. Proposed, May 31st, 2012; launched, Jun 8, 2012.
  • Polymath8: Improving the bounds for small gaps between primes. Proposed, June 4, 2013; launched, June 4, 2013. Research results have now been published.
  • Polymath9: exploring Borel determinacy-based methods for giving complexity bounds. Proposed, Oct 24, 2013; launched, Nov 3, 2013.
  • Polymath10: improving the bounds for the Erdos-Rado sunflower lemma. Launched, Nov 2, 2015.
  • Polymath11: proving Frankl's union-closed conjecture. Proposed Jan 21, 2016; launched Jan 29, 2016. Concluded, Jan 17, 2017.
  • Polymath12: proving Rota's conjecture. Proposed Feb 28, 2017.
  • Polymath13: Intransitive dice. Proposed Apr 28, 2017.
  • Polymath14: Classifying homogeneous norms on groups. Initiated Dec 16, 2017; solved Dec 21, 2017. Research results have now been published.
  • Polymath15: Upper bounding the de Bruin-Newman constant. Proposed, Jan 24 2018; launched Jan 27 2018.
  • Polymath16: Simplifying the lower bound proof for the Hadwiger-Nelson problem. Proposed, Apr 10, 2018; launched, Apr 14, 2018.

Polymath-like projects

Proposed polymath projects


A (partial) list of proposed projects can be found 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 here.

Discussions about polymath

Additional links are very welcome.

Other links

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 thomas@asone.ai.

Note on image uploads

Image uploads have been disabled, as they were causing problems with spam. If you'd like to upload an image, please email thomas@asone.ai

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Main_Page&oldid=11188"