4 ms·

Are there any unsolved math problems that aren't proving things?

TheLoneWolfling 12y ago
Yes, sort of. There are a number of problems that basically boil down to "what's the smallest value that has property <x>", which can be solved via brute force - or rather, could be, except that naive brute force would take too long, and no-one has figured out any tricks to make it fast enough to be practical. For example, calculating the value of any but the first few Ramsey numbers (the minimum number of vertices v = R(m, n) such that all undirected simple graphs of order v contain a clique of order m or an independent set of order n). There are also a lot of problems that could be proven or disproven via (counter)example - something like the Collatz conjecture, for instance.
zornthewise 12y ago
Finding [Ramsey numbers](http://en.wikipedia.org/wiki/Ramsey%27s_theorem http://en.wikipedia.org/wiki/Ramsey%27s_theorem) is one. They are hard to calculate even for small values. Most open problems are either to prove something because we can make a good guess to what the answer should be.
jordigh 12y ago
This isn't a meaningful question. There isn't a distinction between what is mathematics with a proof and what is mathematics without a proof. The examples that others have given about Ramsey numbers are, in fact, a proof. The proof could consist of a gigantic computation or it could be some other deep insight. But in the end, saying the Ramsey number R(5,5) is, say, 47, is not very meaningful without a convincing argument that establishes why it's that number. And those convincing arguments are a proof.
- Houshalter 12y ago
  That's not true. There is a whole class of problems that are trivial to prove an answer is correct, but very difficult to find the answer. Like factoring the RSA numbers, or finding a large prime number, etc.
  - jordigh 12y ago
    You're thinking of computer things like P vs NP. Any mathematician who develops some sort of algorithm for factoring large numbers would announce this algorithm and a proof of its correctness as the interesting thing to announce, not merely that some large number was factored, without disclosing how. Or perhaps they would keep it secret, but it would be a huge cultural faux pas to have a method to factor large numbers without also explaining (and thus proving) how it works.
    - Houshalter 12y ago
      It was just an example of a problem where the hard part is finding an actual answer, not just proving that the answer is correct. Proving things seems really boring and uninteresting to me, and there is no guarantee the task is even possible.
      - jordigh 12y ago
        There is no guarantee it's possible to factor large numbers quickly either. "Proving" isn't distinct from "mathematics". That's what I'm trying to get at. In a sense, a proof is equivalent to a computation (and it's possible to make this precisely true in some contexts). The public at large has gotten some impression that proofs are something only some kind of mathematics needs, probably after being traumatised by high school geometry classes. Proofs are all that mathematics is.
        Houshalter 12y ago
        You can model many problems as proofs, but not all, and it's not usually a useful observation. Most interesting math problems have nothing to do with proving things. The problem is people have already solved all the interesting problems. Proofs are just what's left. One interesting math problem someone told me just the other day was to come up with a series of forward and backward steps that would keep you from falling off a cliff, if a malicious person only chose each 2nd, 3rd or 4th step. Or to find the resistance between two points on an infinite grid of resistors. Or to find a series of bridges to get between several island without ever crossing a bridge twice. Or coloring a map with only 4 colors. Or in machine learning, tons of unsolved problems involving approximating intractable inference problems. That's a pretty wide variety of problems just off the top of my head, none of which are proving things. Sure some of the problems might not have a solution, but at least I'm not asking people to solve the halting problem, which is what half of those "unsolved math proofs" require. Even if you do solve them, the result is uninteresting. You could, at least in theory, quickly explain fermats last theorem to almost anyone. Or the four color theorem, or most of the problems I mentioned. But only a few mathematicians understand the proofs, and sometimes no one understands them (the ones proved computers.)

Yes, sort of. There are a number of problems that basically boil down to "what's the smallest value that has property <x>", which can be solved via brute force - or rather, could be, except that naive brute force would take too long, and no-one has figured out any tricks to make it fast enough to be practical. For example, calculating the value of any but the first few Ramsey numbers (the minimum number of vertices v = R(m, n) such that all undirected simple graphs of order v contain a clique of order m or an independent set of order n). There are also a lot of problems that could be proven or disproven via (counter)example - something like the Collatz conjecture, for instance.

zornthewise 12y ago

Finding [Ramsey numbers](http://en.wikipedia.org/wiki/Ramsey%27s_theorem http://en.wikipedia.org/wiki/Ramsey%27s_theorem) is one. They are hard to calculate even for small values. Most open problems are either to prove something because we can make a good guess to what the answer should be.

jordigh 12y ago

This isn't a meaningful question. There isn't a distinction between what is mathematics with a proof and what is mathematics without a proof. The examples that others have given about Ramsey numbers are, in fact, a proof. The proof could consist of a gigantic computation or it could be some other deep insight. But in the end, saying the Ramsey number R(5,5) is, say, 47, is not very meaningful without a convincing argument that establishes why it's that number. And those convincing arguments are a proof.

Houshalter 12y ago
That's not true. There is a whole class of problems that are trivial to prove an answer is correct, but very difficult to find the answer. Like factoring the RSA numbers, or finding a large prime number, etc.
- jordigh 12y ago
  You're thinking of computer things like P vs NP. Any mathematician who develops some sort of algorithm for factoring large numbers would announce this algorithm and a proof of its correctness as the interesting thing to announce, not merely that some large number was factored, without disclosing how. Or perhaps they would keep it secret, but it would be a huge cultural faux pas to have a method to factor large numbers without also explaining (and thus proving) how it works.
  - Houshalter 12y ago
    It was just an example of a problem where the hard part is finding an actual answer, not just proving that the answer is correct. Proving things seems really boring and uninteresting to me, and there is no guarantee the task is even possible.
    - jordigh 12y ago
      There is no guarantee it's possible to factor large numbers quickly either. "Proving" isn't distinct from "mathematics". That's what I'm trying to get at. In a sense, a proof is equivalent to a computation (and it's possible to make this precisely true in some contexts). The public at large has gotten some impression that proofs are something only some kind of mathematics needs, probably after being traumatised by high school geometry classes. Proofs are all that mathematics is.
      - Houshalter 12y ago
        You can model many problems as proofs, but not all, and it's not usually a useful observation. Most interesting math problems have nothing to do with proving things. The problem is people have already solved all the interesting problems. Proofs are just what's left. One interesting math problem someone told me just the other day was to come up with a series of forward and backward steps that would keep you from falling off a cliff, if a malicious person only chose each 2nd, 3rd or 4th step. Or to find the resistance between two points on an infinite grid of resistors. Or to find a series of bridges to get between several island without ever crossing a bridge twice. Or coloring a map with only 4 colors. Or in machine learning, tons of unsolved problems involving approximating intractable inference problems. That's a pretty wide variety of problems just off the top of my head, none of which are proving things. Sure some of the problems might not have a solution, but at least I'm not asking people to solve the halting problem, which is what half of those "unsolved math proofs" require. Even if you do solve them, the result is uninteresting. You could, at least in theory, quickly explain fermats last theorem to almost anyone. Or the four color theorem, or most of the problems I mentioned. But only a few mathematicians understand the proofs, and sometimes no one understands them (the ones proved computers.)