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.

30 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.

  11. Pingback: To cheer you up in difficult times 25: some mathematical news! (Part 2) | Combinatorics and more

  12. dsp says:

    I don’t know if anyone will read this comment on a thread long gone dormant, but can I just throw in my hat here for a polymath project on the 3^d conjecture?

    I think I may have a neat idea how to prove the conjecture based on induction and McMullen’s concept of sweeping a hyperplane through a polytope. All that really remains to be done is to make everything rigorous. The idea goes like this: Suppose we have a d-dimensional centrally symmetric polytope P centered at the origin in \mathbb{R}^d. Take a sufficiently generic hyperplane H containing the origin (defined, say, by c(\mathbf{x}) = 0 for a linear functional c.) Consider first the intersection H \cap P. This is a d-1-dimensional centrally symmetric polytope, so by the induction assumption, it has at least 3^{d-1} nonempty faces. Call this polytope P_0. Now imagine that we have two copies of H sweeping through the polytope at the same speed in opposite directions, and consider the slice of the polytope between them. This means that we consider the intersection P_\epsilon of P with the two halfspaces defined by c(\mathbf{x}) \leq \epsilon and c(\mathbf{x}) \geq -\epsilon for some \epsilon. For each \epsilon, this intersection is a centrally symmetric polytope, and the combinatorial type of this polytope changes only when the hyperplanes pass through vertices of P (the points at which McMullen’s “flips” occur). Now it seems obvious to me (and this is the point which needs to be made rigorous!) that when \epsilon is sufficiently close to zero, P_\epsilon is combinatorially isomorphic to I \times P_0 — the direct product of P_0 with a line segment, and hence its number of nonempty faces is at least the number of nonempty faces of a line segment times the number of nonempty faces of P_0, which is at least 3 \cdot 3^{d-1} = 3^d (recall the induction assumption!) Furthermore, it is not difficult to see that when the hyperplanes pass a vertex (when a flip occurs), the number of faces of P_\epsilon cannot decrease, which proves the conjecture.

    • Thomas Vu says:

      Hi, dsp! As the current admin for the Polymath Wiki, I’m always keeping an eye on anything Polymath Project-related!

      I’m eager to support anyone who is interested in starting new polymath projects. If you want to share your ideas and progress in a dedicated page for the $3^d$ conjecture, I created one here: https://asone.ai/a/3dconjecture (I created this website to help make it easy for anyone to start a polymath-style project)

      Alternatively, if you wish to create a page on the Polymath Wiki and don’t currently have an account, email me at thomas@asone.ai and I can help set one up for you!

    • Gil Kalai says:

      Thanks dsp! One things that worries me is that usually (say when you start with the cube) the intersection you start with will have strictly more than 3^{d-1} facets. So one needs to check if we don’t get a result which is too strong.

      • dsp says:

        After some more thought, this “proof idea” turns out to be pretty silly anyway, because it just is completely wrong that the flips can never decrease the number of faces. Furthermore, I just realized that if a proof along these lines worked, it would also work for arbitrary (not necessarily centrally symmetric) polytopes. So in the end, nothing fits together.

  13. dsp says:

    For what it‘s worth, here is a possible approach to another of your tentative future polymath problems that I‘ve been thinking about for years without being able to make it work, but which still seems very tempting to me: Let D be a downset on the ground set/universe U. Then I can show by Mobius inversion that Chvatal‘s conjecture holds for D whenever there is an i in U such that |f^{\hat}(\{i\})| \leq |f^{\hat}(U)|, where f is the indicator function of D and f^{\hat}(X) denotes the Boolean Fourier coefficient corresponding to latex X \subseteq U$. Is this relation too good to be true, or might it be worth exploring?

    • dsp says:

      Sorry for the latex errors. The proposed relation which implies Chvatal‘s conjecture is |\hat{f}(\{i\})| \leq |\hat{f}(U)| (i. e., at least one level-one Fourier coefficient is bounded above by the top Fourier coefficient).

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