What Is Normal?

É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 is the set of the vectors which are orthogonal to the tangent space at .
• A function 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 are the ordinals, as used in set theory.
• A commutative ring with identity is called normal if it is reduced and : see this for details.
• An algebraic extension is called normal if every irreducible polynomial in that has a root in completely factors into linear factors over .
• In topology, a normal space is a topological space that satisfies Axiom T4: every two disjoint closed sets of have disjoint open neighborhoods.
• A normal measure is a measure on a measurable cardinal —see this for details.
• Normal number, a number with a “uniform” distribution of digits.
• I give up 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 that represent the real number . Certainly we would consider not to be “random” if the digit never occurred, or even if it did but only very infrequently. Even more, we would probably consider the number to be non-random if never occurred. The notion of a normal number formalizes this idea as follows:

Call the number normal provided for any decimal pattern of digits in the long run the pattern occurs of the time. Thus, one tenth of the digits in the limit are , and also in the long run one of the triples of digits are all ‘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 , 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

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

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 para-linear if for every , outgrows . A set of integers has para-linear density if the cardinality of is para-linear. The primes have para-linear density, since their cardinality goes as roughly .

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

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 , and write it in any base . Let be any pattern of digits in base . Then, the pattern does occur infinitely often in . This is a simple consequence of the famous theorem on arithmetic progressions due to Gustav Dirichlet. Let where is larger than the number of digits in . Then there are an infinite number of primes of the form

These primes have the pattern 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 to be sure that the pattern is relatively prime to the base. Suppose the base was and the pattern was . Then a direct application of the progression theorem would fail, since and are not relatively prime. But and 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.