Paper deep dive
CAS II: Symmetric Partitions as Kolmogorov Models
Romie Banerjee
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
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. Vereshchagin's strong models, those computable from the data by a total algorithm, are essentially the cells of simple partitions. We read a partition of binary strings as a hypothesis, with the cell containing x as its model, and 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 a lattice of symmetric partitions, with canonical certificates, canonical costs, and an algebra of hypotheses. The resulting structure function and symmetric sophistication measure which part of the regularity of x is symmetric. For the full symmetric group every partition is symmetric: cells recover all Kolmogorov models, cells of cheap partitions recover exactly the strong models, and normal and strange strings are characterized by symmetry. For GL(n,2) the cells are exactly the linearly homogeneous sets, so linear symmetry is a restricted model class. For nonzero x, the linear-symmetry structure function lies in a band between the sufficiency line and the trivial bound, and both edges are attained: there are stochastic normal strings whose simple structure is invisible to linear symmetry. We also give coordinates on 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 via the Mackey formula. In these coordinates the collapse for the symmetric group is a statement about placement, a linear hypothesis is determined by its type up to n^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.
Tags
Links
- Source: https://arxiv.org/abs/2609.40290v1
- Canonical: https://arxiv.org/abs/2609.40290v1
Trouble viewing inline? Open PDF directly →
Full Text
62,147 characters extracted from source content.
Expand or collapse full text
CAS I: Symmetric Partitions as Kolmogorov Models Romie Banerjee September 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. The resulting structure function hxGh^G_x and 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 cells are exactly the linearly homogeneous sets, which turns linear symmetry into a restricted model class. 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 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. 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 [3, 1, 11, 10]. 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 [1] can be sufficient, yet they encode the number of strings of bounded complexity, so they cannot be found from the data. Vereshchagin [9] 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 [6] 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 [2] 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. 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 certificates turn out to be structurally trivial symmetries placed in complicated ways (Section 5). 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, an algebra of joins and meets, and relabelling. Partition structure functions 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 certificates realising arbitrary models have trivial type: all their information sits in the placement. (3) Linear symmetry (Section 6). The cells of ParGLPar_GL are the linearly homogeneous sets, but whole symmetric partitions are rigid. A linear hypothesis is determined by its type up to n2n^2 bits. (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. A figure 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. 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. 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 [4, 1, 11]. 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) [5]. Lemma 2.2 ([11, 8]). 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 [11], 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 [11]). 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 ([9, 6]). 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 [1], which carry the information of the number of strings of bounded complexity [9]. Strange strings exist [9]; normal strings exist for every admissible shape [6]; antistochastic strings are normal [6]. The following lemma is the bridge to partitions. Lemma 2.4 (Partition lemma [6]). 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 p be a total program with p(x)=Ap(x)=A and |p|≤ε|p|≤ . Group the strings x′x with x′∈p(x′)x ∈ p(x ) according to the value p(x′)p(x ), and put every other string in a singleton cell. This partition is computable from p and n, and the cell of x is A1=x′∈A:p(x′)=AA_1=\x ∈ A:p(x )=A\, computable from A, p and n. ∎ 2.3 Restricted model classes A family A of finite sets is acceptable [12] (see also [6, 8]) if it is enumerable, contains every 0,1n\0,1\^n, and satisfies the covering condition: for a fixed polynomial p, every A∈A and every c<|A|c<|A|, the n-bit strings of A are covered by at most p(n)|A|/cp(n)|A|/c members of A of size at most c. Theorem 2.5 ([12]). 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 ([2]). 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 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 halving discussion in Section 7). 3.4 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)orb_G(gUg^-1)=g·orb_G(U) and stabG(g⋅p)=gstabG(p)g−1stab_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. ∎ 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.3 (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.4 (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). By Example 3.2(a), ParSymPar_Sym is the lattice of all partitions. 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. For S∋xS x, the partition S∪singletons\S\∪\singletons\ 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 [9], and every admissible shape is realised by a string whose cheap-symmetry structure function equals its Kolmogorov structure function [6]. Theorem 5.1 says that unrestricted symmetry explains everything. As a statement about symmetry this is vacuous: in the coordinates of Section 9, the certificates realising arbitrary sets are structurally trivial symmetries whose information lies entirely in their placement (Proposition 9.4). 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. 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. S⊆2n∖0S _2^n \0\ is a cell of some partition in ParGLPar_GL if and only if it is linearly homogeneous. Moreover such a cell is a cell of a symmetric partition of complexity C(S)+O(1)C(S)+O(1), so hxGLh^GL_x is Kolmogorov’s structure function restricted to linearly homogeneous sets. Proof. If U⋅x=SU· x=S, every u∈Uu∈ U restricts to a relation-preserving bijection of S, and these act transitively. 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. Extend it by the identity on a canonical complement. The resulting group is computable from S, its orbit through x is S, and its orbit partition costs C(S)+O(1)C(S)+O(1). ∎ Why this matters: linear symmetry as a restricted model class. Theorem 6.3 places the linear theory inside the general theory of restricted model classes of Section 2.3. (1) The groups disappear. hxGLh^GL_x is defined by ranging over subgroups of GL(n,2)GL(n,2) and their orbits. The theorem identifies it with hxh^A_x for the concrete, combinatorially defined family GLA_GL of linearly homogeneous sets. Questions about linear symmetry become questions about a family of sets, and the tools of Vereshchagin–Vitányi [12] apply directly. (2) The restriction costs nothing extra. A homogeneous set comes with a certificate computable from it, so the symmetry hypothesis costs no more than the set itself. Every difference between hxGLh^GL_x and hxh_x is therefore caused by which sets are admissible, not by any overhead of describing groups. This is a different kind of restriction from strong models, where the models are ordinary sets but must be computable from the data. (3) It explains why linear symmetry does not collapse. For Sym(0,1n)Sym(\0,1\^n) every set is a cell, and symmetric models are all models (Theorem 5.1). For GL(n,2)GL(n,2) only homogeneous sets qualify. A string whose good models all have inhomogeneous dependency structure cannot be explained well by linear symmetry. This is the gap measured by the band (Section 7) and realised at its maximum by Theorem 8.2. (4) The class is small. There are at most 2n4+n2^n^4+n homogeneous subsets of 2nF_2^n, since each is an orbit of one of at most 2n42^n^4 subgroups. Arbitrary sets number 22n2^2^n. This size difference is what the counting proof of Theorem 8.2 exploits. (5) The class is not closed under halving. Half of a homogeneous set is usually not homogeneous, since the two halves need not look alike internally. So the covering condition of acceptability, automatic for all sets and easy for affine subspaces, is a genuine question for GLA_GL. This is why the halving law for hxGLh^GL_x is open (Question 7.2). (6) Membership is a finite test. Deciding whether a proposed set is a legitimate linear-symmetry model requires no search over groups: one checks that its dependency structure is point-transitive. Since linear maps fix 00, homogeneous sets avoid 00, and 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). 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.5). 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 2: The band containing hxGLh^GL_x (Theorem 7.1); both edges are attained. All the structure functions together. Figure 3 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 [10]. 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 uninformative about symmetry, since by Proposition 9.4 the certificates realising arbitrary models have trivial type. (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 3: 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. Question 7.2. Is the family of cells of ParGLPar_GL acceptable, i.e. can every cell of size N be covered by poly(n)N/cpoly(n)\,N/c cells of size at most c? Equivalently for the halving law: 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.5, 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 [7] 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.4 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 of Section 7 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.5). 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 US=Sym(S)×1U_S=Sym(S)× 1 be the Young subgroup of a set S⊆XS X with |S|=k≥2|S|=k≥ 2. In the coordinates of Theorem 9.2, its 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], and costs O(n)O(n), while its placement costs minC(σ∣H,b):ΦH(b,σ)=US=C(S)±O(n). \C(σ H,b): _H(b,σ)=U_S\\;=\;C(S)± O(n). Proof. S is the unique cell of size greater than one, so C(US)=C(S)±O(1)C(U_S)=C(S)± O(1). The type is described by k and n. Since C(US)≤n2n+O(1)C(U_S)≤ n2^n+O(1), the error term in Proposition 9.3 is O(n)O(n). ∎ So the explanations that realise arbitrary Kolmogorov models are structurally trivial symmetries placed in a complicated way. A symmetry explanation is informative only when its information lies in the type. The placement for SymSym can cost up to log(2n!)≈n2n (2^n!)≈ n2^n bits, and this is what makes the collapse possible. Proposition 9.5 (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)|<2n2|GL(n,2)|<2^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. 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 certificates that realise arbitrary models have trivial type, so the search would take place almost entirely among placements. 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.5). 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 [10]. 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? (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. (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. 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 [9]? 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 [6]? (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] P. Gács, J. Tromp and P. M. B. Vitányi. Algorithmic statistics. IEEE Transactions on Information Theory, 47(6):2443–2463, 2001. [2] A. Kerber. Applied Finite Group Actions. Springer, 2nd edition, 1999. [3] A. N. Kolmogorov. Talk at the Information Theory Symposium, Tallinn, 1974. [4] M. Koppel. Complexity, depth, and sophistication. Complex Systems, 1, 1987. [5] A. Milovanov. Some properties of antistochastic strings. In Computer Science – Theory and Applications (CSR 2015), LNCS 9139. Springer, 2015. [6] A. Milovanov. Algorithmic statistics: normal objects and universal models. In Computer Science – Theory and Applications (CSR 2016), LNCS 9691. Springer, 2016. arXiv:1512.04510. [7] M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005. [8] A. Shen, V. A. Uspensky and N. Vereshchagin. Kolmogorov Complexity and Algorithmic Randomness. American Mathematical Society, 2017. [9] N. Vereshchagin. Algorithmic minimal sufficient statistics: a new approach. Theory of Computing Systems, 56(2), 2015. [10] N. Vereshchagin and A. Shen. Algorithmic statistics: forty years later. arXiv:1607.08077, 2016. [11] 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. [12] 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.