cs.ITSep 30, 2026

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

Authors: Romie Banerjee

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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

Figure 1: A typical structure function (schematic, after [ 13 ] ). It lies above the sufficiency line, decreases with slope at most −1-1 , and touches the line first at the minimal sufficient statistic.
Figure 2: Cells of GL(3,2)\mathrm{GL}(3,2) on the 33 -cube. The ringed corners form a set SS ; colours are the orbits of its setwise stabiliser GL(3,2){S}\mathrm{GL}(3,2)_{\{S\}} , and hollow corners are fixed points. SS 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.
Figure 3: Orbits of six subgroups of GL(4,2)\mathrm{GL}(4,2) on the 44 -cube F24\mathbb{F}_{2}^{4} (outer cube x4=0x_{4}=0 , inner cube x4=1x_{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 F2\mathbb{F}_{2} -linear structure. In the last panel the orbits are the triples {v,ωv,ω2v}\{v,\omega v,\omega^{2}v\} , which sum to 00 . An interactive version is in the HTML edition.
Figure 4: The band containing hxGLh^{\mathrm{GL}}_{x} (Theorem 7.1 ); both edges are attained.
Figure 5: The structure functions for a typical normal string. The curves hxh_{x} , hxSymh^{\mathrm{Sym}}_{x} and hx,εstr=hx,εSymh^{\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 GL\mathrm{GL} curves are illustrative. See items (1)–(10) in the text.
Figure 6: Types and placements in SXS_{X} for n=3n=3 . A type is a list of cell sizes, with canonical certificate a Young subgroup; a placement is a set partition of the 88 corners. Left: two placements of type 4⋅3⋅14\cdot 3\cdot 1 , of which 280280 exist; only the lower one is also the orbit partition of a subgroup of GL(3,2)\mathrm{GL}(3,2) . Right: for each type, the number of placements and how many are also GL(3,2)\mathrm{GL}(3,2) -symmetric or symmetric under the cube group. An interactive version is in the HTML edition.
Figure 7: The nine Galois-closed types of subgroups of GL(3,2)\mathrm{GL}(3,2) , one placement each, with the 33 -cube coloured by orbits (hollow corners are fixed points). A type with normaliser NN has 168/∣N∣168/|N| placements, and each closed placement gives one symmetric partition, 100100 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

CardsList
Jul 15, 2026cs.IT

CAS I: A Geometric Coding Theorem

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.

Romie Banerjee

Finite GroupsSymmetryInformation-Theoretic LimitsTractability
AskPDF
May 18, 2026cs.LG

Mapping Uncharted Symmetries: Machine Discovery in Combinatorics

Inspired by long-standing open problems in algebraic combinatorics, we show that modern machine learning can meaningfully contribute to verifiable mathematical discoveries. In particular, we focus on the construction of simple mathematical functions under exact distributional constraints, a setting we formalize as Simple Learning Under Rigid Proportions (SLURP). We tackle this problem by introducing two methods: MapSeek-Functional, which models the desired function alternating pseudo-labeling and supervised training steps; and MapSeek-Symbolic, designed to directly produce symbolic formulas. We successfully apply both methods to a research problem in algebraic combinatorics, discovering a new combinatorial interpretation of the q,tq,t-Narayana polynomials arising from representation theory. To our knowledge, this is the first such interpretation based on noncrossing partitions. Using one discovered statistic, we find a combinatorial proof of the symmetry of these polynomials in a previously unsolved case. To streamline verification and reproducibility, we release all code, including a formalization of all the mathematical discoveries of this paper in Lean 4.

Eugenio Cainelli, Lorenzo Luccioli, Alessandro Iraci +2

University of Bologna · Pegaso University · University of Pisa

CombinationsSymmetryDiscoverySimple
AskPDF