[FOM] Roth's Theorem; Liouville numbers
Timothy Y. Chow
tchow at alum.mit.edu
Tue Apr 18 11:50:15 EDT 2006
Stephen G Simpson <simpson at math.psu.edu>
> Earlier this semester, in an introductory course on foundations of
> mathematics, I naively assigned students the following problem:
>
> Prove that the function f(n) = the nth digit of pi is primitive
> recursive.
>
> This turned out to be harder than I expected. The proof that I
> eventually came up with uses a result due to K. Mahler in the 1950s.
> Can anyone here supply an alternative proof that doesn't involve such
> heavy number theory?
Ah yes, a classic chestnut! This sometimes shows up as the puzzle: how
can you make money betting on the next n digits of pi, that haven't been
computed yet? That is, what do we know about the digits of pi that
distinguishes them from a "truly random" sequence?
The basic issue is that of an upper bound on the length of a consecutive
string of 9's in the decimal expansion of pi. This is unavoidably going
to lead to questions of irrationality measures for pi and hence to some
fairly sophisticated number theory. Maybe if all you want is a primitive
recursive bound then Mahler's proof can be simplified, but I've not heard
of anyone doing that.
If you choose the base to be a power of 2, then perhaps a simpler proof
using a Bailey-Borwein-Plouffe-type formula is possible. However, I don't
see how to do this immediately, and a quick look at the original BBP paper
(Math. Comp. 66 (1997), 903-913) reveals that they skirt this issue
themselves. They write:
"There is always a possible ambiguity when computing a digit string base b
in distinguishing a sequence of digits a(b-1)(b-1)(b-1) from (a+1)000. In
this particular case we consider either representation as an acceptable
computation. In practice this problem does not arise."
Tim
More information about the FOM
mailing list