Unsolved Problems due to Lack of Computational Power

Question

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)

I am looking for specific examples.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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!

Answer 10

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.

Answer 11

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

Answer 12

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

Answer 13

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.

The lower bound is currently (as of 2021) only 13, leading a large gap between 13 and G to be improved by computation.

Answer 14

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.

Answer 15

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.

Answer 16

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

Answer 17

The Great Internet Mersenne Prime Search (GIMPS) comes to mind. It's all about using computational muscle to find larger Mersenne primes.

Mersenne primes are primes of the form $2^n-1$. There are $51$ which are known, including the largest known prime number. But there are conjectured to be infinitely many.

Answer 18

One example is the diophantine equation $x^y+y^z=z^x$ for positive integers $x, y, z$. In the paper https://www.researchgate.net/publication/267106572_On_the_Diophantine_equation_ax_y_by_z_cz_x_0 they proved that all the positive integer solutions satisfy $max(x,y,z) \leq e^{e^{e^5}}$. Thus the problem is reduced to a finite but very large computation.