Conservation Laws and Invariant Measures in Surjective Cellular Automata

Abstract

We discuss a close link between two seemingly different topics studied in the cellular automata literature: additive conservation laws and invariant probability measures. We provide an elementary proof of a simple correspondence between invariant full-support Bernoulli measures and interaction-free conserved quantities in the case of one-dimensional surjective cellular automata. We also discuss a generalization of this fact to Markov measures and higher-range conservation laws in arbitrary dimension. As a corollary, we show that the uniform Bernoulli measure is the only shift-invariant, full-support Markov measure that is invariant under a strongly transitive cellular automaton.

Keywords

• surjective cellular automata
• conservation laws
• invariant measures
• statistical equilibrium
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-ds] mathematics [math]/dynamical systems [math.ds]
• [nlin.nlin-cg] nonlinear sciences [physics]/cellular automata and lattice gases [nlin.cg]
• [math.math-co] mathematics [math]/combinatorics [math.co]