The last four post have looked at the bifurcation diagram for the logistic map.
There was one post on the leftmost region, where there is no branching. Then two posts on the region in the middle where there is period doubling. Then a post about the chaotic region in the end.
This post returns the middle region. Here’s an image zooming in on the first three forks.
The nth region in the period doubling region has period 2n.
I believe, based on empirical results, that in each branching region, the branches are visited in the same order. For example, in the region containing r = 3.5 there are four branches. If we number these from bottom to top, starting with for the lowest branch, I believe a point on branch 0 will go to a point on branch 2, then branch 1, then branch 3. In summary, the cycle order is [0, 2, 1, 3].
Here are the cycle orders for the next three regions.
[0, 4, 6, 2, 1, 5, 3, 7]
[0, 8, 12, 4, 6, 14, 10, 2, 1, 9, 13, 5, 3, 11, 7, 15]
[0, 16, 24, 8, 12, 28, 20, 4, 6, 22, 30, 14, 10, 26, 18, 2, 1, 17, 25, 9, 13, 29, 21, 5, 3, 19, 27, 11, 7, 23, 15, 31]
[0, 32, 48, 16, 24, 56, 40, 8, 12, 44, 60, 28, 20, 52, 36, 4, 6, 38, 54, 22, 30, 62, 46, 14, 10, 42, 58, 26, 18, 50, 34, 2, 1, 33, 49, 17, 25, 57, 41, 9, 13, 45, 61, 29, 21, 53, 37, 5, 3, 35, 51, 19, 27, 59, 43, 11, 7, 39, 55, 23, 15, 47, 31, 63]
Two questions:
- Is the cycle order constant within a region of a constant period?
- If so, what can be said about the order in general?
I did a little searching into these questions, and one source said there are no known results along these lines. That may or may not be true, but it suggests these are not common questions.
By inspection, it appears that when there’s a period doubling from n branches to 2n branches:
* The first n/2 entries of the new list are the first n/2 entries of the old list, doubled. [0, 4, 6, 2] -> [0, 8, 12, 4].
* The next n/2 entries are some kind of zig-zag transpose of the last n/2 entries of the old list, doubled. [1, 5, 3, 7] -> [6, 14, 10, 2].
* The next n/2 entries are the first n/2 entries of the old list, doubled plus one. [0, 4, 6, 2] -> [1, 9, 13, 5].
* Finally, the last n/2 entries of the new list are the last n/2 entries of the old list, doubled plus one. [1, 5, 3, 7] -> [3, 11, 7, 15].
I haven’t quite figured out where the ordering of the “second quarter” comes from, but the other 3/4 follow neatly for all of the iterations you listed.
You can of course coalesce the third and fourth rules into one: the second half of the new list is the old list, doubled plus one. Which means that the old cycle becomes all of the “upper branches” of the new cycle, all of which are visited after all of the lower branches, given that we start on 0.
The cycle order is constant within each region. Suppose the points in a given region are x_1(t) .. x_n(t), and for some t we have f_t(x_i(t)) = x_{a_i}(t). By continuity, for u close enough to t we have x_i(u) close to x_i(t), x_{a_i}(u) close to x_{a_i}(t), and f_t(…) close to f_u(…), and the various x_j are separated from one another by nonzero distances. So when u is close enough to t, f(x_i(u)) can’t be any x_j(u) other than x_{a_i}(u).
At a bifurcation each i turns into two; if we number from 0 in binary we can say that i becomes i0 and i1; then similar continuity considerations say that if i->j before the bifurcation then either i0,i1 -> j0,j1 or i0,i1 -> j1,j0 after the bifurcation. I bet Andrew’s summary is correct and I bet it isn’t actually super-difficult to (1) fill in the details and (2) prove it, but I am too lazy to try to do either now :-).
There’s been a huge amount of work on maps from the unit interval to itself, and the logistic map, and period doubling. I have by my bed a nice book called Chaos on the Interval, by Sylvie Ruette, and now I see it’s free on the arXiv:
https://arxiv.org/abs/1504.03001
So, if your question isn’t already solved, it sounds like a great open question!
There’s a pattern that becomes clearer if you consider the sequence that gives the index of the i-th branch in the order (with zero-indexing): i.e. [s.index(i) for i in range(len(s))] produces [0, 2, 3, 1] from the original [0, 2, 1, 3].
If we say that at stage n there are 2^n branches, then at stage m >= n the branch numbered 2^(m-n+1)k has the same index in the order as branch 2k at stage n for any integer k (e.g. the 2nd branch at stage 3, 6th branch at stage 4, 12th branch at stage 5, etc. are all 3rd in the order.)
Notably, this seems not to be true for the corresponding odd-numbered branch k at stage n-1 (with the exception of the 0th branch at stage zero and the 1st branch at stage 1).
Alright, I think I’ve cracked it.
Let n be the region with 2^n branches, and a[n][i] the index of the i-th branch in region n’s cycle order, e.g. a[3][:] = [0, 2, 3, 1] (see previous comment). Then the following recurrence relations empirically hold:
a[n+1][4k] = a[n][2k]
a[n+1][4k+2] = a[n][2k – 1 mod 2^n] (this right shift tripped everyone up)
a[n+1][2k+1] = a[n][k] + 2^n
The next region’s sequence should therefore be [0, 64, 63, 96, 31, 95, 32, 112, 15, 79, 48, 111, 16, 80, 47, 120, 7, 71, 56, 103, 24, 88, 39, 119, 8, 72, 55, 104, 23, 87, 40, 124, 3, 67, 60, 99, 28, 92, 35, 115, 12, 76, 51, 108, 19, 83, 44, 123, 4, 68, 59, 100, 27, 91, 36, 116, 11, 75, 52, 107, 20, 84, 43, 126, 1, 65, 62, 97, 30, 94, 33, 113, 14, 78, 49, 110, 17, 81, 46, 121, 6, 70, 57, 102, 25, 89, 38, 118, 9, 73, 54, 105, 22, 86, 41, 125, 2, 66, 61, 98, 29, 93, 34, 114, 13, 77, 50, 109, 18, 82, 45, 122, 5, 69, 58, 101, 26, 90, 37, 117, 10, 74, 53, 106, 21, 85, 42, 127],
i.e. the cycle order is [0, 64, 96, 32, 48, 112, 80, 16, 24, 88, 120, 56, 40, 104, 72, 8, 12, 76, 108, 44, 60, 124, 92, 28, 20, 84, 116, 52, 36, 100, 68, 4, 6, 70, 102, 38, 54, 118, 86, 22, 30, 94, 126, 62, 46, 110, 78, 14, 10, 74, 106, 42, 58, 122, 90, 26, 18, 82, 114, 50, 34, 98, 66, 2, 1, 65, 97, 33, 49, 113, 81, 17, 25, 89, 121, 57, 41, 105, 73, 9, 13, 77, 109, 45, 61, 125, 93, 29, 21, 85, 117, 53, 37, 101, 69, 5, 3, 67, 99, 35, 51, 115, 83, 19, 27, 91, 123, 59, 43, 107, 75, 11, 7, 71, 103, 39, 55, 119, 87, 23, 15, 79, 111, 47, 31, 95, 63, 127]
Now all that’s left is to prove why this is true.
(Minor typo above, it should be a[2][:] in the second paragraph, obviously.)