Talk:Normal number

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Mid Priority  Field: Analysis
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

"No rational number is normal to any base, since the digit sequences of rational numbers are eventually periodic."

Is this right? Obviously rationals are periodic, but what about 2/3 in base 2 (0.1010101...), or 1234567890/9999999999 in base 10 (0.12345678901234567...)?

I think it is right. Based on the definition, it isn't only single digits that have to appear equally, it's all sequences of digits. So for 2/3 to be normal to base 2, you need to show that 111010101100001101, for instance, occurs as if 2/3 were a random string of digits, when of course it does not occur at all. And similarly with your other example. Eric119 20:53, Mar 26, 2004 (UTC)


I believe there is an inconsistency with the claim at the end of the article that "not a single irrational algebraic number has ever been proven normal in any base", since we know that Copeland-Erdős constant is normal.

Oh wait, it said irrational ALGEBRAIC number - and the Copeland-Erdős constant looks pretty transcendental to me. (Michael Currie)


I think the conjecture that every irrational algebraic number is normal is not due to Bailey and Crandal as asserted but goes back to Borel: É Borel, Sur les chiffres décimaux de $\sqrt 2$ et divers problèmes de probabilités en chaîne, C. R. Acad. Sci. Paris 230 (1950) 591--593. Réédité dans : Œuvres d'É. Borel vol. 2, Éditions du CNRS, Paris, 1972, pp. 1203--1204. [J.-P. Allouche]

Has the Copeland-Erdős constant been proven transcendental? If not, perhaps the statement should be "not a single number has been proven to be both normal in any base and algebraic", which is a bit different from "not a single irrational algebraic number has ever been proven normal in any base". There's also a bit of an ambiguity, in that the latter can be interpreted as "there is no base in which a single irrational algebraic number has ever been proven normal", or "not a single irrational algebraic number has ever been proven normal in every base". Also, the word "irractional" is a bit redundant, as the statement that no rational number has been proven normal in every base is rather trivial.Flarity 20:27, 31 May 2006 (UTC)

Contents

[edit] Layman definition of normal number and other applications to the concept

I would like to add, but am uncertain how to word it academically, a section on the way I had previously understood "normal number" to be defined, which is basically saying the same thing as what is currently in the article but phrased in a different way. Basically, I had been told that a normal number is any number in which, when treated as a string, any possible substring can be found within that string.

This has a number of implications on a number of widely held beliefs. For example, it is often believed that in an infinite universe, there must be an example of anything and everything, which is basically stating "the universe, if infinite, is normal. Another way of rephrasing this belief is "all infinite sequences are normal" which is patently false, since it is easy to come up with counterexamples of infinite sets or sequences that are NOT normal. This means that it is not necessarily a given that there is, for example, a guarantee for the existence of extraterrestrial life, which I find is usually the context for the above statement.

Any suggestions on how to insert this into the article? I think it is of importance to mention... it also has relevance in other areas, like the infinite monkey theorem (and thus relevance to things like evolution). Basically, it says that first you have to prove that a given set is normal before you can assume that it is normal, and thus assuming normality while making a proof doesn't really hold water. Fieari 18:22, 16 May 2005 (UTC)

I think the definition "a normal number is any number in which, when treated as a string, any possible substring can be found within that string" is different from the definition given in the article. For instance, take the number (the spaces are added for clarity)
0.1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 00 11 00 12 00 13 00 14...
which is the sequence of natural numbers (1, 2, 3, 4, ...) with zeros added between them. This number is not normal, since more than half the digits are zero, but it contains every possible string of digits.
Regarding your second, more philosophical, comment, I am not sure this article is the correct place to mention that, but I can't suggest any other place. -- Jitse Niesen 14:30, 17 May 2005 (UTC)

It should be clear that all normal numbers are what, for expendience, I shall call Fieari numbers, but not all Fieari numbers are normal. It should also be pointed out that there is a big difference between every substring being present, and every finite substring being prsent. We also need to be clear on what we mean by "found". Can the sequence "12345" be "found" in the sequence "1020304050"? Flarity 20:27, 31 May 2006 (UTC)

[edit] Demonstration of uncountability of non-normal numbers

The current text says "The set of non-normal numbers is known to be uncountable; this follows easily by simply omitting one digit from each real number." This seems like it could be worded better unless I am missing something. When I hear "omitting a digit" I think of dropping, say, the 15th digit of a number so that the formerly 14th and 16th digits are now adjacent. But I don't immeditely see how that would demonstrate that non-normal numbers are uncountable because it doesn't seem like it would produce non-normal numbers.

If, instead, we drop all instances of a particular numberal in the decimal expansion (all "9"'s for instance), we clearly have a non-normal number for each Real. Even looking at it that way, the result doesn't seem to immediately follow because there will be many duplicates. For instance imagine pi with 3 9's inserted immediately after the decimal point, and pi with 4 9's inserted immediately after the decimal point. The "drop all 9's" procedure would turn both of those into pi. Given that the procedure results in a proper subset, how do we know that the subset isn't countable?

I think a clearer explanation would be helpful, or at least a pointer to another reference.

It seems to me that it would be more easily provable to have a reversible transformation. e.g. "write a digit 0 after every digit 1", "write the number in octal and interpret the result as decimal" or "write in binary-coded decimal and interpret as hexadecimal" or similar. --62.173.111.114 15:16, 18 November 2005 (UTC)
Consider all numbers which only have the digits 1 and 7. None is normal, and there are clearly uncountably many. The current proof should be read "consider all numbers which avoid the digit 5. None is normal, and there are uncountably many". 192.16.204.80 07:31, 9 February 2006 (UTC)
Good point. I changed the formulation. -- Jitse Niesen (talk) 17:52, 9 February 2006 (UTC)

[edit] Disputed

[edit] dispute 1 resolved

A number is normal in base b if and only if it is simply normal in base bk for every k \geq 1.

It's "obvious", but is it true? I'd accept a proof, even if it's OR. — Arthur Rubin | (talk) 18:48, 2 March 2006 (UTC)

It doesn't immediately follow from the finite state machine stuff. — Arthur Rubin | (talk) 18:55, 2 March 2006 (UTC)
This follows from the fact that a sequence is normal if and only if all blocks of equal length occur with equal frequency. (A block is a substring of length k occurring at a position that is a multiple of k). This fact is not obvious; I (or someone) should add this under "Properties of normal numbers". I don't know who proved it originally, but it follows from Ziv and Lempel's work on entropy rates. -- Pexatus 21:31, 2 March 2006 (UTC)
So replace my {{dubious}} tag by a cite, and we've got it. — Arthur Rubin | (talk) 21:45, 2 March 2006 (UTC)
Except I'm not sure whom to cite. It's sort of folklore in the research community now, but there may have been an original proof of it I am not aware of. --Pexatus 21:56, 2 March 2006 (UTC)
You don't have to cite the original author, only somewhere where it's proved. — Arthur Rubin | (talk) 22:09, 2 March 2006 (UTC)
Current citation seems acceptable to me. —The preceding unsigned comment was added by Arthur Rubin (talk • contribs) .

[edit] dispute 2 resolved

\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{j=0}^{n-1}e^{2 \pi i x_j^{(k)}}=0,

is not exactly the Weyl criterion in this context, and I'm not sure how to save it. Perhaps the correct statement would be that x is normal in base b iff the sequence

fp(x), fp(b x), fp(b^2 x), \ldots

is equidistributed. (Where fp indicates the fractional part.)

If that's correct, then the Weyl criterion becomes:
if k \geq 1 then
\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{j=0}^{n-1}e^{2 \pi i k b^j x}=0
Weyl's criterion has an additional integer l in the exponent, and then requires the limit to be 0 for all positive integers l. The substring length at which to look in the infinite sequence plays the role of the integer l in Weyl's criterion. We cannot use Weyl's criterion directly as stated for the following reason: For any given substring length k there will be only bk evenly-spaced vectors to add. Setting l=bk will rotate them all to be the same vector, so they obviously will not sum to a samall vector in that case. -- Pexatus 21:23, 2 March 2006 (UTC)
I disagree that the substring length alone gives adequate generality. However, it appears that requiring that the additional integer l not be divisible by b should give adequate generality. But all of these assertions are non-obvious, and require references due to WP:OR. I've replaced it by a simpler relationship for normal numbers which is obvious, and could even be moved toward the top to the true definition section. Pexatus's original current (as of the overwriting edit below) text is refactored below as #Connection to Equidistributed Sequences (Pexatus). I've chosen to Be bold and replace the section with one I'm sure is correct. — Arthur Rubin | (talk) 21:39, 2 March 2006 (UTC)
Sorry, I think I wrote over it. Redo your changes and I'll take a look at it later. --Pexatus 21:53, 2 March 2006 (UTC)
I'm sure it wasn't intentional. — Arthur Rubin | (talk) 21:57, 2 March 2006 (UTC)
I changed the j to m to avoid confusion with the square root of -1, which is sometimes j, so it's more obvious that that's what i is representing in the equation. —The preceding unsigned comment was added by Pexatus (talk • contribs) .
Resolved by replacing it with my alternate form which is "obvious". (Some variation of Pexatus's expression may be accurate, but, unless it's in the literature, it's original research. —The preceding unsigned comment was added by Arthur Rubin (talk • contribs) .

[edit] Connection to Equidistributed Sequences

Fork as of 22:00, 2 March 2006 (UTC)

[edit] Connection to Equidistributed Sequences (Pexatus)

Normal sequences (of characters) have a clear connection to equidistributed sequences (of real numbers) and exponential sums. (Briefly, a sequence of real numbers is equidistributed mod 1 if the fractional part of each number appears in an interval [a,b] \subseteq [0,1] with frequency b-a, i.e., in proportion to the length of the interval.) The famous Weyl's criterion can be applied to sequences to yield an equivalent characterization of normal sequences. A sequence S is normal if and only if, for all k \geq 1,

\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{j=0}^{n-1}e^{2 \pi i x_j^{(k)}}=0, (disputed — see talk page)

where x_j^{(k)} \in \{0,1,\ldots,b^k-1\} is the nonnegative integer whose base b expansion is the length-k string appearing in the j'th position of the sequence S.

Intuitively, we assign each string of length k a unique 2-dimensional unit vector at the origin. These bk vectors are equally spaced, so that the n'th string of length k is associated with the unit vector of angle \frac{n}{b^k} 2 \pi. If the sum of the vectors obtained from the first n characters in the infinite sequence S is asymptotically smaller than n, then the sequence S is normal.

The above characterization is not exactly the statement of Weyl's criterion, which relates to sequences of real numbers. In this case, the substring length k plays the role of the extra integer appearing in the exponent in the statement of Weyl's criterion.

[edit] Connection to Equidistributed Sequences (Arthur Rubin)

A number x is normal in base b if and only if the sequence {( b^k x ) }_{k=0}^\infty is equidistributed modulo 1, or equivalently, using Weyl's criterion if and only if

(\forall j \geq 1) \lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=0}^{n-1}e^{2 \pi i j b^k x}=0.

[edit] Lexicon (mathematics)

A while back I nominated Lexicon (mathematics) on Wikipedia:Requested articles/mathematics, as there is an intriguing link on Mathworld Real Numbers: that almost all real numbers are lexicons, meaning that they do not obey the law of large numbers. I now think its refering to Normal numbers. Can anyone hear shed some light on the issue? --Salix alba (talk) 15:12, 7 March 2006 (UTC)

Looks like a lexicon seems to be describing a normal number in base 2. Looks that way to me anyway. I've never heard of a lexicon in these terms before. I suggest we merge the article here. Fieari 05:34, 11 February 2007 (UTC)
A disjunctive sequence is a sequence in which every finite string appears, and as the article on normal numbers explains, these are not the same as normal sequences. According to the Wikipedia description of a lexicon, it is a real number whose base-k expansion, for every k \geq 2, is disjunctive. I have never heard of a lexicon, but if that is indeed the definition, then it is not difficult to construct a lexicon that is not normal in base 2. Fix a standard integer pairing function (j,k). Define the binary sequence S = s_1 0^{f(1)} s_2 0^{f(2)} \ldots (and call the real number is represents r), where, for each i, f(i) is chosen large enough that S is not normal, and, if i = (j,k), then si is chosen to be the lexicographically first binary string that causes the jth k-ary string to appear in the base-k expansion of r. Then r is a lexicon but is not normal base 2. I will remove the suggestion to merge the articles. Pexatus 08:05, 11 February 2007 (UTC)
I went ahead and did the merge anyway. They're not the same, but they're so closely related that there's not much more to say about disjunctive sequences and lexicons than what we already say here. And the pre-merge lexicon article was not good: it didn't say anything about the connection to normal numbers, and gave credit to a paper in 1998 for discovering the concept and proving that almost every number is a lexicon, despite the existence of a much older literature on normal numbers. The easiest way to fix the problem seemed to be to add a little more here about the "lexicon" terminology and redirect the other article here. —David Eppstein (talk) 19:03, 23 April 2008 (UTC)

[edit] Why "normal"?

If so amazingly few numbers have ever been shown to have this property, why of all the words that could have been chosen was "normal" used? They seem pretty "abnormal" to me. JackofOz 16:29, 19 May 2006 (UTC)

Almost all numbers have the property. Few individual and interesting numbers have been shown to be normal, but 'random' sequences will have it. Charles Matthews 18:56, 19 May 2006 (UTC)


[edit] Rationals

"No rational number is normal to any base, since the digit sequences of rational numbers are eventually periodic."

Is this true? 123456789/9999999999 is definitely normal in base 10. --Hirak 99 10:10, 2 May 2007 (UTC)

It's simply normal in base 10, but not simply normal in base 100, so not normal in base 10. — Arthur Rubin | (talk) 16:02, 2 May 2007 (UTC)
Right, I got the definition wrong. Thanks a lot for clarifying. Please feel free to delete this section if you want, now that it's cleared up. --Hirak 99 19:43, 2 May 2007 (UTC)

[edit] General proof for almost all numbers

From a recent post in sci.math:

From:  "Dave L. Renfro" <renfr...@cmich.edu>
Newsgroups: sci.math
Subject: Re: Randomness of digits within pi
Date: Fri, 09 Nov 2007 10:59:22 -0800

  "While a general proof can be given that "almost all"
  numbers are normal, this proof is not constructive ..."

If anyone here edits these pages, you might want
to revisit this statement. First of all, "this proof"
seems inappropriate to me, since no specific
proof had been singled out prior to this. Second,
I strongly doubt the standard proof that one can find
in Niven's "Irrational Numbers" is not constructive,
or at least can't easily be reworded so that it is.
In fact, the result itself is due to Borel, who
had very strong constructivists leanings.

Dave L. Renfro  —Preceding unsigned comment added by Loadmaster (talk • contribs) 19:26, 12 November 2007 (UTC)

[edit] Weird statement?

0.1234567891011121314151617..., obtained by concatenating the decimal representations of the natural numbers in order, is normal in base 10, but it might not be normal in some other bases

and the statement

Every normal number in base r is normal in base s if and only if log r / log s is a rational number. (Schmidt 1960)

is really weird together. It is obvious from Schmidt that the constant is normal in base 10^(r) iff r is rational.

Paxinum 20:23, 3 December 2007 (UTC)

First, I hope you don't mind that I've taken the liberty of reformatting slightly to avoid the awkward verbatim environment -- doesn't look good unless the person reading your remarks has the same screen width you do.
Substantively, you seem to have interpreted the Schmidt claim in a way that makes it obviously false. Someone should look this up and see, but my guess is that Schmidt's result is
For every two bases r and s, log r/log s is rational if and only if, for every x that is normal to base r, x is also normal to base s
Now I admit that this is not a very natural reading of the ambiguous claim, but it does have the advantage of not being obviously false, unlike the arguably more natural reading you seem to have understood:
For every base r and every number x normal to base r, and for every base s, x is normal to base s if and only if log r/log s is rational
Note that if the second interpretation were correct, there would be no normal numbers at all (where "normal" means "normal to every base").
But it's good that you caught this -- someone needs to look up the Schmidt reference and see what it really says, and then fix the language, which is currently terrible. --Trovatore 04:47, 4 December 2007 (UTC)
Ok, so your interpretation in math is somehting like this?
\forall \mbox{ bases }r,s : \ \left( \log(r) / \log(s) \in \mathbb{Q} \Leftrightarrow (\forall x : x \perp r \Rightarrow x \perp s)\right)
Or am I wrong again?
Anyways, Mathworld states that if a real number is bk normal, then it is also normal in bm for k,m integers.
Which is same as saying \forall x\in \mathbb{R}, \forall k,m \in \mathbb{N} : x\perp b^k \Rightarrow x\perp b^m. A statement a little weaker to the above statement, since \log(b^k)/ \log(b^m) = k/m \in \mathbb{Q}. This seems to be a special case of Schmidt where r & s are integers, but the equivalence read right-to-left only.
Paxinum 06:56, 4 December 2007 (UTC)
Right, that's the easy direction. (BTW I think we're talking only about natural-number bases here, so the "r and s are integers" bit is just assumed.)
The harder direction is, assuming s is not a rational power of r, can we show that there's a number that's normal to base r but not to base s? It seems very plausible, but I haven't been able to work out a proof just in my head. Not that I've tried very hard. The approach I'd try would be along these lines: Pick two different digits in base s (assuming s>2), and put the natural coin-flipping measure on base-s expansions that consist only of those two digits. None of those numbers are normal to base s. Now try to show that almost all of them (in the above-mentioned coin-flipping measure) are normal to base r. Should be true; not sure how to prove it. --Trovatore 08:30, 4 December 2007 (UTC)
Hmmm. The correct statement seems to be (as the mbox is almost illegible)
\forall \mathrm{bases} \ r,s : \frac {\log r}{\log s} \in \mathbb{Q} \Leftrightarrow \left(\forall x : x \perp r \Rightarrow x \perp s\right),
with the reverse implication being the difficult one, although I don't know why you selected \perp for normal. — Arthur Rubin | (talk) 18:21, 4 December 2007 (UTC)
Prependicular and normal have similar meanings... Tangential and normal components therefore the choise of \perp Paxinum 21:04, 4 December 2007 (UTC)
Not in this context, I'm afraid, but I understand your reasoning. — Arthur Rubin | (talk) 21:30, 4 December 2007 (UTC)
Mm, perpendicular and normal (in this article) has nothing in common. But it would be helpful with a better notation, like x \in N_b if x is normal in base b, where Nb is the set of all real numbers normal in base b. (Or something)... Paxinum (talk) 08:03, 5 December 2007 (UTC)

[edit] Connection to finite-state machines

Agafonov showed an early connection between finite-state machines and normal sequences: every subsequence selected from a normal sequence by a regular language is also normal. In other words, if one runs a finite-state machine on a normal sequence, where the finite-state machine outputs the digit it just read whenever it enters an accepting state, then the sequence it outputs will be normal. (Agafonov 1968)

Am I missing something? Take the following finite automaton:
state 1: input 0 -> go to 2, input 1 -> go to 1, initial, not accepting
state 2: input 0 -> go to 2, input 1 -> go to 1, accepting
Obviously, the machine will only output zeroes (and since the input sequence is normal, it will output an infinite number of zeroes), which is obviously not a normal sequence in base 2. - Mike Rosoft (talk) 22:43, 30 December 2007 (UTC)
Hmm, you're right, this looks wrong as stated. Maybe it's the digit the machine is about to read -- that would make sense. --Trovatore (talk) 02:16, 31 December 2007 (UTC)
Good catch. Pexatus (talk) 07:51, 15 February 2008 (UTC)

[edit] Further reading

I'm sorry to put my request in here, but since I'm not so familiar with the cite-template I can't put it on the page on my own:
Could anyone, who is better in wiki-markup than me, please add this to the refferences?
http://crd.lbl.gov/~dhbailey/dhbpapers/bcnormal.pdf (The authors are on the title-page)
(I think this article might be interesting) —Preceding unsigned comment added by 80.108.153.97 (talk) 16:24, 2 January 2008 (UTC)


[edit] "Every Base"?

The article states that normal numbers have an even distribution of digits in "every base", but perhaps this should read "every rational base"? I mean, for any normal number x, it is exactly 10 in base x, right? 219.78.90.231 (talk) 16:19, 8 March 2008 (UTC)

The "Definitions" section has a more formal definition of the term, which says that if a number is a normal number it is normal to bases b where b is an integer greater than 1. Read carefully. It doesn't mention non-integer rational bases. --CHL (talk) 14:14, 14 March 2008 (UTC)

My above comment refers to the introduction:

"In mathematics, a normal number is, roughly speaking, a real number whose digits (in every base) show a uniform distribution"

I realise it does say 'roughly speaking', but it seems a bit misleading nevertheless.219.77.144.70 (talk) 10:15, 15 March 2008 (UTC)