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

Romie Banerjee

cs.ITSep 30, 2026

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

Authors: Romie Banerjee

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.

Figures & tables

Panel of Figure 1 — Figure 1: A typical structure function (schematic, after [ 13 ] ). It lies above the sufficiency line, decreases with slope at most $-1$ , and touches the line first at the minimal sufficient statistic.

Panel of Figure 2 — Figure 2: Cells of $\mathrm{GL}(3,2)$ on the $3$ -cube. The ringed corners form a set $S$ ; colours are the orbits of its setwise stabiliser $\mathrm{GL}(3,2)_{\{S\}}$ , and hollow corners are fixed points. $S$ is a cell of a symmetric partition exactly when it is one colour (Proposition 3.5 ). The fifth set is the non-homogeneous example of Example 6.2 . An interactive version is in the HTML edition.

Panel of Figure 3 — Figure 3: Orbits of six subgroups of $\mathrm{GL}(4,2)$ on the $4$ -cube $\mathbb{F}_{2}^{4}$ (outer cube $x_{4}=0$ , inner cube $x_{4}=1$ , origin at the bottom left of the outer cube). Each orbit is linearly homogeneous. Only the coordinate groups in the first two panels preserve the edges of the cube; the others see the cube only through its $\mathbb{F}_{2}$ -linear structure. In the last panel the orbits are the triples $\{v,\omega v,\omega^{2}v\}$ , which sum to $0$ . An interactive version is in the HTML edition.

Panel of Figure 4 — Figure 4: The band containing $h^{\mathrm{GL}}_{x}$ (Theorem 7.1 ); both edges are attained.

Panel of Figure 5 — Figure 5: The structure functions for a typical normal string. The curves $h_{x}$ , $h^{\mathrm{Sym}}_{x}$ and $h^{\mathrm{str}}_{x,\varepsilon}=h^{\mathrm{Sym}}_{x,\varepsilon}$ coincide; the first two coincide for every string. The shaded region is the symmetry gap. The ordering, the guides, the endpoints and the coincidences are proved; the shapes of the two $\mathrm{GL}$ curves are illustrative. See items (1)–(10) in the text.

Panel of Figure 6 — Figure 6: Types and placements in $S_{X}$ for $n=3$ . A type is a list of cell sizes, with canonical certificate a Young subgroup; a placement is a set partition of the $8$ corners. Left: two placements of type $4\cdot 3\cdot 1$ , of which $280$ exist; only the lower one is also the orbit partition of a subgroup of $\mathrm{GL}(3,2)$ . Right: for each type, the number of placements and how many are also $\mathrm{GL}(3,2)$ -symmetric or symmetric under the cube group. An interactive version is in the HTML edition.

Panel of Figure 7 — Figure 7: The nine Galois-closed types of subgroups of $\mathrm{GL}(3,2)$ , one placement each, with the $3$ -cube coloured by orbits (hollow corners are fixed points). A type with normaliser $N$ has $168/|N|$ placements, and each closed placement gives one symmetric partition, $100$ in all. The six non-closed types are listed under their closures: they give no new partitions. Superscripts distinguish the classes stabilising a line (ln) or a plane (pl), and the Klein four-groups with a common axis (ax) or centre (ce). An interactive version showing every placement is in the HTML edition.

Explore similar work

CAS I: A Geometric Coding Theorem
Jul 15, 2026Romie BanerjeeFinite Groups Symmetry
Big data approach to Kazhdan-Lusztig polynomials
Dec 2, 2024Abel Lacabanne, Daniel Tubbenhauer, Pedro VazPolynomials Symmetry
Laboratoire de Mathématiques Blaise Pascal, Université Clermont Auvergne
Mapping Uncharted Symmetries: Machine Discovery in Combinatorics
May 18, 2026Eugenio Cainelli, Lorenzo Luccioli, Alessandro Iraci +2Combinations Symmetry
University of Bologna · Pegaso University · University of Pisa

Jul 15, 2026, cs.ITJ/K move · Enter open · S save

CAS I: A Geometric Coding Theorem

Romie Banerjee

Finite Groups Symmetry Information-Theoretic Limits Tractability

Open paper AskPDF arXiv

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 and define the symmetry prior of a string x as the probability that a randomly chosen symmetry from a given group G has x as its unique fixed point. We show that for any fix-retractable symmetry group G, 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. This result is a coding-theoretic restatement of a theorem of Trejo, Kreinovich and Longpré, who showed that the complexity of describing a string by a symmetry with that string as its unique fixed point equals its Kolmogorov complexity. Our contribution is to recast it in terms of algorithmic probability and to treat the symmetry group as a parameter, identifying fix-retractability as exactly the condition under which symmetry complexity collapses onto Kolmogorov complexity.

Abstract

Explore similar work

CAS I: A Geometric Coding Theorem

Big data approach to Kazhdan-Lusztig polynomials

Mapping Uncharted Symmetries: Machine Discovery in Combinatorics