Counting in a base that is not a whole number

The doubling map writes every number in binary: double it, and the whole part that falls off is the next binary digit. The same machine works with any multiplier. Multiply by $\beta$, record the whole part $\lfloor \beta x \rfloor$, keep the fractional part, and repeat; the recorded digits $d_1 d_2 d_3 \dots$ satisfy

$$x = \frac{d_1}{\beta} + \frac{d_2}{\beta^2} + \frac{d_3}{\beta^3} + \cdots,$$

which is $x$ written in base $\beta$. Nothing requires $\beta$ to be a whole number. The expansions were introduced by Alfréd Rényi in 1957, and they turn out to be an unusually clean case of what symbolic dynamics is for: the map is simple, the digits are its itinerary, and the question of which digit strings can occur has an exact answer that fits in one line.

A machine that writes digits in base φ #

With $\beta = \varphi \approx 1.618$ the digits are 0 and 1, like binary. A point in the left part of the interval, below $1/\varphi$, is multiplied into $[0, 1)$ and writes a 0; a point in the right part is multiplied past 1 and writes a 1, and the fractional part left over is at most $\varphi - 1 = 1/\varphi$ — which is back in the left part. So a 1 is always followed by a 0. In base $\varphi$, two consecutive 1s never occur in a greedy expansion.

The reason is the identity $\varphi^2 = \varphi + 1$, rewritten as $1/\varphi + 1/\varphi^2 = 1$. In base $\varphi$ that says $(0.11)_\varphi = 1$: a pair of 1s is exactly the next power up. The greedy algorithm, which always takes the largest digit it can, would have written the 1 at the earlier place instead, so a pair of 1s is simply never produced. The picture shows the same fact geometrically: the second piece of the graph stops short of the top, and everything it lands on is in the first piece’s domain.

That short second piece is the whole difference from binary. In base 2 the map has two full pieces, each carrying its half of the interval across the whole of it, so after any digit any other may follow and every string of 0s and 1s is some number’s expansion. In base $\varphi$ the second piece covers only part of the interval, and the part it misses is exactly where a second 1 would have come from. Every constraint on digits in every base comes from a piece that falls short in this way.

One string decides everything #

The golden case has one forbidden word, $11$. Other bases forbid other things, and a single string says what.

Write the number 1 itself in base $\beta$ by the same greedy rule — first digit $\lfloor \beta \rfloor$, then follow the fractional part.

The criterion is due to William Parry, in 1960. Take the expansion of 1 and, if it stops, make it periodic by lowering its last digit by one and repeating the block for ever — in base $\varphi$, $.11$ becomes $.101010\dots$. Call this the quasi-greedy expansion of 1. Then:

A digit string is a greedy expansion in base $\beta$ exactly when every one of its tails is smaller, in dictionary order, than the quasi-greedy expansion of 1.

In base $\varphi$ the quasi-greedy expansion is $1010\dots$, and a tail beginning $11$ is larger than it — the second digit already exceeds — while every tail that avoids $11$ is smaller. So the criterion reproduces the one rule. For the tribonacci constant, where $1 = (.111)_\beta$, the quasi-greedy expansion is $110110\dots$, and the forbidden pattern is three 1s in a row. For the plastic number, $1 = (.10001)_\beta$, and what is forbidden is any 1 followed too soon by another: fewer than four 0s between them.

The three rules look like three different kinds of constraint — a pair forbidden, a triple forbidden, a spacing enforced — and they are one rule applied to three strings. That is typical of how symbolic dynamics simplifies: a family of systems that look unrelated turns out to be parametrised by a single object, here the digits of 1, and every property of a member can be read from its parameter.

The criterion is dictionary order and nothing else. There is no arithmetic in it beyond knowing one string, and it says precisely which infinite sequences of digits arise from numbers.

Why should dictionary order be the right test? Because the map preserves it. If one number is smaller than another and both lie on the same piece of the graph, their images keep the same order, since the piece is a straight line of positive slope; and the digit written first is larger for the larger number whenever they are on different pieces. So larger numbers have lexicographically larger digit strings, and a string is too large to be an expansion exactly when it is at least as large as the string of something that is not below 1. Every tail of an expansion is itself an expansion — of the point the orbit has reached — so every tail has to pass the same test. Parry’s theorem says that passing it is also enough.

When the expansion of 1 stops, the test can be run by a machine with finitely many states. The state records how much of the expansion of 1 the recent digits have copied so far; a digit smaller than the next one in the expansion resets the machine, a digit equal to it advances, and a digit that would complete the whole expansion is refused. In base $\varphi$ the machine has two states, and its only refusal is a second 1.

The rule checked against the machine #

A criterion about all orbits can be tested against a large sample of them.

The figure’s check runs in both directions. Every string the map actually writes, starting from 400,000 points spread across the interval, passes Parry’s test. And every string that passes the test is written by some starting point in the sample. Up to length nine, in all three bases, the two sets are identical.

In base $\varphi$ the counts are the Fibonacci numbers, for the reason the returns matrix gave in another setting: a string of length $n$ with no two adjacent 1s either ends in 0, after any allowed string of length $n - 1$, or ends in 01, after any allowed string of length $n - 2$. In every base the counts grow like $\beta^n$, so the topological entropy of the system — the growth rate of the number of distinguishable strings, the quantity the folds of the logistic map measured — is exactly $\log \beta$. The base is the entropy. That is the same statement as the slope of the map, and it had to be: a map of constant slope $\beta$ stretches everything by $\beta$ at each step, and the number of distinguishable pieces grows at exactly that rate.

Finite type, and the bases where it fails #

The expansions of 1 in the six bases split into two kinds, and the split is the most important thing in the table.

When the expansion of 1 stops — golden ratio, plastic number, tribonacci — the forbidden patterns are finitely many, each at most as long as the expansion. The allowed strings are then exactly those avoiding a finite list of words, which makes the system a shift of finite type: the same kind of system as the returns matrix, described completely by a finite graph. In base $\varphi$ the graph has two nodes, “last digit 0” and “last digit 1”, and the arrow from 1 to itself is missing.

The plastic number’s graph is a chain: a 1 sends the machine off down a corridor of four states, each passable only by a 0, and only at the end of the corridor may another 1 be written. The growth rate of its walks is the plastic number itself, about $1.3247$, and that number has a small distinction: it is the smallest Pisot number there is. So this is, in a precise sense, the slowest-growing system of this kind that is built on a Pisot base — the one with the most constrained digits.

When the expansion of 1 never ends — $3/2$, $1.8$, $5/2$ — no finite list will do. Parry’s criterion still describes the allowed strings exactly, but the description compares tails against an infinite string, and forbidding longer and longer patterns is needed at every length. The system is a shift, it has entropy $\log \beta$, and it cannot be drawn as any finite graph.

So a question about a dynamical system — is it of finite type? — has become a question about one number’s digits: does 1 have a finite expansion in base $\beta$? That depends on the arithmetic of $\beta$. For integer bases it always does: $1 = .(\beta - 1)(\beta - 1)\dots$ in quasi-greedy form, and the system is the full shift. For $\beta = 3/2$ it cannot. A finite expansion $1 = \sum_{i \le n} d_i (2/3)^i$, multiplied through by $3^n$, leaves every term divisible by 3 except the last, $d_n 2^n$, and the only digits available are 0 and 1 — so the last digit would have to be a multiple of 3 and nonzero at once. For special algebraic numbers — the golden ratio and its relatives — it does.

Which bases are tidy #

The bases in the table where 1 has a finite expansion are all roots of polynomials with integer coefficients, and more: each is a Pisot number, an algebraic integer greater than 1 whose other conjugates all lie inside the unit circle. The golden ratio’s conjugate is $-1/\varphi \approx -0.618$; the plastic number, the smallest Pisot number of all, has two complex conjugates of modulus about $0.87$; the tribonacci constant’s conjugates have modulus about $0.74$.

Klaus Schmidt and Anne Bertrand proved around 1980 that for a Pisot base, the expansion of 1 is always eventually periodic — the system is then sofic, described by a finite graph with labelled arrows even if not by a finite list of forbidden words. For the expansion to stop outright is rarer still, and which Pisot numbers have that property is characterised only in special cases. The same Pisot numbers appeared in the coin tosses whose sums collide: there the golden ratio’s conjugate being small is exactly what made two sign patterns land at almost the same point. Here the same smallness makes the digits of 1 settle into a pattern. Both are consequences of $\beta^n$ being very close to a whole number for large $n$ — the defining property of a Pisot number.

Base φ as a way of writing whole numbers #

There is a surprising footnote. In 1957, the same year as Rényi’s paper, a twelve-year-old named George Bergman published a numeral system in which whole numbers are written in base $\varphi$ with digits 0 and 1 and no two adjacent 1s. Every positive integer has such a representation, and it is finite — it uses finitely many positive and negative powers of $\varphi$. For example $2 = \varphi + \varphi^{-2}$, written $10.01$, and $3 = \varphi^2 + \varphi^{-2}$, written $100.01$.

That every whole number has a finite base-$\varphi$ expansion is not obvious — the powers of an irrational number have no reason to add up to integers — and it follows from the same identity, $\varphi^n + \varphi^{-n}$ being a whole number when $n$ is even, that makes the golden ratio a Pisot number. Bergman’s system is the arithmetic side of the dynamics above: the dynamics says which infinite strings are allowed, and the arithmetic says that the integers sit among them with only finitely many nonzero digits.

Arithmetic in base $\varphi$ is possible by hand and a little strange. Adding $1 + 1$ gives a 2 in the units place, which is not an allowed digit; the identity $2 = \varphi + \varphi^{-2}$ turns it into $10.01$. Carrying therefore moves digits both left and right, and a sum may need several rounds of the rule $011 \to 100$ before it settles into a string with no adjacent 1s — the base-$\varphi$ version of carrying, and the same rewriting the greedy algorithm performs automatically. The Fibonacci numbers appear on both sides — as the count of allowed strings, and, through Zeckendorf’s theorem that every integer is a sum of non-adjacent Fibonacci numbers, as the integer version of the same no-two-1s rule.

What the figures only sample #

The agreement is checked to length nine, not proved. Parry’s criterion is a theorem for strings of every length; the figure confirms it on the lengths where 400,000 sample points are fine enough to land in every allowed cylinder of the interval. Beyond that, some cylinders are narrower than the spacing between samples and would be missed, so the check stops.

Digits of 1 are computed in floating point. Whether the expansion of 1 stops is decided in the figure by the remainder falling below $10^{-10}$, and the golden and tribonacci cases are additionally checked to give exactly $.11$ and $.111$. For the bases whose expansions never end, the figure shows fourteen digits and claims nothing about the rest beyond what the arithmetic argument in the text proves for $3/2$.

The orbit is not the number. The cobweb follows 0.3 for eight steps and recovers it to within $\varphi^{-8}$, about 0.02; the remaining digits would make up the difference. An infinite expansion is a limit, and every figure shows a finite piece of one.

The graphs are drawn only for finite expansions. The base-1.8 system has no finite graph, and no figure pretends otherwise. What it has is an infinite graph — one state for every length of prefix of the expansion of 1 — and its walks count its allowed strings in the same way; the figures stop where the graph stops being finite.

Still open: which algebraic bases are tidy #

For Pisot bases the expansion of 1 is eventually periodic; for Salem numbers — algebraic integers with conjugates on and inside the unit circle — it is conjectured to be eventually periodic too, and this has been proved only for Salem numbers of degree 4 and some of degree 6. For most algebraic numbers that are neither, nothing is known about whether the expansion of 1 ever repeats. And for transcendental bases, such as $\beta = e$ or $\beta = \pi$, there is no known example of any interesting structure in the expansion of 1 at all; the expansion of 1 in base $e$ is expected to look random, and nobody can prove anything about it.

There is also an open question closer to the figures. Which bases $\beta$ give an expansion of 1 that stops — a finite-type system — is known to include every root of a polynomial of the form $x^m - x^{m-1} - \cdots - x - 1$, the golden ratio and tribonacci constant among them, and several other families; a complete description of these “simple Parry numbers” in terms of their minimal polynomials is not known.

The measure-theoretic side is tidier. Parry found, for every base, the probability distribution on the interval that the map preserves — the long-run frequency with which orbits visit each part — and it is determined by the same expansion of 1. That distribution is the next question, and it turns the digits of 1 from a list of rules into a staircase.

One string as the whole rulebook #

The machine that writes base-$\beta$ digits is as simple as a machine can be — multiply, take the whole part, repeat — and yet the set of strings it can write is intricate: finitely described for some bases and not for others, with the dividing line running through the arithmetic of $\beta$. What makes it tractable is Parry’s discovery that the whole rulebook is one string. To know every digit sequence that base $\beta$ allows, it is enough to write down the number 1. Everything else — the forbidden patterns, the graph when there is one, the count of strings of each length, the entropy — follows from those digits by rules that a machine can apply. The expansion of 1 is to base $\beta$ what the list of forbidden words was to the systems drawn by a matrix: the complete specification, compressed into the one orbit that starts at the edge of the interval. Where the matrix listed its rules, the base-$\beta$ system grows them from a single seed, and whether the seed produces finitely many rules or infinitely many is a question about the number $\beta$ that no amount of staring at the map would answer.