The Emergence Theorem: A Universality Result for Binary Branching in Symbolic Dynamics (Version 2)

The Emergence Theorem A Universality Result for Binary Branching in Symbolic Dynamics Michael D. Jensen Independent Researcher Abstract We prove that the presence of a single revisitable binary branching in a strongly connected finite-state dynamical system forces symbolic complexity, including exponential word growth. Specifically, such a system admits a subsystem topologically conjugate to the full twoshift, has positive topological entropy, and supports distinct ergodic measures with incompatible statistics. Moreover, this binary structure recurs self-similarly across scales. Our result elevates classical constructions such as Smale’s horseshoe to a general universality theorem: minimal binary branching suffices for positive entropy and emergent complexity in symbolic dynamics. MSC (2020): 37B10 (primary); 37B40, 37A05, 37D45 (secondary). Keywords: symbolic dynamics; edge shifts; topological entropy; ergodic measures; binary branching; universality; emergence. 1 Introduction Complexity in dynamical systems often arises from simple local branching. Classical constructions such as Smale’s horseshoe show that a binary splitting generates symbolic subsystems with positive entropy. Our goal in this work is to elevate this phenomenon from example to theorem. In the study of complex systems, a central question is how large-scale behavior emerges from simpler components across physics and biology. Anderson emphasized that more is different, highlighting that effective laws at higher levels need not reduce to micro-descriptions [5]. Related perspectives by Laughlin stress the universality of emergent principles [6], while Tegmark frames emergence in terms of hierarchies of effective theories [7]. The theorem below provides a precise symbolic-dynamical formulation of this intuition. 1 We prove that the existence of a single revisitable binary branching in a strongly connected finite-state system forces emergent complexity. In particular, such a system admits a subsystem conjugate to the full two-shift, has positive topological entropy, and supports multiple ergodic regimes. Moreover, this binary structure recurs self-similarly across scales. Thus what has usually been presented as a special case becomes a general law: minimal binary branching suffices for positive entropy and exponential complexity in symbolic dynamics. Related Work Our result builds on several classical constructions in dynamics. The existence of symbolic subsystems conjugate to the full shift goes back to Smale’s horseshoe map [1], and entropy lower bounds from binary branching appear throughout symbolic dynamics (see Lind–Marcus [2], Kitchens [3]). The use of return maps to generate symbolic dynamics is standard in ergodic theory (see Walters [4]). What is new here is the unification: the mere presence of a binary branching in a strongly connected finite-state system forces exponential complexity, a subsystem conjugate to the full two-shift, recurrence across scales, and multiple ergodic measures. This elevates what is usually an example into a general structural theorem. 2 Model and Definitions Let G= (V, E) be a finite directed graph and let S⊆Vbe a strongly connected component (SCC). Definition 1 (Edge shift).The edge shift Xof Sis the space of one-sided infinite sequences of edges (e0e1e2···) with compatible head/tail inside S, equipped with the product (cylinder) topology. The shift σ:X→Xis given by σ(e0e1e2···) = e1e2···. We work with one-sided shifts; all statements have standard two-sided analogues, and topological entropy coincides for oneand two-sided edge shifts. Definition 2 (Return blocks at b).Fix b∈S. A return block at bis a nonempty finite path in Sthat starts at b, ends at b, and does not visit b internally. This restriction guarantees that concatenation of return blocks is unique and unambiguous. Definition 3 (First-return map).Let C⊂Xbe the cylinder set of sequences whose initial edge leaves b. Let Z:= {x∈C:xreturns to Cinfinitely often}. 2 For x∈Z, let τ(x) be the first return time to Cafter time 0. The firstreturn map T:Z→Zis defined by T(x)=στ(x)x. If x∈Zreturns to C infinitely often, then so does στ(x)x; hence T(Z)⊂Z. Notations and Conventions Throughout the paper we adopt the following: •Shifts. All shifts are one-sided unless otherwise stated. •Cylinders. For an admissible word w= (a0, . . . , ak−1), the cylinder [w]={x∈X:x0=a0, . . . , xk−1=ak−1}is clopen in the product topology; continuity checks use cylinders. •Return blocks. Return blocks at bare indexed from the initial edge out of bto the next visit to b(inclusive). Concatenation is unambiguous. •First-return map. τ(x) is the least n > 0 with xnstarting at b; thus Tadvances by one full return block. •Entropy. htop(X, σ) = limn→∞ 1 nlog N(n), where N(n) is the number of admissible words of length n(the limit exists by subadditivity for subshifts). 3 Binary Branching and Growth Lemma 4 (Existence of two closed b→bwalks).If b∈Shas two distinct outgoing edges e0, e1whose heads lie in S, then there exist return blocks C0, C1beginning with e0, e1respectively. Proof. By strong connectivity, each head uiof eiadmits a path Pi:ui→b contained in S. Then Ci:= eiPiis a b→breturn block, and C0, C1have distinct first edges. Lemma 5 (Labyrinth Bound).There exist integers L0, ℓ ≥1such that for each m≥1there are at least 2mdistinct admissible words of length exactly L0+mℓ. Consequently, htop(X, σ)≥log 2 ℓ. 3 Proof. By Lemma 4 there are two distinct b→breturn blocks C0, C1with lengths ℓ0, ℓ1and different first edges. Let ℓ:= lcm(ℓ0, ℓ1) and set D0:= Cℓ/ℓ0 0, D1:= Cℓ/ℓ1 1. Each Diis a b→bwalk of length ℓ, and their first edges remain distinct. Fix s∈Sand a path Q:s→band put L0:= |Q|. For any bitstring x= (x1, . . . , xm)∈ {0,1}m, define W(x) := Q Dx1Dx2···Dxm, which has length L0+mℓ. If x=yand jis the first index with xj=yj, then the first edge of Dxjdiffers from that of Dyj, so W(x)=W(y). Hence there are at least 2mdistinct words of length L0+mℓ, and the stated entropy bound follows from the definition of htop. 4 A Binary Subsystem via Return Maps Lemma 6 (Binary Horseshoe).Let C⊂Xbe the cylinder set of sequences whose initial edge leaves b. Let Z:= {x∈C:xreturns to Cinfinitely often}, and let τ(x)be the first return time to Cafter time 0. Define the first-return map T:Z→Zby T(x) = στ(x)x. Let Z∗⊂Zconsist of those xwhose successive return blocks are only C0and C1. Then (Z∗, T)is topologically conjugate to the full two-shift ({0,1}N, σ). Proof. Well-definedness and continuity of T.Each level set {τ=m}is a finite union of cylinders inside C, hence clopen. Therefore the induced map Tis continuous on Z. Note that Zneed not be σ-invariant; what matters for our arguments is that Z(and in particular Z∗) is invariant under T. Z∗is nonempty, closed, and T-invariant. C0C0C0··· ∈ Z∗, so Z∗is nonempty. Z∗is obtained by forbidding all return-words other than C0and C1; hence it is closed in Z. As a subset of X,Z∗is a closed sofic subshift. If all return blocks of xlie in {C0, C1}, then the same holds after removing the first block; thus T(Z∗)⊂Z∗. Coding and inverse. Define Ψ : Z∗→ {0,1}Nby coding the n-th return block as 0 if C0and 1 if C1. Define Φ : {0,1}N→Z∗by concatenation. Parsing at bis unique, so Ψ,Φ are mutual inverses. Continuity and shift-commutation. Ψ and Φ are continuous, and Ψ◦T=σ◦Ψ. Note. The set Z∗need not be σ-invariant (a one-edge shift typically lies inside a return block); Z∗is closed and T-invariant, which suffices for the conjugacy. 4 Corollary 7 (Self-Similarity Across Scales).For each k≥1, grouping k successive return blocks yields a subsystem conjugate to the full shift on {0,1}k. Projecting each macro-symbol to its first bit recovers the full twoshift as a factor. Thus the binary branching recurs self-similarly at every scale. 5 Emergence and Complexity Lemma 8 (Divergent Ergodic Regimes).Let νpbe the Bernoulli(p) measure on ({0,1}N, σ)and let ˜µpbe its pushforward under the conjugacy Ψ : (Z∗, T)→({0,1}N, σ). Then the Kakutani tower construction µp(A) := 1 RZτ d˜µp ∞ X k=0 ˜µp {x∈Z:k < τ(x), σkx∈A} defines a σ-invariant ergodic probability measure on X. If p0=p1then µp0=µp1. Hence (X, σ)supports distinct ergodic measures with incompatible long-run statistics. Proof. The return-time τis integrable on Zunder ˜µp, since Zis a positiverecurrence cylinder set in a sofic subshift. The displayed formula is the standard suspension (Kac/Abramov) lift of a T-invariant probability to a σinvariant one (see Walters [4]). Ergodicity lifts, and distinct pyield distinct block frequencies, so µp0=µp1. 6 Main Theorem Theorem 9 (Emergence Theorem).Let Gbe a finite directed graph and S a strongly connected component. If b∈Shas two distinct outgoing edges whose heads remain in S, then this single local branching suffices to force global complexity: 1. Binary subsystem: The first-return map Tadmits a closed invariant subsystem topologically conjugate to the full two-shift. 2. Exponential complexity: The edge shift (X, σ)has positive topological entropy, with htop(X, σ)≥log 2 ℓ. 3. Self-similarity: The binary branching recurs at all block scales. 5 4. Multiple ergodic regimes: The system supports distinct ergodic measures with incompatible statistics. Consequently, a single revisitable binary branching forces emergent complexity and a self-similar re-emergence of opposition. Remark 10 (Novelty and Scope).The condition of a revisitable binary branching is both necessary and sufficient for positive entropy in a strongly connected shift of finite type: if no such branching exists, then the shift is ultimately periodic. Classical results (e.g. Smale’s horseshoe) showed sufficiency via geometric constructions. What is new here is the unification: a single local graph feature simultaneously guarantees a symbolic horseshoe, exponential word growth, positive entropy, self-similar recursion at all block scales, and a continuum of Bernoulli-type ergodic measures. To our knowledge, these consequences have not previously been unified under a single minimal local hypothesis. Appendix: A Worked Example We exhibit a 3-vertex graph in which all statements of the theorem can be verified by hand. A. The graph and its edge shift Let V={b, u, v}and E={b→u, b →v, u →b, v →b}. This graph is strongly connected. b u v e0e1 Figure 1: A minimal SCC with a binary branching at b. Let Xbe the one-sided edge shift over these edges, with shift σ. B. Return blocks and the Labyrinth Bound At bwe have e0:b→uand e1:b→v. Concatenate with returns u→b and v→bto get C0:= (b→u)(u→b), C1:= (b→v)(v→b). 6 Each of length 2, hence ℓ= 2 and L0= 0. For m≥1, W(x) = Cx1···Cxm has length 2m; distinct xgive distinct walks, so N(n)≥2⌊n/2⌋⇒htop(X, σ)≥1 2log 2. C. Exact entropy via Perron–Frobenius The vertex-adjacency matrix in order (b, u, v) is A=  011 100 100  , whose eigenvalues are {√2,−√2,0}, so ρ(A) = √2 and htop(X, σ) = log ρ(A) = 1 2log 2, matching the bound. Thus the Labyrinth lower bound is sharp in this example. D. Binary horseshoe and self-similarity As in Lemma 6, (Z∗, T)∼ =({0,1}N, σ) by return-block coding; higher-block and projection yield self-similarity at all scales (Cor. 7). E. Multiple ergodic regimes Pushing forward Bernoulli(p) measures under the conjugacy yields distinct ergodic measures ˜µpon X(Lemma 8). Remark 11 (Aperiodicity (not needed here)).If one prefers a direct Markovchain construction on edges, aperiodicity can be enforced by a small detour along a primitive cycle inside S. The Bernoulli pushforward in Lemma 8is simpler. References [1] S. Smale. Differentiable dynamical systems. Bull. Amer. Math. Soc., 73(6):747–817, 1967. [2] D. Lind and B. Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995. [3] B. Kitchens. Symbolic Dynamics: One-Sided, Two-Sided and Countable State Markov Shifts. Springer, 1998. 7 [4] P. Walters. An Introduction to Ergodic Theory. Springer, 1982. [5] P. W. Anderson. More is Different. Science, 177(4047):393–396, 1972. [6] R. B. Laughlin. A Different Universe: Reinventing Physics from the Bottom Down. Basic Books, 2005. [7] M. Tegmark. Our Mathematical Universe. Knopf, 2014. 8