CAS II: Orbits as Models: Kolmogorov's Structure Function under Symmetry

Abstract

In algorithmic statistics a string x is explained by a finite set containing it, and Kolmogorov's structure function records the smallest such model at each level of complexity. Strong models, those computable from the data by a total algorithm, are essentially the cells of simple partitions, so a partition of {0,1}^n can be read as a hypothesis and the cell containing x as the model it assigns. We develop algorithmic statistics over symmetric partitions, the orbit partitions of groups acting on strings. The Galois connection between subgroups and partitions gives each ambient group G a lattice of symmetric partitions with canonical certificates, joins and meets. A set is a cell of a symmetric partition exactly when its setwise stabiliser in G acts transitively on it, so the resulting structure function is Kolmogorov's restricted to these G-homogeneous sets. With a symmetric sophistication, it measures which part of the regularity of x is symmetric. Under the full symmetric group, cells recover all models and cells of cheap partitions recover exactly the strong models, so normal and strange strings are characterised by symmetry. For GL(n,2) the homogeneous sets are the linearly homogeneous ones, whose XOR dependencies look the same from every point. The GL structure function of a nonzero x lies in a band between C(x) - alpha and n - alpha, and both edges are attained: some stochastic normal strings have simple structure invisible to linear symmetry, with sophistication near 0 but GL-sophistication near C(x). We coordinatise permutation groups by a Burnside ring element (type) and a permutation (placement). In these coordinates a linear hypothesis is determined by its type up to n^2 bits, and any space of symmetry hypotheses small enough to search is small enough to miss simple structure. This sets up learned search over orbit models, the subject of later papers in the series.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Information Theory

• arXiv preprint · 30 September 2026

  Quantum Algorithms for Minimum Generating Set

  Bireswar Das, Udit Kumar, Kavita Samant and 1 other
• arXiv preprint · 1 October 2026

  Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2

  Joshua A. Grochow, Gábor Ivanyos, Youming Qiao and 1 other
• arXiv preprint · 3 October 2026

  Amenable groups with nearly exponential sofic profile, and quantum channels that need nearly linear memory

  Seth Douglas and Nidhal Mghirbi
• arXiv preprint · 29 September 2026

  Sample Complexity of Equivariant Reinforcement Learning

  Rayan Mazouz, Haibo Zhao, Chris Hillar and 1 other
• arXiv preprint · 5 October 2026

  A Cohomological Characterization of the Clifford Hierarchy

  Junaid Aftab

All new papers in Information Theory