# Theorems true “with probability 1”?

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.

-
+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. – Jack Henahan Jun 16 '11 at 2:31
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 – t.b. Jun 16 '11 at 3:00
Great paper, @Theo. +1. – Jack Henahan Jun 16 '11 at 3:13
This makes me wonder if Chaitinesque arguments can be made about the probability that a random theorem is true. – deoxygerbe Jun 16 '11 at 8:47

One sometimes hears "The Riemann Hypothesis is true with probability 1." What's meant is that the Riemann Hypothesis is true if a certain statement $S$ about the Möbius function $\mu(n)$ is true; $\mu(n)$ is a member of a very natural family of functions, a family on which there is a natural probability measure; with probability 1, a function chosen from this family satisfies $S$.

-
Sounds interesting. Could you please add some details / reference? – Grigory M Jun 16 '11 at 9:37
@Grigory, go to the last section of en.wikipedia.org/wiki/Riemann_hypothesis and see the paragraph beginning "Denjoy's probabilistic argument...." There's also an article by Good and Churchhouse, The Riemann Hypothesis and pseudorandom features of the Möbius sequence, in Math Comp from 1968, probably available on the AMS website. – Gerry Myerson Jun 16 '11 at 12:28
Has this argument more merit than saying "The number 2 is irrational with probability 1"? It seems to me that it is a rather weak and misleading statement, but obviously it deserves a place in the wikipedia? – Jens Jun 16 '11 at 14:01
@Jens, depends on what you mean by "merit". Certainly it doesn't bring us any closer to a proof of RH. It does fall in line with the widely held, if somewhat imprecise, belief that "primes are random." – Gerry Myerson Jun 17 '11 at 1:06

A somewhat interesting development in partial differential equations is the study of the wellposedness of the initial value problem for randomised initial data. An example is this recent paper of Burq and Tzvetkov. Let me briefly and vaguely describe what they showed.

Wellposedness of Initial Value Problems

The roughest statement of the question of wellposedness for initial value problems in partial differential equations is to ask "if we prescribe the initial value at time $t = 0$, does there exist a unique solution for $t > 0$". However, to make mathematically precise, the first problem is to specify in what sense and in what sets you allow the solution to exist and require it to be unique (and also in what sense and in what sets do you prescribe the initial data). Well, since functions defined on any manifold form a vector space, we have that our set will at least have a vector space structure. Furthermore, it is realized that a physically natural requirement for wellposedness is an approximation property: that two initial data not differing by too much should generate solutions not differing too much. To quantify "not differing too much" we are led to require our sets to have topology (so we get a notion of continuity). This is in fact the usual notion of wellposedness:

An initial value problem is said to be wellposed if there exists some topological vector space (of functions defined at $t=0$) $X$ of initial data, and some topological vector space (of functions defined on $T > t\geq 0$) $Y$ of solutions such that there exists a continuous function $f:X\to Y$ mapping initial data to solutions.

The main work is then finding a suitable pair of $(X,Y)$ such that $f$ can exist as a function (so the domain is whole of $X$ and for each element in $X$ there is only one image in $Y$) and is continuous.

Regularity issues

Now, it is quite clear that if you make $X$ smaller, then it is "easier" to find the mapping $f$: there are "fewer" elements (less pathological behaviour) to worry about, and so it is more likely you will find that the solution map exists for all initial data in $X$. It is also quite clear that if you make the topology finer continuity becomes easier to prove. If your topology on the vector space is given by a family of semi-norms, then adding more semi-norms will make the space "smaller", and generate a finer topology.

In reality, this is in fact the case: letting $X$ be in the $L^2$-Sobolev scale of function spaces $H^s$, where $s$ measures the number of derivatives you control, the larger the $s$, the more likely you can prove a wellposedness statement.

Burq and Tzvetkov studied a particular equation--the cubic semilinear wave equation, henceforth 3SLW--in their paper. It is known from previous results that in fact there is a cut-off for wellposedness. In the Sobolev scale, 3SLW is wellposed with the time of existence $T$ possibly only finite for $\frac12<s<\frac34$ (some of the inequality signs may actually be non-strict, but I don't remember which way the inclusions go for sure), and with $T$ infinite when $s > \frac34$. For $0 < s < \frac12$, however, it is known that wellposedness fails because the breakdown of continuity (the topology of $X$ becomes too coarse).

Probabilistic wellposedness

However, it is reasoned that the breakdown of continuity for 3SLW is a very special situation, and that "most" rough data will still give good behaviour. In this spirit, fixing $s$ to be any number between 0 and 1, Burq and Tzvetkov constructed a probability measure $\mu$ (see below) on $H^s$ such that there exists a full measure set $\Sigma\subset H^s$ such that the solution map is well-defined (existence and uniqueness) on $\Sigma$ and $\Sigma$ is invariant under the solution flow (which implies the time of existence is infinite). Furthermore, with respect to this measure $\mu$, they showed a "probabilistic continuity" of the solution map: that is, defining the set

$$G(\epsilon,\delta):= \left\{ (V,U)\in X\times X \mid \|f(V)-f(U)\|_Y \geq \epsilon, \|V-U\|_X\leq \delta\right\}$$

of pairs of points where the solution differ by a large amount at least $\epsilon$ while the data differs by a small amount at most $\delta$, Burq and Tzvetkov could show that for any fixed $\epsilon$,

$$\lim_{\delta\to 0} \left|G(\epsilon,\delta)\right|_{\mu\times\mu} = 0$$

in the product measure.

The measure

You may ask, well, what if you just define the measure to be supported precisely on $H^1 \subset H^s$? The main point of the construction is that given any fixed $H^s$ function, one can construct the measure $\mu$ by "randomising" the given function, in such a way that the regularity doesn't increase. (More precisely, they showed that if the given function is in $H^s$ but not in $H^r$ for $r > s$, then the measure $\mu$ they constructed will have the property that $H^r$ has $\mu$-measure zero. So the measure $\mu$ is essentially an object living in the low regularity space.)

-
In computational complexity we have "smoothed analysis". For example, the simplex algorithm has exponential running time for some bad datasets, but its expected running time "close" to any given dataset is polynomial. – Yuval Filmus Jun 16 '11 at 12:31

Two examples, of perhaps opposite kinds:

• almost every real number is normal base 10, therefore (most likely) $\pi$ is normal base 10

• Almost every real number is transcendental, therefore there exists a transcendental number. (Much easier proof than exhibiting with proof an individual transcendental number.)

-
Fun fact: Almost every real number is normal for every base, yet (as far as I know) no number with that property has been found yet. – Jens Jun 16 '11 at 13:57
Fun rejoinder: $\pi$ has been found! – GEdgar Jun 16 '11 at 16:31
Ah, has that finally been proven? Do you have a reference? Last thing I heard was "we believe strongly that $\pi$ may be normal". – Jens Jun 17 '11 at 12:45
I did not say "proven" ... I said "found" as Jens did. As far as I know $\pi$ has not been proved normal in any base. But, regardless of that, $\pi$ has been found. – GEdgar Jun 17 '11 at 14:14
Is the second point the cardinality argument? Proving reals are uncountable is done by diagonal argument, which exhibits an individual transcendental number, although an ugly one. – sdcvvc Dec 7 '11 at 0:36

Below is Theo Buehler's answer (originally a comment).

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 Olivier's invitation to random groups.

-