Fractions, fractals and Thue-Morse sequences, part 1

This 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:

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-Morse

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!

Fractions, fractals and Thue-Morse sequences, part 2

 In part 1 of this series of indeterminate length, I mentioned the Thue-Morse sequence, a certain sequence of zeros and ones, and the counterparts of it for more than two symbols. When I was messing around with Thue-Morse I came across a webpage by Zachary Abel that mentioned something remarkable about them: interpreting them as a turtle-graphics program gives you a thing that somehow converges to the Koch snowflake curve, the archetypical simple fractal. (Abel defines the Thue-Morse sequence as the complement of the way most other people define it, starting with 1 instead of 0, but for this purpose it hardly matters.) This paper by Jun Ma and Judy Holdener proves in some detail that this does in fact converge to the Koch snowflake:

This isn't the textbook way that you usually draw the Koch snowflake with turtle graphics; it's simpler. You don't even need a "right turn" rule. You don't need recursion (except inasmuch as recursion is built into the Thue-Morse sequence, which you could argue it is). You just have the turtle follow the sequence, and turn left 60 degrees when it has a 0, and move forward one unit if it has a 1. The turtle at first seems to be crawling around in drunken squiggles, but if you just let it go, the overall shape of those squiggles turns out to be the Koch snowflake.

And, actually, that's not even the only way to do it. It also works if you interpret the bits the other way around. Or if you tell it to turn 120 degrees instead of 60--the fine details of the path are different but it still converges to the snowflake. Or if you give it a bunch of other ways of interpreting the Thue-Morse sequence as turtle instructions. Abel's page explores all sorts of different cases that work.

Not every interpretation works. If you just put in an arbitrary number for the turn angle, most of them seem to just give a mess. Sometimes, that mess starts to resolve into a directional path on a very large scale and it's possible that you still get the Koch snowflake again, but I haven't been patient enough to tell. Maybe you get something else entirely! Here's 70 degrees:

On the other hand, some you wouldn't think work, do. 75 degrees is sort of a punk rock snowflake:



Sometimes symmetries get you. When I first tried this, it didn't work because I was using the same sequence interpretation I use for the Heighway dragon curve: move forward every time, and turn left if you have a 1 and right if you have a 0. That fails because of the symmetries of the Thue-Morse sequence: every four symbols, the turtle ends up moving in its original direction, and you just get a long line with aperiodic wobbles in it, not very interesting. That's true no matter what turn angle you try.

But if you tweak the rule a little to break the symmetry, so that it turns, say, 120 degrees left for a 1 but only 60 degrees right for a 0... then you get the Koch snowflake again. Only the small-scale squiggles are different.

The Ma and Holdener paper proves that this is indeed the Koch curve for the first rule I mentioned, and for the complementary case where the symbols are interpreted the other way around, and they speculate that there are many other related sequences that have the same property. Kennard, Zaremsky and Holdener then found a whole family of these sequences.

But I don't think there's been a comprehensive study of what happens when you change the turtle interpretation of the series, as Abel did and as I'm doing here. I suspect that in many cases, changing the turtle rule is equivalent on a larger scale to modifying the series instead, in some way that keeps it consistent with Ma and Holdener's conditions.


But there's more...