Possible future Polymath projects (2009, 2021)

What will be our next polymath project?

A polymath project (Wikipedia) is a collaboration among mathematicians to solve important and difficult mathematical problems by coordinating many mathematicians to communicate with each other on finding the best route to the solution. The project began in January 2009 on Timothy Gowers’s blog when he posted a problem and asked his readers to post partial ideas and partial progress toward a solution. This experiment resulted in a new answer to a difficult problem, and since then the Polymath Project has grown to describe a particular process of using an online collaboration to solve any math problem.

After the success of Polymath1 and the launching of Polymath3 and Polymath4, Tim Gowers wrote a blog post “Possible future Polymath projects” for planning the next polymath project on his blog. The post mentioned 9 possible projects. (Three of them later turned  to polymath projects, and one turned into a project of a different nature.) Following the post and separate posts describing some of the proposed projects, a few polls were taken and a problem – the Erdős discrepancy problem, was selected for the next project polymath5. 

One of our next posts will have the same title and similar purpose as Tim’s 2009 post.  I will describe several possibilities for my next polymath project. (A quick rather vague and tentative preview can be found at the end of this post.) Today we go back to Tim’s 2009 post and the problems posed there.

Comments on the 2009 proposed projects, the new proposed projects, other proposed projects, and on the polymath endeavor, are most welcome. (At the end of the post I also mention a few “meta” questions.)

Let me also mention The PolyTCS Project aimed for proposing projects in theoretical computer science. There are so far three very interesting proposals there, and the first proposal is the Friedgut-Kalai Entropy/Influence conjecture. For various proposals, see also the polymath blog administered by Tim Gowers, Michael Nielsen, Terry Tao, and me, and this MO question.

The proposed projects in Gowers’s 2009 post and updates regarding these projects.

1. Littlewood’s conjecture and related problems.

The conjecture states that if \alpha and \beta are any two real numbers, and \epsilon>0, then there exists a positive integer n such that ||\alpha n||\,||\beta n||\leq\epsilon/n. Famously, Einsiedler, Katok and Lindenstrauss proved that the Hausdorff dimension of the set of counterexamples to the conjecture is zero. Gowers had ideas for an elementary approach, and his ideas  are described in this later post. This project was not launched and I am also not aware of progress related to the problem (but I am not an expert). 

2. A DHJ-related project.

DHJ stands for “density Hales Jewett” which was the topic of polymath1. The second proposed project was to build on the success of polymath1 and at a later post the following problem was proposed.

Conjecture:  For every \delta>0 and every positive integer k there exists n such that if A is any subset of [k]^{[n]^2} of density at least \delta, then A contains a combinatorial line such that the wildcard set is of the form X\times X for some subset X\subset[n].

As far as I know, this conjecture is still open.

Both questions “what kind of forbidden patters in [k]^n force exponentially small density” and “what kind of forbidden patters in [k]^n force vanishing density” are fascinating. Let me recommend again the Frankl-Rodl theorem and its proof as a role model.

3. Four Erdős-style combinatorial problems.

3a. Erdős’s discrepancy problem

This was the problem that was eventually chosen for polymath5. This was a very nice story. The problem was presented in this blog post and selected as polymath5 after some polls among readers. The polymath project was the longest in polymath history. There were six preliminary discussion posts with more than 600 comments followed by 21 official posts EDP1-EDP21. There was some short revival of the project (EDP22-EDP27) in 2012 where I contributed three posts. Famously, in 2015 Terry Tao solved the problem. The paper appeared in the journal Discrete Analysis. Tao’s solution relies on some insights from the polymath project including a crucial reduction that Terry himself contributed. It also crucially relied on a (then) new theory by Kaisa Matomaki and Maksym Radziwill. The solution was triggered  by a blog comment by Uwe Stroinski who pointed to a possible connection to EDP, and a subsequent one by Kodlu who seconded Uwe’s suggestion. This is reported in EDP28, and here on my blog we celebrated the solution in this post.  

3b. The Erdős-Hajnal conjecture.

Let k be a positive integer and let H be a graph. Erdös and Hajnal conjectured that there is a constant C=C(H) such that if G is any graph with at least k^C vertices that does not contain any induced copy of H, then either G or G^c contain a clique of size k.

Tim asserted that the simplest open case is where H is a pentagon. This special case was recently settled by Maria Chudnovsky, Alex Scott, Paul Seymour and Sophie Spirkl. They rely on recent results by Janos Pach and Istvan Tomon. See this videotaped lecture by Paul Seymour at IBS Discrete Mathematics Group, South Korea.

3c. Frankl’s union-closed conjecture.

Let \mathcal{A} be a collection of sets that is closed under taking unions. Must there be an element that is contained in at least half the sets?

Tim wrote: This is a notorious question, and possibly the least likely to yield to a Polymath approach (it feels as though there might be a burst of ideas, none of which would work, followed by disillusionment, or else, if we were very lucky, a single bright idea from one person that essentially solved the problem, but I could be wrong).

Polymath11 on Tim Gowers’s blog (Launched January, 2016) was devoted to Frankl’s conjecture. The problem is still open.

3d. The delta-systems problem.

This question is due to Erdős and Rado. A delta system is a collection of sets A_1,\dots,A_m such that all the sets A_i\cap A_j (with i\ne j) are equal. Equivalently, there exists some set X such that X\subset A_i for every i, and the sets A_i\setminus X are disjoint.

Erdös offered 1000 dollars for a solution to the following problem: does there exist a constant C such that for every k and every system of at least C^k sets of size k, there must exist three of them that form a delta system?

I devoted polymath10 to this problem. I tried to promote certain  homological approach. This has not led to progress but did lead to some interesting observations on the problem and also some refinement and better understanding of my approach.

While still open since 2009, there were major breakthroughs regarding the problem that we described here and here, most notably the problem was nearly solved by Ryan Alweiss, Shachar Lovett, Kewen Wu,  and Jiapeng Zhang.

4. Non-mathematical projects.

4a. Developing a new type of chess-playing program.

The precise formulation was: “how good a chess-playing program is possible if the amount of memory space allowed is very restricted, and the amount of calculation is also limited?” In a comment, Tim explained that one would like to find a method of programming that applied to all games of a certain type (things like Othello, Go, etc.) and not just chess. And this could be taken as the aim. 

One comment mentioned the then very recent computer programs for playing Go (based on machine learning). Let me mention that deep learning led to a revolution in this area around 2015.  (And also that we had a guest post by Amir Ban on chess playing computer programs.)

4b. The origin of life.

This rather tentative suggestion, was to try to come up with a model that would show convincingly how life could emerge from non-life by purely naturalistic processes. It was further discussed in this post. There was a lot of excitement around it but it did not lead to a polymath project, and I am not sure about related progress after 2009.

As an aside let me mention that Aubrey de Gray, who famously improved the lower bound on the chromatic number of the plane (that led to polymath16), is very famous for his works and ideas on aging. I suggested to Aubrey, that he should have a “polymath style” project on the issue of aging and his approach to the problem. However Aubrey’s response was that  various attempts to do things like that have failed over the years, across many biological fields. 

5. A tentative approach to complexity lower bounds.

This turned into a series of posts (first one here, whole “complexity category” here) where Tim tried to develop several ideas related to the NP \ne P problem.

________

OK, let me now briefly and tentatively preview some suggestions for my future polymath project. 

Possible future Polymath projects (2021)  

1. The  3ᵈ conjecture and the flag conjecture for centrally symmetric polytopes

2. Mathematical questions regarding social welfare functions.  Here is a  related 2009 post and a survey by Elchanan Mossel.

3. Developing a theory polymath-style

Can a polymath project be used to develop a theory rather than solving a problem? This question was raised by Peter Sarnak in a 2010 IAS debate about polymath projects.

3.a A theory of convex hulls of real algebraic varieties.  One project in this spirit that I already proposed is to try to develop polymathly a theory of convex hulls of real algebraic varieties.

3.b  Extending algebraic shifting to a wide variety of combinatorial structures. This is a project with Hélène Barcelo from the mid 90s that at the time did not get off the ground and it could be very nice to explore it collectively.

What  other theories would you like to see developed openly and collectively?*

4. Touching non overlapping simplices – the 2ᵈ-conjecture.

5.  Erdős-style combinatorial problems. Two possibilities are

5.a Simonyi’s conjecture; and  5.b Chvatal’s conjecture.

Both can be found at the end of this post. More links, SC1, SC2, CC1, CC2

6. Enumeration – weights to the rescue  (sorry for being vague)

7. Mathematics with computers (this is even more vague for now; but see this MO question;   Here I am thinking about an experimental project. Most of the other projects may have large ingredients of computer experimentation.)

8. Is there a statistical methodology for detecting biased data selection and related statistical follies.   See this post and Maya Bar Hillel’s slides, and also this post by Omer Reingold on Windows in Theory. 

9. A problem posed by Oded Schramm: Is there some \epsilon >0 so that for every n>1 there exist a set K_n of constant width 1 in dimension n whose volume satisfies VOL(K_n) \le (1-\epsilon)^n V_n. (V_n is the volume of the n-dimensional ball of width one.) See this MO question.

Meta questions

There are many meta questions regarding polymath projects: 

  1. One important one is: What is the ideal platform for a polymath project?
  2. Could a polymath project be moderated by a computer?
  3.  What are the potential of polymath projects? The limitations? Are polymath projects a good way to do mathematics.
  4. What are the incentives to participate?
  5. Are polymath projects inviting in terms of diversity of participants?  

* I wonder if a question “What mathematical theory would you like to see developed” on Math Overflow could stay alive and whether it may lead to nice responses. (There was a nice question about what book would you like to see written.

 

 

This entry was posted in Combinatorics, Mathematics over the Internet, Open discussion and tagged , , . Bookmark the permalink.

23 Responses to Possible future Polymath projects (2009, 2021)

  1. ryeguy10 says:

    I wouldn’t quite say that we have “nearly solved” the sunflower problem…

    • Gil Kalai says:

      Dear Ryeguy10, well, since I thought about the problem since 1978 and followed the progress carefully, I think I have some justification (or at least mitigating circumstances) for saying “nearly solved.” But this will not reduce my excitement from a complete solution or even further progress in the future.

  2. moderator says:

    The Open Problems in Algebraic Combinatorics blog (https://realopacblog.wordpress.com/) has several problems which are of an elementary nature that might be amenable to polymath-style collaboration.

  3. The graph theory problem described by Dustin Mixon (https://dustingmixon.wordpress.com/2021/01/18/a-graph-coloring-problem-from-quantum-physics-with-prizes/) is just a few years old, but it’s solution could have quite useful applications in quantum physics.

    I worked on this question for some time, and talked to a number of graph theoretists, but no connections to literature came up yet. Thus a more explorative, crowd-sources approach could find some initial paths.

      • Thanks. I would be very curious whether you think that this problem actually hits the characteristics that make a successful polymath problem. It seems so far, polymath projects were successful when they dealed with high-profile questions. This is more a sociological rather than mathematical reason, but it makes sense as high-profile questions would attract more attendances. I would love reading your thoughts on the sociological factor behind chosing polymath projects.

  4. Philip Gibbs says:

    What if there was a polymath blog or other website where all of these problems and more were posted simultaneously in different posts and anyone can start working on them in the comments? Why do we need to focus on just one at a time when there are so many good ideas? Isn’t it true that different people work on different problems anyway?

    • Gil Kalai says:

      Dear Phillip, I think that it is still a good idea (like in 2009) to have preliminary discussions on a larger number of proposals and later to concentrate on fewer. However, I like the idea of having several projects in parallel.

    • Thomas Vu says:

      Dear Philip, I actually created such a platform already!

      It’s called AsOne and we are currently the website which is hosting the Polymath Wiki.
      AsOne is best summarized as a “Reddit for polymath projects”, where the subreddits are individual open problems which can be worked on in parallel.

      https://asone.ai
      https://asone.ai/polymath/index.php?title=Main_Page

      • Gil Kalai says:

        AsOne is indeed a very interesting platform to consider. Maybe we can have also as part of a polymath project also “real” zoom meetings or meetings of similar kinds.

      • Thomas Vu says:

        Thank you for considering us, Gil!

        We started AsOne with the goal of building a custom platform optimized for massively collaborative research, and we are dedicated to continuously improving the platform so that future Polymath projects will be bigger and more successful than the projects that came before!

        Let me know at thomas@asone.ai if you have any plans for a potential Polymath17 now that Polymath16 is winding down and the paper is being written. Cheers!

      • Philip Gibbs says:

        Brilliant. I will definitely take a look at that.

  5. https://mathoverflow.net/questions/325477/resolution-of-multiple-edges
    I think this can be on the list of problems. This problem if true has a nice consequence as explained by prof. Fedor Petrov in the post.

      • I was once working on the problem with prof. Petrov but we couldn’t solve it entirely. We tried to interpret the problem in the language of matrices. So, we consider a matrix whose (i,j)th entry is the number of balls of colour j received by girl i. Then, we want to reach the matrix of all ones, by adding a sequence of trade matrices (which are matrices with exactly two entries equal to one and 2 entries equal to -1 and each row sum and each column sum =0), such that no two of these trade matrices have 1 in a common location (so that no girl receives more than one ball of the same colour during the exchange process). We wanted to approach the problem probabilistically trying to show that a random chosen sum of trade matrices which take us to the matrix of all ones’ satisfies this additional property with a positive probability.

        The problem remains unsolved.

  6. Pingback: To cheer you up in difficult times 19: Nati Linial and Adi Shraibman construct larger corner-free sets from better numbers-on-the-forehead protocols | Combinatorics and more

  7. Pingback: To cheer you up in difficult times 20: Ben Green presents super-polynomial lower bounds for off-diagonal van der Waerden numbers W(3,k) | Combinatorics and more

  8. Pingback: Polymath projects 2021 | The polymath blog

  9. Pingback: 55 Best Computer Science Blogs (+ Example Articles)

  10. >Can a polymath project be used to develop a theory rather than solving a problem?

    For what it’s worth, the n-Category café/nLab/nForum ecosystem has functioned somewhat like this, though clearly with one main contributor with a number of smaller contributions, though the collaborative nature of this has dropped a little of late, due to people focusing their efforts in different ways.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s