Context: I know essentially nothing about cohomology of any kind, but I have a problem involving classifying obstructions to extensions of certain maps or covers, and I have heard that cohomology is relevant to some problems of that flavour in various areas of mathematics. I'll lay out the problem I'm interested in. My question, with the natural follow-up: Is there, or might there be, a kind of cohomology relevant to my problem? If so, where should I look, and if not, why not?

The specific question that interests me: Let $Y$ be a mixing (i.e. irreducible, aperiodic) sofic shift in one dimension and let $Z \subset Y$ be a mixing shift of finite type. When do there exist a mixing shift of finite type $X$ and a factor code (= surjective sliding-block = continuous, shift-commuting surjection) $\pi: X \to Y$ admitting a section of $Z$, i.e. a subshift $Z' \subset X$ such that $\pi|_{Z'}: Z' \to Z$ is a conjugacy (shift-commuting homeomorphism)?

In the case $Z=Y$ [Edit in response to Salo's comment: and if we allow $Z = Y$ to be merely mixing sofic], there are some known obstructions from the work of Mike Boyle, involving periodic points (see e.g. "Lower entropy factors of sofic systems", Ergodic Theory and Dynamical Systems 1984 (4) 541-557). I don't believe the problem has been studied explicitly in the case that $Z$ is a proper subshift of $Y$, where we are asking for $\pi$ to admit a particular local section (i.e. of $Z$), and allowing for the nonexistence of a global section.

I am aware of the use of a kind of cohomology for dynamical systems in, for instance, the work of Bergelson-Tao-Ziegler, but am not sure whether this would be appropriate for problems of the kind I have described.

  • 1
    $\begingroup$ Slight nitpick, there are no obstructions if $Z=Y$, because then $Y$ is SFT. Take $X=Y$ and $\pi$ identity. $\endgroup$
    – Ville Salo
    Jun 4, 2022 at 5:33
  • $\begingroup$ For minimal subshifts, Cech cohomology of the suspension (equivalently, the dimension group of the associated Bratteli-Vershik system) is often a useful invariant that can tell you something about extensions/factors in this way. Unfortunately, Sofic shifts are rarely minimal, which means the Cech cohomology will be infinitely generated, so difficult to handle. The Bowen Franks group is a kind of cohomology group associated with SFTs which I feel might be closer to an invariant relevant for this setting. I'm not sure if there's an analogue that is defined for Sofic shifts. $\endgroup$
    – Dan Rust
    Jun 4, 2022 at 10:04
  • 2
    $\begingroup$ A couple of possibly helpful notes. First, if $Y$ is of almost finite type, then such a "nice" factor map exists iff the minimal SFT cover is an example, since every factor map to $Y$ factors through the minimal cover (Boyle & Kitchens & Marcus 1985: A note on minimal covers for sofic systems.) Second, it's decidable whether a given factor map $\pi$ is nice, and equivalent to the existence of a section on the periodic points of $Z$ that behaves well in terms of eventually periodic tails (Salo & Törmä 2015: Category theory of symbolic dynamics. Theorem 1) $\endgroup$ Jun 4, 2022 at 19:42
  • $\begingroup$ @IlkkaTörmä: To clarify, isn't this is an answer to the technical question for AFT? I.e. it's decidable for them. $\endgroup$
    – Ville Salo
    Jun 5, 2022 at 9:34
  • $\begingroup$ @VilleSalo Yes, it is. And the second note holds more generally. $\endgroup$ Jun 5, 2022 at 12:37

1 Answer 1


This is joint work with Ilkka Törmä (50-50, I am just more interested in points than him).

We did not see a link to cohomology, but your technical question was very interesting, and we believe we solved it.

Theorem. Let $Y$ be a mixing sofic shift and $Z$ a mixing SFT contained in $Y$. Then the following are equivalent:

  1. There exist a mixing SFT $X$ and a factor map $\pi : X \to Y$ such that for some subshift $Z'$ of $X$, $\pi|_{Z'}$ is a conjugacy.
  2. There exist a mixing SFT $X$ and a factor map $\pi : X \to Y$ such that $Z$ admits a shift-commuting continuous section $\phi : Z \to X$.
  3. $Y$ and $Z$ satisfy the first-order formula $\forall s \in L(Y): \exists u, w \in L(Y): \exists a, b \in L(Z): \forall v \in L(Z): (a v b \in L(Z) \implies s u a v b w s \in L(Y)).$

Proof. 1 $\iff$ 2. is trivial and was noted in the post.

For 2 $\implies$ 3., suppose such $X$, $\pi$ and $\phi$ exist. We may recode them so that $X$, $Z$ and $Z' = \phi(Z)$ are nearest-neighbor SFTs, $\pi$ has radius $0$ and $\phi$ has radius $1$. The recoding for $\pi$ is standard (you can do it first), others come from simple higher block coding, i.e. remembering multiple symbols at once.

Note that nearest-neighbor SFTs are equivalent to vertex shifts, i.e. configurations are sequences of vertices that form a valid path in a graph; we use this terminology. In particular, $Z'$ corresponds to a (not necessarily induced) subgraph of $X$.

Take any word $s \in L(Y)$ and choose a $\pi$-preimage $s' \in L(X)$ for it. Extend $s'$ into a word $s' u' \in L(X)$ that can be followed by a vertex of $Z'$, and then extend it by a path of three $Z'$-vertices $a' = a'_1a'_2a'_3$ to get some $s' u' a'$. Let $b' w' s'$ be defined similarly, but extending $s'$ to the left. Let $u, w, a, b$ be the $\pi$-images of $u', w', a', b'$. Note that $a, b, a', b'$ all have length $3$.

Take any $v$ such that $a v b \in L(Z)$. Then $c v' d = \phi(a v b)$ has length equal to $|v| + 4$ (when applying a radius-$1$ map to a word, the length decreases by one on each side), $|v'| = |v|$, $|c| = |d| = 2$. Now observe that $a'$ maps to $a$ in $\pi$ and $a'$ is a word in $Z'$, so $\phi$ maps $a$ to the central vertex of $a'$; similarly for $b$ and $b'$. Therefore the first vertex of $cv'd$ is just the second vertex of $a$, and similarly the last vertex of $cv'd$ is the second vertex of $b$.

Since $X$ is nearest-neighbor, we have $s' u' a'_1 c v' d b'_3 w' s' \in L(X)$. The $\pi$-image of this word is $s u a v b w s \in L(Y)$, which proves the first-order formula.

For 3. $\implies$ 2., we may recode $Y$ so that $Z$ is an edge shift. Let $\pi' : Y' \to Y$ be the Fischer cover of $Y$ (the minimal right-resolving cover), which is the labeled edge shift whose vertices are follower sets of words in $L(Y)$. Let $s \in L(Y)$ be a synchronizing word, that is, one for which any $\pi'$-preimage terminates at the same vertex $q$ in $Y'$. Let $u, w, a, b$ be given for $s$ by the assumption.

We add new vertices and edges to $Y'$: from each vertex $p$ that can be followed by $s$, a path $P$ with label $s u a$ (which merge after their first edges); a copy of the graph of $Z$; and a path $Q$ with label $b w s$ terminating at $q$. For any edge $e$ in $Z$ that can follow $a$, we add a new edge with label $e$ from the endpoint of $P$ to the endpoint of $e$. For any edge $e$ in $Z$ that can precede $b$, we add a new edge with label $e$ from the start of $e$ to the start of $Q$.

We claim that this new edge-labeled graph $G$ defines a mixing SFT $X$ and a factor map to $Y$ that admits a section $\phi$ with $\phi(Z)$ being the copy of $Z$ we added by hand. Take any path $v$ in $G$; we claim that its labeling is in $L(Y)$. We may assume that the labeling begins and ends with $s$ by extending $v$ if necessary. Since $s$ is a synchronizing word for $Y$, we may split the path into overlapping segments that start and end with $s$, and handle each segment separately. The labeling of $G$ has the property that any path with label $s$ terminates in either $q$ or the $|s|$th vertex of $P$. A segment that goes through $P$, then the copy of $Z$ and then $Q$ has a labeling of the form $s u a v b w s$ with $a v b \in L(Z)$, which we assumed are all in $L(Y)$. A segment that does not go through $P$ is entirely inside $Y'$, and thus its labeling is in $L(Y)$. Hence we have a factor map onto $Y$. It is clear that $X$ is mixing (since $Y'$ is), and the section $\phi$ just maps $Z$ to the copy edge-by-edge. Square.

Corollary. The condition is decidable.

Proof. Use basic automata theory. Square.

As Ilkka's comment showed, for subshifts of almost finite type, the condition is equivalent to Fischer cover being an example (and that's decidable). The following example, taken from [1], shows that the Fischer cover may not admit a section even if some other factor map does.


Namely, take the labels of this graph as $Y$ (so it's a mixing sofic shift), and pick $Z = \{1^{\mathbb{Z}}\}$. If we take $X$ the Fischer cover (that's what's shown in the picture), there is no preimage for the unique point in $Z$. However, it is easy to show that the above first-order condition holds.

We do not know how to extend the result to the case where $Z$ is only mixing sofic.

[1]: Ballier, Alexis, Limit sets of stable cellular automata, Ergodic Theory Dyn. Syst. 35, No. 3, 673-690 (2015). ZBL1355.37025.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.