4

The full shift over an alphabet $A$ is the set of all bi-infinite sequences built from characters belonging to $A$. The full $n$-shift is the full shift over some alphabet of size $n$.

The exercise I was asked to solve is to tell whether the $2$-shift is conjugate to the $3$-shift, and whether there exists a factor map from the full $2$-shift to the full $3$-shift.

Searching the web I found (in Scholarpedia) that the topological entropy is invariant under isomorphism of symbolic dynamics. The topological entropy of the full $n$-shift is $\log (n)$ (as described in the link and not hard to see), therefore these two dynamics are not conjugate, and moreover, an additional result states that a factor map cannot increase the entropy, therefore a factor map from the full $2$-shift to the full $3$-shift cannot exist.

Can you help in finding a more basic way of proving that these dynamics are not conjugate? I don't think this was the method implied in the exercise - we haven't reached topological entropy in the course yet.

co.sine
  • 629

2 Answers2

2

You can count fixed points.

For the full $n$-shift, the number of fixed points is $n$, one per symbol. Since the number of fixed points is an invariant of topological conjugacy, the full $m$ and $n$-shifts are not conjugate when $m \ne n$.

As noted in the comment of @DanRust, under a factor map it is possible for the number of fixed points to go up or down. I don't have a particular example at hand, but one idea is that a period 2 orbit can be mapped to a single point. So this method does not seem useful for the question about factor maps.

Lee Mosher
  • 120,280
  • This may be simple, but why a factor map cannot increase the number of fixed points? – co.sine Oct 26 '18 at 13:56
  • 1
    You just need to show that the image of a fixed point under a factor map is a fixed point. Then just use the fact that a factor map is surjective. – Dan Rust Oct 26 '18 at 14:39
  • @DanRust (or anyone) please help, I still can't figure this out. A fixed point really goes to a fixed point: if $\phi$ is the factor map, $\sigma_X$ is the shift function in the domain set, $\sigma_Y$ the shift function in the codomain set, and $x \in X$ a fixed point, then $\sigma_X(x)=x$, and $\sigma_Y(\phi(x))=\phi(\sigma_X(x))=\phi(x)$ and therefore $\phi(x)$ is a fixed point. But, why a non-fixed point cannot go to a fixed point? I don't see how surjectiveness helps... – co.sine Oct 27 '18 at 05:21
  • 1
    Sorry actually the statement is false! The map from any shift space to the single point system is a factor map, so factor maps can in fact decrease or increase the number of fixed points (take a sturmian shift for examples to see how the number of fixed points can increase from $0$ to $1$). What you should really be using is the fact that a full topological conjugacy preserves the number of fixed points (and in general the number of points of period $p$ for any given $p$). Lee should edit his post. – Dan Rust Oct 27 '18 at 08:41
  • @DanRust: OK, thanks. Do you know than a method to show that there cannot exist a factor map from the full $2$-shift to the full $3$-shift? – co.sine Oct 27 '18 at 11:01
  • 1
    Entropy is the easiest method for showing that imo. Entropy is non-increasing under factor maps. – Dan Rust Oct 27 '18 at 11:07
  • 1
    Thanks Dan, that was careless of me. I'm removing that part. – Lee Mosher Oct 27 '18 at 14:44
  • Thank you both @DanRust and Lee Mosher. If you come up with an idea about the factor map please post it here :) – co.sine Oct 27 '18 at 16:23
1

The factor part of the question has the following entropy-free solution:

Assume by contradiction that $$\phi \quad \colon\quad \text{full shift over \{v,w\}} \to \text{full shift over \{x,y,z\}}$$

is a factor map. By the Curtis–Hedlund–Lyndon theorem, $\phi$ is induced by a sliding block code with some memory $m$ and anticipation $a$: $$\Phi \quad \colon \quad \{v,w\}^{m+a+1} \to \{x,y,z\}$$

$\phi$ is onto, so any word of $\{x,y,z\}$ of length $n$ is an image of some word of $\{v,w\}$ of length $m+a+n$. As a consequence, $$\forall n \ \colon 2^{m+a+n} \geq 3^n$$ which is impossible ($m$ and $a$ are constants).

co.sine
  • 629