Reflection Symmetry

expansion(1) = 11
expansion(2) = 22

I'm pretty sure I noticed the first real example in passing.

expansion(29) = 221122

I'm also pretty sure I never noticed the second real example until I started work on this essay, even though I used it as an example in Symmetries (immediately above the third symmetry).

expansion(14701) = 22112222221122

There are no other examples in the range u < 10⁶. To go beyond that, I ran a breadth-first search on the tree of solutions, and here are the results to depth 10.

0	0
1	1	2	6		1
2	0
3	1	5	14		101
4	1	7	22		1110
5	1	11	34		10101
6	2	17	50		101110
		16	50		111001
7	2	27	82		1010101
		26	82		1110110
8	3	40	122		10101110
		38	114		10111001
		39	122		11100101
9	4	65	198		101010101
		62	186		101110110
		57	178		111001110
		59	186		111011001
10	5	97	294		1010101110
		92	278		1010111001
		93	278		1011100101
		94	294		1110010101
		97	306		1110110110

The first column shows the depth. I placed the solution u = 5 at depth 0 so that at depth n there are 2ⁿ solutions. The second column shows the number of solutions with reflection symmetry at each depth. Let's call that a(n). The rest of the columns describe the individual solutions. Here, unfortunately, the values of u and expansion(u) are so large that they're meaningless, but we can transform them to make them smaller. For u, we can use the number of digits, a.k.a. ⌊1 + log₁₀ u⌋. That's the third column. And, for expansion(u), we can use the expansion length L(u). That's the fourth column. The fifth column is a short code that uniquely identifies the solution. There are several ways that we can think about it.

• If we start with the solution u = 5, read the code from left to right, and do a v-flip for each “0” and a w-flip for each “1”, we get the desired solution.
• As a result, the length of the code is equal to the depth of the solution.
• If we read the code as a binary number and then add 1, we get the one-based index of the solution within solutions at the same depth. For example, 14701 is solution 6 of 8 at depth 3.
• If we add a 1 in front and then read the code as a binary number, we get the one-based index of the solution within the tree. For example, 14701 is solution 13.

Based on the second column, I imagined that the sequence a(n) was going to settle into linear growth, but when I computed a few more terms, I found that it had been on the verge of revealing some other kind of growth.

0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28

I didn't recognize the numbers, so I looked them up on OEIS and learned that they're called Padovan numbers. For completeness, here are a bunch of links to OEIS and Wikipedia.

A000045	Fibonacci number
A000129	Pell number
A000931	Padovan number

Just as Fibonacci numbers obey this recurrence relation, …

a(n) = a(n−1) + a(n−2)

… Padovan numbers obey this recurrence relation. Fibonacci numbers with the output delayed by 1!

a(n) = a(n−2) + a(n−3)

When I said “some other kind of growth”, did you check the differences to see what kind of growth it was? If you did, you got a preview of an alternate recurrence relation. Fibonacci numbers with one input delayed by 3!

a(n) = a(n−1) + a(n−5)

How can one sequence have two recurrence relations? It's simple. The main characteristic polynomial is a factor of the alternate. (The second factor is the cyclotomic polynomial P₆.)

(x³ − x − 1)(x² − x + 1) = (x⁵ − x⁴ − 1)

Just for fun, we can get a shorter statement by thinking of the polynomials as numbers in base x with negative digits.

1011 × 111 = 110001

I still haven't really explained what kind of growth the sequence exhibits, but I'm ready to do that now. The growth is controlled by the largest of the three roots of the main characteristic polynomial, approximately 1.324718. Apparently it's called the plastic number and written as ρ? So, at each depth, the number of expansions with reflection symmetry increases by a factor of ρ, and the fraction of expansions with reflection symmetry decreases by a factor of ρ/2, roughly 2/3. Of course that's all approximate because we haven't taken the other roots into account, but it's a good enough approximation that we can get the correct value for the number of expansions by rounding to the nearest integer. That works as long as the initial value is at least 3.

Finally, let's look at the main recurrence relation again.

a(n) = a(n−2) + a(n−3)

Soon after I saw it on OEIS, it occurred to me that maybe it wasn't just an equation, maybe it was also a recipe for how to find solutions with reflection symmetry. Maybe to find a solution at depth n we can either take a solution at depth n−2 and do some unspecified thing or take a solution at depth n−3 and do some other unspecified thing. And what could the unspecified things be? The obvious first guess is that we could do a fixed sequence of flips, or equivalently append a fixed suffix onto the code. And, sure enough, when I looked more carefully at the table, I saw that that guess was exactly right. We get solutions from other solutions by appending “01” or “110”.

That's a nice rule. To make it even nicer, we can use the concept of large and small units from Symmetries to prove that it works. Remember that for any solution (u,v,w), the expansions have the following structure.

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

The one new thing we'll need is some kind of notation that means that an expansion or part of an expansion should be reversed. For example, to reverse the small unit S, one option would be to write reverse(S). That blunt instrument has some appeal, but here I want something more compact. We can get other ideas from the fact that reversing is (naturally) an order-reversing operation.

reverse(LS) = reverse(S) & reverse(L)

We've already encountered two other order-reversing operations. Would it make sense to reuse the notation for either of those?

• The inverse S⁻¹ seems promising. The name is good because “inverse” and “reverse” have the same Latin root “verto”, “I turn”. The concept is good because I'm very comfortable with the idea that inverting a long sequence reverses it, partly from studying group theory but mostly from playing with Rubik's Cubes. Unfortunately, one essential property is missing. When I see S⁻¹ next to S, I definitely expect the two to cancel.
• The transpose S^T seems mediocre, mostly because expansions aren't matrices.

The other option would be to invent some custom notation, but that's not as easy as it sounds. S^*? Unintuitive. S^R? Ugly.

So how did I decide? A fact that arrived late tipped the scale. Expansions aren't matrices, but there's a nice correspondence between expansions and matrices, and under it, reversed expansions correspond to transposed matrices. That fact took the transpose S^T from mediocre to pretty good, so that's what I picked. If you don't like it, you can think of L and S as matrices instead.

Now we're ready for a quick proof by induction! The solution (29,5,2) will be the starting point, of course. The thing we're interested in is that expansion(u) has reflection symmetry, but it also turns out to be important that expansion(w) has reflection symmetry. Those will be our two conditions. Here's what they look like in terms of units.

(LS)T	= LS
ST	= S

Now suppose we have an arbitrary solution (u,v,w) that satisfies the conditions. If we do a v-flip and then a w-flip, we reach the solution (u_vw,u_v,u). We already know that expansion(u) has reflection symmetry, but what about expansion(u_vw)? As it happens, I used it as an example in Symmetries. It has the sequence LSSLS, and that sequence has reflection symmetry.

(LSSLS)^T = S^TL^TS^TS^TL^T = (LS)^TS^T(LS)^T = LSSLS

Or, if we do two w-flips and then a v-flip, we reach the solution (u_wwv,u_ww,u). Again, we already know that expansion(u) has reflection symmetry, but what about expansion(u_wwv)? I didn't use it as an example in Symmetries, but we can get its sequence LSLLSLS from the partial tree of sequences there. The middle part has reflection symmetry, …

(LLS)^T = S^TL^TL^T = (LS)^TL^T = LSL^T = LS^TL^T = L(LS)^T = LLS

… therefore the whole thing has reflection symmetry.

(LSLLSLS)^T = S^TL^TS^TL^TL^TS^TL^T = (LS)^T(LLS)^T(LS)^T = LSLLSLS

And that's that! We do get solutions from other solutions by appending “01” or “110”.

Maybe this next thought is obvious, but it surprised me. Since each solution with reflection symmetry has two descendants, those solutions constitute an infinite binary tree embedded in the infinite binary tree of Markov solutions.

That proof still doesn't quite guarantee that the actual numbers will agree with the recurrence relation.

• The numbers could be smaller if parts of the tree overlapped. Fortunately, that can't happen. If parts of the tree overlapped, then there would be two paths to the same solution, but every code has a unique decomposition into suffixes. In fact, because the two suffixes start with different digits and end with different digits, we can instantly read off the decomposition either forward or backward.
• The numbers could be larger if one or more solutions with reflection symmetry were produced by some other mechanism. I can't rule that out, but since I already computed the numbers up to depth 16, any such solutions would have to lie beyond that point.