Skip to content

What Is Normal?

June 11, 2012


Normal often mens really special

Émile Borel was a French mathematician who created many fundamental concepts that changed the landscape of math forever. He created what we now call Borel sets, which is one of the main notions of descriptive set theory. He also—somewhat unusual for a mathematician—became a politician. In 1925 he was Minister of Marine in the of cabinet Paul Painlevé, who was also a mathematician. I do not think we have any mathematicians in high positions in governments anymore–was there something special about France in the twenties?

Today I want to talk about the term “normal” as it is used in mathematics, and especially how Borel used it to describe certain numbers.

There are some English words that have many meanings, and there are some words that have many many meanings. The word “run” is one of the champions. Words like “put” and “set” do well in this regard, but “run” is incredible. A fun game is to see how many distinct meanings of the word run you know. Just to start: (i) there is the act of moving fast, (ii) an event in baseball, and (iii) a tear in a stocking.

Here is a list of 89 meanings for “run.” But that is only the beginning: look at this discussion from a radio show on NPR that shows that “run” does really much better than 89:

But when the OED got around to working on the letter R, which they began working on about two years ago, and got towards the end of R and started looking at words beginning with R-U, it became rapidly apparent that run completely outran, if that doesn’t sound a terrible pun, both put and set. And when it was finished, about three weeks ago—I think, Peter Gilliver, who is this extraordinarily clever lexicographer who’s putting it together, he counted out just for the verb alone 645 different meanings. So it’s the absolute champion. So the order is run, put, set.

This is in conversation with the author Simon Winchester, who wrote a wonderful book on the Oxford English Dictionary (OED) titled: The Professor and the Madman: A Tale of Murder, Insanity and the Making of the Oxford English Dictionary. Ken and I definitely recommend the book to you—it is an amazing tale. The original OED was created long before computers, so very clever methods were used to make searches for the definitive definitions of words possible. Winchester’s book is a great read.

Normal

I am not going to get to 645 meanings, but here are a few mathematical meanings of the word “normal.” They are:

  • Normal distribution, the Gaussian continuous probability distribution.
  • Normal subgroup, a subgroup whose right cosets are the same as its left cosets.
  • Surface normal, a vector perpendicular to a surface.
  • Normal to another vector.
  • Extending the last two meanings, the normal vector space of a manifold at a point {P} is the set of the vectors which are orthogonal to the tangent space at {P}.
  • A function {f : Ord \rightarrow Ord} is called normal (or a normal function) if and only if it is continuous (with respect to the order topology) and strictly monotonically increasing. Here {Ord} are the ordinals, as used in set theory.
  • A commutative ring with identity is called normal if it is reduced and {\dots}: see this for details.
  • An algebraic extension {L/K} is called normal if every irreducible polynomial in {K[X]} that has a root in {L} completely factors into linear factors over {L}.
  • In topology, a normal space is a topological space {X} that satisfies Axiom T4: every two disjoint closed sets of {X} have disjoint open neighborhoods.
  • A normal measure is a measure on a measurable cardinal {\kappa}—see this for details.
  • Normal number, a number with a “uniform” distribution of digits.
  • I give up {\dots} There are more, but let’s move on to discuss normal numbers.

Normal Numbers

I would like to focus and discuss one notion of normal: that of a normal number. This was the invention of Borel who created the concept and proved a pretty theorem about normal numbers. Roughly a normal number, in his sense, is a number that looks random at least to certain simple tests.

Consider an infinite string of decimal digits {0.d_{1}d_{2}\dots} that represent the real number {d}. Certainly we would consider {d} not to be “random” if the digit {7} never occurred, or even if it did but only very infrequently. Even more, we would probably consider the number to be non-random if {777} never occurred. The notion of a normal number formalizes this idea as follows:

Call the number {d=0.d_{1}d_{2}\dots} normal provided for any decimal pattern {q} of {k} digits in the long run the pattern {q} occurs {\frac{1}{10^{k}}} of the time. Thus, one tenth of the digits in the limit are {7}, and also in the long run one {1/1000} of the triples of digits are all {7}‘s. More generally, say a number is normal with respect to a base, if the above is true for patterns over that base.

Borel proved the following pretty theorem:

Theorem 1 Almost all real numbers are normal in every base.

Here “almost all” is with respect to measure theory: pick a random real number in {[0,1]}, for instance, and with probability one it will be normal in any base.

Explicit Ones

Mathematics, old and modern, and modern complexity theory share the same fundamental meta problem: Often we can prove the existence of objects with property X or even prove that most objects have property X, but are unable to give explicit examples of objects that have this property. This is very troubling.

But sometimes we can prove that some objects have the property—this happens with normal numbers. There are results about some numbers being normal. However, the results often prove only that the number is normal with respect to one base. For example, David Champernowne proved—as we just discussed here—that his sequence

\displaystyle  0.123456789101112\cdots

is a normal number as a decimal. He also conjectured that if the sequence of all integers were replaced by the sequence of primes then the corresponding decimal

\displaystyle  0.12357111317\cdots

is also normal. Arthur Copeland and Paul Erd\H{o}s proved in 1946 his conjecture and more. They did this by a clever counting argument. Call a function {\delta(N)} para-linear if for every {\theta < 1}, {\delta(N)} outgrows {N^{\theta}}. A set {A} of integers has para-linear density if the cardinality of {A \cap \{1,\dots,N\}} is para-linear. The primes have para-linear density, since their cardinality goes as roughly {N/\log N}.

Theorem: For every increasing sequence of integers of para-linear density, the infinite decimal

\displaystyle  0.a_{1}a_{2}a_{3}\cdots

is normal with respect to the base in which the integers are expressed.

It is not known whether these numbers are normal to all bases.

We can say something weaker than for the Copeland-Erd\H{o}s number made out of primes. Let that number be {\kappa}, and write it in any base {b}. Let {q} be any pattern of digits in base {b}. Then, the pattern does occur infinitely often in {\kappa}. This is a simple consequence of the famous theorem on arithmetic progressions due to Gustav Dirichlet. Let {q^{*} = b^{m}q + 1} where {m} is larger than the number of digits in {q}. Then there are an infinite number of primes {p} of the form

\displaystyle  p = b^{m+1}x + q^{*}.

These primes have the pattern {q} in them, and therefore we have proved our claim. Note, Dirichlet’s theorem can be made stronger and gives precise bounds on how often such primes occur. Perhaps this can be used to prove more.

Note that we need {q^{*}} to be sure that the pattern is relatively prime to the base. Suppose the base was {10} and the pattern {q} was {555}. Then a direct application of the progression theorem would fail, since {10} and {555} are not relatively prime. But {10} and {5551} are.

Open Problems

.

Can you find more meanings for the word normal?

Verónica Becher and Santiago Figueira gave an explicit example of a computable number that is normal in any base. See their paper for details. Their proof is based on a 1916 theorem of Waclaw Sierpiński, who supplied the first explicit example, although it was not clear that his number was computable. Note, he proved it way before the notion of computable was even available.

I conjecture that there should be an easy proof that shows that some explicit number is normal in any base. The rationale for the conjecture is the observation that the property that defines normal is computable by a logspace machine, and thus I think we should be able to exploit that.

14 Comments leave one →
  1. June 11, 2012 4:12 pm

    Professor Daniel Hershkowitz, the Israeli Minister of Science and Technology, is a mathematician…🙂

  2. Serge permalink
    June 11, 2012 4:17 pm

    > “I do not think we have any mathematicians in high positions in governments anymore–was there something special about France in the twenties?”

    That was only a few years after Henry Poincaré’s death in 1912. He’s often called the last universalist. He was a cousin of Raymond Poincaré, then president of France. I suppose the tradition you’re referring to was first established by him.

    > “Normal often means really special”

    Our newly elected president François Hollande prides himself on being normal, so I believe he must be a lot more special than he claims to be…🙂

  3. June 11, 2012 6:02 pm

    “I do not think we have any mathematicians in high positions in governments anymore”

    The current president of Singapore has a PhD in applied math:

    http://en.wikipedia.org/wiki/Tony_Tan_Keng_Yam

  4. John Sidles permalink
    June 11, 2012 8:14 pm

    Here are five adjectives that appear nowhere in Mathematical Review (in alphabetical order): gnostic, hirsute, ornery, rollicking, and washable.

    These five were found *without* consulting a thesaurus, and please let me say, it’s not easy to find unused mathematical words!

    What other virginal mathematical words still exist? (Hmmm … what about ”virginal” itself? Oops! ”Virginal” isn’t virginal).🙂

  5. June 12, 2012 1:58 am

    Here is a math-overflow quation about overloaded words in mathematics: http://mathoverflow.net/questions/7389/what-are-the-most-overloaded-words-in-mathematics-closed . (Normal was number 2 in popularity after regular.)

  6. Anon permalink
    June 12, 2012 9:59 am

    For what it’s worth, Rush Holt (D-NJ) is a physicist.

  7. June 12, 2012 1:32 pm

    “I conjecture that there should be an easy proof that shows that some explicit number is normal in any base.” Not sure what you mean by “easy”, but Chaitin’s Omega is normal in any base. Indeed so is any 1-random. This is pretty easy to prove.

  8. June 12, 2012 3:35 pm

    For what its worth, India’s Prime minister (Manmohan Singh) is a Phd in Economics (a math heavy subject) from Oxford:

    http://en.wikipedia.org/wiki/Manmohan_Singh#Early_life_and_education

  9. June 12, 2012 3:44 pm

    And Angela Merkel also has a PhD in physics…

  10. Siddharth permalink
    June 12, 2012 5:09 pm

    Could you elaborate or give a reference to how normal is computable using a logspace machine?

  11. Yamado permalink
    June 17, 2012 6:30 am

    Émile Borel was also diplomed of the french “École Normale Supérieure”.

  12. June 27, 2012 1:54 pm

    Typo fix: “Normal often MEANS really special” (not “mens”)

Trackbacks

  1. Thinking Out of the Notation Box « Gödel’s Lost Letter and P=NP
  2. Adding Dollar Signs « Gödel’s Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s