\documentclass[10pt]{article}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{verbatim}
\usepackage{graphicx}
\usepackage{color}

\begin{document}

\thispagestyle{empty}

\begin{center}

\begin{large}
\noindent
MATH 4290 Homework Assignment 4
\end{large}

\end{center}

\noindent
Due on Thursday, October 11th, at the BEGINNING of class.\\

\noindent $\bullet$ Prove the Hedlund-Morse theorem for two-sided shifts, namely\\

\noindent
(a) If $x \in A^{\mathbb{Z}}$ satisfies $c_n(x) \leq n$ for some $n$, then $x$ is periodic

\noindent
(b) If $X \subseteq A^{\mathbb{Z}}$ satisfies $c_n(X) \leq n$ for some $n$, then $X$ is finite\\

\noindent $\bullet$
Design a subshift $X \subseteq A^{\mathbb{N}}$ which satisfies $c_n(X) = n + 2$ for all $n \in \mathbb{N}$. (We could call such a subshift ``almost Sturmian.'')\\

\noindent $\bullet$
Prove that for every $n$, the higher-block code $\phi_n$ defined in class is a conjugacy from the full shift $A^{\mathbb{Z}}$ to its image.
(Reminder: for any $x \in A^{\mathbb{Z}}$, $\phi_n(x) \in (A^n)^{\mathbb{Z}}$ is defined by $(\phi_n(x))_j$, the $j$th letter of $\phi_n(x)$, is equal to 
$x_j \ldots x_{j + n - 1} \in A^n$ for all $j \in \mathbb{Z}$.)\\

%\noindent $\bullet$
%Prove that $X \subset A^{\mathbb{Z}}$ is a subshift, i.e. is closed and $\sigma$-invariant, if and only if there exists a (not necessarily finite) list $\mathcal{F}$ of finite words on $A$ such that $X = X(\mathcal{F}) := \{x \in A^{\mathbb{Z}} \ : \ x \textrm{ does not contain any of the words in } \mathcal{F}\}$.\\

\noindent $\bullet$
Define $X \subseteq \{0,1\}^{\mathbb{Z}}$ to be the set of all $0$-$1$ biinfinite sequences such that the number of $0$s between any two closest $1$ symbols is even. 
For instance,
\[
\ldots 01001000011001 \ldots \in X, \ldots 0100\textcolor{red}{10001}001 \notin X.
\]
Prove that $X$ is NOT a subshift of finite type, i.e. there does not exist a finite set $\mathcal{F}$ of words so that $X = X(\mathcal{F})$. 


\end{document}
 
