85
$\begingroup$

Most open problems, when formalized, naturally involve quantification over infinite sets, thereby obviating the possibility, even in principle, of "just putting it on a computer."

Some questions (e.g. the existence of a projective plane of order 12) naturally resolve after a finite computation but not feasibly.

I'd like examples of reasonably important open problems that have now been reduced, via nontrivial arguments, to finite but infeasible computations.

I'm sure that additive number theory gives examples (certain questions along the lines of Goldbach conjecture and Waring's problem, but I don't have the details handy). I'd love especially to see examples that don't seem to originate in discrete mathematics.

$\endgroup$
8
  • 5
    $\begingroup$ There are quite a few extremal problems where the conjecture is that something is the unique global minimum of continuous function over a compact set and it has been proved that it is a local minimum with an effective bound for the neighborhood, so all that remains is to take a finite net and to verify the inequality for each element. The problems are certainly open, the proof of local minimality is sometimes nontrivial, but I'm reluctant to post them because you imposed the "importance" restriction, which is hardly satisfied by any open problem in any field or any event in the Universe... $\endgroup$
    – fedja
    Nov 11, 2012 at 18:52
  • 3
    $\begingroup$ @fedja Let us say "for some value of `important'." Please do post. $\endgroup$ Nov 11, 2012 at 18:58
  • 2
    $\begingroup$ I think that the homotopy groups of spheres falls into thi category. $\endgroup$ Nov 11, 2012 at 19:40
  • 3
    $\begingroup$ @David Roberts: it is weak Goldbach (so three primes); no hope at all for (binary) Golbach. Here is a link to the paper arxiv.org/abs/1205.5252 Also it should be noted that the reduction to a finite problem for weak Goldbach is already due to Vinogradov himself I think yet definitely much older. But they and latter improvements were completely infeasibale, whereas the one you mention is (potentially) feasible. Perhaps I should explcitly add I find this recent progress quite great (to avoid my comment being misinterpreted). $\endgroup$
    – user9072
    Nov 11, 2012 at 19:56
  • 4
    $\begingroup$ Ben Green and Terence Tao have recently reduced the Dirac-Motzkin conjecture on the number of ordinary lines to a finite number of verifications; see this blog post: terrytao.wordpress.com/2012/08/24/… and this paper: arxiv.org/abs/1208.4714. $\endgroup$ Nov 11, 2012 at 21:43

17 Answers 17

33
$\begingroup$

Computing homotopy groups of spheres has been reduced in several different ways down to a finite but infeasible computation. This was discussed in another thread. John Klein's answer describes an algorithm Dan Kan came up with. The accepted answer points to other work which contains a more efficient method, but which I haven't read. I suppose you could argue that this is not an important enough problem (actually, this has also been done on MathOverflow), but most topologists would disagree. Certainly this is not a problem which originates in discrete math.

$\endgroup$
2
  • 8
    $\begingroup$ It was an important enough problem to award a Fields medal in 1954! $\endgroup$ Nov 14, 2012 at 8:22
  • 3
    $\begingroup$ I guess you're referring to the question of computing any individual homotopy group of sphere, as opposed to the totality of all homotopy groups of spheres. $\endgroup$ Jul 8, 2019 at 10:09
28
$\begingroup$

Numerical evidence suggested $\pi(x)$ is always less than $\mathrm{li}(x)$.

Littlewood proved that $\pi(x) - \mathrm{li}(x)$ changes sign infinitely often, but the smallest $x$ s.t. $\pi(x) > \mathrm{li}(x)$ is currently not known. The smallest such $x$ is Skewes' number There is a crossing near $e^{727.95133}$. It is not known whether it is the smallest.

The problem possibly might be solved by some clever method other than naiively computing $\pi(x)$, but I don't see why this argument doesn't apply to the other answers.

$\endgroup$
26
$\begingroup$

Baker's work on linear forms in logarithms reduced great big families of diophantine equations to finite searches. In many cases, sharpening of Baker's results plus large amounts of cleverness have brought the computations into the feasible range, but many other cases are still infeasible.

$\endgroup$
0
26
$\begingroup$

One of the most important open questions in graph theory is Hadwiger's conjecture, which asserts that every graph with no $K_{t}$-minor is $(t-1)$-colourable. The cases $t=1,2$ are trivially trivial, and the case $t=3$ is trivial. The case $t=4$ was actually proved by Hadwiger himself. The case $t=5$ was proved by Wagner to be equivalent to the Four colour theorem (and hence is true). The case $t=6$ was proved to hold by Robertson and Seymour and also uses the Four colour theorem. The case $t=7$ is open.

This naturally leads us to the question of given a fixed $t$, does Hadwiger's conjecture hold for $t$? Reed and Kawarabayashi proved that this question can be solved with a finite amount of computation. Namely, they prove:

  1. There is a computable function $f(t)$ such that every minimal counterexample to Hadwiger's conjecture for $t$, has at most $f(t)$ vertices.

  2. For any fixed $t$, there is an $O(n^2)$-algorithm to decide if a graph with $n$ vertices is a counterexample to Hadwiger's conjecture for $t$.

Therefore, for any fixed $t$, Hadwiger's conjecture can be decided in finite time (but the amount of time is currently infeasible).

$\endgroup$
5
  • $\begingroup$ I'm not sure what the use of the word "constant" means here, because the time depends on $t$. Do you mean "finite"? $\endgroup$
    – Will Sawin
    Nov 12, 2012 at 0:09
  • $\begingroup$ Probably "finite" would have been a better choice. I just meant that for fixed $t$, the running time is a constant. Of course Hadwiger's conjecture cannot yet be resolved via a finite amount of computation, because if we allow $t$ to vary, then the "constant" changes. I edited accordingly. $\endgroup$
    – Tony Huynh
    Nov 12, 2012 at 1:04
  • 1
    $\begingroup$ Are any bounds known for f, or, say, f(7)? $\endgroup$ Mar 31, 2014 at 12:05
  • 4
    $\begingroup$ Interestingly, for infinite cardinals $\kappa$ the "Hadwiger statement" is true: If the complete graph on $\kappa$ vertices is not a minor of a graph $G$, then there is a $\kappa$-coloring of $G$ (see arxiv.org/pdf/1312.2829.pdf ) $\endgroup$ Sep 10, 2014 at 14:04
  • 2
    $\begingroup$ @NateEldredge $f(t)$ is at most $p^{p^{p^t}}$ where $p = 10^{10^{10^t}}$. See Hadwiger's conjecture is decidable, STOC '09. $\endgroup$ Jul 6, 2023 at 23:26
21
$\begingroup$

In principle, any mathematical question $\psi$ that is not independent of ZFC (or some standard stronger theory, such as ZFC+large cardinals) is reducible to the finite computational procedure: search for a proof of $\psi$ or a proof of $\neg\psi$. If the statement is not independent, then we will find one or the other; but such computation procedures are generally infeasible, with no known bound on their length. Meanwhile, if $\psi$ is provably independent of ZFC, then we may search for a proof of that. But alas, if our axioms are consistent, then some statements may be independent, but not provably so, and we can prove that if our axioms are consistent, then there will be such examples.

Meanwhile, there are many interesting and useful theories that have been proved to be decidable, but which have infeasible decision procedures. For example, any question of Cartesian geometry in any finite dimension is decidable in principle by computational means, since the theory of real-closed fields is decidable, meaning that in principle, we can decide the truth of any assertion expressible in the structure $\langle\mathbb{R},{+},{\cdot},{\lt},0,1\rangle$, which includes many interesting statements, many of which are natural open problems of the kind you seek, such as almost all the famous packing problems. Unfortunately, the best-known algorithms for this decision procedure are at least double-exponential time, and hence infeasible. Similarly, the theory of abelian groups is decidable; Presburger arithmetic is decidable; the theory of infinite chess is decidable and many other interesting theories, capable of expressing many natural problems.

So there would seem to be an abundance of examples of the type you seek.

$\endgroup$
3
  • 14
    $\begingroup$ I took the question to mean to mean that the OP wanted problems that could be solved in $n$ computational steps, where $n$ could actually be estimated, and the answer would be a definite yes or no, but $n$ was too large to be practical. This would be a much smaller class of problems than the class you describe. $\endgroup$
    – user21349
    Nov 14, 2012 at 6:54
  • 4
    $\begingroup$ Interesting, but is it entirely ontopic? The question asks about "reduced, via nontrivial arguments". Your examples appear for all problems without need of nontrivial reduction. $\endgroup$
    – joro
    Nov 14, 2012 at 7:06
  • 12
    $\begingroup$ Ben and joro, if you follow the link in my answer on real closed fields, you will find that there is a rich body of nontrivial work providing exact upper bounds on the length of the algorithm to decide statements of Cartesian geometry. Tarski's original bound was that any statement using $n$ symbols could be decided in time $2^{2^{2^{\ldots^n}}}$, but this was subsequently improved by other researchers, eventually reduced to double exponential time. Similar nontrivial complexity analysis has been undertaken for the other theories, providing precise but infeasible upper bounds. $\endgroup$ Nov 14, 2012 at 17:21
16
$\begingroup$

Thurston asked for the maximal number of non-hyperbolic Dehn fillings on a one-cusped hyperbolic 3-manifold, and conjectured that the maximum is 10 which is only achieved by the figure eight knot complement. It's now been shown that the maximum is 10 by Lackenby-Meyerhoff, but I've also shown that there is an algorithm which will determine the finitely many manifolds with $>8$ exceptional Dehn fillings.

$\endgroup$
16
$\begingroup$

You mention additive number theory in the question, so perhaps this isn't the type of example that you want. However my understanding is that the Three Primes Conjecture (every odd number $\geq 7$ is the sum of three primes) is now at the cusp of a feasible computer solution.

Vinogradov proved that the conjecture was true for all sufficiently large odd numbers (i.e. there exists $C>0$ such that every odd number greater than $C$ is the sum of three primes).

Various people have given explicit values for $C$ but, up until recently, the best (i.e. lowest) explicit value was $e^{3100}$. This is still, obviously, way out of computational range.

However Tao and, then, more recently Helfgott have improved these bounds by studying so-called `minor arcs', so that now one could just about imagine dealing with remaining cases via computer. The results of Helfgott are expressed in terms of a parameter $q$ pertaining to minor arcs. His work implies that the conjecture is true for $q>4\cdot 10^6$.

If you're interested you should read Helfgott's preprint which begins with a brief summary of the history of this problem.

EDIT: and since then it has been resolved: http://arxiv.org/abs/1501.05438 . Congratulations to Prof. Helfgott.

$\endgroup$
2
  • $\begingroup$ This was also discussed in the comments, but it is nice to have a more detailed version. $\endgroup$
    – user9072
    Nov 14, 2012 at 11:04
  • $\begingroup$ Good point! Sorry, I missed the earlier discussion. $\endgroup$
    – Nick Gill
    Nov 14, 2012 at 12:10
15
$\begingroup$

As a result of Terry Tao's recent blog post the lonely runner conjecture for any particular value of $n$ has been reduced to a finite computation. Currently the LRC is verified only for $n \leq 7$.

$\endgroup$
13
$\begingroup$

I am not sure if this fits all the stated criterions but since it is a neat problem here it goes..

Is there a 57-regular graph $X$ of order 3250 , girth 5 and diameter 2?

$X$ is known as a Moore graph

A lot is known about $X$ (automorphism group has order less than 350), independence number is at most 400, the chromatic polynomial is $(x-57)(x+8)^{1520}(x-7)^{1729}$, but the search space of all potential graphs is still too large to be computed with an algorithm.

$\endgroup$
2
  • 2
    $\begingroup$ Interesting problem, but it is a finite computation by definition, so no nontrivial reduction :-) $\endgroup$
    – joro
    Nov 14, 2012 at 7:49
  • 16
    $\begingroup$ Say that the original problem is "describe all Moore graphs". Then the nontrivial reduction is the use of spectral graph theory to show that the degree is one of $2$, $3$, $7$, or $57$. Each of the first three occurs uniquely (pentagon, Petersen, Hoffman-Singleton) but the last is famously open. $\endgroup$ May 16, 2015 at 0:31
12
$\begingroup$

Voronoi gave an algorithm to enumerate all perfect quadratic forms in $n$ variables and consequently to identify the densest lattice packing of spheres in $\mathbb{R}^n$.

$\endgroup$
10
$\begingroup$

This is an elaboration of a comment on Suvrit's answer.

Ramsey numbers can be defined for (infinite) ordinals, just as in the finite case: $r(\alpha,\beta)$ is the least $\gamma$ such that for any $2$-coloring of the edges of the complete graph on $\gamma$ vertices there is a set of vertices of type $\alpha$ whose induced graph is red, or a set of vertices of type $\beta$ whose induced graph is blue.

Ramsey's theorem gives that $r(\omega,\omega)=\omega$, but already $r(\omega+1,\omega)=\omega_1$. On the other hand, if $\alpha\lt\omega_1$ and $n$ is finite, then $r(\alpha,n)\lt\omega_1$, and for reasonably small infinite values of $\alpha$, one can attempt to compute $r(\alpha,n)$ explicitly. It turns out that this computation reduces to (Ramsey-theoretic) finite problems, which, just as with the classic computation of finite Ramsey numbers, quickly become unfeasible.

For example:

  • $r(\omega+3,3)=\omega\cdot2 + 8$. In general, if $0\lt n,m\lt\omega$, then $$ r(\omega+n,m)=\omega\cdot(m-1)+(g(n,m)-(m-1)), $$ where $g(n,m)$ is the least $k$ such that any $2$-coloring of the edges of the complete graph on set of vertices $\{1,\dots,k\}$ such that the induced graph on $C=\{1,\dots,m-1\}$ is blue, either admits a blue $K_m$, or a red $K_{n+1}$ with one of its vertices in $C$.

This was first established by Haddad and Sabbagh in 1969. One has $r(n+1,m)\le g(n,m)\lt\infty$, but typically the first inequality is strict. For example, $r(4,3)=9$ but $g(3,3)=10$. In general, computing $g(n,m)$ is similar to, but harder than computing $r(n+1,m)$.

  • $r(\omega\cdot3,3)=\omega\cdot9$. In general, if $0\lt n,m\lt\omega$, then $$ r(\omega\cdot n,m)=\omega\cdot l(n,m), $$ where $l(n,m)$ is the least $k$ such that any $2$-coloring of the edges of the complete digraph on $k$ vertices either contains a red complete digraph on $n$ vertices, or a blue transitive tournament on $m$ vertices.

Here, in complete digraphs we have two arrows (going in opposite directions) between any two distinct vertices. This was shown by Erdős and Rado in 1955. As with $g$, the computation of the values of $l(n,m)$ quickly becomes unfeasible.

  • $r(\omega^2\cdot2,3)=\omega^2\cdot10$. In general, if $0\lt n,m\lt\omega$, then $r(\omega^2\cdot m,n)=\omega^2\cdot h(m,n)$ for a Ramsey-theoretic function $h$ related to $3$-colorings of the edges of digraphs, though its exact description is somewhat technical to include here. This was shown fairly recently by Thilo Weinert, see here.
$\endgroup$
6
$\begingroup$

In Conway's Game of Life, a lot of active problems are related to reducing the size of currently known types of starting states:

  • It's well-known that there are diagonal (e.g. glider) and orthogonal (e.g. Conway's "lightweight spaceship") spaceships, and these are quite small. It was unknown whether there were any spaceships that travel at any slopes other than these eight basic slopes, until the Gemini (which moves at a slope of five-to-one) was constructed as late as in 2010! Gemini's starting position is massive and doesn't fit inside a box of $10^6\times 10^6$ cells, so improving the size of such a spaceship was a problem among Life enthusiasts. This problem was greatly improved by computer search, resulting in Sir Robin, which moves in the direction of a knight (two-to-one slope.) Finding another so-called "knightship" that fits within Sir Robin's bounding box would require at most a naive brute-force search of $2^{31\times 79}$ positions.
  • A Garden of Eden is a state that is not the image of some previous state. The smallest known Garden of Eden is this one, and details can be found here. Finding a smaller GoE is a straightforward computer search with an explicit upper bound: $2^{10\times 10}$ states needs to be examined, at most. The smallest known example was found by searching for GoE with an additional symmetry, and is thus the smallest symmetric (in some sense) GoE.
$\endgroup$
4
$\begingroup$

Is there always a prime in the interval $(x^3,(x+1)^3]$ for every natural number $x\geq 2$?

Equivalently the interval may be changed to $[x^3,(x+1)^3]$. Assuming the Riemann hypothesis, this is provable via the inequality $\textrm{li}(x)-\frac{\sqrt{x}\log x}{8\pi}<\pi(x)<\textrm{li}(x)+\frac{\sqrt{x}\log x}{8\pi}$ due to Schoenfeld.(1) Without assuming RH, this has been proven for $x\geq e^{e^{15}}$.(2)

(1): Caldwell, Cheng, Detetmining Mills' Constant and a Note on Honaker's Problem, 2013.

(2): Cheng, Explicit Estimate on Primes between Consecutive Cubes, 2013.

$\endgroup$
1
  • 1
    $\begingroup$ As discussed in the first paper linked, this then also impacts bounding the Mills' constant, whose often cited value 1.306... is conditional on knowing primes exist in such intervals. $\endgroup$
    – Wojowu
    May 17, 2023 at 23:17
3
$\begingroup$

It is thought that it is more difficult to calculate the permanent of an $n\times n$ matrix than to calculate the determinant of the matrix.

However, even for $4\times 4$ matrices this problem seems far out of reach - calculating the determinant of a $4\times 4$ matrix requires least 37 arithmetic operations, yet it would naively require evaluating about $10^{123}$ different programs to prove that the permanent of a $4\times 4$ matrix cannot be calculated in 37 or fewer operations. See Aaronson's slides from 2007.

(I know this doesn't perfectly fit the desiribles of the OP, but at least it's a reasonably important open problem outside of additive number theory that is finite but presently infeasible.)

$\endgroup$
1
  • 1
    $\begingroup$ If one asks for circuits for the permanent over the reals or complex numbers, then this isn't obviously a finite problem, but is reduced to one by the theory of (effective) quantifier elimination, as in Joel David Hamkin's answer. So I would say this counts! $\endgroup$ Sep 28, 2022 at 14:07
2
$\begingroup$

Computing Ramsey numbers or even tighter bounds on them is perhaps a prototypical example that fits the bill.

$\endgroup$
3
  • 4
    $\begingroup$ I think you need to read the question more carefully -- computation of Ramsey numbers is obviously a finite problem that can be brute-forced. The question asks for problems which cannot obviously solved by computation, but have since been reduced (nontrivially) to an (infeasible) computation. $\endgroup$ Nov 14, 2012 at 0:37
  • 2
    $\begingroup$ I like this example. But we can go a bit further: For finite $n$ and small infinite countable ordinals $\alpha$, the value of the Ramsey numbers $r(\alpha,n)$ is an infinitary problem that can be reduced to some Ramsey-theoretic finite problems, typically unfeasible. I'll be happy to elaborate, but here is an example: $r(\omega\cdot 2,3)=\omega\cdot 4$, as shown by Erdős and Rado, because 4 is the smallest number $k$ needed to ensure that any 2-coloring of the complete digraph on $k$ vertices either contains a red complete digraph on 2 vertices, or a blue transitive tournament on 3 vertices. $\endgroup$ Nov 14, 2012 at 4:22
  • $\begingroup$ @Harry: true, true! @Andres: please elaborate---sounds quite cool. $\endgroup$
    – Suvrit
    Nov 14, 2012 at 4:27
2
$\begingroup$

Jacobsthal's function $g(n)$ for a positive integer $n$ gives the smallest number $g$ such that any interval of consecutive integers of length $g$ contains an integer coprime to $n$. I have been working on bounding this function for a while now, hoping to beat lower bounds near $k \log k$ (many researchers, most recently Konyagin-Ford-Green-Maynard-Tao) and upper bounds $(k\log k)^2$ (Iwaniec), where $k$ is the number of distinct prime factors of $n$.

Some have wondered about Jacobsthal's $C(k)$, which is the maximum over all $n$ with $k$ distinct prime factors of $g(n)-1$. (Read Jacobsthal's 1961 paper for why this definition.) It is not immediately clear that one should check only finitely many cases to determine $C(k)$, however a nice argument in Hajdu and Saradha's paper "Disproof of a Conjecture of Jacobsthal" shows that indeed only a finite number of $n$ need to be checked. Further, the maximum does not always occur at $n =P_k= \prod_{1 \leq i \leq k} p_i$, the product of the first $k$ primes. Although exact computations have been carried out for $k \lt 50$ for $g(P_k)$, $C(k)$ seems to be known only up to $k=24$.

Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2015.05.15

$\endgroup$
2
  • 2
    $\begingroup$ Konyagin not Kolyvagin $\endgroup$
    – Lucia
    May 15, 2015 at 16:06
  • 1
    $\begingroup$ Thanks. Will fix. Apologies to both Kolyvagin and Konyagin Gerhard "Do Not Call Me Passman" Paseman, 2015.05.15 $\endgroup$ May 15, 2015 at 16:08
2
$\begingroup$

At the turn of the 21st century, Catalan's conjecture that $8$ and $9$ are the only non-trivial consecutive powers was reduced to a finite but intractable problem.

For example, it was known that to prove that

$$3^2-2^3=1$$

are the only non-trivial integral solutions to

$$x^p-y^q=\pm 1$$

required checking a finite number of $p$'s and $q$'s with $\max(p,q)=8\times10^{16}$.

However, in 2002 Mihăilescu proved the conjecture in its entirety.

See, e.g., Metsänkylä's AMS article, especially § 4 titled "Can the Problem be Solved by a Computer?"

Although it's not 'open', I think this is in the spirit of the question.

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