Paper deep dive
CAS I: A Geometric Coding Theorem
Romie Banerjee
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/16/2026, 7:12:58 AM
Summary
This paper introduces a geometric analogue of the classical coding theorem within the framework of symmetry groups. It defines the symmetry prior as the probability that a randomly selected computable bijection uniquely fixes a binary string. The authors prove that for fix-retractable symmetry groups, this prior becomes a universal lower semi-computable semi-measure, satisfying the Geometric Coding Theorem which equates the negative logarithm of the symmetry prior to prefix Kolmogorov complexity. The work establishes a Galois connection between symmetry subgroups and binary string subsets, unifying algorithmic information theory with group theory under the Computational Algorithmic Statistics (CAS) framework.
Entities (7)
Relation Signals (5)
Geometric Coding Theorem → equates → Prefix Kolmogorov Complexity
confidence 95% · −log2mG(x)=K(x)+O(1) where K(x) is the prefix Kolmogorov complexity of x
Symmetry Prior → isdefinedon → Binary Strings
confidence 94% · symmetry prior of a string x as the probability that a randomly chosen symmetry from a given group has the string as its unique fixed point
Fix-retractable Symmetry Group → implies → Symmetry Prior is Universal
confidence 93% · for any fix-retractable symmetry group... the symmetry prior is a universal lower semi-computable semi-measure
Symmetry Prior → dominates → Solomonoff Prior
confidence 89% · The symmetry prior dominates the Solomonoff prior: ∃C s.t C.mGU(x)≥mU(x)
Galois Connection → connects → Subgroups of Symmetry Groups
confidence 88% · develop a Galois connection between subgroups of G and subsets of binary strings
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This paper establishes a direct analogue of the classical Coding Theorem in the setting of symmetry groups. We consider computable bijections on the set of binary strings, called symmetries and define the symmetry prior of a string as the probability that a randomly chosen symmetry from a given group has the string as its unique fixed point. We show that for any fix-retractable symmetry group, a group admitting a computable section that selects an isolating symmetry for every string, the symmetry prior is a universal lower semi-computable semi-measure. In this case, the Geometric Coding Theorem holds. We also develop a Galois connection between subgroups of G and subsets of binary strings, characterizing closed points and maximal closed subgroups, and explore the join-semilattice of dense subgroups. Our results unify algorithmic information theory with group theory and provide a framework for studying symmetry-induced complexity measures. This paper is the first in a series on Computational Algorithmic Statistics (CAS).
Tags
Links
- Source: https://arxiv.org/abs/2607.13796v1
- Canonical: https://arxiv.org/abs/2607.13796v1
Trouble viewing inline? Open PDF directly →
Full Text
31,441 characters extracted from source content.
Expand or collapse full text
CAS I: A Geometric Coding Theorem Romie Banerjee Abstract This paper establishes a direct analogue of the classical Coding Theorem in the setting of symmetry groups. We consider computable bijections on the set of binary strings—called symmetries—and define the symmetry prior of a string x as the probability that a randomly chosen symmetry from a given group G has x as its unique fixed point. We show that for any fix-retractable symmetry group G—a group admitting a computable section that selects an isolating symmetry for every string—the symmetry prior is a universal lower semi-computable semi-measure. In this case, the Geometric Coding Theorem holds: −log2mG(x)=K(x)+O(1)- _2m_G(x)=K(x)+O(1) where K(x)K(x) is the prefix Kolmogorov complexity of x. We also develop a Galois connection between subgroups of G and subsets of binary strings, characterizing closed points and maximal closed subgroups, and explore the join-semilattice of dense subgroups. Our results unify algorithmic information theory with group theory and provide a framework for studying symmetry-induced complexity measures. This paper is the first in a series on Computational Algorithmic Statistics (CAS). Keywords: Kolmogorov complexity, Solomonoff prior, algorithmic probability, coding theorem, symmetry groups, Galois connections 1 Introduction 1.1 Program-Size Complexity The concept of algorithmic complexity defined by Solomonoff, Kolmogorov, Chaitin and Levin is a measure that quantifies the algorithmic randomness of a binary string. Formally, the algorithmic complexity, denoted by K of a binary string x is the length of the shortest computer program p running on a universal Turing machine U that generates the string x as an output and halts [[1] Ch. 2]. KU(x)=minℓ(p)∣U(p)=xK_U(x)= \ (p) U(p)=x\ (1) The invariance theorem says that the definition of K above is independent of the choice of the universal Turing machine U. For a a different choice V, the K values differ by a constant term independent of x. The constant term comes from the cost of simulating U by V and vice-versa. The function K that takes in x and gives the length of the shortest program producing x is uncomputable. This is due to the halting problem, given that one cannot always find the shortest problem in finite time without having to run all programs. This means having to wait forever in case they never halt. The function K is however upper semi-computable, i.e. it can approximated from above by computable functions. This is because the set of computer programs that output x and halt is recursively enumerable. 1.2 Algorithmic Probability The ordinary probability of production of a binary string x among all possible 2n2^n strings of length n is given by P(x)=1/2nP(x)=1/2^n. The concept of algorithmic probability replaces the random production of outputs with the random production of programs that produce the output. The algorithmic probability (or Solomonoff prior or Levin’s semi-measure) m(x)m(x) of a binary string x is the sum over all prefix-free programs p for which a universal Turing prefix machine U running p outputs x and halts. The replaces the length of x with the length of the program p that produces x. It is thus a measure that estimates the probability of a random program p producing x when run on U. [[1] Ch. 3] mU(x)=∑p∣U(p)=x12ℓ(p)m^U(x)= _p U(p)=x 12 (p) (2) The algorithmic probability is independent of the choice of universal prefix machine (up to a constant term) and as a function from binary strings to ℝR is lower semi-computable. 1.3 Coding Theorem There is a direct and miraculous connection between the algorithmic complexity and algorithmic probability of binary strings. The negative logarithm of the algorithmic probability −log2mU(x)- _2m^U(x) gives a complexity measure. By this measure the complexity of a string is directly related to the frequency of production of the string in a universal prefix machine. More programs imply lower complexity. This is related to the algorithmic complexity as the shortest program producing x on U will contribute to the largest term contributing to mU(x)m^U(x). The inequality −log2mU(x)≤KU(x)- _2m^U(x)≤ K_U(x) is obvious. The algorithmic coding theorem says that something much stronger is true. Theorem 1.1 ([1] Thm.4.3.3 ). The algorithmic coding theorem, KU(x)=−log2mU(x)+O(1)K_U(x)=- _2m^U(x)+O(1) (3) The theorem establishes that, if there are many programs producing a string then there is also a short program producing the string ; and strings of lower frequency have higher Kolmogorov complexity. The key idea behind the proof comes down to the observation that if there are k prefix programs of length n producing x on U, then there is a prefix program of length n−log2k+O(1)n- _2k+O(1) that produces x on U. There is another way of state the coding theorem. The semi-measure on bit strings defined by P(x)=1/2K(x)P(x)=1/2^K(x) is a universal lower semi-computable semi-measure. 1.4 Geometric Coding Theorem A symmetry is a computable bijection of the set of binary strings. If a symmetry has a string x as its only fixed point, it can be framed as program that produces the string x and halts. Q: Do the frequency of symmetry programs producing x have a direct relationship with the Kolmogorov complexity of x in the same way the frequency of ordinary programs does (via the classical coding theorem)? Let the symmetry prior be the probailiy of producing a bit string by randomly selecting a symmetry program. The symmetry prior mGU(x)m^U_G(x) of a bit string x is the sum over all prefix-free programs symmetry programs p for which a universal Turing prefix machine UGU^G running p outputs x and halts. mGU(x)=∑p∣UG(p)=x12ℓ(p)m^U_G(x)= _p U^G(p)=x 12 (p) (4) In this paper we lay down a condition on the group of symmetries so that the coding theorem with the symmetry prior is true. Theorem 1.2. Let G be a group of computable bijections of 0,1∗\0,1\^* with following property: there exists a subgroup H≤GH≤ G which can isolate all bit strings and the symmetries H and isolating symmetries H I_H are recursively enumerable. Then the following (equivalent) statements are true: 1. KU(x)=−log2mGU(x)+O(1)K_U(x)=- _2m^U_G(x)+O(1). 2. The symmetry prior dominates the Solomonoff prior: ∃C∃ C s.t C.mGU(x)≥mU(x),∀x∈0,1∗C.m^U_G(x)≥ m^U(x),∀ x∈\0,1\^*. 3. The symmetry prior is a universal lower semi-computable semi-measure on finite bit strings 1.5 Results Dependencies ∃H≤G∣H,H r.e. ∃ H≤ G H, I_H r.e. Thm.2.7G fix-retractable 2.4 G fix-retractable def:fix-ret Thm.2.6UG simulates U2.5 U^G simulates U def:simul Thm.3.5Thm.3.3LSC LSCGCT1.2 GCT thm:gct (5) 2 Coding with symmetries 2.1 Symmetries The set of total recursive functions 0,1∗→0,1∗\0,1\^*→\0,1\^* is denoted by T. The group of total recursive bijective functions is denoted TB. Elements of TB are called symmetries. =f:0,1∗→0,1∗∣f(x) halts ∀x T=\f:\0,1\^*→\0,1\^* f(x) halts ∀ x\ (6) =f∈∣f is a bijection TB=\f∈ T f is a bijection\ (7) Given x∈0,1∗x∈\0,1\^*, the set of symmetries that fix x is a subgroup of TB denoted by (x) stab(x). (x)=f∈∣f(x)=x≤ stab(x)=\f∈ TB f(x)=x\≤ TB (8) A symmetry f∈(x)f∈ stab(x) isolates x when x is the only fixed point of x. The set of isolating symmetries for x is denoted by IxI_x. (x)=f∈∣f(x)=x and f(y)≠y,∀y∈0,1∗⊆(x) I(x)=\f∈ TB f(x)=x and f(y)≠ y,∀ y∈\0,1\^*\ stab(x) (9) Let I denote the set of all isolating symmetries in TB. =f∈∣|(f)|=1=∐x∈0,1∗(x) I=\f∈ TB | fix(f)|=1\= _x∈\0,1\^* I(x) (10) Let G≤G≤ TB be a subgroup of total bijections of 0,1∗\0,1\^*. Subgroups of TB will be called symmetry groups. Given x∈0,1∗x∈\0,1\^*, the elements of G that fix x, G(x)=g∈G∣g(x)=x≤G stab_G(x)=\g∈ G g(x)=x\≤ G (11) The set of isolating symmetries in G for x is denoted by G(x) I_G(x). (x)=g∈G∣g(x)=x and g(y)≠y,∀y∈0,1∗⊆G(x) I(x)=\g∈ G g(x)=x and g(y)≠ y,∀ y∈\0,1\^*\ stab_G(x) (12) The set of all isolating symmetries in G is denoted G I_G. G=g∈G∣|(g)|=1=∐x∈0,1∗G(x) I_G=\g∈ G | fix(g)|=1\= _x∈\0,1\^* I_G(x) (13) 2.2 Algorithmic properties of symmetry groups The group of total recursive bijections TB is not r.e.. To enumerate all computable bijections, one needs to enumerate all programs that compute total bijective functions. This requires checking totality and bijectivity, which are Π2 _2-complete. Since TB is not r.e., there is no effective enumeration of (x) stab(x) either. If we make the assumtion however that G is a r.e. subgroup of TB, the stabiliser group G(x) stab_G(x) is r.e. One can enumerate through G and check if g∈Gg∈ G fixes x, provided that the action of the group on bit strings is computable . Under the assumption that G is r.e., the subset G(x) I_G(x) is co-r.e. To enumerate x I_x, one would enumerate elements of G(x) stab_G(x) to check that they have no fixed points other than x. This is a co-r.e. condition (finding the second fixed point is r.e., proving none exists is co-r.e.). Proposition 2.1. Let G be a r.e. symmetry group. Then for all x∈0,1∗x∈\0,1\^*, the stabilizer subgroups G(x) stab_G(x) are r.e. The point-wise isolators and total isolator G(x) I_G(x) and G I_G are co-r.e. A prefix universal computer is a partial recursive function U:0,1∗×0,1∗→0,1∗U:\0,1\^*×\0,1\^*→\0,1\^* so that U(p,x)=yU(p,x)=y where p is prefix-free code for the function U(p,⋅):0,1∗→0,1∗U(p,·):\0,1\^*→\0,1\^*. A program encoding a symmetry is a prefix code p so that U(p,⋅)U(p,·) is a symmetry. We call this a symmetry program. The set of all symmetry programs is denoted by U TB. U=p∣U(p,⋅)∈U TB=\p U(p,·)∈ TB\ (14) By the discussion there U TB is not a recursively enumerable language. Let G⊂G⊂ TB be a r.e. subset. The set of symmetry programs for symmetries in G UG=p∣U(p,⋅)∈GU^G=\p U(p,·)∈ G\ (15) is r.e. Let us denote the universal computer for G-symmetries by the same name. Proposition 2.2. Let G be a r.e. symmetry group. There is an effective enumeration of G-symmetries. The universal computer for this is a p.r. function UG:0,1∗×0,1∗→0,1∗U^G:\0,1\^*×\0,1\^*→\0,1\^* (16) such that UG(p,⋅)∈GU^G(p,·)∈ G when p is halting. A symmetry program computes x when it is a program for an isolating symmetry for x. The set of all symmetry programs computing x is denoted by UxU TB_x. Ux=p∣U(p,⋅)∈xU TB_x=\p U(p,·)∈ I_x\ (17) The set of all symmetry programs in UGU^G computing x is denoted by UxGU^G_x. UxG=p∣UG(p,⋅)∈xU^G_x=\p U^G(p,·)∈ I_x\ (18) Remark 2.3. Note that U TB is not a universal computer for total recursive bijections. The set TB is not recursively enumerable. There is no Turing machine that accepts only the symmetry prefix programs in U. 2.3 Simulations The fixed-point set of computable symmetries offers a mapping from G≤G≤ TB to subsets of bit strings G→(0,1∗)G (\0,1\^*). This is non-computable in general. Restriction to isolating symmetries gives a computable map, :G→0,1∗. fix: I_G→\0,1\^*. (19) Definition 2.4. An I-section of G≤G≤ TB is a computable right-inverse of fix, i.e. a computable map :0,1∗→G sec:\0,1\^*→ I_G (20) such that ∘=id0,1∗ fix sec=id_\0,1\^*. The existence of the section means G(x) I_G(x) is non-empty ∀x∈0,1∗∀ x∈\0,1\^*. A symmetry group G is fix-retractable if it admits an I-section. The existence of a I-section implies an important property of the program spaces. Any ordinary program for outputting a bit string can be simulated by a symmetry program of the same length (up to additive constant term). The fix map implies a similar property in the other direction, any symmetry program that isolates a bit string can be simulated by an ordinary program of the same length (up to a additive constant). The idea of codes being simulatable by codes of another type of the same length is formalized in the definition below. The subsequent proposition proves the connection claimed. Definition 2.5. UGU^G simulates U if there is a injective computable function Φ:0,1∗→0,1∗ :\0,1\^*→\0,1\^* that maps programs computing x to symmetry programs computing x. Φ(Ux)⊂UxG,∀x∈0,1∗ (U_x)⊂ U^G_x,∀ x∈\0,1\^* (21) and ℓ(Φ(p))=ℓ(p)+O(1) ( (p))= (p)+O(1) for all p∈Uxp∈ U_x. U simulates UGU^G if there is a injective computable function Ψ:0,1∗→0,1∗ :\0,1\^*→\0,1\^* that maps symmetry programs to programs computing x Ψ(UxG)⊂Ux,∀x∈0,1∗ (U^G_x)⊂ U_x,∀ x∈\0,1\^* (22) and ℓ(Ψ(q))=ℓ(q)+O(1) ( (q))= (q)+O(1) for all q∈UxGq∈ U^G_x. Theorem 2.6. If G is a fix-retractable symmetry group, then U and UGU^G can simulate each other. Proof. 1. (U simulates UGU^G): The map :G→0,1∗ fix: I_G→\0,1\^* lifts to a computable map between program spaces: U:q∣UG(q) halts and∈G→p∣U(p) halts U_ fix:\q U^G(q) halts and∈ I_G\→\p U(p) halts \ (23) such that ∀x∈0,1∗∀ x∈\0,1\^*, U(UxG)⊂UxU_ fix(U^G_x)⊂ U_x. The mapping U_ fix is defined as follows: given a program q for an x-isolator, run q, get the isolator g∈G(x)g∈ I_G(x), compute the fixed point by computing g(x)g(x) through enumerating x∈0,1∗x∈\0,1\^*. This will stop eventually because g is an isolator for x. The program U(q)U_ fix(q) is therefore a program that produces x. The prefix code for U(q)U_ fix(q) is obtained by concatenating the prefix code with q with the code for U_ fix plus a constant overhead code. This is injective and the length, ℓ(U(q))≤ℓ(q)+O(1). (U_ fix(q))≤ (q)+O(1). (24) 2. (UGU^G simulates U): The section :0,1∗→G sec:\0,1\^*→ I_G lifts to a computable map between program spaces: U:p∣U(p) halts →q∣UG(q) halts and∈GU_ sec:\p U(p) halts \→\q U^G(q) halts and∈ I_G\ (25) such that ∀x∈0,1∗∀ x∈\0,1\^*, U(Ux)⊂UxGU_ sec(U_x)⊂ U^G_x. The mapping U_ sec is defined as follows: given a program p that produces x, run p, get x, apply sec to get (x)∈G(x) sec(x)∈ I_G(x). The program U(p)U_ sec(p) is program for an isolator for x by concatenating the prefix code for p with the constant length prefix code for U_ sec. This makes U_ sec injective and the length, ℓ(U(p))≤ℓ(p)+O(1). (U_ sec(p))≤ (p)+O(1). (26) ∎ We give an alternate characterization of fix-retractable symmetry groups. The presence of an I-section implies and is implied by the existence of a subgroup of G which is r.e. and for which the set of isolators is also r.e. Theorem 2.7. The following properties of a symmetry group G≤G≤ TB are equivalent. 1. G is fix-retractable 2. ∃H≤G∃ H≤ G such that (a) H can isolate all x∈0,1∗x∈\0,1\^* (b) H and H I_H are r.e. Therefore for a symmetry group G satisfying 2, UGU^G can simulate U. Proof. 1. (⇐ ) Let UHU^H and UHU I_H be effective enumerations of H and H I_H. Define the I-section of G, :0,1∗→G sec:\0,1\^*→ I_G as follows: Enumerate isolators in H by running UHU I_H. For every h∈Hh∈ I_H check if it belongs to H(x) I_H(x) by computing h(x)h(x). This will eventually halt because of the first assumption about H. 2. (⇒ ) Let :0,1∗→G sec:\0,1\^*→ I_G be an I-section for G. Consider the induced map on programs (see proof of 2.6) U:p∣U(p) halts →q∣UG(q) halts and∈GU_ sec:\p U(p) halts \→\q U^G(q) halts and∈ I_G\ (27) which satisfies (Ux)⊆UxG sec(U_x) U^G_x for all x∈0,1∗x∈\0,1\^*. Consider the set of isolators in G defined by the image of sec: S=U(q,⋅)∣q∈(Ux)⊆G(x)S=\U(q,·) q∈ sec(U_x)\ I_G(x) (28) Let H:=⟨h:h∈S⟩H:= h:h∈ S be the subgroup of G generated by S. ∎ 3 Algorithmic Probability from Symmetries 3.1 Symmetry Priors Definition 3.1. The G-symmetry prior of a string x with respect to a computer U is the probability that a random symmetry program computes x. mGU(x)=∑p∈UxG12ℓ(p)m^U_G(x)= _p∈ U_x^G 12 (p) (29) The Solomonoff Prior mU(x)m^U(x) is lower semi-computable. The proof relies on the fact that the set of programs UxU_x is recursively enumerable. The direct analogy fails to work with the symmetry prior since the set of symmetry programs computing x is not r.e. In the sequel we show that the symmetry prior is equal to the Solomonoff prior up to a constant term when every program can be simulated by a symmetry program. But first, we have to make the idea of simulation precise. 3.2 Universal Semi-measures Definition 3.2. A function μ:0,1∗→ℝμ:\0,1\^* is a probability semi-measure if 1. μ(ϵ)≤1μ(ε)≤ 1 2. μ(x)≥μ(x0)+μ(x1)μ(x)≥μ(x0)+μ(x1) A semi-measure is lower semi-computable if the function μ is lower semi-computable. Let ℳM be a class of discrete semi-measures. A semi-measure P0P_0 is universal (or maximal) for ℳM if P0∈ℳP_0 , and for all P∈ℳP there exists a constant cPc_P such that for all x∈0,1∗x∈\0,1\^* we have cPP0(x)≥P(x)c_PP_0(x)≥ P(x), where cPc_P possibly depends on P but not on x. The Solomonoff prior mU(x)m^U(x) and 2−K(x)2^-K(x) are lower semi-computable semi-measures. The condition of being semi-measures is a consequence of teh Kraft inequality of prefix codes. Lower semi-computability of both semi-measures come from the fact that UxU_x is recursively enumerable. The prior mU(x)m^U(x) is universal for the following reason. For any lower semi-computable semi-measure μ, there is a computable enumeration of programs that realize μ. The universal machine U can simulate all such programs. The sum mU(x)m^U(x) includes all programs, so it dominates each μ up to a constant (the weight assigned to the program that enumerates μ). The classical coding theorem implies that 2−K(x)2^-K(x) is universal: since mU(x)≍2−KU(x)m^U(x) 2^-K_U(x), and mU(x)m^U(x) is universal, 2−KU(x)2^-K_U(x) inherits universality. Proposition 3.3. If G is fix-retractable, the symmetry prior mGU(x)m^U_G(x) is a lower semi-computable semi-measure. Proof. Compose the two simulations Θ:=∘:UxG→UxG := sec fix:U^G_x→ U^G_x (30) This map takes any symmetry program p∈UxGp∈ U^G_x, converts it into a standard program (p) fix(p) and converts it back into a symmetry program ((x)) sec( fix(x)). The length of the program Θ(p) (p) is no longer than p by a constant term ℓ(Θ(p))=ℓ(((p))≤ℓ(p)+cΨ+cΦ ( (p))= ( sec( fix(p))≤ (p)+c_ +c_ (31) Let Sx=Θ(UxG)⊆UxGS_x= (U^G_x) U^G_x be the set of symmetry programs that are in the image of Θ . Two important properties of SxS_x: 1. SxS_x is recursively enumerable. This is so because UxU_x is recursively enumerable and Φ is a computable map. Therefore SxS_x is the image of a r.e set under a computable map. 2. SxS_x is probability dense in UxGU^G_x. ∑q∈Sx12ℓ(q)≥∑p∈UxG12ℓΘ(p)=2−cθ∑p∈UxG12ℓ(p)=2−ΘmGU(x) _q∈ S_x 12 (q)≥ _p∈ U_x^G 12 (p)=2^-c_θ _p∈ U_x^G 12 (p)=2^- m^U_G(x) (32) So SxS_x carries a constant fraction of the total probability mass of UxGU^G_x. To approximate the symmetry prior from below we only need to enumerate a probability-dense r.e. subset Sx⊆UxGS_x U^G_x. Since SxS_x is r.e., we can enumerate its elements and sum their probabilities, giving a non-decreasing sequence that converges to the value at least 2−cΘmGU(x)2^-c_ m^U_G(x). ∎ The proof of lower semi-computability of the symmetry prior 3.3 inspires the following definition. Definition 3.4. For every x∈0,1∗x∈\0,1\^*, let xC_x be a set of codes with prefix-free encoding and a probability semi-measure μ. A subset x⊆xD_x _x is called uniformly probability dense if: 1. xD_x is recursive enumerable 2. There exists a constant c>0c>0 such that μ(x)≥c.μ(x)μ(D_x)≥ c.μ(C_x) for all x. In the context of symmetry programs, x=UxC_x=U TB_x, and a uniformly probability-dense subset Sx⊂UxS_x⊂ U_x TB provides a lower semi-computable approximation to the symmetry prior mGU(x)m^U_G(x). Theorem 3.5. If G is a fix-retractable symmetry group then the symmetry prior is equal to the Solomonoff prior up to a multiplicative constant. mGU(x)≍mU(x).m^U_G(x) m^U(x). (33) Therefore, the symmetry prior is a universal lower semi-computable semi-measure on binary strings. Also as a consequence of the classical coding theorem −log2mGU(x)=K(x)+O(1)- _2m^U_G(x)=K(x)+O(1) (34) Proof. 1. (mGU(x)≥C.mU(x)m^U_G(x)≥ C.m^U(x)) From the simulation :U→UG sec:U→ U^G, every program p for x gives a symmetry program (p) sec(p) with ℓ((p))=ℓ(p)+c1 ( sec(p))= (p)+c_1, where c1c_1 is the constant overhead of the simulation. Therefore: mGU(x)=∑p∈UxG12ℓ(p)≥∑p∈Ux12ℓ((p))=2−c1∑p∈Ux12ℓ(p)=2−c1mU(x)m^U_G(x)= _p∈ U_x^G 12 (p)≥ _p∈ U_x 12 ( sec(p))=2^-c_1 _p∈ U_x 12 (p)=2^-c_1m^U(x) (35) 2. (mU(x)≥C.mGU(x)m^U(x)≥ C.m^U_G(x)) From the simulation :UxG→Ux fix:U^G_x→ U_x, every symmetry program q for x gives a program (q) fix(q) for x with ℓ((q))=ℓ(q)+c2 ( fix(q))= (q)+c_2 where c2c_2 is the constant overhead of the simulation fix. Therefore: mU(x)=∑p∈Ux12ℓ(p)≥∑q∈UxG12ℓ((q))=2−c2∑q∈UxG12ℓ(q)=mGU(x)m^U(x)= _p∈ U_x 12 (p)≥ _q∈ U^G_x 12 ( fix(q))=2^-c_2 _q∈ U^G_x 12 (q)=m^U_G(x) (36) ∎ 3.3 Examples 3.3.1 G=G= TB Theorem 3.6. [2] TB is fix-retractable. Hence the GCT is true for the full symmetry group of all computable symmetries. Proof. An I-section of TB would be a computable map :0,1∗→ sec:\0,1\^*→ I such that (x)∈x sec(x)∈ I_x. We give an explicit construction. For every x∈0,1∗x∈\0,1\^* let sxs_x be a x isolator defined as follows: 1. sx(x)=xs_x(x)=x 2. sx(x∗)=ϵs_x(x^*)=ε and sx(ϵ)=x∗s_x(ε)=x^* 3. ∀y≠x,sx(y)=y∗∀ y≠ x,s_x(y)=y^*, where y∗y^* is y with its last bit flipped. The mapping x↦sxx s_x is computable. ∎ 4 Algebraic Characterizations 4.1 Galois Connections Let G≤G≤ TB be a symmetry group. Definition 4.1. The stabilizer of a subset X⊂0,1∗X⊂\0,1\^* is the subgroup of G that fixes X (X)=f∈G∣X⊂(f) stab(X)=\f∈ G\ X⊂ fix(f)\ (37) The fixed points of a subgroup H≤GH≤ G is (H)=x∈0,1∗∣h(x)=x∀h∈H fix(H)=\x∈\0,1\^* h(x)=x∀ h∈ H\ (38) Theorem 4.2. The pair (,):ℒ(G)→P(0,1∗)( fix, stab):L(G)→ P(\0,1\^*) (39) forms an order-reversing Galois connection between the the subgroup lattice of G and the subset lattice of 0,1∗\0,1\^*. That is for every H≤GH≤ G and X⊂0,1∗X⊂\0,1\^* X⊂(H)⇔H≤(X)X⊂ fix(H) H≤ stab(X) (40) Definition 4.3. (Closure Operations) Composing the left and right adjoints of the Galois connection gives closure operations. 1. On subsets of 0,1∗\0,1\^* X¯:=((X))⊇X X:= fix( stab(X)) X (41) 2. On subgroups of G H¯:=((X))≥H H:= stab( fix(X))≥ H (42) These are closure operations in the sense they are monotone and idempotent, and are guaranteed by the Galois connection. A subset X⊆0,1∗X \0,1\^* or subgroup H≤GH≤ G is closed when its closure is itself. A point x∈0,1∗x∈\0,1\^* is said to be closed when x\x\ is closed. The closure of x is the intersection of the fixed points sets of all the elements of G that fix x. x¯=⋂f(x)=x(⟨f⟩) \x\= _f(x)=x fix( f ) (43) Proposition 4.4. A symmetry group G can isolate every x∈0,1∗x∈\0,1\^* if and only if every maximal subgroup of G is closed in ℒ(G)L(G) Proof. A point x is closed i.e. ((x))=x fix( stab(x))=\x\ iff G(x)≠∅ I_G(x)≠ . The Galois connection of Thm.4.2 implies there is a order reversing bijection between closed sets in 0,1∗\0,1\^* and closed subgroups in G given by X⟷(X)X stab(X) and H⟷(H)H fix(H). i.e. the closed subgroups are precisely the subgroups of the form (X) stab(X) for some subset X⊆0,1∗X \0,1\^*. The maximal closed subgroups are (x) stab(x) for some x∈0,1∗x∈\0,1\^*. The closed points of 0,1n\0,1\^n are therefore in one-to-one correspondence with maximal closed subgroups of G. ∎ Proposition 4.5. Given a symmetry group G, the set of isolating symmetries G I_G can be identified with the minimal (w.r.t lattice) points in the join semi-lattice of dense subgroups of G. Proof. For any closed bit string x∈0,1∗x∈\0,1\^* let (x)≤G stab(x)≤ G be the corresponding maximal closed point in the lattice ℒ(G)L(G). The elements of (x) stab(x) fix x, but are not necessarily isolators of x. We can characterize the isolators subset G(x)⊆(x) I_G(x) stab(x) in the following way: A dense point below (x) stab(x) is a subgroup D≤(x)D≤ stab(x) such that D¯=((D))=(x) D= stab( fix(D))= stab(x). Dense points are those subgroups of (x) stab(x) whose fixed points set is x\x\. The join of two dense subgroups is dense, (⟨D1,D2⟩)=(D1)∩(D2)=x fix( D_1,D_2 )= fix(D_1)∩ fix(D_2)=\x\ (44) Therefore the set of dense subgroups of (x) stab(x) forms a join semi-lattice, denote this by D(x)D(x). The lowest points of this semi-lattice are cyclic groups generated by isolators of x. The cyclic subgroups ⟨g⟩:g∈G(x) g :g∈ I_G(x) are the principal dense subgroups. The stabilizer (x) stab(x) can be constructed as the join of all the cyclic dense subgroups ⋁g∈G(x)⟨g⟩=(x) _g∈ I_G(x) g = stab(x) (45) ∎ Theorem 4.6. Let G be a symmetry group. The conditions of Thm.2.7(2) are satisfied if 1. ∃H≤G∃ H≤ G such that H is closed in ℒ(G)L(G) and every maximal subgroup of H is closed in ℒ(G)L(G) 2. the subgroup lattice ℒ(H)L(H) is computable (i.e. the points in the lattice, join, meet and closure operations are computable) 5 Conclusion We have established a direct analogue of the classical Coding Theorem in the context of symmetry groups. The central notion of a fix-retractable symmetry group—one that admits a computable section selecting an isolating symmetry for every string—provides the precise condition under which the symmetry prior mGU(x)m^U_G(x) becomes a universal lower semicomputable semimeasure. When this condition holds, the Geometric Coding Theorem −log2mGU(x)=K(x)+O(1)- _2m^U_G(x)=K(x)+O(1) follows, extending Solomonoff’s celebrated result to the realm of algorithmic symmetry. The Galois connection between subgroups of G and subsets of binary strings reveals a rich algebraic structure: closed points correspond to maximal closed subgroups, and the join-semilattice of dense subgroups offers a natural framework for understanding how isolating symmetries generate the full stabilizer. The results presented here form the foundation for the broader program of Computational Algorithmic Statistics (CAS). References [1] Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, 4th edition, 2019. [2] Raúl A. Trejo, Vladik Kreinovich, and Luc Longpré. Choosing a Physical Model: Why Symmetries? Bulletin of the European Association for Theoretical Computer Science (EATCS), vol. 70, p. 159–161, 2000. Also available as UTEP technical report UTEP-CS-00-04.