Proposals for polymath projects

Question

Background

Polymath projects are a form of open Internet collaboration aimed towards a major mathematical goal, usually to settle a major mathematical problem. This is a concept introduced in 2009 by Tim Gowers and is in line with other forms of Internet mathematical research activity which include MathOverflow.

Former and current projects

The polymath wiki page gives a description and links to former polymath projects and much additional information. So far, there were about 10 polymath projects of which 6-7 led to intensive research, and among those 3-4 were successful. (There were several MathOverflow questions motivated by running polymath projects, especially questions related to polymath5.) Those projects ran over Gowers's blog (polymath1, polymath5 and others), Tao's blog (polymath8), the Polymath Blog (administered by Tao, Gowers, Nielsen, and me) (polymath4 and polymath7), and my blog (polymath3).

Updates (Before Nov 2016) There were a couple of additional polymath-type projects. (Nov '15, 2016) Currently, polymath10 on Erdős-Rado delta system conjecture is running on my blog.(New, Dec 29, '15) Terry Tao posted (on behalf of Dinesh Thakur) an interesting proposal for a polymath project regarding identities for irreducible polynomials Update: problem solved by David Speyer. ( January 31, 2016) Tim Gowers launched on his blog polymath11 on Frankl's union-closed conjecture.

Updates (Before January 2018) : Timothy Chow launched polymath12 on Rota's basis conjecture (February 24, 2017). (It was proposed as an answer to this question here.) (May 14, 2017) Tim Gowers is running a polymath-like project polymath13 on "Intransitive dices". (Dec 24 2017) A spontaneous polymath project, polymath14, over Tao's blog: A problem was posed by Apoorva Khare was presented and discussed and openly and collectively solved. (And the paper arxived.)

Update (January 25,2018) A new polymath project is emerging on Tao's blog: Polymath proposal: upper bounding the de Bruijn-Newman constant. Update: This is polymath15 which seems very active and quite successful. (wikipage)

Updates (April 14, 2018, June, 2019) Dustin Mixon and Aubrey de Grey have launched Polymath16 over at Dustin’s blog. The project is devoted to the chromatic number of the plane (Wikipage) following Aubrey de Grey's example showing that the chromatic number of the plane is at least 5. See also a proposal post and discussion thread over the polymath blog, and a proposal over here. Polymath 16 was now concluded.

Update, June 2019 Terry Tao initiated a sort of polymath attempt to solve the following problem conditioned on some conjectures from arithmetic algebraic geometry: Is there any polynomials $P$ of two variables with rational coefficients, such that the map $ P: \mathbb Q \times \mathbb Q \to \mathbb Q$ is a bijection? This is a famous 9-years old open question on MathOverflow.

Update, March 2020: On Terry Tao's blog, Polymath proposal: clearinghouse for crowdsourcing COVID-19 data and data cleaning requests. The proposal is to: (a) a collection of public data sets relating to the COVID-19 pandemic, (b) requests for such data sets, (c) requests for data cleaning of such sets, and (d) submissions of cleaned data sets. (Proposed by Chris Strohmeier after discussions among several mathematicians.)

Update (January 12, 2021) A polyTCS blog-based project was launched a year ago by Rupei Xu and Chloe Yang. It contains several interesting proposals.

Former proposals for future projects

There were also 10-20 additional serious proposals. A few proposals of various nature (from which polymath5 was selected) are gathered in this post on Gowers's blog, and several that appeared on various places are summarized on the polymath Wiki and also on the polymath blog. The polymath projects so far consisted of an attempt to solve a specific open problem but some of the proposals were of different nature.

More background

So far, polymath projects, while getting considerable attention and drawing enthusiasm, (and some controversy,) were limited in scope within mathematics and among mathematicians.

In most cases a small team of participants were the devoted contributed and in some cases those devoted participants were experts in the relevant area. Thus projects may apply primarily to experts in a specific field of mathematics. In all existing examples the project itself had some general appeal.

For a polymath project, in addition to the main task of trying to reach or at least greatly advance the goals of the specific project there are secondary goals of trying to understand the advantages and limitation of the polymath concept itself, and of trying to openly record the thought process of different participants towards the specific goal.

The question

The question is simple:

Make additional proposals for polymath projects.

Summary of proposals (updated: January 12, 2021)

1. The LogRank conjecture. Proposed by Arul.

2. The circulant Hadamard matrix conjecture. Proposed by Richard Stanley.

3. Finding combinatorial models for the Kronecker coefficients. Proposed by Per Alexandersson.

4. Eight lonely runners. Proposed by Mark Lewko.

5. A problem by Ruzsa: Finding the slowest possible exponential growth rate of a mapping $f:N→Z$ that is not a polynomial and yet shares with (integer) polynomials the congruence-preserving property $n−m∣f(n)−f(m)$. Proposed by Vesselin Dimitrov.

6. Finding the Matrix Multiplication Exponent ω. (Running time of best algorithm for matrix multiplication.) Proposed by Ryan O'Donnell.

7. The Moser Worm problem and Bellman's Lost in a forest problem. Proposed by Philip Gibbs.

8. Rational Simplex Conjecture ( by Cheeger and Simons). Proposed by Sasha Kolpakov.

9. Proving that for every integer $m$ with $|m| \le c(\sqrt{n}/2)^n$ there is an $n \times n$ 0-1 matrix matrix whose determinant equals $m$. Proposed by Gerhard Paseman.

10. Proving or disproving that the Euler's constant is irrational. Proposed by Sylvain JULIEN.

11. The Greedy Superstring Conjecture. Proposed by Laszlo Kozma.

12. Understanding the behavior and structure of covering arrays. Proposed by Ryan.

13. The group isomorphism problem, proposed by Arul based on an early proposal by Lipton.

14. Frankl's union closed set conjecture (Proposed by Dominic van der Zypen; Also one of the proposals by Gowers in this post). (Launched)

15. Komlos's conjecture in Discrepancy Theory. Proposed by Arul.

16. Rota's Basis Conjecture. Proposed by Timothy Chow. Launched on the polymath blog.

17. To show that $2^n+5$ composite for almost all positive integers $n$. (Might be too hard.) Proposed by me.

18. To prove a remarkable combinatorial identity on certain Permanents. Proposed by me. Update, Aug 6, 2016: settled!

19. Real world applications of large cardinals Proposed by Joseph van Name. There were a few more proposals in comments.

20. A project around a cluster of tiling problems. In particular: Is the Heech number bounded for polygonal monotiles? Is it decidable to determine if a single given polygonal tile can tile the plane monohedrally? Even for a single polyomino? Proposed by Joseph O'Rourke

21. To prove that $\sum \frac{\sin (2^n)}{n}$ is a convergent series. Proposed by JAck D'aurizio

22. The Nakayama conjecture and the finitistic dimension conjecture (major problems from the intersection of representation theory of finite dimensional algebras) and homological algebra. Proposed by Mare.

23. Major questions in the field of stereotype spaces and their applications, proposed by Sergei Akbarov.

24. The Erdos-Straus conjecture, proposed by Amit Maurya

25. The Collatz conjecture, proposed by Amit Maurya.

26. Indecomposability of image transformations, proposed by Włodzimierz Holsztyński

27. Is there a degree seven polynomial with integer coefficients such that (1) all of its roots are distinct integers, and (2) all of its derivative's roots are integers?, Proposed by Benjamin Dickman.

28. The Cartan determinant conjecture for quiver algebras, proposed by Mare.

29. The number of limit cycles of a polynomial vector field, Proposed by Ali Taghavi.

30. Small unit-distance graphs with chromatic number 5, proposed by Noam Elkies. Became Polymath16, see above.

31. (new) Lower bounds for average kissing numbers of non-overlapping spheres of different radii Proposed by Sasha Kolkapov.

32. (new) A uniformly distributed random variable decomposition conjecture proposed by Sil.

33. (new) The 3ᵈ conjecture and the flag-number conjecture proposed by me.

Proposed rules (shortened):

1. All areas of mathematics including applied mathematics are welcome.

2. Please do explain what the project is explicitly and in some details (not just link to a paper/wilipedea). Even if the project appeals to experts try to give a few sentences for a wide audience.

3. Please offer projects that you genuinely think to be potentially suitable for a polymath project.

(Added) Criteria that were proposed for a polymath project.

Joel David Hamkins asked for some criteria that have been proposed for what kind of problem would make a good polymath project?

I don't think we have a clear picture on criteria for good polymath projects and there could be good projects of various kind. But the criteria for the first project are described by Gowers (I modified the wording to make them not specific in one sentence), and they seem like good criteria for a first project in a new field be it algebraic geometry, algebraic topology, group theory, logic, or set theory (to mention a few popular MO tags).

" I wanted to choose a genuine research problem in my own area of mathematics, rather than something with a completely elementary statement or, say, a recreational problem, just to show that I mean this as a serious attempt to do real mathematics and not just an amusing way of looking at things I don’t really care about. This means that in order to have a reasonable chance of making a substantial contribution, you probably have to be a fairly experienced [researcher in the field of research]. So I’m not expecting a collaboration between thousands of people, but I can think of far more than three people who are suitably qualified.

Other criteria were that I didn’t want to choose a famous unsolved problem, or a problem where I had no idea whatever where to start. For a first attempt, it seemed a better idea to choose a problem that I’d love to solve, about which I already have some ideas, but in which I don’t (yet) have a significant emotional investment.

Does the problem split naturally into subtasks? That is, is it parallelizable? I’m actually not completely sure that that’s what I’m aiming for. ... I’m interested in the question of whether it is possible for lots of people to solve one single problem rather than lots of people to solve one problem each.

However, my contention would be that any reasonably complex solution to a problem is somewhat parallelizable and becomes increasingly so as one thinks about it."

Answer 1

Could You consider the conjecture as follows to make additional proposals for polymath project?

Let $A, B, C$ be three positive integer numbers such that $A+B=C$ with $\gcd(A, B, C) = 1$. By Fundamental theorem of arithmetic we write:

$A=a_1^{x_1}a_2^{x_2}...a_n^{x_n}$,

$B=b_1^{y_1}b_2^{y_2}...b_m^{y_m}$,

$C=c_1^{z_1}c_2^{z_2}...c_k^{z_k}$

Let $d=\min\{x_i, y_j, z_h \}$ where $1 \le i \le n, 1\ \le j \le m, 1\le h \le k$ then:

My conjecture: $$d \le 5$$

The conjecture in here

PS: I researched about one hundred papers, in any case $h \le 3$?

Answer 2

All trees are graceful, probably

A graceful labelling of a (finite) tree with $n$ vertices is a bijection from $\{1,2,\ldots,n\}$ to the vertices of the tree such that each of the numbers in $\{1,2,\ldots,n-1\}$ is the absolute difference of the labels at the ends of some edge.

For example, the path with 5 vertices has graceful labelling 2,5,1,3,4 as the weights of the edges are respectively 3,4,2,1.

It was conjectured long ago (by Alex Rosa?) that every tree has a graceful labelling, but this is still open. There is proof by computer up to something like 30 or 40 vertices, and tons of partial results.

A less known problem concerns the graceful labellings of a path, which are called graceful permutations (see A006967). The number of them grows quickly but nobody knows how quickly. Nor, as far as I know, is there any recurrence or generating function known.

Answer 3

Consider a probabilistic graph $G = (V, E)$ where each edge operates (exists) with probability $p$, independent of other edges. We consider a set $S \subseteq E$ to be a state of $G$. We say that $S$ occurs when each edge of $S$ operates, and all other edges fail (i.e., in $E \setminus S$). Define $\phi(S)$ to be 1 if $S$ operates, and 0 otherwise. We want to know: what is the probability that $G$ is in an operating state, under $\phi$?

The reliability polynomial is $\text{Rel}_\phi(G; p) = \sum_{S \subseteq E} \Pr[S\;\text{is operating}]\phi(S)$. What is interesting is calculating the coefficients of this polynomial.

Due to Valiant, in general this task is $\mathcal{\#P}$-complete. However, several classes of graphs are known to have this task be poly-time computable, such as cycles, series-parallel graphs, etc.

Say that $\phi$ is coherent when if $S \subseteq T$, $\phi(S) \le \phi(T)$. Define $F_\phi = \{S \colon S \subseteq E, \phi(E\setminus S) = 1\}$, and $F_i = \{F \in F_\phi \colon |F| = i\}$. This is called the $F$-form of the reliability polynomial. Therefore, we can rewrite the polynomial as: $\text{Rel}_\phi(G;p) = \sum_{i=0}^m F_i(1-p)^ip^{m-i}$.

What is known about $F$-forms? Suppose $|V| = n, |E| = m$. $F_i = 0$ for $i > n-m+1$, and if the smallest edge cutset has size $c$, $F_i = {m \choose i}$ for $i < c$. For any $k$, calculating $F_{c+k}$ runs in time exponential in $k$. By the Kirchoff Matrix Tree Theorem, $F_{m-n+1}$ is the number of spanning trees in the graph, which is poly-time computable. Once new coefficients are known, the bounds on the remaining ones become tighter.

Open questions:

1. Can we compute the number of spanning connected subgraphs with exactly 1 cycle in poly-time? This can be done for planar graphs. (this would be the coefficient $F_{m-n}$).
2. What is the complexity of the decision problem $\{<G, H>\;\vert\;\text{Rel}(G; p) \ge \text{Rel}(H; p)\;\text{for all $0 \le p \le 1$}\}$? It doesn't even appear to be in $\mathcal{NP}$.
3. Cycles are poly-time computable; what about $k$-regular graphs for $k \ge 3$?

Answer 4

Finding lower bounds on the average kissing number of spheres in higher dimensions.

This problem is not famous, but can be nevertheless fun (and it seems important enough and hard enough to warrant its place here, since possible approaches to it may include classical geometry, linear programming, semidefinite programming, lattice theory, among others).

Let $S$ be a set of spheres in $\mathbb{R}^n$, with non-intersecting interiors and arbitrary positive radii. The contact graph of $S$ has spheres as vertices, and an edge whenever two spheres are tangent. The average kissing number $k_a(S)$ of $S$ is then $\frac{2 E}{V}$, where $E$ is the number of edges and $V$ the number of vertices in the contact graph of $S$. Now, $k_a(n) = \sup_{S} k_a(S)$ is the average kissing number in $\mathbb{R}^n$, where the supremum is over all finite kissing configurations of spheres $S$ as described above.

Recently, some work has been done on the upper bounds for average kissing numbers (https://arxiv.org/abs/2003.11832), and before that there were these two beautiful papers (https://arxiv.org/abs/math/9405218 and https://arxiv.org/abs/math/0204007) that gave a very good lower bound on $k_a(3)$.

However, due to the lack of good regular polytopes in higher dimensions (and the lack of knowledge about hyperbolic polytopes in higher dimensions in general), some other methods (apparently) should be employed.

A randomised approach may not bring much success, since random configurations tend to be "not very dense" (see Average degree of contact graph for balls in a box).

Answer 5

I do not know if the problem has been posed or solved before, but I would like to launch a Polymath project about proving that $$ a_n=(1-\frac12)^{(\frac12-\frac13)^{...^{(\frac{1}{n}-\frac{1}{n+1})}}} $$ is a convergent sequence which it is assigned the two following sequences in OEIS odd sequences and even sequence. A quite detailed description of some attempts can be found on MSE.

Answer 6

Like Erdos-Straus conjecture, another result, which is very simple to state and understand and yet a proof remains elusive, is the Collatz conjecture.

If the function $f(n)$ is applied recursively enough number of times on any positive integer $n$, then unity will always be reached. \begin{align*} f(n) &= \left\{ \begin{array}{ll} n/2 &\text{if }n \bmod2=0 \\ 3n+1 &\text{if }n \bmod2=1 \end{array} \right.\\ \strut\\ \end{align*}

Some mathematicians have commented on the difficulty level of this problem, which makes it more worthy of collaborative effort.

Paul Erdős said about the Collatz conjecture: "Mathematics may not be ready for such problems."[8] He also offered $500 for its solution.[9] Jeffrey Lagarias in 2010 claimed that based only on known information about this problem, "this is an extraordinarily difficult problem, completely out of reach of present day mathematics." -Source

I believe this contribution might fulfil the comment below

http://idrissaberkane.org/wp-content/uploads/2017/08/Aberkane_Syracuse_2017.pdf