exampleExample remarkRemark hypothesisHypothesis claimClaim Computing the
Conley Index: a Cautionary TaleKonstantin Mischaikow and Charles Weibel
[][nocite]ex_supplement

# Computing the Conley Index: a Cautionary Tale††thanks: Submitted to the
editors DATE. K.M. was partially supported by the National Science Foundation
under awards DMS-1839294 and HDR TRIPODS award CCF-1934924, DARPA contract
HR0011-16-2-0033, National Institutes of Health award R01 GM126555, and Air
Force Office of Scientific Research under award number FA9550-23-1-0011. K.M.
was also supported by a grant from the Simons Foundation. C. W. was supported
by NSF grant 2001417.

Konstantin Mischaikow Department of Mathematics, Rutgers University, New
Brunswick, NJ<EMAIL_ADDRESS>Charles Weibel Department of
Mathematics, Rutgers University, New Brunswick, NJ<EMAIL_ADDRESS>
###### Abstract

This paper concerns the computation and identification of the (homological)
Conley index over the integers, in the context of discrete dynamical systems
generated by continuous maps. We discuss the significance with respect to
nonlinear dynamics of using integer, as opposed to field, coefficients. We
translate the problem into the language of commutative ring theory. More
precisely, we relate shift equivalence in the category of finitely generated
abelian groups to the classification of ${\mathbb{Z}}[t]$-modules whose
underlying abelian group is given. We provide tools to handle the
classification problem, but also highlight the associated computational
challenges.

###### keywords:

Conley index, Shift equivalence, Localization of modules, Picard group.

68Q25, 68R10, 68U05

##  1 Introduction

This paper concerns the computation and identification of the (homological)
Conley index in the context of a discrete dynamical system generated by a
continuous map $f\colon X\to X$.

The Conley index [9, 27, 22, 30, 12, 21] is a powerful algebraic topological
invariant for the analysis of nonlinear dynamical systems for at least two
reasons. First, it can be computed using finite data, and thus is applicable
in the context of computational or data driven dynamics. Second, there are a
variety of theorems in which knowledge of the Conley index leads to
information about the structure of the dynamics, e.g., existence of nontrivial
invariant sets [9], heteroclinic orbits [10], fixed points [28, 19], periodic
orbits [20], chaotic dynamics [21, 30, 11], etc.

The computation of the Conley index begins with the identification of a pair
of compact sets $P_{0}\subset P_{1}$, called an _index pair_ [27], where for
the sake of simplicity we assume that $f(P_{i})\subset P_{i}$, $i=0,1$. The
(homological) Conley index of the index pair is the shift equivalence class of
the _index map_ , i.e., the induced map on homology

$f_{*}\colon H_{*}(P_{1},P_{0};k)\to H_{*}(P_{1},P_{0};k).$

(See Section 2 for the definition of shift equivalence.) The index is
important because, if $(P_{1},P_{0})$ and $(P^{\prime}_{1},P^{\prime}_{0})$
are index pairs with the property that the maximal invariant sets under $f$ in
$P_{1}\setminus P_{0}$ and $P^{\prime}_{1}\setminus P^{\prime}_{0}$ are the
same, then the associated Conley indices are the same. The converse need not
hold.

Computational identification of index pairs is relatively easy [1, 7, 6], but
highly dependent upon the particular approximation used in the computation.
Therefore, in the context of applications, two related challenges appear.
First, to determine whether $f_{*}\colon H_{*}(P_{1},P_{0};k)\to
H_{*}(P_{1},P_{0};k)$ and $f_{*}\colon
H_{*}(P^{\prime}_{1},P^{\prime}_{0};k)\to
H_{*}(P^{\prime}_{1},P^{\prime}_{0};k)$ induce the same or different shift
equivalence classes, and second, to determine the shift equivalence class of
$f_{*}$ with minimal computational effort. We return to these challenges
below.

Recall that $k[t]$ denotes the ring of formal polynomials with coefficients in
$k$ (see [2]). The starting point for our analysis is the following
observation: a $k$-module $A$ with an endomorphism $\alpha$ may be regarded as
a $k[t]$-module, $M=(A,\alpha)$. Indeed, given a $k[t]$-module $M$,
multiplication by $t$ is an endomorphism of the underlying $k$-module.
Conversely, given an endomorphism $\alpha$ of a $k$-module $A$, we obtain a
$k[t]$-module structure on $A$ by letting $t$ act on $x\in A$ by $t\cdot
x=\alpha(x)$.

Here is our module-theoretic interpretation of shift equivalence; the proof is
given in Section 2.

######  Proposition 1.1.

Let $\alpha\colon A\to A$ and $\beta\colon B\to B$ be endomorphisms of
finitely generated abelian groups, and let $M=(A,\alpha)$ and $N=(B,\beta)$ be
the associated ${\mathbb{Z}}[t]$-modules. Then $\alpha$ and $\beta$ are shift
equivalent (denoted by $\alpha\sim_{s}\beta$) if and only if
$M\left[t^{-1}\right]\cong N\left[t^{-1}\right]$ as
${\mathbb{Z}}\left[t,t^{-1}\right]$-modules.

As a consequence, the issue of whether two index pairs have the same
homological Conley index is decidable, because it reduces to determining
whether ${\mathbb{Z}}[t,t^{-1}]$–modules are isomorphic; see [4].

Returning to the challenge of determining the shift equivalence class, it is
often computationally efficient to first compute $f_{*}\colon
H_{*}(P_{1},P_{0};k)\to H_{*}(P_{1},P_{0};k)$ when $k$ is a field. In this
case it is well known that shift equivalence is completely determined by the
rational canonical form of $f_{*}$, excluding nilpotent blocks, i.e., blocks
with eigenvalue $t=0$. See [18, 7.3–7.5], for example. An efficient rational
canonical form algorithm is due to Storjohann [29] and implemented for Conley
index computations in [6].

However, essential information can be lost if one considers shift equivalence
over fields.

######  Example 1.2.

Consider two invariant sets for a one-dimensional map
$f\colon{\mathbb{R}}\to{\mathbb{R}}$. Let the first invariant set consist of
two unstable hyperbolic fixed points $\left\\{{x_{0},x_{1}}\right\\}$, e.g.,
$f(x_{k})=x_{k}$ and $f^{\prime}(x_{k})=(-1)^{k}2$ for $k=1,2$. Let the second
invariant set consist of an unstable orientation-preserving period two orbit
$\left\\{{y_{0},y_{1}}\right\\}$ where $f(y_{0})=y_{1}$, $f(y_{1})=y_{0}$, and
$(f^{2})^{\prime}(y_{k})=2$. Using the simplest possible index pairs (see
[21]), the associated index maps on $H_{1}$ are

(1) $\begin{pmatrix}1&0\\\
0&-1\end{pmatrix}\quad\text{and}\quad\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},$

respectively. Since the eigenvalues for both these matrices are $\pm 1$, they
are shift equivalent over any field. However, a simple calculation shows that
they are not shift equivalent over ${\mathbb{Z}}$ (see Lemma 3.1 and Example
3.3 for a more general analysis). This example shows that the Conley index can
distinguish between an invariant set consisting of two fixed points and a
period two orbit – clearly a result of interest in dynamical systems – but at
the cost of using integer coefficients.

This raises two questions: how much information concerning the Conley index is
lost by computing with field coefficients, and how difficult is it to compute
with integer coefficients? Complete answers to both questions appear to be
extremely technical, and beyond the needs of current applications. Thus, the
focus of this paper is on providing the reader with hopefully useful insights
on how integer computations could be done, and a sense of the algebraic
challenges that need to be addressed to perform these computations.

To perhaps further whet the reader’s appetite, consider Example 1.2 again. In
Section 3 we will show that every $2\times 2$ matrix with eigenvalues $\pm 1$
is shift equivalent to either
$\left(\genfrac{}{}{0.0pt}{}{1}{0}\genfrac{}{}{0.0pt}{}{0}{-1}\right)$ or
$\left(\genfrac{}{}{0.0pt}{}{0}{1}\genfrac{}{}{0.0pt}{}{1}{0}\right)$, but not
both. Here is the significance of this result. Suppose that the induced map on
homology of the index map is identified as having characteristic polynomial
$x^{n}(x^{2}-1)$. In this case, (1) provides a complete identification of the
homology Conley indices. Unfortunately, as is made clear in this paper, this
kind of identification is difficult in general.

Here is an outline of this paper. Section 2 provides a brief discussion the
Conley index and explains why, for computational reasons, we restrict our
attention to the homological Conley index. The problem of shift equivalence is
then translated into the realm of commutative ring theory and the proof of
Proposition 1.1 is presented. In Section 3 we provide an elementary result in
the setting that the endomorphisms are invertible, and apply it to the matrix
algebra associated with Example 1.2.

The complexity of this result motivates our focus on the case
$M=({\mathbb{Z}}^{2},T)$. We use the form of the characteristic polynomial
$\chi(t)=\det(t\cdot I-T)$ to organize our presentation. In Section 4 we
consider the case where $\chi(t)$ factors into linear terms. If $\chi(t)$ is
irreducible, then the problem of shift equivalence breaks up into two
additional cases: ${\mathbb{Z}}[t]/(\chi)$ is a Dedekind domain, which is
dealt with in Section 5, and ${\mathbb{Z}}[t]/(\chi)$ is not a Dedekind
domain, which is addressed in Section 6. In each of these sections, we provide
a fundamental algebraic technique for identifying classes of shift
equivalence, examples of how this technique can be employed, and a brief
remark highlighting the technical difficulty of considering higher dimensional
cases, i.e., $M=({\mathbb{Z}}^{n},T)$.

We conclude in Section 8 with a brief discussion of shift equivalence in the
setting of finite abelian groups.

##  2 Translation into Algebra

The goal of this section is the proof of Proposition 1.1, which states that
the problem of identifying the shift equivalence class of a
${\mathbb{Z}}[t]$-module $M$ (represented by an endomorphism $\alpha$ of the
underlying abelian group) is equivalent to identifying the isomorphism class
of the related module $M[t^{-1}]$. We begin by reviewing the necessary
concepts and notation.

######  Definition 2.1.

In any fixed category, endomorphisms $\alpha\colon A\to A$ and $\beta\colon
B\to B$ are _shift equivalent_ , written $\alpha\sim_{s}\beta$, if there exist
morphisms $r\colon A\to B$, $s\colon B\to A$, and a positive integer
$m\in{\mathbb{Z}}^{+}$ such that

(2) $(i)\ r\circ\alpha=\beta\circ r,\qquad(ii)\ s\circ\beta=\alpha\circ
s,\qquad(iii)\ s\circ r=\alpha^{m},\qquad\text{and}\qquad(iv)\ r\circ
s=\beta^{m}.$

######  Example 2.2.

In the category of free $k$-modules, such as vector spaces over a field $k$,
endomorphisms are represented by square matrices. Square matrices $T_{1}$ and
$T_{2}$ are shift equivalent if there are matrices $R$ and $S$ over $k$ such
that $RT_{1}=T_{2}R$, $ST_{2}=T_{1}S$, $SR=T_{1}^{m}$ and $RS=T_{2}^{m}$.

It is well known that shift equivalence over a field $k$, such as
${\mathbb{Q}}$, is completely determined by the rational canonical form of
$T$, excluding nilpotent blocks, i.e., blocks with eigenvalue $t=0$. In
particular, the nonzero eigenvalues are an invariant; see [18, 7.3–7.5]. This
reflects the fact that finite-dimensional $k[T]$-modules are classified by
their rational canonical forms. Thus if $(M_{1},T_{1})$ and $(M_{2},T_{2})$
are shift equivalent over $k$, their characteristic polynomials
$\chi(t)=\det(t\cdot I-T_{i})$ differ only by powers of $t$ and the $T_{i}$
have the same rational canonical form. An efficient rational canonical form
algorithm is due to Storjohann [29].

### Homotopy theory

The combined work of [30, 12] shows that the most general form of the Conley
index is shift equivalence in the homotopy category of maps on pointed
topological spaces. This implies that shift equivalence of homotopy groups (in
the category of groups) is an invariant of the Conley index. Thus, in this
general setting the issue of whether two index pairs have the same Conley
index requires the ability to decide if two finitely generated groups are
isomorphic. This is known to be impossible; see [2, 7.10]. Therefore, from the
perspective of applications, working on the level of the homotopy Conley index
is not a natural starting point. With this in mind, we focus on the
homological Conley index. Consequently, we are interested in shift equivalence
in the category of finitely generated abelian groups.

Stated more explicitly, let $(P_{1},P_{0})$ and $(Q_{1},Q_{0})$ be index pairs
for continuous maps $f$ and $g$ (it is possible that $f=g$). We are interested
in understanding whether $f_{*}\colon H_{*}(P_{1},P_{0};k)\to
H_{*}(P_{1},P_{0};k)$ and $g_{*}\colon H_{*}(Q_{1},Q_{0};k)\to
H_{*}(Q_{1},Q_{0};k)$ are shift equivalent or not. We leave it to the reader
to check that $f_{*}$ and $g_{*}$ are shift equivalent if and only if
$f_{n}\colon H_{n}(P_{1},P_{0};k)\to H_{n}(P_{1},P_{0};k)$ and $g_{n}\colon
H_{n}(Q_{1},Q_{0};k)\to H_{n}(Q_{1},Q_{0};k)$ are shift equivalent for each
$n$.

We finish our discussion of the Conley index by citing a result of J. Bush [5,
Corollary 4.7] that every $n\times n$ matrix $T$ with integer entries can be
realized as a representative of a Conley index. More precisely, given $T$
there exists a one-dimensional continuous function $f$ and an index pair
$(P_{1},P_{0})$ such that $T$ is shift equivalent over ${\mathbb{Z}}$ to
$f_{1}\colon H_{1}(P_{1},P_{0})\to H_{1}(P_{1},P_{0})$.

Turning to the algebraic formulation of shift equivalence, recall [3] that the
_localization_ $M[t^{-1}]$ of a $k[t]$-module $M$ is the set of equivalence
classes of formal fractions $x/t^{i}$, where $x\in M$, $i\geq 0$, and
$x/t^{i}\equiv y/t^{j}$ if and only if $t^{j+m}x=t^{i+m}y$ for some $m>0$.

######  Proof 2.3 (Proof of Proposition 1.1).

Assume $\alpha\sim_{s}\beta$, and let $r:A\to B$,
$s:B\,{\buildrel\over{\longrightarrow}}\,A$ and $m$ be as in Definition 2.1.
Then $r$ is a $k[t]$-module homomorphism from $M=(A,\alpha)$ to $N=(B,\beta)$,
because for all $x\in A$:

$r(t\cdot x)=r(\alpha(x))=\beta(r(x))=t\cdot r(x).$

The same argument shows that $s$ is a $k[t]$-module homomorphism. The
conditions that $sr=t^{m}$ and $rs=t^{m}$ translate into
$sr(x)=\alpha^{m}(s(x))=t^{m}\cdot x$ and $rs(y)=\beta^{m}(r(y))=t^{m}\cdot
y$. Passing to $M[t^{-1}]$ and $N[t^{-1}]$, this is equivalent to $t^{-m}\cdot
s(r(x))=x$ and $r\cdot(t^{-m}\cdot s)y=y$. Therefore $t^{-m}\cdot s$ is an
inverse of $r$ and $t^{-m}\cdot r$ is an inverse of $s$. Thus $M[t^{-1}]\cong
N[t^{-1}]$.

Now assume that there exists a $k\\!\left[t,t^{-1}\right]$–module isomorphism
$f\colon M\left[t^{-1}\right]\to N\left[t^{-1}\right]$. Because $M$ is
finitely generated, say by $x_{1},...,x_{n}$, there are $d_{i}>0$ and
$y_{i}\in N$ such that $f(x_{i})=y_{i}/t^{d_{i}}$. Let
$d=\max\left\\{{d_{1},\ldots,d_{n}}\right\\}$. Set $r(x)=t^{d}f(x)$ and
observe that $r:M\to N$ is a group homomorphism and $f(x)=r(x)/t^{d}$.
Similarly, the isomorphism $f^{-1}:N\left[t^{-1}\right]\to
M\left[t^{-1}\right]$ has the form $f^{-1}(y)=s(x)/t^{e}$ for some $e>0$. Then
for all $x\in M$ we have $x=f^{-1}f(x)=r(s(x))/t^{d+e}$, i.e.,
$r(s(x))=t^{d+e}x$; similarly we have $s(r(y))=t^{d+e}y$ for all $y\in N$.
Thus $\alpha$ and $\beta$ are shift equivalent.

######  Remark 2.4.

The Bowen–Franks group of $M$ is $M/(1-t)M$; see [18, 7.4.15]. Since this is a
quotient of $M[t^{-1}]$, this invariant is weaker than the invariant we
consider.

As we pointed out in the introduction, most Conley index computations are done
with $k$ chosen to be a field using rational canonical forms, for the sake of
computational efficacy (see [2, Section 14.8]). Even though the worst bounds
on computational complex of homology computations with integer coefficients
are worse than that of fields, computations over the integers are possible.
Thus for the remainder of this paper we assume that $k\cong{\mathbb{Z}}$, and
$M$ is a ${\mathbb{Z}}[t]$-module, finitely generated as an abelian group,
with $t$ acting as an endomorphism of the underlying abelian group.

######  Remark 2.5.

For the sake of simplicity, we will talk about the shift equivalence class of
a ${\mathbb{Z}}[t]$-module $M$, meaning the shift equivalence class of the map
$M\to M$, $m\mapsto tm$. We will say that a ${\mathbb{Z}}[t]$-module $M$ is
finitely generated if it is finitely generated as an abelian group; and that
$M$ is torsionfree if it is torsionfree as an abelian group.

We focus first on ${\mathbb{Z}}[t]$-modules $M$ which are finitely generated
and torsionfree as abelian groups. That is, the underlying abelian group is
${\mathbb{Z}}^{m}$ and $t$ acts by an $m\times m$ integer matrix $T$. As in
Example 2.2, the characteristic polynomial $\chi_{M}(t)=\det(t\cdot I-T)$ is
an invariant in ${\mathbb{Z}}[t]$ up to powers of $t$. The following result
allows us to assume that a torsionfree ${\mathbb{Z}}[t]$-module $M$ has no
$t$-torsion.

Set $M_{\mathrm{nil}}=\\{x\in M:t^{n}x=0,n\gg 0\\}$. Then $M/M_{\mathrm{nil}}$
is also a ${\mathbb{Z}}[t]$-module.

######  Lemma 2.6.

If $M$ is a ${\mathbb{Z}}[t]$-module, finitely generated and torsionfree as an
abelian group, then $M/M_{\mathrm{nil}}$ is torsionfree and
$M[t^{-1}]{\buildrel\cong\over{\to}}M/M_{\mathrm{nil}}[t^{-1}]$.

######  Remark 2.7.

Proposition 1.1 and Lemma 2.6 imply that $(M,t)$ is shift equivalent to
$(M/M_{\mathrm{nil}},t)$.

######  Proof 2.8.

If $x\in M$ and there exists $a\in{\mathbb{Z}}$ such that $ax\in
M_{\mathrm{nil}}$, then $t^{n}(ax)=a(t^{n}x)=0$. Since $M$ is torsionfree this
implies that $t^{n}x=0$ and hence $x\in M_{\mathrm{nil}}$. This implies that
if $x\in M/M_{\mathrm{nil}}$ then $ax\neq 0$ for all $a\neq 0$, i.e.,
$M/M_{\mathrm{nil}}$ is torsionfree as an abelian group.

Finally, since $M_{\mathrm{nil}}$ is finitely generated there is an $m$ such
that $t^{m}\cdot M_{\mathrm{nil}}=0$, and hence the map $s:M\to M$,
$s(x)=t^{m}x$, factors through a map $S:M/M_{\mathrm{nil}}\to M$ with $S\circ
q=t^{m}$, where $q$ is the quotient map $q:M\to M/M_{\mathrm{nil}}$. (See [2,
14.1.6].) Thus $q$ and $S$ form a shift equivalence between $M$ and
$M/M_{\mathrm{nil}}$.

######  Remark 2.9.

$M_{\mathrm{nil}}$ is zero if and only if the determinant of the associated
matrix $T$ is nonzero.

######  Remark 2.10.

As with any finitely generated ${\mathbb{Z}}[t]$-module, $M$ has associated
prime ideals $\wp_{i}$ in ${\mathbb{Z}}[t]$ and submodules $Q_{i}$ of $M$ such
that $0=Q_{0}\cap\cdots\cap Q_{n}$. See [3, 4.20–22]. In this primary
decomposition, the $Q_{i}$ are associated to $\wp_{i}$ in the sense that

$\wp_{i}=\\{f\in{\mathbb{Z}}[t]:f^{n}\cdot M\subset Q_{i}\text{ for }n\gg
0\\}.$

######  Definition 2.11.

Let $M$ be a ${\mathbb{Z}}[t]$-module whose underlying abelian group is
${\mathbb{Z}}^{n}$. Throughout this paper we set $R={\mathbb{Z}}[t]/I$, where
$I$ is the ideal $\\{f\in{\mathbb{Z}}[t]\colon f(x)=0\textrm{ on }M\\}$ of
${\mathbb{Z}}[t]$.

######  Lemma 2.12.

Let $M$ and $I$ be as in Definition 2.11. Then, $M$ is an $R$-module, and $I$
is a principal ideal of ${\mathbb{Z}}[t]$, generated by a monic polynomial.

######  Proof 2.13.

We adopt standard terminology; see [2, 3]. Since $I\cap{\mathbb{Z}}=0$ and $I$
contains the monic polynomial $\chi(t)$, every associated prime of $M$ is
generated by a monic polynomial. Since ${\mathbb{Z}}[t]$ is a unique
factorization domain, we can factor $\chi(t)$ as a product of irreducible
polynomials, and these must be monic. Let $h(t)$ denote the minimal polynomial
in ${\mathbb{Q}}[t]$ of $t$ acting on $M$. Then $h(t)$ is monic and divides
$\chi(t)$; clearing fractions, we may assume $h$ is a primitive polynomial in
${\mathbb{Z}}[t]$, i.e., its coefficients are relatively prime integers. Since
$h$ divides $\chi(t)$ in ${\mathbb{Q}}[t]$, there is a $g(t)$ in
${\mathbb{Z}}[t]$ and a constant $c$ such that $h(t)g(t)=c\chi(t)$; $c$ must
be the greatest common divisor of its coefficients, i.e., the content of $g$.
Replacing $g$ by $g/c$ we have $hg=\chi$. This implies that $h(t)$ is a
product of monics and hence is monic in ${\mathbb{Z}}[t]$.

Conversely, any $R$-module may be considered as a ${\mathbb{Z}}[t]$-module by
letting $f\in{\mathbb{Z}}[t]$ act as its image in $R={\mathbb{Z}}[t]/I$ acts;
this change from $R$-modules to ${\mathbb{Z}}[t]$-modules is called
restriction of scalars [3]. Thus $R$-modules $M$ and $N$ are shift equivalent
if and only if $M[t^{-1}]\cong N[t^{-1}]$ as $R[t^{-1}]$-modules.

######  Remark 2.14.

When $\chi(t)$ is an irreducible polynomial $f$ of degree 2, $M$ is a module
over the 1–dimensional domain $R={\mathbb{Z}}[t]/I$, and the field of
fractions of $R$ is a number field. This case is discussed in Sections 6 and
5.

##  3 Invertible matrices

It is well known that conjugate matrices are shift equivalent: $T$ is shift
equivalent to $RTR^{-1}$ via $R$ and $S=R^{-1}$. Here is a partial converse.
Recall that a matrix $T$ over the integers is invertible if and only if
$\det(T)=\pm 1$.

######  Lemma 3.1.

Suppose that $T_{1}$ is shift equivalent to $T_{2}$ (via $R$ and $S$). If
$T_{1}$ is invertible and $det(T_{2})\neq 0$, then $T_{2}$, $R$ and $S$ are
invertible and $T_{2}=RT_{1}R^{-1}$.

######  Proof 3.2.

The axiom that $SR=T_{1}^{m}$ implies that $R:A\to B$ is an injection and
$S:B\to A$ is a surjection. Therefore, $B\cong R(A)\oplus\ker(S)$ (see [14,
Theorem IV.1.18]). Because $\det(T_{2})\neq 0$, the axiom that $RS=T_{2}^{m}$
implies that $\ker(S)=0$. Hence $R$ and $S$ are invertible and
$S=T_{1}^{m}R^{-1}$. The axiom that $RT_{1}=T_{2}R$ implies that
$T_{2}=RT_{1}R^{-1}$.

We now present a sequence of examples that are consequences of Lemma 3.1; they
are indicative of the types of results obtained in the more challenging
settings discussed in the sections that follow.

The only simple general result that we are aware of is that the $n\times n$
matrices $\pm I_{n}$ are not shift equivalent to any other $n\times n$ matrix
because they are in the center of $GL_{n}({\mathbb{Z}})$. (This follows from
Lemma 3.1.)

######  Example 3.3.

Returning to Example 1.2, we claim that
$P=\left(\genfrac{}{}{0.0pt}{}{0}{1}\genfrac{}{}{0.0pt}{}{1}{0}\right)$ is
shift equivalent to the matrix
$\left(\genfrac{}{}{0.0pt}{}{1}{x}\genfrac{}{}{0.0pt}{}{0}{-1}\right)$ if and
only if $x$ is odd. To see this, conjugate $P$ with
$R=\left(\genfrac{}{}{0.0pt}{}{a}{c}\genfrac{}{}{0.0pt}{}{b}{d}\right)$ (where
$\det(R)=\pm 1$) to get

$\begin{bmatrix}bd-ac&a^{2}-b^{2}\\\ d^{2}-c^{2}&ac-
bd\end{bmatrix}=\begin{bmatrix}1&0\\\ x&-1\end{bmatrix}.$

Solving gives $a=\pm b$, $a(c\pm d)=\pm 1$, $a=\pm 1$ and $x=1\pm 2c$, so $x$
is odd. $P$ is also shift equivalent to
$-P=\left(\genfrac{}{}{0.0pt}{}{0}{-1}\genfrac{}{}{0.0pt}{}{-1}{0}\right)$ via
$R=\left(\genfrac{}{}{0.0pt}{}{-1}{0}\genfrac{}{}{0.0pt}{}{0}{1}\right)$.

A similar argument shows that
$Q=\left(\genfrac{}{}{0.0pt}{}{1}{0}\genfrac{}{}{0.0pt}{}{0}{-1}\right)$ is
shift equivalent to the matrix
$\left(\genfrac{}{}{0.0pt}{}{1}{c}\genfrac{}{}{0.0pt}{}{0}{-1}\right)$ if and
only if $c$ is even, and that $Q\sim_{s}-Q$.

######  Example 3.4.

Suppose that $\chi(t)=t^{2}+1$. Then the rotation matrix
$T=\left(\genfrac{}{}{0.0pt}{}{0}{-1}\genfrac{}{}{0.0pt}{}{1}{0}\right)$ is
shift equivalent to every matrix of the form
$\left(\genfrac{}{}{0.0pt}{}{c}{1+c^{2}}\genfrac{}{}{0.0pt}{}{-1}{-c}\right)$,
via $R=\left(\genfrac{}{}{0.0pt}{}{1}{-c}\genfrac{}{}{0.0pt}{}{0}{-1}\right)$.
In particular, $T\sim_{s}-T$. Similarly, $T$ is shift equivalent to every
matrix of the form
$\left(\genfrac{}{}{0.0pt}{}{c}{1-c^{2}}\genfrac{}{}{0.0pt}{}{+1}{-c}\right)$
and
$\left(\genfrac{}{}{0.0pt}{}{c}{-1}\genfrac{}{}{0.0pt}{}{1+c^{2}}{-c}\right)$.

######  Proposition 3.5.

Every integer matrix $T$ with $\chi(t)=t^{2}-1$ is shift equivalent to either
$P=\left(\genfrac{}{}{0.0pt}{}{0}{1}\genfrac{}{}{0.0pt}{}{1}{0}\right)$ or
$Q=\left(\genfrac{}{}{0.0pt}{}{1}{0}\genfrac{}{}{0.0pt}{}{0}{-1}\right)$.

An alternate proof is given by Example 6.4 below.

######  Proof 3.6.

Let $T(x,u,v)$ denote the matrix
$\left(\genfrac{}{}{0.0pt}{}{x}{v}\genfrac{}{}{0.0pt}{}{u}{-x}\right)$ with
$x^{2}+uv=1$ and $\chi(t)=t^{2}-1$.

We proceed by induction on $|x|$. When $x=0$, we get the matrices $P$ and $-P$
of Example 3.3. When $|x|=1$, we get the triangular matrices of Example 3.3,
which are shift equivalent to either $P$ or $Q$.

Suppose that $|x|\geq 2$. Since $x^{2}-1=-uv$ either $|u|$ or $|v|$ is less
than $|x|$ but not both, and $u$ and $v$ have opposite signs. Conjugating with
$E=\left(\genfrac{}{}{0.0pt}{}{1}{1}\genfrac{}{}{0.0pt}{}{0}{1}\right)$ and
$E^{-1}$ yields

$ETE^{-1}=T(x-u,u,v-u+2x);\quad E^{-1}TE=T(x+u,u,v+u-2x).$

If $|u|<|x|$, either $|x-u|<|x|$ or $|x+u|<|x|$ and we are done. Similarly, if
$|v|<|x|$, conjugating $T$ with
$\left(\genfrac{}{}{0.0pt}{}{1}{0}\genfrac{}{}{0.0pt}{}{-1}{1}\right)$ (resp.,
its inverse) yields $T(x-v,u-v+2x,v)$, respectively, $T(x+v,u+v+2x,v)$, and we
are done in this case as well.

A similar analysis using $T(x,u,v)$ with $uv=1+x^{2}$ shows that every integer
matrix with $\chi(t)=t^{2}+1$ is shift equivalent to the rotation matrix
$T=\left(\genfrac{}{}{0.0pt}{}{0}{-1}\genfrac{}{}{0.0pt}{}{1}{0}\right)$. A
different proof is given in Example 5.5(1) below.

######  Remark 3.7.

Extending Example 1.2 to a periodic $n$ orbit gives rise to an index map whose
associated characteristic polynomial has the form $t^{n}-1$. As is indicated
in Example 7.10, identifying the associated shift equivalence classes over
${\mathbb{Z}}$ is non-trivial.

##  4 Shift equivalence when $\chi(t)$ factors into linear terms

As indicated in the introduction, we shall focus for simplicity on shift
equivalence between $2\times 2$ matrices over ${\mathbb{Z}}$. First, we handle
the easy case, when the characteristic polynomial $\chi(t)$ factors in
${\mathbb{Z}}[t]$, i.e., $\chi(t)=(t-\lambda_{1})(t-\lambda_{2})$, and $T$ is
a lower-triangular matrix.

For $a\in{\mathbb{Z}}$, we write $M_{a}$ for the ${\mathbb{Z}}[t]$-module
which is the abelian group ${\mathbb{Z}}^{2}$ with
$T=\bigl{(}\genfrac{}{}{0.0pt}{}{\lambda_{1}}{a}\genfrac{}{}{0.0pt}{}{0}{\lambda_{2}}\bigr{)}$,
i.e., $t$ acts by $t(x,y)=(\lambda_{1}x,\lambda_{2}y+ax)$. Note that $M_{a}$
is conjugate to both $M_{-a}$ and $({\mathbb{Z}}^{2},T^{\prime})$, with
$T^{\prime}=\bigl{(}\genfrac{}{}{0.0pt}{}{\lambda_{2}}{0}\genfrac{}{}{0.0pt}{}{a}{\lambda_{1}}\bigr{)}$.
Therefore, $T$ is shift equivalent to
$\bigl{(}\genfrac{}{}{0.0pt}{}{\lambda_{1}}{-a}\genfrac{}{}{0.0pt}{}{0}{\lambda_{2}}\bigr{)}$
and $T^{\prime}$.

In general, a ${\mathbb{Z}}[t]$-module map $h\colon M_{a}\to M_{b}$ may be
represented as a map ${\mathbb{Z}}^{2}\to{\mathbb{Z}}^{2}$ given by a lower
triangular matrix
$R=\bigl{(}\genfrac{}{}{0.0pt}{}{r}{u}\genfrac{}{}{0.0pt}{}{0}{s}\bigr{)}$
such that

$\begin{pmatrix}\lambda_{1}&0\\\
b&\lambda_{2}\end{pmatrix}\begin{pmatrix}r&0\\\
u&s\end{pmatrix}=\begin{pmatrix}r&0\\\
u&s\end{pmatrix}\begin{pmatrix}\lambda_{1}&0\\\ a&\lambda_{2}\end{pmatrix},$

i.e,

(3) $\begin{pmatrix}\lambda_{1}r&0\\\
br+\lambda_{2}u&\lambda_{2}s\end{pmatrix}=\begin{pmatrix}r\lambda_{1}&0\\\
as+u\lambda_{1}&s\lambda_{2}\end{pmatrix}.$

Recall from Proposition 1.1 that $M_{a}$ is shift equivalent to $M_{b}$ if and
only if $M_{a}[t^{-1}]$ is isomorphic to $M_{b}[t^{-1}]$. We spend the rest of
this section identifying conditions under which $h[t^{-1}]\colon
M_{a}[t^{-1}]\to M_{b}[t^{-1}]$ provides such an isomorphism.

We first consider the case when $\lambda_{1}=\lambda_{2}$, i.e., when $T$ has
just one Jordan block.

######  Proposition 4.1.

The shift equivalence classes of
$T_{a}=\bigl{(}\genfrac{}{}{0.0pt}{}{\lambda}{a}\genfrac{}{}{0.0pt}{}{0}{\lambda}\bigr{)}$,
$\lambda\neq 0$, are in 1–1 correspondence with the infinite set of positive
integers $a$ such that $a$ is relatively prime to $\lambda$.

######  Proof 4.2.

When $\lambda=\lambda_{1}=\lambda_{2}$, the condition that $h$ be a module map
is that $as=br$. Now $h$ induces an isomorphism $M_{a}[t^{-1}]\cong
M_{b}[t^{-1}]$ if and only if $\det(h)=rs$ is a unit in
${\mathbb{Z}}[\lambda^{-1}]$, i.e., if and only if $r$ and $s$ divide
$\lambda^{n}$ for some $n$. Therefore $M_{a}$ and $M_{b}$ are shift equivalent
if and only if $as=br$, where $r$ and $s$ are integers which become units in
${\mathbb{Z}}[\lambda^{-1}]$.

######  Example 4.3.

If $b$ divides $\lambda^{n}$, the map $M_{1}\,{\buildrel
h\over{\longrightarrow}}\,M_{b}$, $h(x,y)=(x,by)$ induces a shift equivalence.
More generally, if $b=as$ and $s$ divides $\lambda^{n}$, the map $h\colon
M_{a}\to M_{b}$, $(x,y)\mapsto(x,sy)$, is part of a shift equivalence.

######  Proposition 4.4.

The ${\mathbb{Z}}[t]$-modules $M_{a}$ and $M_{b}$ are shift equivalent if and
only if there are integers $r$,$s$ with the same prime factors as
$\lambda_{1}\lambda_{2}$ such that $as-br$ is divisible by
$(\lambda_{1}-\lambda_{2})$.

######  Proof 4.5.

From the matrix equality (3) before Proposition 4.1, we see that a necessary
and sufficient condition is that $as-br=u(\lambda_{2}-\lambda_{1})$, and
$\det(h)=rs$ is a unit in ${\mathbb{Z}}[\lambda_{1}^{-1},\lambda_{2}^{-1}]$.

######  Example 4.6.

If $|\lambda_{1}-\lambda_{2}|=1$ then every $M_{a}$ is shift equivalent to
$M_{0}$, because the condition in Proposition 4.4 is satisfied for all $a,b$.

If $|\lambda_{1}-\lambda_{2}|=2$, either both $\lambda_{i}$ are even, in which
case every $M_{a}$ is shift equivalent to $M_{0}$, or else both $\lambda_{i}$
are odd, in which case there are two shift equivalence classes: $M_{a}$ with
$a$ even, and $M_{a}$ with $a$ odd.

######  Example 4.7.

If $|\lambda_{1}-\lambda_{2}|=p$ is an odd prime, and $\lambda_{1}$ and
$\lambda_{2}$ are prime to $p$, the issue is whether the primes dividing
$\lambda_{1}\lambda_{2}$ generate the cyclic group of units of
${\mathbb{Z}}/p$. In any event, $M_{a}$ is not shift equivalent to $M_{0}$
because $p$ does not divide $\lambda_{1}$ or $\lambda_{2}$.

For example, if $p=17$ then the units of ${\mathbb{Z}}/17$ are cyclic of order
16, generated by 6 with $6^{2}\equiv 2\pmod{17}$. If
$(\lambda_{1},\lambda_{2})=(2,19)$ then there are 4 shift equivalence classes
of $M_{a}$ $(a=0,\pm 6,2).$ If $(\lambda_{1},\lambda_{2})$ is $(1,18)$ or
$(3,20)$ then there are 2 shift equivalence classes of $M_{a}$ (for $a=0,1$).

######  Example 4.8.

If $(\lambda_{1},\lambda_{2})=(1,p)$ with $p$ prime, then $M_{a}\sim_{s}M_{b}$
if and only if $a\equiv\pm b\mod(p-1)$. Thus if $p$ is odd there are $(p-1)/2$
shift equivalence classes; if $p=2$ there is only one shift equivalence class.

Similarly, if $(\lambda_{1},\lambda_{2})=(1,p^{n})$ then $M_{a}\sim_{s}M_{b}$
if and only if $a\equiv\pm p^{k}b\mod(p^{n}-1)$ for some $k<n$.

If $\lambda_{1}$ is relatively prime to $\lambda_{2}$, then the diagonal
matrix $M_{0}$ is not shift equivalent to $M_{a}$ for any nonzero integer $a$.
Indeed, $as\not\equiv 0$ modulo $\lambda_{1}-\lambda_{2}$.

######  Remark 4.9.

Proposition 4.4 can be generalized to any commutative ring $R$. In particular,
given $\lambda_{1},\lambda_{2}\in R$, let $M^{R}_{a}$ denote the $R[t]$-module
which is $R^{2}$ as an $R$-module, with $t$ acting by
$t(x,y)=(\lambda_{1}x,\lambda_{2}y+ax)$. Then, the proof of Proposition 4.4
goes through to show that $M^{R}_{a}$ and $M^{R}_{b}$ are shift equivalent if
and only if $a$ and $b$ differ by a unit of
$R[\lambda_{1}^{-1},\lambda_{2}^{-1}]$, modulo $(\lambda_{1}-\lambda_{2})$.
This will be used with $R={\mathbb{Z}}/p^{n}$ and $\lambda_{1}=\lambda_{2}$ in
Section 8.

When $M={\mathbb{Z}}\oplus{\mathbb{Z}}/m$, every $T:M\to M$ has the form
$\bigl{(}\genfrac{}{}{0.0pt}{}{\lambda_{1}}{a}\genfrac{}{}{0.0pt}{}{0}{\lambda_{2}}\bigr{)}$
for $\lambda_{1}\in{\mathbb{Z}}$ and $a,\lambda_{2}\in{\mathbb{Z}}/m$. Passing
to $M\otimes{\mathbb{Q}}$ and $M/mM$, we see that $\lambda_{1}$ and
$\lambda_{2}$ are shift equivalence invariants. We write $M_{a}$ for this
${\mathbb{Z}}[t]$-module, and $\bar{\lambda}_{1}$ for the image of
$\lambda_{1}$ in ${\mathbb{Z}}/m$. Note that $r$ is a unit in
${\mathbb{Z}}[\lambda_{1}^{-1}]$ if and only if $r\in{\mathbb{Z}}$ has the
same prime factors as $\lambda_{1}$. Using (3), the proof of 4.4 goes through
to show:

######  Corollary 4.10.

When $M={\mathbb{Z}}\oplus{\mathbb{Z}}/m$, and $\lambda_{1}\in{\mathbb{Z}}$,
$\lambda_{2}\in{\mathbb{Z}}/m$ are nonzero, then:

  1. 1.

$M_{a}$ and $M_{b}$ are shift equivalent if and only if there is an
$r\in{\mathbb{Z}}$ with the same prime factors as $\lambda_{1}$, and an
$s\in{\mathbb{Z}}/m$ with the same prime factors as $\lambda_{2}$ so that
$as\equiv br$ modulo $\bar{\lambda}_{1}-\lambda_{2}$.

  2. 2.

If $\lambda_{2}\equiv\lambda_{1}\pmod{m}$ and $\lambda_{1}$ is relatively
prime to $m$, then:
$M_{a}$ and $M_{b}$ are shift equivalent if and only if $a$ and $b$ differ by
a unit of ${\mathbb{Z}}[\lambda_{1}^{-1}]/m$.

  3. 3.

In particular, if $m$ is prime then shift equivalence classes on
$M={\mathbb{Z}}\oplus{\mathbb{Z}}/m$ are completely classified by
$\lambda_{1}\in{\mathbb{Z}}$ and $\lambda_{2}\in{\mathbb{Z}}/m$.

######  Remark 4.11.

Our discussion in this section has focused on shift equivalence between
$2\times 2$ matrices over ${\mathbb{Z}}$ where the characteristic polynomial
$\chi(t)$ factors into linear terms. Using similar arguments, one could
analyze the general case where $2$ Jordan blocks are replaced by $n$ Jordan
blocks. However, the complexity of determining the shift equivalence classes
grows rapidly. Determining $h$ requires satisfying a system of $n(n-1)/2$
Diophantine equations arising from the analogue of (3). For individual
examples these computations can be done, but we do not know of a simple closed
form expression for the number of shift equivalence classes based on the
eigenvalues of $T$.

##  5 Integers in quadratic number fields

Still assuming $T$ is a $2\times 2$ matrix, we now examine the case where the
characteristic polynomial $\chi(T)$ is irreducible. This implies that
$R={\mathbb{Z}}[t]/(\chi)$ is a 1-dimensional integral domain, isomorphic to
${\mathbb{Z}}^{2}$ as an abelian group [2, Chapter 15]. Let $\xi$ denote the
image of $t$ in $R$. Then, $F={\mathbb{Q}}(\xi)$ is a quadratic number field,
i.e., a field with $\dim_{\mathbb{Q}}(F)=2$. Since the minimal polynomial of
$\xi$ is a quadratic polynomial, $(R,\xi)$ is a ${\mathbb{Z}}[t]$-module with
$t$ acting as multiplication by $\xi$.

For the remainder of this section we assume that $R={\mathbb{Z}}[\xi]$ is the
ring of integers in $F={\mathbb{Q}}(\xi)$, and hence that $R$ is a Dedekind
domain. We treat the non-Dedekind case in the next section.

Recall that an ideal $I$ of $R$ is invertible if there is an ideal $J$ such
that $IJ\cong R$ as modules.

######  Definition 5.1.

The Picard group $\operatorname{Pic}(R)$ of a domain $R$ is the set of
isomorphism classes of invertible ideals in $R$. In this group, the product of
$[I]$ and $[J]$ is the class of $[IJ]$.

If $R$ is a Dedekind domain, every nonzero ideal is invertible, and
$\operatorname{Pic}(R)$ is the set of isomorphism classes of nonzero ideals in
$R$. We refer the reader to [31, I.3] for basic facts about Dedekind domains,
such as the fact that torsionfree $R$-modules are completely classified by
their rank and their class in $\operatorname{Pic}(R)$. In particular,
$R$-modules isomorphic to ${\mathbb{Z}}^{2}$ as an abelian group have rank 1.
We refer the reader to [17, Section 5] and [8, Chapter 5] for discussions on
algorithms for computing $\operatorname{Pic}(R)$.

The group $\operatorname{Pic}(R[\xi^{-1}])$ is the quotient of
$\operatorname{Pic}(R)$ by the subgroup generated by the prime ideals of $R$
dividing $\xi$; see [31, Ex.I.3.8]. If all these prime ideals are principal,
$\operatorname{Pic}(R)\cong\operatorname{Pic}(R[\xi^{-1}])$.

Since every nonzero ideal $I$ of $R$ has ${\mathbb{Z}}^{2}$ as its underlying
abelian group, each $(I,\xi)$ has the same minimal polynomial as $(R,\xi)$.
This proves:

######  Theorem 5.2.

Let $R={\mathbb{Z}}[\xi]$ be the ring of integers in a quadratic number field
${\mathbb{Q}}(\xi)$, with $\chi(t)$ the minimal polynomial of $\xi$. Then:

  1. 1.

the elements of $\operatorname{Pic}(R)$ are in 1–1 correspondence with the
isomorphism classes of ${\mathbb{Z}}[t]$-modules $({\mathbb{Z}}^{2},T)$ with
$\chi(T)=0$, with $T$ acting as $\xi$. The Picard class of an ideal $I$ of $R$
corresponds to $(I,\xi)$.

  2. 2.

the elements of $\operatorname{Pic}(R[\xi^{-1}])$ are in 1–1 correspondence
with the shift equivalence classes of matrices $T\in M_{2}({\mathbb{Z}})$ with
$\chi(T)=0$.

In particular, if every prime ideal of $R$ dividing $\xi$ is principal, then
shift equivalence is the same as isomorphism for ideals of $R$.

######  Corollary 5.3.

If $d\not\equiv 1\pmod{4}$ and
$\operatorname{Pic}({\mathbb{Z}}[\sqrt{d},1/\sqrt{d}])=0$, then the shift
equivalence class of a matrix $T\in M_{2}({\mathbb{Z}})$ with ††margin:
tweaked $\chi(T)=t^{2}-d$ is determined by the rational canonical form of $T$.

######  Remark 5.4.

In more concrete terms, two $2\times 2$ matrices $T_{1}$, $T_{2}$ with the
same characteristic polynomial $\chi(t)$ determine ideals $I_{1}$, $I_{2}$ in
$R={\mathbb{Z}}[t]/(\chi)$ that are well defined up to isomorphism. Then
$T_{1}$ and $T_{2}$ are shift equivalent if and only if $I_{1}[t^{-1}]$ and
$I_{2}[t^{-1}]$ are isomorphic as $R[t^{-1}]$-modules.

Suppose that $d$ is a nonzero integer with $|d|$ _square-free_ , and consider
the ring of integers in $F={\mathbb{Q}}(\sqrt{d})$. There are two cases:

Case 1:

If $d\not\equiv 1\pmod{4}$, the ring of integers in ${\mathbb{Q}}(\sqrt{d})$
is $R={\mathbb{Z}}[\sqrt{d}]$. Letting $t$ act as $\xi=\sqrt{d}$, we see from
Theorem 5.2 that shift equivalence classes $({\mathbb{Z}}^{2},T)$ with
characteristic polynomial $t^{2}-d$ are in 1–1 correspondence with elements of
$\operatorname{Pic}(R[1/\sqrt{d}])$.

######  Example 5.5.

1) If $\chi(t)=t^{2}-d$ for $d=2,3,6,7,11,14,19$ or $d=-1,-2,-7$, then
$R={\mathbb{Z}}[\sqrt{d}]$ and $\operatorname{Pic}(R)=0$ [26]111Alternatively,
the reader may determine the order of the Picard group using the command
NumberFieldClassNumber[$\sqrt{d}$] in Mathematica[24]. For these values of
$d$, there is only one shift equivalence class on $({\mathbb{Z}}^{2},T)$ with
$\chi(t)=t^{2}-d$, namely the class of
$T=\left(\genfrac{}{}{0.0pt}{}{0}{1}\genfrac{}{}{0.0pt}{}{d}{0}\right)$;
$({\mathbb{Z}}^{2},T)$ is $(R,\sqrt{d})$.

2) If $\chi(t)=t^{2}+5$, then
$\operatorname{Pic}(R)={\mathbb{Z}}/2=\\{R,I\\}$, where
$R={\mathbb{Z}}[\sqrt{-5}]$ and $I=(2,1+\sqrt{-5})R$. Since $\sqrt{-5}\not\in
I$, it follows that $\operatorname{Pic}(R[(\sqrt{-5})^{-1}])={\mathbb{Z}}/2$
as well. Thus there are two non-isomorphic shift equivalence classes on
${\mathbb{Z}}^{2}$ with characteristic polynomial $t^{2}\\!+5$ : $R$ and $I$.
The matrices for $T$ corresponding to the bases $\\{1,\sqrt{-5}\\}$ and
$\\{2,\sqrt{-5}\\}$ are

$\begin{pmatrix}0&-5\\\
1&0\end{pmatrix}\quad\text{and}\quad\begin{pmatrix}-1&-3\\\ 2&1\end{pmatrix}.$

3) If $d=-6$ or $d=-10$,
$\operatorname{Pic}({\mathbb{Z}}[\sqrt{d}])\cong{\mathbb{Z}}/2$ but
$\operatorname{Pic}({\mathbb{Z}}[\sqrt{d},1/\sqrt{d}])=0$. (See [26, p. 636].)
In this case, the ideal $I=(2,\sqrt{d})$ is not isomorphic to $R$, but the
modules $R$ and $I$ are shift equivalent. The corresponding shift equivalent
matrices are

$\begin{pmatrix}0&d\\\
1&0\end{pmatrix}\quad\text{and}\quad\begin{pmatrix}0&d/2\\\ 2&0\end{pmatrix}.$

Case 2:

If $d\equiv 1\pmod{4}$, the ring of integers in ${\mathbb{Q}}(\sqrt{d})$ is
not ${\mathbb{Z}}[\sqrt{d}]$ but $\overline{R}={\mathbb{Z}}[\omega]$, where
$\omega=\frac{1+\sqrt{d}}{2}$. We let $t$ act as $\xi=\omega$. The minimal
polynomial of $\omega$ is $t^{2}-t-c$, where $c=(d-1)/4$.

By Theorem 5.2, the isomorphism and shift equivalence classes
$({\mathbb{Z}}^{2},T)$ with characteristic polynomial $t^{2}-t-c$ are in 1–1
correspondence with elements of $\operatorname{Pic}(\overline{R})$ and
$\operatorname{Pic}(\overline{R}[1/\omega])$, respectively.

######  Example 5.6.

If $d$ is $5,13,17,21,29$ or $-3,-7,-11,-19$ then
$\overline{R}={\mathbb{Z}}[\omega]$ has $\operatorname{Pic}(\overline{R})=0$,
and hence $\operatorname{Pic}(\overline{R}[1/\omega])=0$, so there is only one
shift equivalence class with characteristic polynomial $t^{2}-t-c$, that of
$\overline{R}$, i.e.,
$T=(\genfrac{}{}{0.0pt}{}{0}{1}\genfrac{}{}{0.0pt}{}{-c}{1})$, where
$c=(d-1)/4$.

######  Remark 5.7.

For irreducible polynomials of degree $\geq 3$, much less is known. For
example, little is known about $R={\mathbb{Z}}[t]/(\chi)$ when $\chi(t)$ is
$t^{n}+5t+10$ (a polynomial which is irreducible by Eisenstein’s criterion).
In general, the computation of $\operatorname{Pic}(R)$ becomes unwieldy when
$n$ gets bigger.

##  6 non-Dedekind subrings of number fields

When $T$ is a $2\times 2$ matrix, and its characteristic polynomial $\chi(t)$
is irreducible, the ring $R={\mathbb{Z}}[t]/(\chi)$ is usually not integrally
closed; it is the integral closure $\overline{R}$ of $R$ that is Dedekind [3].
Recall [3] that an $R$-module $N$ is _invertible_ if there exists an
$R$-module $N^{\prime}$ such that $N\otimes_{R}N^{\prime}\cong R$. If
$R/(\chi)$ is not integrally closed, not every $R$-module isomorphic to
${\mathbb{Z}}^{2}$ is invertible. (For example, $\overline{R}$ is not an
invertible $R$-module.)

In this case, we need to supplement the Picard group
$\operatorname{Pic}(\overline{R})$ in Theorem 5.2 with another invariant: the
conductor ideal. It is defined as
$\mathfrak{c}=\textrm{ann}_{R}(\overline{R}/R)=\\{r\in R\mid r\bar{R}\subseteq
R\\}$, and is the largest ideal of $\overline{R}$ contained in $R$.

Let $M$ and $M^{\prime}$ be $R$-submodules of $\overline{R}$. Since
$\overline{R}$ is ${\mathbb{Z}}^{2}$ as an abelian group, $M$ and $M^{\prime}$
are also ${\mathbb{Z}}^{2}$ as abelian groups. We want invariants to decide
whether $(M,t)$ and $(M^{\prime},t)$ are shift equivalent.

One invariant is the shift equivalence class of
$(M\otimes_{R}\overline{R},t)$. Since $M\otimes_{R}\overline{R}$ is a rank 1
$\overline{R}$-module, it is isomorphic to an ideal $I$ of $\overline{R}$; the
isomorphism $\phi:M\otimes_{R}\overline{R}{\buildrel\cong\over{\to}}I$ is well
defined up to multiplication by a unit of $\overline{R}$. Hence one invariant
of $(M,t)$ is the shift equivalence class of $(I,t)$ over $\overline{R}$.
Given $I$, and an isomorphism
$\phi:M\otimes_{R}\overline{R}{\buildrel\cong\over{\to}}I$, we now show that
the class of $\overline{M}=M/\mathfrak{c}I$ yields another invariant. Since we
can reconstruct $M$ from this data, we get a classification of the $R$-modules
isomorphic to ${\mathbb{Z}}^{2}$.

######  Theorem 6.1.

If $M$ is an $R$-module isomorphic to ${\mathbb{Z}}^{2}$ as an abelian group,
and $\phi:M\otimes_{R}\overline{R}{\buildrel\cong\over{\to}}I$ is given, there
are canonical $R$-module inclusions $\mathfrak{c}I\subseteq M\subseteq I$.
Hence the $R$-modules isomorphic to ${\mathbb{Z}}^{2}$ are classified up to
isomorphism by

  1. 1.

the elements $[I]$ of $\operatorname{Pic}(\overline{R})$, and

  2. 2.

for each $[I]$, the equivalence classes of nonzero $R$-submodules
$\overline{M}=M/\mathfrak{c}I$ of
$I/\mathfrak{c}I\cong\overline{R}/\mathfrak{c}$, where
$\overline{M}\simeq\overline{N}$ if $r\overline{M}=\overline{N}$ or
$r\overline{N}=\overline{M}$ for some element $r$ of $\overline{R}$.

######  Proof 6.2.

Consider the short exact sequence $0\to R\to\overline{R}\to\overline{R}/R\to
0$. Tensoring with $M$ yields the exact sequence

$\operatorname{Tor}^{R}_{1}(M,\overline{R})\to\operatorname{Tor}^{R}_{1}(M,\overline{R}/R)\,{\buildrel\partial\over{\longrightarrow}}\,M\otimes_{R}R\to
M\otimes_{R}\overline{R}\to M\otimes_{R}(\overline{R}/R)\to 0.$

There is a canonical isomorphism $M\cong M\otimes_{R}R$, and the term
$M\otimes_{R}\overline{R}$ is isomorphic to $I$ by $\phi$. Since $M$ is a
torsionfree abelian group, and the $\operatorname{Tor}$-module is torsion, the
map $\partial$ is zero. This gives the inclusion $M\subseteq I$.

Similarly, beginning with the short exact sequence $0\to\mathfrak{c}\to R\to
R/\mathfrak{c}\to 0$ and tensoring with $M$, the same argument yields the
assertion $\mathfrak{c}I\subseteq M$, since

$M\otimes_{R}\mathfrak{c}\cong
M\otimes_{R}({\overline{R}}\otimes_{\overline{R}}\mathfrak{c})\cong(M\otimes_{R}{\overline{R}})\otimes_{\overline{R}}\mathfrak{c}\cong
I\otimes_{\overline{R}}\mathfrak{c}\,{\buildrel\cong\over{\longrightarrow}}\,\mathfrak{c}I.$

This construction depends on the choice of isomorphism
$\phi:M\otimes\overline{R}{\buildrel\cong\over{\to}}I$. If $N=rM$ for nonzero
$r\in\overline{R}$, then $N\cong M$ but $\phi(N)=r\phi(M)$. Since
$\operatorname{Hom}_{\overline{R}}(I,I)=\overline{R}$, the choices of $\phi$
determine the $R/\mathfrak{c}$-module up to multiplication by an element of
$\overline{R}$.

######  Remark 6.3.

Theorem 6.1 provides us with a simple count of an upper bound on the number of
shift equivalence classes, namely, the product of the order of
$\operatorname{Pic}(\overline{R})$, which is readily computable [24], times
the number of isomorphism classes of $R$-modules $M$ with
$\mathfrak{c}\subseteq M\subseteq\overline{R}$, which by Proposition 6.6 is at
most four. Corollary 6.8 indicates that it is at least two.

Our next family of examples concerns $T$ with $T^{2}=dI$, i.e., modules over
$R={\mathbb{Z}}[t]/(t^{2}-d)$ with $T$ acting as $\sqrt{d}$.

######  Example 6.4.

($t^{2}=1$). If $R={\mathbb{Z}}[t]/(t^{2}-1)$, then
$\overline{R}={\mathbb{Z}}\times{\mathbb{Z}}$ and the conductor is
$2\overline{R}$. Theorem 6.1 applies and says that the equivalence classes
correspond to the equivalence classes of the four subgroups of
$\overline{R}/2={\mathbb{Z}}/2\times{\mathbb{Z}}/2$, with $\overline{R}/2$
corresponding to $\overline{R}$ and the subgroup generated by $(1,1)$
corresponding to $R$. The subgroups generated by $(0,1)$ and $(1,0)$
correspond to the $R$-modules ${\mathbb{Z}}\times 2{\mathbb{Z}}$ and to
$2{\mathbb{Z}}\times{\mathbb{Z}}$ of $\overline{R}$, both isomorphic to
$\overline{R}={\mathbb{Z}}\times{\mathbb{Z}}$. Hence there are only two shift
equivalence classes, corresponding to $R$ and $\overline{R}$. This provides an
alternate calculation to Example 3.3.

######  Example 6.5 ($t^{2}=-4$).

In this case $|d|$ is not square-free, so this does not fall under Case 1 of
Section 5. Here $R={\mathbb{Z}}[2i]$, and $\xi=2i$;
$\overline{R}={\mathbb{Z}}[i]$, $\operatorname{Pic}(\overline{R})=0$,
$\mathfrak{c}=2\overline{R}$ and
$\bar{R}/\mathfrak{c}\cong{\mathbb{Z}}/2\times{\mathbb{Z}}/2$. Because there
are 4 nonzero subgroups of $R/\mathfrak{c}$, there are three isomorphism
classes of $R$-modules with $M\otimes_{R}\overline{R}\cong\overline{R}$,
namely $R\cong iR$, $J_{1}=(2,1+i)R$ and $\overline{R}$. (See below for why
$R$ and $J_{1}$ are not isomorphic.) Relative to the ${\mathbb{Z}}$-bases
$\\{1,2i\\}$, $\\{2,1+i\\}$, and $\\{1,i\\}$ of these $R$-modules, $t=2i$ is
represented by the matrices

$\begin{pmatrix}0&1\\\ -4&0\end{pmatrix},\quad\begin{pmatrix}-2&4\\\
-2&2\end{pmatrix}\quad\text{and}\quad\begin{pmatrix}0&2\\\ -2&0\end{pmatrix}.$

As $R[t^{-1}]={\mathbb{Z}}[1/2,i]=\overline{R}[t^{-1}]$, these matrices are
all shift equivalent.

In contrast $t=1+2i$ is represented on $R$, $J_{1}$ and $\overline{R}$ by the
respective matrices

$\begin{pmatrix}1&1\\\ -4&1\end{pmatrix}\quad\begin{pmatrix}-1&2\\\
-2&3\end{pmatrix}\quad\text{and}\quad\begin{pmatrix}1&2\\\ -2&1\end{pmatrix}.$

In contrast $t=1+2i$ is represented on $R$, $J_{1}$ and $\overline{R}$ by the
respective matrices

$\begin{pmatrix}1&1\\\ -4&1\end{pmatrix}\quad\begin{pmatrix}-1&2\\\
-2&3\end{pmatrix}\quad\text{and}\quad\begin{pmatrix}1&2\\\ -2&1\end{pmatrix}.$

These three matrices are in distinct shift equivalent classes, even though
they have the same canonical form and characteristic polynomial $t^{2}-2t+5$.

To see why $R\not\cong J_{1}$, suppose that $f:R\to J_{1}$ has
$f(1)=2x+(1+i)y$, so $f(2i)=-2(2x+2y)+(1+i)(4x+2y)$. The map $f$ is
represented by the matrix

$A=\begin{bmatrix}x&-(2x+2y)\\\ y&4x+2y\end{bmatrix},$

and $\det A=4x^{2}+4xy+2y^{2}\neq\pm 1$. Hence $f$ cannot be an isomorphism.

When $d\equiv 1\pmod{4}$, $d\neq 1$, then the integral closure of
$R={\mathbb{Z}}[\sqrt{d}]$ is $\overline{R}={\mathbb{Z}}[\omega]$,
$\omega=\frac{1+\sqrt{d}}{2}$. It is convenient to use the parameter
$c=(d-1)/4$, as $\omega^{2}-\omega-c=0$.

######  Proposition 6.6 ($t^{2}=d$).

When $d\equiv 1\pmod{4}$, $d\neq 1$, there are up to four isomorphism classes
of $R$-modules $M$ with $\mathfrak{c}\subseteq M\subseteq\overline{R}$,
namely: $R$, $J_{0}=(2,\omega)R$, $J_{1}=(2,1+\omega)R$, and $\overline{R}$.
(Modulo $\mathfrak{c}$, these are the nonzero linear subspaces of
$\overline{R}/\mathfrak{c}$.) Relative to the ${\mathbb{Z}}$-bases
$\\{1,\sqrt{d}\\}$, $\\{2,\omega\\}$, $\\{2,1+\omega\\}$ and $\\{1,\omega\\}$
of $R$, $J_{0}$, $J_{1}$ and $\overline{R}$, multiplication by $t=\sqrt{d}$ is
represented by the matrices

$\biggl{(}\genfrac{}{}{0.0pt}{}{0}{d}\genfrac{}{}{0.0pt}{}{1}{0}\biggr{)},\quad\biggl{(}\genfrac{}{}{0.0pt}{}{-1}{c}\genfrac{}{}{0.0pt}{}{4}{1}\biggr{)},\quad\biggl{(}\genfrac{}{}{0.0pt}{}{-3}{4}\,\genfrac{}{}{0.0pt}{}{c-2}{3}\biggr{)},\quad\textrm{and}\quad\biggl{(}\genfrac{}{}{0.0pt}{}{-1}{2c}\genfrac{}{}{0.0pt}{}{2}{1}\biggr{)}.$

Since $t=\sqrt{d}$ is relatively prime to $\mathfrak{c}$ in $R$, the non-
isomorphic $R$-modules among them remain non-isomorphic modules over
$R[t^{-1}]=R[1/\sqrt{d}]$. That is, they are not shift equivalent.

######  Proof 6.7.

The conductor ideal is $\mathfrak{c}=2\bar{R}=(2,1+\sqrt{d})$, and
$|\overline{R}/\mathfrak{c}|=4$. (If $c$ is even,
$\overline{R}/\mathfrak{c}={\mathbb{F}}_{2}\times{\mathbb{F}}_{2}$, where
${\mathbb{F}}_{2}$ is the field of order 2; if $c$ is odd then
$\overline{R}/\mathfrak{c}$ is the field ${\mathbb{F}}_{4}$ of order 4.)

By Theorem 6.1, there are up to four isomorphism classes of $R$-modules $M$
with $\mathfrak{c}\subseteq M\subseteq\overline{R}$, namely: $R$, $J_{0}$,
$J_{1}$, and $\overline{R}$. Modulo $\mathfrak{c}$, these are the nonzero
linear subspaces of $\overline{R}/\mathfrak{c}$. (If $c$ is even,
$\overline{R}/\mathfrak{c}={\mathbb{F}}_{2}\times{\mathbb{F}}_{2}$, where
${\mathbb{F}}_{2}$ is the field of order 2; if $c$ is odd then
$\overline{R}/\mathfrak{c}$ is the field ${\mathbb{F}}_{4}$ of order 4.)

######  Corollary 6.8.

If $d\equiv 1\pmod{4}$, $d\neq 1$, then $\overline{R}$ is not isomorphic to
$R$, $J_{0}$ or $J_{1}$. Therefore there are at least two shift equivalence
classes.

######  Proof 6.9.

$\overline{R}/\mathfrak{c}$ has 4 elements, while $R/\mathfrak{c}$,
$J_{0}/\mathfrak{c}$ and $J_{1}/\mathfrak{c}$ have only 2 elements. Therefore,
$\overline{R}$ cannot be isomorphic to $R$, $J_{0}$ or $J_{1}$. The conclusion
follows from Proposition 6.6.

Here is a simple example, showing how to apply Proposition 6.6. In the next
section, we develop tools to apply Proposition 6.6 more generally.

######  Example 6.10.

($t^{2}=5,c=1$). The ring of integers in ${\mathbb{Q}}(\sqrt{5})$ is
$\overline{R}={\mathbb{Z}}[\omega]$, $\omega=\frac{1+\sqrt{5}}{2}$ is the
fundamental unit, and $\operatorname{Pic}(\overline{R})=0$. In this case, $R$,
$\omega R\cong J_{0}$ and $\omega^{2}R\cong J_{1}$ are all isomorphic as
$R$-modules. By Theorem 6.1 and Proposition 6.6, there are exactly two shift
equivalence classes with characteristic polynomial $t^{2}-5$. They are
represented by the matrices
$\left(\genfrac{}{}{0.0pt}{}{0}{5}\genfrac{}{}{0.0pt}{}{1}{0}\right)$ and
$\left(\genfrac{}{}{0.0pt}{}{-1}{2}\genfrac{}{}{0.0pt}{}{2}{1}\right)$ (for
the $R$-modules $R$ and $\overline{R}$); the matrices
$\left(\genfrac{}{}{0.0pt}{}{-1}{1}\genfrac{}{}{0.0pt}{}{4}{1}\right)$ and
$\left(\genfrac{}{}{0.0pt}{}{-3}{4}\genfrac{}{}{0.0pt}{}{-1}{3}\right)$ are
both shift equivalent to
$\left(\genfrac{}{}{0.0pt}{}{0}{5}\genfrac{}{}{0.0pt}{}{1}{0}\right)$.

##  7 Finding Isomorphisms

The first step towards exploiting Proposition 6.6 and Corollary 6.8 is to
identify whether or not $R$, $J_{0}$, and $J_{1}$ are isomorphic $R$-modules,
as a function of the nonzero integer $c$.

  1. 1.

Given the ${\mathbb{Z}}$-bases of Proposition 6.6, any $R$-module map $f\colon
R\to J_{0}$ is determined by $f(1)=2x+\omega y$, because
$f(\sqrt{d})=\sqrt{d}\cdot f(1)=2(-x+yc)+\omega(4x+y)$ in $J_{0}$. The map $f$
is represented by $A\in M_{2}({\mathbb{Z}})$ where

$A=\begin{bmatrix}x&-x+cy\\\ y&4x+y\end{bmatrix},$

which is an isomorphism if and only if the quadratic form

(4) $\det(A)=Q(x,y)=4x^{2}+2xy-cy^{2}=\pm 1$

has a solution over ${\mathbb{Z}}$. That is, $R$ and $J_{0}$ are isomorphic
$R$-modules if and only if $Q(x,y)=\pm 1$ has a solution over ${\mathbb{Z}}$.

  2. 2.

Similarly, a map $f\colon R\to J_{1}$ is determined by $f(1)=2x+(1+\omega)y$
and

$f(\sqrt{d})=\sqrt{d}f(1)=[(c-2)y-3x]2+(4x+3y)(1+\omega).$

Thus it is represented by $A\in M_{2}({\mathbb{Z}})$ where

$A=\begin{bmatrix}x&-3x+(c-2)y\\\ y&4x+3y\end{bmatrix}.$

Thus $f$ is an isomorphism if and only if $(x,y)$ is a solution to the
quadratic form

(5) $\det(A)=Q(x,y)=4x^{2}+6xy+(2-c)y^{2}=\pm 1.$

######  Remark 7.1.

$R$ is isomorphic to $J_{0}$ if and only if $R$ is isomorphic to $J_{1}$.
Indeed, a map $f_{0}:R\to J_{0}$ with $f_{0}(1)=2x+\omega y$ is an isomorphism
if and only if the map $f_{1}:R\to J_{1}$ is an isomorphism, where
$f_{1}(1)=2x+(1-\omega)y$.

  3. 3.

We can use a similar computational scheme to compare $J_{0}$ and $J_{1}$,
using the given bases of these $R$-modules. Set

$\displaystyle f_{2}(2)$ $\displaystyle=x\cdot 2+y(1+\omega)$ $\displaystyle
f_{2}(\omega)$ $\displaystyle=u\cdot 2+v(1+\omega)$

Then, regarding $J_{1}$ as a subgroup of $\overline{R}$, we have

$\displaystyle f_{2}(2\omega)=\omega f_{2}(2)$ $\displaystyle=x\cdot
2\omega+y(1+\omega)\omega$
$\displaystyle=2x\omega+y\omega+\frac{y}{4}(1+2\sqrt{d}+d)$
$\displaystyle=2x\omega+y\omega+\frac{y}{4}+\frac{y}{2}\sqrt{d}+\frac{y}{4}(4c+1)$
$\displaystyle=2(x+y)\omega+cy$ $\displaystyle=2(x+y)(1+\omega)+cy-2(x+y)$
$\displaystyle=\left(\left(\frac{c}{2}-1\right)y-x\right)\cdot
2+2(x+y)\cdot(1+\omega)$

Therefore

$\displaystyle v$ $\displaystyle=x+y$ $\displaystyle 4u$
$\displaystyle=(c-2)y-2x.$

The $M_{2}({\mathbb{Z}})$ representation of $f_{2}$ is

$A_{2}=\begin{bmatrix}x&\frac{1}{4}\left((c-2)y-2x\right)\\\
y&x+y\end{bmatrix}.$

Observe that $u$ must be an integer which is equivalent to $(c-2)y-2x=4k$ for
some integer $k$. For $f_{2}$ to be an isomorphism it must be the case that

$\det(A_{2})=Q(x,y)=x^{2}+\frac{3}{2}xy-\frac{c-2}{4}y^{2}=\pm 1,$

which is equivalent to solving

$4x^{2}+6xy-(c-2)y^{2}=\pm 4.$

Using the constraint that $2x=(c-2)y-4k$ we conclude that $f_{2}$ is an
isomorphism if and only there exist integers $k$ and $y$ that solve

(6) $c(c-2)y^{2}-4(2c-1)ky+16k^{2}=\pm 4.$

######  Lemma 7.2.

If $c$ is even or $c\leq-3$, then $R$ is not isomorphic to $J_{0}$ or $J_{1}$.
If $c\leq-5$, then $J_{0}$ is not isomorphic to $J_{1}$.

If $c=-4$, then $J_{0}$ and $J_{1}$ are isomorphic. It follows from
Proposition 6.6 that there are 3 isomorphism classes of $R$-modules $M$ with
$M\otimes_{R}\overline{R}\cong\overline{R}.$

######  Proof 7.3.

The parity of (4) and (5) shows that if $c$ is even, then there cannot be any
solutions. Applying Mathematica’s FindInstance [25] shows that if $c\leq-3$
then there are no solutions; in fact, the appropriate $Q$ are positive
definite in these ranges.

When $c=-4$, $(x,y)=(1,1)$, $k=2$, defines an isomorphism $J_{0}\cong J_{1}$.

######  Remark 7.4.

Using Mathematica again, we discover that if $c\geq 9$ then $J_{0}\not\cong
J_{1}$, because there are no solutions to (6), and $Q$ is positive definite in
this range. We also see that there appear to be infinitely many values of $c$
for which $J_{0}\cong J_{1}$, and infinitely many values of $c<0$ for which
$J_{0}\not\cong J_{1}$.

######  Example 7.5 ($t^{2}=-15$, $c=-4$).

The ring $\overline{R}={\mathbb{Z}}[\omega]$ of integers in
${\mathbb{Q}}(\sqrt{-15})$ has
$\operatorname{Pic}(\overline{R})={\mathbb{Z}}/2$ on the class of
$I=(2,\omega)\overline{R}$, where $\omega=\frac{1+\sqrt{-15}}{2}$. By Theorem
6.1, Proposition 6.6, Remark 7.1 and Lemma 7.2, $R\not\cong J_{0}$ and
$J_{0}\not\cong J_{1}$. Thus there are 6 non-isomorphic $R$-modules $M$ with
underlying group ${\mathbb{Z}}^{2}$: 3 with
$M\otimes\overline{R}\cong\overline{R}$ and 3 more with
$M\otimes\overline{R}\cong I$.

Since $I[1/\omega]\cong\overline{R}[1/\omega]$, we have
$\operatorname{Pic}(\overline{R}[1/\omega])=0$. As in Proposition 6.6, they
represent the 4 distinct shift equivalence classes with $\chi(t)=t^{2}+15$.

######  Remark 7.6.

When $d<-3$, ${\mathbb{Q}}[\sqrt{d}]$ is an imaginary number field, and the
only units of ${\mathbb{Z}}[\omega]$ are $\pm 1$. When $d>0$, there is a
“fundamental unit” $\eta$ of infinite order, and every unit of
${\mathbb{Z}}[\omega]$ is $\pm\eta^{n}$ for an integer $n$. Fundamental units
can be found using the Mathematica command NumberFieldFundamentalUnits.

######  Example 7.7 ($t^{2}=101,c=25$).

The ring of integers in ${\mathbb{Q}}(\sqrt{101}])$ is
$\overline{R}={\mathbb{Z}}[\omega]$, where $\omega=\frac{1+\sqrt{101}}{2}$ and
$\omega^{2}-\omega-25=0$. Now $\operatorname{Pic}(\overline{R})=0$, and the
fundamental unit is $\eta=10+\sqrt{101}$.

Set $R={\mathbb{Z}}[\sqrt{101}]$, and note that $\eta\in R$. By Theorem 6.1,
Corollary 6.8 and Remark 7.4, there are 4 isomorphism classes of $R$-modules
with underlying group ${\mathbb{Z}}^{2}$. Hence there are 4 shift equivalence
classes of $R$-modules with $t=\sqrt{101}$. For the ${\mathbb{Z}}$-bases of
Proposition 6.6, the matrices are

$\begin{pmatrix}0&1\\\ 101&0\end{pmatrix},\quad\begin{pmatrix}-1&4\\\
25&1\end{pmatrix},\quad\begin{pmatrix}-3&23\\\
4&3\end{pmatrix},\quad\text{and}\quad\begin{pmatrix}-1&2\\\
50&1\end{pmatrix}.$

For every monic irreducible quadratic polynomial $f$ with roots $r,\bar{r}\in
R$, there are 4 isomorphism classes of matrices $T$ acting as $r$. If $r$ is
prime to $\mathfrak{c}=(2,\sqrt{101})R$, these matrices will have 4 distinct
shift equivalence classes. For example, $\eta=10+\sqrt{101}$ is a root of the
polynomial $f(t)=t^{2}-20t-1$. Hence there are 4 distinct shift equivalence
classes of ${\mathbb{Z}}[t]$-modules ${\mathbb{Z}}^{2}$ with $t=\eta$.

We can now recover a well-known result; see [23, p.81]. Set
$J_{0}=(2,\omega)R$.

######  Lemma 7.8.

The matrix
$T=\left(\genfrac{}{}{0.0pt}{}{19}{4}\genfrac{}{}{0.0pt}{}{5}{1}\right)$ is
not shift equivalent to its transpose
$T^{t}=\left(\genfrac{}{}{0.0pt}{}{19}{5}\genfrac{}{}{0.0pt}{}{4}{1}\right)$.

######  Proof 7.9.

The matrix $T$ represents $t=\eta$ acting on the basis $\\{5,-9+\sqrt{101}\\}$
of $J_{0}$, and $T^{t}$ is the matrix of $t=\eta$ acting on the basis
$\\{2,-2+\sqrt{101}\\}$ of $R$. By Theorem 6.1 and Example 7.7, there are 4
shift equivalent classes of $R$-modules with $t=\eta$. Since $R\not\cong
J_{0}$, the ${\mathbb{Z}}[t]$-modules $J_{0}$ and $R$ are not shift
equivalent.

When $\chi(t)$ is a polynomial of degree more than 2, the computational
difficulty explodes. We give a simple example, with 3 Jordan blocks over
${\mathbb{C}}$, to illustrate some of the techniques involved.

######  Example 7.10.

Consider the case $\chi(t)=t^{3}-1$, which is the characteristic polynomial of
both $T$ (the rotation matrix), as well as $T_{2}$ and $T_{3}$:

$T=\begin{pmatrix}0&0&1\\\ 1&0&0\\\ 0&1&0\end{pmatrix}\quad\textrm{and}\qquad
T_{2}=\begin{pmatrix}1&0&0\\\ 0&0&-1\\\
0&1&-1\end{pmatrix}\quad\textrm{and}\qquad T_{3}=\begin{pmatrix}1&1&0\\\
1&-2&-2\\\ 0&-2&1\end{pmatrix}.$

The integral closure of the ring $R={\mathbb{Z}}[t]/(\chi)$ is
$\overline{R}={\mathbb{Z}}\times{\mathbb{Z}}[\omega]$, where $\omega=\root 3
\of{1}$; the map $R\to\overline{R}$ sends $t$ to $(1,\omega)$. Note that
$\mathfrak{c}=(3,\omega-1)\overline{R}$. Since
$R/\mathfrak{c}={\mathbb{F}}_{3}$ and
$\overline{R}/\mathfrak{c}\cong{\mathbb{F}}_{3}\times{\mathbb{F}}_{3}$, the
$R$-modules isomorphic to ${\mathbb{Z}}^{2}$ correspond to the 5 nonzero
${\mathbb{F}}_{3}$-subspaces of $V={\mathbb{F}}_{3}\times{\mathbb{F}}_{3}$.

There are $3$ shift equivalence classes with $\chi(t)=t^{3}-1.$ In more
detail, Theorem 6.1 implies that $V={\mathbb{F}}_{3}\times{\mathbb{F}}_{3}$
corresponds to $\overline{R}$, with matrix $T_{2}$ (for the basis
$\\{(3,0),(0,1),(0,\omega)\\}$), and the diagonal subspace on $(1,1)$
corresponds to $R$, with matrix $T$ (for the basis $\\{1,t,t^{2}\\}$). The two
1-dimensional subspaces of $V$, ${\mathbb{F}}_{3}(1,0)$ and
${\mathbb{F}}_{3}(0,1)$ correspond to the $R$-modules
${\mathbb{Z}}\times(\omega-1){\mathbb{Z}}[\omega]$ and
$3{\mathbb{Z}}\times{\mathbb{Z}}[\omega]$, both isomorphic to $\overline{R}$.
The final 1-dimensional subspace ${\mathbb{F}}_{3}(1,2)$ of $V$ corresponds to
the $R$-submodule $M$ with basis $\\{(2,1),(0,\omega-1),(1,2)\\}$; the
associated matrix is $T_{3}$.

##  8 Shift equivalence over ${\mathbb{Z}}/p^{n}$

We briefly consider shift equivalence of $(M,T)$ when $M$ is a finite
$p$-group, i.e., shift equivalence over $R={\mathbb{Z}}/p^{n}$. The
classification of finite Artinian modules over ${\mathbb{Z}}/p^{n}[t]$ for all
$n$ is equivalent to the classification of finite ($p$-primary) Artinian
modules over ${\mathbb{Z}}_{p}[t]$, where ${\mathbb{Z}}_{p}$ is the $p$-adic
integers [3]. The associated primes over these modules contain $p$ and are in
1–1 correspondence with the prime ideals in ${\mathbb{Z}}/p[t]$, such as
$(p,t-\lambda)$. We can ignore the subgroup $M_{\mathrm{nil}}$ on which $t$
acts nilpotently, as $M_{\mathrm{nil}}$ is shift equivalent to $0$ and $M$ is
shift equivalent to $M/M_{\mathrm{nil}}$; see Lemma 2.6. We therefore restrict
to the case when $t$ is an automorphism of $M$.

We do not know of a complete set of invariants for shift equivalence in this
setting. A partial list can be obtained by observing that $M$ determines
$\overline{M}_{j}:=M/p^{j}M$, so that shift equivalence of $\overline{M}_{j}$
for $j=1,\ldots,n$ gives a family of invariants. To give a sense of the
relevant calculations we note that $\overline{M}_{1}=M/pM$, so the rational
canonical form of $T$ mod $p$ is an invariant of the shift equivalence class
of $M$.

Suppose that $M$ is $({\mathbb{Z}}/p^{n})^{2}$, so $T$ is a $2\times 2$ matrix
over ${\mathbb{Z}}/p^{n}$, with characteristic polynomial $\chi(t)$. Thus
there is either one block (and $M/pM\cong{\mathbb{F}}_{p^{2}}$) or two
1-dimensional blocks (and $M/pM\cong{\mathbb{F}}_{p}^{2}$). The analysis is
governed by the considerations in Section 4.

######  Example 8.1.

Suppose $M_{a}$ is $({\mathbb{Z}}/p^{n})^{2}$ with
$T=\left(\genfrac{}{}{0.0pt}{}{\lambda}{a}\genfrac{}{}{0.0pt}{}{0}{\lambda}\right)$
for some $a\in{\mathbb{Z}}/p^{n}$, and $\lambda$ is not nilpotent (i.e., not
divisible by $p$). Since every element of ${\mathbb{Z}}/p^{n}$ is either a
unit or nilpotent, $\lambda$ must be a unit of ${\mathbb{Z}}/p^{n}$. As in
Proposition 4.1, we see from (3) that $M_{a}$ and $M_{b}$ are shift equivalent
if and only if $as=br$ for units $r,s$, i.e., $a$ and $b$ differ by a unit of
${\mathbb{Z}}/p^{n}$.

Since each nonzero $a\in{\mathbb{Z}}/p^{n}$ is $up^{k}$ for a unit $u$ and a
unique $k$, $0\leq k\leq n-1$, every $M_{a}$ is shift equivalent to exactly
one of $M_{0},M_{1},M_{p},M_{p^{2}},...,M_{p^{n-1}}$.

Arguments similar to those employed in Example 8.1 apply to the general case
when $\chi(t)$ factors as $(t-\lambda_{1})(t-\lambda_{2})$, where
$\lambda_{1}\neq\lambda_{2}$ are elements of ${\mathbb{Z}}/p^{n}$. As in
Proposition 4.4, the classification of shift equivalence classes is more
complicated, as it depends on $\lambda_{1}-\lambda_{2}$. Again, returning to
(3) we see that $M_{a}$ and $M_{b}$ are shift equivalent if and only if $br-
as=u(\lambda_{1}-\lambda_{2})$ for units $r,s\in{\mathbb{Z}}/p^{n}$. Thus, for
example if $(\lambda_{1}-\lambda_{2})=1$, then there is a unique shift
equivalence class since one is free to choose $u=br-as$.

We conclude our cautionary tale with a peek into the jungle of modules over
${\mathbb{Z}}/p^{3}$. Consider the following quotient ring of
${\mathbb{Z}}_{p}[t]$:

$R_{\lambda}={\mathbb{Z}}_{p}[t]/(p^{3},(t-\lambda)^{2},p^{2}(t-\lambda)).$

By [15, 6.1][16, 3.2], $R_{\lambda}$ is “finite-length wild”: any description
of finite $R_{\lambda}$-modules would have to contain a description of all
finite-dimensional modules over finite ${\mathbb{Z}}/p$-algebras. This is
generally considered to be hopeless, in the sense that it is an impractically
complicated computational task. This notion of wildness goes back to [13].

######  Example 8.2.

Consider $M=({\mathbb{Z}}/p^{3})\oplus({\mathbb{Z}}/p^{2})$ with
$t(x,y)=((\lambda+up^{2})x,\lambda y+px)$; $\overline{M}=M_{p}$ does not
recover $u$. In fact, $M$ is a module over the ring $R_{\lambda}$.

##  Appendix A Simple Mathematica Code

The following Mathematica code provides information about the existence or
nonexistence of isomorphisms between $R$, $J_{0}$, and $J_{1}$ as discussed in
Section 7 for $100\leq c\leq 100$.

    For[c = -101, c < 99, c++;
      Print["c=", c, "  R iso J0 ",
        !And[ResourceFunction["EmptyQ"][FindInstance[4x^2 + 2x*y - c*y^2 == 1,
        {x, y}, Integers]],
        ResourceFunction["EmptyQ"][FindInstance[4x^2 + 2x*y - c*y^2 == -1,
        {x, y}, Integers]]],
        "   R iso J1 ",
        !And[ResourceFunction["EmptyQ"][FindInstance[4x^2+6x*y+(2-c)*y^2 == 1,
        {x, y},Integers]],
        ResourceFunction["EmptyQ"][FindInstance[4x^2+6x*y+(2-c)*y^2 == -1,
        {x, y}, Integers]]],
        "   J0 iso J1 ",
        !And[ResourceFunction["EmptyQ"][FindInstance[c*(c-2)*y^2-4*(2*c-1)*k*y+16*k^2 == 4,
        {k, y}, Integers]],
        ResourceFunction["EmptyQ"][FindInstance[c*(c-2)*y^2-4*(2*c-1)*k*y+16*k^2 == -4,
        {k, y}, Integers]]]
      Ψ]
     Ψ]

## Acknowledgments

We would like to thank A. Kontorovich for his assistance with solving the
Diophantine equations discussed in Section 7.

## References

  * [1] Z. Arai, W. Kalies, H. Kokubu, K. Mischaikow, H. Oka, and P. Pilarczyk, A database schema for the analysis of global dynamics of multiparameter systems, SIAM J. Appl. Dyn. Syst., 8 (2009), pp. 757–789, https://doi.org/10.1137/080734935, https://doi-org.proxy.libraries.rutgers.edu/10.1137/080734935.
  * [2] M. Artin, Algebra, Prentice Hall, Inc., Englewood Cliffs, NJ, 1991.
  * [3] M. F. Atiyah and I. G. Macdonald, Introduction to commutative algebra, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969.
  * [4] P. A. Brooksbank and E. M. Luks, Testing isomorphism of modules, J. Algebra, 320 (2008), pp. 4020–4029, https://doi.org/10.1016/j.jalgebra.2008.07.014, https://doi.org/10.1016/j.jalgebra.2008.07.014.
  * [5] J. Bush, Shift equivalence and a combinatorial-topological approach to discrete-time dynamical systems, ProQuest LLC, Ann Arbor, MI, 2015.  Thesis (Ph.D.)–Rutgers The State University of New Jersey - New Brunswick.
  * [6] J. Bush, W. Cowan, S. Harker, and K. Mischaikow, Conley-Morse databases for the angular dynamics of Newton’s method on the plane, SIAM J. Appl. Dyn. Syst., 15 (2016), pp. 736–766, https://doi.org/10.1137/15M1017971, https://doi-org.proxy.libraries.rutgers.edu/10.1137/15M1017971.
  * [7] J. Bush, M. Gameiro, S. Harker, H. Kokubu, K. Mischaikow, I. Obayashi, and P. Pilarczyk, Combinatorial-topological framework for the analysis of global dynamics, CHAOS, 22 (2012), https://doi.org/{10.1063/1.4767672}.
  * [8] H. Cohen, A course in computational algebraic number theory, vol. 138 of Graduate Texts in Mathematics, Springer-Verlag, Berlin, 1993, https://doi.org/10.1007/978-3-662-02945-9, https://doi-org.proxy.libraries.rutgers.edu/10.1007/978-3-662-02945-9.
  * [9] C. Conley, Isolated Invariant Sets and the Morse Index, Regional conference series in mathematics, R.I.:American Mathematical Society, 1978.
  * [10] C. C. Conley and J. A. Smoller, The existence of heteroclinic orbits, and applications, (1975), pp. 511–524. Lecture Notes in Phys., Vol. 38.
  * [11] S. Day and R. Frongillo, Sofic shifts via Conley index theory: computing lower bounds on recurrent dynamics for maps, SIAM J. Appl. Dyn. Syst., 18 (2019), pp. 1610–1642, https://doi.org/10.1137/18M1192007, https://doi-org.proxy.libraries.rutgers.edu/10.1137/18M1192007.
  * [12] J. Franks and D. Richeson, Shift equivalence and the Conley index, Trans. Amer. Math. Soc., 352 (2000), pp. 3305–3322.
  * [13] I. M. Gel’fand and V. A. Ponomarev, Remarks on the classification of a pair of commuting linear transformations in a finite-dimensional space, Funkcional. Anal. i Priložen., 3 (1969), pp. 81–82.
  * [14] T. W. Hungerford, Algebra, vol. 73 of Graduate Texts in Mathematics, Springer-Verlag, New York-Berlin, 1980.  Reprint of the 1974 original.
  * [15] L. Klingler and L. S. Levy, Representation type of commutative Noetherian rings. I. Local wildness, Pacific J. Math., 200 (2001), pp. 345–386, https://doi.org/10.2140/pjm.2001.200.345, https://doi-org.proxy.libraries.rutgers.edu/10.2140/pjm.2001.200.345.
  * [16] L. Klingler, R. Wiegand, and S. Wiegand, Tame–wild dichotomy for commutative noetherian rings — a survey, in Rings, monoids and module theory, vol. 382 of Springer Proceedings in Mathematics & Statistics, Springer, Singapore, 2021.
  * [17] H. W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. (N.S.), 26 (1992), pp. 211–244, https://doi.org/10.1090/S0273-0979-1992-00284-7, https://doi-org.proxy.libraries.rutgers.edu/10.1090/S0273-0979-1992-00284-7.
  * [18] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2021.  Second edition [of 1369092].
  * [19] C. McCord, Mappings and homological properties in the Conley index theory, Ergodic Theory Dynam. Systems, 8∗ (1988), pp. 175–198, https://doi.org/10.1017/S014338570000941X, https://doi-org.proxy.libraries.rutgers.edu/10.1017/S014338570000941X.
  * [20] C. McCord, K. Mischaikow, and M. Mrozek, Zeta functions, periodic trajectories, and the Conley index, J. Differential Equations, 121 (1995), pp. 258–292, https://doi.org/10.1006/jdeq.1995.1129, https://doi.org/10.1006/jdeq.1995.1129.
  * [21] K. Mischaikow and M. Mrozek, Conley index, in Handbook of dynamical systems, Vol. 2, North-Holland, Amsterdam, 2002, pp. 393–460, https://doi.org/10.1016/S1874-575X(02)80030-3, http://dx.doi.org.proxy.libraries.rutgers.edu/10.1016/S1874-575X(02)80030-3.
  * [22] M. Mrozek, Leray functor and cohomological Conley index for discrete dynamical systems, Trans. Amer. Math. Soc., 318 (1990), pp. 149–178, https://doi.org/10.2307/2001233, https://doi-org.proxy.libraries.rutgers.edu/10.2307/2001233.
  * [23] W. Parry and S. Tuncel, Classification problems in ergodic theory, vol. 41 of Statistics: Textbooks and Monographs, Cambridge University Press, Cambridge-New York, 1982.
  * [24] W. Research, NumberFieldClassNumber, Wolfram Language function, 2007, https://reference.wolfram.com/language/ref/NumberFieldClassNumber.html.
  * [25] W. Research, Findinstance.  https://reference.wolfram.com/language/ref/FindInstance.html, 2017.  Accessed: 19-January-2023.
  * [26] P. Ribenboim, Classical theory of algebraic numbers, Universitext, Springer-Verlag, New York, 2001, https://doi.org/10.1007/978-0-387-21690-4, https://doi.org/10.1007/978-0-387-21690-4.
  * [27] J. W. Robbin and D. Salamon, Dynamical systems, shape theory and the Conley index, Ergodic Theory Dynam. Systems, 8∗ (1988), pp. 375–393, https://doi.org/10.1017/S0143385700009494, https://doi.org/10.1017/S0143385700009494.
  * [28] R. Srzednicki, On rest points of dynamical systems, Fund. Math., 126 (1985), pp. 69–81, https://doi.org/10.4064/fm-126-1-69-81, https://doi-org.proxy.libraries.rutgers.edu/10.4064/fm-126-1-69-81.
  * [29] A. Storjohann, An $O(n^{3})$ algorithm for the Frobenius normal form, in Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation (Rostock), ACM, New York, 1998, pp. 101–104, https://doi.org/10.1145/281508.281570, https://doi-org.proxy.libraries.rutgers.edu/10.1145/281508.281570.
  * [30] A. Szymczak, The Conley index and symbolic dynamics, Topology, 35 (1996), pp. 287–299.
  * [31] C. A. Weibel, The $K$-book, vol. 145 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 2013, https://doi.org/10.1090/gsm/145, https://doi-org.proxy.libraries.rutgers.edu/10.1090/gsm/145.  An introduction to algebraic $K$-theory.