170
$\begingroup$

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

$\endgroup$
18
  • 3
    $\begingroup$ I'm noticing a large matricial aspect to the proposals. Gerhard "Glad I Proposed Mine Early" Paseman, 2015.09.30 $\endgroup$ Sep 30, 2015 at 16:32
  • 4
    $\begingroup$ 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? $\endgroup$ Sep 30, 2015 at 18:27
  • 4
    $\begingroup$ Perhaps you could mention some criteria that have been proposed for what kind of problem would make a good polymath project? $\endgroup$ Sep 30, 2015 at 21:13
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Sep 30, 2015 at 21:19
  • 10
    $\begingroup$ 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. $\endgroup$
    – John Baez
    Oct 1, 2015 at 5:20

36 Answers 36

58
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$ Dec 7, 2017 at 23:22
  • $\begingroup$ @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. $\endgroup$
    – Mark Lewko
    Dec 11, 2017 at 1:17
46
$\begingroup$

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

$\endgroup$
5
  • 3
    $\begingroup$ 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 $\endgroup$
    – Yemon Choi
    Oct 2, 2015 at 1:30
  • 2
    $\begingroup$ (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) $\endgroup$
    – Yemon Choi
    Oct 2, 2015 at 1:37
  • $\begingroup$ 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. $\endgroup$
    – Simd
    Jan 4, 2016 at 10:42
  • $\begingroup$ 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$? $\endgroup$
    – Gil Kalai
    Apr 10, 2018 at 11:12
  • $\begingroup$ If you convert $a$ to the binary sequence $b = (a+1)/2$ then you have that a sequence $b$ of length $n=4m$ needs to have at least $m$ 1s and one 0. Can $\langle b, b'\rangle$ even just be constant for all cyclic shifts $b'$, never mind vanish? $\endgroup$
    – user114668
    Sep 10, 2020 at 8:54
43
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ 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 $\endgroup$ Aug 31, 2017 at 15:25
33
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Are these all arithmetic combinatorics? $\endgroup$
    – user76479
    Oct 1, 2015 at 5:15
  • $\begingroup$ @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? $\endgroup$ Oct 1, 2015 at 5:47
  • $\begingroup$ 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) $\endgroup$
    – user76479
    Oct 1, 2015 at 5:49
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 1, 2015 at 6:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – user9072
    Nov 4, 2015 at 16:35
33
$\begingroup$

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.

$\endgroup$
2
31
$\begingroup$

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.

$\endgroup$
4
  • 10
    $\begingroup$ 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}$? $\endgroup$ Oct 19, 2016 at 23:06
  • 2
    $\begingroup$ @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. $\endgroup$ Oct 19, 2016 at 23:08
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 19, 2016 at 23:39
  • 2
    $\begingroup$ 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$? $\endgroup$ Sep 20, 2017 at 11:50
28
$\begingroup$

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

The abstract reads:

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.

$\endgroup$
13
  • 6
    $\begingroup$ Dear Noam, no no no no no, please don't remove it. $\endgroup$
    – Gil Kalai
    Apr 10, 2018 at 14:26
  • 7
    $\begingroup$ OK, I won't won't won't won't won't remove it :-) $\endgroup$ Apr 11, 2018 at 0:34
  • 4
    $\begingroup$ 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. $\endgroup$ Apr 11, 2018 at 0:37
  • 7
    $\begingroup$ To avoid ambiguity (although perhaps not needed by ordinary English usage) I was careful to have an odd number (five) of "no"s. $\endgroup$
    – Gil Kalai
    Apr 11, 2018 at 21:03
  • 4
    $\begingroup$ Apparently we are down to 826 vertices, so progress has been fast! $\endgroup$
    – David Roberts
    Apr 17, 2018 at 3:29
26
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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 $\endgroup$
    – Igor Pak
    Aug 26, 2016 at 12:14
23
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Dirk
    Oct 1, 2015 at 8:18
  • $\begingroup$ 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. $\endgroup$ Oct 1, 2015 at 9:44
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 2, 2015 at 9:03
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 2, 2015 at 12:01
  • $\begingroup$ This strikes me as a reformulation of the traveling salesman problem. $\endgroup$
    – user102126
    Jul 6, 2018 at 7:56
21
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$ Oct 6, 2015 at 17:08
  • 3
    $\begingroup$ 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) $\endgroup$ Oct 7, 2015 at 9:50
21
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 24, 2017 at 4:01
  • $\begingroup$ 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. $\endgroup$ Apr 7, 2017 at 1:49
17
$\begingroup$

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.

$\endgroup$
0
17
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Jan 31, 2016 at 12:13
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 31, 2016 at 16:41
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 31, 2016 at 16:47
  • $\begingroup$ (Sorry, I meant to write "$\sum 1/\mathrm{ord}_p^{\times}{2} < \infty$" in the first comment above.) $\endgroup$ Jan 31, 2016 at 16:50
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 31, 2016 at 23:15
16
$\begingroup$

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.

$\endgroup$
3
  • 15
    $\begingroup$ What problem could be more famous than this? It was the dream of many great number theorists. $\endgroup$ Sep 30, 2015 at 16:53
  • 3
    $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Sep 30, 2015 at 19:03
  • $\begingroup$ 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. $\endgroup$ Oct 26, 2015 at 16:15
14
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Sep 30, 2015 at 16:28
  • $\begingroup$ $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 $\endgroup$ Oct 1, 2015 at 3:42
13
$\begingroup$

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

"Linear Optical Quantum Metrology with Single Photons: Exploiting Spontaneously Generated Entanglement to Beat the Shot-Noise Limit"

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.

$\endgroup$
2
  • 14
    $\begingroup$ 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 $\endgroup$ Aug 26, 2016 at 6:43
  • 6
    $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Sep 27, 2016 at 10:08
13
$\begingroup$

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 upper bounds of $CAN(t, k, v)$ for many values. However, most of these bounds come from lots of computation, usually from randomized constructions. Many recursive constructions are not competitive, and there are far too few direct constructions.

There is a vast literature on covering array construction techniques, nearly all of which show upper bounds. Many of the best-known constructions involve at least one of: the probabilistic method, random graph theory (specifically chromatic numbers of random graphs), and algebra.

Here are some worthwhile questions to answer:

  • A long-standing conjecture is the "uniform CA conjecture", which asserts that for any row-optimal CA, there exists another CA on the same parameters where the number of symbols in each column is as-equal-as-possible. When there are non-symmetric constraints on the problem, the conjecture is known to be false.

  • Can one improve the best known asymptotic upper bounds? This would most likely involve improving estimates of existing probabilistic methods.

  • A constructive upper bound makes "many" rows that don't have all tuples, but most of them, and then form an "incompatibility" graph among all remaining tuples. The chromatic number of this graph is the number of remaining rows, so there is a balance to play here on what "many" means at the beginning. What is the appropriate balance?

  • Covering arrays are equivalent to finding the chromatic number of graphs with all vertices of the form $(C, T)$ where $C$ is a tuple of $t$ distinct column indices, $T$ is a tuple of $T$ values (not necessarily distinct). An edge is formed between $(C_1, T_1)$ and $(C_2, T_2)$ if for all $c \in C_1 \cap C_2$, the corresponding values in $T_1, T_2$ are distinct.

  • Covering perfect hash families (CPHFs) are compact representations of covering arrays defined over a finite field, but only when $v$ is a prime power. What nontrivial direct (algebraic) constructions exist for CPHFs? What about a related object when $v$ is not a prime power (if a reasonable definition of such an object exists)?

  • What if we insist that all $t$-tuples appear a given number of times $\lambda \ge 1$? This is resolved, in that $\Theta_{v,t}(\log k + \lambda)$ rows are needed, which is asymptotically optimal when $v,t$ are fixed. But the hidden constants are most likely not optimal when $v,t$ are not fixed.

  • What "large" subsets of the $\binom{[k]}{t}$ sets of columns allow for sublogarithmic growth in the number of rows (in terms of $k$)?

  • 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$. This is likely a very hard problem.

$\endgroup$
12
$\begingroup$

Solving Polynomial Diophantine equations in order

Define size h of a polynomial Diophantine equation to be a non-negative integer such that there is only a finite number of equations of every size, order all equations by size, and then solve all equations in order. For an example of such project see Mathoverflow questions What is the smallest unsolved diophantine equation? and Can you solve the listed smallest open Diophantine equations? where a specific choice of h is suggested.

The first equations will be solvable by trivial methods such that, for example, analysis modulo some integer. However, very soon you will meet equations like $x(y^2+2)=1$ solvable in reals and modulo every integer but still with no integer solutions, elliptic curve equations like $y^2=x^3-3$, equations like $y(x^2-y)=z^2+1$ that require analysis of prime factors of quadratic forms, equations like $x^2+y^2-z^2=xyz-2$ that require Vieta jumping technique, and then very soon you meet equations like $x^3y^2=z^3+6$ that look amazingly simple but that you will not be able to solve. And it does not really matter how exactly you define the size h - for different h, you will meet essentially the same interesting equations, just in a different order.

This project is ideal for polymath. We will need a computer program for enumerating the equations and automatically solving as many simple equations as possible. This is work for someone who likes programming. Then, for each new value of h, computer program will return some equations it cannot automatically solve. Some of these equations will be still easy for human, so amateurs and undergraduate students can contribute by solving them, and leaving only a short list of interesting equations. At this point more senior participants may step in and try more advanced methods (for example, calculate the Brauer group of the corresponding surface and determine whether there is a Brauer-Manin obstruction to solutions). The project is perfectly parallelizable, and there will be an interesting job (and something to learn) for everyone!

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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)$ $\endgroup$ Jan 5, 2016 at 0:01
  • $\begingroup$ This problem is given a [purported - TT] proof. arxiv.org/pdf/1507.01270v6.pdf $\endgroup$ Jun 13, 2016 at 20:13
  • 1
    $\begingroup$ This might land in the "too-famous" category. $\endgroup$
    – Todd Trimble
    Jan 3, 2017 at 2:24
11
$\begingroup$

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)

$\endgroup$
11
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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$ $\endgroup$
    – individ
    Feb 23, 2017 at 6:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – individ
    Feb 23, 2017 at 10:50
11
$\begingroup$

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

For more information, see (e.g.) the arXiv paper here (pdf) as well as the aforelinked.

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

$\endgroup$
0
9
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ But X+Y does not appear uniform if X, Y uniform. E.g. the sum of two fair dice is not uniform ( 7,8 more frequent than 2, 12). $\endgroup$
    – JHM
    Jan 12, 2021 at 14:29
  • 2
    $\begingroup$ @JHM But there are examples uniform on their support, like a fair die with faces 1,2,3,4,5,6 and another fair die with faces 6,12,18,24,30,36. $\endgroup$
    – Will Sawin
    Apr 17, 2021 at 1:56
9
$\begingroup$

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

A simple formulation of the problem: Consider the following differential equation on $\mathbb{R}^2:$

$$(H)\;\;\;\begin{cases} x'=P(x,y)\\y'=Q(x,y)\end{cases}$$ Here $x.y$ are real variables and $x'=dx/dt.\;\;y'=dy/dt$ where $t$ is a real (say time)parameter. Moreover the functions $P.Q$ are polynomial functions in $x,y$. A periodic orbit for this system is a closed orbit $\gamma(t)=x(t).y(t)$ where $(x(t),y(t)$ is a periodic function in $t$ satisfies the above differential equation $(H)$.

Example: Consider $$(C)\;\;\;\begin{cases} x'=y\\ y'=-x\end{cases}$$ Then every closed curve $\gamma_r (t)=(rsin(t),rcos(t))$ is a solution for this equation. In fact we have a familly of periodic solutions for $(C)$. This band of closed orbits surround the singularity $(0,0)$. Such kind of singularity which is surrounded by a familly of closed orbits is called a center. Notice that a singularity of a differential equation $x'=P(x,y),\qquad y'=Q(x,y)$ is a point $(x_0,y_0)$ such that $P(x_0,y_0)=Q(x_0,y_0)=0$.

In contrast to this very simple example, that we have a band of closed orbit, it may happen we have an isolated closed orbit for our system of differential equation. Any such isolated closed orbit is called a Limit cycle.

https://ars.els-cdn.com/content/image/3-s2.0-B9780081024454000059-f05-20-9780081024454.jpg

The second part of the Hilbert 16th problem asks that:"Are there uniform upper bounds $H(n)$ for the number of limit cycles of a polynomial differential equation as $(H)$ whose components $P,Q$ are polynomial functions of degree $n$?

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:( Question 0trace 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). Some of these questions are included in this RG project.

These questions are the following:(The reason for unusal numbering of the early questions, as 00 or 0trace, ..etc, is that they should have been at the top of the list but the shift of numbers (of items) was difficult)

(Morse Theory and Limit cycle theory) A closed leaf with two different index with respect to two different Riemannian metrics

(Jacobi field, conjugate points and Limit cycle theory)Jacobi equation and conjugate points on solution curves of the Van der Pol vector field

(TOPOFTHELIST) Does $P_xP_y+Q_xQ_y=0 \implies$ "non-existence of limit cycle" for $P\partial_x+Q\partial_y$"? (Complex dilatation and limit cycle theory)

00)A cohomology associated to a (not necessarily integrable) distribution (Hilbert 16th problem and dynamical Lefschetz trace formula 2)

0TRACE) Hilbert 16th problem and dynamical Lefschetz trace formula

0WG) A concept weaker than geodesibility of flows which is possibly useful in limit cycle theory

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

  1. (Some possible obstructions to ) Limit cycles as closed geodesics(3)

1)Limit cycles as closed geodesics(2)

2)A curvature description for center condition for quadratic vector field

3)Limit cycles of quadratic systems and closed geodesics(Finitness of $H(2)$)

  1. Flat Riemannian metrics adapted to quadratic vector fields with center

  2. Limit cycles as closed geodesics (in negatively or positively curved space)

6)Hilbert 16th problem via hyperbolic geometry

  1. The error in Petrovski and Landis' proof of the 16th Hilbert problem

8)Analytic vector fields on surfaces which have infinite number of singularities

9)Fredholm index vs. Limit cycle theory

  1. Codimension of the range of certain linear operators

11)The Moyal action of a planar vector field

  1. The integral of torsion

  2. The perturbation of non-Hamiltonian algebraic vector fields

  3. Counting limit cycles via curvature in Riemannian geometry

  4. Elliptic operators corresponds to non vanishing vector fields

  5. A complex limit cycle not intersecting the real plane(2)

  6. The adjoint operators as elliptic operators

  7. Dynamical obstructions for a vector field $X$ whose adjoint operator $ad_X$ sends a global orthonormal frame to a set of mutually orthogonal vectors

  8. Lifting a quadratic system to a non-vanishing vector field on $S^{3}$ or $T^{1} S^{2}$

20)Is the closed orbit of the Vander pol equation a stable periodic orbit?

  1. The Spectrum of certain differential operators

  2. Uniform upper bound for dim of kernel and codimension of range of certain familly of PDE

  3. The study of dynamics of a polynomial vector field via Green's function methods

  4. An algebraic Hamiltonian vector field with a finite number of periodic orbits (2)

  5. Dynamical obstructions for a vector field whose derivation sends an orthonormal set to a mutually Sasakian orthogonal vectors

$\endgroup$
1
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Todd Trimble
    Feb 19, 2021 at 16:01
8
$\begingroup$

Solving all cubic Diophantine equations in two variables.

Develop an algorithm which, given any integers $a,b,c,d,e,f,g,h,i,j$,

(a) determines whether equation $$ ax^3+bx^2y+cxy^2+dy^3+ex^2+fxy+gy^2+hx+iy+j=0 $$ has any solution in integers $x,y$;

(b) lists all the solutions if there are finitely many of them and somehow "describes" all the solutions if there are infinitely many of them.

(c) Ideally, the algorithm should be actually implemented.

By Matiyasevich solution of Hilbert's tenth problem, we know that the problem of determining whether a polynomial diophantine equation has an integer solution is undecidable. It is therefore natural to look at the equations of given degree and the given number of variables. The problem is known to stay undecidable for equations in 11 variables, and also for equations of degree 8 in 174 variables (of degree 4 in 58 variables if we are looking for solutions in natural numbers).

On the algorithmic side, Siegel proved in 1972 that the problem is solvable for quadratic equations in any number of variables. Also, the case of 1 variable is trivially solvable. Hence, the next case is cubic equations in 2 variables.

This is a rare case of a major open problem which is "almost solved", but some final efforts are missing. The existing results cover all "hardest" equations, leaving out only some degenerate ones. In 1970, Baker and Coates [1] developed an algorithm to find all integer points on elliptic curves. While the original algorithm in [1] is finite but impractical, subsequent authors [4, 5] made it practical. The algorithm is actually implemented in SageMath, which is an open-source and free to use mathematical software system [6].

Not all cubic equations in 2 variables are elliptic curves, some equations define genus 0 curves. For such curves, some progress is made by Poulakis [2,3]. However, these papers consider only absolutely irreducible curves.

If the curve is not absolutely irreducible, it is a product of a linear and a quadratic polynomial. If the coefficients in these polynomials are integers, the problem reduces to the known cases. If the coefficients are complex, the problem remains open, but, intuitively, such factorization should make the problem easier to solve.

I am sure that the combined polymath efforts should finish off the remaining open cases and present the general algorithm for the problem. Ideally, the algorithm should be actually implemented. The implementation may use the Sage algorithm for elliptic curves as a subroutine.

[1]. Alan Baker and John Coates. Integer points on curves of genus 1. In Mathematical Proceedings of theCambridge Philosophical Society, volume 67, pages 595–602. Cambridge University Press, 1970.

[2]. Dimitrios Poulakis. Points entiers sur les courbes de genre 0. In Colloquium Mathematicae, volume 66, pages 1–7, 1993.

[3]. Dimitrios Poulakis and Evaggelos Voskos. Solving genus zero diophantine equations with at most two infinite valuations. Journal of Symbolic Computation, 33(4):479–491, 2002.

[4]. Attila Peth˝o, Horst G Zimmer, Josef Gebel, and Emanuel Herrmann. Computing all s-integral points on elliptic curves. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 127, pages 383–402. Cambridge University Press, 1999.

[5]. Roel Stroeker and Nikolaus Tzanakis. Computing all integer solutions of a genus 1 equation. Mathematicsof computation, 72(244):1917–1933, 2003.

[6]. Paul Zimmermann, Alexandre Casamayou, Nathann Cohen, Guillaume Connan, Thierry Dumont, Laurent Fousse, Franc¸ois Maltey, Matthias Meulien, Marc Mezzarobba, Cl´ement Pernet, et al. Computational mathematics with SageMath. SIAM, 2018.

$\endgroup$
2
  • $\begingroup$ Interestingly for three-variable cubics it is far beyond current knowledge to give an algorithm that provably terminates - specifically, for $x^3 + y^3 + z^3 = n $, with $n$ not congruent to $4$ or $5$ mod $9$, the best known algorithm is to search for solutions by an algorithm much cleverer than brute force but not entirely dissimilar to it, and we have no idea how to prove a solution exists for particular $n$ other than running the algorithm until we find one. $\endgroup$
    – Will Sawin
    Apr 17, 2021 at 1:47
  • $\begingroup$ An algorithm for two-variable equations of degree <=3 already exists! WLOG the polynomial is irreducible over Z, hence irreducible over Q. If it not absolutely irreducible, then the absolute factors are conjugate, so any rational solution to one of them satisfies them all, so one can solve the system to find the finitely many rational points and check whether any of them are integer points. $\endgroup$ Jul 21, 2021 at 5:27
7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

I'd like to propose to prove the irrationality of $\zeta(5)$.

A particularly computational approach would be to search for a rational number $m$ and a sequence $(w_n)$ where $w_n$ is a polynomial of degree at least 5 in $n$, that allow to write $m \zeta(5) = \frac{1}{w_1-\frac{1^{10}}{w_2-\frac{2^{10}}{\dots}}}$.

For a crisp description and comparison to $\zeta(3)$ see this blog post https://tpiezas.wordpress.com/2012/05/04/continued-fractions-for-zeta2-and-zeta3/

$\endgroup$
4
  • $\begingroup$ Are there some out-by-one errors in the blog post? In particular, it would seem to already answer this question unless the given $w_n$ should actually be $w_n = (n-1)^4 + n^4$. $\endgroup$ Jul 22, 2021 at 14:08
  • $\begingroup$ No, I don't think so. Note that the blog post, which I found yesterday, skips $\zeta(4)$. $\endgroup$
    – Archie
    Jul 22, 2021 at 14:34
  • $\begingroup$ So why does $m=1$ and $w_n = (n-1)^5 + n^5$ not answer your question? $\endgroup$ Jul 22, 2021 at 14:42
  • $\begingroup$ Please look at the blog post, we are of course looking for an accelerated sequence to prove irrationality. $\endgroup$
    – Archie
    Jul 22, 2021 at 16:22
6
$\begingroup$

The $3^d$ conjecture

Here is a problem of mine from 1989 that could be the basis of a good polymath project.

The $3^d$ conjecture: Let $P$ be a centrally symmetric $d$-dimensional polytope. Then $P$ has at least $3^d$ non-empty faces.

A maximal flag of faces of a $d$-polytope is a chain of faces of dimensions $0,1,\dots,d-1$. A related conjecture is:

The flag conjecture: Every centrally symmetric $d$-dimensional polytope has at least $2^dd!$ maximal flags.

These conjectures are related to various other problems in geometry and combinatorics. See this blog post.

$\endgroup$
5
$\begingroup$

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:

$\qquad$ Indecomposability of image transformations (pure algebra). Open questions

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

$\endgroup$
3
  • 1
    $\begingroup$ What's an "OM question"? $\endgroup$ Jun 6, 2017 at 22:46
  • 1
    $\begingroup$ @GerryMyerson, it's a dislexic description of that question. $\endgroup$
    – Wlod AA
    Jun 6, 2017 at 22:52
  • 5
    $\begingroup$ "dislexic" is dysorthographic "dyslexic" (will this process ever converge?). $\endgroup$
    – Wlod AA
    Jun 7, 2017 at 2:22
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.