Fractions repeat and roots look random

Writing a number in base φ, the golden ratio, means multiplying by φ, taking the whole part as the next digit, and keeping the fractional part: $x \mapsto \varphi x \bmod 1$. The digits are 0 and 1, and the one rule they obey is that two 1s never touch. Following that map for a long time showed where a typical orbit spends its time — unevenly, on a staircase found by Rényi and Parry — and so how often a typical number’s expansion uses each digit: the digit 1 about 27.64 per cent of the time, which is $1/(1 + \varphi^2)$.

“Typical” there means almost every: the numbers whose digits do something else form a set of total length zero. It says nothing about any particular number. The same gap exists in base 2 and base 10, where almost every number is normal and no natural constant is known to be. This essay asks the question for base φ about four particular numbers, two fractions and two irrationals, and gets two completely different kinds of answer.

Four numbers, digit by digit #

Computing base-φ digits of a particular number is harder than it looks, because the map stretches errors: each step multiplies any error by φ. So the digits here are computed exactly. The fractions are handled in exact arithmetic on numbers of the form $(a + b\varphi)/q$ with whole $a$, $b$, $q$; the irrationals are handled with whole numbers of more than eight thousand binary digits, enough for twelve thousand steps, and the whole computation is repeated with three hundred more bits to confirm that no rounding has reached the digits used.

The contrast is visible at once. The expansion of $1/3$ is the block 00101000 repeated for ever; that of $2/7$ is a block of sixteen digits repeated for ever. The expansions of $\sqrt2 - 1$ and $1/\pi$ show no pattern at all in their first 72 digits, and none appears in the first twelve thousand.

The fractions repeat for a reason that is easy to state and has a surprising consequence. Write the current remainder as $(a + b\varphi)/q$. Multiplying by φ uses $\varphi^2 = \varphi + 1$ to give $(b + (a+b)\varphi)/q$, and subtracting the digit changes only the whole-number part. So the pair $(a, b)$ steps along like a pair of Fibonacci numbers, corrected by a multiple of $q$ whenever a 1 is written. The remainder always lies between 0 and 1, and so does its “conjugate” with φ replaced by $-1/\varphi$, which keeps $a$ and $b$ bounded; a bounded pair of whole numbers can take only finitely many values, so the remainders must eventually repeat, and with them the digits.

The eight remainders of a third #

The cycle for $1/3$ can be written out completely. Start with $a = 1$, $b = 0$, so the remainder is $1/3$. Multiplying by φ gives $\varphi/3 \approx 0.539$, less than one, so the first digit is 0 and the new pair is $(0, 1)$. Then $(1 + \varphi)/3 \approx 0.873$, digit 0 again, pair $(1, 1)$. Then $(1 + 2\varphi)/3 \approx 1.412$, so the digit is 1 and subtracting one leaves $(-2 + 2\varphi)/3 \approx 0.412$, the pair $(-2, 2)$.

Continuing, the pairs run through $(2, 0)$, $(-3, 2)$, $(2, -1)$ and $(-1, 1)$ — remainders of about 0.667, 0.079, 0.127 and 0.206 — and the next step returns to $(1, 0)$, the starting third. Eight remainders, eight digits, 0 0 1 0 1 0 0 0, and then the same eight again for ever. Every one of the eight is a number of the form $(a + b\varphi)/3$ with small $a$ and $b$, and every comparison that decides a digit is made exactly, by squaring, with no decimal approximation at any point.

The pairs stay small for a reason worth seeing. Replace φ everywhere by its partner $-1/\varphi \approx -0.618$, the other root of $x^2 = x + 1$. The same pairs then describe a second sequence of numbers, and the step that multiplies the real remainder by φ multiplies this shadow by $-0.618$, shrinking it, while the digits subtracted are whole numbers of size at most one. A sequence that shrinks by a fixed factor and receives bounded kicks stays bounded. Both the remainder and its shadow are bounded, so $a$ and $b$ are, and a bounded pair of whole numbers has only finitely many values to visit.

The period is the Fibonacci period #

The argument says the expansion of a fraction must repeat. How long it takes is decided by the same arithmetic.

The computation finds two things for every fraction with denominator up to twenty. The repetition starts at the very first digit — no fraction has a preamble before its block begins. And every fraction in lowest terms with the same denominator has the same period: 3 for halves, 8 for thirds, 6 for quarters, 20 for fifths, and so on up to 60 for twentieths.

Those numbers are familiar from elsewhere: they are the Pisano periods, the lengths after which the Fibonacci numbers repeat when reduced modulo $q$. The Fibonacci numbers modulo 3 run 0, 1, 1, 2, 0, 2, 2, 1 and then start again, a period of eight, and $1/3$ repeats every eight digits in base φ. The reason is in the step just described. Modulo $q$, subtracting a multiple of $q$ changes nothing, so the pair $(a, b)$ reduced modulo $q$ steps exactly like consecutive Fibonacci numbers modulo $q$, starting from $(p, 0)$. It returns to its starting value after exactly one Pisano period when $p$ is coprime to $q$, so the full state cannot repeat sooner; the computation shows it repeats exactly then, for every denominator drawn. Klaus Schmidt proved in 1980 that for bases like φ every rational number has an eventually periodic expansion; the figure adds, for these denominators, what the period is.

The consequence is the point for this essay. A repeating expansion has digit frequencies fixed by its block: $1/3$ uses the digit 1 twice in every eight digits, so its frequency of 1s is exactly a quarter, not 27.64 per cent. Every rational number in the interval — and, by the same argument, every number of the form $(a + b\sqrt5)/c$ — belongs to the exceptional set of measure zero. None of them is typical in base φ.

Numbers built from the base itself #

The same argument covers more than fractions. Any number of the form $(a + b\sqrt5)/c$ with whole $a$, $b$, $c$ is also of the form $(a' + b'\varphi)/c'$, and its remainders stay in a finite set in exactly the same way. So its expansion is eventually periodic too.

Some of these are very short. The number $1/\varphi = \varphi - 1 \approx 0.618$ has expansion 0.1000…, a single 1 followed by zeros for ever, because multiplying it by φ gives exactly one. Its square, $1/\varphi^2 \approx 0.382$, is 0.01000…, and in general a sum of distinct powers $\varphi^{-k}$ with no two consecutive exponents is a terminating expansion, the base-φ counterpart of a finite decimal. These are the numbers the base can write in finitely many digits, just as base ten writes a tenth and not a third.

Base φ is unusual in one respect: the whole numbers themselves have terminating expansions in it, though finding them takes some care — the number 2 is $\varphi + \varphi^{-2}$, written 10.01 — and every positive whole number has one. That is a relative of Zeckendorf’s representation of whole numbers as sums of non-consecutive Fibonacci numbers, and it is another sign that the arithmetic of φ and the arithmetic of Fibonacci numbers are one arithmetic. The periods in the figure above are the same fact again, seen modulo $q$.

Two irrationals that look typical #

For $\sqrt2 - 1$ and $1/\pi$ there is no repetition to find, and the natural test is to compare their digits with what a typical number’s digits do.

Every block matches. The digit 1 occurs 27.63 per cent of the time in $\sqrt2 - 1$ and 27.86 per cent in $1/\pi$, against 27.64; the blocks 00, 01 and 10 occur about 44.7, 27.6 and 27.6 per cent of the time, as predicted; and the blocks of three match too, including the ones that are rarer than a naive guess would suggest, such as 101 at about 10.6 per cent. The predictions come from a simple rule: after a 1 the next digit must be 0, and after a 0 the next digit is 0 with chance $1/\varphi$ and 1 with chance $1/\varphi^2$. That is the chain the symbolic description of the map leads to, and both numbers follow it as closely as twelve thousand samples can show.

The running averages show the difference between the two kinds of number in motion. The irrationals wander above and below the line and close in on it, as a random sequence’s average would. The fraction locks on to a quarter within a few dozen digits and never moves again. Nothing distinguishes $\sqrt2 - 1$ from a number chosen at random, and everything distinguishes $1/3$.

Why the agreement proves nothing #

It is tempting to read the block figure as evidence that $\sqrt2 - 1$ is normal in base φ, and in a statistical sense it is. As proof it is worth nothing. Normality is a statement about the limiting frequency of every block, of every length, over infinitely many digits. Twelve thousand digits constrain the frequencies of short blocks to within a per cent or so and say nothing about blocks of length thirty, of which there are more than a million admissible ones, nor about what happens after the twelve-thousandth digit.

This is the same position as for $\pi$ in base ten, where trillions of digits have been computed, every statistical test passes, and there is no proof that the digit 7 occurs at all infinitely often. What is known for base φ is structural: numbers of the form $(a + b\sqrt5)/c$ are periodic and never normal; almost every other number is normal; and no specific number outside the first class is known to be in the second. One can construct numbers that are provably normal in base φ, by concatenating admissible words in a careful order as Champernowne did for base ten, but such numbers are built to be normal and are not constants anyone met for another reason.

There is a partial link between bases. Since $\sqrt2 - 1$ is irrational and not in $\mathbb{Q}(\sqrt5)$, its base-φ expansion cannot be eventually periodic, because Schmidt’s theorem runs both ways for numbers of this kind: an eventually periodic expansion in base φ always represents a number of $\mathbb{Q}(\sqrt5)$. So $\sqrt2 - 1$ is certainly not in the periodic class. Whether it is in the typical class is open, exactly as its normality in base 2 or base 10 is.

A double carries seventy-four digits #

The exact arithmetic was not a luxury. Iterating the map in ordinary floating-point arithmetic is the obvious way to generate digits, and it fails quickly.

A double-precision number carries 53 binary digits. Each step of the map multiplies the error by φ, which costs $\log_2 \varphi \approx 0.694$ bits, so after about $53 / 0.694 \approx 76$ steps no correct information about the starting number remains. The figure finds the first wrong digit at step 75. After that the computed orbit is a perfectly good orbit of the map — of some other starting point, which is the shadowing property at work — and says nothing about $\sqrt2 - 1$.

That rate of loss is the Lyapunov exponent of the map, $\log \varphi$, measured in bits. Computing twelve thousand digits correctly requires carrying about 8,330 bits, plus a margin, from the start, which is what the exact computation does, and checking that a run with more bits agrees is the only way to know the margin was enough. A histogram of a million floating-point steps, as in the essay on where the orbit spends its time, is a fine sample of typical behaviour. It is not a computation of the digits of any number named in advance.

What the computation cannot show #

The periods of fractions are computed exactly, and the equality with Pisano periods is checked for every denominator up to twenty; the argument above explains why the period is at least the Pisano period and the computation shows equality in those cases. It is not a proof for every denominator, although the argument makes the general statement very plausible.

The digits of $\sqrt2 - 1$ and $1/\pi$ are correct to twelve thousand places, confirmed by a second computation at higher precision. Their statistics are what they are: consistent with normality, and incapable of establishing it. And the Parry predictions for blocks of three are compared with twelve thousand overlapping samples, which are not independent; the agreement to within a few sampling errors is the honest claim, not agreement to a stated confidence.

Other bases with the same arithmetic #

Nothing in the periodicity argument was special to φ except two properties: φ is a root of a whole-number polynomial with leading coefficient one, and its other root is smaller than one in size. Numbers with those properties — algebraic integers all of whose other roots lie strictly inside the unit circle — are the Pisot numbers, and for every Pisot base the same argument shows that every element of the corresponding number field has an eventually periodic expansion. The tribonacci constant $1.839\ldots$, root of $x^3 = x^2 + x + 1$, and the plastic number $1.3247\ldots$, root of $x^3 = x + 1$, are examples, and in both every rational has a repeating expansion.

For bases with a conjugate on the unit circle, the Salem numbers, the argument fails, because the shadow no longer shrinks. Whether rationals still have eventually periodic expansions there is open, and it is the same difficulty as the question raised about the expansion of 1 in those bases, which is settled only for Salem numbers of degree four and some of degree six. For a transcendental base, nothing about particular numbers is known at all.

Still open: one specific number #

It is not known whether $\sqrt2 - 1$ is normal in base φ, or whether $1/\pi$ is, or whether any algebraic irrational outside $\mathbb{Q}(\sqrt5)$ is. The corresponding questions in base 2 and base 10 are among the best-known open problems about numbers, and there is no reason to expect base φ to be easier.

What is known is that the obstacle is not special to integer bases. In base 10 the rationals are periodic, the numbers built for the purpose are normal, and the constants of analysis and algebra are unknown. In base φ the periodic class is larger — all of $\mathbb{Q}(\sqrt5)$ — the normal class is again almost everything, and the constants are again unknown. The dynamics has changed; the ignorance has not.

What a particular number tells the map #

The map $x \mapsto \varphi x \bmod 1$ treats almost every number the same way, and that uniformity is a theorem. Particular numbers split into those the arithmetic of φ can see — fractions and numbers built from $\sqrt5$, whose orbits cycle with Fibonacci periods — and those it cannot, whose orbits look exactly like a random one and cannot be proved to be. The digits of $1/3$ repeat because $1/3$ lives in the same number system as φ. The digits of $\sqrt2 - 1$ look random because it does not, and that is as far as anyone can take it.

The division is sharper than in base ten, where the only numbers the base can see are the fractions. In base φ it can also see $\sqrt5$ and everything built from it, and it sees them through the Fibonacci numbers: the period of a fraction is a Fibonacci period, the terminating expansions are sums of powers of φ that avoid consecutive exponents, and the whole numbers are written by the same rule as Zeckendorf’s. What the base cannot see, it treats exactly as chance would — as far as any finite computation can tell.