# A small talk on topological entropy

Today, for the first Theory Lunch after the summer holidays, I happened to talk about the subject of some notes I am taking for myself.

Let us start by clarifying the context. Recall that a topology on a set $X$ is a family $\mathcal{T}$ of subsets of $X$ such that:

1. $\emptyset, X \in \mathcal{T}$;
2. if $\{ U_i \}_{i \in I} \subseteq \mathcal{T}$ then $\bigcup_{i \in I} U_i \in \mathcal{T}$; and
3. if $U_1, \ldots, U_n \in \mathcal{T}$ then $\bigcap_{i=1}^n U_i \in \mathcal{T}$.

For instance, the family $\mathcal{T}$ made of all the unions of open intervals of $\mathbb{R}$ is the Euclidean topology.

The members of $\mathcal{T}$ are called the open sets of $X$; the complements of the open sets are called closed. If $Z \subseteq X$, then $\mathcal{T}_Z = \{ U \cap Z \mid U \in \mathcal{T} \}$ is a topology on $Z$, called the induced topology. For instance, the interval $[0,1]$ is closed in the Euclidean topology of $\mathbb{R}$, as it is the complement of the open set $U = (-\infty,0) \cup (1,+\infty)$; and $[0,2/3) = (-1/3,2/3) \cap [0,1]$ is an open subset of $[0,1]$.

An open cover of $X$ is a family of open sets of $X$ whose union is $X$. Open covers can be thought of as models of the level of detail one can achieve by observing a space while one’s vision is, for some reason, blurred: an observer will be able to tell point $x$ from point $y$ if and only if there are two disjoint open sets from the given open cover (possibly, the whole topology) one of which contains $x$ and the other $y$.

A topological space is compact if every open cover contains a finite subcover. Suppose that, to compensate our blurred vision, we hire guardians to keep track of the points of the space, but the contract with the security company states that each guardian will only watch the points of a given open set: compactness then ensures that we can always watch the whole space while only hiring finitely many guardians. (This similitude was suggested to me by Tommaso Toffoli.) The Heine-Borel theorem states that every open cover of the closed and bounded interval $[0,1]$ contains a finite subcover. Tychonoff’s theorem implies that the set $A^\omega$ of infinite words on a finite alphabet $A$, whose open sets are unions of sets of the form $wA^\omega$ with $w \in A^\ast$, is a compact space.

A function between two topological spaces is said to be continuous if the counterimage of any open subset of the codomain is an open subset of the domain. According to our similitude, going back along a continuous function does not worsen the level of detail: if the images of two points can be distinguished in the codomain, then the original points can also be distinguished in the domain. The usual $\varepsilon-\delta$ formulation of continuity from Calculus courses is, in fact, a special case of this definition.

If $X$ is a compact space, then for every open cover $\mathcal{U}$ of $X$ there is a minimum number $N(\mathcal{U}) \geq 1$ of elements of a finite subcover of $\mathcal{U}$. We set $H(\mathcal{U}) = \log \, N(\mathcal{U})$, where the logarithm is taken in a fixed base $a > 1$.

Let $\mathcal{U}$ and $\mathcal{V}$ be open covers of $X$: we say that $\mathcal{V}$ is a refinement of $\mathcal{U}$ if for every $V \in \mathcal{V}$ there exists $U \in \mathcal{U}$ such that $V \subseteq U$: we then write $\mathcal{U} \prec \mathcal{V}$. The intuitive meaning is that $\mathcal{V}$ allows a level of detail no smaller than $\mathcal{U}$ does: if $\mathcal{U}$ allows telling any two points apart, so does $\mathcal{V}$.

It is immediate to check that $\prec$ is a preorder: usually, $\prec$ is not antisymmetric. As a counterexample, let:

• $X = [0,1]$;
• $\mathcal{U} = \{(x-1/(2n+1),x+1/(2n+1)) \cap [0,1] \mid x \in [0,1], n \geq 0\}$; and
• $\mathcal{V} = \{(x-1/(2n+2),x+1/(2n+2)) \cap [0,1] \mid x \in [0,1], n \geq 0\}$.

Then $\mathcal{U} \prec \mathcal{V}$ and $\mathcal{V} \prec \mathcal{U}$, but $\mathcal{U} \neq \mathcal{V}$ The example above can be modified to show that the case $\mathcal{U} \cap \mathcal{V} = \emptyset$ is also possible.

The common refinement of $\mathcal{U}$ and $\mathcal{V}$ is

$\mathcal{U} \vee \mathcal{V} = \{ U \cap V \mid U \in \mathcal{U}, V \in \mathcal{V} \}$

Clearly, $\mathcal{U}, \mathcal{V} \prec \mathcal{U} \vee \mathcal{V}$; if $\mathcal{W}$ is any open cover such that $\mathcal{U}, \mathcal{V} \prec \mathcal{W}$, and $W \in \mathcal{W}$, then there exist $U \in \mathcal{U}$ and $V \in \mathcal{V}$ such that $W \subseteq U \cap V$: thus, $\mathcal{U} \vee \mathcal{V} \prec \mathcal{W}$ too.

The operation $\vee$ is commutative and associative, but usually not idempotent: as a counterexample, if $X = [0,1]$ and $\mathcal{U} = \{ [0,2/3), (1/3,1] \}$, then $\mathcal{U} \vee \mathcal{U} = \{ [0,2/3), (1/3,2/3), (1/3,1] \}$. Observe that, with our choice, $\mathcal{U} \vee \mathcal{U} \prec \mathcal{U}$: this is actually a general fact.

Theorem. Let $X$ be a compact topological space, let $\mathcal{U}$ and $\mathcal{V}$ be open covers of $X$, and let $F : X \to X$ be a continuous function.

1. If $\mathcal{U} \prec \mathcal{U}'$ and $\mathcal{V} \prec \mathcal{V}'$ then $\mathcal{U} \vee \mathcal{V} \prec \mathcal{U}' \vee \mathcal{V}'$.
2. If $\mathcal{U} \prec \mathcal{V}$ then $\mathcal{U} \vee \mathcal{V} \prec \mathcal{V}$ and $H(\mathcal{U}) \leq H(\mathcal{V}) = H(\mathcal{U} \vee \mathcal{V})$.
3. $H(\mathcal{U} \vee \mathcal{V}) \leq H(\mathcal{U}) + H(\mathcal{V})$.
4. If $\mathcal{U} \prec \mathcal{V}$ then $F^{-1}(\mathcal{U}) \prec F^{-1}(\mathcal{V})$.
5. $F^{-1}(\mathcal{U} \vee \mathcal{V}) = F^{-1}(\mathcal{U}) \vee F^{-1}(\mathcal{V})$.
6. $H(F^{-1}(\mathcal{U})) \leq H(\mathcal{U})$. If $F$ is surjective then equality holds.

Given an open cover $\mathcal{U}$ of a compact space $X$ and a continuous function $F : X \to X$, let

$\mathcal{U}_F^{(n)} = \bigvee_{i=0}^{n-1} F^{-i}(\mathcal{U})$

Then for every $m,n \geq 1$,

$\mathcal{U}_F^{(m+n)} = \bigvee_{i=0}^{m-1} F^{-i}(\mathcal{U}) \vee F^{-m} \left( \bigvee_{j=0}^{n-1} F^{-j}(\mathcal{U}) \right) \,,$

so that $H(\mathcal{U}_F^{(m+n)}) \leq H(\mathcal{U}_F^{(m)}) + H(\mathcal{U}_F^{(n)})$: by Fekete’s lemma,

$h(F,\mathcal{U}) = \lim_{n \to \infty} \dfrac{H(\mathcal{U}_F^{(n)})}{n} = \inf_{n \geq 1} \dfrac{H(\mathcal{U}_F^{(n)})}{n}$

exists. The quantity above is called the entropy of $F$ relative to $\mathcal{U}$. The topological entropy of the continuous function $F$ is then defined as

$h(F) = \sup_{\mathcal{U}} h(F,\mathcal{U})$

Intuitively, topological entropy is the worst-case amount of average
information per iteration required to reconstruct the initial state, given the
current one. As a quick sanity check, let us verify that the identity has zero topological entropy. Clearly, $\mathcal{U}_{\mathrm{id}_X}^{(n)} = \bigvee_{i=0}^{n-1} \mathcal{U} \prec \mathcal{U}$ whatever $n \geq 1$ is, so that $H(\mathcal{U}_{\mathrm{id}_X}^{(n)}) = H(\mathcal{U})$ for every $n \geq 1$, and $h(\mathrm{id}_X,\mathcal{U}) = 0$ whatever $\mathcal{U}$ is.