![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mmcirvinThis is part 1 of a series of indeterminate length. Part 2 is much better-looking and it's OK to skip ahead. Part 3 is here and contains some explorations I think may be new.
When Google+ went down, it took with it a bunch of my recreational-mathematics fumbling from the past several years. Fortunately I downloaded an archive of all that stuff, but it's not in the greatest format to browse. There are some things that deserve revisiting.
In 2017, Owen Maresh (who often gets me investigating things by making mathematical art or speculating about some intriguing pattern) mentioned something peculiar on Facebook: that the sequence of nested fractions that goes
1/2, (1/2)/(3/4), ((1/2)/(3/4))/((5/6)/(7/8)), ...
seems to converge to 1/sqrt(2).
Three-legged fractions
Not content to stop there, he started thinking about his own generalization of fractions (which I've never seen anywhere else, so I'll name them after him: "Maresh multifractions") that had more numbers in it than just a numerator and a denominator. He came up with a lovely notation in which the fraction bar was replaced with a three-legged shape, like a Y. I'll use a form that is easier to type:
M(a, b, c) = a * b^(e^(i*2*pi/3)) * c^(e^(i*4*pi/3))
This is easy to generalize to more numbers (I wish I had MathJax here):
M(a_0 ... a_(n-1)) = a_0 * a_1^(e^(i*2*pi/n)) * ... * a_(n-1)^(e^(i*(n-1)*2*pi/n)))
The idea is that you have n numbers, and they're raised to the power of complex numbers that are equally spaced around the unit circle, then multiplied together.
For n=2, these are regular fractions: the complex exponent that a_1 is raised to just reduces to e^(i*pi)= -1, so it's M(a, b) = a/b. For n>2 they are generally complex numbers. I don't think objects like these have been studied much, because if you plug in integers, they don't form a field or even a ring: they are not, in general, closed under addition for n>2. So they're not a simple generalization of the rationals.
Still, he wondered aloud about nesting them the same way, as in M(M(1,2,3),M(4,5,6),M(7,8,9)), and so on. What do you get in the limit if you nest those to infinity? I eventually did some numerical experiments and didn't find an obvious detailed pattern in the complex phases, but the absolute magnitudes of these numbers did seem to converge to 1/sqrt(3), and in general to 1/sqrt(n) for n-legged Maresh multifractions.
Jumping numbers
But, meanwhile, I played around with the simple fraction case and soon realized that in the nested fractions, once a fraction in the sequence up top was reduced to an ordinary fraction, the integers would jump between the numerator and the denominator in a strange aperiodic way. For instance, here's the fifth iteration:
31*30*28*25*24*21*19*18*16*13*11*10*7*6*4*1
------------------------------------------------------------------
32*29*27*26*23*22*20*17*15*14*12*9*8*5*3*2
Whether a given integer ended up in the numerator or the denominator depended on an aperiodic sequence that I eventually realized was the Thue-Morse sequence:
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, ...
This is oeis.org/A010060 and is much more famous than I'd initially realized. You can generate it by starting with 0, then at each stage adding the complement of the existing sequence onto the end (all zeros become ones and vice versa). Or, if you want to go inside out, you can generate the whole sequence by repeatedly replacing every 0 with 0, 1 and every 1 with 1, 0.
The j'th number in the sequence is also the sum of the binary digits of the number j, modulo 2. (In other words, it's zero if the number of 1s in the binary representation is even, and one if it is odd. The ubiquitous John H. Conway called these "evil numbers" and "odious numbers", so the Thue-Morse sequence says whether every nonnegative integer is evil or odious.) Very simple.
Once I'd figured out that the Thue-Morse sequence was relevant and had a name, Owen then looked at the MathWorld page for the Thue-Morse sequence and noted that it had the answer to his original question: the convergence he'd noticed by experiment is equation (2) there, a theorem conjectured by Woods in 1978 and proven by Robbins in 1979 (at the time I think they had the attribution wrong, but they've corrected it since).
This paper by Allouche and Shallit, www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps (PostScript file!) has a lovely short proof of the theorem that Woods described in 1987. The best thing I can do to summarize it is just quote my departed Google+ article:
Though I still haven't worked it out in detail, I strongly suspect that that proof can be generalized to Maresh multifractions to obtain the result about the absolute magnitude of the nesting limit that I found by experiment, 1/sqrt(n). Only, in that case, the relevant sequence would not be the binary Thue-Morse sequence, it would be a generalization to base n. For instance, for the three-legged fractions Owen was wondering about directly, it'd be oeis.org/A053838 , which we might as well call the ternary Thue-Morse sequence:
0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1, 2, 0, 1, 2, 0, 2, 0, ...
Here, at each stage of the expansion you'd concatenate the sequence with two versions of itself, with the symbols incremented by one or two steps modulo 3. Or, alternatively, just replace every 0 with 0, 1, 2, every 1 with 1, 2, 0, and every 2 with 2, 0, 1. Or, it's the base-3 digit sums of the nonnegative integers modulo 3. And there's an analogous sequence for any n, many of which are linked from the OEIS page for the ternary version.
Why am I talking about this now? Why are fractals mentioned in the title of this post? See why in part 2!
When Google+ went down, it took with it a bunch of my recreational-mathematics fumbling from the past several years. Fortunately I downloaded an archive of all that stuff, but it's not in the greatest format to browse. There are some things that deserve revisiting.
In 2017, Owen Maresh (who often gets me investigating things by making mathematical art or speculating about some intriguing pattern) mentioned something peculiar on Facebook: that the sequence of nested fractions that goes
1/2, (1/2)/(3/4), ((1/2)/(3/4))/((5/6)/(7/8)), ...
seems to converge to 1/sqrt(2).
Three-legged fractions
Not content to stop there, he started thinking about his own generalization of fractions (which I've never seen anywhere else, so I'll name them after him: "Maresh multifractions") that had more numbers in it than just a numerator and a denominator. He came up with a lovely notation in which the fraction bar was replaced with a three-legged shape, like a Y. I'll use a form that is easier to type:
M(a, b, c) = a * b^(e^(i*2*pi/3)) * c^(e^(i*4*pi/3))
This is easy to generalize to more numbers (I wish I had MathJax here):
M(a_0 ... a_(n-1)) = a_0 * a_1^(e^(i*2*pi/n)) * ... * a_(n-1)^(e^(i*(n-1)*2*pi/n)))
The idea is that you have n numbers, and they're raised to the power of complex numbers that are equally spaced around the unit circle, then multiplied together.
For n=2, these are regular fractions: the complex exponent that a_1 is raised to just reduces to e^(i*pi)= -1, so it's M(a, b) = a/b. For n>2 they are generally complex numbers. I don't think objects like these have been studied much, because if you plug in integers, they don't form a field or even a ring: they are not, in general, closed under addition for n>2. So they're not a simple generalization of the rationals.
Still, he wondered aloud about nesting them the same way, as in M(M(1,2,3),M(4,5,6),M(7,8,9)), and so on. What do you get in the limit if you nest those to infinity? I eventually did some numerical experiments and didn't find an obvious detailed pattern in the complex phases, but the absolute magnitudes of these numbers did seem to converge to 1/sqrt(3), and in general to 1/sqrt(n) for n-legged Maresh multifractions.
Jumping numbers
But, meanwhile, I played around with the simple fraction case and soon realized that in the nested fractions, once a fraction in the sequence up top was reduced to an ordinary fraction, the integers would jump between the numerator and the denominator in a strange aperiodic way. For instance, here's the fifth iteration:
31*30*28*25*24*21*19*18*16*13*11*10*7*6*4*1
32*29*27*26*23*22*20*17*15*14*12*9*8*5*3*2
Whether a given integer ended up in the numerator or the denominator depended on an aperiodic sequence that I eventually realized was the Thue-Morse sequence:
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, ...
This is oeis.org/A010060 and is much more famous than I'd initially realized. You can generate it by starting with 0, then at each stage adding the complement of the existing sequence onto the end (all zeros become ones and vice versa). Or, if you want to go inside out, you can generate the whole sequence by repeatedly replacing every 0 with 0, 1 and every 1 with 1, 0.
The j'th number in the sequence is also the sum of the binary digits of the number j, modulo 2. (In other words, it's zero if the number of 1s in the binary representation is even, and one if it is odd. The ubiquitous John H. Conway called these "evil numbers" and "odious numbers", so the Thue-Morse sequence says whether every nonnegative integer is evil or odious.) Very simple.
Once I'd figured out that the Thue-Morse sequence was relevant and had a name, Owen then looked at the MathWorld page for the Thue-Morse sequence and noted that it had the answer to his original question: the convergence he'd noticed by experiment is equation (2) there, a theorem conjectured by Woods in 1978 and proven by Robbins in 1979 (at the time I think they had the attribution wrong, but they've corrected it since).
This paper by Allouche and Shallit, www.cs.uwaterloo.ca/~shallit/Papers/ubiq.ps (PostScript file!) has a lovely short proof of the theorem that Woods described in 1987. The best thing I can do to summarize it is just quote my departed Google+ article:
What we're really trying to find is the infinite product
P = (1/2)^1 * (3/4)^(-1) * (5/6)^(-1) * (7/8)^(1) * ...
where the exponents are all -1 raised to the power of the Thue-Morse sequence numbers. Now consider the product Q, which is constructed almost the same way, only we start with 2, and also start with the second element of the Thue-Morse sequence:
Q = (2/3)^(-1) * (4/5)^(-1) * (6/7)^1 * (8/9)^(-1) *...
Now multiply them together. The odd numbers cancel out, except for 1:
PQ = (1/2)^1 * (2/4)^(-1) * (4/6)^(-1) * (6/8)^1 * ...
We can simplify those factors to make
PQ = (1/2) * (1/2)^(-1) * (2/3)^(-1) * (3/4)^1 * (4/5)^(-1) * (5/6)^1 * (6/7)^1 * ...
Now, the Thue-Morse sequence has a kind of self-similarity: if you pick out the even-numbered elements (with zero-based numbering), they're the same as the original sequence, and the odd-numbered elements are the complement of the original sequence (0 swapped with 1). (That follows immediately from its definition in terms of a symbol-rewriting system). So if we separate out the even-numbered and the odd-numbered factors in this infinite product, we get
PQ = (1/2) * (1/P) * Q
Q drops out entirely, and
P^2 = 1/2
P = sqrt(2)/2.
Q, which I'd approximately calculated (or was it just a related number?) while I was messing around with this stuff earlier (it fell out of my sort of "generating function" method), is quite mysterious; this paper says it first appeared in a paper by Flagolet and Martin (the Inverse Symbolic Calculator mentioned Flagolet), and claims nobody has proven whether it is even rational or irrational.
n-ary Thue-MorseThough I still haven't worked it out in detail, I strongly suspect that that proof can be generalized to Maresh multifractions to obtain the result about the absolute magnitude of the nesting limit that I found by experiment, 1/sqrt(n). Only, in that case, the relevant sequence would not be the binary Thue-Morse sequence, it would be a generalization to base n. For instance, for the three-legged fractions Owen was wondering about directly, it'd be oeis.org/A053838 , which we might as well call the ternary Thue-Morse sequence:
0, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 2, 0, 1, 0, 1, 2, 2, 0, 1, 0, 1, 2, 1, 2, 0, 1, 2, 0, 2, 0, ...
Here, at each stage of the expansion you'd concatenate the sequence with two versions of itself, with the symbols incremented by one or two steps modulo 3. Or, alternatively, just replace every 0 with 0, 1, 2, every 1 with 1, 2, 0, and every 2 with 2, 0, 1. Or, it's the base-3 digit sums of the nonnegative integers modulo 3. And there's an analogous sequence for any n, many of which are linked from the OEIS page for the ternary version.
Why am I talking about this now? Why are fractals mentioned in the title of this post? See why in part 2!