Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes a geometric analogue of the classical Coding Theorem within the context of symmetry groups, focusing on computable bijections of binary strings. It introduces the concept of the symmetry prior, which quantifies the likelihood of a symmetry having a specific string as its unique fixed point, and demonstrates that for fix-retractable symmetry groups, this prior acts as a universal lower semi-computable semi-measure. The findings unify aspects of algorithmic information theory and group theory, offering a new framework for analyzing complexity measures influenced by symmetry.
The symmetry prior reveals a universal measure of complexity that bridges algorithmic information theory and group theory in groundbreaking ways.
This paper establishes a direct analogue of the classical Coding Theorem in the setting of symmetry groups. We consider computable bijections on the set of binary strings, called symmetries and define the symmetry prior of a string as the probability that a randomly chosen symmetry from a given group has the string as its unique fixed point. We show that for any fix-retractable symmetry group, a group admitting a computable section that selects an isolating symmetry for every string, the symmetry prior is a universal lower semi-computable semi-measure. In this case, the Geometric Coding Theorem holds. We also develop a Galois connection between subgroups of G and subsets of binary strings, characterizing closed points and maximal closed subgroups, and explore the join-semilattice of dense subgroups. Our results unify algorithmic information theory with group theory and provide a framework for studying symmetry-induced complexity measures. This paper is the first in a series on Computational Algorithmic Statistics (CAS).