1 Introduction
Measure-preserving and topological dynamical systems have representations as successor (Vershik) maps on path spaces of Bratteli diagrams [Reference Herman, Putnam and Skau17, Reference Vershik24, Reference Vershik and Livshits25]. Whether they can be coded as subshifts is the question of expansiveness. The combinatorial nature of these symbolic dynamical representations provides a viewpoint that can suggest new questions and new methods to deal with them. Previously, Méla [Reference Méla and Petersen20, Reference Méla21] showed that in the famous Pascal adic system, with the left–right ordering, the orbits of infinite paths from the root that do not eventually follow only minimal or only maximal edges can be faithfully coded by the partition determined by the first edge. Frick [Reference Frick12, Theorem 4.3] extended this kind of expansiveness to limited scope systems, including those defined by polynomials in one variable (in our current setting, two variables) as well as higher-dimensional Pascal systems. The proofs relied on the particular structure and ordering of the diagrams and explicit descriptions of the maps. We showed [Reference Frick, Petersen and Shields10] that for every ordering of the Pascal diagram, the set of paths not in the orbit of a minimal or maximal path can be faithfully coded by the first three edges, so that this system is inherently expansive. These results raise the natural question of what is it about the diagram and order (and maybe measure) that guarantees this kind of essential expansiveness, and then, what is it about the diagram that guarantees expansiveness for every order? (There are easy examples of diagrams that are essentially expansive for some orders, but not others.)
Our aim here is to extend this result to a fairly wide family of diagrams, which we call polynomial shape, that includes the diagrams defined by homogeneous multivariable polynomials, the Pascal, Euler, and reverse Euler diagrams in higher dimensions, and more, generalizing systems previously studied in, for example, [Reference Bailey2, Reference Bailey, Keane, Petersen and Salama3, Reference Frick and Ormes13–Reference Frick and Petersen15, Reference Kerov18–Reference Méla21, Reference Strasser23, Reference Vershik and Livshits25]. Recent papers related to expansiveness of Bratteli–Vershik systems include [Reference Adams, Ferenczi and Petersen1, Reference Berthé, Steiner, Thuswaldner and Yassawi5, Reference Bezuglyi, Kwiatkowski and Medynets7, Reference Downarowicz and Maass8, Reference Frick, Petersen and Shields10, Reference Frick, Petersen and Shields11].
As mentioned below (Remark 6.4), it may be possible to formulate general conditions on a diagram that guarantee inherent expansiveness. The class of diagrams considered in this paper is wide enough to include many interesting examples and their variants. The multidimensional polynomial structure enables the use of coordinate descriptions for precision and visualization of important aspects of the argument. Nevertheless, the main argument is necessarily indirect, so the problem of finding a satisfactory characterization of inherently expansive diagrams (as well as essentially expansive systems) remains open.
The next section begins by recalling basic definitions and terminology about Bratteli diagrams and Bratteli–Vershik systems. When coding orbits, it is necessary to discard those of maximal and minimal paths, and our proofs require paths with dense orbits. Proposition 2.3 establishes that, under mild conditions on the diagram, for each ordering the exceptional set (one-sided orbits of maximal and minimal paths together with the non-dense orbits) is meager (first category). The set of invariant measures depends only on the tail relation and so is independent of the choice of ordering. For the diagrams dealt with in this paper, the exceptional set also has measure zero for every fully supported ergodic invariant probability measure—see Remark 2.4 and Proposition 3.7.
In §3, we define the polynomial diagrams and their generalization polynomial shape diagrams that are the subject of this paper, establish terminology and notation for keeping track of connections between vertices, and identify distinguished source vertices which are useful as pivots for moving around in the diagram. (When working in higher dimensions, the coordinate representation is essential to make sure that the motion continues in a consistent direction.) In the proof of the main theorem, it is essential to observe the intersections of source sets of certain vertices (v is in the source set of w if there is an edge from v to w, see Definition 3.3), so in §4 we determine exactly which vertices at a given level have their source sets inside those of other vertices at that level. To prove that orbits of paths not in the exceptional set can be distinguished from one another by observing their initial finite segments of a fixed length, one necessarily proceeds by contradiction. In §5, based on the hypothesis that there exist pairs of paths that cannot be so distinguished, we build machinery (chains and links) within the diagram that connect the vertices through which these paths pass at two adjacent levels. Although all of this is fictional, since the ultimate aim is to show that none of it is possible, in the final §6 the constructions do produce a contradiction to how the pair of paths would have to move through the diagram, thereby proving the main theorem (Theorem 6.3): Every polynomial shape diagram is inherently expansive.
Now, we summarize with more detail the main steps of the argument.
The idea is to show that if a depth i pair (Definition 2.10) did indeed exist, then we could construct a long linearly ordered chain (Definition 5.1) consisting of uncovered (Definition 4.1) shared and splitting vertices (Definition 5.1). We then argue that this leads to a contradiction, as follows.
Assuming that the orbits of both paths are dense, eventually one of them, say
$x'$
, must be the first to change vertices at level
$i+2$
. For i sufficiently large, the constructed chain will be long enough so that (1) the first vertex at level
$i+1$
that
$x'$
passes through after switching vertices twice at level
$i+2$
is still part of the chain; and (2) if z is the second vertex at level
$i+2$
through which the forward orbit of
$x'$
passes while in the chain, then there is a vertex in its source set
$S(z)$
that is not one of the splitting vertices met by the orbit of
$x'$
during the time that it moves through the chain. (This is argued in the proof of the main theorem using Lemma 6.2.) Hence, the orbit of
$x'$
does not meet every vertex in
$S(z)$
before changing vertices again at level
$i+2$
. However, according to the definition of the Vershik map, it must. Therefore, there can be no depth i pair.
To produce the straight chain used in this proof, we first show that there exist a large region of uncovered vertices at level
$i+1$
(Lemma 5.4, Proposition 4.2) and a time when the orbits of x and
$x'$
meet distinct vertices in this region,
$w_0$
and
$w_1$
, respectively (Lemma 6.1). The vertices
$w_0$
and
$w_1$
are then chosen to be the first and second splitting vertices of our chain.
Since
$w_1$
is uncovered, there exists a distinguished direction and distinguished vertex (Definition 3.8) u in
$S(w_1)\setminus S(w_0)$
. To find the next splitting vertex of the chain, we consider the first time (forward or backward) that the orbit of
$x'$
meets u, while still at
$w_1$
. Since x and
$x'$
have the same i-coding, the orbit of x must switch vertices at level
$i+1$
by this time, while the orbit of
$x'$
does not leave
$w_1$
until afterwards. The fact that
$w_0$
is in our desired region of uncovered vertices (in particular,
$S(w_0)$
is not contained in
$S(w_1)$
) is then sufficient (and necessary) for us to show that when the orbit of x leaves
$w_0$
, it cannot switch to
$w_1$
(Lemma 5.4).
Hence, the next vertex
$w_2$
at level
$i+1$
met by the orbit of x is distinct from both
$w_0$
and
$w_1$
. We let
$w_2$
be the third vertex in our chain. Since the region of uncovered vertices containing
$w_0$
and
$w_1$
is large enough to contain
$w_2$
, we can repeat the process, using
$w_1$
and
$w_2$
, with the roles of x and
$x'$
reversed. We continue in this manner until we produce a sufficiently long chain whose splitting vertices are met, in an alternating fashion, by the orbits of x and
$x'$
, respectively. The properties of the distinguished source vertices and our region ensure that each new splitting vertex is in our region and distinct from all previous splitting vertices in the chain. Thus, the chain has the properties necessary to complete the proof as sketched above (Theorem 6.3).
To highlight the essentials of the argument even more, we now very briefly describe how it applies to the two-dimensional Pascal system, which is defined by the polynomial in two variables
$p(x_1,x_2) = x_1 + x_2$
. The proof of the main theorem, when applied to this system, would require
$i \geq 20$
, but in fact we need only
$i \geq 3$
.
If there were a depth i pair x,
$x'$
, then at some time their orbits would follow different paths into level
$i+1$
, and since there is at most one edge between any two vertices, they would meet different vertices
$w_0$
and
$w_1$
at level
$i+1$
at this time, which we can assume is time 0.
Note that each row of the two-dimensional Pascal diagram has only two covered vertices and they are at the ends, so every vertex after the root is in the source set of at most one covered vertex. Since x and
$x'$
meet the same vertex at level i, at least one of
$w_0$
or
$w_1$
is uncovered.
Consider the case where one of these vertices, say
$w_0$
, is covered. Replacing T with
$T^{-1}$
if necessary, assume that the orbit of
$x'$
meets the (automatically distinguished) vertex
$u \in S(w_1) \setminus S(w_0)$
at some time
$m>0$
, while still at
$w_1$
. Since
$m>0$
, it is then necessarily the case that the edge the path
$x'$
follows into
$w_1$
is minimal according to the edge ordering, while the edge that
$T^mx'$
follows from u to
$w_1$
is maximal. Then,
$T^mx$
also meets u. Since
$u \notin S(w_0)$
, the vertex
$w_2$
at level
$i+1$
met by
$T^mx$
is clearly distinct from
$w_0$
. It also follows that
$w_2 \neq w_1$
, since
$T^mx$
follows a minimal edge into
$w_2$
and the minimal edge into
$w_1$
has source in
$S(w_0)$
.
Note that
$w_1$
shares one of its source vertices with the covered vertex
$w_0$
and the other with
$w_2$
. So since
$i+1 \geq 3$
,
$w_2$
is clearly uncovered. Hence, we can now add to the current chain (whose splitting vertices are
$w_0$
,
$w_1$
, and
$w_2$
) by using the (distinguished) vertex in
$S(w_2) \setminus S(w_1)$
to extend the subchain (link,
$w_1$
to
$w_2$
) to a new vertex,
$w_3$
. We can continue to extend our chain, moving in a fixed direction away from
$w_0$
, at step
$k+1$
adding a splitting vertex
$w_{k+1}$
whose source set intersects that of
$w_k$
and which is distinct from
$w_0, \ldots , w_k$
, until its last splitting vertex is covered (that is, until we reach the other edge of the diagram). The existence of the chain forces a consistent ordering (left to right or right to left) on the edges entering the vertices at level
$i+1$
. Each of the uncovered vertices at level
$i+1 \geq 4$
(of which there are at least three) is a splitting vertex in our chain, and our construction ensures that collectively the orbits of x and
$x'$
meet them all, in an alternating manner, before one of them meets the last (covered) splitting vertex in the chain. We claim that this does not happen until after the orbit of x has changed vertices twice at level
$i+2$
.
Looking at the diagram structure, it is easy to see that two splitting vertices can both be in the source set of a vertex z at level
$i+2$
only if they are adjacent in the chain (equivalently, next to each other on row
$i+1$
of the diagram). Because the orbits of x and
$x'$
are skipping every other splitting vertex in the chain, every time one of them changes splitting vertices it changes vertices at level
$i+2$
. Furthermore, the chain has length at least 5 (counting the two covered vertices at its beginning and end), so the orbit of x, beginning at
$w_0$
, will meet at least 3 splitting vertices. Hence, the orbit of x changes vertices at level
$i+2$
at least twice before reaching the end of the chain.
If z is the second vertex at level
$i+2$
through which the forward orbit of x passes while in the constructed chain,
$|S(z)| = 2$
. The orbit of x meets z and a splitting vertex (at level
$i+1$
) that is adjacent to two other splitting vertices in the chain. It does not meet either of these adjacent vertices while moving through the chain, since it skips alternate splitting vertices in the chain, However, one of these splitting vertices must be in
$S(z)$
, which contradicts the fact that the orbit of x must meet every vertex in
$S(z)$
before changing vertices again at level
$i+2$
. So there can be no depth i pair.
If we start near the middle of the diagram, with
$w_0$
and
$w_1$
both uncovered, we build the chain in both directions, using forward time for one direction and backward for the other (starting with (distinguished) vertices in
$S(w_1) \setminus S(w_0)$
and
$S(w_0) \setminus S(w_1)$
, respectively). Replacing x and
$x'$
with paths in their orbits that simultaneously meet two splitting vertices of the chain, the first of which is covered, we will be in the previously considered case.
2 Background
We now recall (in fact, partly quote) from [Reference Petersen and Shields22] the standard basic definitions about Bratteli diagrams, ordered Bratteli diagrams, and Bratteli–Vershik systems. For further terminology and background, see [Reference Bezuglyi and Karpel6, Reference Durand9, Reference Frick, Petersen and Shields10, Reference Giordano, Putnam and Skau16, Reference Herman, Putnam and Skau17] and their references.
A Bratteli diagram (here also just called a diagram) is a countably infinite, directed, graded graph. For each
$n=0,1,2,\ldots $
, there is a finite non-empty set of vertices
$\mathcal {V}_n$
. Here,
$\mathcal V_0$
consists of a single vertex, called the ‘root’. The set of edges is the disjoint union of finite non-empty sets
$\mathcal E_n, n\geq 0$
, with
$\mathcal E_n$
denoting the set of edges with source in
$\mathcal V_{n}$
and target in
$\mathcal {V}_{n+1}$
. The source map
$s: \mathcal E_n \to \mathcal V_{n}$
and target map
$t:\mathcal E_n \to \mathcal {V}_{n+1}$
are defined as usual. The source set of a vertex
$w \in \mathcal V_{n+1}$
is
$S(w)= s(t^{-1}\{w\})$
. In words, v is in the source set of w if there is an edge from v to w. (To simplify notation, we write
$t^{-1}\{w\} = t^{-1}w$
.) We define
$\mathcal V=\bigcup _n\mathcal {V}_n$
,
$\mathcal {E}=\bigcup _n\mathcal {E}_n$
and denote the diagram by
$\mathcal B=(\mathcal {V},\mathcal {E})$
.
Every vertex other than the root has at least one incoming edge and at least one outgoing edge, and there can be multiple edges between pairs of vertices.
The space X is the set of infinite paths (sequences
$x=x_0 x_1\cdots $
, each
$x_i$
in
$\mathcal {E}_{i}$
) starting at the root at level
$i=0$
. For a path x, we denote by
$v_i(x)$
the vertex of the path at level i. In other words,
$v_i(x)=s(x_i)=t(x_{i-1})$
. The set X is a compact metric space when we specify that two paths have distance
$1/2^n$
if they agree from levels
$0$
to n and disagree leaving level n. We avoid degenerate situations and only consider diagrams for which X is homeomorphic to the Cantor set. The cylinder sets
$x_{[0,n]}=\{y \in X: y_i = x_i, i=0, \ldots , n\}$
, for
$n \geq 0$
and
$x \in X$
, are clopen sets that generate the topology.
The edges entering each vertex can be totally ordered by specifying a map
$\xi : \mathcal {E}\to \mathbb {N}$
such that for
$n>0$
and
$w\in \mathcal {V}_n$
,
$\xi $
restricted to
$t^{-1}w$
is a bijective map with range
$\{1, 2,\ldots ,|t^{-1}w|\}$
. The diagram together with such an order is called an ordered Bratteli diagram.
Two paths x and y are comparable, or tail equivalent, if they are cofinal: there is a smallest
$N>0$
such that
$x_N=y_N$
for all
$n \geq N$
. In this case,
$x_{N-1} \neq y_{N-1}$
; we agree that
$\xi (x)<\xi (y)$
if
$\xi (x_{N-1}) < \xi (y_{N-1})$
, and
$x>y$
if not. The set of minimal paths, meaning all of those whose edges are minimal into all of their vertices, is denoted by
$X_{{\text {min}}}$
and, similarly, the set of maximal paths is denoted by
$X_{{\text {max}}}$
. The Vershik, or adic, map
$T=T_\xi $
is defined from the set of non-maximal paths to the set of non-minimal paths by mapping each path x to its successor, the smallest
$y>x$
. The pair
$(X,T)$
is called a Bratteli–Vershik system.
We do not always need an ordering or transformation to use dynamical concepts and terminology. Given a diagram, we think of the tail relation as the ‘orbit’ relation: two points are in the same ‘orbit’ if they agree from some level downward. If x and
$x'$
are tail related, then for each ordering
$\xi $
there is
$n \in {\mathbb {Z}}$
such that
$T_\xi ^nx =x'$
; thus, every tail-relation orbit is a
$T_\xi $
-orbit.
An invariant set is one that is a union of orbits, that is, it is saturated with respect to the tail relation. Note that each orbit is at most countably infinite. An invariant measure
$\mu $
is one that for each vertex w assigns equal measure to all the cylinder sets determined by paths from the root to w: if
$v_n(x)=v_n(y)=w$
, then
$\mu (x_{[0,n]})=\mu (y_{[0,n]})$
.
We denote by
$X^{\prime }_\xi $
the set consisting of the backward
$T_\xi $
-orbits of maximal paths and the forward orbits of minimal paths. Thus,
$X^{\prime }_\xi $
consists of the paths whose edges are all eventually minimal or all eventually maximal. (We make no assumptions that our diagrams are proper.)
Denote by
$X_0$
the set of paths whose orbits are not dense. Then
$X_0$
has measure
$0$
for every fully supported ergodic invariant measure on X. Unlike the situation for the two-dimensional Pascal system with left–right order [Reference Méla and Petersen20, Proposition 2.3], even for a polynomial shape system the set
$X_0$
need not coincide with
$X^{\prime }_\xi $
for any order. See Proposition 3.6 for a precise description of
$X_0$
in the case of polynomial shape systems.
Definition 2.1. Given an ordering
$\xi $
of a Bratteli diagram as above, we denote by
$X(\xi )$
the set of paths in the path space X that have a dense orbit and are not in
$X^{\prime }_\xi $
. The exceptional set is
$X^{\prime }_{\xi }\cup X_0=X \setminus X(\xi )$
.
We say that two vertices
$v,w$
are connected if there is a finite downward directed path of consecutive edges in the diagram that begins at one of the vertices and ends at the other. If for every n and every pair of vertices
$v_1,v_2 \in \mathcal V_n$
there are
$m> n$
and a vertex
$w \in \mathcal V_m$
that is connected to both
$v_1$
and
$v_2$
, we say the diagram is connected.
We say that a diagram is topologically transitive if given non-empty open sets
$U,V$
, there is a point (infinite path) in U which is tail equivalent to some point in V. Just as for homeomorphisms on compact metric spaces, there are several conditions equivalent to topological transitivity. Recall that a set is called meager, or first category, if it is a countable union of nowhere dense sets, and the complement of a meager set is called comeager or residual.
Proposition 2.2. The following properties of a Bratteli diagram are equivalent:
-
(1) the diagram is connected, in the sense just defined;
-
(2) the diagram is topologically transitive;
-
(3) every proper closed invariant set is nowhere dense;
-
(4) there is a point with dense orbit;
-
(5) the set of points with dense orbit is comeager.
Proof. The equivalence of properties (1), (2), and (3) is immediate. Since X is a Baire space, (5) implies (4), and clearly (4) implies (2). We show now that (1) implies (5).
Given a finite path
$\alpha =\alpha _0 \cdots \alpha _n$
starting at the root, denote by
$[\alpha ]$
the cylinder set consisting of all paths that begin with
$\alpha $
:
If x is a path whose orbit
$\mathcal O(x)$
is not dense, then there is such a finite path
$\alpha $
for which
$\mathcal O(x) \cap [\alpha ] = \emptyset $
. For any finite path
$\alpha $
starting at the root, let
Then each
$A_\alpha $
is invariant (saturated) for the tail equivalence relation. Moreover, we show that it is closed and nowhere dense and thus the set
$\bigcup _\alpha A_\alpha $
of points without a dense orbit is meager.
Suppose that
$y \in A_\alpha ^c$
and find
$z \in \mathcal O(y)$
such that
$z \in [\alpha ]$
. By connectedness of the diagram, there is a vertex w at some level
$m> n$
such that
$v_n(y)$
and
$v_n(z)$
are connected to w. Now, any
$y' \in X$
close enough to y that
$y^{\prime }_{[0,m]}=y_{[0,m]}$
also satisfies
$\mathcal O(y') \cap [\alpha ] \neq \emptyset $
, so
$y' \in A_\alpha ^c$
. Therefore,
$A_\alpha ^c$
is open.
Now, we show that
$A_\alpha $
is nowhere dense by showing that its complement
$A_\alpha ^c$
is dense. Let
$\beta $
be any finite path starting at the root. Extending either
$\alpha $
or
$\beta $
if necessary, we may assume that they end at vertices
$v_1$
and
$v_2$
at the same level
$n> 0$
. By connectedness of the diagram,
$\alpha $
and
$\beta $
have extensions
$\alpha '$
and
$\beta '$
that end at the same vertex w at some level
$m>n$
. Extend
$\beta '$
to an infinite path
$y'$
. Then,
$\mathcal O(y') \cap [\alpha ] \neq \emptyset $
and
$\mathcal O(y') \cap [\beta ] \neq \emptyset $
, so that
$y' \in A_\alpha ^c \cap [\beta ]$
.
Proposition 2.3. Suppose that a diagram is connected and every vertex has at least two outgoing edges. Then for every edge ordering the set of orbits of minimal paths is meager and, similarly, the set of orbits of maximal paths is meager; therefore, for every ordering
$\xi $
the set
$X(\xi )$
as defined above (Definition 2.1) is comeager.
Proof. Fix an arbitrary edge ordering. For each
$k \geq 1$
, let
Then the set of orbits of minimal paths (the set of paths that eventually follow only minimal edges) is
See Figure 1.
The edge ordering is given by the numbers on the edges. Any infinite paths that contain a dashed edge are in
$U_k^c$
and the rest are in
$U_k$
.
To show that E is meager, it suffices to show that each of the closed sets
$\bigcap _{k \geq n} U_k^c$
is nowhere dense, equivalently that each of the open sets
is dense.
Given
$n \geq 0$
and a basic open set B defined by an initial segment y from the root to a vertex
$v_1$
at a level
$m_1$
, we find a point
$x \in \mathcal {E}_n \cap B$
as follows. Since the sets
$\mathcal {E}_n$
are decreasing, we may assume that
$n> m_1$
. Extend y arbitrarily to arrive at a vertex
$v_2$
at level n. The vertex
$v_2$
has at least two outgoing edges. Let us suppose first that all edges leaving
$v_2$
arrive at the same terminal vertex, w. Then, one of these edges, call it
$e_1$
, is not minimal. Extend the finite path downward from
$v_2$
along
$e_1$
and then arbitrarily downward from w, producing a path
$x \in \mathcal {E}_{n+1} \cap B\subseteq \mathcal {E}_n\cap B$
.
If there are two edges leaving
$v_2$
that arrive at different vertices
$w_1, w_2$
, since the diagram is connected there is a first level
$m_2>n+1$
on which there exists a vertex w that connects to both
$w_1$
and
$w_2$
, along paths
$p_1,p_2$
down from
$v_2$
. One of these two paths, call it
$p_1$
, enters w along a non-minimal edge. In this case, we extend the path downward from
$v_2$
along
$p_1$
and then arbitrarily downward from w to produce the path
$x \in \mathcal {E}_{m_2}\cap B\subseteq \mathcal {E}_n \cap B$
. See Figure 2.
The dashed edge into w is non-minimal. The path
$x\in \mathcal {E}_n\cap B$
follows the path
$p_1$
into w through the non-minimal edge.
This proves the set
$X_{\xi }'$
is meager; then, by Proposition 2.2,
$X(\xi )$
is comeager.
Remark 2.4. The preceding argument shows that for every k, the set of minimal paths
$\bigcap _{k \geq 1} U_k^c$
is nowhere dense (but it can be uncountable—see [Reference Frick, Petersen and Shields10, Example 7.2]), similarly for the maximal paths. Using the argument in [Reference Berthé, Steiner, Thuswaldner and Yassawi5, Lemma 6.2], we can show (in Proposition 3.7) that in any polynomial shape diagram (see Definition 3.1), the sets of maximal and minimal paths (along with their orbits) are also negligible in the measure-theoretic sense and, therefore,
$X_0 \cup X_\xi '$
is meager and has measure
$0$
for every fully supported ergodic invariant measure on X. Alternatively, in many cases, the ergodic measures can be identified explicitly (see Méla [Reference Méla19, Reference Méla21] and the extension by Frick [Reference Bailey2, Reference Frick12], showing that the measure of every cylinder set is given by the product of weights that come from a finite set in
$(0,1)$
), and then one can apply an argument such as in [Reference Frick, Petersen and Shields10, Proposition 2.1]. We defer the details to Proposition 3.7 in §3, after the necessary definitions, notation, and properties have been presented.
We turn now to establish terminology and notation for the main question addressed in this paper, the effectiveness of coding of orbits by finite paths, edges, or vertices. For each
$k \geq 1$
, denote by
$A_k$
the finite alphabet whose elements are the finite paths (segments, strings of edges) from the root to level k. For each
$a \in A_k$
, the set
$[a]=\{x \in X: x_0 \cdots x_{k-1}=a\}$
is a clopen cylinder set and
$\mathcal P_k=\{ [a]:a \in A_k\}$
is a partition of X into clopen sets. The map
$\pi _k:X \to A_k^{\mathbb {Z}}$
is defined by
$(\pi _kx)_n=a$
if and only if
$T^nx \in [a]$
. The sequence
$\pi _kx$
is called the k-coding of x. We denote by
$\Sigma _k$
the closure of
$\pi _k X$
. Denote by
$\sigma $
the shift transformation on
$A_k^{\mathbb {Z}}$
. Then,
$\pi _k:(X,T) \to (\Sigma _k, \sigma )$
is a Borel measurable map that commutes with the transformations and
$(\Sigma _k, \sigma )$
is a symbolic dynamical system.
Definition 2.5. The coding by vertices at level
$j<n$
of a vertex w at level n, denoted by
$C_j(w)$
, is defined as follows. List, in the order determined by their lexicographical ordering in the diagram, the paths entering w from vertices at level j as
$\{p_1,\ldots ,p_r\}$
and denote the source of (the first edge of)
$p_i$
by
$u_i, i=1,\ldots ,r$
. Then,
$C_j(w)=u_1 \cdots u_r$
. (For
$j=n-1$
, this is the ‘morphism read on
$\mathcal V_{n}$
’ in [Reference Durand9, p. 328]).
The coding by edges from level
$n-1$
to level n of the orbit of a path x is the sequence
$Edge_n(x)=((T^mx)_{n-1}, m\in \mathbb Z)$
.
The coding by vertices at level n (or by
$\mathcal V_n$
) of the orbit of a path x is the sequence
$Vert_n(x)=(v_n(T^mx), m \in \mathbb Z)=((Vert_n(x))_m, m \in {\mathbb {Z}})$
.
Remark 2.6.
-
(1) The mapping that takes a path x to its coding by vertices at level n intertwines the action of T on X with the shift on $\mathcal V_n^{\mathbb {Z}}$
. -
(2) It might happen that there are $w_1,w_2 \in \mathcal V_n$
with
$w_1 \neq w_2$
but, for example,
$C_{n-1}(w_1)=C_{n-1}(w_2)$
. -
(3) Note that whenever m is such that $(T^m x)_{n-1}$
is the minimal edge entering
$w=v_n(T^mx)$
from level
$n-1$
, then the coding of the orbit of x by
$\mathcal V_n$
begins a string of repeats of w of length equal to the number of paths from the root to w, which we denote by
$\dim w$
. This is because the coding by vertices
$C_{n-1}(v_n(T^mx))=u_1 u_2 \cdots $
of
$v_n(x)$
by vertices at level
$n-1$
expands into the codings of the
$u_i$
by vertices at level
$n-2$
, and each of those vertices has its coding by vertices of the previous level expand to codings by vertices of its previous level, and so on. Stated slightly differently, if we list in their lexicographical order in the diagram the paths from the root entering w as
$\{q_1,\ldots ,q_{\dim w}\}$
, whenever
$(T^mx)_{n-1}$
is the minimal edge to w from level
$n-1$
, as we apply T the orbit of x uses each
$q_i$
in turn, and so in the coding by
$\mathcal V_n$
of the orbit of x we see a string of length
$\dim w$
of repeated w terms with the ‘dot’ to its immediate left (the path being coded passes through the vertex just to the right of the dot).
In [Reference Adams, Ferenczi and Petersen1], a (measure-theoretic) rank-one system was defined to be essentially k-expansive if the partition
$\mathcal P_k$
generates the full sigma-algebra under the transformation T. Since we are dealing here with more generality than rank one, in particular not assuming a fixed invariant measure, we need a slightly different definition. Also, we restrict attention to points that have dense full two-sided orbits.
Definition 2.7. We say that a topologically transitive
$BV$
system (with ordering
$\xi $
) is (bilaterally) expansive if there is an
$i \geq 1$
such that the map
$\pi _i: (X(\xi ),T) \to (\Sigma _i,\sigma )$
is injective, in which case the system is called (bilaterally) i-expansive.
Definition 2.8. We say that a topologically transitive diagram is inherently expansive if for every ordering the resulting system is (bilaterally) expansive.
Remark 2.9. The concept of expansiveness for Bratteli–Vershik systems is tantamount to recognizability for substitutions, morphisms, or sequences of morphisms: see [Reference Béal, Perrin, Restivo and Steiner4, Reference Berthé, Steiner, Thuswaldner and Yassawi5, Reference Bezuglyi, Kwiatkowski and Medynets7] and their references. These papers focus on systems of bounded width (‘finite alphabet rank’, possibly after telescoping) and recognizability for aperiodic points, while most of the examples we are interested in have unbounded width. The sequence of morphisms associated with a Bratteli–Vershik system is recognizable (at all levels, for full orbits) in the sense of [Reference Berthé, Steiner, Thuswaldner and Yassawi5, Definitions 2.1 and 4.1] if (briefly) for each
$n \geq 1$
the coding of an orbit by vertices at level n uniquely determines (by ‘desubstitution’) its coding by vertices at level
$n+1$
. We claim that a system is recognizable at all levels for full orbits if and only if it is
$1$
-expansive for full orbits.
Let us note first that for an ordered Bratteli diagram with at least two vertices per level after the root, for each
$i \geq 0$
codings of a path by edges between levels i and
$i+1$
, and codings by vertices at levels i and
$i+1$
, determine one another.
In each case, we assume that a coding also specifies the location of the central coordinate (‘dot’) in the given sequence of edges or symbols. A sequence of edges,
$(T^mx)_i, m \in {\mathbb {Z}}$
, clearly determines the sequences of vertices
$v_i(T^mx)=u_m(x)$
and
$v_{i+1}(T^mx)=w_m(x)$
. Conversely, given the sequences (on m)
$v_i(T^mx)=u_m(x)$
and
$v_{i+1}(T^mx)=w_m(x)$
, and the position of the dot in each sequence, in a string of repeats of a symbol
$w_m(x)$
the path is entering that vertex along the edge whose label is given by the position of the dot. Thus, the codings by vertices determine for each
$m \in {\mathbb {Z}}$
a unique edge
$e \in \mathcal E_i$
such that
$s(e)=u_m(x)$
and
$t(e)=w_m(x)$
.
Suppose that
$X \setminus X_\xi $
is
$1$
-expansive and we are given the coding
$(v_n(T^mx), m \in {\mathbb {Z}})$
of a path x by vertices at some level
$n \geq 1$
. By Remark 2.6(3), each coding of x by
$\mathcal V_{n}$
determines its coding by
$\mathcal V_{n-1}$
, using the ‘substitution read on
$\mathcal V_{n}$
’, including the position of the ‘dot’. Thus, the coding by
$\mathcal V_{n}$
determines the codings by vertices on all levels
$j \leq n$
, and hence, by the paragraph above, the coding by edges for all levels before level n, in particular, the
$1$
-coding, hence (by
$1$
-expansiveness) the path x itself, and hence the coding by vertices at level
$n+1$
.
Conversely, if
$X \setminus X^{\prime }_\xi $
is recognizable at all levels, then for each path
$x \in X \setminus X^{\prime }_\xi $
the coding by vertices at each level
$n \geq 1$
of the orbit of x determines its coding by vertices at level
$n+1$
, so we may just reverse the process in the previous paragraph: if
$X \setminus X^{\prime }_\xi $
is recognizable at all levels, then coding by edges to level
$1$
, which determines coding by vertices at level
$1$
, by recognizability determines the coding by vertices at all levels, hence the coding by edges at all levels, hence the edge traversed by each path at every level, and hence each path itself, so that the system is
$1$
-expansive.
If a system is not i-expansive, there exist pairs of points in
$X \setminus X^{\prime }_\xi $
such that at all times in their orbits they agree on their first i edges. The following definition is from [Reference Downarowicz and Maass8].
Definition 2.10. Let
$i\geq 0$
. We say two paths
$x, x' \in X \setminus X^{\prime }_\xi $
form a pair of depth i if they have the same i-coding but not the same
$(i+1)$
-coding.
Proposition 2.11. Consider an ordered Bratteli diagram for which there are at least two vertices at every level after the root. Then for each
$i \geq 1$
and every depth i pair, x and
$x'$
in
$X(\xi )$
, there is
$m \in {\mathbb {Z}}$
such that
$v_{i+1}(T^mx) \neq v_{i+1}(T^mx')$
.
Proof. Since the pair
$x,x'$
is depth i, there is
$j \in {\mathbb {Z}}$
such that
$(T^jx)_i \neq (T^jx')_i$
. If it happens that
$v_{i+1}(T^jx)=w=v_{i+1}(T^jx')$
, one of
$x,x'$
must reach the maximal path to w and change vertices at level
$i+1$
before the other, since there are at least two vertices at every level and both x and
$x'$
have dense orbits. Thus, there is a smallest
$k \geq 0$
such that
$v_{i+1}(T^{j+k}x) \neq v_{i+1}(T^{j+k}x')$
. Letting
$m=k+j$
, we have
$v_{i+1}(T^mx) \neq v_{i+1} (T^mx')$
.
3 Multivariable polynomial Bratteli diagrams
NOTE: in this section we use the notation
$x_i$
for variables (the arguments in multivariable polynomials) and not for the edges of paths in the diagram.
Multivariable polynomial adic systems associated to multivariable polynomials of degree d can be represented by a two-dimensional diagram where the vertices are totally ordered on each level. However, to fully exploit the structure given by the polynomials it is convenient to think of the diagrams in higher dimensions.
Let
$p=p(x)$
be a homogeneous positive integer multivariable polynomial of degree d in q variables,
where
$m_1,\ldots , m_q$
are non-negative integers and
$a_{(m_1,m_2,\ldots , m_q)}\in {\mathbb {N}}$
. The polynomial p spawns Bratteli diagrams in the following manner. Each vertex
$w \in \mathcal V_n$
is a monomial
$x_1^{m_1}\cdots x_q^{m_q}$
in
$(p(x))^n$
, with
$\sum _{i=1}^qm_i=nd$
. We identify the monomial
$x_1^{m_1}\cdots x_q^{m_q}$
with the vector
$(m_1,\ldots , m_q)=\sum _{i=1}^q m_ie_i$
, where
$e_i$
is the ith standard basis vector in
${\mathbb {R}}^q$
. We write
$w=(m_1,\ldots ,m_q)=(w(1),\ldots ,w(q))$
. By
$w\geq 0$
, we mean
$w(\ell )\geq 0$
for all
$\ell \in \{1,\ldots ,q\}$
, and
$w\geq w'$
,
$w-w'\geq 0$
, and
$|w|=w_1+w_2+\cdots +w_q$
.
Definition 3.1. For each
$n \geq 0$
, let there be specified a set
$\mathcal E_n$
of edges connecting the set
$\mathcal V_n$
of vertices at level n to the set
$\mathcal V_{n+1}$
of vertices at level
$n+1$
. If for each
$n \geq 0$
the set
$\mathcal E_n$
has the property that there is at least one edge from
$u \in \mathcal V_{n}$
to
$w \in \mathcal V_{n+1}$
if and only if there is
$s \in S$
such that
$u+s=w$
, we say that the diagram is (or has) polynomial shape and is associated to p. If in addition the number of edges between u and w is the coefficient of the monomial
$x_1^{s_1}x_2^{s_2}\cdots x_q^{s_q}$
in p that corresponds to the vector
$(s_1, s_2, \ldots s_q)=w-u$
, we say that the diagram is a polynomial diagram and is defined by p.
For each
$n\in {\mathbb {N}}$
, the number of vertices in
$\mathcal {V}_n$
equals the number of terms in
$(p(x))^n$
, equivalently, the number of ways
$nd$
can be written as a sum of q non-negative integers. In other words,
Definition 3.2. The set of source vectors is
$S=\{s=(s_1,s_2,\ldots ,s_q):s\geq 0 \text { and} {|s|}=d\}$
.
Thinking of
$\mathcal {V}_1$
as a set of vectors, we have that
$\mathcal {V}_1=S$
and hence each
$s\in S$
also corresponds to a monomial in
$p(x)$
.
In a polynomial diagram, the number of paths from the root vertex to a vertex
$u=(m_1,m_2,\ldots ,m_q)$
is the coefficient of the monomial
$x_1^{m_1}x_2^{m_2}\cdots x_q^{m_q}$
in
$(p(x_1,\ldots ,x_q))^{n}$
. See Figure 3.
The polynomial adic system associated with
$p(x,y)=x^4+2x^3y+x^2y^2+3xy^3+y^4$
, has
$q=2$
variables and is of degree
$d=4$
. The vertices on level
$3$
corresponding to terms in
$(p(x,y))^3$
are labeled.
Figure 3 Long description
The diagram is a directed acyclic graph structured in four horizontal levels.
At the top level is a single root vertex.
The second level down contains five vertices arranged horizontally.
The third level down contains nine vertices.
The fourth and bottom level contains thirteen vertices. Each vertex on this level is labeled with a coordinate pair. From left to right, the labels are: 12 comma 0, 11 comma 1, 10 comma 2, 9 comma 3, 8 comma 4, 7 comma 5, 6 comma 6, 5 comma 7, 4 comma 8, 3 comma 9, 2 comma 10, 1 comma 11, and 0 comma 12.
Edges connect vertices between adjacent levels. The connections are dense, with multiple straight and curved lines emanating from each vertex to several vertices in the level below it, forming a complex web of paths that widen as they descend toward the base.
Definition 3.3. For
$n \geq 1$
and
$w \in \mathcal V_{n+1}$
, we define the source set of w to be
This agrees with the definition in §2 in terms of source and target maps,
$S(w)=s(t^{-1}\{w\})$
. Simply stated,
$u \in S(w)$
if and only if there is an edge from u to w. Note that
$S(w)$
can also be described as the set of non-negative vectors in
$w-S=\{w-s:s\in S\}$
. Similarly, for any
$k\leq n$
the set of vectors in
$\mathcal {V}_k$
that connect to w via a path of
$j=n+1-k$
edges is the set of non-negative vectors in
$w-(S+S+\cdots +S)$
, where S is repeated j times. (Here
$S+ \cdots +S$
(j times) means
$\{s_{i_1} + \cdots + s_{i_j}: s_{i_\ell } \in S, \ell =1, \ldots , j\}$
.) Since vector addition corresponds to multiplication of monomials,
$u\in S(w)$
if and only if the monomial corresponding to u can be multiplied by a monomial of
$p(x)$
to obtain the monomial corresponding to w.
Example 3.4. For the diagram in Figure 3 associated with the polynomial
$p(x,y)=x^4+2x^3y+x^2y^2+3xy^3+y^4$
,
$V_1 = S = \{(4,0), (3,1), (2,2), (1,3), (0,4)\}$
. The source sets for each of the eight
$w \in V_2$
are given in the following table. As a reminder, the vertices are associated to monomials. For instance,
$(8,0)\sim x^8$
and
$(7,1)\sim x^7y$
.
Every polynomial diagram has polynomial shape, but a polynomial shape diagram associated to a polynomial p, while having connections between the same pairs of vertices as in the polynomial diagram defined by p, can have any positive number of edges between connected vertices. When
$q=1$
, a polynomial shape diagram is that of either an odometer or a finite set of points.
The incidence matrices for polynomial shape diagrams change at each level but have a predictable structure. They have size
$|\mathcal {V}_n|\times |\mathcal {V}_{n+1}|$
, where the entry for
$(v,w)$
is equal to the number of edges from
$v\in \mathcal {V}_n$
to
$w\in \mathcal {V}_{n+1}$
. The number of non-zero entries on each row is exactly
$|\mathcal {V}_1|$
. For polynomial diagrams those non-zero entries correspond exactly to the coefficients of
$p(x)$
. Further, for polynomial diagrams the column corresponding to a vertex
$w \in \mathcal {V}_{n+1}$
, with
$|S(w)|=|\mathcal {V}_1|$
, will have exactly
$|\mathcal {V}_1|$
non-zero entries that again correspond exactly to the coefficients of
$p(x)$
. This is most easily seen in polynomial diagrams of degree d associated to two variables, x and y. In this case, the associated diagrams can be drawn in such a manner that the incidence matrix representing the connections between levels n and
$n+1$
for each row i has non-zero entries in each position
$(i,i+k)$
, where
$0\leq k\leq d$
. Further, the
$(i,i+k)$
entry in the matrix is the coefficient of
$x^{d-k}y^k$
in
$p(x,y)$
. For example, the connections between level
$2$
and
$3$
of the polynomial diagram associated to
$p(x,y)=x^4+2x^3y+x^2y^2+3xy^3+y^4$
can be described by the 9 by 13 incidence matrix
See Figure 3. Multivariable polynomial shape systems have an analogous representation using higher-dimensional arrays.
For the rest of this work we assume that X refers to the path space of a polynomial shape diagram for which
$q\geq 2$
. This class of diagrams satisfies all the conditions mentioned in §2. Some polynomial shape diagrams that have previously been studied include the Euler and reverse Euler diagrams in any dimension, as well as the Stirling diagrams. See Figure 4.
The Euler, reverse Euler, and Stirling Bratteli diagrams.
Figure 4 Long description
The diagram consists of three distinct triangular Bratteli diagrams arranged horizontally. Each diagram starts with a single node at the top level zero and expands downward.
In the first diagram on the left, the Euler diagram, nodes are connected by single straight lines or double curved edges forming eye shapes. At level one, there are two nodes. At level two, there are three nodes where the outer edges are single lines and the inner connections are double edges. This pattern of increasing multiplicity in the center continues through level four.
In the second diagram in the center, the reverse Euler diagram, the edge multiplicities are inverted compared to the first. The outer diagonal edges often feature multiple curved lines, while some inner connections are single straight lines. The bottom level shows five nodes with varying numbers of curved edges between them, including some with four parallel curved lines.
In the third diagram on the right, the Stirling diagram, the connections follow a different distribution of multiplicities. The edges sloping down to the right are generally single lines, while the edges sloping down to the left feature multiple curved lines. The number of curved lines in these left-leaning edges increases as you move from the top right toward the bottom left of the triangular grid.
Remark 3.5. If
$u\in S(w)$
, then for all
$j\in \{1,2,\ldots , q\}$
,
$u(j)\leq w(j)\leq u(j)+d$
. This implies that if
$w,w'\in \mathcal {V}_{n+1}$
and
$S(w)\cap S(w')\neq \emptyset $
, then for each
$j\in \{1,\ldots q\}$
,
$|w(j)-w'(j)|\leq d$
. Likewise, if
$u,u'\in S(w)$
, then for each
$j\in \{1,\ldots q\}$
,
$|u(j)- u'(j)|\leq d$
. Further, the coordinates of each vertex in
$\mathcal {V}_{n+1}$
must sum to
$(n+1)d$
, and since there are exactly q coordinates, at least one coordinate is at least
$(n+1)d/q$
.
The following proposition gives a complete description of which paths in a polynomial shape diagram have dense orbits.
Proposition 3.6. In a polynomial shape diagram with path space X, a path
$x \in X$
has dense orbit if and only if
Proof. Recall (see the comments after Definition 3.3) that the set of vertices at level
$k\leq n$
that connect to a vertex
$v_n(x)$
at level n via a path of
$j=n-k$
edges is the set of non-negative vectors u in
$v_n(x)-(S+\cdots +S)$
(j times). Each such vertex u is on a path in the orbit of x. So for any k, given a vertex
$u\in \mathcal {V}_k$
, if for each
$i=1,\ldots ,q$
,
$v_n(x)(i)$
grows without bound as n goes to infinity, for large enough n we will have
$u\in v_n(x)-(S+\cdots +S)$
(with S repeated
$n-k$
times), and hence the orbit of x will meet all cylinder sets determined by paths from the root to u. Conversely, if for some
$j=1,\ldots ,q$
the entry
$v_n(x)(j)\leq M$
for all n, no vector u with
$u(j)>M$
can be on any path in the orbit of x. For example, one could take
$u=(M+1)e_j\sim x_j^{M+1}$
.
Proposition 3.7. For polynomial shape diagrams, for every ordering the sets of maximal and minimal paths have measure zero for every fully supported ergodic invariant (Borel probability) measure.
Proof. As mentioned above in Remark 2.4, we can adapt an argument from [Reference Berthé, Steiner, Thuswaldner and Yassawi5]. In [Reference Berthé, Steiner, Thuswaldner and Yassawi5], a diagram was defined to be everywhere growing if
${\text {min}}\{\dim v: v \in \mathcal V_n\} \to \infty $
as
$n \to \infty $
. Polynomial shape diagrams need not have this property, but we show that they almost do, in the sense that for each such diagram there is a finite (possibly empty) set of paths
$x^{(i)}, i=1, \ldots ,q,$
for which
$\dim v_n(x^{(i)})$
is bounded from above, while
${\text {min}}\{\dim v: v \in \mathcal V_n \setminus \bigcup _{1 \leq i \leq q} v_n(x^{(i)})\} \to \infty $
as
$n \to \infty $
.
Let
$\xi $
be an ordering of a polynomial shape diagram
$\mathcal B$
that is associated to a polynomial p, and let
$\mu $
be a fully supported ergodic measure on the path space X. Since larger coefficients lead to larger dimensions for the vertices, we may assume that all coefficients of p are equal to
$1$
, so that
For each
$i=1, \ldots , q$
, consider the path
$x^{(i)}$
such that
$v_n(x^{(i)}) = x_i^{nd} \sim nd e_i$
for all
$n \geq 1$
. Then
$\dim v_n(x^{(i)})=1$
for each i and n. Since
$\mu $
is a fully supported ergodic measure on X,
$\mu \{x^{(i)}\}=0$
for each
$i=1, \ldots , q$
. So to show that for any ordering the sets of minimal and maximal paths have measure
$0$
, we focus on paths not in this finite set.
As just mentioned above, the dimension of vertex
$v=(m_1, \ldots , m_q)$
(with
$\sum _i m_i=nd)$
at level n is the coefficient of
$x_1^{m_1} \cdots x_q^{m_q}$
in
$p(x_1, \ldots , x_q)^n$
. If
$v=(m_1, \ldots , m_q)$
is not one of the vertices
$x_i^{nd}$
(that is, at least two of the
$m_i$
are not equal to
$0$
), then
$\dim v \geq n$
.
(This may be seen as follows. The statement is obviously true for
$n=1$
. Any vertex
$v=x_1^{m_1} \cdots x_q^{m_q}$
at level
$n>1$
is not one of the special
$x_i^{nd}$
if and only if it has at least two of the exponents
$m_i$
positive; equivalently, if and only if it has at least two different source vertices. Thus, the statement is also true for
$n=2$
. Assume now that
$n>2$
, that
$\dim w \geq n-1$
for all
$w \in \mathcal V_{n-1}$
for which w is not one of the special
$x_i^{nd}$
, and that
$v \in \mathcal V_n$
has at least two source vertices,
$v_{n-1}$
and
$v^{\prime }_{n-1}$
. Then at least one of these, call it
$v_{n-1}$
, again has two source vertices, since otherwise both would equal some
$x_i^{(n-1)d}$
, and this cannot occur for
$n>2$
. Since
$\dim v \geq \dim v_{n-1} + \dim v^{\prime }_{n-1}$
and
$\dim v_{n-1} \geq n-1$
, we have
$\dim v \geq n$
.)
Let
$v \in \mathcal V_{n+1}$
be a vertex at level
$n +1$
. Each path
$\alpha = \alpha _0 \cdots \alpha _n$
from the root to v defines a cylinder set
$[\alpha ]=\{x \in X: x_{[0,n]}=\alpha \}$
, and all these cylinder sets have equal measure
where
$[v]=\{x \in X: v_{n+1}(x)=v\}$
. Denote by
$\mathcal V_{n+1}'$
the set of vertices in
$\mathcal V_{n+1}$
that are not any of the
$(n+1)de_i$
and by
$M_n$
the set of finite minimal paths with terminal vertex in
$\mathcal V_{n+1}'$
. If x is a minimal path that is not one of the
$x^{(i)}$
, then
$x_{[0,n]} \in M_n$
for all large enough n. For each
$v \in \mathcal V_{n+1}$
, there is exactly one finite minimal path from the root to v, so, as in [Reference Berthé, Steiner, Thuswaldner and Yassawi5, Lemma 6.2],
Similarly, the set of maximal paths has measure
$0$
.
Definition 3.8. For each
$j\in \{1,\ldots ,q\}$
, let
$e_j$
denote the standard jth basis vector in q-space. Given
$w\in \mathcal {V}_{n+1}$
, the distinguished source vertex of w in direction j, denoted
$DSV(w,j)$
, is the vertex
$w-de_j\in \mathcal {V}_n$
.
Remark 3.9. A vertex
$w\in \mathcal {V}_{n+1}$
has a distinguished source vertex in direction j if and only if
$w(j)\geq d$
. The
$DSV(w,j)$
is the vertex in the source set of w obtained by division of the monomial
$x_1^{w(1)}\cdots x_q^{w(q)}$
by
$x_j^d$
, reducing the exponent of
$x_j$
by the maximal possible amount while the other exponents are unchanged. See Figure 5.
$DSV(w,1)=(2,6)$
is shown in blue and
$DSV(w,2)= (6,2)$
is shown in red. Another vertex with
$DSV(w,1)$
in its source set has first coordinate less than
$w(1)=6$
. Likewise, a vertex with
$DSV(w,2)$
in its source set has second coordinate less than
$w(2)=6$
. (Color online.)
Figure 5 Long description
The graph is structured as a triangular lattice with five horizontal levels.
* At the top level is a single black vertex.
* The second level down contains five black vertices.
* The third level contains nine black vertices.
* The fourth level contains thirteen vertices. Within this level, the fourth vertex from the left is colored red, and the fourth vertex from the right is colored blue.
* The fifth and bottom level contains seventeen vertices. The central vertex of this bottom row is colored red and is positioned directly below a label box containing the text w equals open parenthesis 6 comma 6 close parenthesis.
Connections between levels consist of both straight lines and curved arcs. A highlighted red path connects the red vertex in the fourth level to the labeled red vertex in the fifth level. A highlighted blue path connects the blue vertex in the fourth level to the same labeled red vertex in the fifth level. The density of connections increases toward the center of the diagram.
The
$DSV(w_0,j)$
is in the source set of
$w_1$
and, hence,
$s(j)<d$
, which implies
$w_1(j)<w_0(j)$
.
Lemma 3.10. Let
$w_0,w_1\in \mathcal {V}_n$
with
$w_0\neq w_1$
. If
$DSV(w_0,j)\in S(w_1)$
, then
Proof. Assume
$DSV(w_0,j)\in S(w_1)$
. Then there exists
${s}\in S$
such that
$DSV(w_0,j)+{s}={w_1}$
. This gives
Since the coordinates of s are non-negative and sum to d,
$0\leq {s}(j)= {w_1}(j)-{w_0}(j)+d\leq d$
, implying that
If
${w_0}(j)-{w_1}(j)=0$
, this implies that
${s}=d{e_j}$
. However, then
${w_1}=DSV(w_0,j)+d{e_j}={w_0}.$
Since we assumed that
${w_0}\neq {w_1}$
, we must have
$w_0(j)-w_1(j) \neq 0$
. Hence,
See Figure 6.
Lemma 3.11. Let
$w_0,w_1\in \mathcal {V}_n$
. If
$DSV(w_0,j_1)\in S(w_1)$
and
$DSV(w_0,j_2)\in S(w_1)$
, where
$j_1\neq j_2$
, then
$w_1=w_0$
.
Proof. Recall from the definition of
$DSV(w,j)$
that
Therefore,
$w_0(j_1)=DSV(w_0,j_2)(j_1)$
. Since
$DSV(w_0,j_2)\in S(w_1)$
, by Remark 3.5,
$DSV(w_0,j_2)(j_1)\leq w_1(j_1)$
. So we have
$DSV(w_0,j_1)\in S(w_1)$
and
$w_0(j_1)\leq w_1(j_1).$
Then, by Lemma 3.10, it must be the case that
$w_1=w_0$
.
4 Covered and uncovered vertices
We are trying to prove that for polynomial shape diagrams, for every ordering and all large enough i there are no depth i pairs (outside of a negligible exceptional set), that is, no paths
$x,x'$
that have the same i coding but different
$i+1$
codings. If x and
$x'$
were a depth i pair, then for some
$m \in {\mathbb {Z}}$
,
$w=v_{i+1}(T^mx) \neq v_{i+1} (T^mx')=w'$
, and the source sets
$S(w)$
and
$S(w')$
intersect. Thus, we need to keep track of a key aspect of the interconnections among vertices in a diagram, namely which vertices at a given level have their source sets contained in those of other vertices at that level. This will allow precise tracking of vertices through which the depth i pair passes.
Definition 4.1. We say that a vertex w is covered if there is a vertex
$w' \neq w$
(at the same level as w) such that
$S(w) \subseteq S(w')$
, in which case we say that
$w'$
covers w. Otherwise w is said to be uncovered.
We show that for any depth i pair x,
$x'$
, the time m can be chosen so that w and
$w'$
are uncovered. For i sufficiently large, this will ensure that after time m the orbits of x and
$x'$
continue to pass through distinct uncovered vertices at level
$i+1$
for quite a while, essentially chasing each other at this level, while staying together at level i.
Lemma 3.11 implies that if a vector w has at least two distinct coordinates,
$j_1, j_2$
, for which
$DSV(w,j_1)$
and
$DSV(w,j_2)$
are defined, then w must be uncovered. While this is sufficient, it is not necessary. For example, for
$q\geq 3$
, the vertex on level
$2$
given by
$w=(d,d- 1,1,0,\ldots ,0)$
is uncovered (see Proposition 4.2), but the only distinguished source vertex for w that exists is
$DSV(w,1)$
(we need to subtract exactly d from a single entry of w to get a
$DSV$
). The following discussion gives necessary and sufficient conditions for a vertex to be covered, and in the case that it is covered, explicitly describes the vertices by which it is covered.
Proposition 4.2. A vertex w at a level
$n>q \geq 2$
is covered if and only if there is a
$j \in \{1, \ldots , q\}$
such that
$w(j)> (n-1)d$
.
Proof. We prove the first direction by proving the contrapositive. Suppose that
$w(i) \leq (n-1)d$
for all
$i \in \{1, \ldots , q\}$
. Because
$n>q$
, by Remark 3.5 there is at least one j with
$w(j) \geq d$
. Since
$\sum _{i=1}^qw(i)=nd$
and
$n>q\geq 2$
,
We make two vertices u and
$u'$
in the source set of w that cannot both be in the source set of any
$w' \neq w$
, as follows. Define
(so that
$u = DSV(w,j)$
). Note that
$\sum _iu(i)=(n-1)d$
.
For each
$i \neq j$
, choose
$n(i) \in [0,w(i)]$
so that
$\sum _{i \neq j} n(i)= \sum _{i \neq j} w(i)-d$
, and let
The idea is that to get
$u'$
from w, we subtract, in any possible way, a total of d from coordinates not equal to j. Hence,
$\sum _{i}u'(i)=(n-1)d$
.
By Lemma 3.10, for every
$w'$
such that
$u=DSV(w,j)\in S(w')$
and
$w'\neq w$
, we have
$w'(j)<w(j)$
. If
$s'=w'-u'$
is a non-negative vector with
$|s'|=d$
, and
$s'(j) \geq 0$
, then
$w'(j) \geq w(j)$
. So it is not possible that there is a
$w'$
with u and
$u'$
both in
$S(w')$
. Therefore, such a vertex w is uncovered.
To prove the converse, suppose that there is a
$j \in \{1, \ldots ,q\}$
such that
$w(j)> (n-1)d$
; we will prove that then w is covered. First, we have
$\sum _{i \neq j} w(i) < d$
, so that
Choose
$b \in [1,c(w)]$
, let
$\sigma $
be an integer vector with q components such that
$\sigma (j)=-b$
, choose
$\sigma (i) \geq 0$
for
$i \neq j$
such that
$\sum _{i \neq j} \sigma (i) =b$
, and let
$w'=w+\sigma $
. We claim that
$w'$
covers w.
Suppose that
$u \in S(w)$
. Then,
$u=w-s$
for some s; and
$s(j) \geq c(w)$
, since
$s(j)<c(w)$
implies
$|s|<c(w)+\sum _{i \neq j}s(i)\leq c(w) + \sum _{i \neq j}w(i)=d$
. Therefore, such a triple
$w, s, j$
satisfies the following useful condition.
Condition 4.3. The vertex
$w \in \mathcal V_n$
, non-negative integer vector s with
$|s|=d$
, and
$j\in \{1, \ldots , q\}$
satisfy
$w(j)>(n-1)d$
,
$s(i) \leq w(i)$
for all i, and
$s(j)\in [c(w),d]$
.
(Conversely, for any
$w, j,$
and s that satisfy Condition 4.3,
$u=w-s \in S(w)$
. In fact, the converse holds even if we no longer assume
$s(j)\in [c(w),d]$
.)
We know that
$1 \leq b \leq c(w) \leq s(j)$
, so
$s(j) \geq b$
. Therefore,
$s' = \sigma + s \geq 0$
and
$u+ s' = w'$
, showing that
$u \in S(w')$
. Hence,
$S(w) \subseteq S(w')$
, and w is covered.
Remark 4.4. The previous proposition is stated in terms of the definition of covered. We frequently use it to determine that a vertex is uncovered. In particular, Proposition 4.2 could be stated as follows: for
$n>q\geq 2$
, a vertex
$w\in \mathcal {V}_n$
is uncovered if and only if for every
$l\in \{1,\ldots ,q\}$
we have
$w(\ell )\leq (n-1)d$
or, equivalently, if there exists j for which
$d\leq w(j)\leq (n-1)d$
.
Continue to assume through the end of Remark 4.6 that
$n>q\geq 2$
. Now we will specify, given a covered vertex w, exactly which vertices
$w' \neq w$
cover w. Since this information is not used in our main argument, the proof is omitted.
Proposition 4.5. Suppose that
$n> q \geq 2$
. Let
$w,w'\in \mathcal {V}_n$
with
$w\neq w'$
. Assume that
$j \in \{1, \ldots , q\}$
satisfies
$w(j)>(n-1)d$
, so that w is covered. Let
$\sigma =w'-w$
(so that
$\Sigma \sigma (i)=0$
). Then
$w'$
covers w if and only if
$\sigma $
satisfies the following equivalent conditions with respect to w.
-
(1) For each choice of s satisfying Condition 4.3 with respect to w and j, we have $s \neq \sigma + s \geq 0$
. -
(2) Since $w \in \mathcal V_n$
and
$j \in \{1, \ldots ,q\}$
satisfy
$w(j)>(n-1)d$
, defining
$b=-\sigma (j)\in [1,c(w)]$
, we have
$\sigma (i) \geq 0$
for all
$i \neq j$
, and
$\sum _{i \neq j} \sigma (i) =b$
.
Moreover,
$w'=w+\sigma $
covers w and is itself uncovered if and only if
$\sigma $
satisfies condition (2) with
$b=c(w)$
.
Remark 4.6. The central part of Proposition 4.5 could be restated as follows. If there exists a
$j\in \{1,2,\ldots ,q\}$
such that
$w(j)>(n-1)d$
, then
$w'$
covers w if and only if for
$\sigma =w-w'$
we have
$-d\leq \sigma (j)<0$
, and for
$i\neq j$
,
$\sigma (j)\geq 0$
.
We mention a few more useful observations about uncovered vertices. By Remark 3.5, every vertex in
$\mathcal {V}_n$
has at least one coordinate greater than or equal to
$nd/q$
. Therefore, the hypothesis of the following lemma (Lemma 4.7) can be satisfied only if
$nd/q\leq (n-2)d$
, which implies that
$2q/(q-1)\leq n$
. See Figure 7.
Level 4 is the first level to have a vertex whose entire source set is uncovered. For a vertex source set to be entirely uncovered, all coordinates should be less than or equal to
$(n-2)d$
which, in this case, is
$2(4)=8$
.
Figure 7 Long description
The diagram consists of five horizontal levels of vertices connected by straight and curved edges.
* Level 1 at the top contains a single central vertex.
* Level 2 contains five vertices arranged symmetrically below the top vertex.
* Level 3 contains nine vertices with dense interconnections to the levels above and below.
* Level 4 contains thirteen vertices forming the widest part of the lattice.
* Level 5 at the bottom contains a single central vertex labeled with the coordinates open parenthesis 8 comma 8 close parenthesis.
The edges between levels include both direct straight lines and multiple curved arcs connecting the same pairs of vertices, indicating a complex multigraph structure. The density of connections is highest in the center of the diagram and tapers off toward the left and right edges.
Lemma 4.7. For
$n>q\geq 2$
, if
$w\in \mathcal {V}_n$
is such that for every
$l\in \{1,\ldots ,q\}$
,
$w(\ell )\leq (n-2)d$
, then every vertex in
$S(w)$
is uncovered.
Proof. Let
$u\in S(w)$
. By Remark 3.5, for all
$l\in \{1,\ldots ,q\}$
,
$u(\ell )\leq w(\ell )$
. Since
$u\in \mathcal {V}_{n-1}$
, by Remark 4.4 u is uncovered, since for every
$\ell \in \{i,\ldots , q\}$
,
$u(\ell )\leq (n-2)d$
.
Corollary 4.8. Given
$w\in \mathcal {V}_n$
, if there exists
$j \in \{1,\ldots ,q\}$
such that
$2d\leq w(j)\leq (n-2)d$
, then every vertex in
$S(w)$
is uncovered.
Proof. Since
$2d\leq w(j)$
, we have that
Hence,
$\sum _{l\neq j}w(\ell )\leq (n-2)d$
. Therefore, for each
$l\neq j$
we have that
$w(\ell )\leq (n-2)d$
, and, by assumption,
$w(j)\leq (n-2)d$
. Hence, for all
$\ell \in \{1,\ldots ,q\}$
,
$w(\ell )\leq (n-2)d$
. Then, by Lemma 4.7, every vertex in
$S(w)$
is uncovered.
Lemma 4.9. For
$n-1>q\geq 2$
, if
$u\in \mathcal {V}_{n-1}$
is uncovered and
$u\in S(w)$
, then w is uncovered.
Vertex
$(4,4)$
, pictured in red, in level
$2$
is uncovered, and every vertex in level
$3$
with
$(4,4)$
its source set, pictured in blue, is also uncovered. (Color online.)
Figure 8 Long description
The network is organized into four horizontal levels forming a triangular shape.
At the top level, level 1, is a single black vertex.
Level 2 contains five black vertices arranged horizontally. Each vertex in level 2 is connected to the single vertex in level 1 by multiple lines.
Level 3 contains nine vertices. The central vertex is highlighted in red. The other eight vertices are black. These vertices are connected to the level above by a dense web of straight and curved lines.
Level 4, the base, contains thirteen vertices. Five of these vertices, located in the center of the row, are highlighted in blue. The remaining eight vertices, four on each end, are black. A complex network of lines connects the vertices of level 4 to those in level 3, showing a high degree of connectivity between the blue vertices and the red vertex above them.
Proof. Assume
$u\in \mathcal {V}_{n-1}$
is uncovered. By Remark 4.4, for all
$l\in \{1,\ldots ,q\}$
,
$u(\ell )\leq (n-2)d$
. Further, for all
$\ell \in \{1,\ldots ,q\}$
,
$w(\ell )\leq u(\ell )+d$
(by Remark 3.5). So,
$w(\ell )\leq u(\ell )+d\leq (n-2)d+d=(n-1)d$
. Then, by Remark 4.4, w is uncovered. See Figure 8.
5 Chains and links
In this section we develop some of the machinery that is used in the main theorem, continuing to work in a fixed polynomial shape diagram with path space X.
As mentioned at the beginning of §4, we show that any depth i pair will, at some time, meet distinct uncovered vertices at level
$i+1$
, and these vertices are linked together via edges connecting them to the vertex at level i met by both orbits at this time. The orbits of x and
$x'$
will then continue to meet distinct uncovered vertices (and for i large, this will continue for quite a while), essentially chasing each other at level
$i+1$
, while staying together at level i. Tracking these orbits will produce a sequence of vertices at level
$i+1$
that are met in an alternating manner by the orbits of x and
$x'$
, respectively. Any two consecutive vertices in the sequence will be linked by a vertex at level i that is met simultaneously by both orbits, producing what we refer to as an x,
$x'$
chain.
Definition 5.1. Given
$k, n\geq 1$
, a chain of length k at level n is a double sequence
of vertices
$w_0, \ldots , w_k$
at level n, called splitting vertices, and
$u_0, \ldots , u_{k-1}$
at level
$n-1$
, called shared vertices, such that for every
$0 \leq \ell < k$
,
$u_{\ell } \in S(w_{\ell }) \cap S(w_{\ell +1})$
. We say that the chain links the two vertices
$w_0$
and
$w_k$
. The chain is straight if all vertices are distinct. A chain of length
$1$
is called a link.
Definition 5.2. We say that a straight chain
is a distinguished chain in direction j if for each
$1\leq \ell < k$
,
$u_\ell $
is
$DSV(w_{\ell },j)$
.
We do not want to impose in the above definition any restrictions on
$u_0$
because our ultimate goal is to extend any arbitrary link to a distinguished chain. The coordinate description of the distinguished source vertex allows us to specify a direction (direction j, for some j) in which to keep moving, to ensure that our chain is straight. The following definition will be applied to a depth i pair to find sequences of vertices at levels i and
$i+1$
that eventually cause a contradiction.
Definition 5.3. For
$i \geq 1$
and a pair of paths
$x,x'$
, a chain
of length k at level
$i+1$
is called an
$x,x'$
chain if there is a strictly monotonic sequence of integers
$m_0=0,m_1, \ldots , m_{k-1}$
, called the switching times, such that
for each
$1 \leq \ell \leq k$
,
$u_{\ell }=v_{i}(T^{m_{\ell }}x)=v_i(T^{m_{\ell }}x')$
;
$w_0=v_{i+1}(x)$
,
$w_1=v_{i+1}(x')$
;
for odd
$\ell \in [1,k)$
,
$w_{\ell }=v_{i+1}(T^{m_{\ell -1}}x')=v_{i+1}(T^{m_{\ell }}x')$
;
for even
$\ell \in [2,k)$
,
$w_{\ell }=v_{i+1}(T^{m_{\ell -1}}x)=v_{i+1}(T^{m_{\ell }}x)$
;
and
$w_k=v_{i+1}(T^{m_{k-1}}x)$
if k is even,
$w_k=v_{i+1}(T^{m_{k-1}}x')$
if k is odd.
An
$x,x'$
chain of length
$1$
is called an
$x,x'$
link. See Figure 9.
An example of an
$x,x'$
chain of length k, where k is even. Other vertices are allowed, but those pictured are those that make up the chain.
Figure 9 Long description
The graph consists of two horizontal rows of vertices. The bottom row contains vertices labeled w sub 0, w sub 1, w sub 2, w sub k minus 1, and w sub k. The top row contains vertices labeled u sub 0, u sub 1, u sub 2, and u sub k minus 1. The path zigzags between these rows.
Starting from the left
1. Vertex w sub 0 connects upward to u sub 0. The edge is labeled x sub i.
2. Vertex u sub 0 connects downward to w sub 1. The edge is labeled x prime sub i.
3. Vertex w sub 1 connects upward to u sub 1. The edge is labeled open parenthesis T super m sub 1 x prime close parenthesis sub i.
4. Vertex u sub 1 connects downward to w sub 2. The edge is labeled open parenthesis T super m sub 1 x close parenthesis sub i.
5. Vertex w sub 2 connects upward to u sub 2. The edge is labeled open parenthesis T super m sub 2 x close parenthesis sub i.
6. A horizontal dotted line indicates a continuation of the pattern between u sub 2 and u sub k minus 2.
7. Vertex w sub k minus 1 connects upward to u sub k minus 2. The edge is labeled open parenthesis T super m sub k minus 2 x prime close parenthesis sub i.
8. Vertex w sub k minus 1 also connects upward to u sub k minus 1. The edge is labeled open parenthesis T super m sub k minus 1 x prime close parenthesis sub i.
9. Vertex u sub k minus 1 connects downward to w sub k. The edge is labeled open parenthesis T super m sub k minus 1 x close parenthesis sub i.
Lemma 5.4. [Link Lemma]
For
$i>q\geq 2$
, if
$x,x'$
is a depth i pair of paths, then every straight
$x,x'$
link
$w_0 \overset {u_0}{\longleftrightarrow } w_1$
with
$v_{i+1}(x)=w_0$
,
$v_{i+1}(x')=w_1$
, such that there exists a
$j\in \{1,\ldots ,q\}$
for which
$2d\leq w_1(j)\leq w_0(j)\leq (i-1)d$
, extends to a straight
$x,x'$
chain of length
$2$
with
$m_1$
, as in the definition of an
$x,x'$
chain, satisfying
$v_{i+1}(T^{m_1}x')=w_1$
,
$v_{i+1}(T^{m_1}x)=w_2$
, and moreover for all
$m\in [0,m_1]$
,
$v_{i+1}(T^mx')=w_1$
and
$v_{i+1}(T^mx)\in \{w_0,w_2\}$
.
Proof. By assumption, there exists a j such that
$2d\leq w_1(j)\leq w_0(j)\leq (i-1)d$
, which by Remark 4.4 is more than sufficient to ensure that
$w_0$
and
$w_1$
are both uncovered. Since
$w_1(j)\leq w_0(j)$
, by Lemma 3.10
$DSV(w_1,j) \notin S(w_0)$
. In particular,
$DSV(w_1,j) \neq u_0 =v_i(x')$
. Choose
$m_1 \neq 0$
with
$|m_1|$
minimal such that
$v_i(T^{m_1}x')=DSV(w_1,j)$
, and for all
$m\in [0,m_1]$
(or
$[m_1,0]$
if
$m_1<0$
),
$v_{i+1}(T^mx')=w_1$
. Then define
$w_2=v_{i+1}(T^{m_1}x)$
. Replacing T by
$T^{-1}$
if necessary, assume
$m_1>0$
. Since
$x,x'$
are depth i,
$v_i(T^{m_1}x)=DSV(w_1,j)$
and
$m_1$
is also the first time that the forward orbit of x hits
$DSV(w_1,j)$
.
Since
$DSV(w_1,j) \notin S(w_0)$
,
$w_2 \neq w_0$
. We claim that also
$w_2 \neq w_1$
. Suppose, to the contrary, that
$w_2=w_1$
. By the way we chose
$m_1$
,
$x'$
is still at
$w_1$
at time
$m_1$
. Look at the edge numbers based at
$w_1$
. The orbit of x has entered
$w_1$
before or at time
$m_1$
, but after
$x'$
(which is at
$w_1$
at time
$0$
), so
$\xi ((T^{m_1}x)_{i}) < \xi ((T^{m_1}x')_{i})$
. In other words,
$(T^{m_1}x)_i$
connects
$w_1$
and
$DSV(w_1,j)$
, as does
$(T^{m_1}x')_i$
, and
$(T^{m_1}x)_i$
has smaller edge label than
$(T^{m_1}x')_i$
.
Going backwards in time, the orbit of
$x'$
has to hit
$DSV(w_1,j)$
again. Hence, it passes through edge
$(T^{m_1}x)_i$
at some time
$m_2<m_1$
. Specifically, the backward orbit of
$x'$
goes through edges based at
$w_1$
, starting at edge number
$\xi ((T^{m_1}x')_{i})$
and working down to edge number
$\xi ((T^{m_1}x)_{i})$
. It stays at
$w_1$
all this time, at least through time
$m_2$
. By the minimality of
$m_1$
, there is no time m in
$[0,m_1)$
such that
$v_i(T^mx')=DSV(w_1,j)$
. Therefore, it is necessarily the case that
$m_2<0$
. For all
$m\in [m_2,m_1]$
, since
$v_{i+1}(T^mx')=w_1$
, we have
$v_i(T^mx')=v_i(T^mx)\in S(w_1)$
. Further, since
$DSV(w_1,j)\notin S(w_0)$
, we know that
$v_i(T^{m_2}x)\neq w_0$
. Therefore, we have that
$v_i(T^{m_2}x)\neq w_0, v_i(x)=w_0$
, and
$v_i(T^{m_1}x)\neq w_0$
. Then, by the definition of the Vershik map, the orbit of x must pass through every vertex in
$S(w_0)$
between time
$m_2$
and
$m_1$
. Hence, it is necessarily the case that
$S(w_0)\subseteq S(w_1)$
and
$w_1$
covers
$w_0$
. This contradicts our assumption that
$w_0$
is uncovered, proving that
$w_2\neq w_1$
and
is a straight
$x,x'$
chain of length
$2$
.
We claim that between times
$0$
and
$m_1$
, the orbit of x cannot pass through any vertices at level
$i+1$
other than
$w_0$
and
$w_2$
. For all m in
$[0,m_1]$
,
$v_{i+1}(T^mx')=w_{1}$
and hence
$v_{i}(T^mx')\in S(w_{1})$
; further, since x and
$x'$
are a depth i pair,
$v_i(T^mx)=v_i(T^mx')\in S(w_1)$
. Therefore, if the orbit of x leaves
$w_{0}$
and passes through some vertex
$w\neq w_{2}$
between time
$0$
and
$m_{1}$
, then w must be covered by
$w_{1}$
.
However, since
$2d\leq w_{1}(j)\leq (i-1)d$
, by Corollary 4.8 every vertex in
$S(w_{1})$
is uncovered. In particular, for each
$m\in [0, m_1]$
,
$v_{i}(T^mx)$
is uncovered. Then, by Lemma 4.9,
$v_{i+1}(T^mx)$
is also uncovered. In particular,
$v_{i+1}(T^mx)$
cannot be covered by
$w_{1}$
. Therefore, between time
$0$
and
$m_{1}$
the orbit of x can only pass through the vertices
$w_{0}$
and
$w_{2}$
.
6 Inherent expansiveness of polynomial shape diagrams
Here, X continues to denote the path space of a fixed polynomial shape diagram (Definition 3.1). We intend to prove that outside of the negligible exceptional set defined above (Definition 2.1), there are no pairs of paths of any large enough depth. The idea is to show that for any sufficiently large i and any possible depth i pair
$x,x'$
in
$X(\xi )$
(the set of paths which are not in the orbit of any maximal or minimal path and have dense biinfinite orbits), one can construct a distinguished
$x,x'$
chain in which the splitting vertices are uncovered and the orbits of x and
$x'$
meet vertices of the chain in an alternating manner. The chain will have sufficient length (
$2d+3$
) to ensure that when we look at level
$i+2$
, we find that the alternation contradicts the definition of the Vershik map. To construct this chain, it will be necessary to find two uncovered vertices forming a link (Lemma 6.1), each with jth component of size at least
$2d^2+4d$
for some
$j\in \{1,\ldots ,q\}$
, with which to start the chain. The following lemma allows us to find such a link if we look low enough in the diagram.
Lemma 6.1. (Chain starting)
Let an ordering
$\xi $
be given,
$N= 4dq+6q$
, and
$i>N$
. For any depth i pair
$x,x'\in X(\xi )$
, there exists a time in their orbits when, at level
$i+1$
, they pass through distinct uncovered vertices v and
$v'$
for which there is a
$j\in \{1,2,\ldots ,q\}$
such that
Proof. Let
$\xi $
be given,
$i>N$
, and suppose that
$x,x'\in X(\xi )$
is a depth i pair. Then, by Proposition 2.11, there is a time in their orbits such that x and
$x'$
pass through different vertices at level
$i+1$
, say
$w_0$
and
$w_0'$
, respectively. Without loss of generality, assume this happens at time
$0$
.
Since
$w_0,w_0'\in \mathcal {V}_{i+1}$
and
$i+1\geq 4dq+6q$
, Remark 3.5 tells us that they each have a component (not necessarily the same one) of size at least
Let
$j\in \{1,\ldots ,q\}$
such that
$w_0'(j)\geq 4d^2+6d$
. Since
$v_{i}(x)=v_{i}(x')$
,
$w_0$
and
$w_0'$
share a common source vertex and hence each of their components differ by at most d. (See Remark 3.5.) Therefore, the jth components of both vertices are of size at least
$4d^2+5d$
. Switching names if necessary, assume
$4d^2+5d\leq w_0(j)\leq w_0'(j)$
.
We do not know if our initial
$w_0$
and
$w^{\prime }_0$
meet the conditions of (6.1) or not. However, the following procedure produces two new vertices that meet the conditions of (6.1), regardless of whether
$w_0$
and
$w^{\prime }_0$
do. We produce an
$x,x'$
chain of length
$2d+2$
starting with the link between
$w^{\prime }_0$
and
$w_0$
for which the jth components of the splitting vertices are decreasing by at least one and by at most d each time. Since we know that
$4d^2+5d\leq w_0(j)\leq (i+1)d$
, the splitting vertex
$w_{2d+1}$
at the end of the chain must have jth component at most
$(i+1)d-(2d+1)=(i-1)d-1<(i-1)d$
, but at least
$4d^2+5d-(2d+1)d=2d^2+4d>2d$
, and hence be uncovered and have all vertices in its source set uncovered, by Corollary 4.8. (The ultimate goal is to have the end of this chain start (in the next theorem) a new chain of adequate length for which every splitting vertex has an uncovered source set. The above-mentioned vertex
$w_{2d+1}$
having jth component
$2d^2+4d$
accomplishes this.)
Switching to
$T^{-1}$
if necessary, let
$m_1>0$
be the first time in the orbit of x such that
$v_i(T^{m_1}x)=DSV(w_0,j)$
and for all m in
$[0,m_1]$
,
$v_{i+1}(T^mx)=w_0$
. First, consider the case in which
$v_{i+1}(T^{m_1}x')=w_0$
. Then the orbit of
$x'$
enters
$w_0$
after x, so
$\xi ((T^{m_1}x')_{i}) <\xi ((T^{m_1}x)_{i})$
. By density, the orbits of x and
$x'$
must eventually leave
$w_0$
, but
$\xi ((T^{m_1}x')_{i}) <\xi ((T^{m_1}x)_{i})$
implies this must occur at different times. Let
$n_1> m_1$
be the first time that
$v_i(T^{n_1}x)=v_i(T^{n_1}x')=DSV(w_0,j)$
and
$v_{i+1} (T^{n_1}x)\neq v_{i+1}(T^{n_1}x')$
. In other words,
$n_1$
is the first time after one of these orbits (of x and
$x'$
) leave
$w_0$
that both orbits meet the
$DSV(w_0,j)$
.
Without loss of generality, assume the orbit of
$x'$
leaves
$w_0$
first. We claim that
$v_{i+1} (T^{n_1}x)=w_0$
. Consider the last time
$n^{\prime }_1<n_1$
that
$v_i(T^{n^{\prime }_1}x)=v_i(T^{n^{\prime }_1}x')=DSV(w_0,j)$
and
$v_{i+1}(T^{n^{\prime }_1}x)= v_{i+1}(T^{n^{\prime }_1}x')=w_0$
. Then
$\xi ((T^{n^{\prime }_1}x)_i)<\xi ((T^{n^{\prime }_1}x')_i)$
(since
$x'$
leaves
$w_0$
first) implies the forward orbit of
$T^{n^{\prime }_1}x$
must still pass through
$(T^{n_1'}x')_i$
before it can leave
$w_0$
. In particular, this happens after time
$n^{\prime }_1$
. Since
$n_1$
is the first time after
$n^{\prime }_1$
that the orbits of x and
$x'$
visit
$DSV(w_0,j)$
, it must be the case that the orbit of x is still at
$w_0$
at time
$n_1$
. So we have that
$v_{i+1}(T^{n_1}x)=w_0$
and
$v_{i+1}(T^{n_1}x')\neq w_0$
. See Figure 10.
$\xi ((T^{n_1'}x)_i)<\xi ((T^{n_1'}x')_i)$
and so the orbit of x must pass through
$(T^{n_1'}x')_i$
at some time greater than or equal to time
$n_1$
, and hence, is still at vertex
$w_0$
at time
$n_1$
.
For the second case in which
$v_{i+1}(T^{m_1}x')\neq w_0$
, let
$n_1=m_1$
. Then, in either case, we have
$v_i(T^{n_1}x)=v_i(T^{n_1}x')=DSV(w_0,j)$
,
$v_{i+1}(T^{n_1}x)=w_0$
, and
$v_{i+1}(T^{n_1}x')\neq w_0$
. Call
$v_{i+1}(T^{n_1}x')=w_1$
. Then
$w_1\neq w_0$
, but
$DSV(w_0,j)\in S(w_1)$
. So by Lemma 3.10 and Remark 3.5,
$1\leq w_0(j)-w_1(j)\leq d$
. Furthermore, since
$w_0'(j)\geq w_0(j)$
, Lemma 3.10 also implies that
$DSV(w_0,j)\notin S(w_0')$
, indicating that
$w_1 \neq w_0'$
.
Since
$S(w_1)\cap S(w_0)\neq \emptyset $
, by Remark 3.5
$w_1(j)\geq 4d^2+4d>d$
. Hence, by Remark 3.9,
$DSV(w_1,j)$
exists. Arguing as above, there exists a smallest
$n_2>n_1$
such that
$v_i(T^{n_2}x)=v_i(T^{n_2}x')=DSV(w_1,j)$
and
$v_{i+1} (T^{n_2}x)\neq v_{i+1}(T^{n_2}x')$
. Therefore, one of
$v_{i+1}(T^{n_2}x)$
and
$v_{i+1} (T^{n_2}x')$
must be
$w_1$
. Let the other be
$w_2$
. Then we have
$2\leq w_0(j)-w_2(j)\leq 2d$
. Continue in this manner to define
$w_3, w_2,\ldots , w_{2d},w_{2d+1}$
. See Figure 11.
We build the chain where for
$l\geq 1$
,
$u_l=v_i(T^{n_l}x)=v_i(T^{n_l}x')$
and
$w_l$
is
$v_{i+1}(T^{n_l}x)$
or
$v_{i+1}(T^{n_l}x')$
, and
$w_{l-1}$
is the other vertex.
As
$\ell $
increases from
$0$
to
$2d$
, the jth coordinate of
$w_\ell $
decreases by at least one each time and by at most d each time. Therefore, by the time we produce
$w_{2d}$
, the jth coordinate has decreased by at least
$2d$
from the jth coordinate of
$w_0$
, ensuring that
$w_{2d}(j)\leq w_0(j)-2d\leq (i+1)d-2d=(i-1) d$
. Further, the jth coordinate decreases by at most
$2d^2$
.
Then we have
so that
Also,
$w_{2d}(j)-w_{2d+1}(j)\leq d$
implies that
and hence
Further, since the jth component is decreasing each time,
$w_{2d}$
and
$w_{2d+1}$
are distinct and
$2d^2+4d\leq w_{2d+1}(j)<w_{2d}(j)\leq (i-1) d<id$
. Hence, by Remark 4.4,
$v=w_{2d}$
and
$v'=w_{2d+1}$
are distinct uncovered vertices. Therefore, we have shown that the (dense) orbits of the depth i pair
$x,x'$
pass through distinct uncovered vertices v and
$v'$
for which
$2d^2+4d\leq v'(j) <v(j)\leq (i-1) d<id$
.
Lemma 6.2. Let
$z\in \mathcal {V}_{n+1}$
and
$j\in \{1,2,\ldots ,q\}$
be such that
$d\leq z(j)\leq nd$
. Then there exist
$w_0,w_1,\ldots , w_d\in S(z)$
such that
$w_{\ell }(j)=z(j)-\ell $
for all
$\ell =0,1,\ldots ,d$
.
Proof. Since
$d\leq z(j)\leq nd$
and
$\sum _{i=1}^qz(i)= (n+1)d$
, we have
$d\leq \sum _{i\neq j}z(i)\leq nd$
. We can then find an
${s}_0\in S$
such that
$s_0(j)=0$
,
$\sum _{i\neq j}s_0(i)=d$
and
$z-s_0$
has all non-negative coordinates. Hence,
$w_0=z-s_0\in \mathcal {V}_n$
. This means
$w_0\in S(z)$
and
$w_0(j)=z(j)$
. We proceed in a recursive manner. Since
$\sum _{i\neq j}s_0(i)=d$
, there exists a
$j_1\neq j$
such that
$s_0(j_1)\geq 1$
. Define
$s_1=s_0-e_{j_1}+e_j$
(recalling that
$e_{j_1}$
and
$e_j$
are standard basis vectors in q-space) and let
${w}_1={z}-{s_1}$
. Then
$w_1$
has all coordinates non-negative, and hence is in
$\mathcal {V}_n$
and
$S(z)$
. Further,
$\sum _{i\neq j}s_1(i)=d-1$
,
$s_1(j)=1$
, and
$w_1(j)=z(j)-s_1(j)=z(j)-1$
. We continue recursively, producing
$s_{\ell }\in S(z)$
from
$s_{\ell -1}$
for each
$\ell \leq d$
. Specifically, given that
$\sum _{i\neq j}s_{\ell -1}(i)=d-(\ell -1)$
and
$s_{\ell -1}(j)=\ell -1$
for some
$\ell \leq d$
, choose
$j_{\ell }\neq j$
such that
$s_{\ell -1}(j_{\ell })\geq 1$
and define
$s_{\ell }=s_{\ell -1}-e_{j_{\ell }}+e_j$
. Then define
$w_{\ell }=z-s_{\ell }$
. So,
$s_{\ell }(j)=\ell $
,
$\sum _{i\neq j}s_{\ell }(i)=d-\ell $
, and
$w_{\ell } \geq 0$
. Hence,
$w_{\ell } \in S(z)$
and
$w_{\ell }(j)=z(j)-\ell $
.
Recall that, given an ordering
$\xi $
,
$X(\xi )$
denotes the set of paths which are not in the orbit of any maximal or minimal path and have a dense (biinfinite) orbit. By Propositions 2.3 and 3.7 (and Remark 2.4),
$X(\xi )$
is comeager and has full measure with respect to every fully supported ergodic invariant measure on X.
Theorem 6.3. Suppose we have an unordered polynomial shape Bratteli diagram
$\mathcal B=(\mathcal V,\mathcal E)$
, with path space X. Then, for any ordering
$\xi $
of the diagram, there exists N such that for each
$i\geq N$
there is no depth i pair of paths in
$X(\xi )$
. That is, the Bratteli diagram defining X is inherently expansive: for every ordering
$\xi $
of X the Vershik map is expansive on
$X(\xi )$
.
Proof. Let
$\xi $
be an ordering of
$\mathcal B$
and choose
$N=4dq+6q$
. Suppose to the contrary that for some
$i\geq N$
there exists a depth i pair
$x, x'$
in
$X(\xi )$
. Then, by Lemma 6.1, there exists a time when the orbits of x and
$x'$
pass through distinct uncovered vertices
$w_0$
and
$w_1$
, respectively, at level
$i+1$
such that for some
$j\in \{1,2,\ldots ,q\}$
,
$ 2d^2+4d\leq w_1(j)<w_0(j)\leq (i-1)d$
. Then, by Lemma 5.4, the link
$w_0 \overset {u_1}{\longleftrightarrow } w_1$
extends to a distinguished
$x,x'$
chain of length 2,
for which there exists an
$m_1$
such that
$v_{i+1}(T^{m_1}x')=w_1$
,
$v_{i+1}(T^{m_1}x)=w_2$
, and for all
$m\in [0,m_1]$
we have
$v_{i+1}(T^mx')=w_1$
and
$v_{i+1}(T^mx)\in \{w_0,w_2\}$
.
Since
$DSV(w_1,j)\in S(w_2)$
, by Lemma 3.10 and Remark 3.5
$1\leq w_1(j)-w_2(j)\leq d$
. Together with the fact that
$2d^2+4d\leq w_1(j)\leq (i- 1)d $
, we have that
$2d<2d^2+3d\leq w_2(j)\leq (i-1)d$
. Hence, by Lemma 5.4, we can extend the chain again. Continue in this manner to produce a distinguished
$x,x'$
chain:
Specifically, given
$1<\ell \leq 2d+2$
and a
$w_\ell $
, we have
$2d\leq 2d^2+4d-(\ell -1)d\leq w_{\ell }(j)\leq (i-1)d$
. Then use the Link Lemma to extend the chain to
$w_{\ell +1}$
, where for
$\ell>1$
,
$u_{\ell +1}=DSV(w_{\ell },j)$
and, by Lemma 3.10,
$w_0(j)>w_1(j)>\cdots >w_{2d+3}(j)$
. This means all the splitting vertices are distinct and, by Remark 4.4, uncovered.
By construction of the distinguished chain via the Link Lemma (Lemma 5.4), the orbit of x only passes through even numbered splitting vertices and the orbit of
$x'$
only passes through odd numbered splitting vertices, while moving through the chain. Further, since the jth component of the splitting vertices are strictly decreasing, for all
$\ell \geq 2$
,
$w_{\ell }(j)-w_{\ell +1}(j)\geq 1$
for all
$\ell \in \{1,\ldots ,2d+2\}$
. So the jth components of odd vertices differ by at least 2. Since the orbit of
$x'$
passes through only odd numbered vertices, then for each
$l\in \{0,1,\ldots ,d+1\}$
, there is no
$m\in [0,m_{2d+2}]$
such that
$v_{i+1}(T^mx')(j)=w_{2l+1}(j)-1$
or
$w_{2l+1}(j)+1$
. See Figure 12.
For
$l\geq 1$
,
$u_l=DSV(w_l,j)$
.
Figure 12 Long description
The diagram consists of two horizontal rows of nodes. The bottom row contains nodes labeled w sub 0, w sub 1, w sub 2, w sub 3, followed by an ellipsis, and then w sub 2 d plus 1, w sub 2 d plus 2, and w sub 2 d plus 3. The top row contains nodes labeled u sub 0, u sub 1, u sub 2, followed by an ellipsis, and then u sub 2 d plus 1 and u sub 2 d plus 2.
Edges connect the nodes in a continuous zigzag path from left to right.
1. From w sub 0 up to u sub 0, labeled x.
2. From u sub 0 down to w sub 1, labeled x prime.
3. From w sub 1 up to u sub 1, labeled T super m sub 1 x prime.
4. From u sub 1 down to w sub 2, labeled T super m sub 1 x.
5. From w sub 2 up to u sub 2, labeled T super m sub 2 x.
6. From u sub 2 down to w sub 3, labeled T super m sub 2 x prime.
After the ellipsis, the pattern continues.
7. From w sub 2 d plus 1 up to u sub 2 d plus 1, labeled T super m sub 2 d plus 1 x prime.
8. From u sub 2 d plus 1 down to w sub 2 d plus 2, labeled T super m sub 2 d plus 1 x.
9. From w sub 2 d plus 2 up to u sub 2 d plus 2, labeled T super m sub 2 d plus 2 x.
10. From u sub 2 d plus 2 down to w sub 2 d plus 3, labeled T super m sub 2 d plus 2 x prime.
To understand the switching of vertices at level
$i+1$
of the two orbits, it is necessary to consider vertices at levels lower than
$i+1$
. In fact, we show that we do not have to look any lower than level
$i+2$
. We show that while the chain is being traversed, the orbit of
$x'$
hits a vertex z at level
$i+2$
such that it cannot hit all vertices in
$S(z)$
.
Let
$v_{i+2}(x')=z'$
. Then
$w_1\in S(z')$
. Recall that for
$l\geq 2$
,
$w_{1}(j)-w_l(j)\geq l-1$
. Since the jth coordinates of vertices in the same source set differ by at most d (Remark 3.5), for
$\ell \geq d+2$
,
$w_l\notin S(z')$
. Therefore, there is an
$m\in (0,m_{d+2}]$
such that
$T^mx'$
is minimal into level
$i+2$
and
$v_{i+2}(T^mx')=z\neq z'$
. Further,
$v_{i+1}(T^mx')$
is some odd numbered splitting vertex
$w_t$
with
$t\leq d+2$
. By the way we have constructed our chain, we have that
$2d\leq w_{t}(j)\leq (i-1)d$
. Since
$w_t\in S(z)$
, it follows that
$2d\leq z(j)\leq id$
.
Let
$r=w_t(j)$
, where
$w_t$
is as above, so that
$z(j) \geq r$
. In the case
$z(j)=r$
, by Lemma 6.2 we would have a vertex
$v\in S(z)$
such that
$v(j)=z(j)-1=r-1$
. In the case that
$r+1\leq z(j)\leq r+d$
,
$z(j)-(r+1)$
is in the set
$\{0,\ldots , d-1\}$
. Then, by Lemma 6.2, there is a vertex
$v\in S(z)$
such that
$v(j)=z(j)-(z(j)-(r+1))=r+1$
. Combining these two cases, we have that there is a vertex
$v\in S(z)$
such that either
$v(j)=r-1$
or
$v(j)=r+1$
.
Note that since
$t\leq d+2$
,
$w_{t}(j)-w_{2d+3}(j)\geq w_{d+2}(j)-w_{2d+3}(j)\geq 2d+3-(d+2)=d+1$
. Hence (again by Remark 3.5),
$v_{i+1}(T^{m_{2d+2}}x')=w_{2d+3}\notin S(z)$
. See Figure 13.
The orbit of
$x'$
must pass through at least 3 distinct vertices at level
$i+2$
between time
$0$
and
$m_{2d+2}$
. So, it must pass through all the vertices in
$S(z)$
between time
$1$
and
$m_{2d+2}$
.
By the definition of the Vershik map, between time m and time
$m_{2d+2}$
the orbit of
$x'$
must pass through all of the vertices in
$S(z)$
. However, this contradicts the fact that there is no
$m'\in [0,m_{2d+2}]$
such that
$v_{i+1}(T^{m'}x')(j)=r-1$
or
$r+1$
. Therefore, there can be no depth i pair of paths, each with a dense infinite orbit.
Remark 6.4. The constructions and arguments presented above might extend to more general systems, beyond polynomial shape. As a first step, one could consider systems defined by different polynomials at different levels, adjusting the degree and the number of variables at each level. Even more generally, the properties of polynomial shape systems that allow for the construction of chains can be abstracted to define a class of diagrams, free of coordinate representations for vertices and all the accompanying structure, for which one might still be able to prove inherent expansiveness. Complete details have not yet been established.
Acknowledgements
The authors thank the referees for a careful reading of the manuscript and for helpful comments and suggestions that improved the presentation of this paper.
