Exact Lyapunov spectra of affine cellular automata and the parity rule on networks
summary
The gist
The Lyapunov exponent quantifies the sensitivity of a dynamical system to perturbations, and the full Lyapunov spectrum extends this to every orthogonal direction in tangent space The affine rules…
In short
The paper proves that affine cellular automata have an exact Lyapunov spectrum because their update rules result in a constant Jacobian matrix regardless of configuration. This allows the spectrum to be found simply by calculating the logarithms of the singular values of this single matrix, eliminating the need for trajectory simulation or limit calculations.
Key concepts
- Lyapunov Exponent
- This measures how sensitive a system's evolution is to tiny changes in its starting state. The full Lyapunov spectrum extends this sensitivity analysis across every possible direction in the system's tangent space.
- Affine Rules
- These are cellular automaton rules where the update at any cell is a XOR of a subset of its neighbors plus a constant value. A key property is that these rules have a configuration-independent Boolean Jacobian, meaning the Jacobian matrix remains the same for every possible arrangement of cells.
- Constant Jacobian
- For affine cellular automata on periodic lattices, the constant Jacobian simplifies calculations immensely. It becomes a multilevel circulant matrix, which means its properties can be found using the discrete Fourier transform of the rule's gradient stencil.
Terminology used across episodes
This episode discusses
The paper
Exact Lyapunov spectra of affine cellular automata and the parity rule on networks · Read on arXiv
BionamiX, Department of Data Analysis and Mathematical Modelling, Ghent University · São Carlos Institute of Physics, University of São Paulo
The Lyapunov exponent quantifies the sensitivity of a dynamical system to perturbations, and the full Lyapunov spectrum extends this to every orthogonal direction in tangent space. For cellular automata the spectrum is almost always approximated numerically, and the approximation is delicate. We show that the affine rules, those whose update is an XOR of a subset of the inputs together with a constant, admit an exact Lyapunov spectrum. An affine rule has a configuration-independent Boolean Jacobian, so the spectrum reduces to the logarithms of the eigenvalue moduli of a single constant matrix, with no simulation and no limit involved. Two cases are shown to carry a closed form. For an affine cellular automaton on a periodic lattice the Jacobian is a multilevel circulant matrix, and its eigenvalues are given by the discrete Fourier transform of the rule's gradient stencil, valid in any spatial dimension. For the parity rule on an arbitrary graph the Jacobian is the adjacency matrix, plus the identity in the self-inclusive case, so the spectrum is the logarithm of the absolute spectrum of that matrix, and the maximal exponent the logarithm of its spectral radius. In both cases the exact spectra serve as benchmarks: they expose errors in previously reported spectra, and turn the informal correspondence between spectral radius and tangent-space sensitivity into an exact identity.
Transcript
Introduction to the show: ident: Nonlinear Sciences. The day in nonlinear science: chaos, patterns, networks and adaptation.
Kai: We're looking at the paper: "Exact Lyapunov spectra of affine cellular automata and the parity rule on networks".
Mira: Here's the gist of the paper. The Lyapunov exponent quantifies the sensitivity of a dynamical system to perturbations, and the full Lyapunov spectrum extends this to every orthogonal direction in tangent space The affine rules, those whose update is a XOR of a subset of the inputs together with a constant, admit an exact Lyapunov spectrum This implies that one does not need to calculate a trajectory nor take a limit, because the product of Jacobians collapses to a matrix power, and the Lyapunov spectrum is exactly the set of logarithms of the singular values of that one matrix Exact Spectrum for Affine Rules The paper demonstrates that affine rules possess a configuration-independent Boolean Jacobian, which means "the Jacobian does not depend on the configuration, but is simply a single constant matrix".
Kai: This property simplifies the calculation significantly because "the product of Jacobians collapses to a matrix power, and the Lyapunov spectrum is exactly the set of logarithms of the singular values of that one matrix".
Mira: For an affine cellular automaton on a periodic lattice, this constant Jacobian is a multilevel circulant matrix, leading to a closed-form spectrum that is "the discrete Fourier transform of the rule’s gradient stencil, valid in any spatial dimension".
Kai: Spectrum for Network Automata For the parity rule on an arbitrary graph, the constant Jacobian is the adjacency matrix itself, meaning "the Lyapunov spectrum is the logarithm of the absolute adjacency spectrum, and the maximal exponent is the logarithm of the spectral radius".
Paper summary: Kai: So we're looking at this paper titled "Exact Lyapunov spectra of affine cellular automata and the parity rule on networks." The core idea is that for affine rules—those that are a XOR of inputs plus a constant—we can calculate the exact Lyapunov spectrum without any trajectory simulations or limits.
Mira: They prove this by showing that these rules have a configuration-independent Boolean Jacobian. Because this Jacobian is constant, the full Lyapunov spectrum simplifies down to just the logarithms of the singular values of one single matrix.
Lev: So they're bypassing the typical numerical approximations used in cellular automata, which are usually delicate and sensitive to errors. This suggests a much more robust way to analyze these systems on real hardware or large simulations.
Kai: They handle two main cases: first, affine rules on CAs with periodic lattices, where the Jacobian is a multilevel circulant matrix whose singular values are the discrete Fourier transform of the rule's gradient stencil.
Mira: Then they move to networks on arbitrary graphs, focusing on the parity rule as the most general case. For that parity rule, their constant Jacobian is just the adjacency matrix itself.
Lev: That shift from a spatial structure like a lattice to a graph structure is significant because it means you can study these dynamics using established concepts from algebraic graph theory, specifically eigenvector centralities.
Kai: The main takeaway for me is that this exact formulation gives us concrete relationships between the dynamic sensitivity and the underlying geometry of the system, whether that's a periodic grid or a complex network structure.
Conclusion: Kai: So, looking at "Exact Lyapunov spectra of affine cellular automata and the parity rule on networks," the authors have really nailed down a way to get exact growth rates for these specific types of rules using matrix algebra instead of time-stepping.
Mira: What this means in simpler terms is that for these affine systems, you don't need to wait forever or worry about rounding errors accumulating over long simulations. The sensitivity—how fast things diverge—is fixed by the structure of the rule itself.
Lev: From an engineering standpoint, if you’re designing a system based on a parity rule on a network, this paper tells you exactly how to calculate those growth rates using the adjacency matrix properties rather than having to run massive simulations just to guess where things are unstable.
Kai: The authors also showed that their method is exact for these affine rules, which means it’s not just an approximation that gets better with more computation time; it’s the right answer every single time for those systems.
Mira: And they highlight how this work connects to structural properties of graphs, like eigenvector centrality. It shows that the dynamical sensitivity is intrinsically tied to how connected and influential a node is in the network structure itself.
Lev: I think for future work, you might want to look at extending this idea beyond simple XOR rules or looking at what happens when the neighborhood structure isn't perfectly uniform across a lattice. That’s where things might get interesting again.
More episodes
- 2608.20276-Flip rate prediction in the double pendulum
- The day in conversation for 2026-11-18
- Daily Summary for 2026-11-18
- 2603.16051-Gradual emergence of temporal structures depending on the distance between neighboring callers in natural habitat of male treefrogs
- 2603.21801-Diffraction of deep-water solitons
- The day in conversation for 2026-11-17
- Daily Summary for 2026-11-17
- 2204.04335-Measuring and improving community resilience: a Fuzzy Logic approach
- 2604.11624-Prediction of chaotic dynamics from data: An introduction
- 2610.21575-Cooperation Dynamics with Environmental Feedback: Steady States and Transitions