{'fraction_non_alphanumeric': 0.065369237439183, 'fraction_numerical': 0.011031359892094994, 'mean_word_length': 3.7746090156393746, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Partially observable systems and quotient entropy via graphs

We consider the category of partially observable dynamical systems, to which the entropy theory of dynamical systems extends functorially. This leads us to introduce quotient-topological entropy. We discuss the structure that emerges. We show how quotient entropy can be explicitly computed by symbolic coding. To do so, we make use of the relationship between the category of dynamical systems and the category of graphs, a connection mediated by Markov partitions and topological Markov chains.


Introduction
hom Comp (X,Ỹ ), such that the following diagram commutes.
Remark 1 (PSys is a comma-category). There is a forgetful functor F : Sys → Comp given by the assignment (X, f ) → X on objects and the assignment m → m on morphisms. The functor F forgets the dynamics.
The pair of functors (F, id Comp ) generates the comma-category F id . Its objects are triples of the form (X, f ),X, q X where (X, f ) is a dynamical system,X is a compact Hausdorff space, and q X : X →X is a continuous surjection. A morphism between (X, f ),X, q X and (Y, g),Ỹ , q Y is a tuple (m, n), where m : (X, f ) → (Y, g) is a morphism in Sys and n :X →Ỹ is a morphism in Comp. We obtain the category PSys by switching to compact notation.
There is a forgetful functor U : PSys → Sys which forgets the partial observability. On objects we have (X, f, q) → (X, f ) and on morphisms we have (m, n) → m. There is a functorial embedding E : Sys ֒→ PSys where on objects we have (X, f ) → (X, f, id), and on morphisms we have m → (m, m). The partially observable systems (X, f, q) where q : X →X is a morphism of Sys admit the projection (X, f, q) → (X,f ). The archetypes of systems which admit these projections are the product systems.
Remark 2. We have an adjunction U ⊢ E. The monad generated by this adjunction is trivial since U • E = id Sys . The comonad generated by the endofunctor E • U : PSys → PSys is more interesting. The coalgebras of this comonad consist of objects in PSys of the form (X, f, q) where q is a homeomorphism, hence those partially observable systems which are in fact fully observable.
We close this section by characterizing quotient maps which are morphisms of dynamical systems.
Definition 1. Let X be a set. The canonical order induced onto 2 ( 2 X ) by set inclusion in 2 X is such that for X , Y ∈ 2 (2 X ) we have X ⊑ Y if and only if for every A ∈ X there exists B ∈ Y fulfilling A ⊆ B.
Let A, B ∈ 2 (2 X ) . Their infimum is A ⊓ B = ({A ∩ B}) A∈A,B∈B . Recall that the kernel of a map f : X → Y is the partition of X given as ker(f ) = f −1 (y) y∈Y .
The finest partition of a set X is the partition into points ({x}) x∈X , the kernel of a homeomorphism. We will abuse notation by simply writing ker(f ) for X ker(f ) . The following obvious lemma is the topological analogon to the isomorphism theorem for vector spaces. The latter is crucial in the characterization of morphisms of evolution equations in Banach spaces [AR17] and in turn for flows on finite-dimensional manifolds [HA16].
Lemma 3. Let f : X → Y be a continuous map between compact Hausdorff spaces.
Then ker(f ) ≃ im(f ), where we equipped ker(f ) with the quotient topology.
Proof. Preimages of points under f are closed and therefore the induced quotient space is homeomorphic to ker(f ). Consider the map h : The map h is a continuous bijection by construction. A continuous bijection between compact Hausdorff spaces is a homeomorphism.
Proposition 1 (Characterization of morphisms). Let (X, f ) be a dynamical system and consider a continuous surjection q X : X →X. Then q X is a morphism of dynamical systems if and only if ker(q X ) ⊑ ker(q X • f ). (1) Proof. Suppose that q X is a morphism. Let A ∈ ker(q X • f ). Hence there exists a y 0 ∈ Y such that A = (q X • f ) −1 (y 0 ). Since q X is a morphism there exists g :X →X such that Recall that g −1 (y 0 ) = y 1 ∈X : g(y 1 ) = y 0 . Hence A = y 1 ∈g −1 (y 0 ) q −1 X (y 1 ), which is a union of cells in ker(q X ). Hence every A ∈ ker(q X • f ) contains at least one B ∈ ker(q X ) and therefore ker(q X ) ⊑ ker(q X • f ). Now, suppose that eq. (1) holds. By lemma 3 we have ker(q X ) ≃X. Let h be the respective homeomorphism. Consider the commutative diagram . This construction is possible by the axiom of choice, and is well-defined since it is independent of the choice of y ∈ [x]. Define g :X →X to be Remark 4. Consider the partially observable system (X, f, q). The following two statements are equivalent.
A morphism of systems requires that the target system is equivalent to the action of the source system on the fibers of the morphism.
Remark 5. Let (X, f, q X ) and (Y, g, q Y ) be isomorphic partially observable systems and suppose that (X, f ) q X − → (X,f ) is a morphism of dynamical systems. Then there exists a morphism (Y, g) q Y − → (Ỹ ,g) of dynamical systems and an isomorphism of dynamical systems (X,f ) ≃ (Ỹ ,g).
Consider the mapg :Ỹ →Ỹ given asg = n •f • n −1 . By inspection of the diagram one verifies that q Y • g =g • q Y and n •f =g • n.
Example 1 (Quaternion rotations and the Hopf map). We write S n−1 ⊂ R n for the sphere S n−1 = {x ∈ R n : x 2 = 1} and C n−1 ⊂ R n for the unit hypercube. We exhibit an isomorphism of partially observable systems, according to the following diagram.
We now define the maps in the above diagram. h m : We set q C : It remains to specify the dynamics. There are several rotations that can play this role. A possible choice are the rotations given by the following linear maps.
Note that R i : S i → S i and R i : C i → C i formally coincide as linear operators in the Euclidean ambient space. We have (S 3 , R 3 , q S ) ≃(C 3 , R 3 , q C ).

Entropy and quotient entropy
The complexity of a topological dynamical system is quantified by its entropy. Loosely speaking, the entropy of a system is the asymptotic rate of divergence of infinitesimally close orbits. A zero-entropy system exhibits such divergence at subexponential rate. A positive-entropy system does so at exponential rates, and a system of infinite entropy at superexponential rates. Sometimes systems of positive entropy are called chaotic systems. The notion of topological entropy was developed in the 60s, starting with Adler et al. [AKM65,Din69,Bow71]. The topological entropy of the system (X, f ) is Although the entropy is a number assigned to a system, we may use it to assign a number to morphisms: the difference in entropy between source and target, its complexity-reduction. (This approach, in the context of information-theoretic Shannon entropy, originates with [BFL11].) Unfortunately, the assignment Ent : Arr (Sys) → ([0, ∞], ≥) given by where Arr (Sys) denotes the Arrow category, is not functorial, as the following example shows.
Example 2. Pick a system (X, f ) with Ent(X, f ) = r > 0 and consider the following morphism in Arr (Sys). ( Yet Ent is functorial on a subcategory of Arr (Sys), the category Fac of factorizations of dynamical systems. The objects are morphisms of Sys. The morphisms are diagrams of the following form.
In the above case, we say that r is a morphism from m to n. Composition of morphisms is concatenation of diagrams.
Note that objects of Fac (which are morphisms of Sys) do not admit a morphism between them whenever they start from different objects (as morphisms in Sys).

There is the functorial embedding
on morphisms. The functoriality of entropy on Sys directly implies the functoriality of Ent on Fac.
We want to quantify the loss of complexity due to partial observability. The quantity that we use for this purpose is quotient-topological entropy. We define the quotienttopological entropy of the partially observable system (X, f, q) as where the topology induced by q is the topology that makes X homeomorphic to ker(q). It may not be immediately clear that the above definition is sensical. To see that it is, it suffices to use well-known arguments [AKM65]. Remark 6. If X is a metric space, the quotient-entropy may be computed by taking a limit along covers by quotient-metric balls of vanishing diameter. In fact, Bowen's construction [Bow71] may be applied to the quotient metric.
We have the commutative diagram Fac PSys Note that QEnt is not functorial on all of PSys, but it is functorial on the image of the above embedding.
Example 3. Let (X, f ) be a dynamical system such that Ent(X, f ) = r > 0 and consider the following morphism in PSys.
We interpret Ent as measuring the complexity-reduction of a morphism. In this light, QEnt extends Ent to partially observable systems: it quantifies the complexity reduction due to partial observability. Quotient-topological entropy shares the functoriality of entropy.
Proposition 2. The assignment QEnt : We have the following commutative diagram.
where U is an open cover of X in the topology induced by q X .
The following statements show that the observable complexity is at most equal to the complexity of the base system (Corollary 8), and that, whenever two quotient maps are ordered with respect to their resolution, the respective quotient entropies behave monotonically (Corollary 9).
Lemma 7 (Property 10 in [AKM65]). Let (X, f ) be a dynamical system and let A, B be open covers of X. Then Corollary 8. Let (X, f, q) be a partially observable system. Thenh(X, f, q X ) ≤ h(X, f ).
If the quotient map is a morphism, the quotient-entropy of the partially observable system equals the entropy of the target-system.
Proof. This follows from the observation that the N-action by g onX is isomorphic to the N-action by f on fibers of q X .
Remark 10. In the light of Proposition 3 and Corollary 9, one may interpret QEnt as a closure indicator. If the quotient-map is a morphism, we have QEnt = 0 since the kernel of the quotient map is preserved (Remark 4). It is not a precise closure indicator: If the kernel is scrambled with subexponential speed, this is not witnessed by entropy.
The basic properties of entropy, additivity on products (the Bernoulli property) and multiplicativity under iteration, are shared by quotient-entropy.
Proposition 4. The following two statements hold.
(i) Let m ∈ N. The m-step partially observable system (X, f m , q X ) fulfills h(X, f m , q X ) = m ·h(X, f, q X ).
(ii) Let (X, f, q X ) and (Y, g, q Y ) be partially observable systems.
Proof.  We are interested in quotient maps of state spaces and morphisms of systems. The related isomorphism-problem for topological Markov chains has been solved by Williams, who gave an algebraic condition on matrices encoding edge-shifts [Wil73]. We treat topological Markov chains as vertex-shifts. Remark 11. One may wonder whether defining letter-by-letter morphisms using a family c t : [n] → [m] for t ∈ N leads to a more general theory. This is not so. The theorem of Curtis-Lyndon-Hedlund [Hed69], states that any equivariant continuous map between topological Markov chains is a cellular automaton, hence locally generated by a finite-to-one map between the respective alphabets. This is a consequence of choosing the product topology on sequence space. (Hence any morphism between topological Markov chains can be considered to be letter-by-letter in an appropriate block representation.) For us the following statement will suffice: Let π : Proof. By hypothesis π is such that π • σ = σ • π. We have (π • σ(w)) t = π (σ(w)) t = c t ((σ(w)) t ) = c t (w t+1 ) and (σ • π(w)) t = (σ (π(w))) t = (π(w)) t+1 = c t+1 (w t+1 ), whereby we conclude that c t (w t+1 ) = c t+1 (w t+1 ) for all t ∈ N and any w ∈ [n] N . For any x ∈ [n] we can pick w ∈ [n] N such that w 2 = x. Hence c 1 (x) = c 2 (x) for all x ∈ [n]. Suppose that c i = c 1 . For all v ∈ [n] N such that v i+1 = x the same argument implies c i+1 (x) = c 1 (x). Whenever a test-sequence for y ∈ [n] does not exist, setting c i+1 (y) = c 1 (y) does no harm. The claim follows by induction.
Under this choice of metric C is 1-Lipschitz, hence continuous. The surjectivity of C follows from the surjectivity of c.
The sequence space is a Cantor space: it is compact, metrizable, totally disconnected, and has no isolated point. Hence the following lemma.
Lemma 13 (See Paragraph 3d in [KH97]). The sequence space [m] N with the metric The above lemma allows us to estimate quotient-entropy by a simple procedure.
This can be seen from The interesting question is whether the subspace The following proposition characterizes shift-equivariance of letter-by-letter maps between sequence spaces. Note that this is not a characterization of morphisms but of embeddings of the respective N-actions.
Proof. (ii) =⇒ (i): We have A wtw t+1 = 1 =⇒ B e(wt)e(w t+1 ) = 1 for all w ∈ W A and t ∈ N. Hence A topological Markov chain is fully specified by its underlying graph, which is fully specified by the respective adjacency matrix. (This as an isomorphism of categories.) Definition 3 (The category Graph). The objects are matrices A ∈ Mat n×n ({0, 1}) for The composition of morphisms is the composition of the underlying maps. The associativity-and identity-properties are inherited from maps between finite sets. Via topological Markov chains, the category Graph is functorially embedded into the category Sys.
Proposition 7. We have a functorial embedding S : Graph ֒→ Sys given by A → in Sys, which is equivalent to the commutativity of the following diagram.
Remark 14. The categorical products in Graph correspond to the Kronecker-products of adjacency matrices. The embedding of graphs into dynamical systems respects finite products. We have ( Whenever a graph may be obtained from another by adding edges there is a morphism. In particular, for any A ∈ Mat n×n ({0, 1}) we have A → (1) n×n . The existence of a graph-morphism implies embeddability of the actions (Proposition 6), not the existence of a morphism. A necessary condition for the existence of a morphism can be obtained as follows. Let A f − → B in Graph. Suppose that g : B → A is right-inverse to f , hence f • g = id. Then Sg : SB → SA is right-inverse to Sf : SA → SB. In particular, Sf is surjective. The existence of a section from the generating graph is a sufficient condition for topological Markov chains to be related by a morphism. The following proposition is immediate. In general, it is nontrivial to verify whether a graph is the quotient of another. In the following example the quotient-property is obvious since any inverse of the set-map which induces the graph morphism does induce an inverse graph-morphism. Note that the condition of Proposition 8 is not necessary. In fact, we can give an independent second sufficient condition, which is itself not necessary (as can be seen from Example 8). Proof. It suffices to show that Sc(W A ) = W B , hence that Sc maps words in W A to words in W B and that every word in W B is the image of a word in W A under Sc.
Suppose that U k ∩W B = ∅. We claim that U k+1 ∩W B = ∅. Consider the pair (w k , w k+1 ). We have A w k ,w k+1 = 1. Since c is a graph-morphism this implies B c(w k ),c(w k+1 ) = 1. Therefore U k+1 ∩ W B = ∅ and, by induction, U n ∩ W B = ∅ for all n ∈ N. We conclude Consider the pair (v k , v k+1 ), hence B v k ,v k+1 = 1. By construction there exists A ij = 1 where i ∈ c −1 (v k ) and j ∈ c −1 (v k+1 ) and {x ∈ V k : x k = i} = ∅ by hypothesis. Therefore V k+1 ∩ W A = ∅ and, by induction, V n ∩ W A = ∅ for all n ∈ N. We conclude Sc −1 (v) ∩ W A = ∅.

Quotient entropy and Markov partitions
There are several equivalent ways to define Markov partitions. We follow Adler [Adl98] and Gromov [Gro16].
Definition 4 (Markov partition). A Markov partition for the system (X, f ) is a finite collection {U i } n i=1 , n ≥ 2, of open sets U i ⊂ X such that the following three conditions hold.
Markov partitions are not quite partitions, Adler [Adl98] refers to them as topological partitions. The existence of a Markov partition for a dynamical system is a demanding property. Bowen [Bow70] showed that a Markov partition exists for any system satisfying Axiom A. Explicit constructions go back to Sinai [Sin68]. The usefulness of Markov partitions originates in the following construction.
Definition 5 (Hadamard construction [Had98]). The Hadamard construction assigns to The Hadamard construction and the embedding S : Graph ֒→ Sys have some properties of a retraction. Let (X, f ) be a dynamical system with Markov partition This assignment may be one-to-many on some points: We suppose that some choice is made. The pseudo-inverse assignment Φ −1 : [m] N → 2 X is obtained in the following manner. For any w ∈ W A , define R 0 (w) = {x ∈ X w 0 }, and, iteratively for t ∈ N, Then set Φ −1 (w) := ∞ t=0 R t (w) ⊂ X. Often, for example if f is a minimal homeomorphism, we have |Φ −1 (w)| = 1.
We are interested in systems that are finitely presented, in the sense that they admit a Markov partition such that the Hadamard construction followed by the embedding S yields a homeomorphism. In that case the Hadamard construction yields an isomorphism between the original system and a topological Markov chain.
These structural relationships, as well as others appearing in this work, are illustrated in the following diagram. The Markov graph is the complete graph on four vertices and hence Ent(E 4 ) = ln(4). Clearly no projection of the circle onto the interval is a morphism of the system. We are tempted to say that the quotient map reduces the symbolic dynamics to the full shift on two symbols and that this should implyh(E 4 ) = ln(2) and QEnt(E 4 ) = ln(4) − ln(2) = ln(2).
We proceed by formalizing the above example and by proving its correctness.
Definition 6 (Compatible topological partition). Let (X, f, q) be a partially observable system with Markov partition X = {U i } n i=1 for (X, f ). Consider a surjection s : Corollary 15 (Corollary of the definition). We have a graph-morphism s : A → B where A is the Markov graph of (X, f ) given by which is equivalent to f (U i ) ⊆ f (q −1 V s(i) ), and U j ⊆ q −1 V s(j) . We conclude f q −1 V s(i) ∩ q −1 V s(j) = ∅, which is equivalent to B s(i)s(j) = 1. Hence s is a graph-morphism.
Proposition 10. Let (X, f ) be a finitely presented dynamical system with Markov partition X = {U i } n i=1 . Consider the partially observable system (X, f, q) with quotient map q : X → Y . Suppose that the compatible topological partition Y = {V i } m i=1 of Y induces the graph-morphism s : A → B. Suppose that s admits a right-inverse graph-morphism. Then (W B , σ B ) is a dynamical system such that the diagram Proof. By Proposition 8, the map S is a letter-by-letter morphism of topological Markov chains since s admits a right-inverse graph-morphism. Since S : W A → W B is a morphism, the respective square in the above diagram commutes. We now construct the map h. By hypothesis, a trajectory through the cells of X uniquely identifies a point in X. A trajectory through Y is equivalent to a trajectory through its pullback onto X. Such a trajectory only identifies subsets of X and not points. We extend Φ −1 : 2 W A → 2 X by direct images. The restriction Φ −1 | ker(S) : ker(S) → ker(q) is a continuous bijection of compact Hausdorff spaces and therefore a homeomorphism. By Proposition 2 we know thath(X, f, q) =h(W A , σ A , S). But we have also shown that (W A , σ A ) S − → (W B , σ B ). By Proposition 3 we haveh(W A , σ A , S) = h(W B , σ B ). It remains to apply the spectral formula.
Note that in Example 5 the hypotheses of Proposition 10 are fulfilled: The existence of a right-inverse graph morphism is obvious since the Markov graph of the expanding circle map is complete.
Example 6. Consider the circle-map E 3 and the corresponding Markov partition. The dynamic of the compatible Markov partition of the interval is the full shift on two symbols. Henceh(E 3 ) = ln(2) and QEnt(E 3 ) = ln(3) − ln(2) = ln(3/2) < QEnt(E 4 ). (Combining with Example 5, we have obtained a case whereh(X, f, q) =h(X, g, q) for f = g.) Example 7. Consider the circle-map E 3 and the horizontal projection x → sin(2πx). The images of the cells of the Markov partition overlap in the unit interval in a way that makes a compatible selection impossible. (i) There exists n ∈ N, n ≥ 2, such that the set {0, 1/n, 2/n, ..., (n − 1)/n, 1} is finvariant.
(iii) There are no sinks in the Markov graph F ∈ Mat n×n ({0, 1}) given by  1 if f i−1 n , i n ∩ j−1 n , j n = ∅ 0 otherwise.
A Markov partition for an iterated standard-map is given by i−1 n , i n n i=1 . If we only consider certain quotient maps of the interval, we obtain a class of partially observable systems whose properties are straightforward.
A nontrivial standard quotient-map must be constant on at least one interval. Monotonicity and surjectivity imply that q(0) = 0 and q(1) = 1.