# Important open problems that have already been reduced to a finite but infeasible amount of computation

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.

-
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... – fedja Nov 11 '12 at 18:52
@fedja Let us say "for some value of important'." Please do post. – David Feldman Nov 11 '12 at 18:58
I think that the homotopy groups of spheres falls into thi category. – Lunasaurus Rex Nov 11 '12 at 19:40
@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). – quid Nov 11 '12 at 19:56
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. – Sam Hopkins Nov 11 '12 at 21:43

## 14 Answers

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.

-

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.

-
How is this comment related to the answer on which it was left? It would go better as an independent answer. – John Pardon Nov 12 '12 at 0:37
Looks like a correct answer to me. – Brendan McKay Nov 14 '12 at 5:32
@Brendan McKay: the comment of unknown (which I assime motivated your comment) refers explicitly to a comment asking how it is related to the answer, as opposed to the answer (related to the question). Indeed, there was a comment, meanwhile deleted, really completely unrelated to the answer (though perhaps not the question, if I rememeber well, yet was at least clearly posted at the wrong place in the thread). – quid Nov 14 '12 at 10:17

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.

-
It was an important enough problem to award a Fields medal in 1954! – Denis Serre Nov 14 '12 at 8:22

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

-
I'm not sure what the use of the word "constant" means here, because the time depends on $t$. Do you mean "finite"? – Will Sawin Nov 12 '12 at 0:09
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. – Tony Huynh Nov 12 '12 at 1:04
Are any bounds known for f, or, say, f(7)? – Nate Eldredge Mar 31 '14 at 12:05
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 ) – Dominic van der Zypen Sep 10 '14 at 14:04

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.

-
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. – Ben Crowell Nov 14 '12 at 6:54
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. – joro Nov 14 '12 at 7:06
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. – Joel David Hamkins Nov 14 '12 at 17:21

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.

-
This was also discussed in the comments, but it is nice to have a more detailed version. – quid Nov 14 '12 at 11:04
Good point! Sorry, I missed the earlier discussion. – Nick Gill Nov 14 '12 at 12:10

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

-

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.

-

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.

-
Interesting problem, but it is a finite computation by definition, so no nontrivial reduction :-) – joro Nov 14 '12 at 7:49
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. – Noam D. Elkies May 16 at 0:31

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

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

-

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

-
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. – Harry Altman Nov 14 '12 at 0:37
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. – Andrés Caicedo Nov 14 '12 at 4:22
@Harry: true, true! @Andres: please elaborate---sounds quite cool. – Suvrit Nov 14 '12 at 4:27

In Conways game of life, 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.

It is a straigtforward 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

-

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

-
Konyagin not Kolyvagin – Lucia May 15 at 16:06
Thanks. Will fix. Apologies to both Kolyvagin and Konyagin Gerhard "Do Not Call Me Passman" Paseman, 2015.05.15 – Gerhard Paseman May 15 at 16:08