{\huge Testing Dyson's Conjecture}

An application of deep number theory to complexity theory

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 $latex {\alpha_1,\dots,\alpha_k}&fg=000000$ are algebraic numbers other than $latex {0}&fg=000000$ or $latex {1}&fg=000000$, and if $latex {\beta_1,\dots,\beta_k}&fg=000000$ are irrational algebraic numbers that together with $latex {1}&fg=000000$ are linearly independent over the rationals, then the product of $latex {\alpha_i^{\beta_i}}&fg=000000$ for $latex {i = 1}&fg=000000$ to $latex {k}&fg=000000$ is transcendental. Hilbert had stated the $latex {k=1}&fg=000000$ 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 $latex {N}&fg=000000$, let $latex {A=2^{N}}&fg=000000$. Reverse the digits of $latex {A}&fg=000000$ in decimal. The result is never a power of $latex {5}&fg=000000$.

For example, $latex {2^{19}=524288}&fg=000000$, and its reversal is $latex {882425}&fg=000000$ which at least ends in five. But dividing it by 25 yields $latex {35297}&fg=000000$, so it is not a power of $latex {5}&fg=000000$.

To tell that the answer is no may only need computing a handful of the leading digits of $latex {A}&fg=000000$. This is because when we reverse $latex {A}&fg=000000$, we compare them with the low-order digits of a power of $latex {5}&fg=000000$. 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 claim for $latex {N}&fg=000000$ in time polynomial in the number of bits in $latex {N}&fg=000000$. Thus we should be able to check whether

$latex \displaystyle 2^{(2^{67535726535363576353563653}+1897897)} &fg=000000$

The Answer?

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 $latex {2^{N}}&fg=000000$ for large $latex {N}&fg=000000$, 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 $latex {N}&fg=000000$. Their paper (older TR) states this for base $latex {3}&fg=000000$, but their results on $latex {2^N}&fg=000000$ 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 $latex {\beta_i}&fg=000000$ are not all zero, and no $latex {\alpha_i}&fg=000000$ is $latex {0}&fg=000000$ or $latex {1}&fg=000000$, then

$latex \displaystyle |\beta_0 + \beta_{1}\log(\alpha_{1}) + \cdots + \beta_{k}\log(\alpha_{k})| > \frac{1}{H^C},&fg=000000$

The paper cites later bounds given by Baker for computing $latex {C}&fg=000000$ in the case $latex {\beta_0 = 0}&fg=000000$. This is used to control the amount of precision needed to determine the leading digits of the power of $latex {2}&fg=000000$. This is all very clever, and another example of how results in numerical approximation can be the fulcrum of algorithms.

Open Problems

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 $latex {N}&fg=000000$, we believe it should sufficient to check $latex {\log\log N}&fg=000000$ digits of $latex {2^{N}}&fg=000000$. It is also unclear whether having base $latex {10}&fg=000000$ which is not relatively prime to $latex {2}&fg=000000$ will interfere. We will leave this for the future---again.