## Three gaps, part 4

Okay, we’ve shown that when you generate a scale using an interval X, that scale has no more than three different gap sizes. Now let’s learn about the relationship between those sizes.

Let’s suppose we have three different gap sizes. For instance, the 8 note scale:Here the first note, the note we started with, is F, and the last note added is F♯. That means the Type I rigid gaps are FF♯ and F♯G (the yellow gap on the left, and the purple one immediately to its right, surrounding the last note). AB (the blue gap closest to the center) is a Type II rigid gap, because shifting it by X makes it coincide with EF♯, which isn’t a gap, it’s the two gaps surrounding the first note (EF and FF♯). Clearly that means the size of gap AB is the size of EF (which is the same as the size of rigid gap F♯G) plus the size of FF♯. So in this case the size of the largest gap is the sum of the sizes of the two smaller gaps.

But is that always true? Can you get a Type II gap that isn’t the same size as the sum of the gaps surrounding the first point? Or can you get a scale in which the two gaps surrounding the first point are both the size of one or the other of the Type I gaps?

Let’s try to look at all the possibilities. For the Type I (rigid) gaps:

1. There are no Type I gaps
2. There is only one Type I gap
3. There are two Type I gaps, and they’re the same size
4. There are two Type I gaps, and they’re different sizes

And for the Type II (rigid) gap:

1. There is no Type II gap
2. There is a Type II gap, and it is also a Type I gap
3. There is a Type II gap, and it is not a Type I gap

Type I gaps surround the last note. If the gaps adjacent to the last note aren’t rigid, that means there’s a note X above the last note, which would have to be the first note, and the only way that can happen is if $nX = 0 \mod 1200$. That is, X has to be rational, of the form $1200m/n$ (in lowest terms). Then the n note scale divides the octave into n equal intervals, and we have a 1-gap scale. In that case there aren’t any Type II rigid gaps, either. Every gap coincides with a gap when shifted.

If there is no note X above the last note, then the gap to the left of the last note is rigid and so is the gap to the right, and there are two Type I gaps unless those two gaps are one and the same. In other words, it’s a one-note scale with one (one octave) gap. Which is a degenerate sort of equal division of the octave, so in fact there aren’t any rigid gaps. In other words, if it’s not an equal division of the octave (or a one-note scale), then there must be two distinct Type I gaps. They can be the same size, or not.

Now suppose there is no Type II gap. No gap contains the first note in its shifted interior. The only way that can happen is if there is a note X to the left of the first note, and that would have to be the last note. Again, this means it’s an equal division of the octave, and there are no Type I gaps either.

So suppose there is a Type II gap, but it is also a Type I gap. That is, one of its end notes is the last note. Then when shifted, that end will not coincide with a note. If the two Type I gaps are different sizes, then all we can say is we have a 2-gap scale, and there is no particular relationship between the two sizes.

Example: the 7 note scale:

Here gap AB (the blue gap closest to the center) is a Type II rigid gap: if you shift it, it goes from E to where F♯ would be if there were an F♯, and it contains F. It’s also one of the Type I rigid gaps, since B is the last note; the other is BC. So it’s a 2-gap scale.

If the Type II gap is also Type I, and the two Type I gaps are the same size, well… then obviously we have a 1-gap scale, which means an equal division of the octave, but that has no rigid gaps at all, so by contradiction that case is impossible.

Finally, suppose there is a Type II gap, and it is not a Type I gap. That means there’s a note X to the right of each of its end notes, so when you shift the gap it’ll coincide with two gaps, the two surrounding the first note. The Type II gap is the sum of the gaps surrounding the first note. One of the two gaps surrounding the first note has its “older” end note (namely the first note) on the right end, the other has the older note on the left end. If you shift the first of these as many times as you can, the “newer” note on the left end reaches the last note first, so this gap matches up with the Type I rigid gap in which the last note is on the left end. But if you shift the second one, the “newer” note on the right end reaches the last note first, so that gap matches up with the Type I rigid gap in which the last note is on the right end. So if the two Type I gaps are different sizes, then so are the two gaps surrounding the first note, and we have a 3-gap scale in which the Type II rigid gap is the same size as the sum of the sizes of the two Type I gaps.

The only way the two gaps surrounding the first note can be the same size is if both Type I gaps are the same size, in which case the Type II gap is exactly twice that size and it’s a 2-gap scale. That would happen, for instance, if instead of ~702 cents, X were 700 cents, and you generated an 8-note scale. It would look like the 8-note scale above, except the gaps surrounding the first note both would be 100 cents in size, and so would the gaps surrounding the last note.

Summing up:

1. If there are no Type I gaps, there are no Type II gaps, and vice versa; we have a 1-gap scale
2. If there is a Type II gap, and it is also a Type I gap, then the two Type I gaps are different sizes, and we have a 2-gap scale, with no particular relationship between the two sizes
3. If there is a Type II gap, and it is not a Type I gap, and the Type I gaps are the same size, we have a 2-gap scale with the large gap twice the small gap
4. If there is a Type II gap, and it is not a Type I gap, and the Type I gaps are not the same size, we have a 3-gap scale with the large gap the sum of the small gaps

So there you go. I’ve framed this discussion in terms of musical scales, putting notes within an octave, at positions ranging from 0 to 1200 cents, but of course this all could be restated in terms of putting points on a unit line segment, at positions from 0 to 1, or on a circle, at angular positions from 0 to 2π. The Wikipedia article says in the latter form it has applications to phyllotaxis, although I’m not sure it has anything significant to say in that field. The theorem also has applications in the theory of Sturmian words, it says, and if I ever come to grips with what Sturmian words are and why one would care, maybe I’ll write about them here… don’t hold your breath, though…

## Three gaps, part 3

Let’s look at a proof of the three-gap theorem given by F. M. Liang and restated more clearly by Schiu [paywall].

Here’s the 6-note scale again:

We’re going to look for gaps that are “rigid”, by which we mean this: A rigid gap is one that, if shifted (right) by X, does not coincide with another gap.

Think about the gap from F to G (the leftmost blue gap). If you shift it (right) by X, you get the gap from C to D. Shift gap CD by X and you get the gap GA; shift that by X and you get the gap DE. But if you shift DE by X you don’t get a gap: you get a segment from A to where B would be if there were a B. The gap DE is rigid. EF (the purple gap) is rigid too, because shifting it by X doesn’t give you a gap (it goes from where B would be to C). And AC (orange) is rigid, because shifting it by X gives you the segment EG, which is two adjacent gaps (EF and FG), not one.

Generally, there are only two ways a gap can be rigid. One is if when you do the shift one or the other of its end notes doesn’t map to a note. That happens only when one or the other of the end notes is the last note added (A in this case), in which case there isn’t a note X to the right of it. We’ll call this a Type I rigid gap.

The other way is if when you do the shift there is a note, or more than one note, in the middle of the shifted segment. But that happens only if the note(s) in the middle have no notes X to the left of them. Otherwise there’d be one or more notes in the middle of the unshifted gap, and by the definition of a gap, there isn’t. And the only note with no note X to its left is the first note (F in this case), so there can be only one note in the middle of the shifted gap and there can be only one rigid gap of this sort. This is a Type II rigid gap.

And that means there are no more than three rigid gaps: two Type I gaps that start or end on the last point, and one Type II whose shifted version contains the first point. All the other gaps are nonrigid. By shifting any one of them one or more times, you can make it coincide with one of the rigid gaps, and so it must be the same size as one of the rigid gaps. Therefore there can be at most three gap sizes.

That’s the first part of the theorem. Second part, coming up soon.

## Three gaps, part 2

Previously we saw if you build a musical scale by starting at F and adding notes, each a perfect fifth (702 cents, approximately) above the previous, modulo an octave, you start to see a pattern: Each scale has at most three kinds of intervals between consecutive notes, or what we call gaps. If there are three kinds, then the largest is equal to the sum of the two smaller ones. When you add a note to such a scale, it splits one of the large gaps into one of each of the two other kinds; eventually you split all the large gaps and are left with a scale having only two kinds of gaps.

At least that’s the pattern up through seven notes. Does it continue?

Adding an eighth note, F♯, splits the whole tone between F and G into two semitones — but, contrary to what you might expect, they’re not equal; one is a diatonic semitone and one is a slightly larger chromatic semitone, 104 cents. It’s yellow.So in the eight note scale there are three kinds of gaps again. (And the big one, the whole tone, is the sum of the two others.)

Add notes nine through twelve and you split the remaining whole tones, ending up with a twelve note scale with two kinds of gaps, diatonic and chromatic semitones.

And you can still go on. The thirteenth note splits a chromatic semitone into a diatonic semitone plus a Pythagorean comma (which is very small, about 24 cents, and grey), so we have three kinds of gaps again, with the chromatic semitone being the sum of the diatonic semitone and the Pythagorean comma. (In the diagram I’m running out of room, so I just show the sequence number of each note, not the letter name.)

And if you keep going, when you get to the 17th note it splits the last of the chromatic semitones and you have a scale with two kinds of gaps, diatonic semitones and Pythagorean commas. And so on. You can keep this up for weeks if you want to.

What’s intriguing is that the 5-note scale, called a pentatonic scale, is widely used especially in folk music; the 7-note diatonic scale is the basis of most mainstream Western music; the 12-note chromatic scale (in a slightly different tuning) is what you find on a piano keyboard; and while the 17-note scale has no significant role in western music, the 13th century Islamic music theorist Safi al-Din al-Urmawi developed scales based on division of the octave into 17 notes. Note those are all 2-gap scales. Meanwhile the 3-gap scales with 4, 6, 8, 9, 10…  notes don’t turn up much at all. Hm.

Now, all of this can be generalized. You can use tempered fifths (as opposed to pure), you can use other intervals like major or minor sixths, pure or not; heck, you can use any interval you want to generate scales. For that matter you can use a tempered octave as your circle, or a perfect twelfth or something else. And if you do you always find the same pattern. Every scale has one, two, or three kinds of gap, and if there are three kinds, the largest gap is the sum of the other two.

Yes, that’s what you observe, but is it always true? It is, and that’s the three-gap theorem.

Wikipedia states it as

if one places n points on a circle, at angles of θ, 2θ, 3θ … from the starting point, then there will be at most three distinct distances between pairs of points in adjacent positions around the circle. When there are three distances, the larger of the three always equals the sum of the other two.

An article by Peter Schiu [paywall] gives it as

Let α > 0 be an irrational number and n > 1. For 1 ⩽ m ⩽ n, order the fractional parts of mα to form an increasing sequence (bm):

Then there are at most three distinct values in the set of gaps gm defined by

Moreover, if there are three values, then the largest one is the sum of the other two.

Despite the musical roots going back to Pythagoras and Safi al-Din al-Urmawi, this theorem wasn’t proved until the late 1950s.

Shall we look at a proof? Sure. In the next part.

## Three gaps, part 1

From David Eppstein’s blog I learned of a new Wikipedia article about the three-gap theorem. The who? I’d never heard of it myself, but was familiar with the general idea, having written about an application of it in a long article on scales for xenharmonic music.

In a more conventional music context, think about notes in the range from one note, say F, to the next F an octave higher. Scales, if you will. Here’s a representation of that. Ignore the black box for now and just focus on the white rectangle. That’s an octave, with our first note, F, at the left end.

(These diagrams may be rather small and hard to see; click on them to expand them.) Notes an octave apart are considered to be equivalent for our purposes, so you can think of the left end as being joined to the right.

One way to talk about the distances between musical pitches — intervals, as they’re called — is to use a unit called cents, where 1200 cents make an octave. We’re going to generate a scale based on an interval called a perfect fifth, which is $X\equiv 1200\log_2 (3/2)$ cents — about 702 cents. So we’ll take our note F, shift it to the right by a distance X (see arrow below), and call that new note C.

We’ll call the interval between two consecutive notes a gap. Here there are two gaps, one from F to C which is a perfect fifth, 702 cents, and one from C to F which is a perfect fourth, 498 cents. These are shown in red and green respectively, and they add up to one octave, 1200 cents. This is a rather minimalist scale, two notes, with two kinds of gaps. (The number in the black box tells you how many notes are in the scale.)

Now go up a fifth again, starting from C. That puts you past the right end of the octave, but remember we identify the right end with the left end, so we can think of the arrow as going to the right end and then continuing from the left end to the new note, G.

G lands between F and C. It’s 2X above F, minus an octave, which works out to 204 cents, an interval called a whole tone. From G to C is 702 cents minus 204 cents or 498 cents, so G splits the perfect fifth from F to C into a whole tone (in blue) plus another perfect fourth (again in green). In this three note scale there again are two kinds of gaps.

Going up another perfect fifth gives us D, between C and F and splitting that perfect fourth into a whole tone and a major third (294 cents). Now we have a four note scale with three kinds of gaps. The major third is orange.Notice the big gap (perfect fourth) is equal to the sum of the other two.

The next perfect fifth gives us A, which splits the remaining perfect fourth into a whole tone and a major third. This five note scale is back to having two kinds of gaps.

Add a sixth note, E,  and one of the major thirds gets split into a whole tone and a diatonic semitone (90 cents), shown here in purple. There are three kinds of gaps. The big one (major third this time) is again equal to the sum of the other two.

But adding a seventh note, B, splits the other major third into a whole tone and a diatonic semitone, and once again there are two kinds of gaps.

At this point we have a diatonic scale, or in less pedantic terms, a C major scale if you start on C. (Or A minor if you start on A.)

You start to see a pattern. Each scale has at most three kinds of gaps. If there are three kinds, then the largest is equal to the sum of the two smaller ones. When you add a note to such a scale, it splits one of the large gaps into one of each of the two other kinds; eventually you split all the large gaps and are left with a scale having only two kinds of gaps. But maybe we’re getting ahead of ourselves? That’s the pattern so far, but does it continue?

We’ll see in part 2.