# Proposals for polymath projects

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

### 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: September 24, 2017)

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.

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

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) (New) Indecomposability of image transformations, proposed by Włodzimierz Holsztyński

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

29) (New) 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.

### 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."

• I'm noticing a large matricial aspect to the proposals. Gerhard "Glad I Proposed Mine Early" Paseman, 2015.09.30 – Gerhard Paseman Sep 30 '15 at 16:32
• I don't have the freedom to write a careful proposal at the moment, but I believe a project could built 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? – Joseph O'Rourke Sep 30 '15 at 18:27
• Perhaps you could mention some criteria that have been proposed for what kind of problem would make a good polymath project? – Joel David Hamkins Sep 30 '15 at 21:13
• Dear Joel, I do not think we know the answer to your question. In fact, this is part of what is explored. But there were discussions about it in general and with regard to specific suggestions mainly on Tim's blog. – Gil Kalai Sep 30 '15 at 21:19
• I imagine that a good polymath problem would be one where it's reasonable to take a "divide and conquer" approach, breaking things down into cases, and sending in the troops to tackle different cases. Otherwise the only people who can contribute a lot are those with a global view of the problem, and that means that in the end just a few will contribute. – John Baez Oct 1 '15 at 5:20

8 Lonely Runners

[The aim of this proposal would be to find a project that a massive number of people (including amateur mathematicians) might actually effectively contribute to, which is a somewhat different goal than the other proposed polymath projects.]

A longstanding problem in diophantine approximation is the lonely runner conjecture which states:

Suppose one has $n\geq 1$ runners on the unit circle, all starting at the origin and moving at distinct speeds. Then for each runner, there is a time that that runner is separated by a distance of at least $1/n$ from each other runner.

This has been proven for $n \leq 7$ runners by Barajas and Serra but is open for higher values of $n$. It is known that one can reduce to the case where all of the speeds are integers. From here each of the previously considered cases (for $n \leq 7$) can be treated by case analysis based on various congruence conditions of of the $n$ integer speeds.

Extrapolating from the work on $n \leq 7$, the work of splitting into and proving the various cases should be highly parallelizable and many cases completely elementary. At the same time, however, one might well imagine that more creative/sophisticated/clever arguments could be developed or applied to particular cases, which could have the potential of even yielding progress the general case as well.

In fact, recently Terry Tao proved that one needs only consider a finite number of cases for each $n$ (unfortunately the number of such sets is extremely large even for $n=8$ and beyond the capabilities of computer search) so in some sense this proof strategy is guaranteed to work with enough effort.

• I recently found a way to modify Terry's argument to show that it suffices to check speed vectors in $\mathbb Z^7$ with $l^2$ norm up to $56^6/\text{vol}_6$ (that is the reciprocal of the volume of a ball of radius 1/56 in $\mathbb R^6$). This bound is slightly less than 6 billion which still leaves far too many cases to check without some clever idea. – Anthony Quas Dec 7 '17 at 23:22
• @Anthony: That's quite encouraging! Certainly that is still too large for a brute force search, but I'd imagine that one could whittle the search space down substantially through elementary arguments (congruence considerations, etc) which was the spirit of the polymath proposal. It might be also worth trying to re-frame these argument in terms of Freiman isomorphism classes instead of bounding the size of the largest element. This might also yield a substantial reduction in the size of the search space. – Mark Lewko Dec 11 '17 at 1:17

The circulant Hadamard matrix conjecture states that for $n>4$ there does not exist a sequence $(a_1,\dots,a_n)$ of $\pm 1$'s that is orthogonal to every proper cyclic shift of itself. It has a similar flavor to the Erdős discrepancy problem that was the topic of Polymath5. Terry Tao says the following on his blog about the circulant Hadamard matrix conjecture: "One may have to wait for (or to encourage) a further advance in this area (which would be more or less an exact analogue of the situation with Polymath5 and the Erdos discrepancy problem)."

• There was some recent investigation by Banica, Nechita and Schlenker of some analytical approaches to this conjecture - the authors were, if I read them correctly, keen to point out that they are merely exploring some techniques arxiv.org/abs/1212.3589 – Yemon Choi Oct 2 '15 at 1:30
• (Some years ago I was toying with the idea of proposing the CHM conjecture for Polymath, but at the time I worried that it would just be seen as a curiosity) – Yemon Choi Oct 2 '15 at 1:37
• One can similarly ask about $n$ by $n$ Hankel matrices. Also as far as I know there are no current lower/upper bounds on the max determinant of circulant/Hankel $\pm1$ matrices so this is a possible side project which has the advantage of allowing incremental improvements. – Lembik Jan 4 '16 at 10:42
• Dear Richard, @RichardStanley, for a sequence $a=(a_1,a_2,\dots,a_n)$ of $\pm 1$ vectors, let $D(a)$ be the largest absolute value of the inner product of $a$ with a cyclic shift and let $D(n)$ be the minimum value of $D(a)$ over all $\pm 1$ vectors of length $n$. What is known about $D(n)$? Is it plausible that $D(n)$ tends to infinity with $n$? – Gil Kalai Apr 10 '18 at 11:12

Is the Matrix Multiplication Exponent $\omega$ too famous?

Recall that $\omega$ is the inf of all real numbers $k$ such that two $n \times n$ matrices can be multiplied in $O(n^k)$ steps. It is currently known that $2 \leq \omega < 2.3728639$.

Regarding lower bounds, there are several new ideas over the last few years from the field of Geometric Complexity Theory; see, e.g., Grochow's survey. Computer scientists aren't always too expert in the area of representation theory, so it could be a good chance for cross-area collaboration.

Regarding upper bounds, there have been several improvements over the last few years (Stothers, Vassilevska-Williams, and now Le Gall) pushing hard using the "traditional methods", a new paper on limits of the traditional methods, and the very interesting alternate approach of Cohn-Kleinberg-B.Szegedy-Umans based on group theory and arithmetic combinatorics.

• I wanted to add a link to this paper here, which rules out certain approaches in the group theoretic framework: arxiv.org/abs/1605.06702 – Eric Naslund Aug 31 '17 at 15:25

One of Imre Ruzsa's problems [1], from 1971, asked for the slowest possible exponential growth rate of a mapping $f : \mathbb{N} \to \mathbb{Z}$ that is not a polynomial and yet shares with (integer) polynomials the congruence-preserving property $n - m \mid f(n) - f(m)$. Precisely, what can be said about the infimum of values $A$ for which there is such an $f$ having $|f(n)| < A^n$ for all $n \gg 0$?

Now, while a personal favorite of mine, this hardly qualifies for anything like a major problem. But it does have some interesting extensions, in addition to having itself the feature of a catchy and challenging problem on which, nevertheless, new progress appears within reach.

Here is an example indicating a modest improvement over the published literature on Ruzsa's problem. Using a variant of the construction by Noam Elkies and David Speyer of integer-valued polynomials with slow growth (which they gave solving this question of mine: Are there infinitely many integer-valued polynomials dominated by $1.9^n$ on all of $\mathbb{N}$?), Zannier's auxiliary construction from [3] can be modified to improve the value $A \approx 2.117$ that he gave in 1996 (still the best one in print) up to at least $A \approx 2.22$. This can certainly be improved further, and I do not know just how much the value of $A$ can be raised with this type of modification. (I did make some heuristic calculation suggesting that this addition to Zannier's method may never, by itself, raise the value to $2.316$ or beyond.) I mention this for indication that Ruzsa's problem is not completely blocked; it could be valuable to find alternative constructions or a wholly different approach, and also to formulate and explore some related problems, like the simple ones I sketch below.

To put Ruzsa's problem into perspective, note that $A \leq e$ is plain from the prime number theorem; one perhaps expects equality to hold. In the other direction, letting $S : j \mapsto j+1$ the shift operator on mappings $\mathbb{N} \to \mathbb{Z}$, the prime number theorem together with the congruence $(S-1)^p \equiv S^p - 1 \mod{p}$ and the characterization of polynomials by $(S-1)^n f(\underline{1}) = 0$ for all $n \gg 0$, imply the lower bound $A \geq e-1$. These remarks summarize the two observations made by Ruzsa in [1]. Perelli and Zannier proved [2] that $f$ is necessarily holonomic when $A < e$ (it satisfies a linear recursion with polynomial coefficients), placing the problem into the context of Fuchsian differential equations. Indeed, Zannier's idea in [3] to improve over the previous value of $A$ was to use a result of the Chudnovskys on the Grothendieck-Katz $p$-curvature conjecture for such differential equations.

Concretely, we have:

Problem 1. How much beyond $A = 2.22$ can the infimum on exponential growth rate be improved in Ruzsa's problem? (For instance, with the method I mention in the third paragraph above.)

Problem 2. For $F = \sum f(n)t^n \in \mathbb{Z}[[t]]$ and $p$ prime let $n_p(F) \in \mathbb{N} \cup \{\infty\}$ be the degree of $F \mod{p}$ as a rational function in $\mathbb{F}_p(t)$. In Ruzsa's problem we would have $n_p(F) = p$. Extending this, does the obviously best possible positivity condition $\liminf_n \frac{1}{n} ( - \log{|f(n)|} + \sum_{p : \, n_p(F) < n} \log{p} ) > 0$ force in fact the rationality $F \in \mathbb{Q}(t)$?

Note the immediate countability of the set of $F$ satisfying this assumption. The positivity condition here is similar to the ones in Bost and Chambert-Loir's work on arithmetic algebraization theorems in Arakelov theory and adelic potential theory, themselves having roots in the good old rationality criteria of Borel-Dwork and Polya-Bertrandias. Incidentally, the connection of such ideas with potential-theoretic ones by itself suggests some new twists to the original Ruzsa problem, the simplest being:

Problem 3. May, in the available results on Ruzsa's problem, the condition that $F = \sum f(n)t^n$ be holomorphic on a circular disk of radius $> 1/A$ be extended to a condition of meromorphy on a simply connected domain $\Omega \ni 0$ having conformal mapping radius $\rho(\Omega,0) > 1/A$?

There are (easy) weaker sufficient conditions for rationality that modify the sum under the positivity condition in Problem 2 by $\xi \sum_{p: \, n_p(F) < \kappa n} \log{p}$ for appropriate constants $\xi, \kappa < 1$. An optimal choice of such available constants yields the value $\exp(3-2\sqrt{2})$ in the following problem of Zannier from [4], intermediate in generality between Problems 1 and 2:

Problem 4. What is the infimum of values $A$ such that any integer sequence having $|f(n)| \ll A^n$ and satisfying for almost all $p$ a mod $p$ constant coefficients linear recurrence of size $\leq p + O(1)$, satisfies in fact a constant coefficient linear recurrence over $\mathbb{Z}$? Clearly, $A \leq e$, which could well be an equality. Can Zannier's lower bound $A \geq \exp(3 - 2\sqrt{2})$ be improved?

Again, I am not entirely sure this is the kind of topic that would make a suitable focal point for the polymath type of project. It might be not well known enough, or broad enough, or promising enough. Either way, it is just a suggestion, and I thought I would mention here these problems, which I find attractive -- in view of the intrinsic challenge of Ruzsa's original problem (still open since 1971), as well as of the variety of broader extensions it might suggest.

References.

[1] I. Ruzsa: On congruence preserving functions, Mat. Lapok 22 (1971), pp. 125--134 (In Hungarian).

[2] A. Perelli, U. Zannier: On recurrent mod $p$ sequences, Crelle 348 (1984), pp. 135--146.

[3] U. Zannier: On periodic mod $p$ sequences and $G$-functions (On a problem of Ruzsa), Manuscripta Math. 90 (1996), pp. 391--402.

[4] U. Zannier: A note on recurrent mod $p$ sequences, Acta Arithmetica 41 (1982), pp. 277--280.

• Are these all arithmetic combinatorics? – user76479 Oct 1 '15 at 5:15
• @Arul: This is not really combinatorial, unless you are giving combinatorics a rather broad meaning. It rather fits into the broad label of "mathematics organized around the product formula" (taking it close to diophantine approximations, at least by methodology) - but then it is just a problem. Anyway, if this should be put into any sort of broader perspective, it is about how narrowly an algebraic structure is pinned down by congruence conditions. Obviously, the positivity condition in Problem 2 pins the mapping $f$ down to a countable set; what is the structure of this countable set? – Vesselin Dimitrov Oct 1 '15 at 5:47
• What is a good text for these areas? these objects do not look much far from application in CS (infact Rusza's name is in Arithmetic Combinatorics) – user76479 Oct 1 '15 at 5:49
• @Arul: A good text? Ruzsa's problem itself is not nearly so famous as to have a vast literature of its own. I gave some references that considered it; in addition to these I should add Gilles Christol's paper Globally bounded solutions of differential equations. As for the mathematics behind the arithmetic algebraization theorems and the arithmetic study of linear differential equations, this is a vast subject to which Chambert-Loir's Bourbaki expose Arithmetic algebraization theorems... and Bost and Chambert-Loir's paper Analytic curves in algebraic varieties... are excellent guides. – Vesselin Dimitrov Oct 1 '15 at 6:20
• Tangentially "Arithmetic Combinatorics" is the name of the relevant MSC subject class 11B30. Some prefer this name as "additive" does not quite capture things like sum-product problems and is arguably not so fitting for non-commutative settings. – user9072 Nov 4 '15 at 16:35

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 $$\sum_{n\geq 1}\frac{\sin(2^n)}{n}$$ is a convergent series. A quite detailed description of my attempts can be found on MSE.

• This should be very difficult. Do we even know, for instance, that the powers of $2$ are dense on $\mathbb{R} / 2 \pi \mathbb{Z}$? – Vesselin Dimitrov Oct 19 '16 at 23:06
• @VesselinDimitrov: not according to my knowledge. That depends on the distribution of the $0,1$ digits in the binary representation of $\pi$ or $\frac{1}{\pi}$. My wild guess is that the BBP formula may provide a way to prove it. – Jack D'Aurizio Oct 19 '16 at 23:08
• Right, and the problem is, little is known about the distribution of the binary digits of $\pi$. Needless to say there do exist divergent values of $g(\xi) = \sum_n \sin(2^n\xi) / n$ (while the series is convergent for Lebesgue almost all $\xi$), and so a solution to your problem would have to use special properties of the digits of $\pi$. One of course expects $\pi$ to be a normal number, but extremely little is 'known' in this direction. – Vesselin Dimitrov Oct 19 '16 at 23:39
• Is this equivalent to convergence of $\displaystyle\frac{e^{2i}}{1}+\displaystyle\frac{e^{4i}}{2}+\displaystyle\frac{e^{8i}}{3}+\displaystyle\frac{e^{16i}}{4}+\cdots$? – samerivertwice Sep 20 '17 at 11:50

Update: February 23, 2017. Launched on polymathblog.

Rota's Basis Conjecture. Let $B_1, \ldots, B_n$ be $n$ bases of an $n$-dimensional vector space $V$ (not necessarily distinct or disjoint). Then there exists an $n\times n$ grid of vectors $(v_{ij})$ such that

1. the $n$ vectors in row $i$ are the members of the ith basis $B_i$ (in some order), and

2. in each column of the matrix, the $n$ vectors in that column form a basis of $V$.

Informally, the claim is that we can always find some ordering $(v_{i1},v_{i2},\ldots,v_{in})$ of the $n$ vectors in $B_i$ in such a way that the transversals $(v_{1j},v_{2j},...,v_{nj})$ are all simultaneously bases.

Here are some reasons why I think this is a good polymath project.

1. The conjecture has been open since 1989 and a number of people have made serious attempts to prove it, so it's a significant open problem. It is intrinsically appealing but it also has connections to Rota's bracket-theoretic approach to representation theory, so a positive solution might lead to a deepening of that theory. Also it seems to lie just beyond the boundary of what we understand about matroids and so could expand our knowledge in that direction too.

2. There are multiple partial results coming from different directions, as I'll describe in a moment. The time seems ripe for a group of people to look at the partial results together and see if the whole can be made to be greater than the sum of the parts.

3. The problem feels to me like it falls into the category of problems that have too little structure for a purely deterministic construction but too much structure for a purely random construction. A number of difficult problems of this type have fallen in recent years so the time may be ripe for another such.

Now let me say a bit about the aforementioned "multiple partial results."

1. Playing around a bit, one gets the sense that the complicated way in which circuits (i.e., minimal dependent sets), especially small circuits, interact is one of the key obstacles. Geelen and Humphries (Rota's basis conjecture for paving matroids, SIAM J. Discrete Math. 20 (2006), 1042–1045) have solved the case where all the circuits are large (of size $n$ or $n+1$). Perhaps one can construct a proof by induction on circuit size. I don't think too many people have looked at this.

2. An approach that I've explored is to understand what obstructions arise when, instead of a square matrix, one considers a rectangular matrix that has more rows than columns. I think that there is some chance that there are only a limited number of such obstructions; if these could be characterized then perhaps Rota's basis conjecture would follow. My first attempt in this direction turned out to be too optimistic (see Harvey, Kiraly, and Lau, On disjoint common bases in two matroids, SIAM J. Discrete Math. 25 (2011), 1792–1803) but I still think that there is promise here.

3. The approach that has led (by some measure) to the strongest partial results has been to reduce Rota's basis conjecture (for even dimension and characteristic zero) to the Alon–Tarsi conjecture on even and odd Latin squares, which was proved for $n=p+1$ ($p$ an odd prime) by Drisko in 1997. There have been some recent advances in this direction as well, e.g., Glynn, The conjectures of Alon-Tarsi and Rota in dimension prime minus one, SIAM J. Discrete Math. 24 (2010), 394–399, and Alpoge, Square-root cancellation for the signs of Latin squares, arXiv:1412.7574, and Bollen and Draisma, An online version of Rota's basis conjecture, J. Algebraic Combin. 41 (2015), 1001–1012.

4. Geelen and Webb (On Rota's basis conjecture, SIAM J. Discrete Math. 21 (2007), 802–804) have shown that we can get the first $O(\sqrt{n})$ columns to be bases.

There are some other partial results on the conjecture but this should do for now. All the papers I've just cited use very different ideas and it is tempting to speculate that combining them might give us the extra oomph we need to prove the full conjecture. Or, perhaps one of the ideas just needs an additional push.

I think finding combinatorial models for the Kronecker coefficients, or the multiplicative structure constants for Schubert polynomials would make good polymath projects.

These are quite famous problems in the field of algebraic cominatorics, and would immensely give better insight. Furthermore, the problems are quite accessible, it boils down to fit some combinatorial model to some known (but tricky to compute) data, meaning that even a bright high-school student can give it a try.

Both these problems has the Littlewood-Richardson coefficients as special cases, for which there are plenty of combinatorial models, so a good start would be to collect these, and see if there is some way to generalize these.

Both problems have known models for other sub-cases, so one can imagine that a polymath project could study natural sub-families. In the case of Schubert structure constants (indexed by three permutations), we know the answer for vexillary permutations.

Perhaps it is possible to find models for other natural combinations of permutations.

Finally, it might even be possible to do some "bruteforce" approach, by some kind of machine-learning. I have not heard this being used before, but it is not totally impossible that Schubert structure constants are given by lattice points in certain nice polytopes (since known special cases are), so it might be possible to try to find polytopes to the data.

• I have a rather big issue with this "proposal" for Kron coeff. First, it's been a major open problem for a long time. It makes sense to have a project if you have a reasonable even if very weak idea how to start. You don't, or at least it's not transparent from the answer what is it. Second, I see no definition of a "combinatorial model". Would anything in #P work? Finally, I see no reason why the answer should be positive under any definition. My issue here - after some long thinking I (still) see no framework to disproof. Cf. bit.ly/2ceaDim – Igor Pak Aug 26 '16 at 12:14

Yesterday Aubrey D.N.J. de Grey posted to the arXiv a new preprint that announces the first improvement since 1961 on the lower bound on the Hadwiger-Nelson problem (chromatic number of the plane):

Aubrey D.N.J. de Grey:
The chromatic number of the plane is at least 5.
arXiv:1804.02385


We present a family of finite unit-distance graphs in the plane
that are not 4-colourable, thereby improving the lower bound of
the Hadwiger-Nelson problem. The smallest such graph that we
have so far discovered has 1567 vertices.


(Note: 1567 was later corrected to 1585.)

Proposed Polymath problem:

Reduce the number of vertices (currently $1585$) of the smallest known unit-distance graph in the plane that is not 4-colorable.

• This is excellent news! To put the result in perspective, as far as I know the best current bounds, due to Pritikin in 1998, are that any unit-distance graph in the plane with at most 6197 vertices is 6-colorable, and any such graph with at most 12 vertices is 4-colorable. – Andrés E. Caicedo Apr 10 '18 at 3:29
• Dear Noam, no no no no no, please don't remove it. – Gil Kalai Apr 10 '18 at 14:26
• OK, I won't won't won't won't won't remove it :-) – Noam D. Elkies Apr 11 '18 at 0:34
• It seems that the current status is that the 1567-point graph is 4-colorable (and there was a bug in de Grey's code), but it was obtained by removing a few too many vertices from a 1585-point graph that's not 4-colorable (and this has now been indepndently checked by a SAT solver). So we still have a new lower bound of 5 on the chromatic number of the plane; but I need to edit my post because the target is no longer 1567. In any case the point of the Polymath project would be to find bigger tweaks that change the vertex count by rather more than 18. – Noam D. Elkies Apr 11 '18 at 0:37
• To avoid ambiguity (although perhaps not needed by ordinary English usage) I was careful to have an odd number (five) of "no"s. – Gil Kalai Apr 11 '18 at 21:03

The Moser Worm problem and Bellman's Lost in a forest problem.

The Moser Worm problem is the task of finding a (convex) cover of minimum area in the plane which contains rotated-translated copy of any curve of length one (a worm) as a subset.

Bellman's Lost in a forest problem is to find the shortest path which ensures an escape from a forest of known shape and size.

The problems are directly related in that the Moser worm problem is equivalent to looking for the shape of a forest of given area which has the longest escape path and any solution to Bellman's problem provides an upper bound for the Moser worm problem.

Although these problems are famous I think that this type of geometry problems is often neglected and can be approached with the aid of computational searches to provide new clues.

• Sounds interesting. The Wikipedia article for the Worm problem lists known upper and lower bounds for the area as 0.260437 and 0.232239, respectively. Do you hope for tighter bounds, an explicit solution for the area or even the shape? – Dirk Oct 1 '15 at 8:18
• I think that simply trying to do better with those bounds is not so easy. it would interesting to start with the lost in a forest problem. This was recently solved for the equilateral triangle. Can it be solved for all triangles? What triangle gives the best bound for Moser's problem? What about other simple shapes? Also are there any general statements that might be made about the shape of paths when the forest is a polygon? Will it always be a polyline? etc. – Philip Gibbs Oct 1 '15 at 9:44
• For a convex cover, the lower bound would be 0.270911861. The current lower bound is proved by trying to estimate the minimal area of a convex shape containing a segment, a triangle and a rectangle. We can try to add more shapes to tighten the lower bound, but I am not sure if it will be analytically or computationally feasible. – Tirasan Khandhawit Oct 2 '15 at 9:03
• One approach to this kind of problem is to first try to compute the answer without any attempt to prove the result, so monte carlo methods are fine. The hope is that when you see the answer you can formulate some conjectures and try to prove them. The computation is then just scaffolding that might be removed from the final analysis. This requires collaboration between programmers and problem solvers. – Philip Gibbs Oct 2 '15 at 12:01
• This strikes me as a reformulation of the traveling salesman problem. – user102126 Jul 6 '18 at 7:56

# Real world applications of large cardinals

The goal of this proposed project is to use large cardinals to prove a result in an applied area or at least a “down-to-Earth” area of mathematics such that the large cardinal hypotheses cannot be removed.

Motivation

Large cardinals are able to prove results about finite and countable structures which cannot be proven otherwise. For example, all large cardinals prove the purely combinatorial statement $\textrm{Con}(\mathrm{ZFC})$ and even $\textrm{Con}(\mathrm{ZFC}+\mathbf{S})$ whenever $\mathbf{S}$ is a weaker large cardinal axiom. One should therefore expect for large cardinals to also prove finitistic purely combinatorial statements which are independent of ZFC but which are of interest to mathematicians such as finite group theorists or finite combinatorialists. Unfortunately, large cardinals have not yet found their way into these down-to-Earth subjects.

Rank-into-rank embeddings

At this point in time, the large cardinals around the rank-into-rank level seem to have the most potential for real-world applications due to the intricate algebraic structure of rank-into-rank embeddings. We shall therefore limit the scope of this project to algebraic structure of the large cardinals around the rank-into-rank level.

Let $\lambda$ be a cardinal and let $\mathcal{E}_{\lambda}$ denote the set of all elementary embeddings from $V_{\lambda}$ to $V_{\lambda}$. The elementary embeddings in $\mathcal{E}_{\lambda}$ are known as rank-into-rank embeddings. If there is a non-trivial elementary embedding in $j\in\mathcal{E}_{\lambda}$, then $\lambda$ is an extremely large strong limit cardinal of countable cofinality. Define an operation $*$ on $\mathcal{E}_{\lambda}$ by letting $j*k=\bigcup_{\alpha<\lambda}j(k|_{V_{\alpha}})$.

$\mathbf{Theorem}$ (Laver)

1. The algebra $(\mathcal{E}_{\lambda},*)$ satisfies the left-distributivity identity $j*(k*l)=(j*k)*(j*l)$.

2. If $j\in\mathcal{E}_{\lambda}$ is a non-trivial elementary embedding, then $j$ freely generates a sub-left-distributive algebra of $\mathcal{E}_{\lambda}$.

Rank-into-rank embeddings have also been used to prove purely algebraic results about left-distributive algebras.

$\mathbf{Theorem}$ (Van Name 2015 (Laver 1990's for one generator)) If for all $n\in\omega$ there exists an $n$-huge cardinal, then the free left-distributive algebra on an arbitrary number of generators is isomorphic to a subalgebra of an infinite product of finite left-distributive algebras.

It is currently open as to whether the above result can be proven without the large cardinal assumptions. While the above result applies large cardinals to finite objects, it is hard to call this result “down to earth”; even though we know that the free left-distributive algebras embed into an inverse limit $\varprojlim X_{n}$ of finite algebras, we know that the individual algebras $X_{n}$ converge to the free left-distributive algebras very slowly (slower than the inverse of any monotone primitive recursive function). Furthermore, I would like to see large cardinals applied to finite or countable structures beyond just left-distributive algebras. It seems like in the near future very large cardinals would prove theorems in cryptography, low-dimensional topology, or possibly even group theory which ZFC cannot prove.

Large cardinals in cryptography?

Any type of computable algebraic structure has potential uses in cryptography, and self-distributive algebras have already been used to construct cryptosystems. For example, Dehornoy has shown that self-distributive algebras may be used as platforms for authentication schemes. However, no left-distributive algebra has been shown to be a secure platform for Dehornoy's authentication scheme. Perhaps large cardinals may provide self-distributive algebras which are secure under Dehornoy's authentication scheme. On a different note, the action of braid groups on self-distributive structures has been shown to be able to obfuscate universal reversible circuits in this paper. I therefore see the possibility of large cardinals proving results related to cryptography which cannot be proven in ZFC.

Large cardinals in low-dimensional topology?

In this paper, Dehornoy outlines a future research program in which the Laver tables may be applied to low-dimensional topology. I conjecture that along these lines, large cardinals may be used to prove results in low-dimensional topology which are independent of ZFC.

Why polymath?

Since this proposed project requires the collaboration between set theorists and non-logicians, and set theorists usually do not collaborate with non-logicians (such as algebraic topologists or cryptographers), it seems like a venue such as Polymath would be a good method to promote collaboration between these two very different sorts of mathematicians. Furthermore, since these sorts of self-distributive algebras have not yet been deeply investigated, any mathematician would be able to make contributions to this project. I also expect this project to be largely computational, so one could contribute to this project simply by writing computer programs or observing computed data.

Various areas of mathematics would benefit from this project (if it is successful) since large cardinals will allow people to prove more theorems in these areas of mathematics than they are able to prove in ZFC.

• I have been considering making the goal of this project to construct a public key cryptosystems from the algebras of elementary embeddings and make the cryptosystem as secure and efficient as possible. Though, it is too early to discuss the specifics of this project. – Joseph Van Name Feb 24 '17 at 4:01
• So it looks like the $n$-ary Laver tables could be used as platform for this key exchange arxiv.org/pdf/1305.4401.pdf. Furthermore, since the $n$-ary Laver tables can be endowed with a composition operation, the Ko-Lee key exchange applies to the $n$-ary Laver tables as well. This will be indeed the first and only practical application of set theory. If $n$-ary Laver table based cryptosystems are secure against classical computers, then it seems like they will continue to remain secure against quantum computers. – Joseph Van Name Apr 7 '17 at 1:49

Here is a simple-to-state, but notoriously difficult open question from algorithmics, which I think might not have received yet the attention of the larger mathematics community.

The Greedy Superstring Conjecture:

Consider a set of $n$ strings $s_1, \dots, s_n$ over a finite alphabet $\Sigma$. Assume that none of the strings is a substring of another. We want to find a shortest string $s$ that contains all $s_1, \dots, s_n$ as substrings.

Here's an "obvious" heuristic: find the two strings $s_i, s_j$ with the largest overlap, and replace $s_i$ and $s_j$ with the string obtained by overlapping $s_i$ and $s_j$ as much as possible. After $n-1$ steps we obtain a string that is the superstring of all $s_1, \dots, s_n$. The conjecture says that this solution is at most twice as long as the optimum.

The problem is described (among other places) in Vazirani's book Approximation Algorithms, Chapter 2.3.

• What happens if, during the running of this algorithm, the "none is a substring of another" condition is violated by $s_{i1},...,s_{ik}, b_{n-k+1}$, where the $b$ string is the newly formed big string? Or is that the point? Gerhard "Sometimes Not Quick On Uptake" Paseman, 2015.10.06 – Gerhard Paseman Oct 6 '15 at 17:08
• That can't really happen during the execution (except at the beginning). Suppose for contradiction that this happens first time when we merge $s_i$ and $s_j$ to obtain $b$, and now $s_k$ is contained in $b$. Now either $s_k$ was already contained in $s_i$ or $s_j$ (contradicting that it happened the first time), or the overlap of $s_k$ with $s_i$ is larger than the overlap between $s_i$ and $s_j$, contradicting that we executed the correct step. (my previous comment - now deleted - where I wrote that this can happen was wrong) – László Kozma Oct 7 '15 at 9:50

There is a problem that links both geometry and number theory, called Rational Simplex Conjecture, formulated by Cheeger and Simons. One may regard it more as a question, rather than a conjecture, that asks the following: if you have a spherical tetrahedron with dihedral angles rationally commensurable with $\pi$, will its (spherical) volume be rationally commensurable with $\pi^2$? (The volume of the sphere $\mathbb{S}^3$ in its metric of constant sectional curvature $+1$ is $2\pi^2$, and finite reflection groups give examples of "rational" simplices with "rational" volumes). This problem is discussed in a book by J. Dupont (and several papers by J. Dupont and and C.-H. Sah) on scissors congruences, and also has relations to cone zeta-functions, counting lattice points in polytopes, etc observed by a number of authors (e.g. Robins et all).

Another problem that is even easier to formulate (and which is known since a long time) is to determine all possible tilings of the Euclidean plane by convex pentagons. There have been many attempts to find such pentagonal tilings, one is quite recent: by now, there are 15 convex pentagons known to tile the plane. It would be interesting to see any nice mathematical theory (except making educated guesses or computer brute force) that stands behind the exact number of pentagonal tilings of the plane (there are a few known, but there is no proof the list is complete).

I don't know if any of these problems seems interesting enough (and I'm not even in position to write a full proposal, so you may regard this as a lengthy comment), and if not - I beg you pardon for your time wasted.

Hoping it is not too famous an open problem, I would suggest trying to (dis)prove that Euler's constant $\gamma$, defined as $\displaystyle{\lim_{n\to\infty}H_{n}-\log n}$ where $H_{n}$ is the $n$-th harmonic number, is irrational. A plausibly interesting approach may rely on Hankel determinants, that were successfully used by Yann Bugeaud et al to obtain new results about irrationality exponents in http://arxiv.org/abs/1503.02797.

• What problem could be more famous than this? It was the dream of many great number theorists. – Vesselin Dimitrov Sep 30 '15 at 16:53
• This is indeed a very famous problem. Probably aiming to show that $\zeta (5)$ is irrational, or better perhaps improving quantitatively the results by Ball and Rivoal regarding values of zeta functions at odd integers would be a good project. It is not impossible that in the sequence $a_n$ with , $a_1=$Aperi, $a_2=$ Ball-Rivoal, ... some later terms will have relevance to Euler's constant. – Gil Kalai Sep 30 '15 at 19:03
• I don't know whether Gil allows several answers from the same person, but maybe finding the best possible upper bound for the quantity $\beta$ defined as $\inf\{C\mid p_{n+1}-p_{n}\ll\log^{C} p_{n}\}$ assuming it's finite could me more tractable. – Sylvain JULIEN Oct 26 '15 at 16:15

Here is a personal favorite of mine, considered at this question. Will Orrick has a website with some data on the problem, which I call the "determinant spectrum" problem (range of the determinant function on the finite set of order $n$ 0-1 matrices) , and we hope it will yield information on Hadamard's maximum determinant problem.

Much of the results I know are inspired by computer analysis, and I think a particular goal would not only be accessible but make an advance toward a combinatorial understanding of binary matrices (as opposed to a probabilistic or analytic understanding). The goal I have in mind is to find a short and uniform description of 0-1 matrices whose ADVs (absolute determinant values) span all integers in an interval from below $(1.6)^n$ to $c(\sqrt{n})^n$ for some small constant $c$ and $n$ a sufficiently large integer that gives the rank of the matrix. (The easy case of $[0, (1.6)^n]$ has been handled, initiated by computer investigation by Roger House.) Even if one only gets up to, say, $O((\sqrt{n}/\log n)^n)$, that would be a significant advance. Orrick observes that $c$ is near $1/2$ for small $n$.

Gerhard "Of Course, Modesty Forbids Me..." Paseman, 2015.09.30

• Granted, I've moved away from it for now, but I may make it mine again, violating number (3). Sorry, Gil. Gerhard "Is Willing To Share Project" Paseman, 2015.09.30 – Gerhard Paseman Sep 30 '15 at 16:28
• $c(\sqrt{n})^n$ should be more like $c(\sqrt{n}/2)^n$, as I confused values for determinants of 0-1 matrices with values of their 1,-1 binary counterparts. In any case, I would like seeing even $(\log n)^n$ achieved with a uniform description. At present, I don't know how to make a short and uniform description do better than exponential growth. Gerhard "Just A Difference Of Two" Paseman, 2015.09.30 – Gerhard Paseman Oct 1 '15 at 3:42

Update (Aug 26, 2016), see Ofir's comment to this posting: Ofir Ofir Gorodetsky and Ron Peled have proved the identity!

Update 2 (Sept 27, 2016) In Guo-Niu HAN's 2000 paper "Generalisation de l’identite de Scott sur les permanents," Han proved a more general formula. (See detailed comment below).

The following might be a right-level project for a polymath project.

Keith R. Motes, Jonathan P. Olson, Evan J. Rabeaux, Jonathan P. Dowling, S. Jay Olson, Peter P. Rohde proposed in the paper

An amazing formula for the permanent of the matrix representing a sort of the discrete Fourier transform. The formula was reached at by evaluating the cases $n \le 6$ and was checked symbolically for up to $n\le 16$ or so and numerically much beyond. So it must be true! No proofs is known.

Here is the formula: $$\operatorname{Per}(\hat U^{(n)})=\frac{1}{n^{n-1}}\prod_{j=1}^{n-1}\big[j e^{in\varphi}+n-j\Big],$$

$\hat U ^{(n)}$ is a certain version of the discrete Fourier transform defined as follows: $$\hat U_{j,k}^{(n)}=\dfrac{1-e^{in\varphi}}{n\big(e^{\frac{2i\pi(j-k)}{n}}-e^{i\varphi}\big)}$$ (For the ordinary matrix of the discrete Fourier transform people did look a little at the permanent but it's not so beautiful.)

Of course, it would be nice to prove it. I talked about it a summer ago with Ron Adin and Oron Propp (an undergraduate from MIT) and we had a few ideas but they did not work. I popularized the problem a little among experts in enumerative combinatorics but I don't know if people are working on it.

• Dear Gil, Ron Peled and I were able to prove this nice formula. The main tool is Borchardt's identity, which reduces the permanent calculation to the evaluation of two determinants, which in our case are circulant. Here's a link to the draft of the short proof: dropbox.com/s/p4hdl2qb7pgppn7/identity.pdf?dl=0 – Ofir Gorodetsky Aug 26 '16 at 6:43
• Ron Adin pointed out to a 2000 paper by Guo-Niu Han where he proved formula of a more general nature regarding permanents. www-irma.u-strasbg.fr/~guoniu/papers/p25scott.pdf . (Indeed Ofir Gorodetsky confirmed that it includes the formula we asked for after simple manipulations). Han's proof also rely on Borchardt's identity (that's how Ron Adin had found it). The proof by Ofir Gorodetsky and Ron Peled (being for the special case that it is) proceeds more directly to the final answer. – Gil Kalai Sep 27 '16 at 10:08

Here is a (known) open question that I heard from Peter Sarnak.

Show that $2^n+5$ is composite for almost all positive integers $n$. (Namely, for sets of integers of density 1.)

Since $\prod\limits_p \left(1-\frac{1}{p-1}\right)=0\,$ it looks like proving that

1. $2^n+5$ divides a primes $p$ for a fraction of $1/(p-1)$ integers or so (on average), and

2. these probabilities should be rather independent

should suffice. But alas, both of these are very problematic.

On the other hand, this does not look like a hopeless question, and perhaps requires interesting and not too hard techniques. I suppose I'd enjoy watching such a project. The fraction of "good" $n$'s can be shown to be very close to $1$ by some computer experimentation which may also reveal something.

• Thanks, V. for the good (but short lived) comments. Since this is not in my area I am not sure at all it is a good question. I realize it is very difficult but my uneducated hunch is that it is not hopeless and potentially fruitful. – Gil Kalai Jan 31 '16 at 12:13
• It is a very good problem but first we need to solve the simpler one that the set of primes dividing some member $2^n+5$ is not too sparse. GRH implies a positive density of such $p$ (indeed, $2$ should be a primitive root for a positive density of primes) - this will take care of point (1). But if it happened that $\sum 1/\mathrm{ord}_p^{\times}{2} = \infty$ over those ("good") primes then (2) would actually predict a positive density of prime values. So we need to eliminate such a scenario, and this by itself seems like a very difficult problem. That said, we could try to work under GRH. – Vesselin Dimitrov Jan 31 '16 at 16:41
• The number of "good" primes up to $X$ (i.e., the prime divisors of the sequence) is easily proved to be at least $\gg \log{X}$. I know of no improvement over this basic bound (which works for general linear recurrences, the obvious exceptions set aside). This is in marked contrast to the sequence $2^n + 1$, for which Hasse proved the density $17/24$ for the prime divisors. This is because the set of prime divisors in this case can be expressed in terms of splitting primes for various Kummer fields, to which Chebotarev can be applied. Similarly for $a^n+b^n$ and the Lucas sequence. – Vesselin Dimitrov Jan 31 '16 at 16:47
• (Sorry, I meant to write "$\sum 1/\mathrm{ord}_p^{\times}{2} < \infty$" in the first comment above.) – Vesselin Dimitrov Jan 31 '16 at 16:50
• We could also, instead of fixing the form $2^n+2^2+1$, parametrize the odd numbers $2^{n_1} + \cdots + 2^{n_k}+1$ composed of up to $k+1$ binary digits by $k$-tuples $(n_1,\ldots,n_k)$ (ordered by $\max{n_i}$ and then lexicographically), and ask for which $k$ it could be proved that a full density of those numbers are composite. For $k = 1$ this is obvious, while at least for $k$ large enough ($\geq 3$ it seems, possibly also for $k = 2$) the previous difficulty with (1) is not hard to resolve. – Vesselin Dimitrov Jan 31 '16 at 23:15

A conjecture that can be stated in so simple terms that it is hard to classify, is Frankl's Union-Closed Sets Conjecture. It would be fantastic to see this solved.

• One possible finite set to evaluate: Each prime in the product is found in half of the square-free divisors of the product: Table[GCD[Divisors[2*3*5*7], n], {n, {2, 3, 5, 7}}] // MatrixForm $\left( \begin{array}{cccccccccccccccc} 1 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 2 \\ 1 & 1 & 3 & 1 & 3 & 1 & 1 & 1 & 3 & 3 & 3 & 1 & 3 & 1 & 3 & 3 \\ 1 & 1 & 1 & 5 & 1 & 1 & 5 & 1 & 5 & 1 & 5 & 5 & 1 & 5 & 5 & 5 \\ 1 & 1 & 1 & 1 & 1 & 7 & 1 & 7 & 1 & 7 & 1 & 7 & 7 & 7 & 7 & 7 \\ \end{array} \right)$ – Fred Kline Jan 5 '16 at 0:01
• This problem is given a [purported - TT] proof. arxiv.org/pdf/1507.01270v6.pdf – Takahiro Waki Jun 13 '16 at 20:13
• This might land in the "too-famous" category. – Todd Trimble Jan 3 '17 at 2:24

The two biggest open conjectures in the intersection of representation theory (of finite dimensional algebras) and homological algebra are the Nakayama conjecture (see http://www.math.uni-bonn.de/people/schroer/fd-problems-files/FD-NakayamaConj.pdf) and the finitistic dimension conjecture ( see http://www.math.uni-bonn.de/people/schroer/fd-problems-files/FD-FinitisticDimConj.pdf). I have a plan to test those conjectures: Namely a weaker conjecture is the following: Given a nonselfinjective finite dimensional algebra $A$ over a field K, then $Ext^{i}(D(A),A) \neq 0$ for some $i \geq 1$. Here D(A)=Hom_K(A,K). This has never really been tested for large classes of algebras and for algebraically closed fields, it is enough to test it for quiver algebras (see for example https://www-fourier.ujf-grenoble.fr/~mbrion/notes_quivers_rev.pdf for an introduction to such algebras). For such algebras the problem can be stated in purely graph theoretical/ linear algebraic terms and is thus understandable to a wider audience. To begin, one could start with local algebras. This means quiver algebras with just one point. It is also a win win situation: One might really find a counterexample (this would be big) or at least one could gain good evidence for the conjectures (no big evidence for the homological conjectures seems to exist yet). On the other hand, in the local case the world record for the number $\inf \{ i \geq 1 | Ext^{i}(D(A),A) \neq 0 \}$ seems to be only 2 and also just because of that it would be interesting to study the problem. (one can also let a computer search for examples, this is related to this question Algorithm for finding quiver algebras , where the problem is to find quick programs to find all admissible ideals)

Briefly:

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?

Bit of background:

After asking a question on MSE I see that there are a number of open questions around polynomials in $\mathbb{Z}[x]$ whose roots, and whose derivative's roots, are all distinct integers.

In particular, there seem to be examples known up till degree six, with the sextic case having been resolved in 2015, yet nothing known for polynomials of greater degree. (Of course, if such a polynomial can be found, then a natural follow-up would be whether such polynomials exist of all degrees, and, if not, what the minimal counterexample would be.)

Appropriateness for polymath:

I think this is a not-too-well-known problem that still has a reasonable literature on it (the linked paper above contains a number of references) which would be amenable to computational attacks (especially if answerable in the affirmative for degree seven and above). There are also sub-problems that can be explored around specific families of functions (e.g., those that satisfy this criterion and have degree five) as well as natural generalizations (e.g., explorations of the above question for not just a function and its first derivative, but for a function and all of its derivatives).

Covering Arrays are combinatorial objects that have applications in Computer Science among other fields, specifically in software and hardware testing.

The definition is a 4-tuple $$CA(N;t,k,v)$$, where it is an $$N\times k$$ array, with each entry to be one of $$v$$ possible symbols, and for every $$t$$ columns chosen, all ordered $$v^t$$ $$t$$-tuples appear at least once. We define $$CAN(t, k, v)$$ to be the minimal $$N$$ such that a $$CA(N;t,k,v)$$ exists.

Only in the case for $$v=t=2$$ is known for all $$k$$, shown by Kleitman and Spencer, and only asymptotics are known for other values of $$t, v$$. The true answer for specific parameter situations are known, but only for small $$t, v$$.

Charlie Colbourn's tables provide the best known values of $$CAN(t, k, v)$$ for various values. However, only some heuristics are known via optimization and sub-optimal constructions.

There is a vast literature on covering array techniques; it would be a great success to be able to gain more of an understanding as to the behavior and structure of covering arrays. Some questions that are interesting:

• Covering perfect hash families (CPHFs) are compact representations of covering arrays, but only when $$v$$ is a prime power. What nontrivial direct constructions exist for CPHFs? What about a related object when $$v$$ is not a prime power?

• What if we insist that all $$t$$-tuples appear a given number of times $$\lambda \ge 1$$? Some lower and upper bounds are known, but they are not tight.

• How does $$CAN(t,k+c,v)$$ relate to $$CAN(t,k,v)$$ for a constant $$c$$? Some bounds are known, and recent improvements have been found, but only in specific values of $$t, v$$.

Limit Cycle theory and Hilbert 16th problem:

A longstanding problem in the theory of ordinary differential equations and dynamical systems is the problem of the number of limit cycles of a polynomial vector field. For mathematical development around this historica;l problem, please see this paper.

In this direction, I am interested in the following MO posts, which I have asked them already.

The following questions search for some relations between limit cycle theory and one of the following $$4$$ areas. So the questions can be a link between differential equations and dynamical systems, and the areas listed below :

i) Differential geometry, curvature and torsion.

ii) Complex singular foliation

iii)linear operators, index theory and Dynamica Lefschetz trace formula (Page 9 of this paper)

iv)Algebraic geometry and theory of Abelian integrals

Here, I list these MO questions:( Question0trace is motivated by consideration of a Lefschetz trace formula for counting the number of limit cycles of a 2 dimensional flow. Questions 0WG,0, and 1-6 are related to each other. They try to look at limit cycles and closed orbits, as closed geodesics).

KEEPINGTRACKOFLIMITCYCLES) Keeping track of limit cycles via certain second order differential operator

• And how does this relate to Polymath? – Gerry Myerson Sep 8 '17 at 21:58
• @GerryMyerson Prof. Myerson I collected a list of questions of mine in this answer, which are related to limit cycle theory. All of them have a common point "limit cycles". I love this mysterious concept, "limit cycle". Before posting my answer, I reviewed some answers to Polymath project and I realize that some of them search for collaborators to work on their project. So I post my answer with the same reason. I think that these 24 question are directly (or in a few cases indirectly) related to the second part of the Hilbert 16th problem. – Ali Taghavi Sep 9 '17 at 9:27
• @GerryMyerson Furthermore am i mistaken to think that a polymathy problem is a problem which can be involved with a wide range of (mathematical) fields?If so, does not "the limit cycle problem" satisfy this property? – Ali Taghavi Apr 6 '19 at 20:40
• I don't know, Ali. Have you tried proposing it to the polymath blog, or wherever it is that people decide what the next polymath problem should be? – Gerry Myerson Apr 7 '19 at 2:42

Erdos-Straus conjecture For every integer $n > 1$, there exists three positive integers $x$, $y$ and $z$, such that the equation $\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$ holds. Note that for a given number $n$, the number of triplets i.e. {x,y,z} satisfying above equation might be more than one.

The problem is interesting because of it simplicity. It requires hardly any knowledge of mathematics to understand the problem, and yet it remains unproven for more than 6 decades i.e. since it was proposed by Paul Erdos and Ernst G. Straus in 1948. - Source

• The problem is reduced to this formula. math.stackexchange.com/questions/450280/erdős-straus-conjecture/… Formally we have to show that the solution is always there. And the linear equation solution is always $4L-n=1;2;3;4$ – individ Feb 23 '17 at 6:42
• Formally, the equation $\frac{t}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$ The solution could be implemented and so more. $x=pk$ ; $y=sk$ ; $z=L$ $$k=\frac{nL(p+s)}{ps(tL-n)}$$ For this concrete case it is necessary to prove that the solution is always there. Suffice it to say that for $k$ you can always find an integer solution. It is enough to show that $4L-n=3$ is always a solution. It is necessary to factorize the number $nL=Aps$ Thus to so $(p+s)$ it is divisible by 3. It is easy to show that this can always be done. – individ Feb 23 '17 at 10:50

The Cartan determinant conjecture for quiver algebras. The Cartan determinant conjecture states that every finite dimensional algebra of finite global dimension has the property that the determinant of its Cartan matrix is equal to one. For quiver algebras the problem would reduce to a linear algebra problem concerned with graphs understandable to any student with knowledge of basic linear algebra. And a proof for quiver algebras would provide a proof of the general conjecture over algebraically closed fields. The Cartan matrix of a finite dimensional quiver algebra is defined as the matrix having entries $c_{i,j}:=$dimension of the vector space $e_i A e_j$, which is the space generated by all paths from $i$ to $j$ in the quiver.

If I understand correctly, polymath is a possibility to find like-minded persons to whom you could discuss questions in the area you are currently interested in. If yes, I would be happy to find people willing to discuss problems/to collaborate in the field of stereotype spaces and their applications. I mentioned this activity not long ago in a post concerning applications of functional analysis in other fields of mathematics. I wrote there about the applications of the envelopes of topological algebras. This is an area that opens new connections between functional analysis and geometry.

In a word, an envelope is a functor that turns a topological algebra into a new topological algebra (in fact, envelopes can be defined in each category, not necessarily in a category of topological algebras, but I am speaking here about the most interesting example) with the properties similar to the typical functional algebras in geometry -- the algebras of continuous functions, of smooth functions, of holomorphic functions, etc. It turns out that different classes of functional algebras are closely connected to different classes of morphisms used as "observation tools" in these constructions:

• the algebras ${\mathcal C}(M)$ of continuous functions are connected to the class of homomorphisms into $C^*$-algebras (one can think that this is expected),

• the algebras ${\mathcal C}^\infty(M)$ of smooth functions are connected to the class of "differential" homomorphisms into $C^*$-algebras with joined self-adjont nilpotent elements (in contrast to the previous case, this is unexpected),

• the algebras ${\mathcal O}(M)$ of holomorphic functions are connected to the class of homomorphisms into Banach algebras (this again can be considered as expected).

(These "test algebras" are commutative, but, certainly, the functor of envelope usually turns non-commutative algebras into non-commutative algebras. So this is a language where commutativity is not a necessary condition, and that is why it allows to study, in particularly, quantum groups.)

These observations lead to a purely categorical construction that allows to look at the "big geomertrical disciplines" in mathematics

• topology,

• differential geometry,

• complex geometry,

-- as parts of a general scheme. Each class of observation tools leads to an envelope which gives a "projection of functional analysis to some geometrical discipline" like these three ones (but not necessarily, since there are many different classes of observation tools and each of them leads to a new geometry). And each such a geometry has its own duality theory that generalizes the Pontryagin duality (to a proper class of non-commutative groups).

Of course, this sounds vague, the accurate definitions and proofs are here and here.

This can be considered as a developement of Klein's Erlangen program (and an intriguing possibility to look at mathematics "from above").

The problem for me is that when doing this research I face all the way problems from the parts of mathematics where I have weak intuition. That is why all the way I have to ask people around (including people here, at MO) different questions (sometimes some of my questions turn out to be stupid, so I am sorry for this...).

If there are people who are interested in discussing this with me, I would be happy to share my experience (and to collaborate) with them. There are lots of problems in this area. The simpliest are studying properties of stereotype spaces, and the most "ambitious" are constructing different "new geometries" (look at the introduction here).

Thank you.

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$?

I've asked a question at MO (under my actual name Włodzimierz Holsztyński), which is a basic algebraic problem (it's hard too) while it has a direct application to image and parallel processing:

It was an MO-question, which implies certain MO-limitations. But there is much more to this. If there is an interest in this I will be willing to expand on this earlier MO-note (link above).

• What's an "OM question"? – Gerry Myerson Jun 6 '17 at 22:46
• @GerryMyerson, it's a dislexic description of that question. – Wlod AA Jun 6 '17 at 22:52
• "dislexic" is dysorthographic "dyslexic" (will this process ever converge?). – Wlod AA Jun 7 '17 at 2:22

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$?

I propose the following uniformly distributed random variable decomposition conjecture:

Assume $$X,Y$$ are independent random variables supported on a finite subset of the integers, and assume $$Z=X+Y$$ is uniformly distributed on its support: is it necessarily the case that $$X$$ and $$Y$$ are themselves uniformly distributed on their support?

It has been originally posted in post Why polynomials with coefficients $0,1$ like to have only factors with $0,1$ coefficients? in a form of polynomial factorization. Based on research there, this is an open problem referenced in Krasner and Ranulac (1937), Sur une propri\'et\'e des polynomes de la division du cercle, C.R. Acad. Sci. Paris 204, 397--399, where the result is proven for exponents from some arithmetic progression.

The counterexample search might be parallelizable and has been already attempted in various ways (proving non-existence of such counter example by ruling out small degree polynomials, brute-force search, automatic reasoning/proving based on coefficiients, Groebner basis application).

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

• As stated, this would be unsuitable, as it is unclear how to "parallelize" in a fashion desirable for Polymath. If you were to provide, say, an additional predicate P(n) such that P(n) and the Collatz dynamic terminates upon input n, that might be suitable. Many of the other examples provided are sufficiently restricted that the leap to parallelize is not so great. Please edit this to find a restriction that suits the conditions of the post. Gerhard "Polymath Is Not Group Mathematics" Paseman, 2017.01.07. – Gerhard Paseman Jan 7 '17 at 21:13
• +1, nice paper. We're making progress. Still don't know how to parallelize. – Fred Kline Aug 16 '17 at 3:00
• Regarding the question of parallelising the efforts, here are the three most important theorems that the paper demonstrates: 1) for any odd number a, whoever can prove that 4a+1 and 8a+3 have a common number in their orbit (anywhere, backward or forward) solves Syracuse 2) for any odd number a, either the orbits of 8a+1 and 16a+1 will merge, or 8a+1 will merge with 64a+17 and 16a+1 will merge with 2a-1. 3) theorem 2) will occur at least once in any odd number's forward orbit, because any odd number will have either a number 8a+1 or 16a+1 where a is odd, at least once in its forward orbit. – Falken Aug 19 '17 at 9:20
• Calling the pairs (4a+1, 8a+3) where a is odd "buds", and having established that their solving solves Syracuse, it is important to observe that some of them "solve themselves", and I can demonstrate why. As some buds point one to another (are redundant), it is relevant to ask which proportion of the set of all buds must be solved to solve Syracuse, typically the sort of question one might ask in Ramsey theory. In any case, the systematic attacking of buds can be parallelised, and is one way to parallelise the solving of Syracuse. – Falken Aug 19 '17 at 9:20
• Oh, and don't worry about ego injuring. Most mathematicians (of my acquaintance, and probably outside of it too) are more concerned with time misspent on studying worthless claims than on priority claims. Gerhard "And This Is My Claim" Paseman, 2017.10.05. – Gerhard Paseman Oct 5 '17 at 15:06

I'm coming a bit late to this list but I'd like to see some attention paid to AFK's primary proposition in this question which seems to have been entirely ignored in favour of a discussion of his background behind asking it.

• This thread isn't for drawing attention to just any kind of unsolved problem, but only for those "that you genuinely think to be potentially suitable for a polymath project." So, what makes this question particularly suitable for a polymath project? – Gerry Myerson Nov 7 '17 at 11:06
• @GerryMyerson a) the fact that so many people are motivated to solve it - important because participation is a key ingredient to success of a polymath project. b) its importance and the likely impact of the result - it must surely be an aspiration of polymath to be of consequence c) the fact there is a clear proposition to be assessed d) the problem's difficulty and complexity is going to require many skilled people to assess any proposition and reach consensus. i.e. this problem is sufficiently hard that it's harder to get somebody to read your proof than it is to prove it in the first place! – samerivertwice Nov 7 '17 at 11:35
• Whereas a proof agreed upon by a community will be taken seriously. – samerivertwice Nov 7 '17 at 11:36
• "this problem is sufficiently hard that it's harder to get somebody to read your proof than it is to prove it in the first place!" What nonsense. In the first place, you have no idea how hard it's going to be to resolve the question. In the second place, mathematicians are eager to read solutions of long-standing problems (provided those solutions pass some minimum plausibility tests). And more to the point, how do you propose to break this problem up into pieces on which individuals can work independently? That's what it takes to be a polymath problem. – Gerry Myerson Nov 7 '17 at 11:40
• @GerryMyerson Humour's frequently based on nonsense. I'm not sure why you would say I have no idea how hard it's going to be when its obvious the lower bound on hardness is the vast amount of work that's been carried out on it already. The emphasis on polymath seems to be collaboration rather than independence. On perhaps related note, why do other posters apologise that their proposed problems might be "too famous"? I wondered if this is an issue with this proposal. – samerivertwice Nov 7 '17 at 13:01