Exact Lyapunov spectra of affine cellular automata and the parity rule on networks
Listen
Radio episode about this paper
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.
BionamiX, Department of Data Analysis and Mathematical Modelling, Ghent University · São Carlos Institute of Physics, University of São Paulo
nlin.CG, nlin.CD
Submitted: 2026-06-12
Updated: 2026-11-10
Comments: 10 pages, 6 figures, 4 tables. Revised version, submitted to Chaos, Solitons & Fractals. Code: https://github.com/mrollier/exact-lyapunov-spectra"
License: http://creativecommons.org/licenses/by-sa/4.0/
Importance score: 83/100
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…
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
Summary
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
. 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
. 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
.
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
. This connects network dynamics to structural properties such as the spectral radius and the eigenvector centralities
Furthermore, the long-time amplitude of a single-site perturbation then scales with the eigenvector centrality of the seeded node
.
Mathematical Formulation
The Lyapunov spectrum is defined by tracking the growth rates along every orthogonal direction in tangent space, where the Lyapunov spectrum collects their growth rates, Λk = lim sup t→∞ 1/t ln(sigmak), k = 1, …, N
. For affine rules, this simplifies to Λk = ln(sigmak(J)), k = 1,…, N
. This means the spectrum is a fixed property of one matrix: no trajectory is simulated, no cut-off is chosen, and the numerical instability of the Jacobian product never arises
.
Implications for Numerical Methods
The exact results serve as benchmarks because they reveal numerical artefacts in previously reported spectra and turn the informal correspondence between spectral radius and dynamical sensitivity into an exact identity
. Specifically, when comparing different computation methods, direct multiplication plateaus as the slower-growing directions are lost to floating-point error, whereas Benettin recovers the exact spectrum
. This comparison shows that for affine rules, the exact answer is known
.
Generalization and Bridging Cases
The construction extends to higher dimensions where the constant Jacobian becomes a D-level circulant matrix
diagonalized by the D-dimensional DFT. For affine outer-totalistic rules, the singular values are given by sigmak,l = a◦ + g (k, l)
. This allows for the analytical study of the Lyapunov spectra of parity rules on arbitrary graphs
. The parity rule's true defect propagation is described as walk-counting modulo two, which places it within algebraic graph theory and contrasts with the unbounded tangent-space growth
.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Exact Lyapunov spectrum calculation for affine cellular automata allows AI systems to precisely benchmark numerical Lyapunov routines, identifying
numerical artefacts in previously reported spectra.
-
For affine cellular automata on periodic lattices, the exact Lyapunov spectrum is a
discrete Fourier transform of the rule’s gradient stencil,
enabling analytical prediction of dynamical sensitivity without simulation or limits. -
For parity rules on arbitrary graphs, the Lyapunov spectrum is
the logarithm of the absolute adjacency spectrum,
and perturbation amplitudes can be determined by calculating eigenvector centrality to find which nodes are most influential in a perturbation. -
AI systems can use the exact spectral radius of the adjacency matrix plus a constant term to determine the maximal exponent, which represents
the logarithm of the spectral radius.
-
The paper provides an exact description of configuration space difference patterns for parity rules, allowing AI to model how defects propagate as
walk-counting modulo two,
contrasting this with unbounded tangent-space growth.
Abstract
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.