What Are Normal Numbers and Their Connection to Transcendental Numbers?

[JohnDuck]

I'm an undergrad math major who has recently taken an interest in normal numbers. I've just decided to begin to seriously read about them, and I was wondering if anyone here could point me in the right direction (in terms of which papers to read, for example). I'm wondering what other characterizations there are of normal numbers and normal numbers in base b. For example, Wolfram MathWorld says a normal number is:

...an irrational number for which any finite pattern of numbers occurs with the expected limiting frequency in the expansion in a given base...

Specifically, I suspect that a number is normal in base 2 if and only if its base-2 expansion is a concatenation of every integer. I have sketched a proof though I have not filled in the details, so there remains a significant possibility that my reasoning is wrong. Is anyone here knowledgeable on the subject? Is this blatantly false? Obvious? Simply not a useful characterization?

Additionally, since it seems that normal numbers are related somehow to transcendental numbers, could anyone recommend a good book on that subject?

 

[CRGreathouse]

Specifically, I suspect that a number is normal in base 2 if and only if its base-2 expansion is a concatenation of every integer.

I'm not sure how to interpret this, but it sounds like it follows readily enough from the definition of normal. Can you phrase this formally?

 

[JohnDuck]

I'm not sure how to interpret this, but it sounds like it follows readily enough from the definition of normal. Can you phrase this formally?

I can try. First consider that the binary expansion of an integer is a string of finite length consisting of 1's and 0's. For brevity, when I mention strings I'll mean specifically strings of 1's and 0's. Let the set S_n = {strings of length <= n}, where n is an integer.

Then a concatenation of every string of length <= n is a string gotten by first picking an element a₁ in S_n, then concatenating with an element a₂ from S_n/{a₁}, then concatenating with an element a₃ from S_n/{a₁, a₂}, and so on until you have exhausted every element. Then let a concatenation of every string be the limit as n approaches infinity of a concatenation of every string of length <= n.

In order to prove a concatenation of every string is 2-normal, we need to show that any substring appears in the concatenation with the expected limiting frequency. I believe you can prove this by induction on n, by considering the relative frequency of strings of length m (for 1 <= m < n) in concatenations of strings of length <= n. I haven't worked out the details yet.

I also have a sketch for proving the opposite direction; if a number n is 2-normal, then it can be represented by a concatenation of every string. The gist of it is to systematically pick out every string, though I don't have the time to elaborate right now.

 

[WayneMV]

Um, if I understand your approach correctly - it doesn't work. Here is a way to concatenate every positive integer in a way that is obviously not normal.

0.0 1 2 11 3 111 4 1111 5 11111 6 111111 7 1111111 8 11111111 9 111111111 10 1111111111 12 11111111111 13 111111111111 14 1111111111111 15 ...

Although every positive integer is encountered at least once as a subsequence of digits (actually infinitely many times), the resulting number is obviously not normal in base 10 since it has way too many 1's.

Containing every positive integer as a subsequence is a necessary, but not sufficient, condition for a number to be normal.

Now, if the sequence of numbers is both dense, and in ascending order, then there is a proof that the resulting number is normal. I forget how "dense" is defined though.

These numbers are both proven normal in base 10:

0.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25...

0.2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83...