Chains and Denominators

Here I'd like to shed some light on why the denominators of certain rotated expansions contain chains of Markov numbers. We talked about that near the end of The Pattern, remember.

Let's start with some facts. I now have good experimental evidence that for each solution (u,v,w) with u ≥ 5, 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. I can also improve my answers to the following questions.

• Is the distance between denominators always equal to the repeat length of the expansion? Yes.
• Does rotation always produce the desired denominators? Yes. We never need to allow more general equivalent numbers.

Here are a few other details you might be wondering about.

• 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. Let's take u = 13 as an example; everything I'm going to say about it applies word for word to every other exceptional solution. The rotations with interesting denominators are the original expansion 221111 and the first rotation 211112, and of course the latter has reflection symmetry.
• What about numerators? Well, here's a fun fact that applies to any continued fraction expansion, finite or not, repeating or not. If we remove a₀ and compute the numerators, we get a sequence of numbers. If instead we compute the denominators and remove q₀ = 1, we get the same sequence of numbers. You can visualize that as a commutative diagram if you like! For a purely repeating expansion, removing a₀ is the same as rotating by 1, so as long as rotation is allowed, numerators contain essentially the same things as denominators. I just can't be bothered to talk about both all the time.
• What about the solutions with u = 1 and u = 2? Well, we already know all the facts: the denominators of the original expansions contain the corresponding chains. Can we shoehorn those facts into the shoe that fits all the other solutions? Technically, we do have two rotations (that happen to be equal) and two chains (that happen to coincide), so … maybe? Later I'll present some evidence that supports that point of view.

So much for facts. What about theory? I can't explain everything (yet), but I can explain enough to turn an unfathomable mystery into a plausible result that just needs a few details filled in. It will help to have a large example, that is, an example based on a solution with large numbers that probably won't appear by accident. There's a nice gap between 5 and 13, so let's consider solutions where all the numbers are at least 13. The first, (1325,34,13), turns out to be atypical because 13 is close to 34, but the second, (7561,194,13), is fine. So … first, we'll need to know what the chains look like.

Chain 7561a	starts with	6684339842.
Chain 7561b	starts with	99816291793.

To see how the solutions loop around through the tree, we can use the same kind of table as last time.

n	u	v	w
5	78011745950865685685602	3439216422099659041	7561
4	3439216422099659041	151620880341401	7561
3	151620880341401	6684339842	7561
2	6684339842	294685	7561
1	294685	13	7561
0	13	194	7561
−1	194	4400489	7561
−2	4400489	99816291793	7561
−3	99816291793	2264132942340130	7561
−4	2264132942340130	51357327431284876997	7561

This time it's not a surprise that going backward leads to chain 7561b, I just kept the rows in reverse order for consistency. Also it pleases me to have the upper chain in the upper half of the table.

Also note that the exponential growth factor is approximately 3w = 22683.

Second, we'll need some denominators! To produce the table below, I took the two interesting rotations of expansion(7561), ran the second algorithm on them, removed the numerators to save space, and then rotated the whole thing 90 degrees clockwise. The upper chain started out on top, so now it's on the right. Also I added row numbers so that row n contains a_n and q_n.

−2		1				1
−1		0				0
0		1		2		1		2
1		1		1		2		2
2		2		1		3		1
3		3		1		5		1
4		5		1		13		2
5		13		2		31		2
6		31		2		44		1
7		44		1		75		1
8		75		1		119		1
9		119		1		194		1
10		194		1		507		2
11		507		2		1208		2
12		1208		2		1715		1
13		1715		1		2923		1
14		2923		1		4638		1
15		7561		2		7561		1
16		18045		2		19760		2
17		25606		1		47081		2
18		43651		1		66841		1
19		69257		1		113922		1
20		112908		1		294685		2
21		295073		2		703292		2
22		703054		2		997977		1
23		998127		1		1701269		1
24		1701181		1		2699246		1
25		2699308		1		4400515		1
26		4400489		1		11500276		2
27		11500286		2		27401067		2
28		27401061		2		38901343		1
29		38901347		1		66302410		1
30		66302408		1		105203753		1
31		171506163		2		171506163		1
32		409314734		2		448216079		2
33		580820897		1		1067938321		2
34		990135631		1		1516154400		1
35		1570956528		1		2584092721		1
36		2561092159		1		6684339842		2
37		6693140846		2		15952772405		2
38		15947373851		2		22637112247		1
39		22640514697		1		38589884652		1
40		38587888548		1		61226996899		1
41		61228403245		1		99816881551		1
42		99816291793		1		260860760001		2

If we compare the left and right sides, we find that there are several matches.

• The denominators up to 2923 are the same, although offset by one row.
• The denominators at n = 15 are the same (7561!) and the denominators at n = 31 are the same. That pattern continues: in every sixteenth row, the denominators are the same.

I just mentioned one especially interesting match, u = 7561, but actually there are two more before that, v = 194 and w = 13! I verified by experiment that the same thing happens in general: u, v, and w always appear in denominators that contain chains (and generally don't appear in other denominators). In fact, they appear in predictable locations, but in order to tell you about that, I'll need to define three new things. Technically all three are functions, but when it suits me I'm going to leave off the argument and let it default to u.

• Let L be the length of expansion(u).
• Let W be the total number of w-flips that occur on the way to the solution (u,v,w). For example, W(7561) = 2.
• Let δ be the offset (−1)^W.

Now, here are the locations. For your convenience, the last column shows the raw length values for the large example.

	lower		upper
w	L(w)	− 1	L(w)	− 1 − δ	6
v	L(v)	− 1 + δ	L(v)	− 1	10
u	L(u)	− 1	L(u)	− 1	16