Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 16 / 1

A fixed point of the left shift satisfies $x_{k+1}=x_k$ for every $k\in \mathbb{Z}$, so its entire two-sided sequence is constant. The constant sequence with value $i$ belongs to the subshift of finite type precisely when $A_{ii}=1$: this is exactly the requirement that its repeated transition be allowed by the symbolic transition matrix. There is one such fixed point for each diagonal entry equal to one. ThusThis also covers an empty subshift of finite type, for then no permitted constant sequence exists.

Write $W_n(i,j)$ for the number of locally admissible words $(x_0,\dots ,x_n)$ with $x_0=i$ and $x_n=j$. Here local admissibility means $A_{x_r{x}_{r+1}}=1$ for each consecutive pair; length counts symbols, so there are $n$ transitions. For $n=0$, the single-symbol word gives $W_0(i,j)={\delta }_{ij}=(A^0{)}_{ij}$, and for $n=1$ we have $W_1(i,j)=A_{ij}$.

To append the last symbol $j$, choose the penultimate symbol $k$. Every choice gives a locally admissible word exactly when its length-$n$ prefix is locally admissible and $A_{kj}=1$. Different prefixes or penultimate symbols give different words, and every admissible word is obtained once. ThereforeThis is precisely the rule for matrix multiplication. Mathematical induction consequently givesEquivalently, expanding the matrix entry sums the products $A_{i{x}_1}{A}_{x_1{x}_2}\cdots A_{x_{n-1}j}$ over all intermediate symbols; each product is the indicator function of one allowed transition chain.

The intended meaning of “allowed” here is local admissibility. If instead it means a word that actually occurs in some two-sided sequence in ${\Sigma }_A$, the assertion needs an additional extension assumption. For example, $A=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ permits the word $(1,2)$ and has $(A{)}_{12}=1$, but ${\Sigma }_A$ is empty because no symbol can continue after $2$. Having a nonzero entry in every row and every column is sufficient: one can successively choose a predecessor and a successor to extend every locally admissible word indefinitely in both directions. No such assumption is needed for the local counting formula.

The equation ${\sigma }^{n}x=x$ says $x_{r+n}=x_r$ for every $r\in \mathbb{Z}$. Thus a solution is determined uniquely by the block $(x_0,\dots ,x_{n-1})$, repeated in both directions. It belongs to the subshift of finite type exactly when all transitions inside the block, and the closing transition from $x_{n-1}$ to $x_0$, are allowed. Hence these fixed points of the $n$th iteration of a map are in bijection with the closed transition chains of $n$ steps with a specified symbol at time zero. By the counting argument in part (b), the number starting at $i$ is $(A^n{)}_{ii}$. Summing over $i$ proves the trace formula for periodic points of a subshift:Every closed transition chain extends by periodic repetition, so the extension issue in part (b) does not affect this formula. We count points, not periodic orbits: a least-period-$d$ periodic orbit contributes its $d$ distinct points.

Here period $n$ means fixed by ${\sigma }^n$, so the least period may divide $n$. If $P_d$ denotes the number of points of least period exactly $d$, division with remainder shows that a point is fixed by ${\sigma }^n$ exactly when its least period divides $n$. Consequentlywhere ${\mu }_{\mathrm{M}}$ is the Möbius function and the second equality is Möbius inversion. For example, $A=(1)$ has one point fixed by every power but no point of least period two; interpreting the printed formula as an exact-period count would therefore be false.