A Challenge From Dyson
A reversal question
Freeman Dyson celebrated his birthday last December. He is world famous for his work in both physics and mathematics. Dyson has proved, in work that was joint with Andrew Lenard and independent of two others, that the main reason a stack of children’s blocks doesn’t coalesce into pulp is the exclusion principle of quantum mechanics opposing gravity. He shaved a factor of off the exponent for bounds on rational approximation of algebraic irrationals, before the result was given its best-known form by Klaus Roth. He has received many honors—recently, in 2012, he was awarded the Henri Poincaré Prize at the meeting of the International Mathematical Physics Congress.
Today Ken and I want to talk about one of his relatively recent ideas, which is more mathematics than physics. Perhaps even more theory than mathematics.
It is about an interesting challenge he made, and its significance for knowledge in general. In his popular books on science and public policy, Dyson has issued many challenges to the scientific community and society at large, daring to “disturb the universe” as one of his books is titled. In this challenge he disturbs mathematics—at least we feel that way. Let’s look at it now.
Dyson was one of over a hundred invited respondents to the 2005 edition of the “EDGE Annual Question”:
“What Do You Believe Is True Even Though You Cannot Prove It?”
His son, science historian George Dyson—two of whose books we covered—was also a respondent, and gave a social example that would have interested Ken and his wife Debbie on their trip to Vancouver this July. George suspects that well-documented differences between calls of ravens in different parts of the Pacific Northwest influenced First Nations languages in these regions. His father, however, kept it strictly mathematical, aiming for the most needling contrast between what we believe and what we can prove.
Ken may have his own answer, mine would have been more like: Fermat’s Last Theorem or the Four Color Theorem, since in both cases I believe the results, but I cannot prove them.
Dyson answered as follows:
“Since I am a mathematician, I give a precise answer to this question. Thanks to Kurt Gödel, we know that there are true mathematical statements that cannot be proved. But I want a little more than this. I want a statement that is true, unprovable, and simple enough to be understood by people who are not mathematicians. Here it is.
Numbers that are exact powers of two are 2, 4, 8, 16, 32, 64, 128 and so on. Numbers that are exact powers of five are 5, 25, 125, 625 and so on. Given any number such as 131072 (which happens to be a power of two), the reverse of it is 270131, with the same digits taken in the opposite order. Now my statement is: it never happens that the reverse of a power of two is a power of five.
The digits in a big power of two seem to occur in a random way without any regular pattern. If it ever happened that the reverse of a power of two was a power of five, this would be an unlikely accident, and the chance of it happening grows rapidly smaller as the numbers grow bigger. If we assume that the digits occur at random, then the chance of the accident happening for any power of two greater than a billion is less than one in a billion. It is easy to check that it does not happen for powers of two smaller than a billion. So the chance that it ever happens at all is less than one in a billion. That is why I believe the statement is true.
But the assumption that digits in a big power of two occur at random also implies that the statement is unprovable. Any proof of the statement would have to be based on some non-random property of the digits. The assumption of randomness means that the statement is true just because the odds are in its favor. It cannot be proved because there is no deep mathematical reason why it has to be true. (Note for experts: this argument does not work if we use powers of three instead of powers of five. In that case the statement is easy to prove because the reverse of a number divisible by three is also divisible by three. Divisibility by three happens to be a non-random property of the digits).
It is easy to find other examples of statements that are likely to be true but unprovable. The essential trick is to find an infinite sequence of events, each of which might happen by accident, but with a small total probability for even one of them happening. Then the statement that none of the events ever happens is probably true but cannot be proved.”
One can easily try numbers of the form for modest size to check that Dyson’s intuition is correct. We wonder if it is possible to at least check his intuition for an of size ?
Our challenge is:
Is there an efficient algorithm that given an determines whether the reversal of as a decimal number is a power of ?
Of course we want the algorithm to run in time polynomial in the length of . This would at least allow us to check Dyson’s intuition for extremely large numbers. Not all large numbers, but any particular large number. This seems like a plausible challenge.
Indeed we will now sketch an attack on how one might do this efficiently. The sketch is not a proof—we have not had the time to work all the details but we believe that it might be made into a real algorithm.
Of course, being able to check the conjecture for exponentially wider ranges is not the same as proving it for all . But making the machinery more efficient is a good way to understand the problem. We can try to work in some related ideas, however vague. One is encoding into matrices. There the reversal would perhaps be just the transpose. Another is that the reversal of a regular language remains regular: Given a deterministic finite automaton recognizing , one can create an NFA by adding a new start state that nondeterministically transits to some final state of , reversing each arrow of , and declaring ‘s start state the new final state. This NFA can then be converted back to a DFA. The languages of powers of or in decimal are not regular, but they are sparse enough that the idea might still help.
Let be the reversal of the number when written in decimal. Thus,
The reversal operator is nasty, non-linear, and hard to understand. But there is hope.
Suppose that is a number that we wish to check to see if for some . The idea is two step:
- Compute the top few decimal digits of : call them .
- Then check whether is a possible decimal pattern of low-order digits for a power of .
- If they are not, then conclude that Dyson is right about .
Several comments are in order about this potential algorithm. Clearly, since is just a few digits computing is easy given . Another point is that if is “random,” then there is a high probability that will not be a possible pattern for the low-order digits of a power of . This depends on the key fact that powers of have very constrained decimal patterns for their low-order digits. Of course all powers of end in , but much more is true. Here is a picture of how they behave:
Note: these cycles come in lengths of powers of two—see here for details. The critical point is that the cycles grow exponentially slower than the number of decimal digit patterns. So that if we can compute the top digits of and they are random we are likely to able to show that is not a power of without looking at many digits. This is an important, but simple, insight. Note, of the five lowest order digits only eight out of patterns are possible.
Computing The Top Digits
Next we need to show that we can compute the high order digits of when it is written in decimal. Clearly,
where the ‘s are decimal digits and is nonzero. Let’s try and obtain just the lead digit . The simple approach is to use the fact that we can compute the logarithm of to polynomial bits of precision in polynomial time. The idea is then to take logs base ten of and try to get . This almost works, but numbers like
could make the precision required more than polynomial. We believe that we can make this work, by using the following idea. Use logarithms to tell from and so on. The point is that this should be able to avoid the above problem.
Whether this can be made to work we will leave for the future.
Is Dyson right? Can we make our “algorithm” work?