1 Introduction

1.1 Models, strong models and partitions

Kolmogorov proposed to explain a string \(x\) by a finite set \(S\ni x\), a model, and to measure the explanation by the two-part code \(C(x)\lesssim C(S)+\log|S|\): first the model, then the position of \(x\) in it, which is treated as noise [4, 2, 13, 12]. The structure function \(h_x(\alpha)\) records the smallest model affordable at complexity \(\alpha\), and a model is a sufficient statistic when the two parts together cost no more than \(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'\mapsto 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,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 \[\tag{1.1} C(x)\ \lesssim\ \underbrace{C(p)}_{\text{hypothesis}} \ +\ \underbrace{C(B\mid p)}_{\text{which cell}} \ +\ \underbrace{\log|B|}_{\text{noise}}, \qquad x\in B\in p .\]

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\cdot x|=\log|U|-\log|\mathrm{stab}_U(x)|=-\log\Pr_{u\in 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 \(\mathrm{Par}_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=\mathrm{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\}\) as a cell: a lossless description that costs \(C(x)\). The informative cases lie in between and arise from structured ambient groups, above all the group \(\mathrm{GL}(n,2)\) of linear symmetries of \(\mathbb{F}_2^n\).

1.3 The question and the results

\(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 \(h^G_x\) over \(\mathrm{Par}_G\), and summarise it by the symmetric sophistication \(\mathrm{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(2^{n/2})\) bits of their information sit in the placement.

3. Linear symmetry (Section 6). The cells of \(\mathrm{Par}_{\mathrm{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)-\alpha\le h^{\mathrm{GL}}_x(\alpha)\le n-\alpha\), both edges are attained, and there are stochastic normal strings with \(\mathrm{soph}(x)\approx0\) but \(\mathrm{soph}^{\mathrm{GL}}(x)\approx 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 \(S_X\) the information of a hypothesis sits almost entirely in its placement, whereas a linear hypothesis is determined by its type up to \(n^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 \(3\)- and \(4\)-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)\) of the model found, with \(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 \(\mathit{CT}(y\mid 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(\log n)\)” hold up to additive \(O(\log n)\) terms in all coordinates; \(c\) denotes a sufficiently large constant.

Figure 1 shows a typical structure function. The curve starts near \(n\), where the only affordable model is essentially \(\{0,1\}^n\), and reaches \(0\) at \(\alpha\approx C(x)\), where \(\{x\}\) is affordable. It never lies below the sufficiency line \(C(x)-\alpha\) (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 \(\mathrm{soph}(x)\), and follows the line from there on. The region above the curve is the profile \(P_x\) of all pairs \((\alpha,\log|S|)\) achieved by models \(S\ni x\). For a stochastic string the curve drops to the sufficiency line almost at once; for an antistochastic string it follows \(n-\alpha\) until \(\alpha\approx C(x)\).

2.2 Strong models and partitions

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.

2.3 Restricted model classes

For a family \(\mathcal{A}\) of finite sets, the restricted structure function \(h^{\mathcal{A}}_x(\alpha)=\min\{\log|A| : x\in A\in\mathcal{A},\ C(A)\le\alpha\}\) uses only models from \(\mathcal{A}\), and \(\mathrm{soph}^{\mathcal{A}}(x)\) is defined from it as \(\mathrm{soph}(x)\) is from \(h_x\). The family is acceptable [14] (see also [7, 9]) if it is enumerable, contains every \(\{0,1\}^n\), and satisfies the covering condition: for a fixed polynomial \(\rho\), every \(A\in\mathcal{A}\) and every \(c<|A|\), the \(n\)-bit strings of \(A\) are covered by at most \(\rho(n)|A|/c\) members of \(\mathcal{A}\) of size at most \(c\).

3 The Galois connection

3.1 Symmetric partitions

Fix an ambient finite group \(G\) acting on a finite set \(X\), with \(G=G_n\) computable from \(n\) when \(X=\{0,1\}^n\). Let \(L(G)\) be the subgroup lattice and \(\mathrm{Par}(X)\) the partition lattice, ordered by refinement (\(p\le q\) if every cell of \(p\) lies in a cell of \(q\)). Put \[\mathrm{orb}_G(U)=\{\text{orbits of }U\},\qquad \mathrm{stab}_G(p)=\{g\in G : g(B)=B\text{ for every cell }B\in p\}.\]

The closed subgroup \(\mathrm{stab}_G(p)\) is the largest subgroup with orbit partition \(p\): the canonical certificate of the hypothesis \(p\).

3.2 Canonical cost

\(C(p)\) is the complexity of a partition \(p\) of \(\{0,1\}^n\) as a finite object, \(C(p,B)\) that of \(p\) with one of its cells, and \(C(U)\) the complexity of a generator list of \(U\).

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 \(G_{\{S\}}=\{g\in G: g(S)=S\}\) for the setwise stabiliser of \(S\subseteq X\).

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.

3.4 The algebra of hypotheses

Since \(\mathrm{orb}_G\) is a lower adjoint it preserves joins, and \(\mathrm{stab}_G\) as an upper adjoint preserves meets: \[\mathrm{orb}_G(\langle U,V\rangle)=\mathrm{orb}_G(U)\vee\mathrm{orb}_G(V),\qquad \mathrm{stab}_G(p\wedge q)=\mathrm{stab}_G(p)\cap\mathrm{stab}_G(q).\] So \(\mathrm{Par}_G\) is closed under joins in \(\mathrm{Par}(X)\): the join of two hypotheses is the hypothesis of all their symmetries together, and is coarser. The meet in \(\mathrm{Par}_G\) is \(p\wedge_G q=\mathrm{orb}_G(\mathrm{stab}_G p\cap\mathrm{stab}_G q)\le p\wedge q\), the hypothesis of their common symmetries, which is finer. Both are computable, so \(C(p\vee q),C(p\wedge_G q)\le C(p)+C(q)+O(\log n)\). The cell of \(x\) in \(p\wedge_G q\) 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)\) and by translation on \(\mathrm{Par}_G\), and the two maps are equivariant: \[\mathrm{orb}_G(gUg^{-1})=g\cdot\mathrm{orb}_G(U),\qquad \mathrm{stab}_G(g\cdot p)=g\,\mathrm{stab}_G(p)\,g^{-1}.\] The model \((g\cdot p,gB)\) for \(gx\) is the model \((p,B)\) for \(x\) in new coordinates, and costs at most \(C(g)+O(1)\) more.

4 Partition structure functions

The strong version does not reduce to cells in the same way. The canonical hypothesis satisfies \(C(p_B)\le C(B)+O(1)\), but this can exceed the cost of the cheapest symmetric partition containing \(B\) by up to \(C(B\mid p)\le\log|p|\le n\) bits. So \(h^G_{x,\varepsilon}\) depends on which cheap partitions carry \(B\), not only on \(B\) (compare Question 10.1).

Groups and partitions.

The group formulation defines \(h^{L(G)}_x(\alpha)\) as the least \(\log|U\cdot x|\) over subgroups \(U\le G\) with \(C(U,U\cdot x)\le\alpha\), and \(h^{L(G)}_{x,\varepsilon}\) by adding \(C(U)\le\varepsilon\).

5 All permutations

Let \(\mathrm{Sym}\) denote the ambient group \(\mathrm{Sym}(\{0,1\}^n)\), written \(S_X\) with \(X=\{0,1\}^n\) in Section 9. By Example 3.2(a), \(\mathrm{Par}_{\mathrm{Sym}}\) is the lattice of all partitions, and by Example 3.6(a) every non-empty set is a cell.

Theorem 5.1 says that unrestricted symmetry explains everything. As a statement about symmetry this is nearly vacuous. The canonical certificates in \(S_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 \(2^{n/2}\) has all but \(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 \(S_X\) can hide a genuinely structured symmetry (Example 9.5).

6 Linear symmetry

Identify \(\{0,1\}^n\) with \(\mathbb{F}_2^n\) and take \(G=\mathrm{GL}(n,2)\). Linear maps fix \(0\), so throughout \(x\ne0\).

6.1 Cells: linearly homogeneous sets

Which sets can be cells of linear-symmetric partitions? A linear map preserves all \(\mathbb{F}_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\subseteq\mathbb{F}_2^n\setminus\{0\}\) is a subset \(T\subseteq S\) with \(\sum T=0\), an XOR dependency among elements of \(S\). For example, in \(S=\{e_1,e_2,e_1+e_2\}\) the whole set is a relation, since \(e_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 \(\pi\) of \(S\) preserves relations if \(\sum T=0\iff\sum\pi(T)=0\) for all \(T\subseteq S\), i.e. if it is an automorphism of the dependency structure.

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\setminus\{0\}\) has as many relations as possible, but \(\mathrm{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.

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.

Why this matters.

By Corollary 4.3 and Theorem 6.3, \(h^{\mathrm{GL}}_x\) is Vereshchagin and Vitányi’s structure function for the concrete model class \(\mathcal{A}_{\mathrm{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 \(h^{\mathrm{GL}}_x\) and \(h_x\) comes from which sets are admissible. Under \(\mathrm{Sym}(\{0,1\}^n)\) every set qualifies (Theorem 5.1). Under \(\mathrm{GL}(n,2)\) only homogeneous sets do, and there are at most \(2^{n^4+n}\) of them against \(2^{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 \(\mathcal{A}_{\mathrm{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 \(h^{\mathrm{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 \(h^{\mathrm{GL}}_{x,\varepsilon}\), 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 \(\mathrm{GL}(n,2)\) is determined by its type, an abstract group with a faithful module, up to \(n^2\) bits (Proposition 9.6).

6.2 Affine hypotheses

Every affine subspace is a cell of a cheap symmetric partition. For \(W\setminus\{0\}\) this is Example 3.2(c). For \(a+W\) with \(a\notin W\), fix a complement \(D\) of \(W\oplus\langle a\rangle\), and for \(w\in W\) let \(\tau_w\) fix \(W\oplus D\) pointwise and send \(a\mapsto a+w\). The group \(\{\tau_w\}\cong W\) has cells \(\{v\}\) for \(v\in W\oplus D\) and \(a+d+W\) for \(d\in D\), at cost \(C(W,a)+O(1)\). Writing \(h^{\mathrm{aff}}_x\) for the structure function over affine subspaces, we get, up to \(O(\log n)\), \[\tag{6.1} h_x\ \le\ h^{\mathrm{GL}}_x\ \le\ h^{\mathrm{aff}}_x,\qquad h_x\ \le\ h^{\mathrm{str}}_{x,\varepsilon}\ \le\ h^{\mathrm{GL}}_{x,\varepsilon}.\]

7 The band

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 \(\kappa=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 \(\kappa-\alpha\), and the upper one is the ceiling \(n-\alpha\). By Lemma 2.2(i) and Theorem 7.1(i), every curve in the figure lies between them for \(c\log n\le\alpha\le\kappa\), up to \(O(\log 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)\) shifts, \[h_x\le h^{\mathrm{str}}_{x,\varepsilon}\le h^{\mathrm{GL}}_{x,\varepsilon},\qquad h_x\le h^{\mathrm{GL}}_x\le h^{\mathrm{GL}}_{x,\varepsilon}.\] 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\},\mathbb{F}_2^n\setminus\{0\}\}\) cost \(O(\log n)\). At \(\alpha\approx\kappa\) every curve vanishes, since the discrete partition is cheap and its cell \(\{x\}\) costs \(\kappa\). All differences between the curves occur for \(c\log n\le\alpha\le\kappa\).

4. Kolmogorov’s curve \(h_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 \(\mathrm{soph}(x)\). From there it follows the sufficiency line down to \(\alpha=\kappa\).

5. The unrestricted symmetric curve \(h^{\mathrm{Sym}}_x\) (red dots) lies on \(h_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 \(\mathrm{Sym}(\{0,1\}^n)\), at no extra cost. In particular \(\mathrm{soph}^{\mathrm{Sym}}(x)=\mathrm{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 \(h^{\mathrm{str}}_{x,\varepsilon}\) (green dashes) also lies on \(h_x\). This is the definition of normality: every point of the profile is attained by an \(\varepsilon\)-strong model, up to \(\delta\). By Theorem 5.1 the same curve is the cheap unrestricted symmetric curve \(h^{\mathrm{Sym}}_{x,\varepsilon}\). For a strange string it would separate from \(h_x\) and lie above it, while \(h^{\mathrm{Sym}}_x\) would still lie on \(h_x\).

7. The linear-symmetry curve \(h^{\mathrm{GL}}_x\) (solid violet) uses cells of symmetric partitions of \(\mathrm{GL}(n,2)\) of any cost, that is, linearly homogeneous sets (Theorem 6.3). In the figure it follows the ceiling up to \(\alpha\approx\kappa/2\): at those budgets no linear symmetry sees any structure of \(x\). It then drops, decreases along a segment of slope \(-1\), drops again, and first meets the sufficiency line at the violet dot, whose complexity is the symmetric sophistication \(\mathrm{soph}^{\mathrm{GL}}(x)\). By Theorem 7.1(iii), \(\mathrm{soph}(x)\le\mathrm{soph}^{\mathrm{GL}}(x)\le\kappa\).

8. The symmetry gap (shaded) is the region between \(h_x\) and \(h^{\mathrm{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, \(\mathrm{soph}^{\mathrm{GL}}(x)-\mathrm{soph}(x)\), is the extra budget symmetric explanations need before they become sufficient. By Corollary 8.1 the region can be empty, with \(h^{\mathrm{GL}}_x=h_x\). By Theorem 8.2 it can fill the whole band, with \(h^{\mathrm{GL}}_x\) on the ceiling up to \(\alpha\approx\kappa\), even for stochastic normal strings.

9. The cheap linear-symmetry curve \(h^{\mathrm{GL}}_{x,\varepsilon}\) (orange dashes) uses only cells of symmetric partitions of complexity at most \(\varepsilon\). In the figure it agrees with \(h^{\mathrm{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 \(\alpha=\kappa\). Because \(x\) is normal, this separation from \(h^{\mathrm{GL}}_x\) is caused by symmetry, not by strangeness.

10. The marked points. On the horizontal axis: \(\mathrm{soph}(x)\), equal to \(\mathrm{soph}^{\mathrm{Sym}}(x)\), where \(h_x\) and \(h^{\mathrm{Sym}}_x\) become sufficient; \(\mathrm{soph}^{\mathrm{GL}}(x)\), where \(h^{\mathrm{GL}}_x\) becomes sufficient; and \(\kappa\), where all curves vanish. On the vertical axis: \(n\), where all curves start, and \(\kappa\), 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 \(h^{\mathrm{GL}}_x\) and \(h^{\mathrm{GL}}_{x,\varepsilon}\) are illustrative. Which shape is typical is open, and so is whether the rigidity separation in (9) occurs at all. Whether the \(\mathrm{GL}\) curves obey the halving law (Question 7.2) is also open. If they do not, they may have plateaus, which \(h_x\) never has.

Halving as refinement.

Affine subspaces form an acceptable class: a coset of dimension \(d\) splits into at most \(2|A|/c\) cosets of size at most \(c\). By Theorem 2.5, \(h^{\mathrm{aff}}_x\) obeys the halving law. For \(h^{\mathrm{GL}}_x\) the question becomes one about the lattice \(\mathrm{Par}_{\mathrm{GL}}\). Given a symmetric \(p\) with \(x\in B\in p\), is there a cheap symmetric refinement whose cell containing \(x\) has size about \(|B|/2\)? The algebra of Section 3 suggests meeting \(p\) with a second cheap hypothesis \(q\): the cell of \(x\) in \(p\wedge_{\mathrm{GL}}q\) lies in the intersection of its cells. Transitivity alone does not obstruct this. \(\mathrm{GL}(n,2)\) is \(2\)-transitive on nonzero vectors, so no subgroup between \(\mathrm{stab}(x)\) and \(\mathrm{GL}(n,2)\) refines the orbit of \(x\), but subgroups not containing \(\mathrm{stab}(x)\) can. Since linear maps fix \(0\), homogeneous sets other than \(\{0\}\) avoid \(0\), so \(\mathcal{A}_{\mathrm{GL}}\) contains \(\mathbb{F}_2^n\setminus\{0\}\) rather than the whole space required in the definition of acceptability; this changes nothing up to \(O(1)\).

8 The extremes of the band

8.1 Zero gap: symmetry explains everything

8.2 Maximal gap: structure invisible to symmetry

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\); in our setting \(X=\{0,1\}^n\) and \(N=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\le S_X\) is the image of a faithful action \(\rho\colon H\to S_X\) of an abstract group \(H\cong U\). Up to isomorphism of \(H\)-sets, the action is determined by its class in the Burnside ring \(B(H)\). Fix representatives \(K_1,\dots,K_r\) of the conjugacy classes of subgroups of \(H\). Then \[[X]_\rho=\sum_{i=1}^r a_i\,[H/K_i],\qquad a_i\ge0,\qquad \deg[X]_\rho:=\sum_i a_i\,|H:K_i|=N .\] The action is faithful iff \(\bigcap_{a_i>0}\mathrm{core}_H(K_i)=1\), where \(\mathrm{core}_H(K)=\bigcap_{h}hKh^{-1}\) is the kernel of \(H\) on \(H/K\). By Burnside’s theorem, \(b\in B(H)\) is determined by its marks \(\varphi_K(b)=|X_b^K|\), the number of points fixed by \(K\).

Partitions and cells in coordinates.

The orbits of \(U_b\) are the summands of \(X_b\), which are consecutive intervals of \(X\). Let \(\lambda(b)\) be the integer partition of \(N\) with part \(|H:K_i|\) repeated \(a_i\) times, and \(p_{\lambda(b)}\) the corresponding partition of \(X\) into consecutive intervals. Then \[\mathrm{orb}\big(\Phi_H(b,\sigma)\big)=\sigma\cdot p_{\lambda(b)} .\] So partitions have coordinates \((\lambda,\sigma)\), with \(\sigma\) defined modulo the stabiliser of \(p_\lambda\) in \(S_X\). The projection \((b,\sigma)\mapsto(\lambda(b),\sigma)\) is \(\mathrm{orb}\) written in coordinates: it forgets the structure of \(b\) beyond its cell sizes. If \(\sigma^{-1}(x)\) lies in a summand of type \(H/K_i\), then the cell of \(x\) has size \(|H:K_i|\), its stabiliser is conjugate to \(K_i\), and \[\Pr_{u\in U}[ux=x]=\frac{|K_i|}{|H|} .\] The marks \(\varphi_K(b)\) give the whole distribution of cell sizes and fixed points over \(X\); Proposition 4.5 is the pointwise case.

Navigation.

Two basic moves act on coordinates.

• Relabelling: \((b,\sigma)\mapsto(b,\pi\sigma)\) conjugates the group by \(\pi\) and translates its partition, at cost at most \(C(\pi)\).

• Restriction to a subgroup \(L\le H\): the subgroup \(\sigma\rho_b(L)\sigma^{-1}\) has coordinates \((\mathrm{Res}^H_L b,\ \sigma\tau)\) in \(\mathcal S_L(X)\), where \(\tau\) is computable from \((H,L,b)\). Its partition refines that of \(U\) cell by cell, according to the Mackey formula \[\mathrm{Res}^H_L\,[H/K]=\sum_{LhK\in L\backslash H/K} \big[L/(L\cap hKh^{-1})\big],\] so a cell of size \(|H:K|\) splits into cells of sizes \(|L:L\cap 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\le H\) whose Mackey decomposition splits the cell of \(x\) roughly in half.

9.2 Types and placements: \(S_X\) versus \(\mathrm{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.

So every symmetric realisation of a model in \(S_X\) has a type that records only cell sizes. Such a type carries at most \(O(2^{n/2})\) bits, and only in the numbers \(|B|\), which is a numerical encoding rather than a symmetry. For a model of complexity much larger than \(2^{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 \(S_X\) never provide one.

Contrast Proposition 9.4: in \(S_X\) the placement can carry almost all of the information, whereas in \(\mathrm{GL}(n,2)\) it carries at most \(n^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=3\).

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)\) 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)\) is a good model. No search strategy over \(\mathrm{Par}_{\mathrm{GL}}\), however it navigates the coordinates, can find one, because none exists. Conversely, a model found by search only gives an upper bound on \(h^{\mathrm{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 \(S_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 \(2^{n/2}\) the search takes place almost entirely among placements, under every realisation. The homogeneous spaces \(S_X/N_{S_X}(U_b)\) can have size close to \((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 \(\mathrm{GL}(n,2)\), the placement costs at most \(n^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 \(2^{n^2}\) placements: altogether \(2^{\mathrm{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 \(2^{\mathrm{poly}(n)}\) decidable cells is blind to some stochastic normal strings. The same holds for \(\mathrm{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 \(S_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)\), where \(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.

1. 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 \(\mathrm{soph}^{\mathrm{GL}}(x)-\mathrm{soph}(x)\).

2. Search types first. For \(\mathrm{GL}(n,2)\), enumerate small types \((H,b)\) and only then optimise placements within each type.

3. Refine by restriction and meets. Mackey splitting and meets are the natural moves for halving the cell of \(x\) (Question 7.2).

4. Treat stalls as possibly genuine. If \(h^{\mathrm{GL}}_x\) violates the halving law, a search that stalls at some cell size may have reached a real plateau of \(h^{\mathrm{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 \(2^{\mathrm{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 \(\mathrm{Par}_{\mathrm{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,\sigma)\) 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 \(h^{\mathrm{GL}}_x\) and \(h^{\mathrm{str}}_{x,\varepsilon}\) are both small at some level, yet \(h^{\mathrm{GL}}_{x,\varepsilon}\) 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 \(\mathrm{Par}_{\mathrm{GL}}\) rather than by computability.

   A related question comes from the remark after Corollary 4.3: is the canonical hypothesis \(p_B\) of a homogeneous set \(B\) always within \(O(\log 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 \(\mathrm{Sym}\), Proposition 9.4 shows that arbitrary models need placement. For \(\mathrm{GL}(n,2)\), how do the at most \(n^2\) bits of placement trade against the type in optimal models?

5. Counting symmetric partitions. Bound the number of \(p\in\mathrm{Par}_{\mathrm{GL}}\) with \(C(p)\le\varepsilon\) and given cell sizes, using types (Burnside and Green rings) and placements, and count the homogeneous sets \(\mathcal{A}_{\mathrm{GL}}\) by size. This would sharpen Theorem 8.2, whose counting ranges over all subgroups.

6. Realizability. Which pairs \((h_x,h^{\mathrm{GL}}_x)\) occur? Conjecture: every pair \((P,Q)\) with \(P\) admissible, \(Q\) non-increasing, \(P\le Q\le n-\alpha\) and \(Q\) vanishing where \(P\) does, up to \(o(n)\); in particular every value of \(\mathrm{soph}^{\mathrm{GL}}(x)\) between \(\mathrm{soph}(x)\) and \(C(x)\).

7. Explicit extremal strings. Find explicit stochastic strings with \(\mathrm{soph}^{\mathrm{GL}}(x)\approx C(x)\). Candidates are \((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 \(h^{\mathrm{GL}}_x\approx h_x\) again of this kind, as for normal strings [7]?

9. Other ambient groups. Develop the lattices \(\mathrm{Par}_G\) for the affine group \(\mathrm{AGL}(n,2)\), for coordinate permutations \(S_n\), and for groups of polynomial automorphisms, and determine which regularities each sees.