Talk:Normal number

From Wikipedia, the free encyclopedia

"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)

1 Layman definition of normal number and other applications to the concept
2 Demonstration of uncountability of non-normal numbers
3 Disputed
- 3.1 dispute 1 resolved
- 3.2 dispute 2 resolved
4 Connection to Equidistributed Sequences
- 4.1 Connection to Equidistributed Sequences (Pexatus)
- 4.2 Connection to Equidistributed Sequences (Arthur Rubin)
5 Lexicon (mathematics)
6 Why "normal"?

[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

b k

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 b^k evenly-spaced vectors to add. Setting l=b^k 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 b^k 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)

[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)

Retrieved from "http://en.wikipedia.org../../../n/o/r/Talk%7ENormal_number_d037.html"