A matrix that counts the returns

The orbit written as a word coded the doubling map by recording which half of the interval each step lands in. Every binary word turned out to be the itinerary of exactly one point, so the points that come back after $n$ doublings could be counted by counting words, and there are $2^n$ of them. The essay ended on a hint: forbid some pairs of letters, and the count of allowed words becomes the powers of a matrix.

That hint can be made exact on a real map, one that nobody would think of as a coding until it is drawn. The count it produces is not the number of words but the number of points that return, and the matrix delivers it as a trace.

A map drawn through a cycle #

Pick three points, 0, 1/3 and 1, and demand that the map carry each to the next: 0 to 1/3, 1/3 to 1, and 1 back to 0. Join those requirements with straight lines and the map is complete. On the left piece it is $x \mapsto 2x + 1/3$, rising from 1/3 to 1, and on the right piece it is $x \mapsto 3/2 - 3x/2$, falling from 1 back to 0.

The partition into $L = [0, 1/3]$ and $R = [1/3, 1]$ has a property that almost no partition has. Every piece is carried exactly across whole pieces. The left piece lands precisely on the right piece, not part of the way into it and not spilling over; the right piece lands precisely on the whole interval. That happens because the endpoints of the pieces are the points of the cycle, and the map carries cycle points to cycle points.

So the rule for which piece can follow which is fixed once and for all, and it is simple: an orbit in L must go next to R, and an orbit in R can go to either. As a graph, that is two nodes, an arrow from L to R, an arrow from R to L, and a loop at R. As a matrix, with a 1 wherever an arrow runs, it is

$$A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}.$$

A partition with this property is called a Markov partition. The doubling map’s halves are one, with every arrow present, which is why every binary word was allowed. This map forbids exactly one pair, L followed by L, and the whole of this essay is what that one prohibition does to the counts.

Words are walks on a graph #

An orbit’s itinerary is the sequence of pieces it visits, and every itinerary must follow the arrows. So the itineraries of $n$ steps are the walks of $n$ letters on the two-node graph, and counting them is counting walks.

Walks are what matrix powers count. The entry in row $i$ and column $j$ of $A^m$ is the number of walks of $m$ arrows from node $i$ to node $j$, because multiplying matrices adds up, over every intermediate node, the number of ways to get there times the number of ways to go on. The same bookkeeping drives the transition matrices of the rule that forgets where it came from, where the entries are probabilities rather than counts.

Adding up every entry of $A^{n-1}$ therefore counts the allowed words of $n$ letters, and those counts are 2, 3, 5, 8, 13, the Fibonacci numbers. They are also something visible: the number of straight pieces in the graph of $f^n$. On the set of points that follow one particular word, $f^n$ is a composition of straight maps and so is straight itself, and because each step carries a piece exactly across whole pieces, it stretches that small set across at least one whole piece of the interval.

A return is a closed walk #

A point that returns after $n$ steps is a point where the graph of $f^n$ crosses the diagonal, as the staircase that shows the whole orbit draws it. Which straight pieces of $f^n$ can cross? A piece belongs to a word, and it stretches the points following that word across the whole of the word’s last-reached piece. If the orbit is to come back, it must be able to start again where it began, so the word’s last letter must be allowed to lead to its first. The words that can return are exactly the closed walks.

Each closed word gives exactly one crossing. On its set of points, $f^n$ is a straight line whose slope is the product of the slopes along the word — every factor 2 or $-3/2$, so the product is steeper than 1 — and it takes every value in the piece where the word starts, because the word’s last letter may lead back to its first. A straight line defined on part of a piece, taking every value in that whole piece, and steeper than the diagonal, meets the diagonal exactly once.

The closed walks of $n$ arrows that start and end at node $i$ are counted by the diagonal entry of $A^n$ in row $i$, and all of them together by the sum of the diagonal, which is the trace:

$$\#\{x : f^n(x) = x\} = \operatorname{tr} A^n.$$

For four steps, $A^4$ has diagonal entries 2 and 5, and the graph of $f^4$ crosses its diagonal seven times. The crossings in the figure were not found by looking for them. Each was computed by composing the four straight maps a closed word names and solving the resulting linear equation in fractions, then walked forward four steps by the map itself to confirm it lands back where it started.

Every length, solved exactly #

The returns run 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, and at every length up to ten the exact count equals the trace. These are the Lucas numbers, the companions of the Fibonacci numbers counting the pieces: each is the sum of the two before it, and the Fibonacci and Lucas sequences are two solutions of one recurrence with different starting values.

The single return after one step is the fixed point 3/5, on the right piece, where $3/2 - 9/10 = 3/5$. The three returns after two steps are that fixed point again and the pair 1/4 and 5/6, which swap. The four returns after three steps are the fixed point and the cycle 0, 1/3, 1 the map was drawn through.

Points that return after $n$ steps include every point whose exact period divides $n$, so the count of orbits with period exactly $n$ needs the counts for the divisors taken away. That is the same inclusion and exclusion that necklaces that prove a theorem uses to count necklaces from strings. For six steps it is $(18 - 4 - 3 + 1)/6 = 2$ orbits. The table counts those orbits twice — once by walking every exact point until it returns, once by the formula over traces — and the two agree: 1, 1, 1, 1, 2, 2, 4, 5, 8 and 11 orbits of exact periods one to ten.

A cycle written down from its word #

The counting runs in the other direction too. Any closed word, read round and round, is an instruction for an orbit, and the instruction can be carried out.

Take LRLRR. It never puts L after L, even read round from its last letter to its first, so it is a closed walk. The five straight maps it names compose to a single line of slope $2 \cdot (-3/2) \cdot 2 \cdot (-3/2) \cdot (-3/2) = -27/2$, and solving where that line meets the diagonal gives 9/29. The orbit then runs 9/29, 83/87, 2/29, 41/87, 23/29 and back to 9/29, and each point sits in the piece the word says it should: left, right, left, right, right.

No search was involved and no approximation. The stretching is what makes it work. Because every step multiplies small differences by at least $3/2$, two different points cannot follow the same word for ever — any gap between them would grow past the width of a piece — so a word names at most one point, and the covering property guarantees it names at least one. That is the same fact that how fast two orbits part measures as sensitive dependence, turned into a method for locating orbits exactly.

The growth rate is an eigenvalue #

The table’s last column, the ratio of each trace to the one before, settles at 1.618. The reason is linear algebra. The trace of a matrix is the sum of its eigenvalues, and the eigenvalues of $A^n$ are the $n$-th powers of those of $A$. The eigenvalues of $A$ are the roots of its characteristic polynomial,

$$\det(\lambda I - A) = \lambda^2 - \lambda - 1,$$

which are $\varphi = (1 + \sqrt 5)/2$ and $-1/\varphi$. So

$$\operatorname{tr} A^n = \varphi^n + \left(-\tfrac{1}{\varphi}\right)^n,$$

and the second term shrinks towards zero while the first grows. The polynomial whose roots are the stretches is where that polynomial comes from, and the rectangle that eats itself is where $\varphi$ is met first, as the ratio that survives cutting a square off a rectangle.

The number of returns grows like $\varphi^n$, and so does the number of words. Its logarithm, $\log\varphi \approx 0.481$, is the map’s topological entropy, the growth rate the doubling map had at $\log 2$ and the forbidden pair has cut down. A nonnegative matrix some power of which has every entry positive always has a single largest eigenvalue, positive and strictly bigger than the others in size, with a positive eigenvector — the theorem of Perron and Frobenius — so this growth rate is always one clean number for maps like this one.

Every count in one fraction #

The returns after one step, two steps, three steps and so on are infinitely many numbers, and one expression holds all of them. Artin and Mazur proposed in 1965 packaging the counts of a map’s returning points into a single power series,

$$\zeta(t) = \exp\left(\sum_{n \ge 1} \frac{N_n}{n}\, t^n\right),$$

where $N_n$ is the number of points that return after $n$ steps. For a general map nothing guarantees that this series is anything tidy. For a map whose counts are traces, it always is. The logarithm of a determinant is the trace of a logarithm, and expanding $-\log(I - tA)$ as a power series gives exactly the traces of the powers of $A$ divided by $n$, so

$$\zeta(t) = \frac{1}{\det(I - tA)}.$$

Bowen and Lanford proved in 1970 that this makes the zeta function a ratio of polynomials for every system of this kind. For the map through $0 \to 1/3 \to 1$ the determinant is $(1)(1 - t) - t^2$, and

$$\zeta(t) = \frac{1}{1 - t - t^2} = 1 + t + 2t^2 + 3t^3 + 5t^4 + 8t^5 + \cdots.$$

The Lucas numbers go in and the Fibonacci numbers come out. The traces 1, 3, 4, 7, 11 sit inside the exponential; the coefficients of the fraction are 1, 1, 2, 3, 5, 8. The two sequences that ran side by side in the table — returns and pieces — are the two halves of one identity, and a single fraction with a quadratic in its denominator encodes the number of returning points at every length.

The fraction also shows where the growth rate comes from. The series stops converging when $t$ reaches the smallest root of $1 - t - t^2$, which is $1/\varphi$, and a power series whose radius of convergence is $1/\varphi$ has coefficients growing like $\varphi^n$.

A different cycle, a different matrix #

Nothing about the method depended on the cycle having three points.

Draw a map straight through the four-point cycle $0 \to 1/2 \to 1 \to 1/4 \to 0$ and the interval falls into three pieces, each again carried exactly across whole pieces. The graph now has three nodes, and its matrix has seven ones:

$$B = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{pmatrix}.$$

Its characteristic polynomial factors as $(1 - \lambda)\bigl((1 - \lambda)^2 - 2\bigr)$, so its eigenvalues are $1$ and $1 \pm \sqrt 2$, and the trace of $B^n$ is $1 + (1 + \sqrt 2)^n + (1 - \sqrt 2)^n$. The exact counts of returning points are 3, 7, 15, 35, 83 and 199, and each equals that formula. This map’s entropy is $\log(1 + \sqrt 2) \approx 0.881$, more than the three-cycle map’s, and its graph has more arrows for its size.

A different cycle gives a different graph and a different matrix, and the counting goes through unchanged. The only work is drawing the map and reading off which pieces cover which; matrices as grids is all the linear algebra the reading needs.

A cycle of three forces every period #

The three-node table has a row for every length, and none of its orbit counts is zero. That is no accident of the table’s range. For any $n \ge 2$, the word made of one L followed by $n - 1$ letters R is a closed walk that is not a shorter word repeated, so it names an orbit of exact period $n$; and the single letter R names the fixed point. The map has cycles of every period.

The same conclusion holds for any continuous map of an interval with a cycle of three, not just this straight-line one. Call the cycle’s points $a < b < c$, carried $a \to b \to c \to a$. The intermediate value theorem says the map carries $[a, b]$ over at least $[b, c]$ and carries $[b, c]$ over at least $[a, c]$, whatever it does in between — the covering pattern of the figure, now as a pattern of “at least”. A sequence of nested intervals following any closed walk then exists, and it contains a point that returns along that walk. The other orientation of the cycle, $a \to c \to b \to a$, gives the mirror image and the same graph.

Li and Yorke published this in 1975 under the title “Period three implies chaos”. Sharkovskii had already proved much more in 1964: the periods can be arranged in the order

$$3, 5, 7, \ldots,\ 2 \cdot 3, 2 \cdot 5, \ldots,\ 4 \cdot 3, 4 \cdot 5, \ldots,\ \ldots, 8, 4, 2, 1,$$

and a continuous interval map with a cycle of any period has cycles of every period later in the list. Three comes first, so it forces everything; the powers of two come last, which is why the road paved with doublings can pass through periods 1, 2, 4, 8 and so on without any other period appearing. What a cycle of three forces beyond periods — a lower bound on the entropy itself — is where the folds that measure chaos takes up the question.

Only maps built from stretching straight pieces #

Every map drawn is built from straight pieces through a cycle. That is what makes the partition exact and the arithmetic finite. A general map, the logistic map among them, has no partition with the covering property except at special parameters, and its returns cannot be read off a finite matrix.

Stretching was assumed, not drawn. The count of one point per closed word needs every piece to stretch; a map with a flat stretch or a slope of exactly one could have a whole interval following one word, and a closed word would then name infinitely many returning points or none. Both maps here were checked to have every slope steeper than 1.

And boundaries are handled, not illustrated. The cycle points sit on the edges of the pieces, where an itinerary could be read two ways. For these maps only one reading is ever an allowed walk, and the exact computation confirms that no point is counted twice; for a careless choice of partition that would fail, and the trace would overcount.

Still open: when two matrices describe the same system #

The words of a map with a Markov partition form a system determined entirely by its matrix, and two different matrices can give systems that are the same after a relabelling of words. Williams showed in 1973 that this happens exactly when the matrices are related by a chain of elementary factorisations, $A = RS$ and $B = SR$, called strong shift equivalence, and conjectured that a weaker, algebraically checkable relation would do. Kim and Roush disproved that conjecture in 1999. Whether strong shift equivalence can be decided at all — whether there is any procedure that takes two matrices and says, in finite time, whether their systems are the same — is still not known, and particular pairs of two-by-two matrices remain unresolved.

Counting returns without solving anything #

The maps here were built to be counted. Once their pieces are drawn, the rule for which piece follows which is a graph, the orbits are walks, the returns are closed walks, and a single matrix power delivers the number of points that come back after any number of steps. Every one of those numbers was also found the hard way, by solving for the points in fractions, and none disagreed.

When a system’s states can be cut into pieces that map exactly onto whole pieces, count paths instead of solutions. The trace does the counting, the largest eigenvalue gives the growth, and a cycle of three is enough to guarantee there is something to count at every length.