Normal Numbers

Date: 10/19/1999 at 04:20:18
From: Eugenio Rapella
Subject: Normal numbers

I teach math in an Italian high school; I'm fascinated by number 
theory but I know almost nothing about it. I've some questions 
concerning "normal numbers."

Let's say that a real number r is normal in base b if, writing r as a 
"decimal" number in base b, the frequencies of the b digits (0, 1, 
..., b-1) approach 1/b when you take more and more digits. Thus 
0.010101... (base 2) is normal in base 2 and 2.102102102... (base 3) 
is normal in base 3.

We define a real number r to be "completely normal" (or just "normal") 
if it is normal in any base b > 1. Thus

     0.010101... (base 2) = 0.111... (base 4) = 0.333... (base 10)

is not normal.

A rational number q = n/m (where n, m are integers) cannot be normal 
(as it is not normal in base m), but not all the irrational numbers 
are normal - for instance, 0.03003300033300003333... (base 10) is not 
rational but is not normal in base 10.

I remember from my probability course (more than 20 years ago) that 
we proved that almost every number in [0,1] is normal (the set of the 
"non-normal" numbers in [0,1] has measure 0). It was a "probabilistic 
proof," a kind of proof which is fairly common in number theory 
(probabilistic number theory).

I'm sure "normal numbers" have been studied at length; I have some 
questions:

1. Is there any non-probabilistic proof of the existence of normal 
   numbers?

2. Is there an algorithm to produce a number r that is
   (a) normal in 2 different bases?
   (b) normal in k > 2 different bases?
   (c) completely normal?

3. Years ago I read that pi is conjectured to be normal in base 10; is 
   there any proof that pi is normal in some bases, or even completely 
   normal?

4. What about other irrational numbers like e or the square roots of 
   2, 3, 5, ...?

I think this subject is really interesting and I'd like to write an 
article about it (I cooperate with some Italian reviews dealing with 
didactics of math). If and when the article will ever be produced, 
I'll mention all the contributors (but don't be too technical.) Pardon 
my English and thank you for your attention.

Date: 10/19/1999 at 13:34:42
From: Doctor Rob
Subject: Re: normal numbers

Thanks for writing to Ask Dr. Math, Eugenio. Your English is 
excellent. No apology is required.

Very little is known about number normal in single bases, much less 
ones normal in multiple bases.  Here are some answers as I understand 
them. There may be more recent research on the topic than that of 
which I am aware that would change some of these answers.

>1. Is there any non-probabilistic proof of the existence of normal 
>   numbers?

No. Every proof I have seen relies on counting the normal numbers 
between 0 and 1 and counting all the numbers between 0 and 1, and 
showing that the measure of the former is 0, and the measure of the 
latter is 1.

>2. Is there an algorithm to produce a number r that is
>   (a) normal in 2 different bases?

Of course if B = b^k, and a number is normal in base B, then it is 
normal in base b, too.

We know so little about irrational numbers that might or might not be 
normal, that to try to do this for an irrational is probably hopeless. 
On the other hand, you might try to find a rational number that is 
normal in two bases by this construction:

     Let the two bases be b and B
     Let n = LCM[b,B]

     Take GCD(b^n-1,B^n-1) = d

     Write 1/d in bases b and B

If this has period p in base b, and period P in base B, and b|p and 
B|P, you have a chance that a multiple of e/d, with 1 <= e <= d-1, 
might be normal in both bases b and B, that is, the integer 
e*(b^p-1)/d should have all b digits 0 to b-1 repeated p/b times each, 
and the integer e*(B^P-1)/d should have all B digits 0 to B-1 repeated 
P/B times each.

I haven't been able to make this construction work, but it is at least 
a promising approach.

For example, if b = 2 and B = 3, n = 6, and d = 7. Now the period of 
1/7 in base 2 is p = 3, which is not a multiple of 2, so this can't 
work.

For example, if b = 2 and B = 5, n = 10, and d = 33. Now the period of 
1/33 in base 2 is 10, a multiple of 2. The period of 1/33 in base 5 is 
10, a multiple of 5. Then e*(2^10-1)/33 = 31*e has 5 digits of 1 and 5 
digits of 0 for every e, so that part is fine. But

     e*(5^10-1)/33 = 295928*e = 33432203(base5)*e

doesn't have all five of the digits 0 through 4 each twice for any e, 
so this doesn't work, either.

>   (b) normal in k > 2 different bases?

Except for what is implied by the first sentence in (a) above, I know 
of no such algorithm.

>   (c) completely normal?

No.

>3. Years ago I read that pi is conjectured to be normal in base 10;
>   is there any proof that pi is normal in some bases, or even 
>   completely normal?

No such proof exists.

>4. What about other irrational numbers like e or the square roots of 
>   2, 3, 5, ...?

No such proof exists for any particular number.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/