what numbers are normal?
Main Night
want to know, what numbers have been proven to be normal? the only one i can
think of is champernowne's constant, .1234567891011121314...
it seems to be that proving the normality of a constant must be extremely
difficult. which numbers have been proven normal?
Peace out, Sam.
May Galois live forever.
NFN NMI L.
difficult. which numbers have been proven normal?>>
An infinity of them. :-D For example,
.12345678901234567890...
.12345768901234576890...
And generally any number (rational if it follows a pattern, irrational if it
does not, and possibly trancendental) that is made of 10-digit chunks, and
within each chunk are the numbers 0-9 permuted in some fashion. Like:
.9452081763 4839201657 and so forth.
Proving the normality of these numbers "is obvious to the reader", "is left as
an exercise to the reader", or my favorite, "is easy enough for a drunken
monkey to prove".
Of course, there are other numbers outside this "easy" class of numbers that
are normal, and numbers like Pi that are really, really nasty to prove
normality for.
Moo-Cow-ID: 61 Moo-Cow-Message: and
-*---*-------
S.T.L. (NFN NMI L. also) -===> STL...@aol.com <===- 2^6972593 - 1 IS PRIME!
Quotations: http://quote.cjb.net Main site: http://137.tsx.org F00FC7C8 MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 Mail block
is gone, but will return if I'm bombed again. It was an easy fix. Address is
correct as-is. Giving the correct address is COURTEOUS; junk gets in anyway.
Join the Great Internet Mersenne Prime Search at http://entropia.com/ips/ My
.sig is even shorter, and contains 3046 bits of entropy including next line:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, People for the Ethical
Treatment of Digital Tierran Organisms, the Holy Order of the Catenary, the
Great SRian Conspiracy, the Triple-Sigma Club, the Polycarbonate Syndicate,
the Union of Quantum Mechanics, the Roll-Your-Own Crypto Alliance, and the
Organization for the Advocation of Two-Letter Acronyms (OATLA)
Avid watcher of "World's Most Terrifying Causality Violations", "When Kaons
Decay: World's Most Amazing CP Symmetry Breaking Caught On [Magnetic] Tape",
"World's Scariest Warp Accidents", "When Renormalization Fails", "World's
Most Energetic Cosmic Rays", and "When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #18: There Shalt Be Six Types Of Leptons.
Gus Gassmann
>
> Of course, there are other numbers outside this "easy" class of numbers that
> are normal, and numbers like Pi that are really, really nasty to prove
> normality for.
This we don't know. Since nobody has succeeded yet, it appears unlikely
that the proof is easy, but for all we know, it may fit onto Fermat's
margin
comfortably...
-------------------------------------------------------
gus gassmann (Horand....@dal.ca)
nee...@cableol.co.uk
Main Night wrote:
> It seems normality is growing into the current rage here on sci.math, and i
> want to know, what numbers have been proven to be normal? the only one i can
> think of is champernowne's constant, .1234567891011121314...
>
> it seems to be that proving the normality of a constant must be extremely
> difficult. which numbers have been proven normal?
>
Ronald Bruck
(NFN NMI L.) wrote:
:<<it seems to be that proving the normality of a constant must be extremely
:difficult. which numbers have been proven normal?>>
:
:An infinity of them. :-D For example,
:.12345678901234567890...
:.12345768901234576890...
:And generally any number (rational if it follows a pattern, irrational if it
:does not, and possibly trancendental) that is made of 10-digit chunks, and
:within each chunk are the numbers 0-9 permuted in some fashion. Like:
:.9452081763 4839201657 and so forth.
:Proving the normality of these numbers "is obvious to the reader", "is left as
:an exercise to the reader", or my favorite, "is easy enough for a drunken
:monkey to prove".
"Normal" is usually taken to mean "normal to EVERY BASE." No normal
number can be rational. (If m/n were normal, then when expressed in base
n it would have a sad paucity of digits...)
It's for this reason that "normal" implies that every SEQUENCE of digits
must appear infinitely often (and in fact with the right asymptotic
density). Proof: a digit sequence d_1d_2...d_n in base B is a SINGLE
DIGIT in base B^n. There are countably many (finitely long) digit
sequences.
Main Night mentioned that Champernowne's constant 0.123456789101112... is
known to be normal. Is that known, in fact? To base 10, yes, I'll
believe; but to all bases?
I think it was within the past year that somebody posted a construction
for exhibiting normal numbers. All I remember about it is that it was
nontrivial.
Note that normality to base 10 alone is an extremely unnatural condition.
Alpha Centaurians, who have 12 fingers, would think us quite provincial.
--Ron Bruck
nee...@cableol.co.uk
Main Night wrote:
> It seems normality is growing into the current rage here on sci.math, and i
> want to know, what numbers have been proven to be normal? the only one i can
> think of is champernowne's constant, .1234567891011121314...
>
> it seems to be that proving the normality of a constant must be extremely
> difficult. which numbers have been proven normal?
>
Mike Oliver
Ronald Bruck wrote:
> Note that normality to base 10 alone is an extremely unnatural condition.
> Alpha Centaurians, who have 12 fingers, would think us quite provincial.
You think those are *fingers*? Oh, my poor naive child...
NFN NMI L.
Moo-Cow-ID: 72 Moo-Cow-Message: up
Kurt Foster
. Incidentally, what is meant by a normal number?
[snip previous post]
A number x is normal (to the base b) when, for each positive integer n,
every block of n base-b digits occurs with the frequency expected in a
random string of digits (about once in b^n digits). The previously
mentioned x = .12345678910111213... obtained by concatenating the positive
integers in base ten, is normal to the base ten.
Clearly a number is normal to base b if and only if its fractional part
is normal to base b.
Obviously a rational number is not normal to any base, because whatever
the base, its expansion to that base is either terminating or periodic.
Either way, most sufficiently long blocks of digits fail to appear in
the base-b expansion at all.
OTOH, "almost all" numbers are normal to EVERY base b (integer >= 2), in
the sense that the exceptional numbers form a set "of measure 0".
Unfortunately, there seems to be no obvious way to test a number for
being normal to a given base, let alone to all bases; I am not aware of
any obvious connection between normality and the usual arithmetic
operations, except for the fact that rational numbers aren't normal to any
base.
hack
Main Night <main...@aol.com> wrote:
>It seems normality is growing into the current rage here on sci.math, and i
>want to know, what numbers have been proven to be normal? the only one i can
>think of is champernowne's constant, .1234567891011121314...
>
>it seems to be that proving the normality of a constant must be extremely
>difficult. which numbers have been proven normal?
>
>Peace out, Sam.
>May Galois live forever.
Champerowne's number is normal base ten. Chaitin's Omega has been proved
normal to every base (because it's algorithmically incompressible). The
actual value of Omega depends on a coding choice, so Chaitin provides a
recipe for defining (I almost said "constructing") a family of absolutely
normal numbers, just as Champerowne provides a recipe for constructing numbers
normal to any given base.
Champerowne's number is algorithmically compressible. A number that is
incompressible must be normal in any base (else one could take advantage of
frequency irregularities to encode it more efficiently). What is known about
the converse, i.e. could there be a compressible absolutely normal number?
If we knew how to *construct* an absolutely normal number, that converse would
be false.
Michel.
Bill Taylor
|> A number x is normal (to the base b) when, for each positive integer n,
|> every block of n base-b digits occurs with the frequency expected in a
|> random string of digits (about once in b^n digits).
... ...
|> OTOH, "almost all" numbers are normal to EVERY base b (integer >= 2), in
|> the sense that the exceptional numbers form a set "of measure 0".
Right.
There is also an extension to this basic idea of normal numbers, that
some books occasionally mention. It doesn't seem to have a name, but
it might be called "progressively normal", or "conditionally normal".
The idea is this. A normal number is supposed to be one that "looks random".
At least, looks random when we just look at its digits. (There could also
be an extension whereby the unit continued fraction expansion looks random,
which would prevent `e' from being normal, but not pi.) But anyway, just
looking at the digits alone could *still* cause trouble.
We could take a normal number, then deliberately change to zero every
(perfect-square)th place; the 1st, 4th, 9th, etc. These zeroes would
NEVER show up on a frequency count test, but could easily be picked up
by someone who knew what he was looking for. Thus, not only should
the digit sequence itself have proper frequencies, but every recursively
definable subsequence should do the same! This *still* leaves it
possible for almost all reals to be "subsequentially normal".
But there is more. We can go further. The nasty meddler could also make
it that, say, after each (perfect-squre)th place, he finds the next double
zero, and changes the *next* digit to zero. Again, if we were in the know,
or made an inspired guess, we could search for this and probabilistically
declare (eventually) that the number was not normal. SO we must extend
the definition yet further:- Make it that every subsequence defined by
place-sequences(*) that are recursive functions of all digits prior to
the current such(*)... (phew) ...are normal.
And this STILL leaves it that almost all reals are thus "super-normal".
And no doubt one could go still further...
---------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
---------------------------------------------------------------------------
"It's always crucial, when doing an involved calculation,
to know the answer ahead of time." -- John Baez
---------------------------------------------------------------------------
Zdislav V. Kovarik
DBatchelo1 <dbatc...@aol.com> wrote:
:Kurt Foster wrote:-
:> Obviously a rational number is not normal to any base, because
:>hatever the base, its expansion to that base is either terminating or
:>periodic.
:
:Are there other classes of number that are known not to be normal?
:I conjecture that every quadratic root is not normal: they can be
:expressed as repeating continued fractions and this suggests a high
:degree of order.
: How about other algebraic numbers?
I'd be cautious even about quadratic irrationalities; I doubt there is any
result about frequency distribution of the (decimal or binary) digits of
sqrt(2).
On the other hand, it is easy to produce continuum many non-normal
numbers; first, I am free to pick a base (say 10) to which normality can
be violated. Force every odd-indexed digit to be 3, and fill in the rest
arbitrarily, then collect all such numbers in a set. You can work out
more exotic examples than what I suggested.
And some may feel cheated, if they expected classes of numbers where the
violation of normality was not imposed up front, so to speak. But then let
me see a definition of "up front" in this context (and extramathematical
re-phrasings will not do, such as "so that the collective non-normality
comes out as a surprise" or so).
Have fun, ZVK(Slavek).
DBatchelo1
> Obviously a rational number is not normal to any base, because whatever
>the base, its expansion to that base is either terminating or periodic.
Are there other classes of number that are known not to be normal?
I conjecture that every quadratic root is not normal: they can be expressed as
repeating continued fractions and this suggests a high degree of order.
How about other algebraic numbers?
Dick Batchelor
Keith Ramsay
(Zdislav V. Kovarik) writes:
| And some may feel cheated, if they expected classes of numbers where the
|violation of normality was not imposed up front, so to speak. But then let
|me see a definition of "up front" in this context (and extramathematical
|re-phrasings will not do, such as "so that the collective non-normality
|comes out as a surprise" or so).
I believe it would come as a big surprise if there were any irrational
algebraic numbers that weren't normal.
The best sort of example I can think of is based on the existence of
special functions such as sum{n} q^{n^2} which occur "naturally" in
mathematics, in the study of theta functions, but whose power series
are sparse. Evaluating this at q=1/10 gives an irrational number which
isn't normal in base 10.
Keith Ramsay
Dave L. Renfro
are interesting. I’d appreciate any references to the ideas he
outlines.
On a related matter, I thought it would be of interest to point out
that the set of normal numbers, while large in the sense of measure,
is small in the sense of Baire category. Specifically, the set of
real numbers that are simply normal to base 10 (or to any specific
base) is a first category (i.e. meager) subset of the reals.
A WEAKER statement would be to say that the set of real numbers
that are absolutely normal to every base is a first category set,
since this latter set is smaller. Note that it is this latter set
that is known to have a measure zero complement (i.e. it is maximally
large in the sense of measure), and Taylor's remarks involve much
smaller sets still. As best that I’ve been able to determine,
this Baire category result involving the normal numbers was first
proved by Henry Blumberg (special case (c) of corollary 1 on p. 140)
in
Henry Blumberg, "A theorem on exhaustible sets connected with
developments of positive real numbers", Annals Math. (2)
20 (1918-19), 136-141. [Originally presented at an AMS meeting
in December 1913.]
In fact, Blumberg actually proved a much stronger result than
what I’ve stated:
Let N(n,x) denote the number of occurrences of the digit n in
the first N digits of the decimal expansion of the real number
x in [0,1]. Then the set of x’s in [0,1] such that for EACH value
of n, EVERY real number in the closed interval [0,1] is the limit
of some subsequence of {(1/N)*N(n,x)}, is residual in [0,1]
(i.e. has a first category complement in [0,1]).
In other words, instead of the statement "the set of x’s in [0,1]
such that for SOME value of n we DON’T have
(1/N)*N(n,x) ---> 1/10 as n ---> infinity, is residual in [0,1]"
(i.e. the numbers not simply normal to base 10 forms a
residual set), we have the topological largeness of the much
smaller set of x’s such that the sequence {(1/N)*N(n,x)}
fails to converge (to 1/10, or to anything else) in the worst
possible way. There is a subsequence of {(1/N)*N(n,x)} in which
the density of the digit n is 0, a subsequence of {(1/N)*N(n,x)}
in which the density of the digit n is 1, and similarly for
every real number between 0 and 1.
[For the purist, Blumberg's "special case (c)" was stated only for
the digit 1. However, one would think that the same result holds
for any digit n = 0, 1, ..., 9, and indeed Blumberg's corollary 1
on p. 139 is stated for any digit. The result I stated now follows by
intersecting the 10 residual sets that arise from the 10 digits.
Moreover, I believe Blumberg's corollary 1 is sufficiently general
so as to allow (or to be easily modified so as to allow) the result
I stated to be strengthened so that all the subsequences can be chosen
to have upper (i.e. lim sup) asymptotic density 1 in the sequence
{(1/N)*N(n,x)}.]
Incidentally, this result of Blumberg’s doesn’t seem
to be very well known, which seems strange to me given the
journal it appeared in. [Yes, I know the Annals didn’t have the
prestige then that it now has, but this still doesn’t quite explain
matters since the Annals is (now) quite prestigious and it is
widely available (even the older volumes).] In fact, Blumberg’s
paper is not mentioned in ANY of the references below--not even in the
Oxtoby/Ulam paper that appeared in the same journal just over 20
years later.
Here are some other places where versions of this Baire category
result for normal numbers are proved (or mentioned).
If anyone knows of any additional references, I would appreciate them.
Billingsly’s text PROBABILITY AND MEASURE
[exercise 1.13 on page 17]
J. C. Oxtoby and S. M. Ulam, "Measure-preserving homeomorphisms
and metrical transitivity", Annals of Math. 42 (1941), 874-920.
[footnote #13 on page 877]
V. I. Golubov, "O summirovanii posledovatelnostej", Izv. Vyss.
Uceb. Zaved. Matematika 4 (41) (1964), 47-55.
[see note 5]
Tibor Salat, "A remark on normal numbers", Rev. Roum. Math.
Pures et Appl. 11 (1966), 53-56.
Tibor Salat, "Normale zahlen und Bairesche kategorien von
mengen", pp. 306-307 in GENERAL TOPOLOGY AND ITS
RELATIONS TO MODERN ANALYSIS AND ALGEBRA III,
edited by J. Novak, Proc. 2’nd Prague Topological Symposium,
Czech. Acad. Sciences, Academic Press, 1966.
J. Lynch, "Almost sure theories", Annals of Math. Logic 18 (1980),
91-135.
[see page 100]
Mendez, "On the law of large numbers, infinite games, and
category", Amer. Math. Monthly 88 (1981), 40-42.
Gerry Myerson
(Dave L. Renfro) wrote:
=> Bill Taylor's comments on various strengthenings of "normal number"
=> are interesting. I'd appreciate any references to the ideas he
=> outlines.
Knuth covers some of the same ground in the essay, "What is a random
sequence?" that appears as section 5 of Chapter 3 of Volume 2 of The
Art of Computer Programming. This volume is called, Seminumerical
Algorithms.
Gerry Myerson (ge...@mpce.mq.edu.au)
Charles H. Giffen
Doesn't the connection between normality and incompressibility
depend crucially upon the algorithm(s) for compression allowed?
Although it is quite likely(!?) that any quadratic irrational
is normal, if one uses continued fractions to express numbers,
then quadratic irrationals have ultimately periodic continued
fraction expansions. The most trivial example is, of course,
the Golden Ratio (-1+\sqrt{5})/2 =
1 + 1/(1 + 1/(1 + 1/(1 + 1/( ... )))).
This is no more complicated than the base 10 example of 10/9 =
1.111... .
--Chuck Giffen
r.e.s.
[snip]
: Although it is quite likely(!?) that any quadratic irrational
: is normal, if one uses continued fractions to express numbers,
: then quadratic irrationals have ultimately periodic continued
: fraction expansions.
I don't see why this is quite likely at all.
Wouldn't the periodicity itself be the main
reason to doubt it?
--
r.e.s.
XXr...@mindspring.com (Spam-block=XX)
Kurt Foster
. Kurt Foster wrote:-
.. Obviously a rational number is not normal to any base, because
.. whatever the base, its expansion to that base is either terminating or
.. periodic.
. Are there other classes of number that are known not to be normal?
Sure - numbers known to be missing a nonempty set of digits in their
expansion, e.g. certain Liouville numbers like
SUM, n positive integer, 10^(-n!)
whose decimal expansion has only 1's and 0's; or the Cantor set, whose
members lack any 2's in their ternary expansions.
. I conjecture that every quadratic root is not normal: they can be
. expressed as repeating continued fractions and this suggests a high
. degree of order.
There is no indication AFAIK that this "high degree of order" is
manifest in the distribution of the decimal digits.
. How about other algebraic numbers?
Nobody has a clue. Nobody AFAIK is aware of any algebraic irrational
whose decimal expansion doesn't "look" normal.
Though there is no apparent close connection between the simple
continued fraction expansion and the decimal (or other given base)
expansion of an irrational number there is one remarkable example, due to
Davison IIRC, giving both the simple continued fraction and binary
expansions of the same irrational number.
Charles H. Giffen
(1+\sqrt{5})/2 =
1.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374847540880753868917521266338622235369317931800607667263544333890865959395829056383226613199282902678806752087668925017116962070322210432162695486262963136144381497587012203408058879544547492461856953648644492410443207713449470495658467885098743394422125448770664780915884607499887124007652170575179788341662562494075890697040002812104276217711177780531531714101170466659914669798731761356006708748071...
-- looks pretty normal to me in base 10 (of course that's no proof!).
--Chuck Giffen
Dave L. Renfro
morning for reasons having nothing to do with
normal numbers, I found an additional reference
containing a proof that the set of normal numbers
is a first category (i.e. meager) set in the reals.
Alexander S. Kechris, "Set theory and uniqueness
for trigonometric series", Preprint, 1977, 77 pages.
< http://www.math.caltech.edu/people/kechris.html >
[See proposition 9.4 on pp. 19-20.]
Incidentally (Re Zdislav V. Kovarik's July 16, 1999
post), it is an immediate consequence of the fact
that the generic (i.e. Baire-typical) real number
is non-normal that there exist continuum many
non-normal numbers in every non-degenerate
interval. Moreover, in my earlier post I pointed out
that numbers satisfying much more extreme forms
of non-normality also have this property.