Almost All Numbers Are Normal

“Almost All Numbers Are Normal” is a delightful sentence. In just five words, it relates three mathematical concepts, in a way which is true but misleading - the meaning of the sentence is almost exactly the opposite of what a layman would expect.

Numbers

The intuitive conception of “numbers” if you ask someone to simply “name a number” are the natural numbers $\mathbb{N}$ (0¹, 1, 2, 3, …), or the integers $\mathbb {Z}$ (… -3, -2, -1, 0, 1, 2, 3, …). Of course most folks are familiar with the rationals $\mathbb{Q}$, though probably by the name of and through the lens of “fractions” rather than the more mathematically-precise objects - and even those only scratch the surface of the full set of real numbers $\mathbb{R}$ and beyond.

There are plenty of ways to conceptualize some of these sets of numbers - typically as the unique (up to isomorphism) structure satisfying some particular set of axioms like Peano’s or Dedekind’s - but for the purposes of this post, I want to consider the reals² as an infinite sequence³ of digits 0-9, or equivalently as a function $f: \mathbb{N} \to {0, 1, 2, \cdots 9}$. That is, the number 7394.23 is equivalent to the function partially represented by the following table:

I say partially represented, because of course this table could continue infinitely - for any index greater than 6, the function’s value is 0: [$\forall n > 6, f(n) = 0$].

This way of describing numbers focuses less on their value, and more on their written representation - it stresses the ability to ask “what is the fifth digit of this number?” much more than the ability to ask “which of these two numbers is bigger?”. This focus will be justified in the next section.

Normality

The word “normal” has lots of domain-specific meanings in mathematics, many of them related to one of two concepts:

• orthogonality - that’s fancy mathematician speak for “being at 90-degrees to something”⁴. For instance, we could say that a skyscraper is orthogonal to, or normal to, the ground, because it points straight upwards and the ground is horizontal.
• of or related to the norm, which itself is a function that assigns a length-like value to mathematical objects.

In particular - I don’t think I’ve ever heard the term “normal” used in its layman’s sense of “standard, expected, regular, average”⁵. I guess mathematicians don’t think it’s very normal to be normal.

In number theoretic terms, a normal number⁶ is one in which all digits and sequences of digits occur with the same frequency - no digit or sequence is “favoured”. The string of digits looks like it could have been the output of a random number like coin-flipping (for binary digits) or repeatedly rolling a d10.

It’s pretty easy to immediately see that no number with terminating decimal expansion (which includes all the integers, and all fractions with a denominator of a power of 10) are not normal - if the sequence of digits starts repeating 0, then 0 is “favoured”, and the number is not normal. A little more thought shows that every rational number (every fraction) is abnormal - either the division terminates (and the decimal expansion continues 000...), or the decimal expansion repeats (and so the repeated-string is “favoured”, and any string which didn’t appear before point that is absent).

Corrolary of normalcy

A fun property of normal numbers is that, because all subsequences are “equally likely”, and because they are infinite non-repeating sequences, any given sequence of numbers must exist somewhere in them. Since any content that is stored on a computer is stored as a sequence of numbers, this implies that any content you could imagine - your name and birthday, the Director’s Cut of Lord Of The Rings, a sequence of statements which prove that almost all numbers are normal - exists somewhere within each of them.

The trick would be finding it…

Almost All

Along with “normal”, this is a common term which has a specified mathematical meaning - although, in this case, the meaning is intuitive⁷, just formally-defined.

A property is said to hold for “almost all” elements of a set if the complementary subset of elements for which the property does not hold is negligible. The definition of negligible depends on the context, but will typically mean:

• A finite set inside an infinite set ("almost all natural numbers are bigger than 10" - because the set of numbers smaller-than-or-equal-to 10 is finite, and the set of naturals is infinite)
• A countable set inside an uncountable one, or generally a “smaller” infinity inside a bigger one.

This is probably the least surprising of the three concepts, but it does take a while for Maths undergrads to get their head round the co-feasibility of the statements “P(x) is true for almost all x in S” and “P(x) is false for infinite x in S”.

Putting it all together

So, putting it all together - “almost all numbers are normal” could be roughly translated as “when considering the set of functions which map from $\mathbb{N}$ to ${0, 1, 2, … 9}$, a negligible set of those functions result in sequences which have subsequences roughly evenly distributed”. Which is about as far as you could get from the results you’d get if you asked a layman to name some normal numbers - small natural numbers!

(I’m not actually going to present a proof of that fact here - I vaguely recall the shape of it, but being over a decade out of study, it’s a little beyond my capability to present understandably. There are some reasonably accessible proofs here and here if you’re interested!)

• mathematics