43
$\begingroup$

I would like to ask a question of a similar vein to this question.

Question: I'm asking for a list of long open problems which are computational in nature which a beginning graduate student can understand. One problem per answer, please.

Meaning of "beginning graduate student": anyone who can solve all the problems on a pure mathematics qualifying exam at a top 30 institution in the U.S.

Meaning of "computational in nature": By this, I do not mean a computational task which can be executed by a computer, but rather a problem where one must compute some object (e.g. topological invariant, closed formula, etc.) associated to some mathematical object. Example: calculating the homotopy groups of a sphere.

Meaning of "not too famous": (Same as in this question.): Roughly, if there exists a whole monograph already dedicated to the problem (or narrow circle of problems), no need to mention it again here. I'm looking for problems that, with high probability, a mathematician working outside the particular area has never encountered.

Meaning of "long open": (Same as in this question): The problem should occur in the literature or have a solid history as folklore. So I do not mean to call here for the invention of new problems or to collect everybody's laundry list of private-research-impeding unproved elementary technical lemmas. There should already exist at least of small community of mathematicians who will care if one of these problems gets solved.

Improve this question
$\endgroup$
8
  • $\begingroup$ This doesn't quite fit the bill - so I am leaving it as a comment - but perhaps there is something of interest in the computational number theory text by Hutz: maa.org/press/maa-reviews/… $\endgroup$
    – Benjamin Dickman
    Commented Apr 24, 2020 at 5:57
  • 2
    $\begingroup$ @JoshuaZ : I think user676464327 wants objects that are known to exist but that we don't know as "explicitly" as we would like. Moreover, there should be some "interesting" reason we don't know; it's not that nobody has bothered to leave a computer running long enough, or that no computer is big enough. So something like the Atlas of Lie Groups except that that's probably too famous, and a lot of the computations have been completed now. $\endgroup$
    – Timothy Chow
    Commented Apr 24, 2020 at 14:32
  • 3
    $\begingroup$ Finding more Hadamard matrices might fit the bill, though I don't know if that would be considered too famous of a problem. $\endgroup$
    – John Coleman
    Commented Apr 24, 2020 at 14:35
  • 1
    $\begingroup$ Question for the OP: when you say "computational", can this include problems for which there is not a known algorithm that would find the desired number, but one where we now the desired number (minimizing something like "distance" or energy) must exist by some kind of compactness principle? $\endgroup$
    – Yemon Choi
    Commented Apr 24, 2020 at 18:01
  • 1
    $\begingroup$ @YemonChoi I was hoping for problems for which there is a way of computing the actual number rather than just knowing the existence of the number. $\endgroup$
    – user676464327
    Commented Apr 25, 2020 at 4:30

10 Answers 10

Reset to default
34
$\begingroup$

Problem: extend the table of known van der Waerden numbers from 7 to 8 entries.

Given $K\geq 2$ colors, the length $N=W(L,K)$ of the smallest set of colored integers $\{1,2,3,\ldots N\}$ with a monochromatic arithmetic progression of length $L\geq 3$ is only known in 7 cases.

The seventh entry on the list was computed in 2012: $W(3,4)=293$, meaning 293 is the smallest integer $N$ such that whenever the set of integers $\{1,2,3,\ldots N\}$ is 3-colored, there exists a monochromatic arithmetic progression of length 4.

Adding one more entry to this table seems to meet the four criteria in the OP: a problem which is "understandable", "computational", "not too famous" (unlike the Ramsey numbers), "long open" (van der Waerden's paper, which started the search for $W(2,L)$, is from 1927).

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ This is a cool problem, because you can approach it in a purely computational way and try to find N non-deterministically and then verify it as an upper bound (which shouldn't be too hard since for any given N there are a lot very trivial colorings), or you can try and build the number combinatorially, and both are interesting. $\endgroup$
    – Juan Sebastian Lozano
    Commented Apr 24, 2020 at 7:33
  • 2
    $\begingroup$ Radziszowski's dynamic survey on small Ramsey numbers contains further examples with a similar flavor, but graph-theoretic rather than number-theoretic. $\endgroup$
    – Timothy Chow
    Commented Apr 24, 2020 at 17:04
28
$\begingroup$

Note sure whether it is too famous (it has a monograph).

Find the Moore graph of girth $5$ and degree $57$, if one exists.

That means, find a graph with diameter $=2$ (i.e., the distance between any two vertices is at most two), girth $=5$ (i.e., the shortest cycle has length five) and degree $=57$ (i.e., any vertex has exactly 57 neighbors).

All Moore graphs are known, except this one. If it exists, it must have 3250 vertices, so still quite accessible.

Improve this answer
$\endgroup$
0
18
$\begingroup$

Finding the set of forbidden minors for the class of toroidal graphs (finite graphs that can be embedded in the torus with no crossings). By the Robertson–Seymour theorem, this set is finite, but it is only partially known, and the finiteness proof is ineffective. A recent paper by Myrvold and Woodcock states, among other things, that the current list of known obstructions (over 17000 forbidden minors!) is unlikely to be complete.

Improve this answer
$\endgroup$
14
  • $\begingroup$ I imagine that the proof can be mined to give an upper bound though right? Obviously, it's likely that that bound is hilariously large though. $\endgroup$
    – cody
    Commented Apr 24, 2020 at 18:01
  • 1
    $\begingroup$ @cody : I don't think so. Robertson and Seymour proved Wagner's conjecture that any minor-closed family has a finite forbidden minor characterization. If all you know is that a family is minor-closed, that does not imply any upper bound on the number of minors or the size of the minors. To get a bound, you would have to use some special fact about toroidal graphs, and I don't think anything like that is known. $\endgroup$
    – Timothy Chow
    Commented Apr 24, 2020 at 18:21
  • $\begingroup$ Certainly, the proof that it is finite is a (non-constructive) proof that it is bounded by a natural number, based on the fact that it is closed by minors. My understanding is that such proofs can be proof mined to obtain constructive bounds, in this case, depending on the proof that it is minor closed, and the ambient logic of the proof. Again, this number is likely to be astronomical. $\endgroup$
    – cody
    Commented Apr 25, 2020 at 3:44
  • $\begingroup$ @cody : You can't always get a bound, since the proof is by contradiction. Assume the set S of forbidden minors is infinite. Then there must be 2 members of S such that one is a minor of the other; contradiction. This uses excluded middle and is ineffective. Now if you can prove that the set of forbidden minors must grow at some controlled rate r, then you can mine the proof to get a bound f(r) on how far you have to go to get the requisite 2 graphs. Here f is your astronomical function. But you still need control over r in the first place, and I don't think this is known for toroidal graphs. $\endgroup$
    – Timothy Chow
    Commented Apr 25, 2020 at 5:33
  • 3
    $\begingroup$ @cody: The issue is not that it's non-constructive (proof mining often gets bounds from non-constructive proofs). The issue is that the statement is Sigma2 ("there exists a finite set of minors such that for all finite non-toroidal graphs..."), so proof mining gives a weaker statement than a bound on the finite number. We know this to optimal in this case, because there's a diagonalization argument showing that the bound can't be computed. One thing that is possible is an assignment of ordinals to finite families such that each time we add a new forbidden minor, the assigned ordinal decreases. $\endgroup$
    – Henry Towsner
    Commented Apr 25, 2020 at 13:34
12
$\begingroup$

There exists a (99,14,1,2)-strongly regular graph? That is a graph with 99 vertices, each vertex connected with 14 other vertices, each edge entering in a unique triangle, and such that for each non-connected pair of vertices $a$, $b$, there exist other two $c$ and $d$, and only those two, connected simultaneously with $a$ and $b$?

All the restrictions studied do not rule out the existence, but nobody has been able to construct it. E. Berlekamp, J. H. van Lint y J. J. Seidel have constructed a (243,22,1,2)-strongly regular graph. (A strong Regular Graph Derived from the Perfect Ternary Golay Code, in the book A Survey of Cominatorial Theory, ed. by J. N. Srivastava, North Holland, 1973, p.~25–30.)

Improve this answer
$\endgroup$
9
$\begingroup$

I think the determinant spectrum problem should be more well known.

I've written about this elsewhere on MathOverflow, e.g. Determinants of binary matrices . Briefly:

Fix n, look at the set of n by n binary (I like 0-1 matrices, others prefer 1,-1, but they are morally equivalent) matrices, and compute their determinants over the integers. What is the set of values thus obtained? This is open for n=11, 13, and larger. (Unfortunately, Will Orrick's website at Indiana.edu is down at present, so you have to find an archived copy. The index n shifts by one sometimes, so it may be reported as 12, and 14 or larger.)

There are related questions, one of which might be computationally resolved: find a brief description, uniform in the parameter n, which gives better than exponentially many matrices whose spectrum subset is large and contiguous. I got exponentially many which hit all determinants in (-2F(n-1),2F(n-1)) using Fibonacci matrices; can someone do better?

Gerhard "Thanks Again To Roger House" Paseman, 2020.04.24.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I should add useful to brief and uniform in n. Ideally, given n and d in a given range, use the description to produce quickly an order n binary matrix with determinant d. I can do this for all n and exponentially (in n) many d. How much can this be improved? Gerhard "Not Just For Breakfast Anymore" Paseman, 2020.04.24. $\endgroup$
    – Gerhard Paseman
    Commented Apr 24, 2020 at 16:31
  • $\begingroup$ I was able to improve this to $[-c\cdot 2^n/n, c\cdot 2^n/n]$ from $[-c\cdot 1.618^n,c\cdot 1.618^n]$ using a generalization of Fibonacci matrices. I just uploaded the preprint here arxiv.org/abs/2006.04701 $\endgroup$
    – rikhavshah
    Commented Jun 9, 2020 at 17:04
  • $\begingroup$ @rikav I will check it out. Thanks for letting me know. I don't know if Robert Craigen is still interested, but I'm confident Will Orrick is interested in this. You might notify him by email. If you prefer, you can wait till I check it out. If it looks good to me (and my first skim suggests it will be), I'll ping Will myself. Gerhard "Looking Forward To Good Reading" Paseman, 2020.06.09. $\endgroup$
    – Gerhard Paseman
    Commented Jun 9, 2020 at 17:23
7
$\begingroup$

Černý conjecture was stated in 1964 and it's not very famous (no monograph, but a special number of Journal of Automata, Languages and Combinatorics last year), but probably is not "computational in nature", strictly speaking. Anyway, there are many open problems related to such conjecture which are also less known or studied.

E.g., let $f_1, \ldots, f_m$ be functions from $\{1,\ldots, n+1\}$ to itself, and let $h$ a function obtaind by composing $f_1, \ldots, f_m$ as many times as you want, so $h$ is a word on the alphabet $\{f_1, \ldots, f_m\}$. If the image of $h$ has cardinality $1$, then the set $\{f_1, \ldots, f_m\}$ is $n$-compressible and $h$ is a $n$-collapsing word. Sauer and Stone proved that there exist words like $h$ that are $n$-collapsing for every $n$-compressible set of $m$ functions from $\{1,\ldots, n+1\}$ to itself: such words are called $n$-synchronizing words.

Find $s(n,m)$, the lenght of the shortest $n$-synchronizing word over an alphabet with $m$ functions (letters). This is obviously "computational in nature" as for fixed $n$ and $m$ there is only a finite number of $n$-compressible sets $\{f_1, \ldots, f_m\}$ and an upper bound for $s(n,m)$ it's known. We know that $s(3,2)=33$ and $s(2,3)=22$, try to find other values. (Note that the problem can be stated in a more effective way using automata, see here for many other details and the upper bound for $s(n,m)$).

Improve this answer
$\endgroup$
6
$\begingroup$

I think this one fits the profile, since it computational in nature, understandable by an undergrad student and still an open problem:

The envy-free cake-cutting: the problem of cutting a heterogeneous "cake" that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

How many queries are required for cutting this cake into $n$ slices?

Whether it is "not too famous" might be disputable. Please take it with a grain of salt (I have never heard of it until a while ago, but I am not a mathematician). According to wikipedia and this other question:

The continuous "moving knife" algorithms for envy free cake cutting into connected pieces is only mentioned for up to 4 players. The general case is still an open problem.

Improve this answer
$\endgroup$
3
$\begingroup$

The moving sofa problem is really not too famous and it seems to be open at least since 1966.

This problem is surely computational in nature since it asks for the value of the sofa constant, which, as it seems, is at present unknown.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Isn't this the kind of problem that I asked the OP about, where a constant is known to exist for some compactness reason, but where there is no algorithm or procedure to compute it? The OP seemed to indicate that this was not the kind of example he or she was looking for (otherwise I could think of many examples of a physical or functional-analytic nature). $\endgroup$
    – Yemon Choi
    Commented Apr 25, 2020 at 20:24
  • 1
    $\begingroup$ @YemonChoi there does exist an algorithm, and it is even implemented in software that Yoav Kallus and I published on github (see this paper for the details). It’s just much too slow to be anywhere near practical. It is indeed an interesting open problem to find an efficient algorithm, or something at least more efficient than we developed that can improve our numerical bounds. $\endgroup$
    – Dan Romik
    Commented Apr 26, 2020 at 0:16
  • 2
    $\begingroup$ (To be clear, I wouldn’t describe the moving sofa problem itself as “computational”. Its solution would very likely require some major new insights of a purely theoretical nature. But improving the state of what’s known on the problem in an incremental fashion can be approached from a computational angle.) $\endgroup$
    – Dan Romik
    Commented Apr 26, 2020 at 0:19
  • 1
    $\begingroup$ @DanRomik I stand corrected! Thank you, that's something new I've learned. I am now wondering if some of the "infinite-dimensional" problems I had in mind can be attacked with a family of "finite-dimensional" approximations whose optimal values provably converge to the optimal value for the original problem ... $\endgroup$
    – Yemon Choi
    Commented Apr 26, 2020 at 19:28
1
$\begingroup$

I believe (I'm not a professional mathematician) that the problem concerning aliquot sequences could fit your requirements. Wikipedia has the article Aliquot sequence and the online encyclopedia Wolfram MathWorld has the article (Catalan's Aliquot Sequence Conjecture and) Aliquot Sequence both provide remarkable references.

In my view two important articles that I've known in the past are [1] and [2]. If I refer well, I've known it in the past, the professor Juan Luis Varona (Universidad de La Rioja) has a page/website dedicated to this subject.

For example this conjecture was as an answer on this Mathoverflow from the post What are conjectures that are true for primes but then turned out to be false for some composite number?, question with identificator 117891 on MathOverflow (Jan 2 '13), where is added more information in a concise way.

References:

[1] Richard K. Guy and J. L. Selfridge, What Drives an Aliquot Sequence?, Mathematics of Computation, Vol. 29, No. 129, (January, 1975), pp. 101-107.

[2] P. Erdös, On Asymptotic Properties of Aliquot Sequences, Mathematics of Computation, Vol. 30, No. 135, (July, 1976), pp. 641-645.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Feel free in comments to tell me if my answer is useful. In other case I can to delete it. Many thanks. $\endgroup$
    – user142929
    Commented May 23, 2020 at 10:14
-1
$\begingroup$

Are there any algebraic integers of degree $d \geq 3$ with bounded partial quotients?

It is a theorem of Dirichlet that for every irrational number $\alpha$, there exists infinitely many rational numbers $p/q$ with $\gcd(p,q) = 1$ and $q > 0$ such that

$\displaystyle \left \lvert \alpha - \frac{p}{q} \right \rvert < \frac{1}{q^2}.$

This can be improved with the constant on the right hand side improved to $1/\sqrt{5}$, and then this is sharp (Hurwitz's theorem). The reason is that there are badly approximable numbers, whose partial quotients in their continued fraction expansions are bounded, for which it is possible to prove a lower bound of the form $|\alpha - p/q| \geq c(\alpha) q^{-2}$ for all rational numbers $p/q$ and the constant $c(\alpha)$ depending only on $\alpha$. Note that since quadratic irrationals have eventually periodic continued fraction expansion, all quadratic irrationals are badly approximable.

It is a theorem of Roth, for which he was awarded a Fields Medal in 1958, that for any algebraic integer $\alpha$ having degree $d \geq 2$ and for any $\varepsilon > 0$, the number of reduced fractions $p/q$ such that

$\displaystyle \left \lvert \alpha - \frac{p}{q} \right \rvert < \frac{1}{q^{2 + \varepsilon}}$

is finite. In other words, all algebraic integers are almost badly approximable.

The question is, are there any algebraic integers $\alpha$ having degree $d \geq 3$ which has bounded partial quotients, or equivalently, badly approximable? This question, shockingly, remains open even for degree 3.

Improve this answer
$\endgroup$
3
  • 6
    $\begingroup$ What is the computational aspect of this problem? $\endgroup$
    – JoshuaZ
    Commented Apr 24, 2020 at 14:55
  • $\begingroup$ The question allows for the prospect of computing the existence of an object, and constructing such an algebraic integer could be considered as such. Further, computing the continued fraction expansion of a given real number is, by nature, computational. $\endgroup$
    – Stanley Yao Xiao
    Commented Apr 24, 2020 at 14:56
  • 6
    $\begingroup$ While computing a continued fraction is certainly a computational task, showing that a continued fraction has bounded coefficients certainly is not, and I don't see how you could in any reasonable sense "compute" such a number. $\endgroup$
    – Wojowu
    Commented Apr 24, 2020 at 15:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .