From Program Length to Symmetry: CAS I Recasts the Coding Theorem in Geometric Terms

Introduction

Classical algorithmic information theory asks how hard an object is to describe. A binary string that can be generated by a short program is usually treated as simple; one that requires a long specification is considered more complex. The arXiv paper “CAS I: A Geometric Coding Theorem” reframes that question. Instead of starting from program length, it asks how a string behaves inside a space of computable symmetries.

The paper is presented as the first entry in a series on Computational Algorithmic Statistics. Its central move is to treat computable bijections on the set of binary strings as symmetries. In this view, strings are not merely outputs of programs; they are points in a structured universe acted on by a group of transformations.

Key ideas

• Symmetries as computable bijections: The paper defines symmetries as computable one-to-one transformations of binary strings. This lets the author import group-theoretic language into a setting normally dominated by programs, machines, and semimeasures.

• A symmetry prior: For a given group, the symmetry prior of a string is the probability that a randomly chosen symmetry has that string as its unique fixed point. Intuitively, the prior measures how naturally a string can be singled out by the group action.

• A geometric version of the Coding Theorem: The main theorem applies to fix-retractable symmetry groups, meaning groups that admit a computable section selecting an isolating symmetry for every string. Under this condition, the symmetry prior is shown to be a universal lower semicomputable semimeasure. This yields a direct analogue of the classical Coding Theorem, but expressed through geometric and group-theoretic structure.

• Galois connection and subgroup structure: The paper also develops a Galois connection between subgroups of the symmetry group and subsets of binary strings. This framework is used to characterize closed points, maximal closed subgroups, and the join-semilattice of dense subgroups.

Why it matters

The contribution is theoretical rather than immediately engineering-oriented. It does not claim a new AI model, benchmark, or application. Its significance lies in offering a different mathematical lens for complexity: not only how an object can be generated, but how it can be isolated by computable transformations.

That shift may be useful for researchers working on algorithmic statistics, formal notions of structure, or complexity measures induced by symmetry. It suggests a path for studying data and representations through invariance, fixed points, and group actions. At this stage, however, the work should be read as a foundational framework rather than a practical AI technique.

Source: arXiv