19
$\begingroup$

It seems that in spite of the Bailey–Borwein–Plouffe formula it is still unknown whether $\pi$ is normal in base 16. What are the difficulties in using it for this purpose?

In a comment to his answer to a question about decimal normality of $\pi$ Wadim Zudilin vaguely mentions a certain "plausible conjecture about dynamical behaviour of BBP sum terms, which would imply the normality in base 16".

$\endgroup$
  • 2
    $\begingroup$ With respect to normality, how does 16 help? $\endgroup$ – Włodzimierz Holsztyński Apr 15 '14 at 15:49
  • 2
    $\begingroup$ It is unknown if pi is normal in any (natural number) base, much less all such bases. The BBP algorithm allows a relatively rapid way of computing an arbitrary hex digit of pi, although I think it is still not practical when one tries for the billionth hex digit. That's why 16 is important. $\endgroup$ – The Masked Avenger Apr 15 '14 at 16:30
  • 1
    $\begingroup$ @TheMaskedAvenger On the contrary, BBP is quate practical for arbitrary digits - I believe it was a spigot-style algorithm that was used to compute around the quadrillionth bit (see bbc.com/news/technology-11313194 for more details) $\endgroup$ – Steven Stadnicki Apr 15 '14 at 18:23
  • 2
    $\begingroup$ The difficulty, in my opinion, is that an algorithm for computing base-16 digits does not automatically lead to a way to analyze the distribution of the infinitely many outputs. For that matter, usual long division gives a perfectly good algorithm for computing the base-16 digits of $\pi$, yet that did not yield a proof of normality either. $\endgroup$ – Greg Martin Apr 15 '14 at 19:14
  • 1
    $\begingroup$ The significance of the BBP formula is not just that it yields an efficient algorithm, but that it yields an unexpectedly simple recurrence for the digits (up to an error term that is negligible as far as the normality question is concerned). Unfortunately the recurrence is still too difficult to analyze. $\endgroup$ – Timothy Chow Apr 16 '14 at 15:57
20
$\begingroup$

The usual suspects in this subject (Borwein, Bailey, etc.) have written good expositions of this topic. What follows is shamelessly stolen from them. An easier example to explain, that illustrates the main idea, is log 2. We have the formula $$\log 2 = \sum_{n=1}^\infty {1 \over n 2^n}.$$ You can, if you like, call this a "BBP formula for log 2" since it lets you calculate binary digits of log 2 beginning after position $d$ as follows: $$\eqalign{2^d \log 2 \bmod 1 &= \sum_{n=1}^d {2^{d-n}\over n} \bmod 1 + \sum_{n=d+1}^\infty {2^{d-n}\over n}\cr &= \biggl(\sum_{n=1}^d {2^{d-n}\bmod n\over n} \biggr) \bmod 1 + \sum_{n=d+1}^\infty {2^{d-n}\over n}}.$$ The main point is that the second term here is small while the first term—call it $x_d$—is readily computable, and in fact satisfies the recurrence $$x_d = \biggl(2x_{d-1} + {1\over d}\biggr)\bmod 1.$$ So if one can demonstrate that the sequence $(x_d)$ defined by the above recurrence is equidistributed in the unit interval, then one can conclude (after fussing a little with the error term) that log 2 is normal in base 2.

For $\pi$, the same argument goes through, except that using the (original) BBP formula for $\pi$, one is led to consider a slightly different recurrence, with $2x_{d-1}$ replaced by $16x_{d-1}$ and $1/d$ replaced by a more complicated rational function of $d$.

The upshot is that BBP-type formulas allow us to rephrase the normality of certain constants in terms of the equidistribution of certain simple-looking recurrences. But currently, nobody has any idea how to prove equidistribution. Thus I would not say that there are "difficulties in using the BBP formula for the purpose of proving normality"; rather, the BBP formula can be applied straightforwardly, but the basic difficulty remains intact.

$\endgroup$
  • $\begingroup$ Thank you Timothy for such a nice answer. As I suspected but now I got some insight from you, each term of a sequence can be clearly computed, but the behavior of the total is far from clear. $\endgroup$ – Włodzimierz Holsztyński Apr 15 '14 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.