Properties of Rotations

1. At the start.

   … exactly one rotation of expansion(u) has denominators that contain the upper chain associated with u and exactly one other rotation of expansion(u) has denominators that contain the lower chain associated with u.

2. In the third bullet point.

   The two rotations with interesting denominators are generally disjoint from the two rotations that have reflection symmetry. The exceptions are exactly the solutions in chain 1.

3. Near the end.

   … u, v, and w always appear in denominators that contain chains (and generally don't appear in other denominators).

   The part in parentheses is vague, but it's true as long as you take “appear” to mean “appear together”. It also turns out that in denominators that contain chains, the value u always appears at position L(u) − 1.

4. Near the end of Group Elements and Matrices we saw that c was equal to u for the matrices in the top row of that table. But, c is also a denominator, so we can say that for the solutions in chain 1 (and at least two others), u appears in the denominators of the unrotated expansion.

   To be precise, c is the denominator q_L−1. I explained why near the end of The Discriminant.

   To compute c = q_n, we run the second algorithm on one iteration of the expansion. The first denominator that we get is q₀, so the last, for an expansion of length L, is q_L−1.

Unfortunately, the examples only provide small and frustratingly incomplete views of the underlying structure. To get the big picture, I ran some experiments, and now I'll tell you all about the results. Let's start by making a list of all the properties that we care about.

26. The property of being unrotated. Rotation 0 has this property.
19. The property of having reflection symmetry. We know from Symmetries that exactly two rotations per solution have this property.
3. The property of having denominators that contain a chain. We know from Chains and Denominators that exactly two rotations per solution have this property. Let's also define the more specific properties C₁ for the upper chain and C₂ for the lower chain.
21. The property of having denominators that contain u. With a bit of precognition, let's also define the more specific properties U₁ for when q_L−1 = u and U₂ for when q_L−2 = u.
22. The property of having denominators that contain v.
23. The property of having denominators that contain w.

The last three properties aren't as sharply defined as one might like. For example, we always have q₀ = 1. For the solution (1,1,1), should that count as an appearance of u, v, or w? Or all three? Similar questions arise for (2,1,1), the only other solution with duplicate values. Even worse, when a₁ = 1 we also have q₁ = 1, and the questions multiply.

To avoid the problems of duplicate values and duplicate denominators and the similar problems mentioned in the fifth bullet point of Chains and Denominators, for the rest of the essay I'm just going to require that u ≥ 5. If you have any questions about the first two solutions that aren't about angels dancing on heads of pins, I'm sure you can answer them easily enough. If it helps, you can find the first few denominators near the end of The Pattern.

Two quick notes about the problem of duplicate denominators:

• The problem is small. It's possible to have q₁ = q₀, but after that, the sequence of denominators is strictly increasing, so there are no more duplicates. (What about the initial condition q₋₂ = 1 and all the denominators produced by going backward? We shouldn't count them because they belong to a different rotation.)
• The problem isn't completely swept under the rug by the requirement that u ≥ 5. We still see the value w = 1 in the solutions in chain 1 (almost by definition), and that gives us q₀ = w for all rotations and also q₁ = w for all rotations except the two with a₁ = 2. Maybe we ought to define a property to acknowledge that, something like “w appears twice”, but I think a really good definition would require a larger investigation into the positions that w can appear in.

Now, experimental results! First of all, it turns out that U implies V and V implies W. To me, that means we can forget about properties V and W. If u appears, then so do v and w, and if u doesn't appear, then who cares about v and w. Actually I do care a little, but let's come back to that later.

We can think of a property as a set, the set of rotations (per solution) that have that property. That gives us a bunch of nice words we can use. As one example, we already know that the intersection of C₁ and C₂ is empty, and the union is the whole set C, so {C₁,C₂} is a partition of C. As another example, the intersection of U₁ and U₂ has to be empty, because otherwise we'd have duplicate denominators, and the union, it turns out, is the whole set U, so {U₁,U₂} is a partition of U. OK, technically it's not a partition because U₂ is usually empty, but close enough.

We also already know that C implies U, or more precisely U₁. It turns out that the converse is true as well, that U₁ implies C. That means the two are equivalent, and that means we can forget about property U₁.

Where does that leave us? We have the three properties C₁, C₂, and U₂. They're disjoint. The first two always contain one rotation each, while the third is usually empty. The union of the first two is C, and the union of all three is U. Now we want to see how those properties interact with the properties S and Z.

In general, the answer is that they don't interact. Except in the three cases listed below, U₂ is empty and C₁ and C₂ don't intersect with S and Z. That's pretty straightforward.

Here are the three cases.

			C1	C2	U2	S1	S2
chain 1	u = 5	2211	0	1	3	1	3
	u ≠ 5	2211(11)+	0	1	-	1	1 + L/2
chain 2		2211(22)+	1	4	3	3	3 + L/2

That table has so many interesting features that I want to discuss, but let's stay focused and look at the intersections with S and Z.

• For chain 1, C₁ intersects with Z. That's a slightly more specific version of the fourth example.
• For chain 1, C₂ intersects with S. That's a slightly more specific version of the second example.
• For chain 2 and the solution u = 5, U₂ intersects with S. That's a new result! I'll explain all about property U₂ later on.

Next, let's examine the role that the solution u = 5 plays. It's part of chain 1, of course, so it's not a surprise that the numbers agree with the rest of chain 1. C₁ and C₂ match, and S₁ and S₂ match when we take into account that L(5) = 4. Only U₂ is different.

However, if we take into account not just that L(5) = 4 but also that rotation numbers are not really integers but rather integers mod L, then the numbers agree with chain 2 as well. C₁ and C₂ match with a swap, and S₁ and S₂ match with a swap. Even U₂ is the same! In that sense, the solution u = 5 is also part of chain 2. Let's call the two together extended chain 2.

How can one solution be part of two different structures? Simple! The expansions in chain 1 contain just one pair of 2s, the expansions in extended chain 2 contain just one pair of 1s, and expansion(5) consists of one pair of each. Or, here's another way to look at it. The first symmetry creates a one-to-one correspondence between chain 1 and extended chain 2 … and has the solution u = 5 as a fixed point!

I did mislead you about one little detail, though. I said that C₁ and C₂ matched with a swap, but C₁ and C₂ are not interchangeable. Let's make that abstract statement more concrete by focusing on rotation 1, the one that starts with 211.

• For the solution u = 5 (and the rest of chain 1), rotation 1 has property C₂: the denominators contain the lower chain, the numerically larger one that we reach by doing two w-flips.
• For chain 2, rotation 1 has property C₁: the denominators contain the upper chain, the numerically smaller one that we reach by doing a v-flip and then a w-flip.

So, yes, there's a real difference. We could sweep it under the rug a little by redefining C₁ as the rotation that starts with 22 and C₂ as the rotation that starts with 211, but that seems too artificial. Better to just accept the difference.

I didn't emphasize it, but we ran into the same difference back in Sketch of a Proof. Every little movie there starts and ends with the standard values, right? When δ = +1, the upper expansion starts with 22 and the lower expansion starts with 211, and when δ = −1, it's the other way around. Since δ is (−1)^W, the behavior is controlled by the parity of W. Of course here I mean not W the property but rather W the number, the total number of w-flips that occur on the way to the solution (u,v,w). And, to get back to the current context, in chain 1 we have W = 0, while in chain 2 we have W = 1.

Next, recall that the expansions in extended chain 2 contain just one pair of 1s. That, it turns out, is the reason that rotation 3 of those expansions has property U₂! As an example, let's look at the solution u = 169. Here are the relevant expansions, the associated denominators, and some notes.

		2	1	1	2	2	2	2	2
1	0	1	1	2	5	12	29	70	169
		2	2	2	2	2	2	2
1	0	1	2	5	12	29	70	169
		2	2	2	2	2	2	1	1
1	0	1	2	5	12	29	70	99	169
		1	2	2	2	2	2	2	1
1	0	1	2	5	12	29	70	169	239

1. The first expansion is rotation 1. Because q₇ = 169, it has property U₁, and if you compute more denominators you can see that it also has property C₁.
2. If we shorten the first expansion by performing a same-denominator conversion (see Triangles), we get a useful intermediate expansion that's not a rotation.
3. If we lengthen the second expansion by performing a proper-improper conversion, we get rotation 4. It has property U₁, and if you compute more denominators you can see that it also has property C₂.
4. However, we can also lengthen the second expansion by just tacking a single 1 onto the end. Then we can create a pair of 1s by changing a₀ (doesn't affect the denominators), and then we have a rotation, rotation 3 as it happens. And, because q₆ = 169, it has property U₂.

In that whole process, the four 2s in the middle of the first expansion just went along for the ride, so why does it matter that there was only one pair of 1s? The key is that the pair of 1s that we created is misaligned with respect to the middle. So, if the first expansion had contained any other pairs of 1s, the result wouldn't have been a rotation because it wouldn't even have been composed of pairs.

Now we know all about the three properties C₁, C₂, and U₂ and how they interact with the properties S and Z. That still leaves a tiny gap, though. We know about intersections with S and Z, but what about intersections between S and Z? There are a few, it turns out, but the details are complicated and not really related to anything else we've been talking about, so I moved the whole thing into a separate essay, Reflection Symmetry.

Finally, let's go back and take a very quick look at the properties V and W. I don't want to know how they intersect with other properties, or even which rotations they contain, I just want to know how many rotations they contain. Since we're already thinking of properties as sets, we can use the fairly standard notation |V| for the size of the set V. And, as points of reference, we know that most of the time |U| = 2, while in extended chain 2 we have |U| = 3, and we know that U implies V and V implies W, which means that |W| ≥ |V| ≥ |U|.

The results for |V| are not so different from the results for |U|. Most of the time |V| = 3, in non-extended chain 2 we have |V| = 5, and in two cases we have |V| = 4. Here are the details.

	|U|	|V|
u = 5	3	3
u = 13	2	4
u = 29	3	5
in general	2	3
chain 2	3	5
successor	2	4

Here, by “chain 2” of course I mean “chain 2 minus the solution u = 29”. Can't let the table entries overlap!

By “successor” I mean “successor to chain 2 in breadth-first order”. Remember that picture of the tree structure back in The Markov Equation? If we read across the rows, we get the solutions in depth-first order (specifically preorder), but if we read down the columns, we get the solutions in breadth-first order. So, at depth 0 we get the solution u = 5, then at depth 1 we get 13 and 29, at depth 2 we get 34, 194, 169, and 433, and so on. At depth n there are 2ⁿ solutions. The advantage of breadth-first order is that it makes sense not just for finite pictures but also for the whole infinite tree, and that's what I'm thinking of here.

Note that we can find the successor to any solution in chain 2 by doing a u-flip to undo the last v-flip and then doing a w-flip. We don't need to compute the whole tree.

The solution u = 29 doesn't have a successor at the same depth, but, oddly, its predecessor, the solution u = 13, seems to play the same role.

The results for |W| are … different. If we look at the values in breadth-first order, the first few seem chaotic, …

… but at depth 4 a pattern emerges.

The blocks have lengths that are powers of 2. The colorful ones contain Tower of Hanoi patterns.

red	? 5 7 5
orange	? 5 7 5 9 5 7 5
yellow	? 5 7 5 9 5 7 5 11 5 7 5 9 5 7 5
etc.
gray	? 8 11 7 14 5 10 5

The question marks represent values that depend on the context. They also act as delimiters between blocks.

Once we know what to look for, we can discern a cleaner version of the pattern that extends back to depth 2.

Now the light and dark gray blocks are clouds that rain delimiters, and it's easy to write down the values of all the clouds and delimiters.

chain 1	4 + 2n
chain 2	5 + 2n
light gray	7 + 3n
dark gray	8 + 3n

In most of the rows, the light gray cloud follows the dark gray one, but in the first row, where there's no more room at the same depth, it precedes it. Sound familiar?