Paper deep dive
CAS II: Orbits as Models: Kolmogorov's Structure Function under Symmetry
Romie Banerjee
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/6/2026, 10:12:20 AM
Summary
This paper develops algorithmic statistics over symmetric partitions, defined as orbit partitions of groups acting on bit strings. It establishes a Galois connection between subgroups and partitions, identifying cells of symmetric partitions as G-homogeneous sets. The study analyzes Kolmogorov's structure function restricted to these symmetric models, specifically examining the full symmetric group and the general linear group GL(n,2). Key findings include characterizing normal and strange strings via symmetry, bounding the GL structure function, and introducing coordinates for permutation groups using Burnside ring elements (type) and permutations (placement) to facilitate learned search over orbit models.
Entities (10)
Relation Signals (9)
Symmetric Partitions → definedby → Orbit Partitions
confidence 98% · We develop algorithmic statistics over symmetric partitions, the orbit partitions of groups acting on strings.
Galois Connection → connects → Subgroups
confidence 97% · The Galois connection between subgroups and partitions gives each ambient group G a lattice of symmetric partitions
Galois Connection → connects → Partitions
confidence 97% · The Galois connection between subgroups and partitions gives each ambient group G a lattice of symmetric partitions
GL(n,2) → hashomogeneoussets → Linearly Homogeneous Sets
confidence 96% · For GL(n,2) the homogeneous sets are the linearly homogeneous ones, whose XOR dependencies look the same from every point.
Symmetric Partitions → usedin → Algorithmic Statistics
confidence 95% · We develop algorithmic statistics over symmetric partitions
Symmetric Sophistication → measures → Symmetric Regularity
confidence 94% · With a symmetric sophistication, it measures which part of the regularity of x is symmetric.
Permutation Groups → coordinatizedby → Burnside Ring Element
confidence 93% · We coordinatise permutation groups by a Burnside ring element (type) and a permutation (placement).
Strong Models → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2609.40290v2
- Canonical: https://arxiv.org/abs/2609.40290v2
Trouble viewing inline? Open PDF directly →
Full Text
77,919 characters extracted from source content.
Expand or collapse full text
CAS I: Orbits as Models Kolmogorov’s Structure Function under SymmetryThanks: CAS stands for Computational Algorithmic Statistics. Part I is [1]; see Section 1.4. Romie Banerjee †thanks: An HTML edition with interactive versions of Figures˜2, 3, 6 and˜7 is available at https://romiebanerjee.github.io/CAS2/index.html. October 2026 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. The strong models of Vereshchagin, those computable from the data by a total algorithm, are essentially the cells of simple partitions. So a partition of 0,1n\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 assigns to each ambient group G a lattice ParGPar_G of symmetric partitions. Each has a canonical certificate whose cost equals that of the partition, and hypotheses can be combined by joins and meets. A set is a cell of some symmetric partition exactly when its setwise stabiliser in G acts transitively on it, and naming such a cell already names a canonical hypothesis. So the resulting structure function hxGh^G_x is Kolmogorov’s structure function restricted to these G-homogeneous sets. It and the symmetric sophistication sophG(x)soph^G(x) measure which part of the regularity of x is symmetric. For G=Sym(0,1n)G=Sym(\0,1\^n) every partition is symmetric. Cells then recover all Kolmogorov models, and cells of cheap partitions recover exactly the strong models, so normal and strange strings are characterised by symmetry. For G=GL(n,2)G=GL(n,2) the homogeneous sets are exactly the linearly homogeneous sets, those whose XOR dependencies look the same from every point. For every nonzero x, hxGLh^GL_x lies in a band between C(x)−αC(x)-α and n−αn-α, and both edges are attained. In particular, there are stochastic normal strings whose simple structure is entirely invisible to linear symmetry: soph(x)≈0soph(x)≈ 0 but sophGL(x)≈C(x)soph^GL(x)≈ C(x). Finally, we coordinatise the space of permutation groups. Each group is an element of a Burnside ring (its type) together with a permutation (its placement), and restriction moves refine partitions cell by cell via the Mackey formula. In these coordinates the collapse for SymSym is essentially a statement about placement, a linear hypothesis is determined by its type up to n2n^2 bits, and the maximal gap theorem shows that any space of symmetry hypotheses small enough to search is small enough to miss simple structure. These coordinates and limits set up the learned search over orbit models developed in later papers of the series. 1 Introduction 1.1 Models, strong models and partitions Kolmogorov proposed to explain a string x by a finite set S∋xS x, a model, and to measure the explanation by the two-part code C(x)≲C(S)+log|S|C(x) C(S)+ |S|: first the model, then the position of x in it, which is treated as noise [4, 2, 13, 12]. The structure function hx(α)h_x(α) records the smallest model affordable at complexity α, and a model is a sufficient statistic when the two parts together cost no more than C(x)C(x). Arbitrary finite sets are too generous as models. The universal models of Gács, Tromp and Vitányi [2] can be sufficient, yet they encode the number of strings of bounded complexity, so they cannot be found from the data. Vereshchagin [11] therefore singled out the strong models: those computable from x by a total algorithm. A total algorithm x′↦A(x′)x A(x ) assigns a model to every string, and Milovanov [7] observed that this makes strong models essentially the cells of simple partitions of 0,1n\0,1\^n. So beneath algorithmic statistics lies a theory of partitions. A partition p is a hypothesis: a classification of all strings into classes of strings the hypothesis cannot tell apart. The model for x is its cell, and the description becomes C(x)≲C(p)⏟hypothesis+C(B∣p)⏟which cell+log|B|⏟noise,x∈B∈p.C(x)\ \ C(p)_hypothesis\ +\ C(B p)_which cell\ +\ |B|_noise, x∈ B∈ p. (1.1) 1.2 Symmetric partitions Which partitions are structured hypotheses? The most natural source of classifications in mathematics and physics is symmetry: two strings are indistinguishable if some transformation from a group maps one to the other. The hypothesis is then the orbit partition of a group U acting on strings, and the size of the cell of x is governed by its symmetry. By the orbit–stabiliser theorem, log|U⋅x|=log|U|−log|stabU(x)|=−logPru∈U[ux=x], |U· x|= |U|- |stab_U(x)|=- _u∈ U[ux=x], so strings with large stabilisers lie in small cells and receive short descriptions in (1.1). This is the precise sense in which symmetric objects are simple: a symmetry hypothesis explains x well when it is cheap and x is fixed by a large part of it. Different groups can have the same orbits and then make the same hypothesis, so the group is best seen as a certificate that a partition arises from symmetry. The classical Galois connection between subgroups and partitions [3] makes this precise. For an ambient group G acting on strings it singles out a lattice ParGPar_G of symmetric partitions. Each symmetric partition has a canonical certificate, the largest subgroup with those orbits, which costs exactly as much as the partition. Hypotheses can be combined by joins and meets, and conjugation acts as relabelling. The theory of this paper is algorithmic statistics restricted to cells of symmetric partitions. These cells have an intrinsic description: a set is a cell exactly when its setwise stabiliser acts transitively on it, and the cell then carries a canonical hypothesis at no extra cost (Proposition 3.5). So the theory is that of a restricted model class in the sense of Vereshchagin and Vitányi [14]. The choice of ambient group matters. For G=Sym(0,1n)G=Sym(\0,1\^n) every partition is symmetric, and symmetry adds nothing to the theory of strong models. Its canonical certificates are Young subgroups, whose type records only the sizes of the cells, so for complex models the information sits in how the symmetry is placed (Proposition 9.4). At the other extreme, the orbit partition of the stabiliser of x in a large group has x\x\ as a cell: a lossless description that costs C(x)C(x). The informative cases lie in between and arise from structured ambient groups, above all the group GL(n,2)GL(n,2) of linear symmetries of 2nF_2^n. 1.3 The question and the results C(x)C(x) can always be recovered from a symmetric partition at full price, so the question is not whether but how: which part of the regularity of x is captured by cells of symmetric partitions, and at what cost? We measure this by the structure function hxGh^G_x over ParGPar_G, and summarise it by the symmetric sophistication sophG(x)soph^G(x), the least cost at which a cell of a symmetric partition is a sufficient statistic. (1) Framework (Sections 3–4). The Galois connection between subgroups and partitions: symmetric partitions, their canonical certificates and costs, the characterisation of cells as homogeneous sets, an algebra of joins and meets, and relabelling. Partition structure functions reduce to structure functions over homogeneous sets, and come with a dictionary between the group and partition formulations. (2) All permutations (Section 5). Every partition is symmetric. Cells of symmetric partitions recover all Kolmogorov models, and cells of cheap ones recover exactly the strong models. The canonical certificates are Young subgroups whose type records only cell sizes; for complex models all but O(2n/2)O(2^n/2) bits of their information sit in the placement. (3) Linear symmetry (Section 6). The cells of ParGLPar_GL are the linearly homogeneous sets, a combinatorial class defined by XOR dependencies, but whole symmetric partitions are rigid. Affine subspaces are cells of cheap symmetric partitions. (4) A band and its extremes (Sections 7–8). For nonzero x, C(x)−α≤hxGL(α)≤n−αC(x)-α≤ h^GL_x(α)≤ n-α, both edges are attained, and there are stochastic normal strings with soph(x)≈0soph(x)≈ 0 but sophGL(x)≈C(x)soph^GL(x)≈ C(x): their regularity is simple and computable, yet no linear symmetry captures any of it. Figure 5 places all the structure functions of the paper in one picture. (5) Coordinates and search (Section 9). Every permutation group is a Burnside ring element (its type) together with a permutation (its placement), which gives coordinates on the spaces of permutation groups and symmetric partitions, and moves for navigating them. In SXS_X the information of a hypothesis sits almost entirely in its placement, whereas a linear hypothesis is determined by its type up to n2n^2 bits. The maximal gap theorem limits what any search in these coordinates can achieve: coordinates small enough to search are small enough to miss simple structure. Figures 2, 3, 6 and 7 illustrate cells, orbits, types and placements on the 33- and 44-cubes, and Section 10 collects open problems. 1.4 Place in the series and outlook This is the second paper in a series on computational algorithmic statistics. CAS I [1] treats symmetries as a lossless description language: a string is singled out as the unique fixed point of a symmetry, and for fix-retractable groups the resulting prior satisfies a coding theorem. That result is the algorithmic-probability form of a theorem of Trejo, Kreinovich and Longpré [10], who showed that the corresponding complexity equals Kolmogorov complexity up to an additive constant. In the full group of computable bijections, however, every string has the same symmetries, so this reading measures how cheaply x can be singled out, not how symmetric x is. The present paper takes the complementary, lossy view: symmetries group strings into orbits, and an orbit is a model whose size is governed by the stabiliser. Later papers in the series will develop learned search, in particular reinforcement learning, over orbit models. The theory here is meant to make that search well posed. The coordinates of Section 9 give the state and action spaces: a hypothesis is a type together with a placement, and the moves are relabelling, restriction with its Mackey splitting of cells, and meets with other cheap hypotheses. The symmetric structure function gives the objective, through the deficiency C(p,B)+log|B|−C(x)C(p,B)+ |B|-C(x) of the model found, with C(x)C(x) estimated by a compressor. The maximal gap theorem says what failure means: a search that finds no good orbit model has shown that x has little symmetric structure, not that it is random (Section 9.3). The recommendations at the end of Section 9.3, to search types first and to refine by restriction and meets, are a first prior for such policies. 2 Preliminaries 2.1 Structure functions and sophistication C is plain Kolmogorov complexity and (y∣x)CT(y x) the total conditional complexity: the length of a shortest program that maps x to y and halts on every input. Strings have length n. Statements said to hold “up to O(logn)O( n)” hold up to additive O(logn)O( n) terms in all coordinates; c denotes a sufficiently large constant. Definition 2.1. The structure function of x∈0,1nx∈\0,1\^n is hx(α)=minlog|S|:x∈S⊆0,1n,C(S)≤αh_x(α)= \ |S|:x∈ S \0,1\^n,\ C(S)≤α\ for α≥clognα≥ c n. A model is sufficient if C(S)+log|S|≤C(x)+clognC(S)+ |S|≤ C(x)+c n, and the sophistication soph(x)=minα:hx(α)+α≤C(x)+clognsoph(x)= \α:h_x(α)+α≤ C(x)+c n\ is the complexity of a minimal sufficient statistic [5, 2, 13]. The string is stochastic if soph(x)=O(logn)soph(x)=O( n), and antistochastic if hx(α)≈n−αh_x(α)≈ n-α for all α<C(x)α<C(x) [6]. Lemma 2.2 ([13, 9]). For x∈0,1nx∈\0,1\^n with C(x)=κC(x)=κ, up to O(logn)O( n): (i) hx(α)≥κ−αh_x(α)≥κ-α; (i) hx(clogn)≤nh_x(c n)≤ n and hx(κ)=0h_x(κ)=0; (i) (halving law) hx(α)+αh_x(α)+α is non-increasing. Conversely [13], every simple function with (i)–(i) is the structure function of some x up to O(logn)O( n); such functions are called admissible. Figure 1 shows a typical structure function. The curve starts near n, where the only affordable model is essentially 0,1n\0,1\^n, and reaches 00 at α≈C(x)α≈ C(x), where x\x\ is affordable. It never lies below the sufficiency line C(x)−αC(x)-α (Lemma 2.2(i)), and by the halving law it falls by at least one bit per additional bit of model complexity, possibly in sudden drops. It first meets the sufficiency line at the minimal sufficient statistic, of complexity soph(x)soph(x), and follows the line from there on. The region above the curve is the profile PxP_x of all pairs (α,log|S|)(α, |S|) achieved by models S∋xS x. For a stochastic string the curve drops to the sufficiency line almost at once; for an antistochastic string it follows n−αn-α until α≈C(x)α≈ C(x). α |S| |S| of best modelnnC(x)C(x)00soph(x)soph(x)C(x)C(x)hx(α)h_x(α)minimal sufficient statisticprofile PxP_xsufficiency lineC(x)−αC(x)-α 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. 2.2 Strong models and partitions Definition 2.3 ([11, 7]). A model A∋xA x is ε -strong if (A∣x)≤εCT(A x)≤ , and hx,εstr(α)=minlog|A|:x∈A,(A∣x)≤ε,C(A)≤αh^str_x, (α)= \ |A|:x∈ A,\ CT(A x)≤ ,\ C(A)≤α\. A string is (ε,δ)( ,δ)-normal if hx,εstr(α+δ)≤hx(α)+δh^str_x, (α+δ)≤ h_x(α)+δ for all α, and strange if it has no strong minimal sufficient statistic. Strong models exclude the universal models of [2], which carry the information of the number of strings of bounded complexity [11]. Strange strings exist [11]; normal strings exist for every admissible shape [7]; antistochastic strings are normal [7]. The following lemma is the bridge to partitions. Lemma 2.4 (Partition lemma [7]). If A∋xA x is ε -strong, there is a partition p of 0,1n\0,1\^n with C(p)≤ε+O(logn)C(p)≤ +O( n) and a cell A1∋xA_1 x of p with A1⊆A_1 A and C(A1)≤C(A)+ε+O(logn)C(A_1)≤ C(A)+ +O( n). Proof. Let r be a total program with r(x)=Ar(x)=A and |r|≤ε|r|≤ . Group the strings x′x with x′∈r(x′)x ∈ r(x ) according to the value r(x′)r(x ), and put every other string in a singleton cell. This partition is computable from r and n, and the cell of x is A1=x′∈A:r(x′)=AA_1=\x ∈ A:r(x )=A\, computable from A, r and n. ∎ 2.3 Restricted model classes For a family A of finite sets, the restricted structure function hx(α)=minlog|A|:x∈A∈,C(A)≤αh^A_x(α)= \ |A|:x∈ A ,\ C(A)≤α\ uses only models from A, and soph(x)soph^A(x) is defined from it as soph(x)soph(x) is from hxh_x. The family is acceptable [14] (see also [7, 9]) if it is enumerable, contains every 0,1n\0,1\^n, and satisfies the covering condition: for a fixed polynomial ρ, every A∈A and every c<|A|c<|A|, the n-bit strings of A are covered by at most ρ(n)|A|/cρ(n)|A|/c members of A of size at most c. Theorem 2.5 ([14]). If A is acceptable, hxh^A_x obeys the halving law, and for every admissible shape P there is x with hxh_x and hxh^A_x both C(P)+O(nlogn)C(P)+O( n n)-close to P. 3 The Galois connection 3.1 Symmetric partitions Fix an ambient finite group G acting on a finite set X, with G=GnG=G_n computable from n when X=0,1nX=\0,1\^n. Let L(G)L(G) be the subgroup lattice and Par(X)Par(X) the partition lattice, ordered by refinement (p≤qp≤ q if every cell of p lies in a cell of q). Put orbG(U)=orbits of U,stabG(p)=g∈G:g(B)=B for every cell B∈p.orb_G(U)=\orbits of U\, _G(p)=\g∈ G:g(B)=B for every cell B∈ p\. Proposition 3.1 ([3]). orbG(U)≤p⇔U≤stabG(p)orb_G(U)≤ p U _G(p). Hence both maps are monotone, U≤stabGorbG(U)U _Gorb_G(U), orbGstabG(p)≤porb_Gstab_G(p)≤ p, and the closed subgroups (U=stabGorbGU=stab_Gorb_GU) correspond bijectively and order-preservingly to the symmetric partitions (p=orbGstabGp=orb_Gstab_Gp), which are exactly the orbit partitions of subgroups of G. Denote their lattice by ParGPar_G. Proof. If every U-orbit lies in a cell of p, each cell is a union of U-orbits and is U-invariant; conversely, if U preserves every cell its orbits lie in cells. The rest is the general theory of Galois connections. ∎ The closed subgroup stabG(p)stab_G(p) is the largest subgroup with orbit partition p: the canonical certificate of the hypothesis p. Example 3.2. (a) G=Sym(X)G=Sym(X): every partition is symmetric, and the canonical certificates are the Young subgroups ∏B∈pSym(B) _B∈ pSym(B). (b) G=SnG=S_n permuting the coordinates of 0,1n\0,1\^n: orb(Sn)orb(S_n) is the partition into weight classes; subgroups give finer “combinatorial” partitions. (c) G=GL(n,2)G=GL(n,2): symmetric partitions are rigid. If W≠2nW _2^n is a subspace with dimW≥2 W≥ 2, the partition W∖0∪singletons\W \0\\∪\singletons\ is not symmetric: any g preserving it fixes every vector outside W∖0W \0\, these span 2nF_2^n, so g=1g=1. With a canonical complement D, the orbit partition of GL(W)×idDGL(W)×\id_D\ is symmetric; its cells are d\d\ and d+(W∖0)d+(W \0\), d∈Dd∈ D. A cell can appear only together with the other orbits of its certificate. 3.2 Canonical cost C(p)C(p) is the complexity of a partition p of 0,1n\0,1\^n as a finite object, C(p,B)C(p,B) that of p with one of its cells, and C(U)C(U) the complexity of a generator list of U. Proposition 3.3 (Canonical cost). For U≤GU≤ G with p=orbG(U)p=orb_G(U) and a cell B of p: C(stabGp)≤C(p)+O(1)≤C(U)+O(1),C(stabGp,B)=C(p,B)±O(1).C(stab_Gp)≤ C(p)+O(1)≤ C(U)+O(1), C(stab_Gp,B)=C(p,B)± O(1). The canonical certificate is, up to O(1)O(1), the cheapest group with the given orbits, and it costs exactly as much as the hypothesis. Proof. Orbits are computable from generators; stabG(p)stab_G(p) is computable from p by search in GnG_n, and n is recoverable from p. ∎ 3.3 Cells: homogeneous sets A structure function sees a hypothesis only through the cell containing x and the cost of naming it. So the basic question is which sets occur as cells. Write GS=g∈G:g(S)=SG_\S\=\g∈ G:g(S)=S\ for the setwise stabiliser of S⊆XS X. Definition 3.4. A set S⊆XS X is G-homogeneous if GSG_\S\ acts transitively on S. Let GA_G denote the family of non-empty G-homogeneous subsets of X. Proposition 3.5 (Cells). Let S⊆XS X be non-empty. (i) S is a cell of some partition in ParGPar_G if and only if S∈GS _G. (i) If S∈GS _G, then pS=orbG(GS)p_S=orb_G(G_\S\) is the coarsest partition in ParGPar_G having S as a cell: every p∈ParGp _G with S∈pS∈ p refines pSp_S. (i) If S∈GS _G, then C(pS,S)=C(S)±O(1)C(p_S,S)=C(S)± O(1). For every partition p having S as a cell, C(S)≤C(p,S)+O(1)C(S)≤ C(p,S)+O(1). Proof. (i) If S=U⋅xS=U· x for some U≤GU≤ G, then U≤GSU≤ G_\S\, so GSG_\S\ is transitive on S. Conversely, if GSG_\S\ is transitive on S, then S is one of its orbits, hence a cell of pSp_S, which is symmetric by Proposition 3.1. (i) If p∈ParGp _G and S∈pS∈ p, then stabG(p)≤GSstab_G(p)≤ G_\S\, so p=orbGstabG(p)≤orbG(GS)=pSp=orb_Gstab_G(p) _G(G_\S\)=p_S because orbGorb_G is monotone. (i) GSG_\S\, and hence pSp_S, is computable from S by search in GnG_n, and n is recoverable from S. Conversely S is computable from (p,S)(p,S). ∎ So a cell carries its own canonical hypothesis, and naming the cell already names that hypothesis. Whole symmetric partitions are rigid (Example 3.2(c)), but single cells are constrained only by homogeneity. Example 3.6. (a) G=Sym(X)G=Sym(X): every non-empty set is homogeneous, and pSp_S is S,X∖S\S,X S\ (or X\X\ if S=XS=X). (b) G=GL(n,2)G=GL(n,2): a homogeneous set containing 00 is 0\0\, since 00 is fixed. Theorem 6.3 identifies the others. (c) G=GL(3,2)G=GL(3,2): 7979 of the 255255 non-empty subsets of 23F_2^3 are homogeneous, distributed by size 1,…,81,…,8 as 8,21,35,7,0,7,1,08,21,35,7,0,7,1,0. Every pair and every triple of nonzero vectors is homogeneous, and no 55-set is. Only 100100 of the 41404140 partitions of 23F_2^3 are symmetric, but 695695 have every cell homogeneous. See Figure 2. 100,010 a line affine plane contains 000000 e1,e2,e1+e2,e3e_1,e_2,e_1+e_2,e_3 a 55-set homogeneous homogeneous homogeneous not homogeneous not homogeneous not homogeneous Figure 2: Cells of GL(3,2)GL(3,2) on the 33-cube. The ringed corners form a set S; colours are the orbits of its setwise stabiliser GL(3,2)SGL(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. 3.4 The algebra of hypotheses Since orbGorb_G is a lower adjoint it preserves joins, and stabGstab_G as an upper adjoint preserves meets: orbG(⟨U,V⟩)=orbG(U)∨orbG(V),stabG(p∧q)=stabG(p)∩stabG(q).orb_G( U,V )=orb_G(U) _G(V), _G(p q)=stab_G(p) _G(q). So ParGPar_G is closed under joins in Par(X)Par(X): the join of two hypotheses is the hypothesis of all their symmetries together, and is coarser. The meet in ParGPar_G is p∧Gq=orbG(stabGp∩stabGq)≤p∧qp _Gq=orb_G(stab_Gp _Gq)≤ p q, the hypothesis of their common symmetries, which is finer. Both are computable, so C(p∨q),C(p∧Gq)≤C(p)+C(q)+O(logn)C(p q),C(p _Gq)≤ C(p)+C(q)+O( n). The cell of x in p∧Gqp _Gq lies inside the intersection of its cells in p and q. Meeting with a second cheap hypothesis is thus the natural way to sharpen an explanation (compare the paragraph on halving at the end of Section 7 and Question 7.2). 3.5 Relabelling G acts by conjugation on L(G)L(G) and by translation on ParGPar_G, and the two maps are equivariant: orbG(gUg−1)=g⋅orbG(U),stabG(g⋅p)=gstabG(p)g−1.orb_G(gUg^-1)=g·orb_G(U), _G(g· p)=g\,stab_G(p)\,g^-1. The model (g⋅p,gB)(g· p,gB) for gxgx is the model (p,B)(p,B) for x in new coordinates, and costs at most C(g)+O(1)C(g)+O(1) more. 4 Partition structure functions Definition 4.1. Let P assign to each n a family of partitions of 0,1n\0,1\^n. A P-model for x is a pair (p,B)(p,B) with p∈p and x∈B∈px∈ B∈ p. Define hx(α) h^P_x(α) =minlog|B|:(p,B)-model,C(p,B)≤α, = \ |B|:(p,B)\ P-model,\ C(p,B)≤α\, hx,ε(α) h^P_x, (α) =minlog|B|:(p,B)-model,C(p)≤ε,C(p,B)≤α, = \ |B|:(p,B)\ P-model,\ C(p)≤ ,\ C(p,B)≤α\, soph(x) ^P(x) =minα:hx(α)+α≤C(x)+clogn. = \α:h^P_x(α)+α≤ C(x)+c n\. C(p)C(p) is the cost of the hypothesis and C(B∣p)C(B p) that of the cell; C(p,B)=C(p)+C(B∣p)C(p,B)=C(p)+C(B p) up to O(logn)O( n). For an ambient group G we write hxGh^G_x, hx,εGh^G_x, and sophGsoph^G for =ParGP=Par_G. Proposition 4.2. Up to O(1)O(1) shifts: (i) hx≤hx≤hx,εh_x≤ h^P_x≤ h^P_x, , and ⊆′P implies hx′≤hxh^P _x≤ h^P_x; (i) every cell of a partition of complexity at most ε is (ε+O(1))( +O(1))-strong, so hx,ε+cstr≤hx,εh^str_x, +c≤ h^P_x, ; (i) soph(x)≤soph(x)soph(x) ^P(x) up to O(logn)O( n). Proof. (i) A cell is a finite set containing x and C(B)≤C(p,B)+O(1)C(B)≤ C(p,B)+O(1). (i) A total program knowing p maps x to its cell. (i) Follows from (i). ∎ Corollary 4.3 (Cells suffice). For every ambient G, up to O(1)O(1) shifts in α, hxG=hxGandsophG(x)=sophG(x).h^G_x=h^A_G_x ^G(x)=soph^A_G(x). Proof. A ParGPar_G-model (p,B)(p,B) has B∈GB _G and C(B)≤C(p,B)+O(1)C(B)≤ C(p,B)+O(1). A set B∈GB _G containing x gives the ParGPar_G-model (pB,B)(p_B,B) with C(pB,B)≤C(B)+O(1)C(p_B,B)≤ C(B)+O(1). Both by Proposition 3.5. ∎ The strong version does not reduce to cells in the same way. The canonical hypothesis satisfies C(pB)≤C(B)+O(1)C(p_B)≤ C(B)+O(1), but this can exceed the cost of the cheapest symmetric partition containing B by up to C(B∣p)≤log|p|≤nC(B p)≤ |p|≤ n bits. So hx,εGh^G_x, depends on which cheap partitions carry B, not only on B (compare Question 10.1). Groups and partitions. The group formulation defines hxL(G)(α)h^L(G)_x(α) as the least log|U⋅x| |U· x| over subgroups U≤GU≤ G with C(U,U⋅x)≤αC(U,U· x)≤α, and hx,εL(G)h^L(G)_x, by adding C(U)≤εC(U)≤ . Theorem 4.4 (Dictionary). For every ambient G, up to O(1)O(1) shifts in α and ε , hxL(G)=hxGh^L(G)_x=h^G_x and hx,εL(G)=hx,εGh^L(G)_x, =h^G_x, . Proof. A pair (U,U⋅x)(U,U· x) gives the ParGPar_G-model (orbGU,U⋅x)(orb_GU,U· x) at no greater cost. A ParGPar_G-model (p,B)(p,B) gives (stabGp,B)(stab_Gp,B), and stabG(p)⋅x=Bstab_G(p)· x=B because p is symmetric. Costs are compared by Proposition 3.3. ∎ Proposition 4.5 (Burnside form). If (p,B)(p,B) is a ParGPar_G-model for x with certificate U=stabG(p)U=stab_G(p), then |B|=|U|/|stabU(x)|=1/Pru∈U[ux=x]|B|=|U|/|stab_U(x)|=1/ _u∈ U[ux=x], so C(x∣p,B)≤log|B|+O(1)C(x p,B)≤ |B|+O(1). All but a 2−t2^-t fraction of x′∈Bx ∈ B have C(x′∣p,B)≥log|B|−tC(x p,B)≥ |B|-t. symmetry algorithmic statistics symmetric partition p∈ParGp _G hypothesis (model class) cell B∋xB x model log|U|−log|stabU(x)| |U|- |stab_U(x)| log|B| |B| C(p)C(p) small strong model x typical in its cell small randomness deficiency sophG(x)soph^G(x) soph(x)soph(x) 5 All permutations Let SymSym denote the ambient group Sym(0,1n)Sym(\0,1\^n), written SXS_X with X=0,1nX=\0,1\^n in Section 9. By Example 3.2(a), ParSymPar_Sym is the lattice of all partitions, and by Example 3.6(a) every non-empty set is a cell. Theorem 5.1. Up to O(1)O(1) shifts, hxSym=hxh^Sym_x=h_x, so sophSym=sophsoph^Sym=soph. Up to O(ε+logn)O( + n) shifts, hx,εSym=hx,εstrh^Sym_x, =h^str_x, . Proof. Every set is SymSym-homogeneous, so the first claim is Corollary 4.3; explicitly, for S∋xS x the partition S,X∖S\S,X S\ costs C(S)+O(1)C(S)+O(1). For the second claim combine Proposition 4.2(i) with the partition lemma (Lemma 2.4). ∎ Corollary 5.2. Up to O(ε+δ+logn)O( +δ+ n), a string is (ε,δ)( ,δ)-normal if and only if cells of partitions of complexity at most ε (equivalently, orbits of groups of complexity at most ε ) are as good as arbitrary models at every level. It is strange if and only if no such cell is a minimal sufficient statistic. So there are strings with no sufficient cheap symmetry explanation [11], and every admissible shape is realised by a string whose cheap-symmetry structure function equals its Kolmogorov structure function [7]. Theorem 5.1 says that unrestricted symmetry explains everything. As a statement about symmetry this is nearly vacuous. The canonical certificates in SXS_X are Young subgroups, whose type records only the sizes of the cells. In the coordinates of Section 9, a model of complexity much larger than 2n/22^n/2 has all but O(2n/2)O(2^n/2) bits of its information in the placement of its certificate, under every realisation (Proposition 9.4). Moreover, the canonical certificate in SXS_X can hide a genuinely structured symmetry (Example 9.5). 6 Linear symmetry Identify 0,1n\0,1\^n with 2nF_2^n and take G=GL(n,2)G=GL(n,2). Linear maps fix 00, so throughout x≠0x≠ 0. 6.1 Cells: linearly homogeneous sets Which sets can be cells of linear-symmetric partitions? A linear map preserves all 2F_2-linear dependencies, so a set can be an orbit of a linear group only if its internal dependency structure looks the same from each of its points. We make this precise. A relation in S⊆2n∖0S _2^n \0\ is a subset T⊆ST S with ∑T=0Σ T=0, an XOR dependency among elements of S. For example, in S=e1,e2,e1+e2S=\e_1,e_2,e_1+e_2\ the whole set is a relation, since e1+e2+(e1+e2)=0e_1+e_2+(e_1+e_2)=0. The family of all relations is the dependency structure of S (the binary matroid it represents). A permutation π of S preserves relations if ∑T=0⇔∑π(T)=0Σ T=0 Σπ(T)=0 for all T⊆ST S, i.e. if it is an automorphism of the dependency structure. Definition 6.1. A set S⊆2n∖0S _2^n \0\ is linearly homogeneous if the relation-preserving permutations of S act transitively on S: for any s,s′∈Ss,s ∈ S some automorphism of the dependency structure maps s to s′s . The analogy is with vertex-transitive graphs, where every vertex looks alike; here every point looks alike with respect to XOR dependencies instead of edges. Two extreme cases show the range of the notion. A linearly independent set has no relations, so every permutation preserves them and the set is homogeneous. A punctured subspace W∖0W \0\ has as many relations as possible, but GL(W)GL(W) moves any nonzero vector to any other while preserving them, so it too is homogeneous. Homogeneity fails when some points play special roles. Example 6.2. Linearly homogeneous sets include: W∖0W \0\ for a subspace W; affine subspaces a+Wa+W with a∉Wa∉ W; linearly independent sets; weight classes and other orbits of coordinate permutation groups; and cosets of multiplicative subgroups of 2n×F_2^n^×, identifying 2nF_2^n with 2nF_2^n. The set e1,e2,e1+e2,e3\e_1,e_2,e_1+e_2,e_3\ is not homogeneous: e1e_1 lies in the three-term relation e1,e2,e1+e2\e_1,e_2,e_1+e_2\ while e3e_3 lies in no relation, so no relation-preserving permutation maps e1e_1 to e3e_3. Figure 3 shows orbits of several subgroups of GL(4,2)GL(4,2). S4S_4 (coordinates) S2×S2S_2× S_2 unitriangular orbit sizes 12,42,61^2,4^2,6 orbit sizes 14,24,41^4,2^4,4 orbit sizes 12,2,4,81^2,2,4,8 stabiliser of a 22-face a transvection 4×⊂16×F_4^× _16^× orbit sizes 1,3,121,3,12 orbit sizes 18,241^8,2^4 orbit sizes 1,351,3^5 Figure 3: Orbits of six subgroups of GL(4,2)GL(4,2) on the 44-cube 24F_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 2F_2-linear structure. In the last panel the orbits are the triples v,ωv,ω2v\v,ω v,ω^2v\, which sum to 00. An interactive version is in the HTML edition. The key fact is a small piece of linear algebra: a permutation of S extends to an invertible linear map if and only if it preserves relations. This gives the characterisation of cells. Theorem 6.3. Let S⊆2n∖0S _2^n \0\. Every relation-preserving permutation of S is the restriction of an element of GL(n,2)SGL(n,2)_\S\. Hence S is GLGL-homogeneous if and only if it is linearly homogeneous, and GLA_GL consists of 0\0\ and the linearly homogeneous sets. By Corollary 4.3, hxGLh^GL_x is Kolmogorov’s structure function restricted to linearly homogeneous sets. Proof. The restriction of a linear map preserves relations. Conversely, a relation-preserving π defines a linear bijection Lπ(∑s∈Ts)=∑s∈Tπ(s)L_π( _s∈ Ts)= _s∈ Tπ(s) of span(S)span(S). It is well defined, because ∑T=∑T′Σ T=Σ T implies ∑(T△T′)=0Σ(T T )=0 and hence ∑π(T)=∑π(T′)Σπ(T)=Σπ(T ), and it is injective, because π−1π^-1 also preserves relations. Extending LπL_π by the identity on a complement of span(S)span(S) gives g∈GL(n,2)g (n,2) with g(S)=Sg(S)=S and g|S=πg|_S=π. So the restrictions of GL(n,2)SGL(n,2)_\S\ to S are exactly the relation-preserving permutations, and one group is transitive on S if and only if the other is. Since linear maps fix 00, a homogeneous set containing 00 is 0\0\. ∎ Why this matters. By Corollary 4.3 and Theorem 6.3, hxGLh^GL_x is Vereshchagin and Vitányi’s structure function for the concrete model class GLA_GL of linearly homogeneous sets [14], so the groups drop out of the definition. Since a homogeneous set determines its own certificate (Proposition 3.5), describing the group costs nothing extra, and every difference between hxGLh^GL_x and hxh_x comes from which sets are admissible. Under Sym(0,1n)Sym(\0,1\^n) every set qualifies (Theorem 5.1). Under GL(n,2)GL(n,2) only homogeneous sets do, and there are at most 2n4+n2^n^4+n of them against 22n2^2^n arbitrary sets. This scarcity is what the band (Section 7) measures and what the counting proof of Theorem 8.2 exploits. Membership in GLA_GL is a finite test, namely transitivity of the setwise stabiliser. However, half of a homogeneous set is usually not homogeneous, so the halving law for hxGLh^GL_x is a genuine open question (Question 7.2). Single cells are constrained only by homogeneity, but whole symmetric partitions are rigid (Example 3.2(c)). This matters for the strong version hx,εGLh^GL_x, , which requires a cheap symmetric partition containing the cell (Question 10.1). Linear hypotheses also have little room to hide information in placement: a subgroup of GL(n,2)GL(n,2) is determined by its type, an abstract group with a faithful module, up to n2n^2 bits (Proposition 9.6). 6.2 Affine hypotheses Every affine subspace is a cell of a cheap symmetric partition. For W∖0W \0\ this is Example 3.2(c). For a+Wa+W with a∉Wa∉ W, fix a complement D of W⊕⟨a⟩W a , and for w∈Ww∈ W let τw _w fix W⊕DW D pointwise and send a↦a+wa a+w. The group τw≅W\ _w\ W has cells v\v\ for v∈W⊕Dv∈ W D and a+d+Wa+d+W for d∈Dd∈ D, at cost C(W,a)+O(1)C(W,a)+O(1). Writing hxaffh^aff_x for the structure function over affine subspaces, we get, up to O(logn)O( n), hx≤hxGL≤hxaff,hx≤hx,εstr≤hx,εGL.h_x\ ≤\ h^GL_x\ ≤\ h^aff_x, h_x\ ≤\ h^str_x, \ ≤\ h^GL_x, . (6.1) 7 The band Theorem 7.1 (Band). Let x∈2n∖0x _2^n \0\ with C(x)=κC(x)=κ. Up to O(logn)O( n): (i) κ−α≤hx(α)≤hxGL(α)≤hxaff(α)≤n−ακ-α≤ h_x(α)≤ h^GL_x(α)≤ h^aff_x(α)≤ n-α for clogn≤α≤κc n≤α≤κ; (i) hxGL(clogn)≤log(2n−1)h^GL_x(c n)≤ (2^n-1) and hxGL(κ)=0h^GL_x(κ)=0; (i) 0≤hxGL(α)−hx(α)≤n−κ0≤ h^GL_x(α)-h_x(α)≤ n-κ, and soph(x)≤sophGL(x)≤κsoph(x) ^GL(x)≤κ; (iv) (relabelling) for g∈GL(n,2)g (n,2), hgxGL(α+C(g)+c)≤hxGL(α)h^GL_gx(α+C(g)+c)≤ h^GL_x(α). Proof. (i) By Lemma 2.2(i) and (6.1); for the last inequality use the affine subspace of strings agreeing with x in the first j coordinates. (i) Use the partitions 0,2n∖0\\0\,F_2^n \0\\ and the discrete partition. (i) Follows from (i) and (i). (iv) By equivariance of the Galois connection. ∎ α -size of best cellnnκ 00κ=C(x)κ=C(x)band of hxGLh^GL_xceiling n−αn-α (Thm. 8.2)floor κ−ακ-α (Cor. 8.1) Figure 4: The band containing hxGLh^GL_x (Theorem 7.1); both edges are attained. All the structure functions together. Figure 5 places the structure functions of this paper in one picture, for a typical normal string x of length n with κ=C(x)κ=C(x). Normal strings are the common case. A stochastic string has a simple, hence strong, sufficient model, so strangeness forces non-stochasticity, and non-stochastic strings have small a priori probability [12]. The figure shows six curves, of which three coincide for normal strings, together with two guide lines and three marked points. It should be read as follows. (1) The guides. The lower dashed line is the sufficiency line κ−ακ-α, and the upper one is the ceiling n−αn-α. By Lemma 2.2(i) and Theorem 7.1(i), every curve in the figure lies between them for clogn≤α≤κc n≤α≤κ, up to O(logn)O( n). A model on the sufficiency line is sufficient; a curve on the ceiling means that the models of that kind are no better than those of a random string of length n. (2) The order of the curves (proved for every x). By Proposition 4.2, up to O(1)O(1) shifts, hx≤hx,εstr≤hx,εGL,hx≤hxGL≤hx,εGL.h_x≤ h^str_x, ≤ h^GL_x, , h_x≤ h^GL_x≤ h^GL_x, . The cheap linear-symmetry curve pays for two restrictions at once: its models must be linear-symmetric and strong. (3) The endpoints (proved for every x). At the cheapest budget every curve is at most n: the one-cell partition and the partition 0,2n∖0\\0\,F_2^n \0\\ cost O(logn)O( n). At α≈κα≈κ every curve vanishes, since the discrete partition is cheap and its cell x\x\ costs κ. All differences between the curves occur for clogn≤α≤κc n≤α≤κ. (4) Kolmogorov’s curve hxh_x (solid blue) has the typical shape of Figure 1. It starts on the ceiling, decreases by at least one bit per bit of budget (the halving law), with two sudden drops, and first meets the sufficiency line at its minimal sufficient statistic (blue dot), of complexity soph(x)soph(x). From there it follows the sufficiency line down to α=κα=κ. (5) The unrestricted symmetric curve hxSymh^Sym_x (red dots) lies on hxh_x for every string, not only for normal ones. This is the collapse of Theorem 5.1: every finite set is a cell of a partition symmetric under Sym(0,1n)Sym(\0,1\^n), at no extra cost. In particular sophSym(x)=soph(x)soph^Sym(x)=soph(x), and the two tick labels at the blue dot coincide. The coincidence is nearly uninformative about symmetry: by Proposition 9.4 the canonical certificates are Young subgroups whose type records only cell sizes, so for complex models the information sits in the placement. (6) The strong curve hx,εstrh^str_x, (green dashes) also lies on hxh_x. This is the definition of normality: every point of the profile is attained by an ε -strong model, up to δ. By Theorem 5.1 the same curve is the cheap unrestricted symmetric curve hx,εSymh^Sym_x, . For a strange string it would separate from hxh_x and lie above it, while hxSymh^Sym_x would still lie on hxh_x. (7) The linear-symmetry curve hxGLh^GL_x (solid violet) uses cells of symmetric partitions of GL(n,2)GL(n,2) of any cost, that is, linearly homogeneous sets (Theorem 6.3). In the figure it follows the ceiling up to α≈κ/2α≈κ/2: at those budgets no linear symmetry sees any structure of x. It then drops, decreases along a segment of slope −1-1, drops again, and first meets the sufficiency line at the violet dot, whose complexity is the symmetric sophistication sophGL(x)soph^GL(x). By Theorem 7.1(i), soph(x)≤sophGL(x)≤κsoph(x) ^GL(x)≤κ. (8) The symmetry gap (shaded) is the region between hxh_x and hxGLh^GL_x. At each budget it is the part of the regularity of x that linear symmetry does not see. Its horizontal extent at the sufficiency line, sophGL(x)−soph(x)soph^GL(x)-soph(x), is the extra budget symmetric explanations need before they become sufficient. By Corollary 8.1 the region can be empty, with hxGL=hxh^GL_x=h_x. By Theorem 8.2 it can fill the whole band, with hxGLh^GL_x on the ceiling up to α≈κα≈κ, even for stochastic normal strings. (9) The cheap linear-symmetry curve hx,εGLh^GL_x, (orange dashes) uses only cells of symmetric partitions of complexity at most ε . In the figure it agrees with hxGLh^GL_x on the ceiling, where the cylinder partitions fixing the first j coordinates are cheap, and lies above it afterwards. There the good linear-symmetric cells of x exist only inside expensive symmetric partitions: the rigidity effect of Question 10.1. It meets the sufficiency line only at the right end, just before α=κα=κ. Because x is normal, this separation from hxGLh^GL_x is caused by symmetry, not by strangeness. (10) The marked points. On the horizontal axis: soph(x)soph(x), equal to sophSym(x)soph^Sym(x), where hxh_x and hxSymh^Sym_x become sufficient; sophGL(x)soph^GL(x), where hxGLh^GL_x becomes sufficient; and κ, where all curves vanish. On the vertical axis: n, where all curves start, and κ, where the sufficiency line starts. Items (1)–(6) and the inequality in (7) are theorems; item (10) only names the marked points. The particular shapes of hxGLh^GL_x and hx,εGLh^GL_x, are illustrative. Which shape is typical is open, and so is whether the rigidity separation in (9) occurs at all. Whether the GLGL curves obey the halving law (Question 7.2) is also open. If they do not, they may have plateaus, which hxh_x never has. α -size of best modelnnκ 00soph(x)soph(x)=sophSym(x)=soph^Sym(x)sophGL(x)soph^GL(x)κ gapn−αn- lineκ−ακ- _xhxSymh^Sym_xhx,εstr=hx,εSymh^str_x, =h^Sym_x, hxGLh^GL_xhx,εGLh^GL_x, Figure 5: The structure functions for a typical normal string. The curves hxh_x, hxSymh^Sym_x and hx,εstr=hx,εSymh^str_x, =h^Sym_x, 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 GLGL curves are illustrative. See items (1)–(10) in the text. Halving as refinement. Affine subspaces form an acceptable class: a coset of dimension d splits into at most 2|A|/c2|A|/c cosets of size at most c. By Theorem 2.5, hxaffh^aff_x obeys the halving law. For hxGLh^GL_x the question becomes one about the lattice ParGLPar_GL. Given a symmetric p with x∈B∈px∈ B∈ p, is there a cheap symmetric refinement whose cell containing x has size about |B|/2|B|/2? The algebra of Section 3 suggests meeting p with a second cheap hypothesis q: the cell of x in p∧GLqp _GLq lies in the intersection of its cells. Transitivity alone does not obstruct this. GL(n,2)GL(n,2) is 22-transitive on nonzero vectors, so no subgroup between stab(x)stab(x) and GL(n,2)GL(n,2) refines the orbit of x, but subgroups not containing stab(x)stab(x) can. Since linear maps fix 00, homogeneous sets other than 0\0\ avoid 00, so GLA_GL contains 2n∖0F_2^n \0\ rather than the whole space required in the definition of acceptability; this changes nothing up to O(1)O(1). Question 7.2. Is GLA_GL acceptable, i.e. can every S∈GLS _GL of size N be covered by poly(n)N/cpoly(n)\,N/c members of GLA_GL of size at most c? In the language of Section 3.4: does every cell admit cheap symmetric refinements, for instance by meets? If not, does hxGLh^GL_x exhibit a plateau for some x? 8 The extremes of the band 8.1 Zero gap: symmetry explains everything Corollary 8.1. For every admissible shape P there is a string x with hx≈hxGL≈hxaff≈Ph_x≈ h^GL_x≈ h^aff_x≈ P, up to C(P)+O(nlogn)C(P)+O( n n), so sophGL(x)=soph(x)soph^GL(x)=soph(x) to the same accuracy. Proof. Theorem 2.5 applied to affine subspaces, and (6.1). ∎ 8.2 Maximal gap: structure invisible to symmetry Theorem 8.2 (Maximal gap). There is a constant c such that for all n, all clogn≤m≤nc n≤ m≤ n and all t≥0t≥ 0 there are strings x∈0,1nx∈\0,1\^n with: (a) C(x)=m±O(t+logn)C(x)=m± O(t+ n) and hx(α)=m−α±O(t+logn)h_x(α)=m-α± O(t+ n) for clogn≤α≤mc n≤α≤ m; x is stochastic and (O(logn),O(t+logn))(O( n),O(t+ n))-normal; (b) hxGL(α)≥n−α−t−O(logn)h^GL_x(α)≥ n-α-t-O( n) for all α≤m−t−clognα≤ m-t-c n. In fact all but a 2−t2^-t fraction of a set S with C(S)=O(logn)C(S)=O( n) and |S|≈2m|S|≈ 2^m have these properties. Proof. Counting cells. By Proposition 9.6, or simply because a group of order N has a generating set of size logN N, there are at most 2n42^n^4 subgroups of GL(n,2)GL(n,2), hence at most 2n4+n2^n^4+n cells of symmetric partitions. A set that no cell sees. Put each string into a random S independently with probability 2m−n2^m-n. For a cell B let RB=max(2e 2m−n|B|,n5)R_B= (2e\,2^m-n|B|,n^5). The Chernoff bound Pr[X≥R]≤2−R [X≥ R]≤ 2^-R for R≥2eXR≥ 2e\,EX [8] gives Pr[|S∩B|≥RB]≤2−n5 [|S∩ B|≥ R_B]≤ 2^-n^5. A union bound, and concentration of |S||S|, show that with positive probability 2m−1≤|S|≤2m+1and|S∩B|<max(2e 2m−n|B|,n5)for every cell B.2^m-1≤|S|≤ 2^m+1 |S∩ B|< (2e\,2^m-n|B|,\,n^5)\ for every cell B. (8.1) This property is decidable, so the lexicographically first such S has C(S)=O(logn)C(S)=O( n). Typical elements. All but a 2−t2^-t fraction of x∈Sx∈ S have C(x)≥m−tC(x)≥ m-t; fix one. (a) Cutting S into 2j2^j consecutive pieces gives models of complexity j+O(logn)j+O( n) and size at most 2m+1−j2^m+1-j, each computable from x by a total program of length O(logn)O( n). With Lemma 2.2(i) this gives hxh_x and normality. (b) Fix α,sα,s. Fewer than 2α+12^α+1 models (p,B)(p,B) have C(p,B)≤αC(p,B)≤α, and the union U of those cells with |B|≤2s|B|≤ 2^s is enumerable from n,m,α,sn,m,α,s. By (8.1), |U∩S|≤2α+1max(2e 2m−n+s,n5)|U∩ S|≤ 2^α+1 (2e\,2^m-n+s,n^5). If x∈Ux∈ U, then m−t≤C(x)≤log|U∩S|+O(logn)≤α+max(m−n+s, 5logn)+O(logn).m-t≤ C(x)≤ |U∩ S|+O( n)≤α+ (m-n+s,\ 5 n)+O( n). For α≤m−t−clognα≤ m-t-c n the second branch is impossible, so s≥n−α−t−O(logn)s≥ n-α-t-O( n). ∎ Corollary 8.3 (Simple structure, invisible to symmetry). If moreover m≤n−t−c′lognm≤ n-t-c n, these strings satisfy soph(x)=O(logn)soph(x)=O( n) but sophGL(x)≥C(x)−O(t+logn)soph^GL(x)≥ C(x)-O(t+ n). They are stochastic and normal, yet no cell of a symmetric partition costing less than C(x)−O(t+logn)C(x)-O(t+ n) is sufficient: every sufficient symmetric model essentially names x itself. The gap between the two chains in (6.1) is a symmetry phenomenon, not a computability one. Proof. By (b), hxGL(α)+α≥n−t−O(logn)>C(x)+clognh^GL_x(α)+α≥ n-t-O( n)>C(x)+c n for α≤m−t−clognα≤ m-t-c n. ∎ Remark. The argument only uses that the partition family has 2poly(n)2^poly(n) cells and is decidable. So every such family, for instance ParGPar_G for any ambient group of order 2poly(n)2^poly(n), has stochastic normal strings that it sees as antistochastic. The construction is not explicit. 9 Coordinates on the space of permutation groups The Galois connection organises symmetry hypotheses into a lattice. To move through that lattice, and to search it, we need coordinates. This section shows that every permutation group is a Burnside ring element (its type) together with a permutation (its placement), compares the two ambient groups in these terms, and discusses what the maximal gap theorem implies for searching the coordinates for good models. 9.1 The coordinate theorem We give coordinates on the set of all permutation groups on a finite set X, |X|=N|X|=N; in our setting X=0,1nX=\0,1\^n and N=2nN=2^n. Via the Galois connection of Section 3 these become coordinates on symmetric partitions, and they are used to navigate both spaces. To keep G for the ambient group, we write H for the abstract group. A subgroup U≤SXU≤ S_X is the image of a faithful action ρ:H→SXρ H→ S_X of an abstract group H≅UH U. Up to isomorphism of H-sets, the action is determined by its class in the Burnside ring B(H)B(H). Fix representatives K1,…,KrK_1,…,K_r of the conjugacy classes of subgroups of H. Then [X]ρ=∑i=1rai[H/Ki],ai≥0,deg[X]ρ:=∑iai|H:Ki|=N.[X]_ρ= _i=1^ra_i\,[H/K_i], a_i≥ 0, [X]_ρ:= _ia_i\,|H:K_i|=N. The action is faithful iff ⋂ai>0coreH(Ki)=1 _a_i>0core_H(K_i)=1, where coreH(K)=⋂hKh−1core_H(K)= _hhKh^-1 is the kernel of H on H/KH/K. By Burnside’s theorem, b∈B(H)b∈ B(H) is determined by its marks φK(b)=|XbK| _K(b)=|X_b^K|, the number of points fixed by K. Definition 9.1 (Canonical realisation). Let BN(H)B_N(H) be the set of faithful b=∑ai[H/Ki]b=Σ a_i[H/K_i] of degree N. Fix H concretely (with a total order on its elements) and the representatives KiK_i canonically. For b∈BN(H)b∈ B_N(H) let XbX_b be the disjoint union of aia_i copies of H/KiH/K_i, ordered by i, then by copy, then by the least element of each coset. Identify XbX_b with X in lexicographic order. This gives a faithful action ρb _b and a canonical subgroup Ub=ρb(H)≤SXU_b= _b(H)≤ S_X. Theorem 9.2 (Coordinates). Let H(X)=U≤SX:U≅HS_H(X)=\U≤ S_X:U H\ and ΦH:BN(H)×SX→H(X),ΦH(b,σ)=σUbσ−1. _H B_N(H)× S_X _H(X), _H(b,σ)=σ\,U_b\,σ^-1. (i) ΦH _H is surjective: every U≅HU H has coordinates (b,σ)(b,σ). (i) For fixed b, ΦH(b,σ)=ΦH(b,σ′) _H(b,σ)= _H(b,σ ) iff σ−1σ′∈NSX(Ub)σ^-1σ ∈ N_S_X(U_b). (i) ΦH(b,σ) _H(b,σ) and ΦH(b′,σ′) _H(b ,σ ) are conjugate in SXS_X iff b′∈Aut(H)⋅b (H)· b, where α∈Aut(H)α (H) acts by [H/K]↦[H/α(K)][H/K] [H/α(K)]. Consequently H(X)=⨆[b]∈BN(H)/Aut(H)SX/NSX(Ub):S_H(X)\;=\; _[b]∈ B_N(H)/Aut(H)S_X/N_S_X(U_b): the type [b][b] is a discrete coordinate labelling conjugacy classes, and the placement σ is a coordinate on the homogeneous space SX/NSX(Ub)S_X/N_S_X(U_b). The whole space of permutation groups on X is the disjoint union of these pieces over the isomorphism classes of H with a faithful action of degree N. Proof. (i) Fix an isomorphism ψ:H→Uψ H→ U. The H-set X with action ψ is faithful of some class b∈BN(H)b∈ B_N(H), so there is an isomorphism of H-sets σ:(X,ρb)→(X,ψ)σ (X, _b)→(X,ψ), i.e. σρb(h)σ−1=ψ(h)σ _b(h)σ^-1=ψ(h) for all h. Hence U=σUbσ−1U=σ U_bσ^-1. (i) This is the definition of the normaliser. (i) If τUbτ−1=Ub′τ U_bτ^-1=U_b , then α=ρb′−1∘cτ∘ρbα= _b ^-1 c_τ _b is an automorphism of H, and τ is an isomorphism of H-sets from XbX_b to Xb′X_b twisted by α, so b′=α⋅b =α· b. The converse reverses the argument. ∎ Partitions and cells in coordinates. The orbits of UbU_b are the summands of XbX_b, which are consecutive intervals of X. Let λ(b)λ(b) be the integer partition of N with part |H:Ki||H:K_i| repeated aia_i times, and pλ(b)p_λ(b) the corresponding partition of X into consecutive intervals. Then orb(ΦH(b,σ))=σ⋅pλ(b).orb ( _H(b,σ) )=σ· p_λ(b). So partitions have coordinates (λ,σ)(λ,σ), with σ defined modulo the stabiliser of pλp_λ in SXS_X. The projection (b,σ)↦(λ(b),σ)(b,σ) (λ(b),σ) is orborb written in coordinates: it forgets the structure of b beyond its cell sizes. If σ−1(x)σ^-1(x) lies in a summand of type H/KiH/K_i, then the cell of x has size |H:Ki||H:K_i|, its stabiliser is conjugate to KiK_i, and Pru∈U[ux=x]=|Ki||H|. _u∈ U[ux=x]= |K_i||H|. The marks φK(b) _K(b) give the whole distribution of cell sizes and fixed points over X; Proposition 4.5 is the pointwise case. Proposition 9.3 (Complexity in coordinates). Let U=ΦH(b,σ)U= _H(b,σ), with b chosen canonically in its Aut(H)Aut(H)-orbit. Then, up to O(logC(U))O( C(U)), C(U)=C(H,b)+minC(σ′∣H,b):ΦH(b,σ′)=U.C(U)\;=\;C(H,b)\;+\; \\,C(σ H,b): _H(b,σ )=U\,\. Proof. From U one computes H up to isomorphism, the canonical b, and the least σ in the coset σNSX(Ub)σ N_S_X(U_b). This least element is computable from any member of the coset together with (H,b)(H,b). Apply symmetry of information. ∎ Navigation. Two basic moves act on coordinates. • Relabelling: (b,σ)↦(b,πσ)(b,σ) (b,πσ) conjugates the group by π and translates its partition, at cost at most C(π)C(π). • Restriction to a subgroup L≤HL≤ H: the subgroup σρb(L)σ−1σ _b(L)σ^-1 has coordinates (ResLHb,στ)(Res^H_Lb,\ στ) in L(X)S_L(X), where τ is computable from (H,L,b)(H,L,b). Its partition refines that of U cell by cell, according to the Mackey formula ResLH[H/K]=∑LhK∈L /K[L/(L∩hKh−1)],Res^H_L\,[H/K]= _LhK∈ L H/K [L/(L∩ hKh^-1) ], so a cell of size |H:K||H:K| splits into cells of sizes |L:L∩hKh−1||L:L∩ hKh^-1|. Restriction moves down the subgroup lattice and refines hypotheses; relabelling moves within a conjugacy class. In coordinates, the halving question (Question 7.2) asks for a cheap subgroup L≤HL≤ H whose Mackey decomposition splits the cell of x roughly in half. Remark. For subgroups of GL(n,2)GL(n,2) the same construction applies with B(H)B(H) replaced by the isomorphism classes of faithful 2HF_2H-modules of dimension n (the Green ring), and SXS_X by GL(n,2)GL(n,2). The fibres are then GL(n,2)/NGL(n,2)(Ub)GL(n,2)/N_GL(n,2)(U_b), and the placement costs at most n2n^2 bits (Proposition 9.6). 9.2 Types and placements: SXS_X versus GL(n,2)GL(n,2) The coordinates separate what a symmetry hypothesis is (its type) from where it sits (its placement). The two ambient groups behave very differently. Proposition 9.4 (Placement dominates). Let S⊆XS X, and let p be any partition of X having S as a cell (by Example 3.6(a) there are many, the coarsest being S,X∖S\S,X S\), with canonical certificate U=stabSX(p)U=stab_S_X(p). Let λ(p)λ(p) be the multiset of cell sizes of p, an integer partition of N=2nN=2^n. (i) U=∏B∈pSym(B)U= _B∈ pSym(B) is a Young subgroup, and its type (H,b)(H,b) is determined by λ(p)λ(p): H=∏B∈pS|B|H= _B∈ pS_|B|, and b has one orbit of type H/HBH/H_B for each cell B, where HBH_B is the stabiliser of a point of B. Hence C(H,b)≤C(λ(p))+O(1)≤logP(N)+O(n)=O(2n/2),C(H,b)≤ C(λ(p))+O(1)≤ P(N)+O(n)=O(2^n/2), where P(N)P(N) is the number of integer partitions of N. (i) Every placement realising U is expensive: minC(σ∣H,b):ΦH(b,σ)=U≥C(S)−C(λ(p))−O(n). \C(σ H,b): _H(b,σ)=U\\ ≥\ C(S)-C(λ(p))-O(n). In particular the placement carries at least C(S)−O(2n/2)C(S)-O(2^n/2) bits, for every partition realising S. (i) For p=S∪singletonsp=\S\∪\singletons\ with |S|=k≥2|S|=k≥ 2, the type is H=SkH=S_k, b=[Sk/Sk−1]+(2n−k)[Sk/Sk]b=[S_k/S_k-1]+(2^n-k)[S_k/S_k], costing O(n)O(n), and the placement costs C(S)±O(n)C(S)± O(n). Proof. (i) By Example 3.2(a) the closed subgroups of SXS_X are the Young subgroups. A Young subgroup is determined up to conjugacy by its cell sizes, and its abstract group and Burnside ring element are computable from them. Given N, the partition λ(p)λ(p) is one of P(N)P(N) possibilities, and by the Hardy–Ramanujan formula log2P(N)∼π2N/3/ln2=O(2n/2) _2P(N) π 2N/3/ 2=O(2^n/2). (i) Since U≤SXU≤ S_X, C(U)≤n2n+O(1)C(U)≤ n2^n+O(1), so the error term in Proposition 9.3 is O(n)O(n). From U one computes p, and S is one of at most N cells of p. Hence C(S)≤C(H,b)+minC(σ∣H,b)+n+O(n)C(S)≤ C(H,b)+ C(σ H,b)+n+O(n); now use (i). (i) S is the unique cell of size greater than one, so C(U)=C(S)±O(1)C(U)=C(S)± O(1), and the type is described by k and n. ∎ So every symmetric realisation of a model in SXS_X has a type that records only cell sizes. Such a type carries at most O(2n/2)O(2^n/2) bits, and only in the numbers |B||B|, which is a numerical encoding rather than a symmetry. For a model of complexity much larger than 2n/22^n/2, which includes typical sets of non-trivial size, the placement carries essentially all the information, under every realisation. For simpler models a suitably chosen partition can move information into the cell sizes, but the abstract group remains a product of full symmetric groups. A symmetry explanation is informative only when its information lies in a type with genuine group-theoretic structure, and the canonical certificates of SXS_X never provide one. Remark. The type is cheap, but it is not empty. Write b=∑iai[H/Ki]b= _ia_i[H/K_i]. For any ambient group, the cells of ΦH(b,σ) _H(b,σ) have sizes |H:Ki||H:K_i| with multiplicities aia_i, and there are ∑iai _ia_i of them. In the three-part description (1.1) this divides the terms between the coordinates: C(x)≲C(H,b)+C(σ∣H,b)⏟hypothesis, C(p)+log∑iai⏟which cell+log|H:Ki|⏟noise,C(x)\ \ C(H,b)+C(σ H,b)_hypothesis, C(p)\ +\ _ia_i_which cell\ +\ |H:K_i|_noise, where i is the orbit type of the cell containing x. Both data-to-model terms are read off from the type: it fixes how many cells there are and the multiset of their sizes, and so locates every cell on the vertical axis of the structure function. It does not fix the size of the cell containing x, which depends on the placement, unless all cells have the same size, as for free or transitive actions. For SXS_X, Proposition 9.4 shows that the division is nearly clean: the type costs O(2n/2)O(2^n/2) bits and carries the sizes, while the placement carries essentially all of C(p)C(p). A Young subgroup says how large the cells are, and nothing about which sets they are. For GL(n,2)GL(n,2) the two do not separate in this way, since the type determines the hypothesis up to n2n^2 bits (Proposition 9.6). Example 9.5 (The canonical certificate can hide structure). Let pwtp_wt be the partition of 0,1n\0,1\^n into weight classes. It is the orbit partition of the coordinate group SnS_n permuting bit positions, a small group with structured type ∑w=0n[Sn/(Sw×Sn−w)] _w=0^n[S_n/(S_w× S_n-w)]. It is also the orbit partition of the Young subgroup ∏wSym(x:|x|=w) _wSym(\x:|x|=w\), whose type is just the list of binomial coefficients (nw) nw. Both certify the same hypothesis at the same canonical cost O(logn)O( n). With ambient group SXS_X, however, the Galois connection selects the Young subgroup, so the canonical certificate forgets the symmetry that actually explains the partition. With ambient group GL(n,2)GL(n,2) the closed subgroup of pwtp_wt is exactly the group of permutation matrices, since a linear map preserving weight sends each eie_i to some eje_j. There the certificate keeps its structure. Figure 6 shows types and placements in SXS_X for n=3n=3. a placement a GL-symmetric placement type all GL cube type all GL cube 181^8 1 1 1 5⋅135· 1^3 56 0 0 2⋅162· 1^6 28 0 0 32⋅23^2· 2 280 0 0 22⋅142^2· 1^4 210 21 6 4⋅224· 2^2 210 0 12 3⋅153· 1^5 56 0 0 4⋅3⋅14· 3· 1 280 7 0 23⋅122^3· 1^2 420 7 0 5⋅2⋅15· 2· 1 168 0 0 3⋅2⋅133· 2· 1^3 560 0 0 6⋅126· 1^2 28 7 0 4⋅144· 1^4 70 7 0 424^2 35 0 7 242^4 105 0 13 5⋅35· 3 56 0 0 3⋅22⋅13· 2^2· 1 840 0 0 6⋅26· 2 28 0 4 32⋅123^2· 1^2 280 28 4 7⋅17· 1 8 1 0 4⋅2⋅124· 2· 1^2 420 21 0 88 1 0 1 Total: 4140 partitions, 100 GL-symmetric, 48 cube-symmetric. 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· 3· 1, of which 280280 exist; only the lower one is also the orbit partition of a subgroup of GL(3,2)GL(3,2). Right: for each type, the number of placements and how many are also GL(3,2)GL(3,2)-symmetric or symmetric under the cube group. An interactive version is in the HTML edition. Proposition 9.6 (Type determines the hypothesis up to n2n^2 bits). Let U≤GL(n,2)U (n,2) have coordinates (b,g)(b,g) as in the remark at the end of Section 9.1: b is the class of a faithful 2HF_2H-module of dimension n and g∈GL(n,2)g (n,2) is a placement. Then, up to O(logn)O( n), C(H,b)≤C(U)≤C(H,b)+n2.C(H,b)\ ≤\ C(U)\ ≤\ C(H,b)+n^2. Consequently the number of symmetric partitions in ParGLPar_GL is at most the number of types times |GL(n,2)||GL(n,2)|, which is less than 2n22^n^2. Proof. The type is computable from U. Conversely U=gUbg−1U=gU_bg^-1, where UbU_b is computable from the type and g is an n×n× n matrix. ∎ Contrast Proposition 9.4: in SXS_X the placement can carry almost all of the information, whereas in GL(n,2)GL(n,2) it carries at most n2n^2 bits. A linear symmetry hypothesis is essentially an abstract group with a module, and it cannot hide arbitrary information in its placement. Figure 7 shows the closed types for n=3n=3. 11, order 11, 11 placement C2C_2, order 22, 2121 placements V4axV_4^ax, order 44, 77 placements V4ceV_4^ce, order 44, 77 placements S3S_3, order 66, 2828 placements D8D_8, order 88, 2121 placements closure of C3C_3 closure of C4C_4 S4lnS_4^ln, order 2424, 77 placements S4plS_4^pl, order 2424, 77 placements GL3GL_3, order 168168, 11 placement closure of A4lnA_4^ln closure of A4plA_4^pl closure of C7, 7:3C_7,\ 7:3 Figure 7: The nine Galois-closed types of subgroups of GL(3,2)GL(3,2), one placement each, with the 33-cube coloured by orbits (hollow corners are fixed points). A type with normaliser N 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. 9.3 What the maximal gap theorem means for search The coordinates make the search for symmetric models concrete. A hypothesis is a type (H,b)(H,b) together with a placement, and one moves through the space by relabelling, by restriction with its Mackey splitting of cells, and by meets with other cheap hypotheses. It is natural to try to find good models of a given string x this way, by exhaustive, heuristic or learned search. Theorem 8.2 sets the limits of any such procedure. Failure can be forced by the class, not the search. For the strings of Theorem 8.2, no cell of a linear-symmetric partition costing much less than C(x)C(x) is a good model. No search strategy over ParGLPar_GL, however it navigates the coordinates, can find one, because none exists. Conversely, a model found by search only gives an upper bound on hxGLh^GL_x. Since structure functions are not computable, no search yields matching lower bounds. Failure says little about x. The strings of Theorem 8.2 are stochastic and normal. Their sufficient statistics are simple, and even computable from x by a short total program (Corollary 8.3). So “no good symmetric model found” means “no linear-symmetric structure found”. It is no evidence that x is random, nor that x is strange. Permutation-group coordinates are complete but uninformative. For the ambient group SXS_X, search is complete in principle: by Theorem 5.1, every Kolmogorov model is a cell of a symmetric partition. But by Proposition 9.4, the canonical certificates are Young subgroups whose type is just a list of cell sizes, so for models of complexity much larger than 2n/22^n/2 the search takes place almost entirely among placements, under every realisation. The homogeneous spaces SX/NSX(Ub)S_X/N_S_X(U_b) can have size close to (2n)!(2^n)!, and searching them is searching arbitrary finite sets under another name. The group structure helps only for models whose information lies mainly in the type. Matrix-group coordinates are searchable but blind. For GL(n,2)GL(n,2), the placement costs at most n2n^2 bits (Proposition 9.6). The effective search space is therefore the discrete set of types, small abstract groups with faithful modules, times at most 2n22^n^2 placements: altogether 2poly(n)2^poly(n) hypotheses. This finiteness is what makes the search feasible, and it is exactly what the proof of Theorem 8.2 exploits: any family of 2poly(n)2^poly(n) decidable cells is blind to some stochastic normal strings. The same holds for AGL(n,2)AGL(n,2), for coordinate permutations, and for any finite combination of such classes (the remark after Corollary 8.3). In short: A coordinate system in which the space of symmetry hypotheses is small enough to search is small enough to miss simple structure. Completeness requires the full group SXS_X, where the hypotheses stop being meaningfully symmetric. What search is good for. None of this makes symmetric search useless. Theorem 8.2 is non-constructive. It shows that blind strings exist, not how often they occur in data of interest, and if such data tend to have symmetric regularities, the search target exists (Corollary 8.1) and finding it is a genuine discovery. The theorem changes what a search should report. It should not report “the structure of x”. It should report how much of the structure of x is symmetric: the best model found, with its deficiency C(p,B)+log|B|−C(x)C(p,B)+ |B|-C(x), where C(x)C(x) is estimated by a compressor. A deficiency near the ceiling of Theorem 7.1 means that x looks random to linear symmetry. Four practical consequences follow. (a) Pair symmetric search with strong-model search. Blind strings can be normal, so a search over all simple partitions can succeed where the symmetric search fails. The difference between the two results estimates sophGL(x)−soph(x)soph^GL(x)-soph(x). (b) Search types first. For GL(n,2)GL(n,2), enumerate small types (H,b)(H,b) and only then optimise placements within each type. (c) Refine by restriction and meets. Mackey splitting and meets are the natural moves for halving the cell of x (Question 7.2). (d) Treat stalls as possibly genuine. If hxGLh^GL_x violates the halving law, a search that stalls at some cell size may have reached a real plateau of hxGLh^GL_x, not a local optimum of the algorithm. Strangeness is rare, since strange strings are non-stochastic and non-stochastic strings have small a priori probability [12]. Blindness to symmetry is plausibly common among stochastic strings, because a symmetric family has only 2poly(n)2^poly(n) cells. So in practice the gap between symmetric and arbitrary models, not the gap between strong and arbitrary ones, is the dominant limitation. 10 Open problems (1) Halving as refinement. Resolve Question 7.2: does ParGLPar_GL admit cheap refinements of every cell, for instance by meets with cheap hypotheses, or by restriction moves whose Mackey decomposition halves the cell of x (Section 9)? (2) Navigation. Use the coordinates (b,σ)(b,σ) and the moves of restriction and relabelling to search the space of symmetric partitions for good models of a given string. Which moves are cheap, and how does the structure function change along them? Later papers in the series take this up with reinforcement learning (Section 1.4). (3) Rigidity. Question 10.1. Is there a string x for which hxGLh^GL_x and hx,εstrh^str_x, are both small at some level, yet hx,εGLh^GL_x, is large there? Such an x would have a good linearly homogeneous model and a good strong model, but no cheap symmetric partition, a separation caused by the rigidity of ParGLPar_GL rather than by computability. A related question comes from the remark after Corollary 4.3: is the canonical hypothesis pBp_B of a homogeneous set B always within O(logn)O( n) bits of the cheapest symmetric partition having B as a cell? (4) Type-dominated explanations. Charge the type and the placement separately, and define structure functions in which the placement cost is bounded. Which strings have sufficient symmetric explanations whose information lies mainly in the type? For SymSym, Proposition 9.4 shows that arbitrary models need placement. For GL(n,2)GL(n,2), how do the at most n2n^2 bits of placement trade against the type in optimal models? (5) Counting symmetric partitions. Bound the number of p∈ParGLp _GL with C(p)≤εC(p)≤ and given cell sizes, using types (Burnside and Green rings) and placements, and count the homogeneous sets GLA_GL by size. This would sharpen Theorem 8.2, whose counting ranges over all subgroups. (6) Realizability. Which pairs (hx,hxGL)(h_x,h^GL_x) occur? Conjecture: every pair (P,Q)(P,Q) with P admissible, Q non-increasing, P≤Q≤n−αP≤ Q≤ n-α and Q vanishing where P does, up to o(n)o(n); in particular every value of sophGL(x)soph^GL(x) between soph(x)soph(x) and C(x)C(x). (7) Explicit extremal strings. Find explicit stochastic strings with sophGL(x)≈C(x)soph^GL(x)≈ C(x). Candidates are (y,f(y))(y,f(y)) for simple f whose graph has neither large Walsh coefficients nor large linear symmetry groups. (8) Canonicity and heredity. Is a sufficient cell of a cheap symmetric partition canonical, in the sense of Vereshchagin’s theorem for strong minimal sufficient statistics [11]? Is the code of an optimal symmetric model of a string with hxGL≈hxh^GL_x≈ h_x again of this kind, as for normal strings [7]? (9) Other ambient groups. Develop the lattices ParGPar_G for the affine group AGL(n,2)AGL(n,2), for coordinate permutations SnS_n, and for groups of polynomial automorphisms, and determine which regularities each sees. References [1] R. Banerjee. CAS I: A geometric coding theorem. arXiv:2607.13796, 2026. [2] P. Gács, J. Tromp and P. M. B. Vitányi. Algorithmic statistics. IEEE Transactions on Information Theory, 47(6):2443–2463, 2001. [3] A. Kerber. Applied Finite Group Actions. Springer, 2nd edition, 1999. [4] A. N. Kolmogorov. Talk at the Information Theory Symposium, Tallinn, 1974. [5] M. Koppel. Complexity, depth, and sophistication. Complex Systems, 1, 1987. [6] A. Milovanov. Some properties of antistochastic strings. In Computer Science – Theory and Applications (CSR 2015), LNCS 9139. Springer, 2015. [7] A. Milovanov. Algorithmic statistics: normal objects and universal models. In Computer Science – Theory and Applications (CSR 2016), LNCS 9691. Springer, 2016. arXiv:1512.04510. [8] M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005. [9] A. Shen, V. A. Uspensky and N. Vereshchagin. Kolmogorov Complexity and Algorithmic Randomness. American Mathematical Society, 2017. [10] R. A. Trejo, V. Kreinovich and L. Longpré. Choosing a physical model: why symmetries? Bulletin of the EATCS, 70:159–161, 2000. [11] N. Vereshchagin. Algorithmic minimal sufficient statistics: a new approach. Theory of Computing Systems, 56(2), 2015. [12] N. Vereshchagin and A. Shen. Algorithmic statistics: forty years later. arXiv:1607.08077, 2016. [13] N. K. Vereshchagin and P. M. B. Vitányi. Kolmogorov’s structure functions and model selection. IEEE Transactions on Information Theory, 50(12):3265–3290, 2004. [14] N. K. Vereshchagin and P. M. B. Vitányi. Rate distortion and denoising of individual data using Kolmogorov complexity. IEEE Transactions on Information Theory, 56(7):3438–3454, 2010.