Fair in base two and not in base six

Fractions repeat and roots look random ended on an embarrassment. A number is normal in a base if every block of digits occurs in its expansion with the frequency fairness demands — each digit a tenth of the time in base 10, each pair a hundredth, and so on for ever. Émile Borel proved in 1909 that almost every number is normal in every base at once. And yet for $\sqrt 2$, $\pi$, $e$, or any number anyone meets for a reason other than its digits, normality is unknown in every base — not even known is whether half the binary digits of $\sqrt 2$ are ones.

That essay asked for one specific number. The numbers known to be normal are mostly built for the purpose: David Champernowne’s 0.123456789101112…, written by listing the whole numbers, is normal in base 10 by construction and not by any accident. There is a small class of exceptions — numbers given by a formula with no reference to digits that have been proved normal in a base — and the oldest and simplest of them is Richard Stoneham’s:

$$\alpha = \sum_{k \ge 1} \frac{1}{3^k\, 2^{3^k}} = \frac{1}{3 \cdot 2^3} + \frac{1}{9 \cdot 2^9} + \frac{1}{27 \cdot 2^{27}} + \cdots$$

David Bailey and Richard Crandall proved in 2002 that $\alpha$ is normal in base 2. The surprise is what happens in base 6.

Normal means an orbit spreads evenly #

Normality is a statement about dynamics. The doubling map $x \mapsto 2x \bmod 1$ shifts a number’s binary digits one place to the left and drops the one that falls off, so following $x$’s orbit is reading its binary digits one at a time: the orbit lands in $[0, \tfrac12)$ exactly when the next digit is 0, in $[\tfrac14, \tfrac12)$ when the next two are 01, and so on. A number is normal in base 2 exactly when its orbit under doubling visits every interval in proportion to its length — the property an orbit’s histogram measures. In base 6 the map is $x \mapsto 6x \bmod 1$.

Birkhoff’s ergodic theorem says that almost every orbit is fair, which is Borel’s theorem in dynamical language. It says nothing about any particular orbit, and that is the gap Stoneham’s number crosses. Its orbit under doubling is evenly spread; its orbit under multiplication by six is not. One number, two shifts, two opposite verdicts — and both are theorems.

The binary digits look fairer than fair #

Computed exactly to two hundred thousand binary places — each term is one integer division, and the terms die out after $3^{11} = 177{,}147$ places — the digits of $\alpha$ pass every block test the figure applies. So do the digits of $\sqrt 2$, computed by an integer square root to the same depth, and $\sqrt 2$ looks, by this measure, exactly like a run of fair coin tosses: its worst block departure tracks the coin’s typical value at every block length.

Stoneham’s number does something stranger. Its worst departures are far smaller than a coin’s — 0.0011 for single digits against the coin’s 0.0037, 0.086 for blocks of ten against 0.27. Its digits are too even to be random. That is the fingerprint of how it is built: not from independent choices but from a few periodic patterns laid over one another, which spread more evenly over a finite stretch than chance does. Normality is a statement about the limit, and it is compatible with being suspiciously regular on the way.

Computing the digits exactly #

None of these figures could be drawn in ordinary floating-point arithmetic. A double-precision number carries 53 binary digits, so the doubling map applied to it runs out of digits after 53 steps and lands on nought for ever; any orbit of more than a few dozen steps computed that way is an orbit of the rounding, not of the number.

Stoneham’s formula makes exact computation easy. To get the first $N$ binary digits, multiply $\alpha$ by $2^N$: the $k$-th term becomes $2^{N - 3^k}/3^k$, whose whole-number part is a single division of a power of two by a power of three. Adding those parts for every $k$ with $3^k \le N$ gives $2^N \alpha$ to within a few units in the last place, and the last 64 digits are thrown away to make the rest certain. In base 6 the computation is cleaner still: $6^M \alpha$ is a sum of whole numbers $3^{3^k - k} \cdot 6^{M - 3^k}$, plus a tail smaller than one, so its base-6 digits are exactly the digits of $\alpha$. For $\sqrt 2$ the binary digits come from the integer square root of $2 \cdot 4^N$, found by Newton’s method in whole numbers. None of the three computations takes more than a fraction of a second, and none involves a single rounded number.

In base two every term repeats for ever #

The binary expansion of $1/3^k$ is periodic, and its period is the number of times 2 must be multiplied by itself before it leaves remainder 1 on division by $3^k$ — the multiplicative order of 2 modulo $3^k$, which is $2 \cdot 3^{k-1}$. So the $k$-th term of $\alpha$ begins at binary place $3^k$ and from there on repeats a block of $2 \cdot 3^{k-1}$ digits for ever. Every term overlaps every later one; the binary digits of $\alpha$ are the result of adding infinitely many periodic patterns, with carries.

That 2 has the largest possible order modulo every power of 3 — it is a primitive root — is the engine of Bailey and Crandall’s proof. Each term’s period is as long as it can be, so each periodic block runs through a complete set of residues, and the superposition, read through the doubling map, cannot favour any region of the interval. The argument is a careful estimate of how evenly the points $2^n \alpha$ fall, built on exactly this structure, and it is one of very few routes known from a formula to a proof of normality.

Too even to be random, and still normal #

The extra evenness in the second figure is worth a moment, because it says something about what normality is and is not. A sequence of genuinely random bits fluctuates: over two hundred thousand digits, some block of ten will turn up about a quarter more or less often than its fair share, simply by chance. Stoneham’s digits fluctuate far less. They behave like points placed too evenly to be random — the low-discrepancy sequences of quasi-Monte Carlo integration, which beat random sampling precisely by refusing to clump — and for the same reason: they are built from a few structured pieces whose irregularities cancel.

Normality cannot tell these apart from randomness, because it is a statement about limiting frequencies only, and both random bits and too-even bits have the right limits. A normal number need not look random at any finite scale in any other sense, and a number that passes every frequency test can still be completely predictable — Stoneham’s digits are generated by a two-line formula, and Champernowne’s by counting. This is the distinction a generator of random numbers has to respect, between statistics that look right and a stream that cannot be predicted: a sequence is useful for simulation if its statistics are right and useful for secrecy only if, in addition, nobody can find the formula. Bailey and Crandall in fact proposed Stoneham-type numbers as pseudorandom generators, with the attraction that their equidistribution is a theorem rather than a hope.

In base six every term stops #

The same number in base 6 has a completely different anatomy. Each term is

$$\frac{1}{3^k\, 2^{3^k}} = \frac{3^{3^k - k}}{6^{3^k}},$$

a whole number divided by a power of 6, so in base 6 it is a terminating fraction: the base-6 digits of the whole number $3^{3^k - k}$, ending exactly at place $3^k$.

The whole number $3^{3^k - k}$ has about $(3^k - k)\log_6 3$ base-6 digits, and $\log_6 3 = 0.613$, so the $k$-th term occupies places from about $0.387 \cdot 3^k$ to $3^k$. The next term begins at about $0.387 \cdot 3^{k+1} = 1.161 \cdot 3^k$. Between $3^k$ and $1.161 \cdot 3^k$ no term writes anything, and the digits there are all zero: 16 zeros after place 81, 42 after 243, 121 after 729, 356 after 2,187, 1,058 after 6,561, and so on, each run about 16% as long as its starting position. The figure’s computation checks every digit in every gap among the first sixty thousand.

That is enough to rule out normality. A normal number cannot spend a fixed fraction of every stretch of its digits writing zeros, and Stoneham’s number does exactly that, at every power of three. David Bailey and Jonathan Borwein made the argument precise in 2012: $\alpha$ is normal in base 2 and not normal in base 6, and more generally each Stoneham number of the same shape is normal in one base and abnormal in another that the formula singles out.

The share of zeros never settles #

In base 6 a fair share of zeros is one in six. The running share for $\alpha$ climbs to about 0.345 at the end of every gap — 0.362, 0.365, 0.345, 0.344, 0.345, 0.343 at the ends of the gaps after $3^4$ to $3^9$ — and sinks back towards a sixth across each stretch where a term is being written, only to climb again at the next power of three. It oscillates for ever on a logarithmic clock, and so the digit 0 has no limiting frequency in base 6 at all.

The peak value can be predicted from the anatomy alone. At the end of the $k$-th gap, near place $1.161 \cdot 3^k$, every earlier gap has contributed its zeros — about $0.161 \cdot 3^j$ for each $j \le k$ — and every earlier term has contributed a sixth of its $0.613 \cdot 3^j$ digits, if the digits of the powers of three are themselves evenly spread. Summing the geometric series over $j$ gives about $\tfrac32 (0.161 + 0.102) \cdot 3^k$ zeros, which is 0.34 of the $1.161 \cdot 3^k$ digits read. The measured peaks, 0.343 to 0.365, agree; the small excess at the early gaps is the rounding in small powers of three. Normality fails not by a bias but by a refusal to settle.

Two orbits of one number #

The two expansions are two orbits. Under doubling, a hundred thousand steps of $\alpha$’s orbit fill the interval evenly: the first of 24 bins holds 4.15% against a fair 4.17%. Under multiplication by six, forty thousand steps pile into the first bin, which holds 15.7%, because during every run of zeros the orbit sits just above nought: a number whose next hundred base-6 digits are zero is within $6^{-100}$ of nought, and each multiplication by six carries it only one digit’s worth further away. The same shift on a different alphabet sees a different number.

There is a satisfying symmetry in which maps see which. Multiplying by 2 and by 3 are, in a precise sense, independent operations — no power of 2 is a power of 3 — and Hillel Furstenberg proved in 1967 that a closed set carried into itself by both must be finite or the whole interval — and conjectured the corresponding statement for probability distributions, which is still open. Stoneham’s number is built so that powers of 2 scramble it and powers of 6 do not, which is possible only because 6 contains the 3 that the formula’s denominators are made of.

Other bases, and why the square root of two is harder #

Normality in one base settles some others. A number is normal in base 2 exactly when it is normal in base 4, or 8, or any power of 2, because a block of base-4 digits is a block of binary digits read two at a time; so Stoneham’s number is normal in every base $2^m$. In base 6, and in any base whose powers are related to 6 in the same way, the gaps make it abnormal. In base 3, or base 10, nothing is known in either direction. Normality in bases that are not powers of one another is genuinely independent: there are numbers normal in base 2 and not in base 3, and the reverse, and constructing such numbers was one of the first uses of the dynamics of $\times 2$ and $\times 3$.

For $\sqrt 2$ the gap between what is believed and what is known is wider than for any constructed number. Borel conjectured in 1950 that every irrational algebraic number is normal in every base, and the evidence — trillions of digits of $\sqrt 2$ that look exactly like the coin in the second figure — is overwhelming. What has been proved is almost nothing: David Bailey, Jonathan Borwein, Richard Crandall and Carl Pomerance showed in 2004 that among the first $N$ binary digits of $\sqrt 2$ at least about $\sqrt{2N}$ are ones, a bound that comes from the fact that $\sqrt 2$ squared is a whole number and that its square’s digits must carry somewhere. A fair share would be $N/2$. The same pattern holds for the digits of a root lifted one place at a time in a $p$-adic base: every digit can be computed, and nobody can prove that the digits are evenly spread.

What the computation cannot show #

Every digit in every figure is exact: the binary digits come from integer division, the base-6 digits from adding whole numbers, and only the last 64 binary places — where carries from the infinite tail could reach — are discarded. But normality is a statement about infinitely many digits, and no computation reaches it. The binary figures show that two hundred thousand digits are spread more evenly than coin tosses; the proof that they stay so is Bailey and Crandall’s, and nothing in the figures could replace it.

The base-6 failure is different in kind, because the gaps can be proved from the formula, digit by digit, for every power of three — the computation only illustrates them. That asymmetry is the general one. Abnormality can be exhibited, since it needs only a pattern that recurs; normality can only be proved, since no finite stretch of digits says anything about the rest.

Still open: a number met for another reason #

Is any constant that arises outside the study of digits normal in any base? Stoneham’s numbers, and the related numbers of Bailey and Crandall built from the hypothesis that certain formulas for $\pi$, $\log 2$ and their relatives behave like random generators, sit on the boundary: they have formulas, but formulas chosen for their arithmetic. For $\pi$, $e$, $\sqrt 2$ and $\log 2$ themselves normality is open in every base, and so is the weaker statement that every digit appears with positive frequency. Bailey and Crandall showed that the normality of $\pi$ in base 16 would follow from a hypothesis about a specific chaotic sequence of the kind their proof handles, so the gap has been narrowed to a precise statement about the uniformity of one sequence — and that statement is unproved, in the same way and for the same reasons as the arcsine law for the cosines of the powers of two.

A normal number with a blind spot #

Stoneham’s number is a sum of fractions that never stop in base 2 and always stop in base 6, and that one fact decides both of its fates. In base 2 each term is the repeating expansion of $1/3^k$, whose period $2 \cdot 3^{k-1}$ is as long as it can be, and the superposition is provably normal — more even, over two hundred thousand digits, than fair tosses. In base 6 each term is a whole number ending at place $3^k$, the gaps between them are zeros, the share of zeros swings up to about 0.345 at every power of three, and the orbit under multiplication by six lingers near nought: normal for one shift, abnormal for another, and a theorem both ways.