More on Testing Dyson’s Conjecture
Applying deep number theory to algorithms
Alan Baker won the Fields Medal in 1970 for his work on algebraic and transcendental numbers. He greatly extended a theorem of Aleksandr Gelfond and Theodor Schneider which had solved the seventh problem on David Hilbert’s famous list. Baker’s extension says that if are algebraic numbers other than or , and if are irrational algebraic numbers that together with are linearly independent over the rationals, then the product of for to is transcendental. Hilbert had stated the case, which Gelfond and Schneider solved, and believed it would be harder than the Riemann Hypothesis.
Today Ken and I want to talk about computing numbers to high precision and their relationship to our recent discussion of Freeman Dyson’s challenge.
Recall that Dyson argued that the following is true, but unlikely to ever be proved:
For any , let . Reverse the digits of in decimal. The result is never a power of .
For example, , and its reversal is which at least ends in five. But dividing it by 25 yields , so it is not a power of .
To tell that the answer is no may only need computing a handful of the leading digits of . This is because when we reverse , we compare them with the low-order digits of a power of . It is easy to compute recursions for the low-order digits, in any base. Getting high-order digits, however, is a problem of approximation. Baker’s theorem, in the form that drove his transcendence result, gives a lower bound on how close a “nice” quantity can be to “nasty” values, which in turn provides an upper bound on the error of approximations we need.
Checking Dyson’s Challenge
At the end of our discussion I pointed out that it seemed likely that we could devise an algorithm to test Dyson’s claim for in time polynomial in the number of bits in . Thus we should be able to check whether
reversed in decimal is not a power of five. The point is that such an algorithm would be interesting, since it would allow the checking of the claim for huge numbers, numbers that we cannot even write down in decimal notation. The central issue in this was the ability to compute the leading few decimal digits of such large numbers. A theorem by Richard Brent allows the computation in polynomial time of the logarithm of such numbers to exponential precision. But it does not obviously allow the computation of the top digits. See our discussion for why the top few digits may be sufficient.
The Answer in Sight?
I ended the previous discussion with an implicit question:
Whether this can be made to work we will leave for the future.
Thanks to Eric Allender, I believe that we can almost close the loop and prove that there is an algorithm for checking Dyson’s claim. Almost.
I asked Eric how hard it is to compute the leading decimal digits of for large , and he immediately said that it was known. He pointed out that in 2010—so relatively recently—Mika Hirvensalo, Juhani Karhumäki, and Alexander Rabinovich proved that the top few digits of such numbers can indeed be computed in time polynomial in the size of . Their paper (older TR) states this for base , but their results on appear to work for any base, even even bases. The paper title states the point nicely: “Computing partial information out of Intractable: Powers of algebraic numbers as an example.”
What strikes us as their key insight is to connect the computation with Baker’s theorem. Algebraic numbers have two common measures of complexity: the degree of the minimum polynomial equation they solve, and their height which depends on the size (or rather the lengths) of the coefficients of this equation. The theorem says that provided the algebraic numbers are not all zero, and no is or , then
where is the maximum of and the heights, and is computable in terms of , the degrees, and the choices of complex logarithm branches. When , as the paper intends, this also needs the logarithms to be linearly independent over the rationals. (Independence for the appears needed only for the transcendence deduction; meanwhile, the fact of the sum being nonzero makes and the logarithms collectively linearly independent over the algebraic numbers.)
The paper cites later bounds given by Baker for computing in the case . This is used to control the amount of precision needed to determine the leading digits of the power of . This is all very clever, and another example of how results in numerical approximation can be the fulcrum of algorithms.
The reason the algorithm is not completely worked out is that the authors prove only that one can get the top two digits, and they restrict their results to odd bases. We believe, but have not yet verified, that they should be able to handle a few more digits. To check Dyson’s conjecture efficiently for a given , we believe it should sufficient to check digits of . It is also unclear how much having base which is not relatively prime to will interfere. We will leave this for the future—again.