Possible future Polymath projects (2009, 2021)

Combinatorics and more 2021-01-29

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:

One important one is: What is the ideal platform for a polymath project?
Could a polymath project be moderated by a computer?
What are the potential of polymath projects? The limitations? Are polymath projects a good way to do mathematics.
What are the incentives to participate?
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.)