Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 16 (Dynamical Systems)

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.

The convention intended by this question is existence of a dense forward orbit, also called point transitivity. On a nonempty compact metric space, this means that some $x\in X$ satisfiesEquivalently, that forward orbit visits every nonempty open set.

The other common definition of topological transitivity uses intersections of iterated open sets, as in part (b). The distinction matters on spaces with isolated points: parts (b) and (c) ask precisely how the two conventions are related. We use point transitivity for the dense-orbit convention throughout this solution. As usual for this definition, the state space is assumed nonempty; on an empty space the open-set condition is vacuous and there is no point with a forward orbit.

A compact metric space is second countable. To see this concretely, for each positive integer $r$ choose a finite cover by balls of radius $1/r$. Their centres, over all $r$, form a countable dense subset; balls centred there with positive rational radii form a countable basis of a topology. Enumerate its nonempty members as $(V_j{)}_{j\ge 1}$, repeating members if the basis is finite.

For each $j$, putEach $G_j$ is an open set, because all iterations of a map $f^n$ are continuous. It is dense: if $U$ is any nonempty open set, the hypothesis supplies $n\ge 1$ and $u\in U$ with $f^n(u)\in V_j$, so $u\in U\cap G_j$.

A compact metric space is a complete metric space, hence a Baire space. The Baire category theorem implies that $G={\bigcap }_{j\ge 1}{G}_j$ is dense, and in particular nonempty. For any $x\in G$, the forward orbit of $x$ meets every $V_j$, and therefore every nonempty open set. Its orbit closure is $X$. Thus the open-set intersection hypothesis implies point transitivity, and in fact the set of points with a dense forward orbit contains the dense intersection $G$.

Let $x$ have a dense forward orbit $O=\{f^j(x):j\ge 0\}$, and suppose that $f$ is surjective. Every tail $O_k=\{f^j(x):j\ge k\}$ is then dense. Indeed, continuity givesand the left side equals $f^k(X)=X$ by surjectivity.

Given nonempty open sets $U,V$, choose $k\ge 0$ with $f^k(x)\in U$. The dense tail $O_{k+1}$ supplies $j\ge k+1$ with $f^j(x)\in V$. Taking $n=j-k\ge 1$ gives $f^j(x)\in f^n(U)\cap V$. This proves the required positive-time intersection property.

The result can fail without surjectivity. Take the compact metric spacewith the metric induced from the real line. All nonzero points are isolated, so continuity there is automatic; at zero, $f(1/j)\to 0=f(0)$ proves continuity. The forward orbit of $1$ is $\{1,1/2,1/3,\dots \}$, whose closure is $X$, so this is point transitivity. But $f(X)=X\setminus \{1\}$. The singletons $U=\{1/2\}$ and $V=\{1\}$ are nonempty open sets, and for every $n\ge 1$,The isolated initial point can be visited only at the start of the dense forward orbit; deleting that initial segment destroys density.

Use the separated-set definition of topological entropy. For a compatible metric $d$ and $n\ge 1$, define the Bowen metric and separated-set count byFor fixed $n$, the metric $d_n$ generates the original topology: it includes the $k=0$ term and all finitely many iterations of a map are continuous. Thus its space is compact and $s_n(d,ϵ)$ is finite. With natural logarithms, setThe last limit exists, possibly with value infinity, because decreasing $ϵ$ can only increase separated-set counts.

Let $d^{\prime }$ be another compatible metric. The identity $(X,d)\to (X,d^{\prime })$ is a continuous function on a compact domain, hence uniformly continuous. For every $ϵ>0$, choose $\delta >0$ such that $d(x,y)<\delta$ implies $d^{\prime }(x,y)<ϵ$. The same implication at every iterate givesBy its contrapositive, every $ϵ$-separated set for $d_n^{\prime }$ is $\delta$-separated for $d_n$. Consequently $s_n(d^{\prime },ϵ)\le s_n(d,\delta )$ for every $n$, andTaking $ϵ\downarrow 0$ gives $h_{d^{\prime }}(f)\le h_d(f)$. Interchanging the two compatible metrics gives the reverse inequality. ThereforeCompactness is used for uniform continuity, not merely for pointwise equivalence of the two metrics.

Let $H:X\to Y$ be a homeomorphism with $H\circ f=g\circ H$. This is topological conjugacy. Choose a compatible metric $e$ on $Y$ and pull it back to $X$:Because $H$ is a homeomorphism, $d_H$ is a compatible metric. The conjugacy identity implies $H{f}^k=g^{k}H$ for every $k\ge 0$, so the corresponding Bowen metrics satisfyThe bijection $H$ therefore transports separated sets in either direction without changing their separation, and $s_n(d_H,ϵ)=s_n(e,ϵ)$. Their exponential growth rates, and then their limits as $ϵ\downarrow 0$, agree. Part (a) lets us replace $d_H$ by any compatible metric on $X$. Hence

Write the hyperbolic toral automorphism as $T_A([v])=[Av]$ on ${\mathbb{T}}^2={\mathbb{R}}^2/{\mathbb{Z}}^2$, where $A\in \mathrm{GL}(2,\mathbb{Z})$. Its determinant is $\pm 1$. The eigenvalues cannot be a nonreal conjugate pair: their product would have absolute value one, forcing each to have absolute value one, contrary to hyperbolicity. The same product condition and hyperbolicity imply two distinct real eigenvalues, labelled so thatWe will proveThis is the entropy of a hyperbolic toral automorphism; the absolute value is important when the expanding eigenvalue is negative.

Choose real eigenvectors $v_s,v_u$ and the adapted norm $\Vert a{v}_s+b{v}_u{\Vert }_{\ast }=\max (|a|,|b|)$. Its quotient metric on the torus isIt is a compatible metric, so part (a) allows its use. Let $\rho ={\min }_{0\ne \ell \in {\mathbb{Z}}^2}\Vert \ell {\Vert }_{\ast }>0$ and $D=\Vert A{\Vert }_{\ast }=|{\lambda }_u|$. Fix $ϵ>0$ small enough that $2ϵ<\rho$ and $(D+1)ϵ<\rho$.

If $[v]$ lies in the Bowen ball $B_n(0,ϵ)$, each $T_A^k[v]$ has a unique lift $z_k$ with $\Vert z_k{\Vert }_{\ast }<ϵ$. Uniqueness follows because two such lifts differ by a lattice vector of norm less than $2ϵ<\rho$. Moreover, $z_{k+1}-A{z}_k$ is a lattice vector, andIt must be zero. Thus $z_k=A^k{z}_0$: there is no hidden lattice jump between successive lifted iterates.

Write $z_0=a{v}_s+b{v}_u$. The simultaneous bounds $\Vert A^k{z}_0{\Vert }_{\ast }<ϵ$ for $0\le k<n$ are exactlyThe stable coordinate is largest at time zero and the unstable coordinate at time $n-1$. Conversely, every vector in this rectangle satisfies all the Bowen ball bounds. The quotient is injective on this rectangle by $2ϵ<\rho$. If $J=|\det (v_s,v_u)|$, its normalized Haar measure is thereforeThe quotient metric is translation invariant and $T_A$ is linear, so $d_n(x,y)=d_n(0,y-x)$; every Bowen ball has this same measure, independently of its centre.

Take an $ϵ$-separated set of largest cardinality $s_n(d,ϵ)$. It is maximal under inclusion, so its radius-$ϵ$ Bowen balls cover the torus: a point outside all these balls could be added. The covering bound givesIts radius-$ϵ/2$ Bowen balls are disjoint, by the triangle inequality for $d_n$. Their measures sum to at most one, givingTaking logarithms, dividing by $n$, and letting $n\to \infty$ yields $h_d(T_A,ϵ)=\log |{\lambda }_u|$ for every sufficiently small $ϵ$. The limit as $ϵ\downarrow 0$ proves the answer. Contraction in the stable direction contributes no exponential growth; only expansion in the unstable direction does.

Let $(X,\mathcal{B},\mu )$ be a probability space, let $T$ be a measure-preserving transformation, and let $g\in L^1(\mu )$. The Birkhoff ergodic theorem asserts thatfor almost every $x$, where $\mathcal{I}=\{B\in \mathcal{B}:\mu (T^{-1}B△B)=0\}$ is the invariant sigma-algebra. The limit is integrable, satisfies $g^{\ast }\circ T=g^{\ast }$ almost everywhere, and has $\int g^{\ast }d\mu =\int gd\mu$. On a probability space the convergence also holds in $L^1$. No invertibility of $T$ is required.

If $T$ is ergodic, its invariant sigma-algebra is trivial modulo null sets, so its conditional expectation is constant. In that case the concise form is

Identify the circle group with $[0,1)$ modulo its endpoints, and let $\lambda$ be normalized Lebesgue measure. We first check invariance. On the $r$th inverse branch, $x=(y+r)/m$ for $0\le r<m$. For an integrable function $g$, substitution givesIn particular, testing indicator functions shows that the integer multiplication map on the circle preserves $\lambda$.

To prove ergodicity, let $B$ be a measurable set with $\lambda (E_m^{-1}B△B)=0$ and put $h=1_B$. Then $h(E_{m}x)=h(x)$ almost everywhere. Its Fourier coefficients areUsing invariance of $h$ and substituting separately on the same $m$ branches givesIn the last line, the finite geometric series of $m$th roots of unity is zero unless $m$ divides $k$, when it equals $m$. For any nonzero integer $k$, divide repeatedly by $m$ until the resulting integer is no longer divisible by $m$. The recurrence then implies $c_k=0$.

Since the Fourier basis is a complete orthonormal basis of $L^2([0,1),\lambda )$, the absence of every nonconstant Fourier coefficient implies $h=c_0=\lambda (B)$ almost everywhere. An indicator function takes only the values zero and one, so $\lambda (B)$ must be zero or one. This proves

Outside the countable set of dyadic rational numbers, the binary expansion $x={\sum }_{j\ge 1}{ϵ}_j(x)2^{-j}$ is unique. Multiplication by two modulo one deletes the first binary digit, soLet $g=1_{[1/2,1)}$. By part (b), the doubling map is a measure-preserving transformation and is ergodic for Lebesgue measure. Applying the Birkhoff ergodic theorem to this indicator function givesfor almost every $x$. The dyadic rationals have Lebesgue measure zero, so the choice of their two possible binary expansions does not affect the conclusion. Thus the limiting frequency of the digit one is $1/2$ almost everywhere.

We first prove invariance, before using any assertion that requires it. Write $A_n\phi (x)=n^{-1}{\sum }_{k=0}^{n-1}\phi (f^{k}x)$. Choose a point whose forward orbit has the prescribed convergence against every continuous function; the hypothesis gives a set of such points of full measure. For each continuous function $\phi$, telescoping givesbecause a continuous function on a compact metric space is bounded. Both test functions are continuous, so their averages converge to their prescribed integrals. Hencefor every continuous function $\phi$. The continuous-test criterion for an invariant measure therefore gives $f_{\ast }\mu =\mu$. The points in the hypothesis can now be called generic points for an invariant measure.

For ergodicity, let $B$ be a Borel set invariant modulo null sets, and set $h=1_B$, $p=\mu (B)$. Then $h\circ f=h$ almost everywhere. Since invariance preserves null preimages, deleting the union of all iterated preimages of the exceptional null set gives $h(f^{k}x)=h(x)$ for every $k\ge 0$ on one full-measure set. Thus $A_{n}h=h$ almost everywhere for every $n$.

Given $ϵ>0$, the continuous approximation of Borel indicators on a compact metric space, proved in the supporting steps below, supplies $\phi \in C(X)$ with $0\le \phi \le 1$ and $\Vert h-\phi {\Vert }_{L^1(\mu )}<ϵ$. By the hypothesis, $A_n\phi \to \int \phi d\mu$ almost everywhere. Since $0\le A_n\phi \le 1$, the dominated convergence theorem also gives convergence in $L^1(\mu )$. Invariance and the triangle inequality give the uniform estimateConsequently,Letting $n\to \infty$ and then $ϵ\downarrow 0$ proves $\Vert h-p{\Vert }_1=0$. Explicitly,so $p\in \{0,1\}$. Every invariant Borel set has measure zero or one, which provesThis proof controls measurable-set averages through a uniform $L^1$ estimate; convergence only against continuous test functions is not silently assumed to include indicator functions.

Here is an alternative route for the ergodicity step using the Birkhoff ergodic theorem. After invariance has been proved, the theorem identifies the almost-everywhere limit of $A_n\phi$ with ${\mathbb{E}}_{\mu }[\phi \mid \mathcal{I}]$. The hypothesis therefore givesfor every continuous function $\phi$. For an invariant Borel set $B$, approximate $h=1_B$ in $L^1$ by such a $\phi$. Since $h$ is measurable with respect to the invariant sigma-algebra, its conditional expectation is $h$ itself. The L1 contraction of conditional expectation givesArbitrarily accurate continuous approximation forces $h=\mu (B)$ almost everywhere. Thus this use of the theorem reaches the same zero-or-one criterion as the direct averaging proof above, without assuming in advance that $\mu$ is ergodic.

For a Borel set $B$ and $ϵ>0$, inner regularity supplies a compact set $K\subseteq B$ with $\mu (B)-\mu (K)<ϵ/2$. Independently, outer regularity supplies an open set $U\supseteq B$ with $\mu (U)-\mu (B)<ϵ/2$. Because $K\subseteq U$ and the measure is finite,This creates an arbitrarily small measurable transition region between a compact inner approximation and an open outer approximation. The cutoff in the next step then approximates $1_B$, rather than merely approximating the number $\mu (B)$.

For the compact set $K\subseteq B\subseteq U$ chosen in the preceding step, the Urysohn lemma gives a continuous function $0\le \phi \le 1$ equal to one on $K$ and zero on $X\setminus U$. In a metric space this cutoff can also be written explicitly, when $K$ and $X\setminus U$ are both nonempty:The two sets are disjoint and closed, so the denominator never vanishes, and their distance functions are continuous. If $K$ is empty, take $\phi =0$; if $U=X$ and $K$ is nonempty, take $\phi =1$. These choices satisfy the required boundary conditions in the exceptional cases.

The difference $\phi -1_B$ vanishes on $K$ and outside $U$, and its absolute value is at most one everywhere. ThereforeThis is the precise continuous approximation required by both proofs of ergodicity, and also gives $|\int \phi d\mu -\mu (B)|<ϵ$.