Three gaps, and never four

The Fibonacci chain has two tile lengths. Every account of it says so, and the reason usually given is that it comes from a projection of a strip of the square lattice, and a strip catches lattice points in two kinds of run. That is true and it is not an explanation: it says where the two lengths come from without saying why there are not five.

The reason there are two is a theorem about a circle, and it has nothing to do with lattices, strips or tiles.

Take an angle α and mark the points {α}, {2α}, … {nα} on a circle of circumference one, fractional parts, so the circle is the unit interval with its ends glued. Include the point at zero. Whatever α is and however large n is, the gaps between neighbouring points take at most three distinct lengths, and when there are exactly three the largest is the sum of the other two.

The claim, and what it is not #

It would be easy to read this as a statement about nice angles. It is not.

The theorem holds for every α — rational, irrational, close to a simple fraction or nowhere near one — and for every n. There is no exceptional case, no asymptotic qualifier, no “for sufficiently large”. A set of points that looks thoroughly disorderly has a gap structure with three values in it, always.

The golden ratio is used throughout this essay because it is the case that connects to the chain, and it is worth saying that nothing in the argument needs it. Rotate by √2 − 1, whose continued fraction is all twos, and the answer is three lengths with the largest the sum of the other two. Rotate by π − 3, whose continued fraction begins 7, 15, 1, 292 and has no pattern in it at all, and the answer is the same. What the choice of α changes is which counts of points give two lengths rather than three — that is the continued fraction, and it is the subject of a later section — and never how many lengths there can be.

That sentence is the proof in miniature. Every new point lands in the largest surviving gap and cuts it into a piece of the second length and a piece of the third; the three-way bookkeeping is preserved. Making that argument airtight takes a page, and it has been made many times — the theorem was conjectured by Steinhaus and proved independently by Sós, Świerczkowski, Surányi and others around 1957.

The proof, in the amount of detail it deserves #

The argument is short enough to give, and giving it makes clear why the answer could not have been any other number.

Suppose the first n points are down and the gaps take the lengths already claimed. The point at (n+1)α lands somewhere, and the question is what it does to the gap it lands in.

It lands in a gap of the largest length. Rotating the whole configuration by α carries each point to the next, so the gap containing the new point is the image of the gap that was cut when the previous new point arrived — and the sequence of gaps cut is the sequence of largest ones.

It cuts that gap into two pieces whose lengths are already present. One of the two is the length of the gap immediately after the first point, and the other is the difference. Both are lengths that occurred before the cut, so the set of lengths after the cut is contained in the set before it plus, at most, one new value.

And the largest is always the sum of the other two, because that is what the cut says: the piece removed and the piece left add to the gap they came from.

Three lengths is therefore the fixed point of that bookkeeping. Two is what happens when the cut is exact — when the piece removed equals the piece left, so no new value appears — and that is precisely the condition on n that makes it a convergent denominator.

Run rather than argued #

This collection’s habit is not to quote a theorem but to feed it inputs it would fail on if it were false, so the claim is checked here rather than cited.

Every number in that computation is an integer. Taking α rational as p/q, the points are the residues of kp modulo q, so a gap is a difference of integers and a + b = c is an identity between whole numbers rather than a comparison against a tolerance. There is nothing to round and nothing to decide.

That is not a loss of generality in the usual sense. It is a restriction that has to be declared, in the same way a search bound is declared: what has been checked is the rational case, exhaustively, and the irrational case is reached the only way a computation may reach it — through convergents, with the report being that the combinatorics stop changing.

And “stop changing” is checked rather than promised. Every circle and interval in this essay is drawn at the convergent 610/987, and each of them is drawn a second time at the convergent before, 377/610, with the two results compared. What is compared is not the lengths — those are fractions over different denominators and cannot agree — but the sequence: which gap is the long one, which the short, in order round the circle. The two agree letter for letter at every count of points drawn here, and the figure does not appear if they do not. So the picture is a picture of the golden ratio rather than of one particular fraction near it, and the claim that the rational case reaches the irrational one has an instrument attached to it instead of an assurance.

When there are only two #

Three is the general case. Two happens sometimes, and when is the whole connection to the chain.

So the three-gap structure is the continued fraction of α, read off a circle. The lengths themselves are the quantities ‖qα‖ — the distance from qα to the nearest integer — for the convergent denominators q, which is the standard measure of how well α is approximated by fractions — the quantity that decides how badly a lattice can match a substrate and, for the same reason, which irrational is worst. Rotation of a circle, the geometry of gaps, and the arithmetic of best rational approximation are one subject seen three ways.

The golden ratio is the extreme case for a reason that now needs no separate argument. Its continued fraction is all ones, so its convergent denominators are the Fibonacci numbers and they grow as slowly as denominators can. Slow growth of denominators is slow convergence of approximations, which is why φ is the worst-approximable number — and it is why the two-gap counts for φ are the Fibonacci numbers minus one.

The chain, recovered #

Now the tiles.

Two independent constructions, required to agree. The gap computation knows nothing about substitutions: it sorts residues and subtracts. The substitution knows nothing about circles: it rewrites letters. That every window of the first occurs in the second is a check, not a restatement, and it is the check that says this really is the Fibonacci word and not merely something with two letters in it.

The chain’s two tile lengths are therefore not a fact about projection. They are a fact about the rotation of a circle by an irrational angle, and the projection construction inherits them because a strip through a lattice is such a rotation, with the strip’s slope playing α’s part.

The one place a computation can go wrong here #

There is a trap in this that changed a number during the writing, and it is worth stating because it is the shape of a whole class of numerical mistakes.

At exactly a convergent denominator there are three gaps, not two. The newest point has just landed in the longest gap and cut it in two, so alongside the two Fibonacci-ratio lengths there is a third, short one. Take the largest and the smallest of those three and their ratio is φ² rather than φ — a plausible-looking 2.618, in a figure that draws perfectly well and a caption that reads perfectly well.

The check that caught it is the one the theorem itself supplies: assert that there are exactly two lengths before using them as the chain’s two tiles. An assertion that would have been redundant if the count had been right is exactly the assertion worth writing.

Two measurements of one chain, and they count different things. The neighbouring result on this site is the complexity function: the number of distinct windows of each length that the chain shows, which for a Sturmian sequence is n + 1 and no fewer. That is a count of patterns along the chain. The three-gap theorem is a count of lengths between its points. They are different measurements of the same object and neither implies the other — a sequence could in principle have few patterns and many lengths, or the reverse — and what makes the Fibonacci chain the extremal object of the subject is that both counts are as small as an aperiodic sequence permits at the same time.

Why three and not two #

A last question the theorem invites: why should the answer be three rather than two or four?

The short answer is that the circle is one-dimensional and a rotation is generated by one element. Each new point cuts one gap, and the piece it cuts off must equal a gap that already exists — because the rotation carrying the new point to its neighbour carries a whole stretch of the configuration with it. Two lengths would require the cutting to be exact, which happens only at the convergent denominators; four would require some gap to be cut in a way the rotation does not repeat, which cannot happen.

In two dimensions there is no such theorem. Points {nα} and {nβ} on a torus leave regions whose areas take many values, and the number grows. The three-gap theorem is a one-dimensional statement in a strong sense, and that is one reason the Fibonacci chain is so much cleaner than its planar relatives.

The planar case is worth stating precisely, because “there is no analogue” can be read as “nobody has found one yet”. A Penrose tiling has two tile shapes and seven vertex environments, and those are counts of configurations rather than of gap lengths; there is no quantity in the plane playing the part of a gap between neighbours, because a set of points in the plane has no neighbours in the sense a set on a circle does. Delaunay cells are the nearest thing, and their areas take many values and go on taking more as the patch grows. The one-dimensionality is not a convenience of the proof; it is the hypothesis.

Where else the same three lengths turn up #

The theorem is not an isolated curiosity, and two of its other appearances are worth naming because both are in this collection already.

A row of atoms in an incommensurately modulated crystal. The displacement of the nth atom depends on {nq} for a modulation wavevector q, so the distinct local environments along the row are governed by the same rotation of the circle. A modulated chain does not have three environments — the displacement is a continuous function — but the environments group into three families in exactly the way the gaps do, and the satellite structure of its diffraction is the arithmetic underneath.

Plant phyllotaxis, which is where most people first meet it. Leaves placed at successive multiples of the golden angle round a stem leave gaps of three sizes, and the reason no two leaves shadow each other is the same reason φ is worst-approximable. That is not a crystallographic claim and nothing here computes it; it is mentioned because it is the same theorem and because it explains why a result about circles has a reputation outside mathematics.

What both share with the chain is a single irrational number generating a one-dimensional sequence. That is the whole hypothesis of the theorem, and everything else about the objects — atoms, leaves, tiles — is decoration.

The renormalisation hiding in the proof #

The proof above is a bookkeeping argument, and underneath it is a structural fact that explains why the chain and the circle turn out to be the same object.

Take the rotation by α and watch it only when the orbit is inside one of the gaps — the first return map. A point in that gap is carried out of it by the rotation, wanders round the circle for a while, and eventually comes back. How long it takes depends on where it started, but only in a very restricted way: it takes one of two numbers of steps, and the map that sends a point to where it lands on its return is again a rotation, of the gap regarded as a circle in its own right, by a new angle.

That is renormalisation, and it is the whole reason the structure repeats at every scale. The new angle is what the continued-fraction algorithm produces from the old one — take the fractional part of the reciprocal, which is the Gauss map — so the sequence of gap structures at n = 1, 2, 3, … is the sequence of rotations the algorithm walks through, each one a scaled copy of the situation before it.

And the two return times are why there are two tile lengths rather than three. A point in the gap returns after either q steps or q' steps, with q and q' the two convergent denominators in play. Recording which of the two happened, for successive points, writes down a sequence in two letters — and that sequence is the chain. The gaps and the tiles are not two constructions that agree; they are the same construction read at two levels, and the substitution rule is what the renormalisation looks like when it is written as a rewriting of letters.

For the golden ratio the Gauss map has a fixed point, since 1/φ has fractional part 1/φ − 1 = 1/φ² and the continued fraction is all ones. That is exactly the statement that the renormalised problem is the same problem, which is why the Fibonacci chain is a fixed point of a substitution and why no other quadratic irrational is quite so clean.

Steinhaus’s question, and the proofs of the late fifties #

The theorem is usually attributed to a conjecture rather than to a proof, which is unusual enough to be worth recording.

Hugo Steinhaus posed it as a question — how many distinct distances are there between adjacent points of {kα}? — and the answer three was conjectured before it was proved. Proofs appeared within about two years of one another around 1957 to 1959, from Vera Sós, Stanisław Świerczkowski and János Surányi, working independently; the result is called the three-distance theorem, the three-gap theorem, or the Steinhaus conjecture depending on which of them a writer read first.

It was then found again, from a different direction and for a different purpose, by Noel Slater, whose interest was in the sequence of times at which a particle crosses a plane — a physics problem about gaps in {nθ} that turns out to be the same question. His 1967 paper on gaps and steps is the one most often cited in the physical literature, and it is a fair guess that neither community knew about the other for some years.

The rediscoveries are the interesting part rather than an accident of bibliography. A statement about an orbit of a rotation is a statement about a one-dimensional quasiperiodic sequence, and one-dimensional quasiperiodic sequences arrive in crystallography as chains, in dynamics as coding sequences, in number theory as continued fractions and in combinatorics on words as Sturmian words. All four fields have the theorem. Only one of them calls the gaps tiles.

What that means for this collection is a rule about attribution rather than about mathematics. A result met in one subject’s vocabulary is worth searching for in another’s before it is called new, and the search is cheap: the objects here are so small that any statement about them can be written as a statement about integers, and integers are the same everywhere.

What is owned, and what is quoted #

The theorem is quoted: Steinhaus conjectured it, and the proofs are from 1957 and later. What is computed here is the exhaustive rational check, the identification of the two-gap counts with the convergent denominators, and the letter-by-letter agreement between the gap word and the substitution word.

The irrational statement is not computed and is not claimed to be. What is shown is a sequence of rational angles whose combinatorics do not change, which is evidence about the convergents rather than a proof about the limit — and the difference between those two things is the difference between this collection and a textbook that would simply assert the limit.

Why the theorem is about rotations and not about points #

The statement is usually given as a fact about the points {kα}, and it is worth restating as a fact about the map that produces them, because the second version explains the first.

The circle rotated by α is a group action, and the points are one orbit. The theorem is therefore a statement about how an orbit of a rotation sits in the circle, and the reason the gap structure is so constrained is that the rotation carries the whole configuration onto a shifted copy of itself. A gap and the gap α further round are related by that shift, so the multiset of gaps is nearly invariant under it — nearly, because the two ends of the orbit are not carried into it.

That “nearly” is where the three comes from. An exactly invariant configuration would have one gap length; the failure at the two ends admits two more, and no mechanism admits a fourth.

The same argument in a group with two generators gives nothing, which is why the plane has no analogue: two rotations of a torus produce an orbit whose gaps are regions, and there is no single shift relating them all. The theorem is a fact about cyclic groups acting on a circle, and everything else about it is decoration.

Where the ladder goes next #

The natural next question is what a pair of incommensurate periods does when both belong to the same object rather than to one chain and its approximants. Two lattices in one crystal share no common multiple, each modulates the other, and the diffraction needs an index from each — the same arithmetic of two scales, in a crystal that exists and has been measured.

The other direction is back to complexity: the three-gap theorem counts lengths, the complexity function counts patterns, and a chain that is Sturmian is exactly one for which both counts are as small as an aperiodic sequence permits.