24
$\begingroup$

This question is inspired by this closed question, per a suggestion on meta.

Some statements believed to be true are difficult to prove with current tools. However, there are some intuitive arguments to support them, some of them precise and some of them imprecise.

An example of a precise argument are random oracle results in computational complexity. A typical results states that under a random oracle, the classes P, NP, coNP are all different with probability 1. The methods used to prove this are not believed to be strong enough to actually prove the respective conjectures, since there exist oracles under which (for example) P=NP.

Examples of imprecise arguments abound in number theory. One can argue that there are "probably" only finitely many Fermat primes, and one can come up with a heuristic estimate of the density of twin primes.

A lot of factorization algorithms are analyzed only heuristically. However, in the case of the quadratic sieve, there is also a rather more complicated argument that shows that a variant of the quadratic sieve actually performs as advertised.

Examples of slightly different flavor are the host of results proved under the Riemann Hypothesis and its relatives. The celebrated AKS primality testing algorithm can be seen as an upgraded version of earlier algorithms whose analysis is conditional of RH; AKS provably performs as advertized.

Do you know of any similar results? I am mostly interested in results of the following two kinds:

  • Results stating that in some precise sense, some statement is true "for most universes".
  • Non-rigorous arguments suggesting the validity of a statement which (arguably) lead to rigorous proofs.

P.S. Please feel free to retag.

  • 0
    +1 for potential for good content. In a tongue in cheek fashion, any time someone says "probably" they implicitly mean "in more than $50\%$ of all possible universes", but that's probably not what you're after.~ I'll see if I can find some more relevant material.2011-06-16
  • 6
    There are some results of this kind in geometric group theory going back to Gromov's monumental paper on hyperbolic groups. The statements are typically of the form: If the group has a presentation of type ... then with overwhelming probability it is a group with such and such properties. Slogan: "Every theorem about all groups is either trivial or false, but it might hold with probability 1". A very nice introduction to these ideas is Yann Oliviers [invitation to random groups](http://www.yann-ollivier.org/rech/publs/randomgroups.pdf)2011-06-16
  • 0
    Great paper, @Theo. +1.2011-06-16
  • 0
    This makes me wonder if Chaitinesque arguments can be made about the probability that a random theorem is true.2011-06-16

4 Answers 4