From: israel@math.ubc.ca (Robert Israel)
Subject: Re: sequences of digits with equal frequency
Date: 9 Nov 2000 22:22:00 GMT
Newsgroups: sci.crypt.random-numbers,sci.math
Summary: Construction of absolutely normal numbers

In article <8udlfk$efd$1@baker.cc.tut.fi>,
Helenius Ville  <heleniuv@cc.tut.fi> wrote:

>It is proved that, the existence of sequence with every 1),2),...,K)
>is true for all N.
>Those are called absolutely normal numbers
>Measure of non absolutely normal numbers is zero
>so almost all numbers are absolutely normal
>But no single number x is known to be absolutely normal
>so far...

The last is not really true.  Maybe you could say, no number written 
in "closed form" is known to be absolutely normal.  But it's not hard to 
come up with a construction of an absolutely normal number x.  

The set X of absolutely normal numbers in [0,1] is the complement of the 
union of a sequence of sets B_n of measure 0.  Each set B_n might be of 
the form: 
the set of x such that, if f(j) is the number of occurrences in x of digit 
d in base b up to the j'th digit, lim sup f(j)/j >= 1/b + epsilon.  
B_n is the intersection of nested sets U_{nm} =  {x : for some j > m,
f(j)/j >= 1/b + epsilon}; and measure(U_{nm}) -> 0 as m -> infinity 
(with explicit estimates available).  
Choose m(n) such that measure(U_{nm(n)}) < 2^(-n).  
U_{nm} = union_{j > m} V_{nj} where 
V_{nj} = { x : f(j)/j >= 1/b + epsilon}.  Note that it's possible to
write each V_{nj} explicitly as the union of a finite number of intervals.
Now construct a nested sequence of closed intervals C_k as follows.
Renumber the doubly-indexed sequence V_{nj} for j > m(n) as the
singly-indexed W_k.  Now measure (union_k W_k) < 1, and
measure(W_k) -> 0 as k -> infinity.  We'll choose C_j so that it is
disjoint from W_k for k <= j, with measure(C_j - union_{k > j} W_k) > 0.
Take C_0 = [0,1].  Given C_j, C_j - W_{j+1} is the union of a finite
number of intervals (and nonempty).  If any of these intervals has 
length more than half the length of C_j, split it in half.  
At least one of these intervals J must have the property that 
measure(J - union_{k > j} W_k) > 0.  Moreover, we can find one of the 
intervals with this property in a constructive way, by looking at a 
large enough finite collection of W_k's.
So choose such a J as C_{j+1}.  

Now the intersection of the C_j consists of exactly one number x, which
by construction is not in any B_n and thus is absolutely normal.  The 
number x is "known" in the sense that we have an algorithm to produce
arbitrarily good rational approximations of it.  However, it's not as
"nice" a number as pi.  

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2