# Freeman Dyson's example of an unprovable truth

Freeman Dyson has claimed that

$$\nexists m,n \operatorname{Reversed}(2^n) = m ^ 5$$

(where $\operatorname{Reversed}(l)$ just is the reverse of the digits of $l$ in base 10), is probably an example of an unprovable truth (source), and that even if it's not, there are many similar statements, some of which will be unprovable. As a heuristic argument, he says that a proof would have to rely on some pattern in the digits of powers of two, but those seem to be random.

Is this heuristic argument reasonable? I was surprised because I had thought that a search for undecidable arithmetic statements in Peano Arithmetic (let alone ZFC or something stronger) was rather challenging. But maybe that's only for (a) provably unprovable statements or (b) interesting statements. I'd tend to assume Dyson knows what he's talking about here, but am still curious.

-
In this area, as in many others, guesses are easier than theorems. There are now a few more or less "natural" statements about the integers that have been shown not provable in Peano Arithmetic (modulo the usual consistency assumptions). Look for the Paris-Harrington Theorem. –  André Nicolas Jun 10 '12 at 20:35
I suspect that Dyson doesn't know whether the statement is true or not (though in a sense he thinks it is very probably true) but thinks that there is no obvious way of proving it and so says it is probably not provable. –  Henry Jun 10 '12 at 20:35
It's clearly a heuristic argument. Logically, you can't do any better, since we're talking about absolutely unprovable true statements, not just ones unprovable in a particular system. My question is whether it's a good heuristic argument. –  user802500 Jun 10 '12 at 20:40
André, what's interesting about this is that Dyson's claim seems to be that it is probably undecidable in any reasonable system we might come up with. In contrast, the version of the Ramsey Theorem involved in the Paris Harrington theorem is decidable, just not in PA. –  user802500 Jun 10 '12 at 20:43
The link to the source no longer works. –  Martin Jun 17 '13 at 3:46

There are many quotes from Dyson's paper/book in this note by Calude: Dyson Statements that Are Likely to Be True but Unprovable

In the end (looking at the quotes in that note), Dyson's argument seems to be: because the identity in question seems to be very "likely" to be true, it must be true. Of course that is not a very strong argument, even for a heuristic one. There are many true statements in mathematics that nevertheless would be extremely "unlikely". In other words, looking at the negations of these "unlikely" but true statements, there are many false statements in mathematics that would nevertheless be extremely "likely" in a naive sense. (For the moment we will assume the claims about "likelihood" and probabilities are correct; that is a separate problem I will discuss below).

For example, the probability that $e^{\pi i} = -1$ is zero, because the set of all $x$ with $x = -1$ has measure zero. Nevertheless $e^{\pi i}$ does equal $-1$.

The main issue is that there is a difference between "we don't understand the pattern" and "the pattern is random". There are occasionally heuristic arguments that use probabilistic methods in a compelling way, but based on the quotes I have seen Dyson's argument is not particularly compelling.

There are two other issues:

1. Dyson is using the word "random" in an unusual way. In the normal sense of probability, the probability that an $(n+1)$-digit natural number ends with $n$ zeros goes to zero very quickly as $n$ increases, but $10^n$ does always end with $n$ zeros. It may be that Dyson clarifies this in his actual book, I don't know. But the precise definition of "random" needs to be clarified to make the argument sensible.

2. Calude quotes Dyson as saying "Any proof of the statement would have to be based on some non-random property of the digits." In fact, if we had a clear definition of the notion of "random" involved (see above), then we might be able to use the very fact that the sequence is random to prove things about it. In other words we might be able to use an assumption that the identity does not hold to show that the sequence would not possess the appropriate form of randomness. This is not entirely hypothetical: in the study of Martin-Lof randomness, it is common to use the assumption that a sequence is Martin-Lof random as a hypothesis to prove facts about the sequence. In general, hypothetical arguments that claim "any possible proof" would have to take a very specific form tend not to be compelling.

-
I don't see the relevance of your comments on "unlikely" true statements. The contrapositive of "it seems likely, so it must be true" is not "it seems unlikely, so it must be false". –  Peter Taylor Oct 26 '13 at 11:57
@Peter Taylor: I added another sentence, does that help? In terms of argument schemes, "if X is likely then X must be true" and "if Z is unlikely then Z must be false" are essentially the same thing, assuming that X is likely if and only if the negation of X is unlikely. –  Carl Mummert Oct 26 '13 at 12:11
That fills the gap nicely. Thanks. –  Peter Taylor Oct 26 '13 at 12:53