Pi in the theory of randomness

This page is consacred to find the place of our constant Pi in the domain of theoretical randomness. This page is mostly inspired up to section D from the remarquable section 10 of "Fascinant nombre Pi" by J.P. Delahaye (no English translation available to this day), but how to present something that is otherwise so well explained !
This page will also improve throught out the years, as this discipline is not that easy to realise. For my part I still only have an imperfect view and in all case very incomplete of all this, so don't hesitate to tell me of extra theorems, examples and definitions you may know!
Here are the paragraph order, you have quite a bit too read !

A - Liouville's Numbers
B - Defining randomness

1 - Definition of "randomness" using Martin-Löf meaning of random
2 - "exceptionnals and checkable" properties
3 - Kolmogorov's theory on complexity

C - The main familly of randomness

1 - Universal Numbers
2 - Evenly spread Numbers
3 - Normal Numbers

D - Some theorems on complexity

1 - And Pi in all of this ??
2 - Hartmanis and Stearns' conjecture...
3 - Randomness generators

E -  BBP Formulae

1 - Bailey and Crendall Hypothesis
2 - Notion of finite attractor
3 - Evenly distributed

Bibliography

---

Is Pi a random number ?

The debate on the randomness of the number Pi is much more important than it seems. For one, an answer for this number would most likely imply the answer for many other constants by the same technique. And second, the understanding of numbers would be that much more enriched.

Historically, the result of the irrationality and transcendenty of Pi did not first of all bring great revalation on the spread of its decimals apart from the fact that they are not periodic. We can go just a little further by introducing the notion of Liouville's number.

A - Liouville's Numbers

In 1851, Joseph Liouville showed that not all the numbers are algebraic, and more precisly if x is irrational and roots of an algebraic equation of degree n, then there exitst C>0 such that for all rational p/q satisfy :

Intuitively, this means that a algebraic irrational number can not have rationals going to near it. An irrational number that alows itself being approach by rational then is trancendent.

We define the Liouville's numbers by this last property, that is x is a Liouville's number (and so transcendent) if for all integers n and C>0, there exists p, q such that

A amusing property is that this result decides the transcendenty of certain numbers containing a lot of 0. For example is transcendent due to the longue sequences of 0, we can come nearer and nearer to it with rationals. We also know the Liouville's number defined by 0, with 1 placed every n! places.

The converse is not true, that is not all transcendents are Liouville's number. For example, the brothers Chudnovsky showed that for Pi

for large enough q.

This implies that we can never find an infinite number of times of "15n" zéeos starting from the n rang, that is for example 15000 zeros starting from the 1000 rang. It's still a very very weak constrain! Imagine....
However, it still shows that Pi is not a Liouville's number, and so not approachable by rationals.

Due to the fact that we are not able to explain the nature of the decimal spread of Pi,  the idea that they could be spreaded "randomly" was borned.

Pi has no reason at all to be random since for certain representation, Pi has a well determined expresion. For example Euler's serie shows that in the mobile base with variable steps , Pi has a very simple expression 2,22222... This property is the one that gave rise to the algorithm spigot !

If we look at the regular continue fraction, we also know that the one for e is perfectly predictible which is not the case for Pi. What can we conclude ?

First of all, what does it mean for a number to be random ?

B - Defining randomness

To really understand the current state of conjectures on this problem, we need to introduce a few definitions:

B.1 - Definition of "Random"

A number is said to be random if the minimal size of a program generating n decimals of the number is at least of size n. Intuitevely, this means that we can't compress the information contained in this number.

More precisly, this approach is linked to the fact that since the property of getting a precise sequence of decimals is null, we can't easily use the thoerem of measure. But we can use the computability theory developed in the 40s by Gödel, Turing, Church and Kleene. This theory implies that not all sequences of numbers are programable, hence can not be calculated by machines. With the help of those work, other lead by Kolmogorov, Solomonoff, Chaitin and Martin-Löf in the 60s precised the definition of a random number with Martin-Löf 's meaning as a number not possesing an exceptional property that we can effectively check.

We land back on the theory of measure by defining an exceptional property as a property that is certainly not checked. So that we don't get trapped by some very special case but we don't know which, we add the condition of effective checking. This signifies that we can verify the property with a program and a risk of being wrong that lessen with the degree of checking.

B.2 - Precise (and tiresome) definition of exceptional and effectively checkable

A property P is exceptional and effectively checkable if there exists a test program that, for all intergers n (which correspond to the degree of test, in pratice a number f(n) of decimals), eliminate certain sequences that appear to satisfu the property P. The test, of level n, is done by using a finite number of digits from the sequence, and is such that the sequence eliminated is in proportion to at most 2^-n. The sequences which are eliminated starting from a certain rang n have to be exactly those which satisfy the property P.

A few remarques need to be said :

• The 2^-n makes sure that the remaining set is of measure null

• The definition is very general for an exceptional property. Because we could for example define the exceptional property "to be equal to Pi". In this case Pi would have an exceptional property and would not be random! It's in this case that the condition of possible checking by a program, that save everything. This condition will naturally impose the fact that checking needs to be in a finite time or in a loop, in short compress the checking, and this is the basis of the complexity theory of Kolmogorov.

• The checking condition hence moderate the probability condition which would have been useless as it would lead to an empty definition.

To link it with the definition given at the beginning, we use the complexity theory of Kolmogorov :

B.3 - Complexity theory of Kolmogorov

The complexity defined by Kolmogorov of a number measures the minimal size of a program allowing to print this number. A sequence of 1 has of course weak complexity while a sequence of length 10¹³ whose program to print it is of size greater or equal to 10¹³ has a very strong complexity and is completly incompressable...

This remarquable theorem proved in the 70s independantly by Schnorr, Levin and the great Chaitin is the following :

An infinite sequence of "0" and "1" is random in the Martin-Löf's meaning if and only if it is uncompressible, that is if and only if there exists a constant c such that Kolmogorov's complexity of the first n digits in the sequence is always greater than n-c.

The constant c is so to avoid problems with the start of the sequences (for example starting with hundreds of 1).

If we need to sum up the previous paragraph, it is that randomness in mathematical terms means uncompressible, which intuitively is not that absurd.
With this definition, Pi is not absolutly random, since the fact that we can write it in the form of series allows us to write a program of size less than n to calculate n decimals (in particcular there exists a program in C with only 158 characters which provided 2400 decimals of Pi, we call this kind of coding tiny-programs).
An other complimentary remark, this definition also shows that the random function on calculators are not "random" in the absolute sense.
Further more, the random numbers by Martin-Löf's meaning must be transcendants and normal, terms that we will define later on.
Finally, by his definition of exceptionals properties, nearly all numbers are random in Martin-Löf's meaning, even if neither the algebraics (anyway a countable number) nor the calculable numbers (also a countable number like the number of programs due to the instructions) are random!
Actually we only know Chaitin's number as truly random (the probability that a universal computer with self-limited program stops).

If Pi is not random by Martin-Löf's meaning, we then need to use properties a bit less "random" otherwise learn nothing about Pi !

C - The principal family of random numbers

C.1 - Universal Numbers

The universal numbers are the numbers where each digit is present. This is the case if each digit has a non null probability of being found in a infinte sequence of digit pulled out randomly.

We don't know how to prove if Pi is a universal number. On the other hand we know that nearly every numbers are universal numbers, even if there exists an infinate non countable numbers who are not universal numbers.

A trivial expample of universal number is Champernowne's number which is equal to 0,123456789101112131415... which is the sequence of all integers.

It's fascinating property implies that if Pi is a universal number, it contains among other the Bible's version of Pi converted in digits, it's own complete biography, without counting the countless containing errors. We can already find on the Internet website allowing you to find your birthdate in the known decimals.

Certain transcendant numbers are universal numbers (Champernowne's number) other not, on the other hand, we don't know at all for algebraic numbers (irrationals).

C.2 - Evenly Spread Numbers

According to the law of big numbers, for a given base b, the frequence of 0 in a sequence of n digits randomly generated tends toward 1/b as n tends toward infinity.

Reciprocally, if the frequence of each b digits of a number is 1/b then we say that the number is evenly spread (this for a base b, or for all the bases b, the following notation).

C.3 - Normal Nombre

Normality is a generalisation of evenly spread numbers.

A number is said to be normal in base b obviously if it is evenly spread in b but also if the frequence of couples is evenly spread, the frequency of triplets also, etc...

Hence, in base 10 the frequency of the digit 2 needs to be 1/10, the one of couple 29 should be 1/100, for 356 it should be 1/1000, etc...

A normal number in base b is by default in base b while the example 1/3=0.010101010101... in base 2 provides an evenly spread rational in base 2, but absolutly not normal in base 2. Un nombre normal en toute base est dit absolument normal.

The notion of normality is the most used one, that is it is often the ultimate property that we try to prove for a number. In truth we suppose that genarally for all the most used constant (but not the most trivials like the previous example) that they satisfy this property. Emile Borel did show that nearly all numbers are absolutly normal.

We could approach this problem of finitly definable numbers by using the formal system of notation and the classical axiomes of ZF. The intuitive definition is pretty clear and we realise that Pi is finitly definable, notably due to it's expansion in infinite series.

A few examples

This is all nice and well, but let's go back to earth with a few examples...
Champernowne's number is normal in base 10, hence evenly spread, and by definition it's a univeral number as we have seen. It's a formal counter-example to the assertions implying randomness from the normality, since this number clearly has a identifiable structure! What we don't know is wether it is normal in other bases, which is logical due to it's construction.

Copeland and Erdös showed that in a certain base b, the numbers in the form 0.u₁u₂u₃u₄... where u_n is an increasing sequence of intergers such that from a certain point are normal. Hence, 0.246810..., 0.510152025 (multiples of 5), 0.23571113 (sequence of primes) are normal.

We don't know how to explicitly construct a normal number in all base, even if Chaitin's number is yet again normal in all base.

D - Some theorems on complexity

D.1 - And Pi in all of that ?

Well the very disapointing but yet promising result is that we don't know anything.... The principal problem is that the mathematicians don't really know how to approach the problem because Pi evades us each time that they think they have found the solution!

As we have said, the results of irrationality and transcendental does not help much on the spread of the decimals of Pi.

We have seen that the Borwein's algorithms allied with modern technics of programming (FFT) allows us to calculate Pi in linear time n.log(n) which is a vast improvement compare to previously. We can imagine ourself to go further and then we arrive at....

D.2 - Hartmanis and Stearns' Conjectur !

All irrational numbers calculable in linear time (a time n gives n decimals) are transcendental.

There exists weaker results, for example the one by Loxton and Van der Poorten published in 1988 which indicates that an irrational number whose decimals are definable by a robot in a finit number of states (finite memory) is trascendantal.

This is of course not the case for Pi.

An other approach uses the BBP formula that we shall see in another paragraph.

D.3 - Random generators

A result that is neverless very interesting by Kannan, Lenstra and Lovasz (1986) concern the use of numbers such as Pi to code or create random generators.
We know that 1 can be written as an algebraic composition by certain function, for example: Pi=2*Arcsin(1)=Arccos(-1)=-2i*Ln(i). More generally, for the function Arccos, Arcsin, Ln and an algebraic a, we get the following result :

If we know a number n big enough with a decimals, the minimal degree of the equation of which n is a root, as well as the maximum size of its decimals, we can reconstruct the equation in time polynomial, and so reconise the number in question (and so continue to calculate it's decimals) An important consequence of this result is that can not use the decimals of those function taken at a (and so Pi) as random generators, since we could quickly violate the coding.

E - BBP formulae

In september 95, Bailey, Borwein and Plouffe found the following result :

It is extremely simple, the prove is obvious if you use integration and series, so it could have been discover way earlier. Further more, it's convergence is linear, all that was needed was to see what it could be used for.
In truth, we notice that we have "nearly" the devellopment of a number (Pi in this case) in base 16. And this nearly will allow us to evaluate the nth digit of Pi in base 16 without knowing the previous one, this in complexity n*ln(n) !
This is now well known, but if we think a bit more, we could imagine tjat by reaching any decimals without knowing the previous one, we can - by hand - we can start to predict one by one the decimals, to know the law of formation. In fact, the crucial question, is how can we be convince that Pi is "random" in base 16 when above we have a nearly-developpment of Pi in base 16... We just need to remove the nearly and the question is finish as long as we choose our definition of random,  but after all this waffle, I hope it's a little bit more clear!

And a first result of irrationality could for example appear. So for Pi, that's fine, we've known it's irrational for a while, but think of the combination of Pi with the logarithm, polynomials or even (in fact mostly) to the whole values of the Zêta function, that we know from the last results of Broadhurst, Plouffe, Huvent, Gourévitch that they can be put in the form of BBP formula!! It would be a great result....
We need to move a little bit off Pi, which is why I won't go in great details (otherwise, it'll never end!).

Intuitevely, the relative easiness with which we find a decimal without knowing the previous let us imagine that we can maybe find properties of those decimals on constantes. Some theorems linking polylogarithm function and irrationality exists but are difficult to exploit in this context.

On the other hand, in october 2000, Bailey and Crandall reduced the condition on normality with the verification of the following hypothesis :

E.1 - Hypothesis "A" of Bailey and Crandall

Note that , n>0 is a rational polynomial fraction with deg(p)<deg(q) and r without poles on N (It's the part in the brackets of the BBP formulae after factorisation of the same denominator). Hence b2 and x₀=0 (b represent the power in the BBP formula, that is also the base) Then the sequence {x₀, x₁, x₂...} defined by :

has a finite attractor or is evenly distributed on [0,1].
Those last two terms need a bit of precision :

E.2 - Finite attractor

Intuitively, the property of possesing a finite attractor represent the fact that a sequence tends toward the same values starting from a certain place, this in any order (we can show that for the case we are interested in, it's always the same order). It's as if it was tending towards a kind of rational (whose decimal sequence is periodic)

More precisly, a sequence posses a finite attractor if there exists and such that for all k0,

We can also show that for our case (BBP formula), this property is equivalent to the rationality of the limit of x_n.

E.3 - Evenly distributed

This notion is quite intuitive, it verifies if the appearance proportion of a sequence with values in [0,1] in a given interval [c,d] is precisly the length of that interval, hence d-c, simply if the taken values are distributed uniformly in the interval [0,1] :

This notion is stronger than the simple density of the sequence (due to it's character of unimore spread) and represent the continu analogue of the evenly spread property of a number's decimals.

Consequences

The evenly distribution for this kind of sequences implies leur normality. As we know that certain sequences like 1, ln(2) or are irrationals, under the hypothesis A, we decduce the normality of those constants. We just need to prove hypothesis A...

We know that the normality of a number implies it's irrationality. This condition is hence a sort of conjecture leading to the reciproque in the case of BBP formula or more generaly for sequences defined above. In any case the BBP formulae have not yet revealed all their secrets....

Bibliography

Oh, you must have guessed...

[1] J. P. Delahaye, Le fascinant nombre Pi

[2] D. Bailey, R. Crandall, On the Random Character of Fundamental Constant Expansions.
http://www.nersc.gov/~dhb/dhbpapers/bcrandom.pdf