Ergodic behaviors in reversible 3-state cellular automata

This paper presents a systematic classification of reversible three-state cellular automata based on discrete symmetries, distinguishing distinct classes of ergodic behavior through observables like mean return time and correlation scaling, while highlighting phenomena such as phase-space fragmentation, anomalous transport, and the existence of quasilocal charges.

The Gist

Imagine a giant, infinite checkerboard where every square can be in one of three states: Empty (a white square), Positive (a red square), or Negative (a blue square).

Now, imagine a set of strict, unchangeable rules that tell these squares how to change their colors based on their neighbors. For example, "If a red square sits next to a blue one, they swap places." Or, "If two empty squares are next to each other, they stay empty."

This is a Cellular Automaton. It's a simple computer game, but because the rules are applied to millions of squares at once, incredibly complex patterns emerge. Sometimes, the squares dance chaotically; sometimes, they form perfect, predictable waves.

This paper is a massive "field guide" to these rules. The authors took every possible set of rules for this specific 3-color game (there are over 40,000 of them!) and sorted them into four distinct "personality types" based on how the game behaves over time.

Here is the breakdown of their findings, using simple analogies:

The Three "Vibe Checks"

To figure out which personality a rule has, the authors looked at three specific things:

1. The "Return Trip" (Return Time): If you start with a random pattern of red, blue, and white squares, how long does it take for the whole board to return to that exact same pattern?
   • Analogy: Imagine shuffling a deck of cards. If you shuffle it randomly, it might take billions of years to get the original order back. If you shuffle it in a specific, rigid way, you might get the original order back in just a few seconds.
2. The "Echo" (Correlation): If you poke a square (change its color), how long does that "ripple" last before it fades away?
   • Analogy: If you drop a stone in a calm pond, the ripples spread out and eventually disappear (fade). If you drop a stone in a muddy swamp, the ripples might get stuck or move very slowly.
3. The "Secret Handshakes" (Conserved Charges): Are there hidden rules that never change? For example, maybe the total number of red squares minus blue squares always stays the same, no matter how they move.
   • Analogy: In a crowded room, if everyone is dancing, the total number of people in the room stays the same. That's a "conserved charge." Some rules have many of these hidden constraints; others have none.

---

The Four Classes of Behavior

The authors sorted the 40,000+ rules into four groups, ranging from "Total Chaos" to "Perfect Order."

Class I: The Chaotic Party

• The Vibe: Pure chaos.
• What happens: If you start with a random pattern, it takes an astronomically long time (exponentially long) for the pattern to repeat. Any ripple you create dies out very quickly.
• The Secret: There are no "secret handshakes." The system forgets its past almost instantly.
• Analogy: This is like a mosh pit. Everyone is bumping into everyone else. If you drop a ball in the middle, it gets kicked around and disappears instantly. The system is "ergodic," meaning it explores every possible state it can, but it does so in a wild, unpredictable way.

Class II: The Anomalous Flow

• The Vibe: Organized chaos with a twist.
• What happens: Like Class I, it takes a long time to repeat the pattern. But here's the kicker: the ripples (echoes) don't die out quickly. They fade away slowly, like a heavy fog lifting.
• The Secret: These systems have "quasi-local" charges. Imagine a rule where the total number of red squares is conserved, but they can't just move freely; they have to push each other in a specific way.
• The Surprise: The authors found some rules where the ripples move slower than normal diffusion (subdiffusive) and some where they move faster than normal (superdiffusive).
  • Subdiffusive: Imagine trying to walk through a crowded hallway where people keep stopping to tie their shoes. You move, but very slowly.
  • Superdiffusive: Imagine a wave of people running down a hallway; the energy moves faster than the people themselves.

Class III: The Frozen Islands

• The Vibe: Stuck in place.
• What happens: The ripples don't fade away at all. They get stuck at a certain level.
• The Secret: The system is broken into "islands." Imagine the checkerboard is split into separate rooms by invisible walls. The squares inside one room can dance, but they can never interact with the squares in the next room.
• Analogy: It's like a party where the music stops, and everyone freezes in place, but they can still wiggle their fingers. The "echo" of your poke never leaves the room you're in.

Class IV: The Perfectly Predictable Machines

• The Vibe: Boring but beautiful.
• What happens: The pattern repeats very quickly (in a time that grows slowly with the size of the board). The ripples don't fade; they stay constant.
• The Secret: These are the "integrable" systems. They have so many "secret handshakes" (conserved charges) that the movement is completely predictable.
• Analogy: This is like a train on a track. The cars (squares) move at a constant speed, never crashing, never changing speed. If you know where they start, you know exactly where they will be forever.
• Special Note: Some of these rules are "free" (particles pass through each other like ghosts), while others are "hardcore" (they bounce off each other like billiard balls).

Why Does This Matter?

You might ask, "Why study a simple color-changing game?"

1. It's a Laboratory for Physics: Real-world physics (like how heat moves through a metal or how electricity flows) is incredibly hard to calculate because there are too many particles. These simple automata act as a "toy model." They are simple enough to simulate on a computer but complex enough to show the same weird behaviors (like slow diffusion or chaotic mixing) as real atoms.
2. New Physics Discovered: The authors found behaviors that physicists hadn't seen before in simple models, like specific types of "slow motion" (subdiffusion) that happen in a very specific way.
3. The Bridge Between Order and Chaos: This paper helps us understand the gray area between a perfectly predictable machine and total randomness. It shows us that there isn't just "chaos" and "order," but a whole spectrum of weird, in-between behaviors.

The Bottom Line

The authors took a massive library of 40,000 simple rules and organized them into a "periodic table" of dynamics. They showed that even in the simplest, most rigid digital worlds, nature can produce everything from total chaos to perfect order, and many strange, slow-moving, and fast-moving states in between. It's a map of how complexity emerges from simplicity.

Technical Summary

1. Problem Statement

The paper addresses the challenge of classifying the emergent dynamical behaviors in classical, time-reversible many-body systems. While equilibrium statistical mechanics and integrable systems are well-understood, the landscape of real-time dynamics for interacting systems with discrete degrees of freedom remains poorly classified. Specifically, the authors aim to:

• Identify distinct classes of ergodic behavior in reversible cellular automata (RCA).
• Move beyond binary (2-state) models, which often yield trivial or limited dynamics, to explore 3-state models (vacuum $\emptyset$, particle $+$, antiparticle $-$).
• Establish a systematic framework to distinguish between chaotic, integrable, super-integrable, and fragmented phases using empirical observables suitable for discrete state spaces where traditional Lyapunov exponents are difficult to define.

2. Methodology

Model Definition

• System: One-dimensional periodic lattice of even length $L$.
• States: Each site $s_i \in \{+, -, \emptyset\}$. The state $\emptyset$ acts as a stable vacuum ($U(\emptyset, \emptyset) = (\emptyset, \emptyset)$).
• Dynamics: "Brickwork" (block) updates. The system evolves in discrete time steps using a local reversible map $U: X^2 \to X^2$ applied to pairs of sites.
  • Odd steps: Update pairs $(1,2), (3,4), \dots$
  • Even steps: Update pairs $(2,3), (4,5), \dots$
• Rule Space: There are $8! = 40,320$ possible reversible local rules. The authors restrict their study to rules respecting specific discrete symmetries: Charge Conjugation ($C$), Parity ($P$), and Time Reversal ($T$). This reduces the search space to a few hundred distinct symmetric rules.

Classification Indicators

To categorize the ergodic behavior, the authors utilize three primary empirical observables:

1. Mean Return Time ($T$): The average time for a random initial configuration to return to itself.
   • Scaling: Exponential ($T \sim e^{\kappa L}$) indicates chaotic/fragmented behavior; Power-law ($T \sim L^p$) indicates integrable or "free" dynamics.
2. Conserved Charges ($N_Q$): The number of extensive, translationally invariant local (or quasilocal) conserved quantities as a function of their support size $r$.
   • Scaling: Constant, linear, or exponential growth distinguishes between non-integrable, integrable, and super-integrable models.
3. Correlation Functions: The decay of two-point correlators for local observables (charge density and particle density).
   • Decay: Exponential ($e^{-\alpha t}$) implies chaos; Algebraic ($t^{-1/z}$) implies transport (diffusive, ballistic, anomalous); Constant implies fragmentation or domain walls.
   • Exponents: The dynamical exponent $z$ characterizes transport (e.g., $z=2$ for diffusion, $z=1$ for ballistic, $z=3/2$ for KPZ-like superdiffusion).

Numerical Tools

• Transfer Matrix: A truncated transfer matrix $T^{(r)}$ is constructed to find eigenvalues. Eigenvalues $\lambda=1$ correspond to conserved charges. Eigenvalues close to 1 with gaps closing exponentially as $r \to \infty$ indicate quasilocal charges.
• Ruelle-Pollicott (RP) Resonances: In chaotic systems, the leading non-trivial eigenvalue of the transfer matrix converges to a value $\lambda^* < 1$, defining the decay rate of correlations.

3. Key Contributions

A. A Four-Class Ergodic Hierarchy

The authors propose a classification of RCA models into four distinct classes based on the interplay of return time scaling, charge scaling, and correlation decay:

• Class I (Chaotic/Mixing):

  • Return Time: Exponential ($e^{\kappa L}$).
  • Charges: Zero local conserved quantities.
  • Correlations: Exponential decay.
  • Feature: Exhibits Ruelle-Pollicott resonances; the most "generic" chaotic behavior.

• Class II (Integrable/Anomalous Transport):

  • Return Time: Exponential ($e^{\kappa L}$).
  • Charges: Non-zero. Subclasses defined by charge scaling:
    • IIa: Constant number of charges (Chaotic but constrained).
    • IIb: Linear growth of charges (Integrable).
    • IIc: Exponential growth of charges (Super-integrable).
  • Correlations: Algebraic decay ($t^{-1/z}$).
  • Feature: Exhibits quasilocal charges even in the absence of strict local charges. Transport is often anomalous (subdiffusive $z=3$ or superdiffusive $z=3/2$).

• Class III (Fragmented/Domain Walls):

  • Return Time: Exponential ($e^{\kappa L}$).
  • Charges: Constant or Exponential growth.
  • Correlations: Decay to a non-zero constant (plateau).
  • Feature: Dynamics are confined to finite regions separated by domain walls that are preserved under evolution. The system does not mix globally.

• Class IV (Integrable/Free/Polynomial Return):

  • Return Time: Power-law ($L^p$ with $p \le 4$).
  • Charges: Exponential growth (Super-integrable) or zero (Trivial/Free).
  • Correlations: Decay to a constant (or slow power-law).
  • Feature: Includes "free" models (non-interacting quasiparticles) and models satisfying the set-theoretic Yang-Baxter equation.

B. Discovery of New Phenomena

• Quasilocal Charges in Chaotic Systems: The authors demonstrate that models can possess quasilocal charges (exponentially decaying density) that govern transport and correlation decay, even when no strictly local charges exist. This challenges the binary view of integrability vs. chaos.
• Anomalous Transport Exponents:
  • Identification of subdiffusive transport with dynamical exponent $z=3$ (decay $\sim t^{-1/3}$), a phenomenon not previously observed in many-body systems.
  • Observation of superdiffusive transport with $z=3/2$ but with a scaling function distinct from the standard KPZ (Prähöfer-Spohn) profile, suggesting a new universality class.
• Ruelle-Pollicott Resonances in Discrete Systems: The paper provides the first clear observation of RP resonances in discrete state-space dynamical systems, defining them via the spectral gap of the transfer matrix.

4. Results

• Systematic Survey: The study analyzed hundreds of symmetric rules out of the 40,320 possible 3-state reversible rules.
• Transport Diversity: A wide variety of transport behaviors were found, including:
  • Normal diffusion ($z=2$).
  • Ballistic transport ($z=1$).
  • KPZ-like superdiffusion ($z=3/2$).
  • Novel subdiffusion ($z=3$ and $z=4$).
• Integrability Beyond Yang-Baxter: Several models in Class II and IV exhibit super-integrable behavior (exponentially many charges) but do not satisfy the set-theoretic Yang-Baxter equation, suggesting new algebraic structures underlying integrability.
• Fragmentation: Class III models exhibit "Hilbert space fragmentation" (in the classical sense), where the phase space splits into disconnected sectors due to conserved domain walls, preventing thermalization.

5. Significance

• Bridging Classical and Quantum: Reversible cellular automata serve as a classical analogue to quantum unitary dynamics. This classification provides a "toy model" framework to understand complex quantum phenomena (like many-body localization, integrability, and hydrodynamics) in a computationally tractable setting.
• Refining Ergodic Theory: The work moves beyond the simple dichotomy of "integrable vs. chaotic." It introduces a nuanced hierarchy involving quasilocal charges, dynamical symmetries, and fragmentation, offering a more complete picture of non-equilibrium statistical mechanics.
• New Universality Classes: The discovery of subdiffusive transport with $z=3$ and non-KPZ superdiffusive scaling suggests the existence of new universality classes in non-equilibrium statistical physics that require further theoretical investigation.
• Methodological Framework: The combination of return time analysis, transfer matrix spectra, and correlation decay provides a robust, numerical toolkit for classifying discrete dynamical systems where traditional chaos indicators (like Lyapunov exponents) are ill-defined.

In conclusion, this paper establishes a comprehensive taxonomy for reversible 3-state cellular automata, revealing a rich landscape of dynamical behaviors that includes novel forms of integrability, anomalous transport, and ergodicity breaking, thereby offering deep insights into the emergence of complex phenomena from simple local rules.