ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 5, Pages 91–101 (June 30, 1999) S 1079-6762(99)00066-9

POWERS OF POSITIVE POLYNOMIALS AND CODINGS OF MARKOV CHAINS ONTO BERNOULLI SHIFTS

BRIAN MARCUS AND SELIM TUNCEL

(Communicated by Klaus Schmidt)

Abstract. We give necessary and sufficient conditions for a Markov chain to factor onto a Bernoulli shift (i) as an eventual right-closing factor, (ii) by a right-closing factor map, (iii) by a one-to-one a.e. right-closing factor map, and (iv) by a regular isomorphism. We pass to the setting of polynomials in several variables to represent the Bernoulli shift by a nonnegative polynomial p in several variables and the Markov chain by a matrix A of such polynomials. The necessary and sufficient conditions for each of (i)–(iv) involve only an eigenvector r of A and basic invariants obtained from weights of periodic orbits. The characterizations of (ii)–(iv) are deduced from (i). We formulate (i) as a combinatorial problem, reducing it to certain state-splittings (partitions) of paths of length n. In terms of positive polynomial masses associated with paths, the aim then becomes the construction of partitions so that the masses of the paths in each partition element sum to a multiple of p^{n}, the multiple being prescribed by r. The construction, which we sketch, relies on a description of the terms of p^{n} and on estimates of the relative sizes of the coefficients of p^{n}.

1. Introduction

We will describe in this article several recent results for coding Markov chains onto Bernoulli shifts. Adopting an approach first espoused by Parry and Tuncel, we will associate polynomial matrices to Markov chains and translate the jointly measure-theoretic and topological coding problems into combinatorial ones. Bernoulli shifts will then be represented by polynomials p with nonnegative integral coefficients, and we will find ourselves facing questions about powers of p: We start our exposition with a number of results on the structure and coefficients of large powers of positive polynomials in several variables. This material is isolated in section 2, and readers whose interests lie with powers of polynomials may go directly to section 2. We remark that proofs of the results in section 2 rely, in turn, on ideas from ergodic theory, specifically, the notion of entropy at a weight-per-symbol and the related equilibrium states [MT2].

It is well known from Ornstein’s isomorphism theory [O] that entropy is a complete invariant of measure-theoretic isomorphism for mixing Markov chains. In that result the isomorphism is two-sided, meaning that it and its inverse are allowed to use the entire past and the entire future of a point in order to determine the present coordinate of its image. In a one-sided isomorphism, the isomorphism

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

Received by the editors January 21, 1999.

1991 Mathematics Subject Classification. Primary 28D20; Secondary 11C08, 05A10.

Partially supported by NSF Grant DMS–9622866.

and its inverse are allowed to use the entire past, but none of the future. In [AMT] Markov chains were completely classified up to one-sided isomorphism, via an effective algorithmic procedure. An intermediate notion is regular isomorphism. Here, the isomorphism and its inverse are allowed to use the entire past and a uniformly bounded amount of the future.

Ideas emanating from symbolic dynamics, in particular right-resolving and rightclosing maps of shifts of finite type (see below for definitions), have a strong bearing on regular isomorphism and one-sided isomorphism of Markov chains: If a rightclosing map is one-to-one almost everywhere, then it defines a (rather concrete) regular isomorphism between the shifts with respect to their measures of maximal entropy. More generally, if the shifts of finite type are endowed with Markov measures and the map preserves measure, then we obtain a regular isomorphism between the Markov chains. It was shown in [BT] that two Markov chains are regularly isomorphic if and only if there exists a Markov chain which factors onto each of them by a right-closing map which is one-to-one almost everywhere. Thus, the study of regular isomorphism largely reduces to that of right-closing maps between Markov chains.

Likewise, two Markov chains are one-sidedly isomorphic if and only if there exists a Markov chain which factors onto each of them by a right-resolving map which is one-to-one almost everywhere. This fact serves as the first step of the classification of [AMT]. Right-closing maps form the closure of right-resolving ones under block isomorphism, that is, measure-preserving topological conjugacy.

We will give complete answers to the following questions for an arbitrary Markov chain and a Bernoulli shift.

(1) Does the Markov chain eventually factor onto the Bernoulli shift by rightclosing maps?

(2) Does the Markov chain factor onto the Bernoulli shift by a right-closing map? By a right-closing map which is one-to-one almost everywhere?

(3) Is the Markov chain regularly isomorphic to the Bernoulli shift?

Without consideration of measures or, equivalently, restricting attention to measures of maximal entropy, analogues of (1)–(3) were answered for shifts of finite type in the sequence of papers [M, BMT, A]. It is natural to seek generalizations of these results to Markov chains. The work presented here realizes the generalizations for a Bernoulli image.

Definitions and the relationship between Markov chains and matrices of polynomials are recalled in section 3 below. The answers to (1)–(3) are then presented in section 4. Sections 5 and 6 outline their proofs. Section 5 reduces (1)–(3) to (1) and, for (1), formulates the problem in terms of state-splittings with certain combinatorial properties. Section 6 is concerned with the construction of the desired state-splitting. Details and complete proofs may be found in [MT4] and [MT5].

2. Powers of positive polynomials

Let p be a Laurent polynomial in the variables x_{1}, …, x_{k}. For w =(w_{1}, …, w_{k})∈ ℤ^{k}, write x^{w} = x_{1}^{w_{1}} ⋯ x_{k}^{w_{k}} and denote the coefficient of x^{w} in p by p_{w}. Then p = ∑_{w∈ℤ^{k}} p_{w} x^{w} and p_{w} are nonzero for only finitely many w ∈ ℤ^{k}. Let Log(p) = {w ∈ ℤ^{k} : p_{w} ≠ 0}. The Newton polyhedron W (p) of p is given by the rational convex hull of Log(p). Denote the collection of nontrivial faces of W (p) by F(p).

For F ∈ F(p), let

p_{F} = ∑_{w∈F} p_{w} x^{w},

and think of p_{F} as the F -face of p. Let Δ(p) be the subgroup of ℤ^{k} generated by {a − b : a, b ∈ Log(p)}, and pick any c_{p} ∈ Log(p) to distinguish a coset c_{p} + Δ(p) of Δ(p).

It is easy to see that Log(p^{n}) ⊂ nW (p) ∩ (nc_{p} + Δ(p)). If H ≥ 0 and S ⊂ ℝ^{k}, we use the usual norm and distance in ℝ^{k} to write B(S, H) = {w ∈ ℝ^{k} : dist(w, S) < H}. For F ∈ F(p) we denote by ∂F the boundary of F taken in its affine hull. Equivalently, ∂F is the union of all G ∈ F(p) which are proper subsets of F. We put

Int(p^{n}, H) = (W (p^{n})\B(∂W (p^{n}), H)) ∩ (nc_{p} + Δ(p)).

In other words, Int(p^{n}, H) is the set of elements of nc_{p}+Δ(p) remaining in W (p^{n}) = nW (p) after we remove a band of width H from around the boundary. For p ∈ ℝ^{+}[x_{1}^{±}, …, x_{k}^{±}], we find that there exists H(p) ≥ 0 such that Int(p^{n}, H(p)) ⊂ Log(p^{n}) for all n ∈ ℕ. The following then describes Log(p^{n}) for large n.

Theorem 2.1. Let p ∈ ℝ^{+}[x_{1}^{±}, …, x_{k}^{±}]. Suppose that, for each F ∈ F(p), we have constants K_{F} ≥ H(p_{F}) and D_{F} ≥ 0. Then there exist H_{F} ≥ K_{F}, N ∈ ℕ and finite subsets T (F) ⊂ ℤ^{k} such that T (W (p)) = {0} and

Log(p^{n}) = ⋃_{F ∈F(p)}(Int(p_{F}^{n} , H_{F} + D_{F}) + T (F)) = ⋃_{F ∈F(p)}(Int(p_{F}^{n} , H_{F}) + T (F))

for all n ≥ N.

In particular, other than magnification of the materials used, the sets Log(p^{n}) are built in the same way: For each F ∈ F(p) cut from the lattice Δ(p_{F}) (or its copy nc_{p_{F}} + Δ(p_{F})) exactly |T (F)| pieces of the right size in the shape of W (p_{F}), translate them according to T (F), and glue them together.

The proof of (2.1) is comprised of two stages. The first expresses Log(p^{n}) in terms of a union over facets of W (p). The second refines this by applying an induction based on the (codimension of) the faces of W (p).

Now write R_{k} = ℤ[x_{1}^{±}, …, x_{k}^{±}] and R_{k}^{+} = ℤ^{+}[x_{1}^{±}, …, x_{k}^{±}]. Let p ∈ R_{k}^{+} and, for F ∈ F(p), put c_{F} = c_{p_{F}}. In sections 5 and 6 we will need the following three estimates on the relative sizes of coefficients of p^{n} for large n.

Proposition 2.2. Let p ∈ ℤ^{+}[x_{1}^{±}, …, x_{k}^{±}] and let F be a proper face of W (p). Let L ∈ ℕ and K, ϵ̄_{F} > 0. There exist ϵ_{F} > 0 and N ∈ ℕ such that for a ∈ ℤ^{k} the inequality

(p^{n})_{a+b} ≥ K(p^{n})_{a}

holds whenever n ≥ N, \frac{a}{n} ∈ B(F, ϵ_{F})\B(∂F, ϵ̄_{F}) and b ∈ (Log(p^{L})\ Log(p_{F}^{L})) − Log(p_{F}^{L}).

Proposition 2.3. Let p ∈ ℤ^{+}[x_{1}^{±}, …, x_{k}^{±}] and F ∈ F(p). Let ϵ̄_{F}, θ > 0 and D ∈ ℕ. There exist ϵ_{F} > 0 and N ∈ ℕ such that

|\frac{(p^{n})_{a}/(p^{n})_{a+b}}{(p^{n})_{a+u}/(p^{n})_{a+u+b}} − 1| < θ

whenever n ≥ N and a, b, u ∈ ℤ^{k} are such that a, a + u ∈ Log(p^{n}), b ∈ Δ(p_{F}), \frac{a}{n} ∈ B(F, ϵ_{F})\B(∂F, ϵ̄_{F}), and ∥b∥, ∥u∥ ≤ D.

Proposition 2.4. Let p ∈ ℤ^{+}[x^{±}, …, x_{k}^{±}] and F ∈ F(p). Let ϵ_{F} > 0, l ∈ ℤ and D ∈ ℕ. There exist ϵ_{F} > 0 and K, N ∈ ℕ such that

\frac{1}{K} (p^{n+l})_{a+lc_{F} +b} ≤ (p^{n})_{a} ≤ K(p^{n+l})_{a+lc_{F} +b}

whenever n ≥ N and a, b ∈ ℤ^{k} are such that \frac{a}{n} ∈ B(F, ϵ_{F})\B(∂F, ϵ̄_{F}), b ∈ Δ(p_{F}) and ∥b∥ ≤ D.

Details of (2.1)–(2.4) may be found in [MT4]. In the case of (2.2)–(2.4), the method of proof and the more technical results at its basis may be objects of greater general interest. They involve the notion of entropy at a weight-per-symbol and the corresponding equilibrium states, which are imported from [MT2] and strengthened in the Bernoulli setting: Letting W_{ℝ}(p) denote the real convex hull of Log(p) and d = ∑_{w∈ℤ^{k}} p_{w}, it turns out that the map w ↦ s(w) that sends w ∈ W_{ℝ}(p) to the corresponding equilibrium distribution s(w), which is a probability vector of size d, is C^{1} on W_{ℝ}(p). It is also shown that, for small ϵ_{F} , δ > 0 and large n, multinomial coefficients lying in a δ-ball around w = \frac{a}{n} will estimate (p^{n})_{a} uniformly closely for w ∈ B(F, ϵ_{F})\B(∂F, ϵ̄_{F}). From this common ground, the proof of each of (2.2)– (2.4) is reduced to a calculation involving multinomial coefficients.

As far as we are aware, the F -faces p_{F} were introduced by Handelman [H].

3. Markov chains and polynomial matrices

It is well known that a directed graph G defines a shift of finite type (X_{G}, σ_{G}). A shift-commuting continuous surjection ϕ : X_{G} → X_{H} of shifts of finite type is known as a factor map. The map ϕ is right-closing if left-asymptotic distinct points of X_{G} have distinct images under ϕ. Right-closing maps are bounded-to-one and, assuming G is irreducible, there exists d = d(ϕ) ∈ ℕ, called the degree of ϕ, so that every doubly transitive y ∈ X_{H} has exactly d pre-images. If d = 1, the map ϕ is said to be one-to-one almost everywhere. For these and other basic definitions and facts on shifts of finite type and factor maps, see [LM].

The directed graph G is weighted if, for some multiplicative Abelian group G, each edge e of G is assigned a weight wt_{G}(e) ∈ G. The weight of a path γ = e_{1}e_{2} ⋯ e_{n} is the product wt_{G}(γ) = wt_{G}(e_{1}) ⋯ wt_{G}(e_{n}). Let Γ(G) be the subgroup of G generated by weights of cycles, and let Δ(G) be the subgroup of Γ(G) consisting of ratios wt_{G}(γ)/ wt_{G}(η) of weights of cycles γ, η of the same length. For irreducible G of period d, let γ, η be cycles whose lengths satisfy l(γ) = l(η) + d and use c_{G} = wt_{G}(γ)/ wt_{G}(η) to distinguish a coset c_{G}Δ(G). (For properties of Γ, Δ, cΔ see [PS, MT1].)

The graphs we consider will always be directed, irreducible and, except for a brief spell, weighted by monomials. Such graphs correspond to irreducible matrices A over R_{k}^{+}: Express each entry A(I, J) as a sum (with multiplicity) of monomials, place as many edges from I to J as there are terms in this sum, and bijectively assign the monomials as weights. Confusing A with the associated graph G(A), we write wt_{A}(γ), Γ(A), Δ(A), c_{A}Δ(A) for the objects defined above for G(A). For a G(A)-cycle γ of length l = l(γ), we define the weight-per-symbol of γ to be wps_{A}(γ) = \frac{1}{l} Log(wt_{A}(γ)) ∈ ℚ^{k}. The rational convex hull of \{wps_{A}(γ) : γ cycle of G(A)} is the weight-per-symbol polytope W (A) of A. For x_{1}, …, x_{k} > 0, let β_{A}(x_{1}, …, x_{k}) > 0 be the spectral radius of the nonnegative real-valued matrix A(x_{1}, …, x_{k}). Writing ℝ^{++} for the positive reals, this defines the beta function β_{A} : (ℝ^{++})^{k} → ℝ^{++} of A.

We write (X_{A}, σ_{A}) for the shift of finite type defined by G(A) together with the weights-per-symbol assigned to its periodic orbits. We require finite-to-one factor maps ϕ : X_{A} → X_{B} between such systems to be weight-preserving in that wps_{B}(ϕ(γ)) = wps_{A}(γ) for every periodic orbit γ of (X_{A}, σ_{A}). The (clearly necessary) factor periodic point condition for A, B is the requirement that, for each periodic orbit γ of (X_{A}, σ_{A}), there exist in (X_{B}, σ_{B}) a periodic orbit of the same weight-per-symbol whose period divides that of γ.

Applying the above to p ∈ R_{k}^{+} by viewing it as a 1 × 1 matrix, note that there is a slight clash with the definitions of Γ(p), Δ(p), c_{p}Δ(p) given in section 2, resulting from confusing monomials and their exponents.

Markov chains are traditionally defined by stochastic matrices. Given an irreducible stochastic matrix M, we construct a graph G(M) taking weights in ℝ^{++}: The vertices of G(M) are given by the indexing set of M, and there is an edge of weight M(I, J) from I to J whenever M(I, J) > 0. The shift of finite type (X_{M}, σ_{M}) defined by G(M) and the Markov measure μ_{M} defined by M give us the Markov chain (X_{M}, σ_{M}, μ_{M}). We will write wt_{M}(γ), Γ(M), Δ(M), c_{M}Δ(M) for the objects defined for the weighted graph G(M). For t ∈ ℝ, let β_{M}(t) be the spectral radius of the matrix M^{(t)} with

M^{(t)}(I, J) = \{ \begin{matrix}0 & if M(I, J) = 0, \\ M(I, J)^{t} & if M(I, J) > 0. \end{matrix}

This defines the beta function β_{M} : ℝ → ℝ^{++} of M.

Letting Q also be an irreducible stochastic matrix, we require factor maps between (X_{M}, σ_{M}, μ_{M}) and (X_{Q}, σ_{Q}, μ_{Q}) to be measure-preserving. In particular, (X_{Q}, σ_{Q}, μ_{Q}) is a right-closing factor of (X_{M}, σ_{M}, μ_{M}) if there exists a right-closing map ϕ of the shift of finite type (X_{M}, σ_{M}) onto (X_{Q}, σ_{Q}) such that μ_{M} ∘ϕ^{−1} = μ_{Q}. The Markov chain (X_{Q}, σ_{Q}, μ_{Q}) is a right-closing eventual factor of (X_{M}, σ_{M}, μ_{M}) if (X_{Q}, σ_{Q}^{n}, μ_{Q}) is a right-closing factor of (X_{M}, σ_{M}^{n}, μ_{M}) for all large n.

Suppose the rows of Q are identical, so that (X_{Q}, σ_{Q}, μ_{Q}) is a Bernoulli shift. Also suppose β_{M} = β_{Q}, since this equality is necessary for the coding problems under consideration. Then, by (6.1) of [MT1], Γ(M) ⊂ Γ(Q). Pick a basis a_{1}, …, a_{k} of the finitely generated Abelian subgroup Γ(Q) of ℝ^{++}. Upon conjugating M, Q by suitable diagonal matrices, we obtain matrices whose entries lie in Γ(Q). Hence, each nonzero entry of M, Q can be uniquely expressed as a product of integral powers of a_{1}, …, a_{k}. Replacing each a_{i} by an indeterminate x_{i}, we get from M, Q irreducible matrices A, B over R_{k}^{+}. A finite-to-one factor map ϕ of the shift of finite type (X_{M}, σ_{M}) onto (X_{Q}, σ_{Q}) satisfies μ_{M} ∘ ϕ^{−1} = μ_{Q} if and only if ϕ is a (weight-preserving) factor map of (X_{A}, σ_{A}) onto (X_{B}, σ_{B}). (See section 2 of [T] for details and credits.) Moreover, since the rows of Q are identical, we can put p = ∑_{J} B(I, J) for any row I to identify (X_{B}, σ_{B}) with (X_{p}, σ_{p}).

Thus, we are in the position of having p ∈ R_{k}^{+} and an irreducible R_{k}^{+}-matrix A with β_{A} = p and studying weight-preserving maps of (X_{A}, σ_{A}^{n}) onto (X_{p}, σ_{p}^{n}). The equality β_{A} = p implies that W (A) = W (p), the Newton polyhedron of p. Consider F ∈ F(p). Define a subgraph of G(A) by retaining an edge e of G(A) (and its weight wt_{A}(e)) if and only if there exists a G(A)-cycle γ which contains e and has wps_{A}(γ) ∈ F. The resulting subgraph is nonwandering; that is, it consists only of irreducible components, which we call the F -components of A. The beta function of an F -component either equals p_{F} or it is strictly less than p_{F} on all of (ℝ^{++})^{k}; the F -components in the former category are said to be principal. (See [MT1, T] for the details.) F -components of A will be central to our solutions of (1)–(3) of the introduction. Note that when F = W (p), we have a single (principal) W (p)-component, namely, A itself.

4. The coding results

To formulate the conditions that will feature in the solutions of (1)–(3), let p ∈ R_{k}^{+} and let F be a proper face of W (p). A polynomial q ∈ R_{k} will be said to F -conform to p if there exists n ∈ ℕ so that for some u ∈ ℤ^{k} we have

Log(q) + u ⊂ Log(p^{n}) and (Log(q) + u) ∩ Log(p_{F}^{n}) ≠ ∅;

in this case we will put Log_{F} (q)=Log(q)∩(Log(p_{F}^{n})−u) and q_{F} =∑_{w∈Log_{F} (q)} q_{w}x^{w}. Roughly speaking, F -conformity asks that, at and near F, both the “shape” and the “gap structure” of Log(q) be subordinate to Log(p^{n}). For a group Δ of monomials in R_{k}, we put R(Δ) = {q ∈ R_{k} : Log(q) ⊂ Log(Δ)}.

Let A be an irreducible R_{k}^{+}-matrix with β_{A} = p. By a right eigenvector of A we will mean a nontrivial vector r over R_{k} such that Ar = pr. Our results will require a right eigenvector which satisfies three conditions. The first two are:

(a) The entries of r lie in R_{k}^{+}.

(b) For each proper face F of W (p) and each state I that belongs to an F - component of A, the entry r(I) F -conforms to p.

The existence of a right eigenvector satisfying (a) was proved in [MT3]. For the description of the third condition, let F ∈ F(p), let C be a principal F -component of A, and let A_{C} be the matrix representing C. Using (b), let r_{C} be the vector indexed by the states of C and having r_{C}(I) = r(I)_{F} for I ∈ C. We then find a monomial m and a diagonal matrix D with monomials for its diagonal entries such that p̃_{F} = mp_{F} ∈ R(Δ(p_{F})), Ã_{C} = mDA_{C}D^{−1} is over R(Δ(A_{C})) ⊂ R(Δ(p_{F})), r̃_{C} = Dr_{C} is over R(Δ(p_{F})) and Ã_{C}r̃_{C} = p̃_{F} r̃_{C}. Put R_{p_{F}} = R(Δ(p_{F}))[\frac{1}{p̃}], the ring obtained upon adjoining \frac{1}{p̃} to R(Δ(p_{F})). Letting d denote the period of C, we have the subring R_{A_{C}} = R(Δ(A_{C}))[\frac{1}{p̃^{d}}] of R_{p_{F}}. View R_{p_{F}} as an R_{A_{C}}-module. For a period class C of C, let r̃_{C} be the restriction of r̃_{C} to C and consider the R_{A_{C}}- submodule ⟨r_{C}⟩ of R_{p_{F}} generated by the entries of r̃_{C}. Our third requirement is that ⟨r_{C}⟩ equal R_{p_{F}}:

(c) If F ∈ F(p) and C is a period class of a principal F -component C of A, then the R_{A_{C}}-module ⟨r_{C}⟩ equals R_{p_{F}}.

The following results answer (1)–(3) of the introduction.

Theorem 4.1. Let (X_{M}, σ_{M}, μ_{M}) be a Markov chain and (X_{Q}, σ_{Q}, μ_{Q}) a Bernoulli shift. Then (X_{Q}, σ_{Q}, μ_{Q}) is a right-closing eventual factor of (X_{M}, σ_{M}, μ_{M}) if and only if β_{M} = β_{Q} and, considering the R_{k}^{+}-matrix A and polynomial p ∈ R_{k}^{+} associated with M, Q, there exists a right eigenvector r of A satisfying (a)–(c).

Theorem 4.2. Let (X_{M}, σ_{M}, μ_{M}) be a Markov chain and (X_{Q}, σ_{Q}, μ_{Q}) a Bernoulli shift. Then (X_{Q}, σ_{Q}, μ_{Q}) is a right-closing factor of (X_{M}, σ_{M}, μ_{M}) if and only if β_{M} = β_{Q}, and, considering the R_{k}^{+}-matrix A and polynomial p ∈ R_{k}^{+} associated with M, Q, there exists a right eigenvector r of A satisfying (a)–(c) and the factor periodic point condition holds for A, p. Moreover, (X_{Q}, σ_{Q}, μ_{Q}) is a factor of (X_{M}, σ_{M}, μ_{M}) by a right-closing map of degree 1 if and only if, in addition, M is aperiodic, Δ(M) = Δ(Q) and c_{M}Δ(M) = c_{Q}Δ(Q).

The past σ-algebra A_{M} of (X_{M}, σ_{M}, μ_{M}) is generated by the cylinder sets

[e_{0}, e_{1}, …, e_{l}]_{h} = {x = (x_{n}) ∈ X_{M} : x_{h} = e_{0}, x_{h+1} = e_{1}, …, x_{h+l} = e_{l}}

with l ∈ ℤ^{+}, h ∈ ℤ and h + l ≤ 0. Markov chains (X_{M}, σ_{M}, μ_{M}) and (X_{Q}, σ_{Q}, μ_{Q}) are said to be regularly isomorphic if there exists a measure-theoretic isomorphism Φ : X_{M} → X_{Q} such that Φ^{−1}(A_{Q}) ⊂ σ_{M}^{−N}(A_{M}) and Φ(A_{M}) ⊂ σ_{Q}^{−N}(A_{Q}) for some nonnegative integer N.

Theorem 4.3. Let (X_{M}, σ_{M}, μ_{M}) be a Markov chain and (X_{Q}, σ_{Q}, μ_{Q}) a Bernoulli shift. The following are equivalent.

(i) (X_{M}, σ_{M}, μ_{M}) and (X_{Q}, σ_{Q}, μ_{Q}) are regularly isomorphic. (ii) There exists a Markov chain (X_{R}, σ_{R}, μ_{R}) and right-closing factor maps ϕ :

(X_{R}, σ_{R}, μ_{R}) → (X_{M}, σ_{M}, μ_{M}) and ψ : (X_{R}, σ_{R}, μ_{R}) → (X_{Q}, σ_{Q}, μ_{Q}) of degree 1.

(iii) M is aperiodic, β_{M} = β_{Q}, Δ(M) = Δ(Q), c_{M}Δ(M) = c_{Q}Δ(Q) and, considering the R_{k}^{+}-matrix A and polynomial p ∈ R_{k}^{+} associated with M, Q, there exists a right eigenvector r of A satisfying (a)–(c).

The equivalence of (i) and (ii) of (4.3) is a special case of the main result of [BT]. The equivalence of (ii) and (iii) is deduced from (4.2) with the aid of discrete geometry and techniques adapted from symbolic dynamics.

5. Combinatorial formulation

We have explained that (4.1) and (4.2) may be regarded as statements on rightclosing maps of (X_{A}, σ_{A}^{n}) onto (X_{p}, σ_{p}^{n}). Taking our cues from [BMT, PT], we formulate such maps in terms of state-splittings. (See [LM] for more on statesplittings, which were first employed by Williams.)

Consider an R_{k}^{+}-matrix B. A state-splitting of (X_{B}, σ_{B}) results from a collection of partitions: For every state I of G(B), the set of edges starting at I is partitioned into sets (I, 1), (I, 2), …, (I, ρ(I)). For each (I, i) form a vector α^{(I,i)} indexed by the states of G(B) by letting the Jth entry α^{(I,i)}(J) be given by the sum of the weights wt_{B}(e) of the edges e that belong to (I, i) and terminate at J. The sum ∑_{i=1}^{ρ(I)} α^{(I,i)} then equals the Ith row of B. State-splittings of (X_{B}, σ_{B}) correspond in this way to partitions of rows of B into vectors over R_{k}^{+}, leading us to also speak of (state-)splitting B. Putting B̂((I, i), (J, j)) = α^{(I,i)}(J), the partition elements index a matrix B̂ such that (XB̂, σB̂) is block isomorphic to (X_{B}, σ_{B}).

Fix p ∈ R_{k}^{+} and an irreducible R_{k}^{+}-matrix A with β_{A} = p. When Ar = pr and the vector r is over R_{k}^{+}, we will seek state-splittings of a particular form: Writing each entry r(I) as a sum of monomials

r(I) = ∑_{k=1}^{ρ(I)} x^{w(I,i)},

we will seek to partition the Ith row of A^{n} into ρ(I) vectors α^{(I,i)}, 1 ≤ i ≤ ρ(I), such that α^{(I,i)} · r = x^{w(I,i)}p^{n}. When we have been able to do this, we say that we have a splitting of A^{n} according to r. This notion derives its significance from the following.

Theorem 5.1. Let A be an irreducible R_{k}^{+}-matrix with β_{A} = p ∈ R_{k}^{+}. The following are equivalent.

(i) (X_{p^{n}}, σ_{p^{n}}) is a right-closing factor of (X_{A^{n}}, σ_{A^{n}}) for some n ∈ ℕ. (ii) A has a right eigenvector r over R_{k}^{+} such that, for some N ∈ ℕ, the matrix

A^{N} can be split according to r. (iii) A has a right eigenvector r over R_{k}^{+} such that A^{n} can be split according to r

for all large n. (iv) (X_{p}, σ_{p}) is a right-closing eventual factor of (X_{A}, σ_{A}).

With both (4.1) and (4.2), the necessity of the conditions is quickly established with the aid of (5.1). Theorem (5.1) also enables us to use [A] to deduce from (4.1) the sufficiency of the conditions of (4.2): By (4.1) and (5.1), the conditions of (4.2) provide splittings of A^{n} according to r for all large n. In [A] Ashley shows how to use analogous splittings and the related factor periodic point condition to produce right-closing maps (of the first powers) in the case of shifts of finite type. A right-closing map of (X_{A}, σ_{A}) onto (X_{p}, σ_{p}) is constructed by going through the argument of [A] with our factor periodic point condition and splittings of A^{n}.

Thus, (4.1)–(4.3) reduce to the construction of a state-splitting of A^{n} according to r. This construction takes up much of [MT5] (in the preprint version, 43 Latex pages out of 72). We provide an outline of it.

The right eigenvector r is said to totally conform to p if, in addition to satisfying (a)–(c), it has the property that every entry r(I) F -conforms to p for every proper face F of W (p).

The construction actually employs two state splittings. The first uses (b) and (2.1) to prove:

Proposition 5.2. For n large enough, A^{n} may be state-split in such a way that the resulting matrix Â^{n} has a right eigenvector r̂ which totally conforms to p.

This is followed by the main splitting, outlined in the next section and showing that if a matrix has a totally conforming right eigenvector, then large powers of the matrix can be split according to that eigenvector.

6. The main state-splitting

By (5.1) and (5.2), we may now replace A by a suitable power to assume that r totally conforms to p and that every F -component of A is aperiodic for every F ∈ F(p). Using (a)–(c) and total conformity, pick L ∈ ℤ^{+}, u_{F,J} ∈ ℤ^{k} and, for each principal component C and coset x^{u}Δ(A_{C}) ∈ Δ(p_{F})/Δ(A_{C}), pick c_{C} ∈ Δ(p_{F}), D_{F,J} ∈ Log(Δ(p_{F})) and polynomials q^{(F,u)}(J) ∈ R(Δ(A_{C})) such that:

(1) Log(r(J)) + u_{F,J} ⊂ Log(p^{L}) and Log(r(J)_{F}) + u_{F,J} ⊂ Log(p_{F}^{L}) for every J ∈ S;

(2) for each principal F -component C, the matrix Ã_{C} indexed by (the states of) C and with

Ã_{C}(J, J′) = A_{C}(J, J′) \frac{x^{u_{F,J}} x^{D_{F,J}}}{c_{C} c_{p_{F}} x^{u_{F,J′}} x^{D_{F,J′}}}

is over R(Δ(A_{C}));

(3) ∑_{J∈C} q^{(F,u)}(J) x^{u_{F,J}} x^{D_{F,J}} r(J)_{F} = x^{u}p_{F}^{L} for every F ∈ F(p), principal F - component C and x^{u}Δ(A_{C}) ∈ Δ(p_{F})/Δ(A_{C}).

Denote the starting and terminal states of a G(A)-path γ by s(γ) and t(γ). Let W_{n}(I) be the set of G(A)-paths γ of length n and with s(γ) = I. Let W_{n}(I, J) be the set of γ ∈ W_{n}(I) with t(γ) = J; and W_{n}(I, J, w) the set of γ ∈ W_{n}(I, J) with Log(wt(γ)) = w. For a ∈ Log(r(I)p^{n}), let π(n, a) denote the probability vector of length ρ(I) whose ith entry equals π(n, a, i) = (x^{w(I,i)}p^{n})_{a}/(r(I)p^{n})_{a}. The following lemmas make use of (2.3) and (2.4).

Lemma 6.1. Let θ, ϵ̄_{F} > 0 and D, l ∈ ℤ^{+}. There exist ϵ_{F} > 0 and N ∈ ℕ such that

|π(n + l, a + lc_{F} + b, i)/π(n, a, i) − 1| < θ

whenever n ≥ N, \frac{a}{n} ∈ B(F, ϵ_{F})\B(∂F, ϵ̄_{F}), (p^{n})_{a} ≠ 0, b ∈ Log(Δ(p_{F})) and ∥b∥ ≤ D.

Lemma 6.2. Let F ∈ F(p), ϵ̄_{F} > 0 and D̄ ∈ ℕ. There exist ϵ_{F} > 0 and N, K̄ ∈ ℕ such that, for every n ≥ N and a ∈ ℤ^{k} with \frac{a}{n} ∈ B(F, ϵ_{F})\B(∂F, ϵ̄_{F}), we can find a principal F -component C, J_{1} ∈ C and x^{u}Δ(A_{C}) ∈ Δ(p_{F})/Δ(A_{C}) with

|W_{n}(I, J_{1}, a − u + b − Lc_{F} + u_{F,J_{1}} + D_{F,J_{1}})| ≥ \frac{1}{K̄} (r(I)p^{n})_{a}

whenever b ∈ Log(Δ(A_{C})) and ∥b∥ ≤ D̄.

Define the mass of γ ∈ W_{n}(I) to be mass(γ) = wt(γ) r(t(γ)). For W ⊂ W_{n}(I), let mass(W) equal the sum of mass(γ) over γ ∈ W. Our goal is to partition W_{n}(I) into sets (I, i), 1 ≤ i ≤ ρ(I), so that mass((I, i)) = x^{w(I,i)}p^{n}. We will speak of allocating the elements of W_{n}(I, J, w) according to π(n, w+a), where a ∈ Log(r(J)): What we mean by this is that the number of elements placed in the ith set differs from (the possibly nonintegral) number π(n, w + a, i)|W_{n}(I, J, w)| by less than 1. Condition (1) guarantees that, any time we assign paths from W_{n}(I, J, w) to the ith set, we have w + Log(r(J)) ⊂ Log(r(I)p^{n}).

For the sake of simplicity, we restrict our attention to the case k = 2.

For each F ∈ F(p) and J, fix a_{F,J} ∈ Log(r(J)_{F}). Write a_{J} = a_{W (p),J}. For F ∈ F(p), also fix v_{F} ∈ ℤ^{k} with coprime entries which exposes F by having F · v_{F} = min{W (p) · v_{F} }. Write δ_{F} = min{W (p) · v_{F} } = min{Log(p) · v_{F} } and δ_{F} (J) = min{r(J) · v_{F} }. For F ∈ F(p) and λ ∈ ℤ, let

N_{n}(F, λ) = {a ∈ Log(r(I)p^{n}) : a · v_{F} ≤ δ_{F} (I) + nδ_{F} + λ}.

Recalling k = 2, define N_{n}(λ_{0}) to be the union of N_{n}(F_{0}, λ_{0}) over all vertices F_{0} of W (p) and define N_{n}(λ_{0}, λ_{1}) = N_{n}(λ_{0}) ∪ ⋃_{F_{1}} N_{n}(F_{1}, λ_{1}), where the last union is over all edges F_{1} of W (p). Let W_{n}(F, λ), W_{n}(λ_{0}), W_{n}(λ_{0}, λ_{1}) respectively denote the union of the sets W_{n}(I, J, w) over all (J, w) such that w + Log(r(J)) intersects N_{n}(F, λ), N_{n}(λ_{0}), N_{n}(λ_{0}, λ_{1}). We drop the subscript from our notation when the length is clear from the context.

Consider ξ, D ≥ 0 and a partition of W_{n}(λ_{0}, λ_{1}) into sets P (i), 1 ≤ i ≤ ρ(I), satisfying two conditions:

(i) For every a ∈ N_{n}(λ_{0}, λ_{1}) we have mass(P (i))_{a} = (x^{w(I,i)}p^{n})_{a}. (ii) If W_{n}(I, J, w) ⊂ W_{n}(λ_{0}, λ_{1})\W_{n}(λ_{0} − D, λ_{1} − D), then

1 − ξ ≤ \frac{|W_{n}(I, J, w) ∩ P (i)|}{π(n, w + a_{J}, i)|W_{n}(I, J, w)|} ≤ 1 + ξ.

For a suitable choice of the constant D, we have:

Lemma 6.3. For every small ϵ > 0 there exist ξ ≥ 0 and N ∈ ℕ such that, for any n ≥ N and λ_{0}, λ_{1} > nϵ, the existence of a partition of W_{n}(λ_{0}, λ_{1}) into ρ(I) sets P (i) satisfying (i) and (ii) implies the existence of a partition of W_{n+L}(I) into ρ(I) sets (I, i) such that mass((I, i)) = x^{w(I,i)}p^{n+L}.

Sketch of proof. If W_{n}(I, J, w) is not contained in W_{n}(λ_{0}, λ_{1}), allocate it according to π(n, w + a_{J}). Let P′(i) be the set containing these allocations and P (i). Let P̃(i) ⊂ W_{n+L}(I) be obtained by extending the paths in P′(i):

P̃(i) = {γη : γ ∈ P′(i), η ∈ W_{L}(t(γ))}.

Then mass(P̃(i)) = mass(P′(i))p^{L}, and mass(P′(i))_{a} = (x^{w(I,i)}p^{n})_{a} for all a ∈ W_{n}(λ_{0}, λ_{1}). Consider a ∈ Log(p^{n}r(I))\W_{n}(λ_{0}, λ_{1}). Taking F = W (p), x^{u}Δ(A) = x^{a}Δ(A) in (3), writing q^{(u)}(J) = q^{(W (p),u)}(J) and multiplying by x^{a−u},

∑_{J} x^{a−u+u_{W (p),J} +D_{W (p),J}} q^{(u)}(J) r(J) = x^{a}p^{L}.

Consider moving, for each b ∈ Log(q^{(u)}(J)), exactly q^{(u)}(J)_{b} elements of W_{n+L}(I, J, mya − u + u_{W (p),J} + D_{W (p),J} + b) from P̃(j) to P̃(i). (If q^{(u)}(J)_{b} < 0, we move the paths from P̃(i) to P̃(j).) By the above equation, this adds x^{a}p^{L} to mass(P̃(i)) and subtracts x^{a}p^{L} from mass(P̃(j)). To complete the proof, one uses (ii), (6.1) and (6.2) to verify that, for small ξ and large n, the sets P̃(j) contain the paths required to repeat this “correction” (x^{w(I,i)}p^{n})_{a} − mass(P′(i))_{a} times.

A partition to which (6.3) applies is constructed by induction. For ease of exposition, we assume L = 0. This enables us to avoid having, as we did in the sketch of the proof of (6.3), to extend paths by L each time we use (3) to make corrections. For small ϵ_{0} > ϵ_{1} > 0, the induction will have ϵ_{0}n + ϵ_{1}n stages. (The choices of ϵ_{0}, ϵ_{1} are indicated below.) For λ ∈ {1, …, ϵ_{0}n + ϵ_{1}n}, we will describe the sets P (λ, i), 1 ≤ i ≤ ρ(I), we have at the end of stage λ.

For λ ∈ {1, …, ϵ_{0}n}, we only make allocations near vertices of W (p^{n}): We start the λth stage having partitioned W (λ − 2) = W_{n}(λ − 2) into sets P (λ − 1, i) with mass(P (λ − 1, i))_{a} = (x^{w(I,i)}p^{n})_{a} for all a ∈ N (λ − 2). Then, for each vertex F_{0}, allocate according to π(n, w + a_{F_{0},J}) each W (I, J, w) contained in W (F_{0}, λ − 1)\W (λ − 2). According to (2.2), by picking ϵ_{0} small and n large, we can be sure that for a ∈ N (F_{0}, λ − 1)\N (λ − 2) the coefficient mass(P (λ − 1, i))_{a} will be an arbitrarily small fraction of (x^{w(I,i)}p^{n})_{a}. Combining this with (6.2), we are assured of the supply of paths needed to use (3) to make corrections and obtain P (λ, i) with mass(P (λ, i))_{a} = (x^{w(I,i)}p^{n})_{a} for all a ∈ N (λ − 1).

From λ = ϵ_{0}n + 1, we allocate paths near the edges of W (p^{n}) as well. For λ ∈ {ϵ_{0}n + 1, …, ϵ_{0}n + ϵ_{1}n} the λth stage consists of d steps. (The choice of d will become clear in a minute.) We start the λth stage having partitioned W (λ − 2, λ − ϵ_{0}n − 2) into sets P (λ − 1, i) with mass(P (λ − 1, i))_{a} = (x^{w(I,i)}p^{n})_{a} for all a ∈ N (λ − 2, λ − ϵ_{0}n − 2). In step 1, we allocate and correct near edges: For each edge F_{1}, allocate according to π(n, w + a_{F_{1},J}) each W (I, J, w) contained in W (F_{1}, λ−ϵ_{0}n−1)\W (λ−2, λ−ϵ_{0}n−2). Then use (3) to correct: We employ (2.2) and (6.2) as before, this time applying them to edges. In addition, we use (6.1) to see that errors due to the choice of a_{F_{1},J} may be corrected. While getting the coefficients correct for a ∈ N (F_{1}, λ−ϵ_{0}n−1), step 1 may perturb those of boundedly many a ∈ N (λ − 2)\N (λ − d). Steps 2 to d − 1 make up for the perturbations. (Step μ ∈ {2, …, d − 1} gets N (λ − d + μ − 1) correct.) Applying (2.2) to edges, for small ϵ_{1} and large n, the perturbations will be small enough for us to correct them by employing (3) near vertices. Finally, step d allocates and corrects at a ∈ N (λ−1)\N (λ−2, λ−ϵ_{0}n−1) to yield P (λ, i) with mass(P (λ, i))_{a} = (x^{w(I,i)}p^{n})_{a} for all a ∈ N (λ − 1, λ − ϵ_{0}n − 1).

References

[A] J. Ashley, Resolving factor maps for shifts of finite type with equal entropy, Ergod. Th. and Dynam. Sys. 11 (1991), 219–240. MR 92d:58056

[AMT] J. Ashley, B. Marcus and S. Tuncel, The classification of one-sided Markov chains, Ergod. Th. and Dynam. Sys. 17 (1997), 269–295. MR 98k:28021

[BMT] M. Boyle, B. Marcus and P. Trow, Resolving maps and the dimension group for shifts of finite type, Mem. Amer. Math. Soc. 377 (1987). MR 89c:28019

[BT] M. Boyle and S. Tuncel, Regular isomorphism of Markov chains is almost topological, Ergod. Th. and Dynam. Sys. 10 (1990), 89–100. MR 92i:28021

[H] D. Handelman, Positive polynomials and product type actions of compact groups, Mem. Amer. Math. Soc. 320 (1985). MR 86h:46091

[LM] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge Univ. Press, Cambridge, 1995. MR 97a:58050

[M] B. Marcus, Factors and extensions of full shifts, Monatshefte Math. 88 (1979), 239–247. MR 81g:28023

[MT1] B. Marcus and S. Tuncel, The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains, Ergod. Th. and Dynam. Sys. 11 (1991), 129–180. MR 92g:28038

[MT2] B. Marcus and S. Tuncel, Entropy at a weight-per-symbol and embeddings of Markov chains, Invent. Math. 102 (1990), 235–266. MR 91k:28023

[MT3] B. Marcus and S. Tuncel, Matrices of polynomials, positivity, and finite equivalence of Markov chains, J. Amer. Math. Soc. 6 (1993), 131–147. MR 93e:28022

[MT4] B. Marcus and S. Tuncel, On large powers of positive polynomials in several variables, preprint.

[MT5] B. Marcus and S. Tuncel, Resolving Markov chains onto Bernoulli shifts, preprint.

[O] D. Ornstein, Ergodic Theory, Randomness and Dynamical Systems, Yale Univ. Press, New Haven, 1974. MR 56:5836

[PS] W. Parry and K. Schmidt, Natural coefficients and invariants for Markov shifts, Invent. Math. 76 (1984), 15–32. MR 86b:28022a

[PT] W. Parry and S. Tuncel, On the stochastic and topological structure of Markov chains, Bull. London Math. Soc. 14 (1982), 16–27. MR 84i:28024

[T] S. Tuncel, Faces of Markov chains and matrices of polynomials, Contemp. Math., Vol. 135, Amer. Math. Soc., Providence, 1992, pp. 391–422. MR 94m:28034

IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120

   E-mail address: marcus@almaden.ibm.com

Department of Mathematics, Box 354350, University of Washington, Seattle, WA 98195

   E-mail address: tuncel@math.washington.edu