The word a straight line spells

A ball set rolling on a square table without friction bounces for ever, and unfolding the table — reflecting the square instead of the ball at each wall — turns its path into a single straight line across a grid of squares. Where the line crosses a vertical grid line, the ball hits a side wall; where it crosses a horizontal one, an end wall. Write V for the first and H for the second, and the ball’s infinite life becomes an infinite word.

The unfolding essay used the slope of that line to decide whether the path closes: a rational slope gives a closed path, an irrational one a path that never repeats and passes arbitrarily close to every point. The word says much more than that. For an irrational slope it is one of the most orderly words that are not periodic — it has exactly $n + 1$ different blocks of every length $n$, which is the fewest any non-repeating word can have. Every stretch of it has almost exactly the right number of H’s. And its blocks occur with at most three different frequencies, for the same reason that a circle turned by an irrational angle leaves at most three gap lengths. These words are called Sturmian, and Marston Morse and Gustav Hedlund, who named them in 1940, proved that the billiard in a square produces every one of them.

A line across a grid #

Take the line $y = \alpha x + \beta$ with $\alpha = (\sqrt5 - 1)/2 = 0.6180\ldots$, the reciprocal of the golden ratio, and follow it to the right across a grid of unit squares, recording each crossing.

The word begins $\text{VHVHVVHVHVVHV}\ldots$. Two facts about it are visible at once. The V’s come roughly one per unit of horizontal distance and the H’s roughly $0.618$ per unit, since the line rises that much for each unit it advances, so in a long stretch the letters occur in the ratio $1 : 0.618$ and the share of H’s is $0.618/1.618 = 0.382$. And the H’s never come together: between any two H’s there is at least one V, because the slope is less than one and the line cannot cross two horizontal lines without crossing a vertical one in between.

Folding the grid back into one square, on the right, gives the billiard path, and the word is the order in which the ball meets the walls. Every question about the ball’s walls is a question about the word, and every question about the word is a question about a straight line, which is the reason the word can be understood at all.

The fewest blocks a non-repeating word can have #

Look at every block of $n$ consecutive letters in the word and count how many different blocks occur. That count, as a function of $n$, is called the word’s complexity, and it measures how much freedom the word has.

For both irrational slopes the count is exactly $n + 1$ at every length checked: two blocks of length one ($\text{V}$, $\text{H}$), three of length two ($\text{VH}$, $\text{HV}$, $\text{VV}$), four of length three, and so on. A word of coin tosses, at the other extreme, contains every one of the $2^n$ blocks. And the rational slope $2/5$ gives a word that repeats every seven letters — five V’s and two H’s per period — so its count climbs to seven and stays there.

The $n + 1$ is not a coincidence of these slopes, and it is not merely small. Morse and Hedlund proved in 1938 that if a word has at most $n$ different blocks of some length $n$, it is eventually periodic. The argument is a pigeonhole: if the count ever fails to grow from one length to the next, then some block has only one possible continuation, and following continuations round must eventually repeat. So a word that never repeats has at least $n + 1$ blocks of every length, and the cutting words of irrational slopes have exactly that many. They are the least complex words that are not periodic, and a later theorem of Ethan Coven and Hedlund showed that every non-periodic word with exactly $n + 1$ blocks of each length is, in essence, the cutting sequence of a line.

Why exactly $n + 1$ has a geometric answer, and it leads straight to the three-gap theorem.

Blocks are arcs of a circle #

Record, at each V, how high above the last horizontal grid line the path is — a number between $0$ and $1$. From one V to the next that height goes up by $\alpha$, and wraps round when it passes $1$, at which moment an H is crossed. So the heights at successive V’s are a point turning round a circle of circumference one by a fixed step, the rotation the three-gap essay studied, and the letters are read off from where the point lands.

A block of $n$ letters is then determined by the starting position on the circle, and two starting positions give the same block exactly when no letter-changing boundary separates them over the next $n$ steps. Those boundaries are $n$ points, spaced by the rotation, and they cut the circle into $n + 1$ arcs. Each arc is one block, and the block’s frequency in the word is the arc’s length — because a rotation by an irrational angle visits every part of the circle in proportion to its length.

The figure measures both sides separately — the block frequencies from the word, the arcs from the circle — and they agree. And the arcs, by the three-gap theorem, take at most three lengths, however many points there are. So the blocks of any length occur with at most three different frequencies, a statement about a word that would be hard to guess and is immediate from the circle. For six-letter blocks of the golden word the frequencies are $0.236$, $0.146$ and $0.090$, and they are consecutive powers of the golden ratio’s reciprocal, as the gaps in the three-gap essay were.

Every stretch holds its share #

The complexity counts how many blocks there are. A second property says how evenly the letters are spread within them.

Every block of $n$ letters holds either $\lfloor nf \rfloor$ or $\lceil nf \rceil$ H’s, where $f = 0.382$ is the share of H’s in the whole word. No stretch has even one H more or fewer than the two nearest whole numbers to its fair share. The word is called balanced, and the reason is again geometric: the number of H’s in a block is the number of horizontal lines the path crosses over a fixed horizontal distance, and a straight line crosses either $\lfloor \text{rise} \rfloor$ or $\lceil \text{rise} \rceil$ of them depending on where it starts. The strip under a straight line cannot hold two more or two fewer lattice rows than another strip of the same width.

Morse and Hedlund’s theorem closes the circle: the balanced words that never repeat are exactly the cutting words of lines with irrational slope. Balance and minimal complexity turn out to be two descriptions of the same words, and both are the straightness of a line, written in letters.

Reading the slope back off the word #

The word is not only produced by the line; it records the line completely. The share of H’s is $\alpha/(1+\alpha)$, so the slope can be read from a long enough stretch by counting. More strikingly, it can be read exactly, digit by digit, without counting anything, by an operation on the word itself.

Because the slope is less than one, the H’s never touch, and between consecutive H’s the V’s come in runs of only two possible lengths, $\lfloor 1/\alpha \rfloor$ and $\lfloor 1/\alpha \rfloor + 1$. For the golden slope, $1/\alpha = 1.618$, so the runs are single V’s and pairs, which is what $\text{VHVHVVHVHVVHV}$ shows. The first digit of the slope’s continued fraction is that run length. Now replace every short run and its H by one letter and every long run and its H by another: the result is again a balanced, non-repeating word — the cutting word of a new line, whose slope is the remainder of the continued fraction after the first digit. Repeating the collapse reads off the continued fraction one digit at a time.

That is Euclid’s algorithm run on the word instead of on the numbers. Each collapse is one subtraction step: it removes the whole number of V’s that fit between H’s and keeps the fractional remainder as a new word. For the golden slope every run is one or two and every collapse returns the same word again — the continued fraction is all ones, and the word is its own collapse, which is why it can be grown by a single substitution. For a slope like $\sqrt 2 - 1$, whose continued fraction is all twos, the collapse is again the same at every stage, with a different substitution. Substitutions only ever produce words whose slopes have eventually repeating continued fractions — the quadratic irrationals — and David Crisp, William Moran, Andrew Pollington and Peter Shiue determined in 1993 exactly which of those slopes give a word that a substitution fixes.

A rational slope, and a word that repeats #

A line of rational slope $p/q$ in lowest terms crosses $q$ vertical and $p$ horizontal lines before it returns to the same position relative to the grid, and then repeats. Its word is periodic with period $p + q$ — the slope-$2/5$ word in the complexity figure repeats every seven letters — and one period of it is called a Christoffel word, after the nineteenth-century geometer Elwin Christoffel who studied them in connection with continued fractions.

The connection to continued fractions is not a detail. A line of irrational slope is approximated by lines of rational slope, and the best approximations are the convergents of the slope’s continued fraction. The cutting word of the irrational line through a corner of the grid begins with the Christoffel words of its convergents, each longer one starting with the shorter: the golden slope’s convergents are ratios of Fibonacci numbers, $1/1, 1/2, 2/3, 3/5, 5/8, \ldots$, and its word begins with each of their periodic words in turn. Euclid’s algorithm drawn as a tiling generates the convergents, and so it generates the word — which is one way of saying that the word of a straight line encodes the slope’s continued fraction in its letters.

The golden word grows by itself #

For the golden slope the continued fraction is all ones, and the word has an especially direct description: it is generated by a substitution.

Starting from $\text{V}$ and replacing every $\text{V}$ by $\text{VH}$ and every $\text{H}$ by $\text{V}$ gives $\text{V}$, $\text{VH}$, $\text{VHV}$, $\text{VHVVH}$, $\text{VHVVHVHV}$, each beginning with the last and each of Fibonacci length, since a word’s length is the previous length plus the one before. The limit is the Fibonacci word, and it is exactly the cutting word of a line of slope $1/\varphi$ through a corner of the grid. The substitution is self-similarity made mechanical: replacing each letter by its image is the same as looking at the line through a coarser grid, and for the golden slope the coarser grid sees the same line again, just as a golden rectangle minus a square is a golden rectangle.

The same word turns up in places that have nothing to do with billiards. The positions of the letters in it are Beatty sequences, $\lfloor n\varphi \rfloor$ and $\lfloor n\varphi^2 \rfloor$, which split the whole numbers into two complementary sets — and those are exactly the losing positions of Wythoff’s game, the game whose first long run decides it. A physicist knows it as the Fibonacci chain, a one-dimensional quasicrystal: two kinds of atom in a sequence that is perfectly ordered and never periodic, whose diffraction pattern has sharp spots at positions indexed by the golden ratio.

A measure of chaos that the word makes zero #

Writing a trajectory as a word is the basic move of symbolic dynamics, and the complexity of the word is a direct measure of how chaotic the trajectory is. For the doubling map on a circle, the natural code is the binary expansion of the starting point, and every block of $n$ binary digits occurs — the complexity is $2^n$, the most possible. For the ball on a square table it is $n + 1$.

The rate at which the complexity grows is called the topological entropy: the limit of $\log(\text{number of blocks of length } n)/n$. The doubling map has entropy $\log 2$, the signature of chaos — the number of distinguishable futures doubles with every step, and two nearby starting points separate at the same exponential rate. The square billiard has entropy $\lim \log(n + 1)/n = 0$. Its future is determined by a slope and a starting height, two numbers, and knowing more letters only ever pins those two numbers down more finely; the future never branches. A chaotic system’s word is as rich as a word can be, and the square table’s is as poor as a word can be without repeating. Between those extremes, a matrix of allowed transitions counts the blocks, and its largest eigenvalue is the growth rate.

What the words cannot show #

They cannot show infinity. Every count here is made on a finite stretch — 20,000 letters for the complexity, 5,000 for the balance, 200,000 for the frequencies. That the complexity is exactly $n + 1$ for every $n$, and that balance holds in every block however long, are theorems of Morse and Hedlund; the figures check them where they can and cannot check the rest.

They cannot show why the ball’s word needs a square. In a rational polygon other than a square the unfolding still works, but the grid of copies is replaced by a surface of higher genus, and the words become codings of more complicated maps, with complexity growing faster than $n + 1$. The square’s words are Sturmian because its unfolding is a flat torus, and the figures do not show any other case.

And they cannot show the three-gap connection at every length. The frequencies are matched to the arcs for one block length in the figure; the general statement, that block frequencies are arc lengths and so take at most three values, is argued from the rotation and not measured for every $n$.

Still open: the word of a line in a cube #

A billiard ball in a cube hits three kinds of wall, and its wall sequence is a word in three letters. For irrational directions the number of different blocks of length $n$ is $n^2 + n + 1$ — conjectured by Pierre Arnoux, Christian Mauduit, Iekata Shiokawa and Jun-ichi Tamura and proved by Yuri Baryshnikov in 1995. What is missing is the rest of the square’s story. In the square, balance and minimal complexity together characterise exactly which words come from lines, and a word can be recognised as a billiard word by inspecting its blocks. In the cube no comparably clean description of which three-letter words arise is known, so there is no test, short of finding the direction, that says whether a given word is the wall sequence of some straight line.

A line, written as a word #

The order in which a ball on a square table meets the side and end walls is the cutting word of a straight line across a unit grid, and for an irrational slope it is a Sturmian word. It has exactly $n + 1$ different blocks of each length $n$ — the fewest possible for a word that never repeats, by Morse and Hedlund’s pigeonhole — and every stretch holds its share of H’s to within one.

Both properties come from the straight line, and a third comes from the circle it secretly traces: the word codes a rotation, its blocks are the arcs cut by $n$ points, and by the three-gap theorem the blocks occur with at most three different frequencies. A rational slope gives a periodic Christoffel word; the golden slope gives the Fibonacci word, grown by $\text{V} \to \text{VH}$, $\text{H} \to \text{V}$, the same word that lists the losing positions of Wythoff’s game.

When a trajectory is too complicated to follow, write down its symbols — the word can be simpler than the path, and here it is as simple as a word can be without repeating.