ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 3, Pages 105–109 (October 16, 1997) S 1079-6762(97)00032-2

THE WILLIAMS CONJECTURE IS FALSE FOR IRREDUCIBLE SUBSHIFTS

K. H. KIM AND F. W. ROUSH

(Communicated by Svetlana Katok)

Abstract. We prove that the Williams conjecture is false for irreducible subshifts of finite type using relative sign-gyration numbers defined between different subshifts.

1. Introduction

Shifts of finite type (SFTs) are topological dynamical systems which are the fundamental building blocks of symbolic dynamics, with diverse applications [4]. 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 [1], 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 Aut(σ_{A}) of a shift of finite type σ_{A}. A key part of that development is the Factorization Theorem [3] which states that the SGCC representation of Aut(σ_{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 [2].

2. Definitions

A square nonnegative integral matrix A presents an edge shift of finite type σ_{A} as follows. Let A be the adjacency matrix of a directed graph G: if A is n × n, then G has vertices 1, 2, …, 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 = … x_{−1}x_{0}x_{1} … such that for all i, x_{i} is in the edge set E of G, and the terminal vertex of x_{i} equals the initial vertex of x_{i+1}. Let X_{A} have the compact, metrizable, zero-dimensional topology which is its relative topology as a subset of E^{ℤ}. Then σ_{A} is the shift homeomorphism from

\begin{matrix}c \\ ◯ \end{matrix}1997 American Mathematical Society

Received by the editors June 5, 1997.

1991 Mathematics Subject Classification. Primary 58F03, 54H20.

Key words and phrases. Williams conjecture, irreducible subshift of finite type, strong shift equivalence, gyration numbers.

The authors were partially supported by NSF Grants DMS 9024813 and DMS 9405004.

X_{A} to X_{A}, defined by (σ_{A}x)_{i} = x_{i+1}. A topological conjugacy, or isomorphism, from σ_{A} to σ_{B} is a homeomorphism h : X_{A} → X_{B} such that σ_{A}h = hσ_{B}.

Let Λ be a subset of a ring such that Λ contains 0 and 1. Let A and B be square matrices over Λ. An elementary strong shift equivalence over Λ from A to B is a pair (R, S) of rectangular matrices over Λ such that A = RS and B = SR. When such a pair exists, the matrices A and B are lag-1 strong shift equivalent over Λ. Strong shift equivalence is the equivalence relation on matrices over Λ which is the transitive closure of lag-1 strong shift equivalence. Matrices A and B with entries from Λ are shift equivalent over Λ if there exist matrices R and S over Λ 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 [5] proved that matrices A and B are strong shift equivalent over ℤ^{+} if and only if the SFTs σ_{A} and σ_{B} are isomorphic, and he conjectured that shift equivalence over ℤ^{+} implies strong shift equivalence over ℤ^{+}. 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 ℤ, then they are strong shift equivalent over ℤ^{+}. We produce a counterexample to this formulation.

3. The obstruction

As in [3], we work in the setting of Wagoner’s space of strong shift equivalences over Λ. (In this announcement, Λ is ℤ or ℤ^{+}.) 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 Λ, an edge from A to B is an elementary strong shift equivalence (R, S) over Λ (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_{1}R_{2} = R_{3} ,  R_{2}S_{3} = S_{1} ,  S_{3}R_{1} = S_{2} .

A path from A to B in RS(Λ) is homotopic to a path of edges

P = (R_{1}, S_{1})^{ϵ(1)}(R_{2}, S_{2})^{ϵ(2)} … (R_{k}, S_{k})^{ϵ(k)}

where ϵ(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 Λ = ℤ^{+}, G_{A} is a presentation of Krieger’s dimension group for σ_{A}; the dimension group has an order structure, which we ignore here.) We let 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 R̂ of direct limit groups and the path P induces the isomorphism P̂ : G_{A} → G_{B} given by (R̂_{1})^{ϵ(1)} … (R̂_{k})^{ϵ(k)}. Two such paths from A to B are homotopic in RS(ℤ) if and only if they induce the same isomorphism G_{A} → G_{B} [3].

Suppose ϕ is a conjugacy from σ_{A} to σ_{B}. For a given positive integer m, let P_{m}^{o}(σ_{A}) denote the points in σ_{A}-orbits of cardinality m. Let (x_{1}, …, x_{k}) be a basis for P_{m}^{o}(σ_{A}): that is, a tuple of distinct points x_{i} such that each σ_{A}-orbit of cardinality m contains exactly one of the points x_{i}. Similarly let (y_{1}, …, y_{k}) be a basis for P_{m}^{o}(σ_{B}). Then there is a permutation π of {1, …, k} and a k-tuple of integers (n(1), …, n(k)) such that ϕ(x_{i}) = (σ_{B})^{n(i)}y_{π(i)}. We define the orbit sign number OS_{n}(ϕ) in ℤ/2 to be 0 if the permutation π has even sign and 1 otherwise. We define the gyration number in ℤ/m to be GY_{m}(ϕ) = ∑_{i} n(i). Finally we define in ℤ/m the sign-gyration number

SGCC_{m}(ϕ) = GY_{m}(ϕ) + (m/2) ∑_{i} OS_{i}(ϕ)

where the last sum is over the positive integers i < m such that m/i is a power of 2 (and an empty sum is 0). “SGCC” refers to “sign-gyration-compatibility-condition” but for euphony we condense to “sign-gyration”.

To apply these ideas in RS(ℤ^{+}), at each vertex A we fix a definite choice of basis for each P_{n}^{o}(σ_{A}), and at each edge (R, S) we fix a definite choice of elementary conjugacy c(R, S). This is done by certain natural lexicographic rules, chosen in [3]. For each edge (R, S), these choices determine SGCC_{m}(c(R, S)), which we abbreviate as SGCC_{m}(R, S). To a path P = (R_{1}, S_{1})^{ϵ(1)}(R_{2}, S_{2})^{ϵ(2)} … (R_{k}, S_{k})^{ϵ(k)} from A to B in RS(ℤ) we associate the relative sign-gyration number

SGCC_{m}(P) = ∑_{i} ϵ(i)SGCC_{m}(R_{i}, S_{i}) .

The central result of [3] is that SGCC_{m} extends (by certain explicit formulas) to a map sgcc_{m} on paths in RS(ℤ) which depends only on the homotopy class of P as a path from A to B in RS(ℤ). For example, when A has nonnegative integral entries and tr(A^{2}) = 0, it follows from (3.3) of [3] that sgcc_{2}(R, S) is given by the polynomial formula

sgcc_{2}(R, S) = ∑_{\begin{matrix}i<j \\ k>l \end{matrix}} R_{ik}S_{ki}R_{jl}S_{lj} + ∑_{\begin{matrix}i<j \\ k≥l \end{matrix}} R_{ik}S_{kj}R_{jl}S_{li} + ∑_{i,k} \frac{R_{ik}(R_{ik} − 1)}{2}S_{ki}^{2} .

Now, sgcc_{m}(P) depends only on the isomorphism P̂ : G_{A} → G_{B}, and the map P ↦ P̂ induces an isomorphism π_{1}(RS(ℤ, A)) → Aut(s_{A}). It follows that with this identification, modulo the set sgcc_{m}(Aut(s_{A})), the relative sign-gyration number sgcc_{m}(P) is uniquely determined by the pair (A, B) and can be computed from any path P from A to B in RS(ℤ).

4. The counterexample

We will produce primitive matrices A and B satisfying the following conditions:

(1) tr(A^{2}) = 0,

(2) sgcc_{2} vanishes on Aut(s_{A}), and

(3) there is a path in RS(ℤ) from A to B with nonzero sgcc_{2}.

If P were a strong shift equivalence over ℤ^{+} from A to B, then sgcc_{2}(P) would vanish, since SGCC_{2} = sgcc_{2} over ℤ^{+} and the subshift σ_{A} has no points of period 1 or 2. Therefore A and B are not strong shift equivalent over ℤ^{+}.

It remains to produce the matrices and check the conditions. Define

S = (\begin{matrix}2 & 2 & 2 & 1 & 3 & 0 & 0 \\ 1 & 2 & 2 & 1 & 3 & 0 & 0 \\ 1 & 1 & 2 & 1 & 3 & 0 & 0 \\ 1 & 1 & 1 & 1 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 4 & 5 & 6 & 3 & 10 & 0 & 0 \\ 4 & 5 & 6 & 3 & 0 & 1 & 0 \end{matrix}) ,

R = (\begin{matrix}−1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & −1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & −1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & −1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}) ,

A = (\begin{matrix}0 & 0 & 1 & 1 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 & 3 & 0 & 0 \\ 0 & 1 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 1 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 10 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 \end{matrix}) ,

B = (\begin{matrix}0 & 0 & 1 & 1 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 4 & 5 & 6 & 3 & 10 & 0 & 0 \\ 4 & 5 & 6 & 3 & 0 & 1 & 0 \end{matrix}) .

Then the matrices A and B are primitive; A = SR, B = RS; and tr(A^{2}) = 0. The condition sgcc_{2}(R, S) ≠ 0 can be checked with a simple program (for example, the Maple program mentioned in §5). It remains to check that sgcc_{2} vanishes on Aut(s_{A}). Here |det(A)| = 1, so Aut(s_{A}) may be identified with C(A), the centralizer of A in GL(7, ℤ). The characteristic polynomial p of A is irreducible, so C(A) ⊂ ℚ[A] and ℚ[A] is isomorphic to the algebraic number field ℚ[t]/p(t) under the isomorphism [t] ↦ A. This identifies C(A) with a subgroup of the units group U of the algebraic integers of this field. The only torsion elements of U are 1 and −1. Our program checks sgcc_{2}(−I) = 0. A PARI computer calculation gives the following system of fundamental units for U:

f_{1} = t,

f_{2} = \frac{1}{3}(38t^{6} + 2t^{5} − t^{4} − 872t^{3} − 1108t^{2} − 1309t − 713),

f_{3} = \frac{1}{3}(842t^{6} + 5072t^{5} − 6847t^{4} − 46061t^{3} − 34930t^{2} − 52216t + 2878),

\begin{matrix}f_{4} = \frac{1}{3}(4260971t^{6} − 3124108t^{5} + 2290532t^{4} − 99681839t^{3} − 46221667t^{2} \\ −106722952t + 5811547). \end{matrix}

Define F_{i} = f_{i}(A). Because C(A) corresponds to a proper subgroup of U, the matrices F_{i} are not all integral. However, the five matrices −I, A, F_{2}F_{3}, F_{3}F_{4}, (F_{2})^{3} do have integral entries and generate a group of index 3 in U. Therefore these matrices generate all of C(A). For each of these matrices M, we check that sgcc_{2} vanishes on the edge (R, S) = (M, M^{−1}A). This finishes the proof.

5. Remarks

1. The extension sgcc_{m} of [3] can be simplified, the worry about integral matrices can be avoided by working over more general rings, and in checking, the dependence on PARI can be avoided. These things are explained in the full paper.

2. We have tried for a number of years to find both a suitable obstruction to the irreducible Williams Conjecture and a realizing example. The obstruction we could finally realize should have been obvious from our automorphisms paper [3] with Jack Wagoner, but actually we only noticed it when we tried to simplify more complicated invariants. Our development of forms and heuristics to search for an actual example is too complicated to recapitulate; in the end, the example derived from perturbing block forms involving the example (4.1) of [3].

3. Our example could be checked without a computer by a human being who is unusually accurate and takes delight in arithmetic. We don’t know, though, that it is feasible by hand to actually find the units in the first place in a given degree 7 number field.

4. For a short Maple program to compute the required sgcc_{2}, go to MAPPRO at http://www.ams.org/era/1997-03-16/S1079-6762-97-00032-2/html/MAPPRO.

Acknowledgment

This strategy for finding a counterexample and the theory of the invariant were developed by Jack Wagoner unknown to us and prior to our independent discovery of this theory. We thank Mike Boyle and Jack Wagoner for help with the exposition.

References

1. K. H. Kim and F. W. Roush, Williams’s conjecture is false for reducible subshifts, J. Amer. Math. Soc. 5 (1992), 213–215. MR 92j:54055

2. , Williams’s conjecture is false for irreducible subshifts, to appear in Annals of Mathematics.

3. K. H. Kim, F. W. Roush, and J. Wagoner, Automorphisms of the dimension group and gyration numbers, J. Amer. Math. Soc. 5 (1992), 191–212. MR 93h:54026

4. D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, 1995. MR 97a:58050

5. R. F. Williams, Classification of subshifts of finite type, Ann. of Math. (2) 98 (1973), 120–153; Errata ibid. 99 (1974), 380–381. MR 48:9769

Mathematics Research Group, Alabama State University, Montgomery, AL 36101-0271, and Korean Academy of Science and Technology

   E-mail address: kkim@asu.alasu.edu

Mathematics Research Group, Alabama State University, Montgomery, AL 36101-0271

   E-mail address: froush@asu.alasu.edu