Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Normal Numbers

  1. Apr 7, 2008 #1
    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:
    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?
     
  2. jcsd
  3. Apr 7, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  4. Apr 7, 2008 #3
    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 Sn = {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 a1 in Sn, then concatenating with an element a2 from Sn/{a1}, then concatenating with an element a3 from Sn/{a1, a2}, 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.
     
  5. Dec 22, 2008 #4
    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....
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Normal Numbers
  1. Is this normal? (Replies: 6)

  2. Is pi a normal number? (Replies: 29)

  3. Normal number (Replies: 4)

Loading...