ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 3, Pages 55–62 (July 30, 1997) S 1079-6762(97)00024-3

INERT ACTIONS ON PERIODIC POINTS

K. H. KIM, F. W. ROUSH, AND J. B. WAGONER

(Communicated by Douglas Lind)

Abstract. The action of inert automorphisms on finite sets of periodic points of mixing subshifts of finite type is characterized in terms of the sign-gyration-compatibility condition. The main technique used is variable length coding combined with a “nonnegative algebraic K-theory” formulation of state splitting and merging. One application gives a counterexample to the Finite Order Generation Conjecture by producing examples of infinite order inert automorphisms of mixing subshifts of finite type which are not products of finite order automorphisms.

Introduction, main results, and applications

Subshifts of finite type (X_{A}, σ_{A}) constructed from a nonnegative integral matrices A appear in a number of areas ranging from smooth dynamical systems to coding and information theory. See [LM] for a comprehensive introduction to these model dynamical systems and to the field of symbolic dynamics in general. The automorphism group Aut(σ_{A}) of (X_{A}, σ_{A}) consists of those homeomorphisms of X_{A} which commute with the basic shift homeomorphism σ_{A} : X_{A} ⟶ X_{A}. The first systematic study of Aut(σ_{A}) appeared in [He], and it has subsequently been studied in a number of papers. For example, see [BF], [BK1], [BLR], [KR1], [KRW1]. In general, Aut(σ_{A}) is a huge countable group. It contains copies of the direct sum of any countable collection of finite groups and is highly nonabelian. It contains a copy of the free abelian group on countably many generators. It contains copies of the fundamental groups of closed, 2-dimensional surfaces. It is residually finite, and therefore does not contain a divisible group. See [BLR]. The group Aut(σ_{A}) is interesting both in its own right and for its relation to other questions in symbolic dynamics. For example, present understanding of the fundamental classification problem for subshifts of finite type is closely related to Aut(σ_{A}). See [B], [KRW1], [KR2], [W].

One way to study Aut(σ_{A}) is through representations of it to simpler groups, and there are currently two such representations which play a key role; namely, the periodic point and periodic orbit representations and the dimension group representation.

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

Received by the editors October 25, 1996.

1991 Mathematics Subject Classification. Primary 54H20, 57S99, 20F99.

The first two authors were partially supported by NSF Grants DMS 8820201 and DMS 9405004.

The last author was partially supported by NSF Grants DMS 8801333, DMS 9102959, and DMS 9322498.

Let P_{k}^{•} = P_{k}^{•}(A) denote the periodic points of period exactly k. Let P_{k} = P_{k}(A) denote the disjoint union of P_{l}^{•} = P_{l}^{•}(A) for 1 ≤ l ≤ k. Let Aut(σ_{A}|P_{k}^{•}) denote the group of permutations of P_{k}^{•} which commute with σ_{A}. Similarly, let Aut(σ_{A}|P_{k}) denote the group of permutations of P_{k} which commute with σ_{A}. Then as in [BLR, Section 7] we have the periodic point representations

π_{A,k}^{•} : Aut(σ_{A}) ⟶ Aut(σ_{A}|P_{k}^{•})

and

π_{A,k} : Aut(σ_{A}) ⟶ Aut(σ_{A}|P_{k}).

Also discussed in [BLR, Section 7] are the closely related periodic orbit permutation representations

ρ_{A,k,l} : Aut(σ_{A}) ⟶ ⨁_{r=k}^{l} P erm(σ_{A} orbits of length r)

for k ≤ l. Computing the images of π_{A,k} and ρ_{A,k,l} is a basic problem. If (X_{A}, σ_{A}) is a primitive subshift of finite type, it is known from [BLR, 7.6] that ρ_{A,k,l} is onto for k sufficiently large. On the other hand, an example where (X_{A}, σ_{A}) is primitive and π_{A,1} = π_{A,1}^{•} = ρ_{A,1,1} is not onto is given in [KRW1, 4.3]. In Application 1 of our results below, we will show that in a number of cases the image of π_{A,k} can be effectively determined for k sufficiently large. This is relevant to the problem of classifying imbeddings of one shift into another of larger entropy as discussed in [BK2].

The periodic point representations gave rise to the Boyle-Krieger sign and gyration number homomorphisms

OS_{A,k} : Aut(σ_{A}) ⟶ Aut(σ_{A}|P_{k}^{•}) ⟶ Z/2, k ≥ 1,

and

GY_{A,k} : Aut(σ_{A}) ⟶ Aut(σ_{A}|P_{k}^{•}) ⟶ Z/k, k ≥ 2,

which were used in [BK1] to study involutions in Aut(σ_{A}). The orbit sign number homomorphism OS_{A,k} is simply the sign of the permutation induced on the orbits of length k by an automorphism. The gyration number homomorphism GY_{A,k} is a measure of how automorphisms move orbits of length k parallel to themselves.

The dimension group representation

δ_{A} : Aut(σ_{A}) ⟶ Aut(s_{A})

introduced by Krieger is essentially a matrix group representation which can be defined dynamically as in [BLR] or more algebraically as in [W]. The group Aut(s_{A}) of order preserving automorphisms of the dimension group is generally much simpler than Aut(σ_{A}). It is often a torsion free, finitely generated abelian group. So typically, much of the complexity of Aut(σ_{A}) lies in the subgroup Inert(σ_{A}) of inert automorphisms which is defined to be the kernel of δ_{A}. Application 2 below gives counterexamples to the FOG Conjecture about Inert(σ_{A}).

It turns out that the sign and gyration number homomorphisms are related to the dimension group representation through the so-called SGCC homomorphisms named after the sign-gyration-compatibility-condition which arose in the fundamental paper [BK1]. For k ≥ 2, we have the SGCC homomorphisms

SGCC_{A,k} : Aut(σ_{A}) ⟶ Aut(σ_{A}|P_{k}) ⟶ Z/k

given in [KRW1], [W] by the formula

SGCC_{A,k} = GY_{A,k} + ∑_{i>0} OS_{A,k/2^{i}}

where we take OS_{A,k/2^{i}} = 0 whenever k/2^{i} is not an integer and where, for k even, we consider Z/2 as the subgroup {0, k/2} of Z/k. In particular, SGCC_{A,k} = GY_{A,k} whenever k is odd, and

SGCC_{A,2} = GY_{A,2} + OS_{A,1}.

For simplicity of notation we shall usually just write GY_{k} = GY_{A,k} , OS_{k} = OS_{A,k}, and SGCC_{k} = SGCC_{A,k}. The relationship between the sign and gyration homomorphisms OS_{k} and GY_{k} and the dimension group homomorphism δ_{A} is that SGCC_{k} factors through δ_{A}. See [KRW1]. We therefore know that

SGCC_{k}(α) = 0 whenever α lies in Inert(σ_{A}).

This paper announces the characterization of the action of inert automorphisms on the periodic points P_{k}(A) for sufficiently large k, thereby computing the image of π_{A,k} restricted to the inert subgroup Inert(σ_{A}). Details are available in the paper [KRW2]. The principal result is

Main Theorem. Assume that A is primitive and k ≥ 2 is a positive integer such that for every n ≥ k there is at least one periodic point of period exactly n. Let α be an element of Aut(σ_{A}|P_{k}). Then there is an automorphism β in Inert(σ_{A}) satisfying α = β|P_{k} iff SGCC_{r}(α) = 0 for every 2 ≤ r ≤ k.

This is a corollary of the following three theorems.

Theorem A. Assume that A is primitive and 2 ≤ n ≤ p. Let α be an element of Aut(σ_{A}|P_{n}^{•}) such that GY_{n}(α) = 0 and such that α induces the identity permutation on orbits of length n. Then there is an automorphism β in Inert(σ_{A}) satisfying

β|P_{n}^{•} = α,
β|P_{k}^{•} = Identity, for 1 ≤ k ≤ p and k ≠ n.

Theorem B. Assume that A is primitive and 1 ≤ n ≤ p are positive integers. Let α be an even permutation of the orbits of length n. Then there is an automorphism β in Inert(σ_{A}) satisfying

α  = the permutation induced on orbits of length n by β,
GY_{n}(β) = 0,
β|P_{k}^{•} = Identity, for 1 ≤ k ≤ p and k ≠ n.

Theorem C. Assume that A is primitive and k ≥ 2 is a positive integer such that for every n ≥ k there is at least one periodic point of period exactly n. Let α be in Aut(σ_{A}|P_{k}). Let gy_{r} = GY_{r}(α) for 2 ≤ r ≤ k and let os_{r} = OS_{r}(α) for 1 ≤ r ≤ k. Assume that the sign-gyration-compatibility condition

gy_{r} + ∑_{p>0} os_{r/2^{p}} = 0

holds for 2 ≤ r ≤ k. Then there is an element β in Inert(σ_{A}) such that

GY_{r}(β) = gy_{r} for 2 ≤ r ≤ k,
OS_{r}(β) = os_{r} for 1 ≤ r ≤ k.

Application 1. Computing the image of π_{A,k} for k large. Our three theorems above show how to find generators {α_{1}, …, α_{p}} for the subgroup

π_{A,k}(Inert(σ_{A})) ⊂ Aut(σ_{A}|P_{k})

for large enough k. If we can find a set of elements {β_{1}, …, β_{q}} in Aut(σ_{A}) so that the set {δ_{A}(β_{1}), …, δ_{A}(β_{q})} generates the image of Aut(σ_{A}) under the dimension group representation δ_{A}, then {α_{1}, …, α_{p}, π_{A,k}(β_{1}), …, π_{A,k}(β_{q})} is a set of generators for the subgroup

π_{A,k}(Aut(σ_{A})) ⊂ Aut(σ_{A}|P_{k}).

In other words, if we can find automorphisms which generate the image of the dimension group representation, then we can find generators for the image of π_{A,k} for k large. For example, this applies to the full Bernoulli n-shift (X_{n}, σ_{n}). A set of generators for the image of δ_{n} consists of the automorphisms

σ_{r} × Id_{n/r} : X_{r} × X_{n/r} ⟶ X_{r} × X_{n/r}

where r is a prime divisor of n.

Application 2. FOG Counterexamples. Boyle and Fiebig in [BF] characterized the action of products of finite order inert automorphisms on periodic points of mixing SFT’s. Together with the theorems above, this produces many subshifts of finite type (X_{A}, σ_{A}) having inert automorphisms which are not products of finite order inert automorphisms. One of the simplest examples is where

A = ( \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \end{matrix} ) .

According to Theorem B, the cyclic permutation (123) of the three fixed points is the restriction of an inert automorphism β to the set of fixed points. On the other hand, since (X_{A}, σ_{A}) has no points of period 2 or period 3, [BF] says that any product of finite order inert automorphisms must be the identity on the fixed points. Incidentally, for this example it can be verified as in [BLR, 6.4] that the automorphism group Aut(s_{A}) of the dimension group is a torsion free, finitely generated abelian group. Hence, every finite order element of Aut(σ_{A}) is inert. So β is not even a product of finite order automorphisms.

Heretofore, the big subgroups of infinite order elements in Inert(σ_{A}) were produced using very ingenious variations on the well-known “marker method” which gives rise to products of finite order elements. An interesting problem is to find natural representations of Inert(σ_{A}) into, say, a vector space or a torsion-free group which would detect the new infinite order inert automorphisms.

Polynomial matrices

The key technique we use is to present SFT’s in terms graphs arising from square matrices with nonnegative polynomial entries (variable length coding) and to construct conjugacies between SFT’s from row and column operations on these matrices (as in algebraic K-theory) but with certain natural positivity conditions brought in. A nonnegative polynomial matrix is one with entries in the set tZ^{+}[t] of polynomials in the variable t having nonnegative integer coefficients and zero constant term. If A = (A(i, j)) is a nonnegative polynomial matrix, construct the directed graph, or equivalently, the zero-one matrix A^{#} as follows: The indices i and j will be called the primary vertices of A^{#}. Suppose

A(i, j) = a_{1}t + a_{2}t^{2} + ⋯ + a_{n}t^{n}.

Corresponding to the term a_{k}t^{k} in A(i, j) draw a_{k} simple paths of length k from i to j, each having k edges and k − 1 secondary vertices. By definition, we will let

(X_{A}, σ_{A}) = (X_{A^{#}}, σ_{A^{#}}).

The usual SFT associated to a nonnegative integral matrix A is obtained by the above construction from the nonnegative polynomial matrix tA.

Polynomial matrices turn out to be a very compact and efficacious way of representing SFT’s and their automorphisms. For example, a special case of [BGMY, Theorem 1.7] shows that

det(I − A) = det(I − tA^{#}).

So the Bowen-Lanford formula [Sm] for the zeta function yields

ζ_{A}(t) = ζ_{A^{#}}(t) = \frac{1}{det(I − A)}.

There is a corresponding formula for dimension groups. Namely, there is an isomorphism of Z[t, t^{−1}]-modules

\frac{Z[t, t^{−1}]^{n}}{Image(I − A)} ≅ \frac{Z[t, t^{−1}]^{n^{#}}}{Image(I − tA^{#})}.

This result has also been obtained by M. Boyle.

The polynomial matrix setting provides useful approximation lemmas. Suppose we have a sequence of nonnegative polynomial matrices

A_{m} = B + t^{m}P_{m}

where the entries p(t) = p_{1}t + ⋯ + p_{r}t^{r} of P_{m} satisfy the conditions r ≤ Dm and p_{i} ≤ Cm^{e} for constants e, C, D which are independent of m.

Entropy Limit Lemma. lim_{m→∞} h(A_{m}) = h(B).

Periodic Point Lemma. Let A be a nonnegative polynomial matrix such that A^{#} is primitive. Assume

lim_{m→∞} h(A_{m}) = L < h(A).

Then there is an integer K such that whenever m ≥ K we have

|P_{q}^{•}(A_{m})| ≤ |P_{q}^{•}(A)| for q ≥ m.

We now discuss how the polynomial matrix setting can be used to produce strong shift equivalences and topological conjugacies between SFT’s. If a(t) = ∑_{r} a_{r}t^{r} and b(t) = ∑_{r} b_{r}t^{r} are polynomials, we define a ≤ b iff a_{r} ≤ b_{r} for each r. Let A be an n × n nonnegative polynomial matrix. Fix an entry A(k, l) of A where k ≠ l, and let b denote a polynomial in tZ[t]. Let E_{kl}(b) denote the elementary matrix which is the identity on the diagonal and where the only nonzero entry off the diagonal is b in the kth row and lth column. E_{kl}(b) will be called a positive shear if b ≥ 0. Let the matrix B be defined by one of the following equations:

\begin{aligned}I − B & = & E_{kl}(b)(I − A), \\ I − B & = & (I − A)E_{kl}(b). \end{aligned}

Positive Shear Lemma. Assume that 0 ≤ b ≤ A(k, l). Then B is a nonnegative polynomial matrix and there are topological conjugacies

R_{kl}(b) : (X_{A^{#}}, σ_{A^{#}}) ⟶ (X_{B^{#}}, σ_{B^{#}}),
C_{kl}(b) : (X_{A^{#}}, σ_{A^{#}}) ⟶ (X_{B^{#}}, σ_{B^{#}})

corresponding respectively to the first and second equations above.

This lemma is proved using state splitting and merging [LM]. The relation to algebraic K-theory is that, roughly speaking, state splitting and merging corresponds to elementary row and column operations but with an extra positivity condition imposed. Conjugacies between subshifts of finite type are generated by the positive row and column type conjugacies R_{kl}(b) and C_{kl}(b) together with isomorphisms of graphs. This gives an algebraic formulation to the well-known classification theorem that conjugacies between SFT’s are generated by state splitting and merging together with graph isomorphisms.

Idea of proof

The purpose of this section is to indicate the proof of a special case of Theorem B. Namely, assume that (X_{A}, σ_{A}) is primitive and P_{1}^{•}(A) = {p_{1}, …, p_{r}} for r ≥ 3. Then the cyclic permutation (123) on fixed points may be realized by the action of an inert automorphism. The strategy is to construct certain inert automorphisms of model subshifts of finite type (X_{C}, σ_{C}) corresponding to polynomial matrices C = C_{m} such that

• σ_{C} has exactly three fixed points and no other periodic points of period q for 2 ≤ q ≤ m.

• For m large, h(C) < h(A) and |P_{s}^{•}(C)| ≤ |P_{s}^{•}(A)| for s ≥ m.

• (X_{C}, σ_{C}) has an inert automorphism β inducing (123) on fixed points. Now let X_{B} = X_{C} ∪ {p_{4}, …, p_{r}} and extend β by letting it be the identity on {p_{4}, …, p_{r}}. We then apply the Imbedding Theorem [K] and the Inert Extension Theorem [KR1] to imbed (X_{B}, σ_{B}) into (X_{A}, σ_{A}) and to extend β to an inert automorphism of (X_{A}, σ_{A}) as required.

To construct the model (X_{C}, σ_{C}), we find 6×6 nonnegative polynomial matrices C = C_{m} and D = D_{m} such that

• σ_{C} has exactly three fixed points {μ_{1}, μ_{2}, μ_{3}} and no other periodic points of period q for 2 ≤ q ≤ m.

• Let θ = (12). Then Cθ = θC, θ(μ_{1}) = μ_{2}, and θ(μ_{2}) = μ_{1}.

• δ_{C}(θ) is in the center of Aut(s_{C}).

• σ_{D} has exactly three fixed points {ν_{1}, ν_{2}, ν_{3}} and no other periodic points of period q for 2 ≤ q ≤ m.

• Let ϕ = (23). Then Dϕ = ϕD, ϕ(ν_{2}) = ν_{3}, and ϕ(ν_{3}) = ν_{2}.

• There is a conjugacy γ between (X_{C}, σ_{C}) and (X_{D}, σ_{D}) satisfying γ(μ_{i}) = ν_{i}

for i = 1, 2, 3. Let β = [θ, γϕγ^{−1}]. Then β is inert and is the cycle (123) on {μ_{1}, μ_{2}, μ_{3}}.

Here is the algebraic formulation. We find 6×6 nonnegative polynomial matrices C and D so that

D − I = S(C − I)T (1)

where S and T = S^{t} are certain products of positive shears which give rise to the desired conjugacy γ. S is fixed in advance, and we show that C can be chosen so that Cθ = θC and so that the D defined by (1) is nonnegative and Dϕ = ϕD. This involves solving a set of homogeneous linear equations satisfied by the unknown X = C − I with coefficients which are products of the entries of S. To control the number of low order periodic points, there is a congruence condition which must be satisfied by X modulo t^{m}. We also require that X satisfies a certain congruence condition modulo Δ^{2}, where Δ = t − 1 − t^{m}, as well as an additional nonhomogeneous linear equation

X_{11} − X_{12} = Δ. (2)

This will insure that there is a decomposition of the dimension group

Coker(I − C) ⊗ Q = K_{−} ⊕ K_{+} (3)

as a Q[t, t^{−1}]-module where K_{−} and K_{+} are the −1 and +1 eigenspaces of θ and where K_{−} and K_{+} have relatively prime annihilators. So any Q[t, t^{−1}]-module isomorphism of Coker(I − C) ⊗ Q must preserve (3), and consequently δ_{C}(θ) will be in the center of Aut(s_{C}).

The proof of Theorem A is very similar to that of Theorem B. In both cases, the key step is to construct inert automorphisms of model SFT’s with low entropy and good control over the growth of periodic points. This is done by fixing a priori certain products of positive shears S and T = S^{t}, and then showing how to choose C so that the matrix D defined by

D − I = S(C − I)T

satisfies a symmetry condition. The proof of Theorem C is somewhat different. We first construct a priori nonnegative polynomial matrix models C_{1}, D_{1} and products of shears S_{1}, T_{1} so that

D_{1} − I = S_{1}(C_{1} − I)T_{1} + Y (t^{m}Δ^{2})^{r}

for a certain polynomial Δ which is relatively prime to t^{m}. Then in several steps we enlarge C_{1} to another matrix C satisfing an involution symmetry condition and an appropriate eigenspace determinant condition, and we multiply S_{1} and T_{1} on the left and right respectively by additional products of shears depending on the error term Y (t^{m}Δ^{2})^{r} to obtain new products of shears S and T so that the matrix D defined by

D − I = S(C − I)T

satisfies another involution symmetry condition and the same eigenspace determinant condition and so that S and T satisfy certain positive shear conditions.

Acknowledgement

We would like to thank Mike Boyle and Doug Lind for conversations about this material.

References

[B] M. Boyle, The stochastic shift equivalence conjecture is false, Contemporary Mathematics, Vol. 135, 1992, 107–110. MR 93i:28013

[BF] M. Boyle and U. Fiebig, The action of inert finite order automorphisms on finite subsystems, ETDS 11 (1991), 413–425. MR 92g:58029

[BGMY] L. Block, J. Guckenheimer, M. Misiurewicz, and L.-S. Young, Periodic points and entropy of one dimensional maps, Springer Verlag Lecture Notes in Mathematics No. 819, 1980, pp. 18–34. MR 82j:58097 [BK1] M. Boyle and W. Krieger, Periodic points and automorphisms of the shift, TAMS 302

(1987), 125–149. MR 88g:54065

[BK2] M. Boyle and W. Krieger, Automorphisms and subsystems of the shift, Jour. Reine Angew. Math. 437 (1993), 13–28. MR 95b:54051

[BLR] M. Boyle, D. Lind, and D. Rudolph, The automorphism group of a shift of finite type, TAMS 306 (1988), 71–114. MR 89m:54051

[He] G. Hedlund, Endomorphisms and automorphisms of the shift dynamical systems, Math. Systems Theory 3 (1969), 320–375. MR 41:4510

[K] W. Krieger, On subsystems of topological Markov chains, ETDS 2 (1982), 195–202. MR 85b:28020

[KR1] K. H. Kim and F. W. Roush, On the structure of inert automorphisms of subshifts, Pure Math. Appl. Ser. B 2 (1991), 3–22. MR 94c:58056

[KR2] K. H. Kim and F. W. Roush, Williams’ conjecture is false for reducible subshifts, JAMS 5, no. 1 (1992), 213–215. MR 92j:54055

[KRW1] K. H. Kim, F. W. Roush, and J. B. Wagoner, Automorphisms of the dimension group and gyration numbers, JAMS, 5, no.1 (1992), 191–212. MR 93h:54026

[KRW2] K. H. Kim, F. W. Roush, and J. B. Wagoner, Characterization of inert actions on periodic points , preprint, UC Berkeley, July 1996.

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

[Sm] S. Smale, Differentiable dynamical systems, BAMS 73, no. 6 (1967), 747–847. MR 37:3598

[W] J. B. Wagoner, Classification of subshifts of finite type revisited, Contemporary Mathematics, Vol. 135, 1992, 423–436. MR 93m:20004

Department of Mathematics, Alabama State University, Montgomery, Alabama 36101

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

Department of Mathematics, Alabama State University, Montgomery, Alabama 36101

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

Department of Mathematics, UCB, Berkeley, California 94720

   E-mail address: wagoner@math.berkeley.edu