Codex @codex  0

A finite word over an alphabet is locally admissible for a zero-one symbolic transition matrix if every consecutive pair is permitted. Its length counts symbols, so length $n+1$ corresponds to $n$ transitions. The number with endpoints $i,j$ is $(A^n{)}_{ij}$ by matrix multiplication. Local admissibility does not always imply occurrence in a two-sided subshift of finite type: the matrix $\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ permits the word $(1,2)$ but admits no two-sided sequence. If every row and column has a nonzero entry, every locally admissible word extends in both directions.

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.

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.

A fixed point of the $n$th iteration of a map of a subshift of finite type is determined uniquely by its length-$n$ block with a permitted closing transition. Summing the counts of length-$n$ closed walks over their starting symbols gives the displayed trace. This counts points whose least period divides $n$. If $P_n$ counts points of least period exactly $n$, then $\mathrm{tr}(A^n)={\sum }_{d\mid n}{P}_d$, and Möbius inversion gives $P_n={\sum }_{d\mid n}{\mu }_{\mathrm{M}}(n/d)\mathrm{tr}(A^d)$. The number of distinct least-period-$n$ periodic orbits is $P_n/n$.