5 ms·

You'll never be sure if you got all the numbers though. You could try 1 trillion numbers and mathmaticians wouldn't be satisfied. Because 1 trillion and 1 could

by zaarn 7y ago

You'll never be sure if you got all the numbers though. You could try 1 trillion numbers and mathmaticians wouldn't be satisfied. Because 1 trillion and 1 could be it. You'll only know for sure if you prove it false.

segfaultbuserr 7y ago
> You'll only know for sure if you prove it false. Yes. Interestingly, there are disproved hypotheses, of which, before they got disproved formally, previous massive computations failed to find a single counterexample despite the search reached a huge upper bound. But from time to time, someone could get lucky enough and actually find one to disprove something entirely through computation... The CDC 6600, R and a Conjecture by Euler * https://criticathink.wordpress.com/2018/09/30/the-cdc-6600-r-and-a-conjecture-by-euler/ https://criticathink.wordpress.com/2018/09/30/the-cdc-6600-r...
- zaarn 7y ago
  Where they disproven of massive computation failing to find a counter example or was the search space entirely exhausted? Or by actually finding the counter example? Those are different things. You can disprove by computing every possible input but you can only reasonably disprove but not actually disprove if you didn't test every input. And if you don't find ANY counter example you can't definitely disprove.
  - segfaultbuserr 7y ago
    I've edited the comment and clarified the ambiguity.
  - thaumasiotes 7y ago
    > And if you don't find ANY counter example you can't definitely disprove. This is... not even close to being true.
    - zaarn 7y ago
      How is it untrue?
      - thaumasiotes 7y ago
        Any nonconstructive proof would fail to meet your criterion (which pretty much defines constructive mathematics). Consider the standard proof that the square root of 2 is irrational -- it takes the logical form 1. IF sqrt(2) is rational... 2. THEN it has a representation a/b where a and b are coprime integers. 3. THEN (after some algebra) a is a multiple of 2. 4. THEN (after some more algebra) b is a multiple of 2. 5. Points (3) and (4) contradict point (2), which says that a and b are coprime. 6. THEREFORE, we have disproven the idea that sqrt(2) is rational. This is a correct proof, but not a constructive proof. It's difficult to have a constructive disproof of the claim that a particular number is rational. What would you construct? But you can easily have a nonconstructive disproof of any given claim. Sticking to proof by contradiction, imagine the sequence "if this conjecture were true, there would be a unique largest prime number -> there is no largest prime number -> this conjecture is false".
        zaarn 7y ago
        I'm aware that nonconstrutive disproof/proof exists but my comments were about constructive/example-driven proofs/disproofs, so I don't see the point really.
        afiori 7y ago
        this is actually a constructive proof, you are proving that sqrt(2) = a/b implies false and "irrational" is defined as "not rational". A better easy non constructive proof is to show that there are two irrational numbers c and d such that c^d is rational. and either c1=d1=sqrt(2) or c2=(sqrt(2)^sqrt(2)) and d2=sqrt(2) as c2^d2 == 2 and if c2 is irrational you are done and if c2 is rational then c1^d1 is rational and you are done. The non constructivity is in that you do not know two irrational numbers c and d such that c^d is rational. In general proving "not P" by "P is absurd" is constructive and proving "P" by "not P cannot happen" is not.
        7y ago
  - ColinWright 7y ago
    There are cases of all of the following: (a) A conjecture claims that X doesn't exist, and a proof has been found to show that X does not exist; (b) A conjecture claims that X doesn't exist, and an exhaustive search has failed to find X; (c) A conjecture claims that X does exist, and a search has found a sample X; (d) A conjecture claims that X does exist, and a proof has been given that such an X does exist but without ever demonstrating a specific example. This collection of cases seems to show that your statements are mistaken.
    - a1369209993 7y ago
      I think they're saying that case d specifically is not a legitimate proof, or equivalently that instances of case that are legitimate proof can be made constructive through a trivial addition (eg https://news.ycombinator.com/item?id=20395476 https://news.ycombinator.com/item?id=20395476). I suspect they are mistaken, depending on how one defines "demonstrate" and "specific", but you haven't actually shown that.
      - ColinWright 7y ago
        It would be interesting to see how they react to this proof: https://en.wikipedia.org/wiki/Probabilistic_method#First_example https://en.wikipedia.org/wiki/Probabilistic_method#First_exa...
- raverbashing 7y ago
  There was also a computational search for counterexamples of Fermat's last theorem (with nothing found - April 1st jokes regardless)
ColinWright 7y ago
I seem to be missing something here. The comment is that this provides a way to show that the Riemann Hypothesis is false. And that statement is true - finding a single number n such that n>5040 and σ(n)/(n ln(ln (n))) is enough to show that the Riemann Hypothesis is false. Checking this for a bunch of numbers and not finding one does not, of course, show that the RH is true, but that's not what this comment is stating. The only way I can understand your comment is that you think the grandparent comment, the one to which you are replying, is asserting that we can use this result to prove the RH by computer search. The GP comment is not saying that. So I don't understand what you're saying. Let me summarise: * If we can find n such that n>5040 and σ(n)/(n ln(ln (n))) then the RH is false; * This gives a method by which Joe Random could, in theory, prove the RH false - that is, simply find and publish such a number; * This does not give a way for Joe Random to prove that the RH is true, since searching for such a number and failing does not prove anything. So, what are you saying?
HeadsUpHigh 7y ago
You are missing the point. The logic goes as follows: Logically constructed unproven argument: Statement x is true for all numbers with y property Now how do you go about proving or disproving the argument: One way is to provide a general proof that it is true for all numbers. A way to disprove it is to find a single number that doesn't work. This is basically why people have been running huge computations trying to find a number that disproves the Riemann hypothesis. What this article essentially says is that we can transform the hypothesis in such a way that the space within which we have to search for that magical number that disproves it has a certain property.

by zaarn 7y ago

segfaultbuserr 7y ago

> You'll only know for sure if you prove it false. Yes. Interestingly, there are disproved hypotheses, of which, before they got disproved formally, previous massive computations failed to find a single counterexample despite the search reached a huge upper bound. But from time to time, someone could get lucky enough and actually find one to disprove something entirely through computation... The CDC 6600, R and a Conjecture by Euler * https://criticathink.wordpress.com/2018/09/30/the-cdc-6600-r-and-a-conjecture-by-euler/ https://criticathink.wordpress.com/2018/09/30/the-cdc-6600-r...

zaarn 7y ago
Where they disproven of massive computation failing to find a counter example or was the search space entirely exhausted? Or by actually finding the counter example? Those are different things. You can disprove by computing every possible input but you can only reasonably disprove but not actually disprove if you didn't test every input. And if you don't find ANY counter example you can't definitely disprove.
- segfaultbuserr 7y ago
  I've edited the comment and clarified the ambiguity.
- thaumasiotes 7y ago
  > And if you don't find ANY counter example you can't definitely disprove. This is... not even close to being true.
  - zaarn 7y ago
    How is it untrue?
    - thaumasiotes 7y ago
      Any nonconstructive proof would fail to meet your criterion (which pretty much defines constructive mathematics). Consider the standard proof that the square root of 2 is irrational -- it takes the logical form 1. IF sqrt(2) is rational... 2. THEN it has a representation a/b where a and b are coprime integers. 3. THEN (after some algebra) a is a multiple of 2. 4. THEN (after some more algebra) b is a multiple of 2. 5. Points (3) and (4) contradict point (2), which says that a and b are coprime. 6. THEREFORE, we have disproven the idea that sqrt(2) is rational. This is a correct proof, but not a constructive proof. It's difficult to have a constructive disproof of the claim that a particular number is rational. What would you construct? But you can easily have a nonconstructive disproof of any given claim. Sticking to proof by contradiction, imagine the sequence "if this conjecture were true, there would be a unique largest prime number -> there is no largest prime number -> this conjecture is false".
      - zaarn 7y ago
        I'm aware that nonconstrutive disproof/proof exists but my comments were about constructive/example-driven proofs/disproofs, so I don't see the point really.
      - afiori 7y ago
        this is actually a constructive proof, you are proving that sqrt(2) = a/b implies false and "irrational" is defined as "not rational". A better easy non constructive proof is to show that there are two irrational numbers c and d such that c^d is rational. and either c1=d1=sqrt(2) or c2=(sqrt(2)^sqrt(2)) and d2=sqrt(2) as c2^d2 == 2 and if c2 is irrational you are done and if c2 is rational then c1^d1 is rational and you are done. The non constructivity is in that you do not know two irrational numbers c and d such that c^d is rational. In general proving "not P" by "P is absurd" is constructive and proving "P" by "not P cannot happen" is not.
      - 7y ago
- ColinWright 7y ago
  There are cases of all of the following: (a) A conjecture claims that X doesn't exist, and a proof has been found to show that X does not exist; (b) A conjecture claims that X doesn't exist, and an exhaustive search has failed to find X; (c) A conjecture claims that X does exist, and a search has found a sample X; (d) A conjecture claims that X does exist, and a proof has been given that such an X does exist but without ever demonstrating a specific example. This collection of cases seems to show that your statements are mistaken.
  - a1369209993 7y ago
    I think they're saying that case d specifically is not a legitimate proof, or equivalently that instances of case that are legitimate proof can be made constructive through a trivial addition (eg https://news.ycombinator.com/item?id=20395476 https://news.ycombinator.com/item?id=20395476). I suspect they are mistaken, depending on how one defines "demonstrate" and "specific", but you haven't actually shown that.
    - ColinWright 7y ago
      It would be interesting to see how they react to this proof: https://en.wikipedia.org/wiki/Probabilistic_method#First_example https://en.wikipedia.org/wiki/Probabilistic_method#First_exa...
raverbashing 7y ago
There was also a computational search for counterexamples of Fermat's last theorem (with nothing found - April 1st jokes regardless)

ColinWright 7y ago

I seem to be missing something here. The comment is that this provides a way to show that the Riemann Hypothesis is false. And that statement is true - finding a single number n such that n>5040 and σ(n)/(n ln(ln (n))) is enough to show that the Riemann Hypothesis is false. Checking this for a bunch of numbers and not finding one does not, of course, show that the RH is true, but that's not what this comment is stating. The only way I can understand your comment is that you think the grandparent comment, the one to which you are replying, is asserting that we can use this result to prove the RH by computer search. The GP comment is not saying that. So I don't understand what you're saying. Let me summarise: * If we can find n such that n>5040 and σ(n)/(n ln(ln (n))) then the RH is false; * This gives a method by which Joe Random could, in theory, prove the RH false - that is, simply find and publish such a number; * This does not give a way for Joe Random to prove that the RH is true, since searching for such a number and failing does not prove anything. So, what are you saying?

HeadsUpHigh 7y ago

You are missing the point. The logic goes as follows: Logically constructed unproven argument: Statement x is true for all numbers with y property Now how do you go about proving or disproving the argument: One way is to provide a general proof that it is true for all numbers. A way to disprove it is to find a single number that doesn't work. This is basically why people have been running huge computations trying to find a number that disproves the Riemann hypothesis. What this article essentially says is that we can transform the hypothesis in such a way that the space within which we have to search for that magical number that disproves it has a certain property.