Abstract
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).
Blogger's Review: This paper introduces the concept of symmetry prior, merging algorithmic information theory with group theory, and opens new research directions, particularly in symmetry-induced complexity measures. The proposed Geometric Coding Theorem lays a foundation for future studies and is worthy of in-depth exploration.