Monday, November 26, 2018

If you think a theorem is true then spend half your time trying to prove its true, and half trying to prove its false.

There is a quote I recall but not who said it.  I have not been able to find it on the web.


If you think a theorem is true then spend half of your time trying to prove that its true, and half trying to prove that its false.

I thought it was Erdos but I could not find any connection between him and the saying. I did find something that indicates he did not say it:

An Erdos problem that pays different amounts of money for the conjecture being true of false:

--------------------------------------------------------------------------------
For a finite family F of graphs, let t(n,F) denote the smallest integer m that every graph on n vertices and m edges must contain a member of F as a subgraph.

A problem on Turán numbers for graphs with degree constraints} (proposed by Erdös and Simonovits [1]. $250 for a proof and $100 for a counterexample)

Prove or disprove that
t(n,H)=O(n^{3/2})
t(n,H)=O(n^{3/2})
if and only if H does not contain a subgraph each vertex of which has degree >2

Bibliography
1 P. Erdös, Some of my old and new combinatorial problems, Paths, flows, and VLSI-layout (Bonn, 1988), Algorithms Combin., 9, 35-45, Springer, Berlin, 1990.
----------------------------------------------------------------------------------------

A while back there was a $1,000,000 prize for PROVING Goldbach's conjecture (the prize had a deadline which is past). See here. However, the article does not say what you win for a counterexample. I suspect nothing. Is this fair? (1) YES- proving Goldbach would be hard, where as if its false just finding the counterexample likely won't require hard math, (2) NO- HEY, they resolved it, so there, (3) Have a panel look at the solution and decide if it has merit.

ANYWAY- if someone knows the source of the quote, please let me know.

7 comments:

  1. Manuel Blum has a quotation like that, though I think his counsel only involves one day a month trying to prove it's false.

    ReplyDelete
  2. Replies
    1. Thanks for the correction- I have made it.
      If you google "Goldback's conjecture" you get 212 hits
      If you google "Goldbach's conjecture" you get 105,000 hits

      Delete
  3. If there were a counterexample to Goldbach that didn't "require hard math" wouldn't it have been found by now?

    ReplyDelete
  4. I heard "prove by day, disprove by night" during my PhD studies. A cursory Google search points to Jordan Ellenberg's book "How not to be wrong," where he acknowledges hearing this from his PhD adviser, but calls it "a common piece of folk advice" without identifying a definitive source.

    ReplyDelete
  5. @ryan o'donnell: have heard great many stories about Manuel Blum. One day, he started to keep remembering digits of pi, by the next day he remembered the first 30, the next week, he remembered almost 1000 digits.

    ReplyDelete
  6. @Jake, No. If there is a counterexample, then a trivial computer program will find it in finite time depending on the computational resources (which might be available tomorrow, but not today).

    ReplyDelete