Windows counted like necklaces

Every window is the whole diagram again showed that each periodic window of the logistic map holds a small copy of the entire bifurcation diagram, which in turn holds copies of every window. That makes the windows dense and self-similar. It does not say how many there are.

The question has a precise form. Each window is centred on a superstable parameter, a value of $r$ at which the top of the hump, $x = \tfrac12$, lies on the window’s periodic orbit — the parameter at which the orbit is most strongly attracting. For each period $n$ there are finitely many such parameters, because they are roots of a polynomial in $r$. How many?

For the logistic map the answer, found by searching every parameter from $1.9$ to $4$ for roots of exact period, is $1, 1, 1, 2, 3, 5, 9, 16, 28$ for periods one to nine. For the sine map $r \sin(\pi x)$, whose formula has nothing in common with the logistic map’s except a single smooth hump, the same search gives the same numbers. And both columns agree with a formula that has nothing to do with dynamics at all:

$$W(n) = \frac{1}{2n} \sum_{\substack{d \mid n \\ d \text{ odd}}} \mu(d)\, 2^{n/d},$$

which counts necklaces — rings of $n$ beads, each bead one of two colours, that no rotation carries onto themselves, with a necklace and its colour-reversal counted as one.

Where the windows are found #

A superstable parameter of period $n$ is a root of

$$g_n(r) = f_r^n\!\left(\tfrac12\right) - \tfrac12,$$

the critical point’s $n$-th iterate minus the critical point. The function $g_n$ is a polynomial in $r$ of degree $2^n - 1$, and its roots include the superstable parameters of every period dividing $n$ — a point that comes back in two steps also comes back in six — so the roots of exact period $n$ are those that are not roots of any $g_d$ with $d$ a proper divisor.

The figure draws $g_6$. Its zeros between $3.4$ and $4$ are six: five of exact period six and one of period three, the superstable centre of the period-three window at $3.83187$, since a point with period three also has period six. The curve’s swings crowd together near $r = 4$, where the map stretches hardest, and most of the period-six windows are packed into the last few hundredths of the parameter range — which is why a bifurcation diagram shows only the widest of them.

Finding the roots is a matter of sampling $g_n$ finely enough to catch every sign change and refining each by halving the interval. The fineness needed grows with $n$, because the windows of high period are thin; for period nine the search samples two million parameters and finds twenty-eight roots of exact period, on each map, and those counts are what the table’s first two columns report.

Five windows of period six, in order #

The five period-six windows are not all the same kind, and the difference is visible in how they are born.

One of them is the doubling of the period-three window: inside that window’s cascade, the cycle of three forks into a cycle of six, and the superstable parameter of the six-cycle, $3.84457$, lies in the window’s own copy of the diagram. There is only one window of period three to double, so the other four period-six windows are new: each opens with its own tangent collision, the way the window that opens with a stutter opened, somewhere in the chaos. So the count of five includes one inherited window and four primitive ones, and in general $W(n)$ counts every superstable parameter of period $n$, whether it is the doubling of a smaller window or a window of its own.

The distinction matters for what the numbers mean, and it does not change them: the formula counts both kinds, the search finds both kinds, and a count of windows born new would subtract the doublings, $W(n) - W(n/2)$ when $n$ is even.

Most windows are new #

Subtracting the doublings separates the two kinds of window, and the subtraction is revealing. A window of period $n$ born by doubling is the doubling of a window of period $n/2$, one for each, so the number of windows born new at period $n$ is $W(n) - W(n/2)$ for even $n$ and $W(n)$ for odd $n$. From period one to ten that gives

$$1,\ 0,\ 1,\ 1,\ 3,\ 4,\ 9,\ 14,\ 28,\ 48.$$

Period two has no window of its own: its only superstable parameter, $1 + \sqrt 5$, is the first doubling of the fixed point. Period four has one new window beside the one inherited from period two, and it is far up in the chaotic range, at about $3.9603$, the window the stutter at its edge cannot be seen at by eye. After that the new windows outnumber the inherited ones overwhelmingly, since $W(n/2)$ is roughly the square root of $W(n)$: almost every window is born new, with its own tangent collision, and the cascades of doubling that fill the eye in a picture of the diagram account for a vanishing share of the count.

The same order on every hump #

The two maps agree on more than the counts.

List every window of period at most six in the order it appears as the parameter rises, and read off the periods. For the logistic map the sequence is

$$1,\ 2,\ 4,\ 6,\ 5,\ 3,\ 6,\ 5,\ 6,\ 4,\ 6,\ 5,\ 6.$$

For the sine map it is the same sequence. Nicholas Metropolis, Myron Stein and Paul Stein found in 1973 that this holds for every map of the interval with a single smooth hump whose height rises steadily with the parameter: the windows come in one universal order, and a list of periods read off one such map is the list for all of them. They named it the U-sequence, for universal, and it predates Feigenbaum’s constant by five years — the first sign that one-humped maps share far more than their shape.

The reason is that a window is identified not by its parameter but by its itinerary: the sequence of lefts and rights of $\tfrac12$ that the critical point visits on its way round the cycle. The period-three window’s itinerary is right, left, then back to the centre; the period-five windows’ itineraries are three different words of that kind. The order of the windows along the parameter is an order on these words — a lexicographic order with a twist, reversed after every right, since the map is decreasing right of the hump — and that order depends only on the words, not on the formula for the map. The folds that measure chaos used the same words to count the laps of iterated maps; here they label the windows and sort them.

Why necklaces #

The necklace formula can be understood from the itineraries, and the argument is a close relative of the one necklaces that prove a theorem used for Fermat’s little theorem.

An itinerary of a period-$n$ window is a word of $n - 1$ letters, each left or right, followed by the centre. Not every word occurs. A word is admissible exactly when it is the largest of its own shifts in the twisted order — a condition which says that the critical point, which goes highest, must stay highest in every rotation of its own itinerary. That is the same kind of condition that picks one representative out of each necklace class: among the rotations of a word, keep the one that is largest. So admissible itineraries correspond to necklace classes, and the question becomes how many classes there are of words that no rotation fixes.

The twist is what brings in colour-reversal and odd divisors. Passing the hump reverses the order, so the natural objects are words up to a reversal of colours, and in the inclusion–exclusion that removes words fixed by a rotation, the rotations whose order interacts badly with the reversal drop out — which is why only odd divisors appear. The count is a sum over odd divisors because the map turns the interval over, and the halving in $\frac{1}{2n}$ is a necklace identified with its colour-swap. The precise bookkeeping, which Milnor and Thurston’s theory of kneading supplies, is longer than the idea, and the figure checks the result rather than the argument: it lists every word of length up to fourteen, groups them by rotation and colour-swap, and counts the classes no rotation fixes, and the census and the formula agree at every length.

The same numbers from a finite field #

The necklace formula has a second life far from dynamics, and the table’s last column records it.

A polynomial with coefficients $0$ and $1$, where $1 + 1 \equiv 0$, is irreducible if it does not factor into polynomials of lower degree. The irreducible polynomials of degree $n$ build the field with $2^n$ elements, as the field with four elements is built from $x^2 + x + 1$, and counting them is a classical necklace count: each has $n$ roots that the squaring map cycles round like beads on a ring, and every necklace in order lists the aperiodic words the count is really about. The sum of an irreducible polynomial’s roots — its coefficient of $x^{n-1}$ — is either $0$ or $1$, and the polynomials whose roots add to $1$ are counted by exactly $W(n)$. The table finds them by trial division, every polynomial of each degree up to twelve divided by every candidate factor, and the column agrees with the windows and the necklaces at every entry.

The shared count has a shared reason. The squaring map on a field of characteristic two and the doubling map at the heart of the logistic map at $r = 4$ are the same combinatorial object, a shift on binary words, and in both settings a periodic point of period $n$ is a word of length $n$ that no rotation fixes. The windows of the logistic family, the irreducible polynomials of trace one, and the necklaces up to colour-swap are three readings of one count of words.

Where each period first appears #

The U-sequence also records something older than itself: the order in which periods first appear.

Reading the sequence from the left and noting each period the first time it occurs gives $1, 2, 4, 6, 5, 3$. Period three is the last to arrive; after the period-three window, every period has already appeared somewhere to its left. That is Sharkovskii’s order, found by Oleksandr Sharkovskii in 1964 for continuous maps of the interval: list the whole numbers as

$$3 \succ 5 \succ 7 \succ \cdots \succ 2 \cdot 3 \succ 2 \cdot 5 \succ \cdots \succ 4 \cdot 3 \succ \cdots \succ 8 \succ 4 \succ 2 \succ 1,$$

odd numbers first, then twice the odd numbers, then four times them, and finally the powers of two in decreasing order; a continuous map with a cycle of some period has cycles of every period further along the list. The windows of the logistic map are born in the reverse of that order — powers of two first, in the cascade, then the doubles of odd numbers, and the odd numbers last, three at the very end — and John Milnor and William Thurston proved in 1977 that this is forced, because the complexity of the logistic map, measured by its topological entropy, only increases with $r$. Sharkovskii’s abstract order is the order in which a real family creates its cycles, and the period-three window is where the family has created them all.

Every window of small period, placed #

Placed on the diagram, the windows of period at most seven show two things the counts do not. They are concentrated towards the top of the parameter range, where the map’s stretching is greatest and the windows are narrowest; and they are unevenly spaced, with the period-three window standing alone in a wide gap. Beyond period seven the marks would thicken into a band, and between any two of them there would be windows of higher period — the density the whole diagram again explained by self-similarity, arriving here as a count.

The three period-five windows sit at $3.7389$, $3.9057$ and $3.9903$ — the first the widest, the third squeezed into the last hundredth. The second and third are invisible in any ordinary picture of the diagram, and they are as much windows as the first: each has its own copy of the whole diagram, its own cascade and its own crisis, scaled down by a factor that grows with how close to $4$ it sits.

Real windows among complex ones #

The polynomial $g_n$ has degree $2^n - 1$ and most of its roots are not real. Allowing $r$, or equivalently the parameter of the complex quadratic family, to be complex, the parameters at which the critical point has exact period $n$ are the centres of the components of the Mandelbrot set’s interior, one per bulb, and they number $1, 1, 3, 6, 15, 27, 63, 120, 252, 495$ for periods one to ten.

Of the $495$ centres of period ten, $51$ are real. The real ones are the windows of the logistic map; the rest are bulbs off the real axis, with no real counterpart. As $n$ grows, the complex count behaves like $2^{n-1}$ and the real count like $2^{n-1}/n$, so the fraction of centres on the real line falls like $1/n$ — thinning, but never to nothing, and every one of them is a window with a copy of the whole diagram inside it.

What the searches establish #

The counts are found up to period nine and trusted beyond. For each period the searches sample the parameter range finely and refine every sign change; a root in a window narrower than the sampling step would be missed, and the evidence that none was is that both maps’ counts agree with the formula at every period checked. Beyond nine the table gives the formula alone.

The order is checked up to period six. The two maps’ sequences agree entry for entry there, which is thirteen windows; the theorem of Metropolis, Stein and Stein, and Milnor and Thurston’s kneading theory behind it, is what extends the agreement to every period and every hump.

The necklace correspondence is explained, not constructed. The census confirms that the formula counts necklaces; it does not build the bijection between windows and necklaces, which goes through the itineraries and the twisted order and is described above in outline.

Still open: whether the complex windows are dense #

For real parameters the windows are dense: Jacek Graczyk and Grzegorz Świątek, and independently Mikhail Lyubich, proved in 1997 that every interval of real parameters contains a window. That settled for the logistic family a question Pierre Fatou had asked in the 1920s: whether maps with an attracting cycle are dense among all maps of the family.

For complex parameters the question is open. Is every point on the boundary of the Mandelbrot set a limit of bulb centres — that is, are the complex windows dense in the set? It is known to follow from the conjecture that the Mandelbrot set is locally connected, which has been proved at many boundary points and not at all of them, and both questions remain open after decades of work. The real line, where the windows can be counted and ordered and matched with necklaces, is the one slice of the family where the answer is known.

A count that does not depend on the map #

The habit worth keeping is the replacement of parameters by words.

The windows of the logistic map sit at irrational parameters with no closed form, and their widths shrink in ways only computation describes. But each window carries a word — the itinerary of the critical point round its cycle — and the words obey rules that know nothing about the formula for the map. Counting windows is counting admissible words, the admissible words are necklaces up to a twist, and the order of the windows along the parameter is an order on words. That is why a different hump, with a different formula, has the same windows in the same order: the parameters differ, and the words, which are what the windows are, do not.