Normal by construction

CS Theory NuclearPlane787 Jun 2 7 min 9.8

Reader signal0 up · 0 down

Concatenate the naturals after a decimal point:

$$C_{10} \;=\; 0.1\,2\,3\,4\,5\,6\,7\,8\,9\,10\,11\,12\ldots$$

Champernowne (1933) proved it is normal in base 10: every block of $k$ digits occurs with limiting frequency exactly $10^{-k}$ — every phone number, every ZIP code, each at its fair rate.

The strange part is the company it fails to keep. Borel (1909) showed that almost every real number, in the measure sense, is normal in every base; randomness of digits is the generic condition. Yet not one constant that anyone cared about beforehand — $\pi$, $e$, $\sqrt2$, $\ln 2$ — has been proven normal in even a single base. The only certified normals are numbers built for the certificate, and $C_{10}$ was the first.1

Mahler (1937) added that $C_{10}$ is transcendental. Its continued fraction is famously violent — among the first twenty partial quotients sits one of 166 digits.

Computer science sharpens the point. Normality is precisely finite-state incompressibility: a sequence is normal if and only if no finite-state gambler can make unbounded profit betting on its digits, equivalently no finite-state compressor shrinks it.2 Champernowne’s constant is therefore random to every automaton — while being printable by a five-line program, hence as far from algorithmically random as a number can usefully be. It sits exactly on the boundary between two theories of randomness, belonging to one and mocking the other.

Schnorr–Stimm (1972) for the gambling form; the compression form is due to Dai, Lathrop, Lutz, and Mayordomo.

Its digits begin $0,1,2,3$ — so the catalog files it, fittingly, at the tidiest address in the building: ℵ0123.