Unsolved Problems (Not Independent of ZFC) due to Lack of Computational PowerIs there any conjecture that we know is provable/disprovable but we haven't found a proof of yet?How to show $e^e^e^79$ is not an integer$e^e^e^79$ and ultrafinitismTheorems true “with probability 1”?Can all maths be represented in geometry?Examples of falsified (or currently open) longstanding conjectures leading to large bodies of incorrect results.Big-Daddy-Conjectures and Hierarchy of Mathematical ConjecturesFormal notion of computational contentFirst job in industry for a pure, pure mathematics folkAlgorithmic procedure to establish the possibility of finding a proof of a conjenctureHow to know if one problem is more difficult than another one?
Pen test results for web application include a file from a forbidden directory that is not even used or referenced
Why do IR remotes influence AM radios?
What should be done with the carbon when using magic to get oxygen from carbon dioxide?
Count the number of triangles
What does it mean to move a single flight control to its full deflection?
Cutting numbers into a specific decimals
If the integral of a series of functions converges to zero, does that series also converge pointwise to zero?
If I said I had $100 when asked, but I actually had $200, would I be lying by omission?
Can a network vulnerability be exploited locally?
Is the Amazon rainforest the "world's lungs"?
What checks exist against overuse of presidential pardons in the USA?
Why did Lucius make a deal out of Buckbeak hurting Draco but not about Draco being turned into a ferret?
Wrong Stamping of UK Visa
Coupling two 15 Amp circuit breaker for 20 Amp
Looking for a plural noun related to ‘fulcrum’ or ‘pivot’ that denotes multiple things as crucial to success
Why is there no Disney logo in MCU movies?
Why did the population of Bhutan drop by 70% between 2007 and 2008?
Board Chinese train at a different station (on-route)
In Endgame, wouldn't Stark have remembered Hulk busting out of the stairwell?
Normalized Malbolge to Malbolge translator
How could a self contained organic body propel itself in space
Defending Castle from Zombies
How to prevent a hosting company from accessing a VM's encryption keys?
Fantasy Macro Economics: What would Merfolk trade for?
Unsolved Problems (Not Independent of ZFC) due to Lack of Computational Power
Is there any conjecture that we know is provable/disprovable but we haven't found a proof of yet?How to show $e^e^e^79$ is not an integer$e^e^e^79$ and ultrafinitismTheorems true “with probability 1”?Can all maths be represented in geometry?Examples of falsified (or currently open) longstanding conjectures leading to large bodies of incorrect results.Big-Daddy-Conjectures and Hierarchy of Mathematical ConjecturesFormal notion of computational contentFirst job in industry for a pure, pure mathematics folkAlgorithmic procedure to establish the possibility of finding a proof of a conjenctureHow to know if one problem is more difficult than another one?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$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.
soft-question computer-science computational-mathematics big-list computer-assisted-proofs
$endgroup$
|
show 22 more comments
$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.
soft-question computer-science computational-mathematics big-list computer-assisted-proofs
$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
6
$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
|
show 22 more comments
$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.
soft-question computer-science computational-mathematics big-list computer-assisted-proofs
$endgroup$
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.
soft-question computer-science computational-mathematics big-list computer-assisted-proofs
soft-question computer-science computational-mathematics big-list computer-assisted-proofs
edited Aug 19 at 19:42
community wiki
10 revs, 4 users 95%
StackUpPhysics
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
6
$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
|
show 22 more comments
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
6
$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
2
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
$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
6
6
$begingroup$
Near duplicate on MO mathoverflow.net/q/112097/30186
$endgroup$
– Wojowu
Aug 17 at 9:39
$begingroup$
Near duplicate on MO mathoverflow.net/q/112097/30186
$endgroup$
– Wojowu
Aug 17 at 9:39
4
4
$begingroup$
Perhaps Skewes' number, the least $x$ for which $pi(x)le li(x)$.
$endgroup$
– DanielWainfleet
Aug 17 at 11:47
$begingroup$
Perhaps Skewes' number, the least $x$ for which $pi(x)le li(x)$.
$endgroup$
– DanielWainfleet
Aug 17 at 11:47
3
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
$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
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
$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
|
show 22 more comments
16 Answers
16
active
oldest
votes
$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 $nleqslant e^e^16,038$ though.
$endgroup$
36
$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
1
$begingroup$
This is exactly the example that I had in mind when reading the question.
$endgroup$
– Sebastian Bechtel
Aug 18 at 12:09
add a comment |
$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
add a comment |
$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
add a comment |
$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$
3
$begingroup$
A recent result: arxiv.org/abs/1406.4088
$endgroup$
– Count Iblis
Aug 18 at 2:16
$begingroup$
Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
$endgroup$
– Yly
Aug 19 at 18:23
add a comment |
$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$
add a comment |
$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
$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
add a comment |
$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
add a comment |
$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:
$$ beginarrayl hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \ hline textDepth & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \ hline textSize, upper bound & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \ hline textSize, lower bound (if different) & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \ hline endarray $$
$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
add a comment |
$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^5qquadtext(found in 1966)$$
$$95800^4 + 217519^4 + 414560^4 = 422481^4qquadtext(found in 1988)$$
but nobody knows if it is false for any or all $ngeq6$. 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
add a comment |
$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
2 days ago
|
show 5 more comments
$begingroup$
Littlewood proved in 1914 that there exists a number $ninmathbbN$ (called Skewes' number) such that:
$$
pi(n) > operatornameli(n),
$$
where $pi(n)$ is the amount of primes below $n$ and $operatornameli(n)$ denotes the logarithmic integral $displaystyle int_0^n fracdtln t$.
It is conjectured that $n$ is a huge number, recent analysis suggests $napprox 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
add a comment |
$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
add a comment |
$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:
beginarrayc
hline
8 & 3 & 4 \ hline
1 & 5 & 9 \ hline
6 & 7 & 2 \ hline
endarray
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$
$begingroup$
Reading this Parker's Square comes to my mind if you know what I mean
$endgroup$
– StackUpPhysics
Aug 19 at 18:44
$begingroup$
The reference if you didn't get it- bradyharanblog.com/the-parker-square
$endgroup$
– StackUpPhysics
Aug 19 at 19:41
add a comment |
$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$
add a comment |
$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$
add a comment |
$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
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3325462%2funsolved-problems-not-independent-of-zfc-due-to-lack-of-computational-power%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
16 Answers
16
active
oldest
votes
16 Answers
16
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 $nleqslant e^e^16,038$ though.
$endgroup$
36
$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
1
$begingroup$
This is exactly the example that I had in mind when reading the question.
$endgroup$
– Sebastian Bechtel
Aug 18 at 12:09
add a comment |
$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 $nleqslant e^e^16,038$ though.
$endgroup$
36
$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
1
$begingroup$
This is exactly the example that I had in mind when reading the question.
$endgroup$
– Sebastian Bechtel
Aug 18 at 12:09
add a comment |
$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 $nleqslant e^e^16,038$ though.
$endgroup$
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 $nleqslant e^e^16,038$ though.
edited Aug 16 at 21:29
community wiki
José Carlos Santos
36
$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
1
$begingroup$
This is exactly the example that I had in mind when reading the question.
$endgroup$
– Sebastian Bechtel
Aug 18 at 12:09
add a comment |
36
$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
1
$begingroup$
This is exactly the example that I had in mind when reading the question.
$endgroup$
– Sebastian Bechtel
Aug 18 at 12:09
36
36
$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
$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
1
1
$begingroup$
This is exactly the example that I had in mind when reading the question.
$endgroup$
– Sebastian Bechtel
Aug 18 at 12:09
$begingroup$
This is exactly the example that I had in mind when reading the question.
$endgroup$
– Sebastian Bechtel
Aug 18 at 12:09
add a comment |
$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
add a comment |
$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
add a comment |
$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$
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.
edited Aug 18 at 22:57
community wiki
2 revs, 2 users 57%
ahulpke
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
add a comment |
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
27
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
$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
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
$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
1
$begingroup$
@PeterLeFanuLumsdaine: That is shockingly delightful!
$endgroup$
– Daniel R. Collins
Aug 18 at 4:24
$begingroup$
@PeterLeFanuLumsdaine: That is shockingly delightful!
$endgroup$
– Daniel R. Collins
Aug 18 at 4:24
add a comment |
$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
add a comment |
$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
add a comment |
$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$
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.
answered Aug 17 at 19:51
community wiki
Jeff Y
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
add a comment |
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
3
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
$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
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$
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 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$
@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
$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
add a comment |
$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$
3
$begingroup$
A recent result: arxiv.org/abs/1406.4088
$endgroup$
– Count Iblis
Aug 18 at 2:16
$begingroup$
Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
$endgroup$
– Yly
Aug 19 at 18:23
add a comment |
$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$
3
$begingroup$
A recent result: arxiv.org/abs/1406.4088
$endgroup$
– Count Iblis
Aug 18 at 2:16
$begingroup$
Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
$endgroup$
– Yly
Aug 19 at 18:23
add a comment |
$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$
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.
answered Aug 18 at 1:39
community wiki
Yly
3
$begingroup$
A recent result: arxiv.org/abs/1406.4088
$endgroup$
– Count Iblis
Aug 18 at 2:16
$begingroup$
Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
$endgroup$
– Yly
Aug 19 at 18:23
add a comment |
3
$begingroup$
A recent result: arxiv.org/abs/1406.4088
$endgroup$
– Count Iblis
Aug 18 at 2:16
$begingroup$
Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
$endgroup$
– Yly
Aug 19 at 18:23
3
3
$begingroup$
A recent result: arxiv.org/abs/1406.4088
$endgroup$
– Count Iblis
Aug 18 at 2:16
$begingroup$
A recent result: arxiv.org/abs/1406.4088
$endgroup$
– Count Iblis
Aug 18 at 2:16
$begingroup$
Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
$endgroup$
– Yly
Aug 19 at 18:23
$begingroup$
Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
$endgroup$
– Yly
Aug 19 at 18:23
add a comment |
$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$
add a comment |
$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$
add a comment |
$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$
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.
answered Aug 17 at 7:47
community wiki
mlk
add a comment |
add a comment |
$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
$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
add a comment |
$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
$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
add a comment |
$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$
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.]
edited Aug 20 at 11:56
community wiki
2 revs
YiFan
$begingroup$
Nice to know about this. Thanks for pointing it out
$endgroup$
– StackUpPhysics
Aug 18 at 13:29
$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
add a comment |
$begingroup$
Nice to know about this. Thanks for pointing it out
$endgroup$
– StackUpPhysics
Aug 18 at 13:29
$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
$begingroup$
Nice to know about this. Thanks for pointing it out
$endgroup$
– StackUpPhysics
Aug 18 at 13:29
$begingroup$
Nice to know about this. Thanks for pointing it out
$endgroup$
– StackUpPhysics
Aug 18 at 13:29
$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$
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
$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
add a comment |
$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
add a comment |
$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
add a comment |
$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$
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!
answered Aug 18 at 3:16
community wiki
user21820
$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
add a comment |
$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
$begingroup$
Interesting to get to know about this. Haven't heard about this conjecture before
$endgroup$
– StackUpPhysics
Aug 18 at 13:28
$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$
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
$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
add a comment |
$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:
$$ beginarrayl hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \ hline textDepth & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \ hline textSize, upper bound & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \ hline textSize, lower bound (if different) & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \ hline endarray $$
$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
add a comment |
$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:
$$ beginarrayl hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \ hline textDepth & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \ hline textSize, upper bound & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \ hline textSize, lower bound (if different) & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \ hline endarray $$
$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
add a comment |
$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:
$$ beginarrayl hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \ hline textDepth & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \ hline textSize, upper bound & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \ hline textSize, lower bound (if different) & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \ hline endarray $$
$endgroup$
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:
$$ beginarrayl hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \ hline textDepth & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \ hline textSize, upper bound & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \ hline textSize, lower bound (if different) & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \ hline endarray $$
edited Aug 18 at 18:48
community wiki
2 revs
g.kov
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
add a comment |
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
1
1
$begingroup$
can you elaborate in the answer?
$endgroup$
– Kai
Aug 18 at 17:15
$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
$begingroup$
@ Kai : updated
$endgroup$
– g.kov
Aug 18 at 18:50
add a comment |
$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^5qquadtext(found in 1966)$$
$$95800^4 + 217519^4 + 414560^4 = 422481^4qquadtext(found in 1988)$$
but nobody knows if it is false for any or all $ngeq6$. 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
add a comment |
$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^5qquadtext(found in 1966)$$
$$95800^4 + 217519^4 + 414560^4 = 422481^4qquadtext(found in 1988)$$
but nobody knows if it is false for any or all $ngeq6$. 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
add a comment |
$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^5qquadtext(found in 1966)$$
$$95800^4 + 217519^4 + 414560^4 = 422481^4qquadtext(found in 1988)$$
but nobody knows if it is false for any or all $ngeq6$. 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$
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^5qquadtext(found in 1966)$$
$$95800^4 + 217519^4 + 414560^4 = 422481^4qquadtext(found in 1988)$$
but nobody knows if it is false for any or all $ngeq6$. 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.
answered Aug 18 at 4:21
community wiki
Tito Piezas III
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
add a comment |
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
4
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
$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
add a comment |
$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
2 days ago
|
show 5 more comments
$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
2 days ago
|
show 5 more comments
$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$
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.
answered Aug 17 at 18:41
community wiki
saulspatz
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
2 days ago
|
show 5 more comments
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
2 days ago
4
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$
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$
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$
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
$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
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
2 days ago
$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
2 days ago
|
show 5 more comments
$begingroup$
Littlewood proved in 1914 that there exists a number $ninmathbbN$ (called Skewes' number) such that:
$$
pi(n) > operatornameli(n),
$$
where $pi(n)$ is the amount of primes below $n$ and $operatornameli(n)$ denotes the logarithmic integral $displaystyle int_0^n fracdtln t$.
It is conjectured that $n$ is a huge number, recent analysis suggests $napprox 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
add a comment |
$begingroup$
Littlewood proved in 1914 that there exists a number $ninmathbbN$ (called Skewes' number) such that:
$$
pi(n) > operatornameli(n),
$$
where $pi(n)$ is the amount of primes below $n$ and $operatornameli(n)$ denotes the logarithmic integral $displaystyle int_0^n fracdtln t$.
It is conjectured that $n$ is a huge number, recent analysis suggests $napprox 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
add a comment |
$begingroup$
Littlewood proved in 1914 that there exists a number $ninmathbbN$ (called Skewes' number) such that:
$$
pi(n) > operatornameli(n),
$$
where $pi(n)$ is the amount of primes below $n$ and $operatornameli(n)$ denotes the logarithmic integral $displaystyle int_0^n fracdtln t$.
It is conjectured that $n$ is a huge number, recent analysis suggests $napprox 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$
Littlewood proved in 1914 that there exists a number $ninmathbbN$ (called Skewes' number) such that:
$$
pi(n) > operatornameli(n),
$$
where $pi(n)$ is the amount of primes below $n$ and $operatornameli(n)$ denotes the logarithmic integral $displaystyle int_0^n fracdtln t$.
It is conjectured that $n$ is a huge number, recent analysis suggests $napprox 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.
edited Aug 19 at 14:05
community wiki
2 revs, 2 users 97%
Klangen
$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
add a comment |
$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
$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
$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
add a comment |
$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
add a comment |
$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
add a comment |
$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$
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).
answered Aug 17 at 23:30
community wiki
gnasher729
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
add a comment |
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
1
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
$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
add a comment |
$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:
beginarrayc
hline
8 & 3 & 4 \ hline
1 & 5 & 9 \ hline
6 & 7 & 2 \ hline
endarray
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$
$begingroup$
Reading this Parker's Square comes to my mind if you know what I mean
$endgroup$
– StackUpPhysics
Aug 19 at 18:44
$begingroup$
The reference if you didn't get it- bradyharanblog.com/the-parker-square
$endgroup$
– StackUpPhysics
Aug 19 at 19:41
add a comment |
$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:
beginarrayc
hline
8 & 3 & 4 \ hline
1 & 5 & 9 \ hline
6 & 7 & 2 \ hline
endarray
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$
$begingroup$
Reading this Parker's Square comes to my mind if you know what I mean
$endgroup$
– StackUpPhysics
Aug 19 at 18:44
$begingroup$
The reference if you didn't get it- bradyharanblog.com/the-parker-square
$endgroup$
– StackUpPhysics
Aug 19 at 19:41
add a comment |
$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:
beginarrayc
hline
8 & 3 & 4 \ hline
1 & 5 & 9 \ hline
6 & 7 & 2 \ hline
endarray
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$
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:
beginarrayc
hline
8 & 3 & 4 \ hline
1 & 5 & 9 \ hline
6 & 7 & 2 \ hline
endarray
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.
answered Aug 19 at 18:23
community wiki
kviiri
$begingroup$
Reading this Parker's Square comes to my mind if you know what I mean
$endgroup$
– StackUpPhysics
Aug 19 at 18:44
$begingroup$
The reference if you didn't get it- bradyharanblog.com/the-parker-square
$endgroup$
– StackUpPhysics
Aug 19 at 19:41
add a comment |
$begingroup$
Reading this Parker's Square comes to my mind if you know what I mean
$endgroup$
– StackUpPhysics
Aug 19 at 18:44
$begingroup$
The reference if you didn't get it- bradyharanblog.com/the-parker-square
$endgroup$
– StackUpPhysics
Aug 19 at 19:41
$begingroup$
Reading this Parker's Square comes to my mind if you know what I mean
$endgroup$
– StackUpPhysics
Aug 19 at 18:44
$begingroup$
Reading this Parker's Square comes to my mind if you know what I mean
$endgroup$
– StackUpPhysics
Aug 19 at 18:44
$begingroup$
The reference if you didn't get it- bradyharanblog.com/the-parker-square
$endgroup$
– StackUpPhysics
Aug 19 at 19:41
$begingroup$
The reference if you didn't get it- bradyharanblog.com/the-parker-square
$endgroup$
– StackUpPhysics
Aug 19 at 19:41
add a comment |
$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$
add a comment |
$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$
add a comment |
$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$
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.
edited Aug 20 at 0:32
community wiki
3 revs, 2 users 89%
TStancek
add a comment |
add a comment |
$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$
add a comment |
$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$
add a comment |
$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$
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."
answered Aug 20 at 4:05
community wiki
Joshua
add a comment |
add a comment |
$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
add a comment |
$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
add a comment |
$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$
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
answered Aug 18 at 21:36
community wiki
Gapcoin Club
$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
add a comment |
$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
$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
$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
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3325462%2funsolved-problems-not-independent-of-zfc-due-to-lack-of-computational-power%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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
6
$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