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*^{13}
whose program to print it is of size greater or equal to *10*^{13}
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*_{1}u_{2}u_{3}u_{4}...
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 *n*th 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}=0
(*b* represent the power in the BBP formula, that is also the
base) Then the sequence *{**x*_{0},
x_{1}, x_{2}...} 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...
back to home page |