The word a line spells in a cube

The word a straight line spells followed a ball across a square table and wrote down the walls it hit, V for a side and H for an end. Unfolding the table turned the ball into a straight line across a grid of squares, as a bounce is a fold of the table had shown, and the word into the order in which the line crosses vertical and horizontal grid lines. The word turned out to be as simple as a word can be without repeating: exactly $n + 1$ different blocks of length $n$, for every $n$, whenever the slope is irrational.

A cube is the next table. A ball in a cube bounces off three pairs of walls — the two facing across, the two facing up, the two facing into the room — and the order spells a word in three letters, X, Y and Z. Unfolded, the cube becomes a stack of unit cubes filling space, the ball becomes a straight line through it, and the word records which family of planes the line crosses next: a plane $x = k$, $y = k$ or $z = k$.

The question is the same as for the square. How many different blocks of $n$ letters does the word contain? The answer was conjectured by Pierre Arnoux, Christian Mauduit, Iekata Shiokawa and Jun-ichi Tamura and proved by Yuri Baryshnikov in 1995: for a direction in general position, $n^2 + n + 1$. This essay computes that number, shows where it comes from, and finds a direction that the phrase “in general position” has to exclude although nothing about its three components looks special.

Three speeds, and letters in proportion #

The direction in the figure is $(1, \sqrt2, \sqrt3)$: the ball moves one unit across for every $\sqrt 2$ up and $\sqrt 3$ into the room. Unfolded, it crosses a plane $x = k$ once per unit of time, a plane $y = k$ every $1/\sqrt 2$ units and a plane $z = k$ every $1/\sqrt 3$. So the letters X, Y and Z occur in the proportions $1 : \sqrt 2 : \sqrt 3$, about 24%, 34% and 42%, and the word starts ZYXZYZXYZZXYZYXZ…

Each letter is placed by a simple rule, and the rule is the whole of the construction: from the current point, compute the time to the next plane in each family, and write down the family that arrives first. The times are computed afresh from whole numbers at every step, so nothing accumulates, and each bounce point in the figure is checked to lie on a wall of the kind its letter names.

A word built this way never repeats when the three speeds are not whole-number multiples of a common one. If they are — direction $(1, 2, 3)$, say — the line returns to its starting point in the unfolded lattice after one unit of time, shifted by whole numbers, and the word repeats with period six. The interesting directions are those with no such return, and among them the cube offers a distinction the square did not: the speeds can be irrational and still satisfy a whole-number relation, such as $(1, \sqrt2, 1 + \sqrt 2)$, where the third is the sum of the other two.

Three, seven, thirteen, twenty-one #

Count the different blocks of each length in the first six hundred thousand letters.

The general direction gives 3, 7, 13, 21, 31, 43, 57, 73, 91: exactly $n^2 + n + 1$, checked at each length. The word is still far from random — a random word in three letters has $3^n$ blocks, 19,683 at length nine against 91 here — but it is quadratically richer than the square’s, where the count grows by one at each length rather than by $2n$.

The other curves place it. The direction $(1, \sqrt 2, 1 + \sqrt 2)$ starts the same way, 3 and 7, and then falls behind, growing only by three at each length: the whole-number relation among its speeds makes the line lie in a family of planes, so its motion is really two-dimensional in disguise, and the count grows linearly like a square’s. The Tribonacci word, built by the substitution X → XY, Y → XZ, Z → X, is the most famous three-letter word that never repeats, and it has $2n + 1$ blocks, fewer than any cube direction in general position. It belongs to the Arnoux–Rauzy words, which generalise the square’s words in a different direction: they keep exactly one block of each length that can be extended in more than one way, as the square’s words do, while the cube’s words keep many.

Blocks are regions of a square, cut by lines #

In the square, recording the height of the line at each vertical crossing turned the word into a rotation of a circle, and the blocks of length $n$ into the $n + 1$ arcs that $n$ points cut the circle into — the arcs that three gaps and no more measured. The cube’s version is one dimension up. Record where the line is, in the other two coordinates, each time it crosses a plane $x = k$: a point in a unit square, wrapped round at its edges into a torus, which moves by the fixed step $(\sqrt 2, \sqrt 3)$ from one crossing to the next, as in a table folded into a surface.

A block of $n$ letters is decided by where on that square the line starts, and two starting points give the same block exactly when no boundary between letters separates them over the next $n$ steps. In the square’s case the boundaries were points on a circle. Here they are segments of lines on a square, one family for each letter that could change, and $n$ steps of boundaries cut the square into regions. Each region is one block, and each block’s frequency in the word is its region’s area.

Counting regions cut by lines is a familiar problem: $k$ lines in general position cut a plane into $1 + k + \binom{k}{2}$ pieces, one more for each line and one more for each crossing. Lines grow linearly with $n$, crossings quadratically, and that is where the $n^2$ comes from. The exact count $n^2 + n + 1$ requires that the segments cross as often as they can and that no three of them pass through one point, and that is the part of “general position” that needs a hypothesis.

Thirteen of twenty-seven #

At length three the count is thirteen, and the figure shows which thirteen.

Most of the absences have a reason that can be stated in a sentence. Two X’s in a row would need a whole unit of time with no crossing of a $z$-plane, but $z$-planes are crossed every $1/\sqrt 3$ units, so it never happens; the same goes for two Y’s. Only the fastest letter can repeat, and it cannot repeat three times, since that would need $2/\sqrt 3 \approx 1.15$ units with no $y$-crossing, longer than the $y$-spacing $0.71$. The rest of the absent blocks are excluded by comparisons of the same kind between sums of the three spacings.

The frequencies, printed in each shaded cell, are the areas of the thirteen regions, and unlike the square’s three-gap theorem nothing limits them to a few values. The thirteen regions have seven different areas, from five blocks in a thousand to a hundred and forty-four, and four blocks share the most common value. The cube’s word is regular — the blocks are exactly the regions of a fixed cutting of a square — but the regularity no longer forces the frequencies into a short list.

Erase a letter and the square’s word is left #

The cube’s word contains three square words inside it, and they can be extracted by erasing.

Erasing Z leaves the sequence in which the line crosses $x$-planes and $y$-planes, ignoring $z$ entirely. That is the order in which the line’s shadow on the floor, a straight line of slope $\sqrt 2$, crosses the floor’s grid: a square’s word. The same holds for each of the three letters, so every two-letter shadow of a cube’s word has exactly $n + 1$ blocks of length $n$, which the figure checks to length eight.

That gives a test. A three-letter word that comes from a line in a cube must have all three of its two-letter shadows balanced and minimal, in the sense of the square’s words. The Tribonacci word fails: erase Y and the word that remains has 6 blocks of length four rather than 5, so it is not the shadow of any line, and the Tribonacci word is not a billiard word in any cube, whatever its complexity. Combined with the count $n^2 + n + 1$, the shadow test is a strong filter. Whether it is a complete one — whether every word with the right count and three square shadows comes from a line — is not known.

A direction that is irrational and still special #

The theorem holds for directions in general position, and the natural guess is that general position means no whole-number relation among the three speeds. The direction $(1, \sqrt 2, 1 + \sqrt 2)$ has such a relation and fails badly, so the guess is at least necessary. It is not sufficient.

Take the direction $(\sqrt 2, \sqrt 3, \sqrt 5)$. No whole-number combination of $\sqrt 2$, $\sqrt 3$ and $\sqrt 5$ vanishes, and the same is true of their reciprocals, so by any test of rational independence the direction is as irrational as $(1, \sqrt 2, \sqrt 3)$. Its word agrees with $n^2 + n + 1$ for blocks of length up to five. At length six it has 41 blocks rather than 43: the blocks ZZXYZX and XZYXZZ never appear, in a million letters or in three million, while every other block of six appears thousands of times.

The perturbation in the figure locates the cause. Multiply the third component by $1 + \varepsilon$ and the two missing blocks appear at once, with a frequency that falls towards zero roughly as $\varepsilon^2$. In the language of regions, that is the behaviour of a small piece of the cutting whose sides close up to a single point as $\varepsilon$ goes to nought: three boundary segments meeting at one point, the coincidence the count of regions forbids. It is produced not by a linear relation among the speeds but by something about their geometry that no test of linear independence looks at. Which relation it is has not been identified here. The squares of the components satisfy $2 + 3 = 5$, which is suggestive, but the direction $(\sqrt 2, \sqrt 7, 3)$, whose squares satisfy $2 + 7 = 9$, shows no shortfall up to blocks of length eight, so the sum of squares alone is not the cause.

So “general position” in the cube is a condition about how the boundary segments meet, and it excludes a set of directions with no area but more structure than the rational relations. The square had nothing analogous: its boundaries are points, and points on a circle cannot meet three at a time.

One dimension up, and the next #

The argument that produced the cube’s count does not depend on there being three letters. A line through a $d$-dimensional cube crosses $d$ families of planes, its word has $d$ letters, and the starting points live on a torus of dimension $d - 1$, which the boundaries of $n$ steps cut into pieces. Baryshnikov’s theorem counts the pieces in every dimension at once: for a direction in general position the number of blocks of length $n$ is

$$\sum_{i=0}^{\min(n,\,d-1)} i!\binom{d-1}{i}\binom{n}{i},$$

which is $n + 1$ for the square, $n^2 + n + 1$ for the cube, and $n^3 + 2n + 1$ for a four-dimensional cube.

The four-dimensional count can be checked the same way as the others: a line in the direction $(1, \sqrt2, \sqrt3, \sqrt7)$, its crossings of four families of hyperplanes written as four letters, and the blocks counted. The measured counts are 4, 13, 34, 73, 136 and 229, matching the formula at every length. The terms of the sum can be read in the geometry of the cutting: the term with $i = 0$ is the single starting region, the terms with $i = 1$ count the boundaries added, and each higher term counts the places where $i$ boundaries cross. In the cube those are points where two segments meet; in four dimensions there are also points where three walls of the cutting meet, and those contribute the cubic term.

The formula also makes the meaning of general position exact in every dimension. Each term assumes that boundaries meet as often as they can and never more than the dimension allows. A direction in which too many boundaries pass through one point — the cube’s $(\sqrt2, \sqrt3, \sqrt5)$ is one — loses regions, and the loss need not show at short lengths: in that direction the count agreed with the formula for every block shorter than six, so a direction cannot be certified as general by checking a few lengths.

The entropy is still zero #

A quadratic count is a richer word than the square’s, but not a chaotic one. The rate at which the number of blocks grows exponentially is the topological entropy, $\lim \log p(n)/n$, and for $p(n) = n^2 + n + 1$ the limit is zero, as it was for $n + 1$. The ball in the cube is as predictable as the ball on the square: its future is determined by one direction and one starting point, and more letters only locate them more finely. What the cube adds is a polynomial of higher degree, and the degree measures the dimension of the space the starting points live in — one for the square’s circle, two for the cube’s torus, and $d - 1$ for a line in a $d$-dimensional cube, where Baryshnikov’s formula gives a polynomial of degree $d - 1$.

That makes the billiard words a sequence of increasing complexity that never reaches chaos, set against the doubling map, whose word has every block and whose orbits part exponentially fast. The cube’s word is richer than any one-dimensional rotation can produce and still as far from randomness, in the sense of entropy, as the square’s.

What the counts do not show #

The counts in the figures come from finite words, and a block whose region has very small area may not yet have appeared in a few hundred thousand letters. For the general direction every one of the 91 blocks of length nine appears at least a few times in the sample, so the counts are complete; for the degenerate direction the absence of two blocks at three million letters, alongside thousands of occurrences of every other block, is evidence rather than proof, and the perturbation is what makes the explanation convincing.

The figures also concern single directions and starting points chosen away from edges and corners. A line that passes exactly through an edge of the lattice crosses two planes at once and its word is ambiguous there; such lines form a set of starting points with no area and are excluded.

Still open: which three-letter words come from lines #

In the square, a word comes from a line exactly when it is balanced — any two blocks of equal length differ by at most one in their count of each letter — and the balanced, non-repeating words are exactly those with $n + 1$ blocks of each length. The cube has no such characterisation. The count $n^2 + n + 1$ is necessary for a direction in general position, and three square shadows are necessary for any line, but whether the two together suffice, or what further condition would, is not known, so there is no test that decides from a word alone whether some line in some cube spells it.

The degenerate direction raises a second question. The directions in which the count falls short have no area, since the formula holds for almost every direction, but they are not described: which algebraic relations among the components, beyond the linear ones, make three boundaries concurrent, and whether the set of such directions can be listed in any useful form, is open in the cube and more so in higher dimensions, where the regions are cut by planes rather than lines and the coincidences have more ways to occur.