{'fraction_non_alphanumeric': 0.05998434704830054, 'fraction_numerical': 0.011683810375670841, 'mean_word_length': 3.437856611262714, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Extracting invariant of conjugacy from independence entropy

The concept of independence entropy for symbolic dynamical systems was introduced in [LMP13]. This notion of entropy measures the extent to which one can freely insert symbols in positions without violating the constraints defined by the shift space. Independence entropy is not invariant under topological conjugacy. We define an invariant version of the independence entropy by setting sup h_{ind}(X) = sup{h_{ind}(Y )|Y ' X}. This invariant is bounded above by the topological entropy. We prove that equality sup h_{ind}(X) = h(X) holds for all sofic shift spaces over Z, then we give an example showing that equality does not hold for general shift spaces.


Introduction
We are concerned with invariants of shift spaces (X, σ) ⊆ (A Z d , σ), where A is a finite alphabet and σ is the shift. Topological entropy is the most fundamental numerical invariant associated to a d-dimensional shift space. When d = 1 and X is either of finite type (SFT), or a sofic shift, the topological entropy is easy to compute as the log of the largest eigenvalue of a non-negative integer matrix. However, when d = 2 there is no known explicit expression for the topological entropy of SFTs, even for the simplest non-trivial examples. The notion of independence entropy of a shift space defined in [LMP13] comes to measure the part of the entropy resulting from inter-symbol independence in elements of the shift space. The notion of independence entropy is not invariant under topological conjugacy. Still we can define an invariant notion: sup h ind (X) = sup{h ind (Y )|Y ≃ X}, which is bounded above by the topological entropy.
The aim of this paper is to prove the following theorems: Theorem 1.1. Let X be a one-dimensional sofic shift over an alphabet A. Then sup h ind (X) = h(X).
Theorem 1.2. There exists a one-dimensional shift space X with h(X) > 0 and sup h ind (X) = 0.
This paper is organized as follows. In sections 2 and 3, we introduce the basic theory of shift spaces, and the notion of topological entropy, independence entropy, and supremum independence entropy. In section 4, we show that for any one-dimensional sofic shift space, the supremum independence entropy and topological entropy coincide. In section 5, we give an example of a one-dimensional shift space X, with sup h ind (X) = h(X).

Definitions and Preliminary Results
We start with some definitions and results from symbolic dynamics and graph theory.
An alphabet A consists of a finite set of discrete symbols such as {0, 1, 2, ..., 9} or {a, b, c, ..., z}. The fundamental elements of study in symbolic dynamics are bi-infinite sequences of these letters, drawn from a given alphabet. Such a sequence is denoted by The full A-shift is the set of all bi-infinite sequences of symbols from A, written as A block (or word ) over A is a finite sequence u of symbols from A. An n-block is a block of length n, the length denoted by |u| . An empty block is the block with no symbol denoted by ε with |ε| = 0. The set of all n-blocks over A is denoted by A n . A sub-block or sub-word of u = a 1 a 2 ...a n is a block of the form a i a i+1 ...a j where 1 ≤ i ≤ j ≤ n. The empty block is a sub-block of every block. If x is a point in A Z and i ≤ j, then x [i,j] = x i x i+1 ...x j will denote the corresponding sub-block. By extension, we will use the notation x [i,∞) for the right-infinite word The shift map σ on the full shift A Z maps a point x to the point y = σ(x) such that y i = x i+1 , ∀i ∈ Z. Thus every letter is shifted one place to the left. The inverse shift map σ −1 shifts every letter to the right. We write σ n to denote the n-fold composition. A set of infinite words over A is a shift space (or sub-shift) if it is closed with respect to the natural product topology of A Z and invariant under the shift operator. A shift space X is sometimes denoted as (X, σ X ) to emphasize the role of the shift operator.
For X ⊆ A Z , let B n (X) denote the set of all n-blocks that occur in any of the sequences inside X. The language of X is the set: B(X) = ∞ n=0 B n (X) that is, all possible "allowed" blocks in all points of X. A shift space X is irreducible if for every ordered pair u, v ∈ B(X) there is a block w such that uwv ∈ B(X).
We say that a map φ : Let X be a shift space and A, A ′ two alphabets. Fix n, m ∈ Z with −m ≤ n. A block map or an (m + n + 1)−block map is a function Φ : B m+n+1 (X) → A ′ . The sliding block code induced by Φ is the map , Proposition 1.5.7). An injective sliding block code φ : X → Y is called an embedding of X into Y and we say that X embeds into Y if such a map exists. A surjective sliding block code φ : X → Y is called a factor code from X onto Y and we say that Y is a factor of X if there is a factor code from X to Y. Every bijective sliding block code φ : X → Y has a sliding block inverse ([LM95], Theorem 1.5.14). In this case we call φ a conjugacy from X to Y. Two shift spaces are conjugate if there exists a conjugacy between them.
Let X be a shift space over the alphabet A, and A [N ] X = B N (X) be the collection of all allowed N-blocks in X. We can consider A X . Let F be a set of words over A, and X F the set of points x ∈ A Z such that no word of F occurs in x. The set F is called a set of forbidden words for X. A shift of finite type is a shift space of the form X F with |F | < ∞. A shift of finite type is M-step (or has memory M) if it can be described by a collection of forbidden blocks, all of which have length M + 1.
Let G = (V, E) be a directed graph with a finite set of vertices V and a finite set of directed edges E. For an edge e ∈ E we denote by i(e) and τ (e) the starting and terminating vertices of e in G. A biinfinite path in G is a sequence (e i ) ∞ i=−∞ ⊆ E of edges such that for all integers i, τ (e i ) = i(e i+1 ). We also deal with finite paths, which are finite sequences (e i ) ℓ i=1 ⊆ E of some length ℓ such that τ (e i ) = i(e i+1 ) for i = 1, ..., ℓ − 1. Such a path is said to start at the vertex i(e 1 ) and end at the vertex τ (e ℓ ). A cycle is a finite path that starts and ends at the same vertex. A cycle (e i ) ℓ i=1 is simple if the vertices τ (e 1 ), ..., τ (e ℓ ) are distinct. For vertices v, w ∈ V, let A vw denote the number of edges in G with initial vertex v and terminal vertex w. The adjacency matrix For a graph G, the associated edge shift X G is a 1-step shift of finite type, ([LM95] Proposition 2.2.6). If X is an M-step shift of finite type, then there is a graph G such that A labeled directed graph G is a pair (G, L), where G is a directed graph with edge set E, together with a labeling function L : E → A to a finite alphabet A. We call G the underlying graph of G. For a labeled graph G = (G, L), we define the label of a path π = e 1 · · · e n to be L (π) = L (e 1 ) · · · L (e n ) , and for a bi-infinite walk ξ = · · · e −1 .e 0 e 1 · · · , A shift space X is said to be sofic if there exists some finite labeled graph G which is a presentation of X -that is, X = X G . A labeled graph is called right resolving if, for each vertex v, the edges starting at v carry different labels. Every sofic shift has a right-resolving presentation, ([LM95], Theorem 3.3.2). A minimal right-resolving presentation of a sofic shift X is a labeled graph G such that X = X G and G has the fewest vertices among all right resolving presentations of X.

Topological Entropy, Independence Entropy and Supremum independence entropy
Topological Entropy may be viewed as a measure of "information capacity" of a shift space -or of its ability to transmit messages.
Definition 3.1 (Topological Entropy). Let X be a shift space. The topological entropy of X is defined by The number of n-blocks appearing in sequences from X gives us some measure of complexity. The definition of entropy given above roughly captures the growth rate of this complexity as n increases. The limit exists (see for instance Lind and Marcus ( [LM95], Prop. 4.1.8)), so the entropy is always well-defined. Topological entropy turns out to be invariant under conjugacy, and more generally: In order to say something about the entropy of sofic shifts, we need the following proposition, which connects a presentation of a sofic shift as a labeled graph with its entropy. A non-negative matrix A is irreducible if for each ordered pair of indices I, J, there exists some n ≥ 0 such that A n IJ > 0. A graph G is irreducible if for every pair of vertices v, w ∈ V, there exists a path beginning at v and terminating at w. The largest eigenvalue of A is called the Perron eigenvalue, and denoted by λ A .  Since entropy measures exponential growth, it seems natural that sub-shifts of X with an entropy less than X can be disregarded in calculating the entropy of X as they only contribute sub-exponentially. This is the basis of the next proposition. Louidor, Marcus and Pavlov introduce ( [LMP13], and see also [PCM06]) the concept of independence entropy for symbolic dynamical systems.
For convenience, we extend the domain of Φ to include bi-infinite words.
Definition 3.8. Ifx ∈Â Z is a bi-infinite word, Φ(x) is given by Definition 3.9 (The multi-choice shift space). Let X be a shift space. We define the multi-choice shift space corresponding to X, denotedX, byX Definition 3.10 (Independence entropy). Let X be a shift space. The independence entropy denoted h ind (X), is defined by The limit exists, (see [LMP13] pages 302-303). For every m ∈ N, and a blockẑ(m) ∈ B m (X), we have Φ(ẑ) ⊆ B m (X). This yields the following theorem.   Lemma 3.15. If X, Y are two shift spaces such that X ⊆ Y, then Proof. B n X ⊆ B n Y , so the maximum of Definition 3.10 is taken over a larger set for Y .
The independence entropy is not invariant under topological conjugacy, but we can extract an invariant of conjugacy from it as follows.
Definition 3.16. Consider the supremum of independence entropy over the collection of shift spaces that are isomorphic to the given one X. We define the supremum independence entropy of X by This is much less obvious to compute, but it is some number bounded above by the topological entropy, and it is a non-trivial invariant.

Supremum independence entropy of one-dimensional sofic shift spaces
In this section we prove Theorem 1.1. Given a sofic shift X and ε > 0, we produce a topological equivalent Y with h ind (Y ) > h(X) − ε. The idea is to find a collection of words Γ = Γ K of length η = η K with the following properties.
(1) Γ captures most of entropy, in the sense that for k large (2) Two different words in Γ never overlap. Having found such Γ we define a new alphabet, is a formal set of symbols representing the words in Γ. We embed X into Y ⊆ A Z , by replacing every occurrence of a word w ∈ Γ by the sequence w * * . . . * . This configuration yields at least h(X) − 2ε in independence entropy for K large, because the substitution of any w ∈ W K gives rise to a legal word in Y .
Proof of Theorem 1.1. Let X be a sofic shift space over an alphabet A with h(X) > 0. Since h ind (Y ) ≤ h(Y ) for every topologically conjugate shift, sup h ind (X) ≤ h(X). Let ε > 0 be given. We will establish our proof by constructing a shift space Y which is topologically conjugate Let G = (G, L) be a minimal right-resolving presentation so that X = X G . By Theorem 3.6 there exists an irreducible sub-graph H of G such that h(X G ) = h(X H ), and therefore there is a minimal rightresolving presentation H = (H, L) , so that X H ⊆ X G is an irreducible sofic shift space. Suppose that H has v vertices. Let ρ be the length of the longest path between any two vertices in H. By Theorem 3.4 and Proposition 3.3, h (X G ) = h(X G ) = h(X H ) = h(X H ) = ln λ, where λ is the Perron eigenvalue of the adjacency matrix A corresponding to the graph G. By Proposition 4.2.1 in [LM95], there is an α > 0 such that |B k (X H )| > αλ k for k ≥ 1. Any labelled path in B k (X H ) has at most v presentations in B k (X H ) since H is right-resolving. Hence Since n ln(n) → ∞ as n → ∞ we can choose N 0 such that for all n > N 0 , there exists k, so that Now fix n and k that satisfy 4.2, and let M ∈ B n (X H ). Since k < n, M has n − k + 1 sub-blocks of length k. From 4.2 and 4.1, we have |B k (X H )| > α v λ k > n − k + 1, and therefore there will be a block C ∈ B k (X H ) that does not appear as a sub-block of M. Since X H is an irreducible shift space, there exists a block S with length l ≤ ρ such that MSC ∈ B (X H ) .
Let us enumerate B n−2k−2ρ (X H ) = {F j }. For every such F j fix, once and for all, a path F ′ j in H representing it in the sense that L(F ′ j ) = F j . Similarly fix presentations C ′ of C, M ′ for M and S ′ for S.
For every F j ∈ B n−2k−2ρ (X H ), let us fix paths L ′ j , R ′ j of lengths ℓ j , r j ≤ ρ respectively concatenating it with C ′ . Thus any path of the following form · · · C ′ L ′ j F ′ j R ′ j C ′ · · · , represents a legal word in B(X H ).
Note that our prior explicit choice for paths representing such words, ensures that every choice of {F i ∈ Υ ℓ,r | 1 ≤ i ≤ K} ⊆ Υ K ℓ,r gives a distinct legal word in Γ K . Yielding a bijection Hence, using 4.2, the collection Γ K of blocks w with the required form has cardinality (4.4) Consider each block w ∈ Γ K as a symbol, say w. Let W K = {w|w ∈ Γ K } be the set of symbols representing the words in Γ K . Define a new alphabet A K as the disjoint union: We will show that the map Ψ is well defined. Let w, w ′ ∈ Γ K and assume these two blocks overlap in the sense that w [q+1, . If l+k ≤ q ≤ η K −k−1 then a comparison of the two blocks immediately shows that M contains C as a sub-block and yields a contradiction. If 1 ≤ q ≤ l +k −1. Then the block D = MSC is q−periodic as is obvious from the comparison of the overlapping words below (Figure 1). Setting |D| = n + l + k = (s + 2)q + i for some integers s, i, q-periodicity implies that D [i+1,i+k] = C and this occurrence of C is contained in M which is a contradiction. Figure 1. The comparison of the two overlapping words.
As a sliding block code, the map Ψ is continuous and commutes with the shift map. By definition it is injective. As X is compact and (A K ) Z is Hausdorff, X and Y K = Ψ (X) are topologically conjugate.
Let Y K be the multi-choice shift space corresponding to Y K over the alphabet A K . Let w K ∈ B( Y K ), be given by: Since ε > 0 was arbitrary, the theorem is proved.
In our definition of sup h ind (X), a natural question that appears is whether this supremum is achieved by any sofic shift. For full shift spaces the answer is clearly positive. One of referees pointed out to us that the answer for general sofic shifts is no. Indeed, if X is irreducible sofic the independence entropy is always equal to ln(n)/k for some integers n and k ([LMP13], Theorem 2), while there are irreducible sofic shifts whose topological entropy is not of this form, for example the topological entropy for golden mean shift is equal ln 1+  Note that by [MP14] Theorem 1.1, the topological entropy of such a shift space X will be equal to that of all of its axial powers. Along the same lines if X is any sofic shift, Theorem 1.1 provides a topological conjugacy shift Y whose entropy is arbitrary close to that of its axial powers.

Supremum independence entropy of general one-dimensional shift spaces
We will use the concept of asymptotic pairs to prove Theorem 1.2.
Definition 5.1. x, y ∈ X are called an asymptotic pair if they differ on finitely many letters. We call an asymptotic pair non-trivial if they are unequal.
In [Sch95] Proposition 2.1, Klaus Schmidt showed that a shift space of finite type with positive entropy always has non-trivial asymptotic pairs. We now show that for independence entropy, the analogue of this result holds in much greater generality.
Lemma 5.2. Let X be a shift space over the alphabet A. If h ind (X) > 0, then X has non-trivial asymptotic pairs.
Proof. Suppose that h ind (X) > 0. Assume that the alphabet A has some linear order. By X we denote the multi-choice shift space of X. Let z (n) ∈ B n X be the word such that: Let R ⊂ 2 A be the collection of all subsets of A which contain more than one element. We have R ∩ B 1 ( X) = ∅, since otherwise |Φ( w)| = | w 0 |.| w 1 |...| w n−1 | = 1 for all n ≥ 0 and w ∈ B n ( X), implying h ind (X) = 0. Hence there exists z ∈ X with z 0 ∈ R. Being an allowed word z (n) appears in some z in X, say z [0,n−1] = z (n) . Let i 0 be the lowest non-negative index such that z i 0 ∈ R. Let x, y ∈ Φ ( z) ⊆ X be points obtained from z by the following construction: x i = The first element ofẑ i , for all i .
The second element ofẑ i , i = i 0 , x i , i = i 0 .
Hence x = y but there is exactly one index for x i = y i . So (x, y) is an asymptotic pair.
Corollary 5.3. A sofic shift space X with positive entropy always has non-trivial asymptotic pairs.
Theorem 5.4 ([Mey19] Section 5). There is a shift space that has positive entropy but no asymptotic pairs.
Proof of Theorem 1.2. Let X be the shift space constructed in ( [Mey19] section 5), with h(X) > 0, and no asymptotic pairs. Since the existence of asymptotic pairs is invariant, any topologically conjugate Y ⋍ X, will have no asymptotic pairs. By Lemma 5.2, h ind (Y ) = 0, for all such Y. Hence sup h ind (X) = 0.
Thus the equality h(X) = sup h ind (X), which holds for sofic shifts does not hold in general. It is interesting to attain a better understanding exactly where the line passes. Two natural test cases that where suggested to us by the referees are sub-shifts with specification property (specification property states that there exists N so that for any words v, w ∈ B(X), there exists u with length N so that vuw ∈ B(X)), and Coded sub-shifts. Concerning sub-shifts that have the specification property. It was noted by the referee that the proof of our Theorem 1.1 works almost verbatim in this case.