[FOM] Roth's Theorem; Liouville numbers

[Timothy Y. Chow]

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