55
$\begingroup$

I was recently reading up about computational power and its uses in maths particularly to find counterexamples to conjectures. I was wondering are there any current mathematical problems which we are unable to solve due to our lack of computational power or inaccessibility to it.

What exactly am I looking for?

Problems of which we know that they can be solved with a finite (but very long) computation?

(e. g. NOT the Riemann hypothesis or twin prime conjecture)

FROM THE COMMENTS

(Maybe this will be helpful for people to understand the question in a better way if they don't already.)

There is a simple algorithm which simply lists all statements provable in ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems I AM interested in is precisely the class of open problems which are known to not be independent from ZFC.

I am looking for specific examples.

$\endgroup$
  • 2
    $\begingroup$ What exactly are you looking for? Problems of which we know that they can be solved with a finite (but very long) computation? (e. g. not the Riemann hypothesis or twin prime conjecture) $\endgroup$ – 0x539 Aug 16 at 20:49
  • 7
    $\begingroup$ Near duplicate on MO mathoverflow.net/q/112097/30186 $\endgroup$ – Wojowu Aug 17 at 9:39
  • 4
    $\begingroup$ Perhaps Skewes' number, the least $x$ for which $\pi(x)\le li(x)$. $\endgroup$ – DanielWainfleet Aug 17 at 11:47
  • 3
    $\begingroup$ The first thing I thought of is chess — 8-piece tablebases are currently on the bubble, and position counts at ply N are only up to N=13 or something — but not sure that’s “math” by your definition. $\endgroup$ – Jeff Y Aug 17 at 12:42
  • 3
    $\begingroup$ As @MarcGlisse mentions, there is a simple algorithm which simply lists all statements provable in ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems the OP is interested in is precisely the class of open problems which are known to not be independent from ZFC. $\endgroup$ – Jim Belk Aug 18 at 9:12

16 Answers 16

70
$\begingroup$

Goldbach's weak conjecture isn't a conjecture anymore, but before it was proved (in 2013), it had already been proved that it was true for every $n>e^{e^{16\,038}}$. It was not computationally possible to test it for all numbers $n\leqslant e^{e^{16\,038}}$ though.

$\endgroup$
  • 40
    $\begingroup$ It's always pretty strange to see the "random" bounds such as this one in number theory $\endgroup$ – Yuriy S Aug 17 at 18:33
  • 2
    $\begingroup$ This is exactly the example that I had in mind when reading the question. $\endgroup$ – Sebastian Bechtel Aug 18 at 12:09
46
$\begingroup$

Some notorious problems of this kind are in discrete mathematics but involve a search space that is many magnitudes beyond what is feasible. For example, the values of certain Ramsey numbers or the existence of a Moore graph of degree 57.

$\endgroup$
  • 27
    $\begingroup$ Ramsey numbers are the canonical “unfeasible computation”. As Erdős said, paraphrased by Joel H. Spencer: “Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” On the other hand [cont’d], $\endgroup$ – Peter LeFanu Lumsdaine Aug 17 at 10:08
  • 2
    $\begingroup$ [cont’d] …values of Ramsey numbers may not quite be what the OP is after, since they’re not typically considered as “counterexamples to a conjecture” (although of course they can be seen as such, in contrived ways). $\endgroup$ – Peter LeFanu Lumsdaine Aug 17 at 10:09
  • 1
    $\begingroup$ @PeterLeFanuLumsdaine: That is shockingly delightful! $\endgroup$ – Daniel R. Collins Aug 18 at 4:24
24
$\begingroup$

If you are including games as part of “math”, chess provides some nice unsolved problems due to computational limits. The game of chess itself cannot even be weakly solved (https://en.m.wikipedia.org/wiki/Solved_game#Overview). But strong solutions are known for a subset of chess positions, those with seven or fewer (total) pieces on the board. These are called (endgame) tablebases: https://en.m.wikipedia.org/wiki/Endgame_tablebase#Background. Any position with eight or more pieces is currently at or beyond present computational resources (chess games start with 32 pieces).

Another source of difficult computation around chess is counting total positions (of certain types) after a certain number of moves. Such as the number of chess games ending in checkmate in exactly N plies (moves by one side), which is presently only known for N <= 13: https://oeis.org/A079485. Or just the total number of possible chess games consisting of N plies, which is presently only known for N <= 14: https://oeis.org/A048987.

$\endgroup$
  • 3
    $\begingroup$ Completely unimportant, but the number of games is known up to 15 ply: wismuth.com/chess/statistics-games.html $\endgroup$ – A. Rex Aug 18 at 15:55
  • 2
    $\begingroup$ What is your source for "the game of chess itself cannot even be weakly solved"? The article you linked itself calls this "speculation", which it might well be despite the sprawling game tree. $\endgroup$ – kviiri Aug 19 at 17:43
  • $\begingroup$ @kviiri Probably it means "cannot currently be weakly solved", i.e. no one has done it yet or currently has a good plan to do it. $\endgroup$ – Will Sawin Aug 20 at 3:25
  • $\begingroup$ @kviiri Yes, the context is "with today's computational (and storage) resources". As the article notes, any finite game is theoretically solvable. But considering the known effort and resources it took to weakly solve checkers, and knowing that chess is an orders-of-magnitude larger game... Nowhere close. $\endgroup$ – Jeff Y Aug 22 at 13:34
  • $\begingroup$ Here's another explanation of why any claim of (weakly) solving even most chess openings (subsets of chess) in the current day is always firmly in the realm of spoofs: en.chessbase.com/post/the-chebase-april-fools-revisited They had published the spoof, which fooled many people, including me, a few days earlier: en.chessbase.com/post/… $\endgroup$ – Jeff Y Aug 22 at 13:52
24
$\begingroup$

Historically, a very important, computationally intensive problem arising from physics was lattice QCD (LQCD). LQCD is a theoretical framework for computing basic quantities like the mass of the proton, and it was introduced by Ken Wilson back in the 70's. However, after some initial successes, this approach stagnated due to a lack of computer power. The basic problem is that our universe has an obnoxiously large number of dimensions (four, in case you were wondering), and doing integrals in four dimensions takes an insane amount of memory. I heard a story that Ken Wilson gave a talk at a conference on LQCD where he declared that "Lattice QCD is dead" as long as a certain 4D integral could not be computed, as was the case at the time he said this.

Several years (or decades) later, computer technology matured to the point that said integral could be computed, and then LQCD theory picked right back up where it left off. Today it is again a flourishing discipline. However, other problems arising from LQCD continue to push supercomputer technology. Apparently LQCD is used as a benchmark for supercomputers nowadays.

$\endgroup$
21
$\begingroup$

Packing problems come to mind, i.e. how to achieve the densest packing of some kind of geometric objects, such as spheres or dodecahedrons. The interesting thing is that this is not a discrete problem, as there are uncountably many irregular, non-periodic packings that need to be checked. Still, the original proof of the sphere packing problem managed to turn this into a finite number of linear programming problems which then could be solved on a computer.

In theory you can use the same approach for objects other than spheres or in higher dimensions (and indeed people do), but in practice you reach a point quite soon, where there is simply not enough computing power to solve the resulting problems.

$\endgroup$
15
$\begingroup$

Is $e^{e^{e^{79}}}$ an integer? See this question for some background. Many other problems of this type are also technically unsolved, although the answer is almost definitely "no". This can be verified by a finite computation, but the sheer size of the numbers involved means that this is not feasible at the moment.

Note: as pointed out by @ruakh, if $e^{e^{e^{79}}}$ were, in fact, an integer, then a naïve finite computation would not be able to resolve the question. [Of course, this seems highly unlikely, but it is not known to be false absent proof.]

$\endgroup$
  • $\begingroup$ Nice to know about this. Thanks for pointing it out $\endgroup$ – StackUpPhysics Aug 18 at 13:29
  • 1
    $\begingroup$ This answer is thought-provoking (+1), but as far as I can tell it's not actually correct: if the answer is "no" then that could be verified by a finite computation that approximated it closely enough to rule out the neighboring integers; but if the answer is "yes" then there's no obvious computational way to prove it. All we could show is that it's within ε of an integer for ridiculously small values of ε. (In fact, this very issue was the motivation for the question you link to: see https://math.stackexchange.com/a/13052/19345.) $\endgroup$ – ruakh Aug 20 at 5:53
  • $\begingroup$ @ruakh Wow, I hadn't thought of that. You're right, I will edit the answer to reflect that later. $\endgroup$ – YiFan Aug 20 at 10:23
12
$\begingroup$

It is strongly believed that the second Hardy-Littlewood conjecture is false, because it contradicts the first Hardy-Littlewood conjecture, which has the backing of not only the probabilistic heuristic but also a lot of recent work. The second link even states that if the first conjecture (also called the prime $k$-tuples conjecture) holds, then there are in fact infinitely many positive integers $x$ such that $π(x+3159)-π(x) = 447 > 446 = π(3159)$. This is obviously something that can be verified with sufficient computational power (simply test every positive integer $x$ until you find one that satisfies the desired inequality), but clearly it has not been done yet otherwise we would have heard news of it!

$\endgroup$
  • $\begingroup$ Interesting to get to know about this. Haven't heard about this conjecture before $\endgroup$ – StackUpPhysics Aug 18 at 13:28
  • $\begingroup$ I don't think this answers the question. It's structurally very similar to disproving the Riemann hypothesis, which is explicitly given as an example of something the OP doesn't want. $\endgroup$ – Brady Gilg Aug 19 at 16:26
  • $\begingroup$ @BradyGilg: Note that I answered the question before it was significantly changed. Besides, this is quite different from disproving RH because people believe RH is true (so it shouldn't be disprovable) whereas people believe that the conjecture stated in my post is true and hence provable by a finite computation. $\endgroup$ – user21820 Aug 19 at 17:00
8
$\begingroup$

Optimal sorting networks for $n>10$.

For small, fixed numbers of inputs n, optimal sorting networks can be constructed, with either minimal depth (for maximally parallel execution) or minimal size (number of comparators)... The following table summarizes the known optimality results:

$$ \begin{array}{l|ccccccccccccccccc|} \hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \\ \hline \text{Depth} & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \\ \hline \text{Size, upper bound} & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \\ \hline \text{Size, lower bound (if different)} & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \\ \hline \end{array} $$

$\endgroup$
  • 1
    $\begingroup$ can you elaborate in the answer? $\endgroup$ – Kai Aug 18 at 17:15
  • $\begingroup$ @ Kai : updated $\endgroup$ – g.kov Aug 18 at 18:50
7
$\begingroup$

Euler's conjecture that it takes $n$ $n$th powers to sum to an $n$ power is true for $n=3$ but proven false for $n=4,5$, for example,

$$27^5+ 84^5+110^5+ 133^5= 144^5\qquad\text{(found in 1966)}$$ $$95800^4 + 217519^4 + 414560^4 = 422481^4\qquad\text{(found in 1988)}$$

but nobody knows if it is false for any or all $n\geq6$. There are heuristics that suggest,

$$x_1^6+x_2^6+\dots+x_5^6 = z^6$$

has positive solutions as well and a fast enough computer might find it. For the moment, such computational power is not available to individuals.

$\endgroup$
  • 4
    $\begingroup$ Interesting problem, but it does not seem to match: "Problems of which we know that they can be solved with a finite (but very long) computation? " (my emphasis). $\endgroup$ – quid Aug 18 at 11:32
6
$\begingroup$

The order of every finite projective plane is a prime power. If this is false, a counterexample can be constructed by exhaustive search of all non-prime powers in increasing order. This has been done by hand for $n=6$ and by computer for $n=10$, but as far as I know, $n=12$ is still out of reach, or at least, it hasn't been done.

$\endgroup$
  • 4
    $\begingroup$ My understanding of the question suggests that this isn't an example unless there's some upper bound at which point we can stop. My interpretation of the question is the problems need to be computationally decidable, not semidecidable. Otherwise, we could say of any (formal) theorem that "if it's 'true', then we can enumerate proofs until we find its proof". Of course, you could say the $n=12$ case is decidable, but it still seems to miss the spirit of the question unless there's something special about this case. I could just as well ask if a theorem has a proof of size at most $N$. $\endgroup$ – Derek Elkins Aug 18 at 1:57
  • $\begingroup$ An alternative conjecture used to be that a finite projective plane exists for every order not ruled out by the Bruck-Ryser theorem. Orders 6 and 14 are so ruled out, but orders 10 and 12 are not. This conjecture is, of course, dead now that a plane of order 10 has been ruled out by computational means. But I think many people still would like to know whether a plane of order 12 exists. $\endgroup$ – Will Orrick Aug 18 at 12:23
  • $\begingroup$ Is it believed that there is a finite projective plane with order not a prime power? $\endgroup$ – user21820 Aug 19 at 15:03
  • $\begingroup$ @user21820 I'm not a worker in the field, so I can't really say. In 1995, Gary Mullen suggested it as a candidate for "the next Fermat problem" Unfortunately, Springer doesn't make the whole article available publicly. The MOLS problem he discusses is equivalent to the finite projective plane problem. See pi.math.cornell.edu/~web4520/CG9-0.pdf $\endgroup$ – saulspatz Aug 19 at 15:18
  • 1
    $\begingroup$ @user21820 Some remarks: (1) In one formulation the problem is to construct a $(q^2+q+1)\times(q^2+q+1)$ matrix $M$ with elements 0 and 1 having $(q+1)$ 1s in every row and column and satisfying $MM^T=qI+J$,where $J$ is the all 1s matrix. (2) If one requires only that $M$ have rational elements in the relation $MIM^T=qI+J$ then the Hasse-Minkowski criterion for the rational equivalence of quadratic forms given by $I$ and $qI+J$ implies that such an $M$ exists if and only if the Bruck-Ryser conditions are satisfied. Ryser attempted to strengthen the Bruck-Ryser result by incorporating... $\endgroup$ – Will Orrick Aug 27 at 13:46
4
$\begingroup$

Littlewood proved in 1914 that there exists a number $n\in\mathbb{N}$ (called Skewes' number) such that:

$$ \pi(n) > \operatorname{li}(n), $$

where $\pi(n)$ is the amount of primes below $n$ and $\operatorname{li}(n)$ denotes the logarithmic integral $\displaystyle \int_0^n \frac{dt}{\ln t}$.

It is conjectured that $n$ is a huge number, recent analysis suggests $n\approx e^{727.951}$. Since then, researchers have worked to find lower and upper bounds for $n$. Currently it is held that:

$$ 10^{19}<n<e^{727.951}. $$

No such number has been found yet.

$\endgroup$
  • $\begingroup$ Is it actually believed that Skewes' number is $\approx e^{727}$? I thought I'd previously read that a crossing point is there but not necessarily the least crossing point (Skewes'), which as you point out could be as low as $10^{19}$ $\endgroup$ – Jam Aug 20 at 0:31
3
$\begingroup$

There was the question: Are there m consecutive positive integers from k to k+m-1 which contain more primes than the m integers from 2 to m+1?

The problem itself is unsolved, but there is a hypothesis with the twin-prime hypothesis as the simplest special case:

Given n ≥ 2, and n integers $0 = k_1 < k_2 < ... < k_n$, and for every prime p ≤ n the set of remainders $k_i \mod p$ has fewer than p elements, then there are infinitely many integers p such that $p + k_i$ is prime for every 1 ≤ i ≤ n.

If there are n primes from 2 to 2+m-1, and we find $k_1$ to $k_{n+1}$ with $k_{n+1} ≤ m-1$, then the hypothesis is that there are infinitely many sequences of m consecutive integers containing n+1 primes.

Finding such a sequence was quite hard but was done. I think there are sequences known that point to 5 more primes in m consecutive integers than in 2 to m-1, but beyond that it's limited by processing power (or by willingness to use that processing power).

$\endgroup$
  • 1
    $\begingroup$ The 1st paragraph is called the Hardy-Littlewood 2nd conjecture, the 3rd paragraph id called the Hardy-Littlewood 1st conjecture, see the answer from user21820. $\endgroup$ – Gerry Myerson Aug 20 at 0:52
3
$\begingroup$

The number of distinct magic squares, for deceptively small sizes

A magic square of order $n$ is a square grid of $n \times n$ boxes where each box contains one distinct integer from the interval $[1 .. n^2]$, so that the sums of the numbers on each row, on each column and on each of the two diagonals are equal to each other. They have been studied for millenia by mathematicians in China, India and Persia, and continue to be of interest to both hobbyist and professional mathematicians.

The smallest magic squares, excluding the trivial case where $n = 1$, are of order $3$. This is one of them:

\begin{array}{|c|c|c|} \hline 8 & 3 & 4 \\ \hline 1 & 5 & 9 \\ \hline 6 & 7 & 2 \\ \hline \end{array}

In a sense, this is the only solution to the problem of this size: the other 7 magic squares of order 3 are mirrored and/or rotated versions of this grid.

We know the number of magic squares of orders 3, 4 and 5. The number of magic squares of order 6 is not known, but is believed to be in the order of $10^{19}$. The number of magic squares is not known for any order greater than 6 either. It should be noted that constructing magic squares of odd and doubly-even (divisible by four) orders is generally regarded as a simpler feat than constructing magic squares of singly-even orders like 6, although this may not guarantee the ease of enumerating all magic squares of such order over enumerating those of orders of smaller singly even numbers.

This problem is trivially solvable if the computational power constraint wouldn't stop us: we could just enumerate all $36!$ possible ways to fit the numbers in the grid, and check each for magic number property. In practice, we can apply a fair bit of pruning to explore only a small fraction of this space. We know the sum that should appear on each row/column/diagonal and we know that only an eighth of the configurations need to be checked to account for their mirrored and/or rotated copies; these and further insights or heuristics may be enough to make the problem computationally tractable for a well-supplied research effort in the coming years.

However, this is in a sense cop-out; even if we solve the number of magic squares of order 6, we'll still be left wondering what the number of magic squares of order 7 and greater might be --- that is, unless someone figures out a more efficient way to compute it than raw enumeration.

$\endgroup$
1
$\begingroup$

What are the odds in Klondike Solitare? An attempt was made based on perfect knowledge yielding 79%, but the player doesn't have perfect knowledge. There's a bunch of Monte-Carlo results on that site; but a direct attack is far beyond reach, and it's not even known if the strategy they're using is actually optimal.

"One of the embarrassments of applied mathematics that we cannot determine the odds of winning the common game of solitaire."

$\endgroup$
0
$\begingroup$

I believe a problem connected with Graham's number is one of the things you are looking for. It is an upper bound to problem in Ramsey theory, that looks for a number $N$ satisfying certain criteria. I do not know much about that, but you can read more here https://en.wikipedia.org/wiki/Graham%27s_number .

But from my understanding, there are bounds on the number $N$, however the range of possible values derived from those bounds is still enormously large, way beyond computational possibilities of today (and probably ever). But with arbitrarily large, yet still finite computational power, the problem could be solved.

$\endgroup$
-2
$\begingroup$

Prime gaps - https://en.wikipedia.org/wiki/Prime_gap - of maximum known merit are found by increasing CPU (and GPU) computational power on the gapcoin network. See: https://gapcoin.club

... So the difficulty will simply be the length of the prime gap?

Not exactly. The average length of a prime gap with the starting prime p, is log(p), which means that the average prime gap size increases with lager primes. Then, instead of the pure length, we use the merit of the prime gap, which is the ratio of the gap's size to the average gap size.

Let p be the prime starting a prime gap, then m = gapsize/log(p) will be the merit of this prime gap.

Also a pseudo random number is calculated from p to provide finer difficulty adjustment.

Let rand(p) be a pseudo random function with 0 less than rand(p) less than 1. Then, for a prime gap starting at prime p with size s, the difficulty will be s/log(p) + 2/log(p) * rand(p), where 2/log(p) is the average distance between a gap of size s and s + 2 (the next greater gap) in the proximity of p.

When it actually comes to mining, there are two additional fields added to the Blockheader, named “shift” and “adder”. We will calculate the prime p as sha256(Blockheader) * 2^shift + adder. As an additional criterion the adder has to be smaller than 2^shift to avoid that the PoW could be reused. ...

Source: gapcoin.org

...

https://web.stanford.edu/~tonyfeng/bounded_gaps.pdf

... (Twin prime conjecture) ...

... This is a just a special case of a far-reaching conjecture of Hardy and Lit- tlewood describing the frequency of prime gaps of any sizes. The Hardy- Littlewood conjecture predicts not only how often twin primes occur, but also how often any finite tuple of the form ( n + h 1 , n + h 2 , . . . , n + h k ) consists en- tirely of prime numbers. But even though analytic number theorists have be- lieved for many years that they know the answers to these questions, progress towards proving the existence of small gaps between primes has been slow. As recently as 2005 , the problem of establishing infinitely many bounded gaps be- tween primes was considered by many mathematicians to be “hopeless” ...

...

Further,

List of unsolved problems in mathematics: https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics

$\endgroup$
  • $\begingroup$ The OP wants a problem that is known to be solvable with a finite algorithm, which afaik is not known to exist for finding either the primegap of maximum merit nor the twin prime conjecture. $\endgroup$ – Jam Aug 20 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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