Symmetries

Here I'd like to talk about three symmetries of the pattern and the expansions. Before that, though, I'd like to make two quick points.

First, let's go back and examine the idea of rotations that I used without much explanation in The Pattern. If we have a purely repeating expansion, we can unroll it and write it in an infinite number of ways, as shown in the first column below. Then, if we remove the non-repeating prefixes, we get a finite number of purely repeating expansions that are equivalent to the original expansion, as shown in the second column below. Those expansions are the rotations that I was talking about. In particular, yes, I count the original expansion as a rotation.

[1,2,3,4]	[1,2,3,4]	[4,3,2,1]
[1,2,3,4,1]	[2,3,4,1]	[1,4,3,2]
[1,2,3,4,1,2]	[3,4,1,2]	[2,1,4,3]
[1,2,3,4,1,2,3]	[4,1,2,3]	[3,2,1,4]
[1,2,3,4,1,2,3,4]
[1,2,3,4,1,2,3,4,1]
:

In the third column I added the reflections of the rotations, which as you can see are also the rotations (in reverse order) of the primary reflection. A nice application of the dihedral group! The reflections are equivalent to each other, but they're generally not equivalent to the rotations.

Second, for reference, here's an abridged table of expansions that also shows the tree structure.

							v	w
1							1	1		[1,1]
	2						1	1		[2,2]
		5					2	1		[2,2,1,1]
			13				5	1		[2,2,1,1,1,1]
				34			13	1		[2,2,1,1,1,1,1,1]
					89		34	1		[2,2,1,1,1,1,1,1,1,1]
					1325		34	13		[2,2,1,1,1,1,1,1,2,2,1,1,1,1]
				194			13	5		[2,2,1,1,1,1,2,2,1,1]
					2897		194	5		[2,2,1,1,1,1,2,2,1,1,2,2,1,1]
					7561		194	13		[2,2,1,1,1,1,2,2,1,1,2,2,1,1,1,1]
			29				5	2		[2,2,1,1,2,2]
				169			29	2		[2,2,1,1,2,2,2,2]
					985		169	2		[2,2,1,1,2,2,2,2,2,2]
					14701		169	29		[2,2,1,1,2,2,2,2,2,2,1,1,2,2]
				433			29	5		[2,2,1,1,2,2,2,2,1,1]
					6466		433	5		[2,2,1,1,2,2,2,2,1,1,2,2,1,1]
					37666		433	29		[2,2,1,1,2,2,2,2,1,1,2,2,1,1,2,2]

Now, symmetries! The first symmetry is easy to understand. If we ignore the first three solutions, the rest of the tree breaks into two subtrees, an upper one rooted at 13 and a lower one rooted at 29. Given an expansion in the upper subtree, if we swap 1s and 2s, we get a rotation of the corresponding expansion in the lower subtree. Or, better, if we swap 1s and 2s and then rotate one pair of 2s from the back to the front, we get precisely the corresponding expansion in the lower subtree. Here's an example with all the clutter removed from the expansions.

2211112211221111 = expansion(7561)
1122221122112222
2211222211221122 = expansion(37666)

It's also fairly easy to understand the reason the symmetry exists. Remember this argument from The Pattern?

The pattern applies when u ≥ 5. Applied repeatedly, it expresses any expansion as a combination of expansion(1) and expansion(2).

Suppose we have a solution (u,v,w) with u ≥ 5. Given an expansion in the subtree rooted at u, if we apply the pattern repeatedly, but stop when we leave the subtree, we'll express the original expansion as a combination of expansion(v) and expansion(w). Let's call those the large and small units. Here's a table of units for some relevant solutions, …

u	v	w		large	small
5	2	1		22	11
13	5	1		2211	11
29	5	2		2211	22
34	13	1		221111	11
194	13	5		221111	2211
169	29	2		221122	22
433	29	5		221122	2211

… and here's the example again with the expansions broken into units.

2211 11 2211 2211 11 = expansion(7561)
1122 22 1122 1122 22
2211 22 2211 2211 22 = expansion(37666)

On the first line we have the units for u = 13. On the second line the pairs of 1s are on the left sides of the large units, so when we rotate, they move to the right sides. Then, on the third line we have the units for u = 29. Since the sequence of large and small units is the same, that's the corresponding expansion in the lower subtree.

Here are some other ways of thinking about the symmetry that don't require rotation.

• Remove the second line and take the operation to be “swap 1s and 2s but only in the small units”. As a bonus, that makes it an involution.
• Remove the third line and take expansion(5) to be [1,1,2,2] for the purpose of constructing all the expansions in the lower subtree. Then the operation is just “swap 1s and 2s”, also an involution.

The second symmetry is less tangible. To begin, I should say more about sequences of large and small units. So, again, suppose we have a solution (u,v,w) with u ≥ 5, and suppose we make the following definitions.

expansion(v)	= L
expansion(w)	= S

From the pattern, we know that expansion(u) consists of one large unit and one small unit.

expansion(u) = expansion(v) & expansion(w) = LS

If we do a v-flip, we replace v with a new value u_v to get the (normalized) solution (u_v,u,w). The numerical value of u_v doesn't matter here, but to avoid total vagueness I'd like to remind you that it's 3uw − v.

expansion(uv)	= expansion(u) & expansion(w)
	= expansion(v) & expansion(w) & expansion(w) = LSS

Similarly, if we do a w-flip from the original solution (u,v,w), we replace w with a new value u_w to get the solution (u_w,u,v).

expansion(uw)	= expansion(u) & expansion(v)
	= expansion(v) & expansion(w) & expansion(v) = LSL

In the same way, we can compute the sequences for as many solutions as we like. For example, if we do a w-flip from (u_v,u,w), we get the solution (u_vw,u_v,u).

expansion(u_vw) = expansion(u_v) & expansion(u) = LSSLS

Here are the results for the first four layers.

LS
	LSS
		LSSS
			LSSSS
			LSSSLSS
		LSSLS
			LSSLSLS
			LSSLSLSS
	LSL
		LSLL
			LSLLL
			LSLLLSL
		LSLLS
			LSLLSLS
			LSLLSLSL

So, when I said that corresponding expansions have the same sequence of large and small units, I wasn't just talking about the subtrees at 13 and 29, I was talking about all possible subtrees! You can use the table of units to see how it works. Just pick a row, then you can map the tree of sequences onto the subtree of expansions rooted at u. I particularly like the row with u = 194.

To make that a bit more formal, for each solution (u,v,w) with u ≥ 5 let's define a function h_u that maps sequences to expansions, so that for example h₅(LS) = 2211. Are the functions h_u one-to-one? It's an interesting question.

1. If we take the domain to be only the sequences that actually occur in the tree of sequences, then the answer is yes, otherwise we'd have two solutions with the same expansion, and that's impossible, as I mentioned in The Markov Constant (“one equivalence class for every solution to the Markov equation”).
2. If we take the domain to be all nonempty sequences of Ls and Ss, then the answer depends on how we think about the expansions.
   1. If we think of them as strings of 1s and 2s, then I suspect the answer is still yes. I don't know how to prove it, but the result in point 3 is probably a good place to start.
   2. If we think of them as numbers, then the answer is no, because for example h_u(LL) always consists of two copies of h_u(L) and so represents the same number.
   3. If we think of them as equivalence classes, then the answer is the same no plus another, because for example h_u(SSL) is always a rotation of h_u(LSS) and so represents an equivalent number.
3. Would any other function h work just as well? No. The sharpest counterexample I have is the function

   h(L) = 212121
   h(S) = 2121,

   which maps LSLL and LSSSS, two sequences that actually occur in the tree, to the same string of 1s and 2s. So, maybe we should impose the condition that h(L) and h(S) don't consist of copies of a common subunit? For point 2a, I can prove that that condition is both necessary and sufficient. For point 1, if the result in point 4 holds, then I can prove that the condition is necessary, but I have no idea whether it's sufficient.

4. Suppose we define a function from sequences to integer points in the plane that counts the Ls and Ss and uses the results as coordinates. Experimental evidence suggests that that function creates a one-to-one correspondence between the tree of sequences and … the open spaces in the number maze!

There are some loose ends in there, but they're harmless because all I really care about is point 1. When the domain is the tree of sequences, the functions h_u are one-to-one, therefore they have well-defined inverses. To compute the inverse image of an expansion, we just need to figure out how to break it into the appropriate large and small units. For u = 5 that's easy, we just break the whole expansion into pairs. For u = 13 and u = 29 that's still easy, we just identify the large units (2211) and then break the rest into pairs. As u becomes larger, though, the process seems to become gradually more difficult. Maybe some kind of branching search is required? It might also be helpful somehow to know that if we do a u-flip to go backward from (u,v,w), we get either (v,w,x) or (v,x,w), so that the small unit expansion(w) is guaranteed to be either a prefix or a suffix of the large unit expansion(v). Sometimes it's even both! The one exception is that if u = 5, then v = 2 and the pattern no longer applies.

Now we have everything we need to construct proper symmetries that relate expansions to expansions. By composing an appropriate function h_u with an appropriate inverse function h_u⁻¹, we can map any subtree through the tree of sequences onto any other subtree. For example, 194 is in the vw position relative to 5, and 14701 is in the vw position relative to 29, so if we apply h₂₉∘h₅⁻¹ to expansion(194), we get expansion(14701).

22	11	11	22	11 = expansion(194)
L	S	S	L	S
2211	22	22	2211	22 = expansion(14701)

The third symmetry will shock you! For every expansion, there's a rotation that has reflection symmetry, i.e., is equal to its own reflection. In fact, there are two such rotations, because if we have one and rotate by half its length, we get another, as in the unrealistic example below.

[1,2,3,4,4,3,2,1]
[4,3,2,1,1,2,3,4]

In fact, there are always exactly two such rotations, no more.

Can we redefine the expansions so that they're symmetrical? No. For one thing, the expansions are completely determined by expansion(1), expansion(2), and the pattern. For another, even if we impose symmetry as an initial condition, the pattern creates new asymmetry. As an example, here's the start of chain 5a.

expansion(194)	=	expansion(13)	&	expansion(5)
2211112211		221111		2211
1122112211		112211		1221
1221111221		211112		2112

The first row shows the actual values of expansion(u), while the second and third rows show the symmetrical forms. The only combination of symmetrical expansion(13) and expansion(5) that even gives a correct answer is 211112 & 2112, and of course that's not symmetrical.

We're on the right track, though. If we split expansion(5) in half and let it wrap around, we get 12 & 211112 & 21, an answer that's both correct and symmetrical. Or, better, if we also split expansion(13) in half, we can discard two of the four halves and work entirely with half-expansions. Then we get 112 & 21, with the symmetry built in.

There's one more complication, however. As we proceed along chain 5a, it seems like we ought to append the same suffix 21 at every step, but that immediately gives us a value 11221 & 21 that's obviously incorrect because it contains unpaired 1s and 2s. But, if we take the other symmetrical form of expansion(5), or equivalently just reflect 21 to make 12, we get a value 11221 & 12 that's not only not obviously incorrect but also correct. At the next step we need to append 21 again, at the next step 12, and so on, with the underlying suffix being reflected at every other step.

There are a few other details that emerge when we expand our view from chain 5a to the entire tree, but let's skip the journey of discovery and go straight to the destination. Here's the pattern for half-expansions.

half(u) = reflect-first(half(v)) & reflect-every-other(half(w))

Here are the definitions of those two functions.

• The function reflect-first reflects at the first step of a chain.
• The function reflect-every-other reflects at every other step of a chain. It starts at the second step for upper chains like chain 5a and at the first step for lower chains like chain 5b.

And here's a table of half-expansions with reflected terms in bold.

							v	w
1							1	1		1
	2						1	1		2
		5					2	1		2	1		1
			13				5	1		21	1
				34			13	1		211	1
					89		34	1		2111	1
					1325		34	13		1112	211		13a
				194			13	5		112	21		5a
					2897		194	5		11221	12
					7561		194	13		12211	112		13b
			29				5	2		12	2		2
				169			29	2		122	2
					985		169	2		1222	2
					14701		169	29		2221	122		29a
				433			29	5		221	12		5b
					6466		433	5		22112	21
					37666		433	29		21122	221		29b

What about the terms on the right in chains 1 and 2? On the one hand, remember this sentence from The Pattern?

So, there are two chains per solution … unless the solution is (1,1,1) or (2,1,1), in which case there's only one chain because the initial flips lead to the same place.

It would be more accurate to say that in that case the two chains coincide, but either way, it isn't clear what the function reflect-every-other is supposed to do. On the other hand, it also doesn't matter what it does, because reflection has no effect on a value of length 1. That's not a satisfying resolution, but I think it's impossible to say more.

The first symmetry is in plain sight here. Just swap the 1s and 2s!

I have good experimental evidence that the pattern for half-expansions agrees with the pattern for full expansions. I think it should be possible to prove that the two always agree, no advanced techniques required, just plenty of attention to detail, but I haven't tried yet. To be honest, the whole idea gives me a headache.

In the end, the pattern for half-expansions seems like more trouble than it's worth. But, it would have been unsatisfying to just say “every expansion has a rotation with reflection symmetry”, and there's no stopping point in between.