%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publisher's TeX code    *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you either view the HTML version or    *
%_ * retrieve the article in DVI, PostScript, or PDF format.                *
%_ **************************************************************************

% Author Package file for use with AMS-LaTeX 1.2
\controldates{9-OCT-1997,9-OCT-1997,9-OCT-1997,9-OCT-1997}
 
\documentclass{era-l}
\issueinfo{3}{16}{January}{1997}
\dateposted{October 16, 1997}
\pagespan{105}{109}
\PII{S 1079-6762(97)00032-2}
\def\copyrightyear{1997}

\usepackage{amstext} 

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\numberwithin{equation}{section}


%    Absolute value notation
\newcommand{\abs}[1]{\lvert#1\rvert}

%    Blank box placeholder for figures (to avoid requiring any
%    particular graphics capabilities for printing this document).
\newcommand{\blankbox}[2]{%
  \parbox{\columnwidth}{\centering
%    Set fboxsep to 0 so that the actual size of the box will match the
%    given measurements more closely.
    \setlength{\fboxsep}{0pt}%
    \fbox{\raisebox{0pt}[#2]{\hspace{#1}}}%
  }%
}

%\issueinfo{3}{1}{September}{1997}
\copyrightinfo{1997}{American Mathematical Society}

%\renewcommand{\baselinestretch}{2}
\begin{document}
\title{The Williams conjecture is false for irreducible subshifts}
\author{K. H. Kim}
%\email{kkim@asu.alasu.edu}
\address{Mathematics Research Group,
Alabama State University, Montgomery, AL 36101-0271,  
and Korean Academy of Science and Technology}
\email{kkim@asu.alasu.edu}

\author{F. W. Roush}
\address{Mathematics Research Group,
Alabama State University, Montgomery, AL 36101-0271} 
\email{froush@asu.alasu.edu}


\date{June 5, 1997}

\commby{Svetlana Katok}

\subjclass{Primary 58F03, 54H20}

\keywords{Williams conjecture, irreducible subshift of finite type, strong 
shift equivalence, gyration numbers}

\thanks{The authors were partially supported by  NSF Grants
DMS 9024813 and DMS 9405004. }


\begin{abstract} We prove that the Williams conjecture is false for
irreducible subshifts of finite type using relative sign-gyration
 numbers defined 
between different subshifts.
\end{abstract}
\maketitle

\section{Introduction}
Shifts of finite type (SFTs) are 
topological dynamical systems which are the fundamental 
building blocks of symbolic 
dynamics, with  diverse 
applications  ~\cite{LM}. %{[]}. 
    The classification problem for these systems 
has been dominated for over two decades 
by the Williams Conjecture that shift equivalence classifies 
shifts of finite type. In ~\cite{KR4}, %{[]},
 we gave a counterexample 
in the reducible case, 
but the conjecture remained open in the most important case, 
the irreducible case. We announce here a counterexample in the 
irreducible case.  
The obstruction makes essential use of results on 
the theory of sign-gyration numbers and the dimension group 
representation built up  by Boyle, U. Fiebig, Krieger,
Lind, Nasu, Rudolph, 
Wagoner and ourselves to study the automorphism group $\text{Aut}(\sigma_A)$
of a shift of finite type $\sigma_A$. 
A key part of that development is the Factorization Theorem 
 ~\cite{KRW} %{[]}
 which states that 
the $SGCC$ representation 
of $\text{Aut}(\sigma_A)$ factors through its 
dimension representation, and by certain explicit formulas. 
We exploit this structure in the more general setting of 
topological conjugacies between (possibly different) SFTs to 
find an obstruction to conjugacy permitting the counterexample.  
Full proofs will appear in ~\cite{KR2}. %{[]}.

\section{Definitions} 



 A square nonnegative integral matrix $A$ presents an {\it edge shift 
of finite type} $\sigma _A$ as follows. Let $A$ be the adjacency 
matrix of a directed graph $\mathcal G$:  if $A$ is 
$n\times n$, then $\mathcal G$ has vertices $1,2,\dots ,n$ and the number 
of edges from vertex $i$ to vertex $j$ is $A(i,j)$.  
Let $X_A$ be the set of 
doubly infinite sequences $x= \dots x_{-1}x_0x_1 \dots$ such that for 
all $i,\ $  
 $x_i$ is in the edge set $\mathcal E$ of  $\mathcal G$, 
and the terminal vertex of $x_i$ equals the initial vertex of $x_{i+1}$. 
%(A point of $X_A$ is the edge-itinerary of an infinite 
%walk through $\mathcal G$.) 
Let $X_A$ have the compact, metrizable, 
zero-dimensional topology which is its relative topology as 
a subset of $\mathcal E^{\mathbb Z}$. Then $\sigma_A$ is the 
shift homeomorphism  from $X_A$ to  $X_A$, defined by 
$(\sigma_Ax)_i=x_{i+1}$. A {\it topological conjugacy},  or 
isomorphism, from  
$\sigma_A$ to $\sigma_B$ is a homeomorphism $h:X_A \to X_B$ 
such that $\sigma_A h= h\sigma_B $.   

Let $\Lambda$ be a subset of a ring such that $\Lambda$ contains 
$0$ and $1$. Let $A$ and $B$ be square matrices over $\Lambda$. 
 An elementary strong shift equivalence over $\Lambda$ from 
$A$ to $B$ is a pair $(R,S)$ of rectangular matrices over $\Lambda$ 
such that $A=RS$ and $B=SR$.  
When such a pair exists, the 
 matrices $A$ and $B$ are 
lag-1 strong shift equivalent over $\Lambda$. 
{\it Strong shift equivalence} is the equivalence 
relation on matrices over $\Lambda$ which is the transitive 
closure of lag-1 strong shift equivalence. 
Matrices $A$ and $B$ with entries from $\Lambda$ are 
{\it shift equivalent} over $\Lambda$ if there exist 
matrices $R$ and $S$ over $\Lambda$ and a positive integer $n$ 
such that the following equations hold: 
%$$
\[RA=BR,\ \ \ AS=SB,\ \ \ RS=B^n,\ \ \ SR=A^n. %$$
\] 
Shift equivalence is a much more tractable 
equivalence relation than strong shift equivalence. 
Williams ~\cite{Wi} %{[]}
 proved that matrices 
$A$ and $B$ are strong shift 
equivalent over $\mathbb Z^+$ if and only if the SFTs $\sigma_A$ and 
$\sigma_B$ are isomorphic, and   he conjectured 
that shift equivalence over   $\mathbb Z^+$ 
implies strong shift equivalence over   $\mathbb Z^+$. 
This is of primary interest in the case that the matrices 
$A$ and $B$ are irreducible, and especially in the case that 
they are primitive, that is, some power has all entries 
strictly positive. For primitive $A$ and $B$, 
the Williams Conjecture can be reformulated 
as the statement: if two primitive matrices are 
strong shift equivalent over $\mathbb Z$, then they 
are strong shift equivalent over $\mathbb Z^+$.
We  produce a counterexample to this formulation. 

\section{The obstruction} 

 As in ~\cite{KRW}, %{[]},
 we work in the setting 
of Wagoner's space of strong shift equivalences 
over $\Lambda$. (In this announcement, $\Lambda $ is 
$\mathbb Z$ or $\mathbb Z^+$.) 
Wagoner's space is a certain 
naturally oriented CW-complex  
which is the  
geometric realization of a simplicial 
set in which a vertex is a 
square matrix $A$ over $\Lambda$, an edge 
from $A$ to $B$ is an 
elementary  strong shift equivalence 
$(R,S)$ 
over $\Lambda$ ($A=RS,B=SR$) and a triangle can 
be presented as a triple 
$[(R_1,S_1),(R_2,S_2),(R_3,S_3)]$ 
satisfying the  all-important Triangle Identities
%$$
\[
R_1R_2 = R_3\, , \qquad 
R_2S_3 = S_1\, , \qquad 
S_3R_1 = S_2\, .
 %$$
\] 
A path from $A$ to $B$ in $RS(\Lambda )$  is 
homotopic to a path of edges 
%$$
\[\mathcal P=(R_1,S_1)^{\epsilon (1)}(R_2,S_2)^{\epsilon (2)} 
\dots (R_k,S_k)^{\epsilon (k)} %$$
\] 
where $\epsilon (i)$ is $1$ or $-1$ depending on whether the edge 
$(R_i,S_i)$ is traversed with positive or negative orientation.
Associated to a vertex $A$ is the direct limit group $G_A$
derived from the 
action of $A$ on integral row vectors.
(For $\Lambda = \mathbb Z^+$, $G_A$ is a presentation of  
Krieger's dimension group for $\sigma_A$; the dimension group 
has an order structure, which we ignore here.)   
We let $\text{Aut}(s_A)$ denote the group of isomorphisms of $G_A$ 
which commute with the automorphism induced by $A$. 
 An edge $(R,S)$ induces an isomorphism  $\widehat R$ 
of direct limit groups  and the path 
$\mathcal P$ induces the isomorphism $\widehat {\mathcal P}: G_A \to G_B$ 
given by 
$(\widehat R_1)^{\epsilon (1)}\dots 
(\widehat R_k)^{\epsilon (k)}$. 
Two such paths  from $A$ to $B$ are homotopic in $RS(\mathbb Z)$ if and only 
if they induce the same isomorphism $G_A \to G_B$ ~\cite{KRW}. %{[]}.  

Suppose $\phi $ is a conjugacy from $\sigma_A$ to $\sigma_B$.
 For a given positive integer $m$,  let 
$P^o_m(\sigma_A)$ denote the points in $\sigma_A$-orbits 
of cardinality $m$. 
Let $(x_1, \dots , x_k)$ be a basis for $P^o_m(\sigma_A)$: 
that is, a tuple of distinct points 
$x_i$ such that each $\sigma_A$-orbit of cardinality $m$ contains 
exactly one of the points $x_i$. Similarly let $(y_1, \dots, y_k)$ 
be a basis for $P^o_m(\sigma_B)$. Then there is a permutation 
$\pi$ of $\{1, \dots ,k\}$ and a $k$-tuple of integers 
$(n(1),\dots ,n(k))$ such that 
$\phi (x_i) = (\sigma_B)^{n(i)} y_{\pi (i)}$. We define the 
{\it orbit sign number} $OS_n(\phi)$ in $\mathbb Z/2$
to be $0$ if the permutation $\pi$ has even sign  
and $1$ otherwise. We define the {\it gyration number} in $\mathbb Z/m$ 
to be 
$GY_m(\phi)=\sum_i n(i)$.  Finally we define in $\mathbb Z/m$ the 
{\it sign-gyration} number 
%$$
\[
SGCC_m(\phi ) = GY_m(\phi ) +  (m/2) \sum _i  OS_i(\phi )
 %$$
\]
where the last sum is over the positive integers $il}} R_{ik}S_{ki}R_{jl}S_{lj}+
\sum_{\substack{ i
Received: from AXP14.AMS.ORG by AXP14.AMS.ORG (PMDF V5.1-8 #1)
 id <01IO0NEECQK0001FLI@AXP14.AMS.ORG>; Wed, 24 Sep 1997 10:36:25 EST
Date: Wed, 24 Sep 1997 10:36:22 -0400 (EDT)
From: "pub-submit@ams.org " 
Subject: ERA/9700
To: pub-jour@MATH.AMS.ORG
Reply-to: pub-submit@MATH.AMS.ORG
Message-id: <01IO0NIQNBA6001FLI@AXP14.AMS.ORG>
MIME-version: 1.0
Content-type: TEXT/PLAIN; CHARSET=US-ASCII


Return-path: 
Received: from gate1.ams.org by AXP14.AMS.ORG (PMDF V5.1-8 #1)
 with SMTP id <01IO0KN9SKLS001T2F@AXP14.AMS.ORG>; Wed, 24 Sep 1997 09:14:01 EST
Received: from leibniz.math.psu.edu ([146.186.130.2])
 by gate1.ams.org via smtpd (for axp14.ams.org [130.44.1.14]) with SMTP; Wed,
 24 Sep 1997 13:13:44 +0000 (UT)
Received: from cantor.math.psu.edu (aom@cantor.math.psu.edu [146.186.130.194])
 by math.psu.edu (8.8.5/8.7.3) with ESMTP id JAA09857 for
 ; Wed, 24 Sep 1997 09:13:42 -0400 (EDT)
Received: (aom@localhost) by cantor.math.psu.edu (8.8.5/8.6.9)
 id JAA22647 for pub-submit@MATH.AMS.ORG; Wed, 24 Sep 1997 09:13:38 -0400 (EDT)
Date: Wed, 24 Sep 1997 09:13:38 -0400 (EDT)
From: Alexander O Morgoulis 
Subject: *accepted to ERA-AMS, Volume 3, Number 1, 1997*
To: pub-submit@MATH.AMS.ORG
Message-id: <199709241313.JAA22647@cantor.math.psu.edu>
%% Modified September 10, 1997 by A. Morgoulis

% Date: 25-SEP-1997
%   \pagebreak: 0   \newpage: 0   \displaybreak: 0
%   \eject: 0   \break: 0   \allowbreak: 0
%   \clearpage: 0   \allowdisplaybreaks: 0
%   $$: 20   {eqnarray}: 0
%   \linebreak: 0   \newline: 0
%   \mag: 0   \mbox: 0   \input: 0
%   \baselineskip: 0   \rm: 0   \bf: 0   \it: 8
%   \hsize: 0   \vsize: 0
%   \hoffset: 0   \voffset: 0
%   \parindent: 0   \parskip: 0
%   \vfil: 0   \vfill: 0   \vskip: 0
%   \smallskip: 0   \medskip: 0   \bigskip: 0
%   \sl: 0   \def: 0   \let: 0   \renewcommand: 1
%   \tolerance: 0   \pretolerance: 0
%   \font: 0   \noindent: 0
%   ASCII 13 (Control-M Carriage return): 0
%   ASCII 10 (Control-J Linefeed): 0
%   ASCII 12 (Control-L Formfeed): 0
%   ASCII 0 (Control-@): 0
%