The classical Coding Theorem says: if many programs produce a string, that string is simple.
I generalize this to symmetries—computable bijections on binary strings. A symmetry “defines” a string if that string is its only fixed point. The symmetry prior is the probability that a random symmetry from a group defines a given string.
The main result: if the group has a computable way to pick an isolating symmetry for every string (I call this fix-retractable), then the symmetry prior satisfies the same Coding Theorem as the classical one. So the probability that a random symmetry defines a string is high if and only if that string is simple—just like in Solomonoff induction.
This generalizes Solomonoff induction to symmetry-based descriptions, gives a Galois connection between subgroups and fixed-point sets, and reframes inductive inference as search through a subgroup lattice rather than a program tree.
The Classical Picture
Solomonoff induction is one of the cleanest ideas we have about how to do induction from first principles. The setup is simple: you have a universal Turing machine, and you feed it random programs. The probability that a particular string pops out is the sum over all programs that output , each weighted by .
The Coding Theorem: This probability is essentially , where is the Kolmogorov complexity of . So the more programs produce , the simpler is.
Many descriptions → simple. Few descriptions → complex.
This is the foundation of universal induction, Occam’s razor, and most Bayesian approaches to intelligence. It tells us that simplicity is deeply connected to the distribution of programs.
Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and ItsApplications. Springer, 4th edition, 2019.
The Symmetry Generalization
Now, what if we replace “programs” with “symmetries”? A symmetry is a computable bijection on the space of binary strings—a way of rearranging the universe that preserves some structure. A symmetry “defines” a string if is its only fixed point: the symmetry leaves unchanged, but moves everything else.
The symmetry prior is then the probability that a randomly chosen symmetry (from some group ) defines . The question is: does the same Coding Theorem hold? Does the probability that a symmetry defines track the complexity of ?
The answer is yes—provided the group is fix-retractable. That means there is a computable way to pick, for every , a symmetry that fixes only . If you can do that, then the probability that a random symmetry defines is again up to a constant. The Coding Theorem holds for symmetries too.
The probability that a random symmetry defines is high if and only if is simple.
A Simulation Argument
Why does this work? The key is that symmetries and ordinary programs can sometimes simulate each other with only a constant overhead. The goal of the paper is to find out the exact conditions on the symmetry group for which this is possible.
From symmetries to programs: If you have a symmetry that isolates , you can find by enumerating all strings and checking which one is fixed. This gives you a program that outputs , with only a small constant added to the length.
From programs to symmetries: If you have a program that outputs , you can build a symmetry that isolates . The construction has to be uniform in . This gives a symmetry program with only a constant overhead.
Because these simulations are uniform and length-preserving up to a constant, the probability masses and complexity measures on both sides are asymptotically equivalent. This is the core mechanism that makes the Geometric Coding Theorem true.
The Lattice Insight
Here’s where it gets even more interesting. In classical Solomonoff induction, the search space is the set of all programs, which is a tree. You search for programs that output . In the symmetry framework, the search space becomes the subgroup lattice of . Instead of searching through programs, you search through subgroups that isolate . The join operation in this lattice merges many symmetries into a larger subgroup, much like taking a prefix merges many programs into a shorter one.
This suggests that inductive inference can be rephrased as navigating a lattice of symmetries. That’s a potentially richer and more structured search space than the program tree, and it might lead to new ways of thinking about inductive bias.
Their motivation came from physics. In modern fundamental physics, theories are often chosen not because they are the shortest description of the data, but because they have the simplest symmetry group. The question they asked was: does this symmetry-based Occam principle lose anything compared to the standard one?
Their answer was no. They proved that for every binary string , the shortest symmetry that uniquely defines (i.e., fixes and moves everything else) has essentially the same complexity as the shortest program that outputs .
The Trejo–Kreinovich–Longpré paper established the basic equivalence for the full group of all computable bijections. My work generalizes this in several ways:
From one group to all groups: I characterize exactly which symmetry groups satisfy the coding theorem. The key property is fix-retractability: the group must have a computable way to pick an isolating symmetry for every string. This gives a precise criterion that separates groups that work (like all computable bijections) from those that don’t (like polynomial-time or affine groups).
From single symmetries to subgroups: Where the original paper looked at individual symmetries with singleton fixed point sets, I develop a Galois connection between subgroups of and subsets of binary strings. This reveals that closed points correspond to maximal closed subgroups, and the set of subgroups that isolate forms a join-semilattice.
A proof that the symmetry prior is a universal semi-measure: I show that when is fix-retractable, the symmetry prior is a universal lower semi-computable semi-measure, just like the Solomonoff prior. This extends the coding theorem from a complexity equivalence to a full probabilistic statement.
Computability analysis: I prove that the symmetry prior is lower semi-computable when is fix-retractable, and explain why this is non-trivial (the full group of computable bijections is not c.e.). The key insight is that a probability-dense r.e. subset of the isolating symmetries suffices.
The lattice-search view: I reframe the search for isolating symmetries as search through the subgroup lattice of . This gives a new perspective on inductive inference: instead of searching through programs (a tree), we search through subgroups that isolate .
Why This Matters for AI
First, it bridges two foundational ideas: Solomonoff induction and symmetry. This paper gives an algorithmic foundation for why symmetry-based simplicity priors work: they are universal in the same sense as Solomonoff’s prior.
Second, it re-frames simplicity. The classical Coding Theorem says “many programs → simple.” This paper says “many symmetries → simple.” That suggests that simplicity is not fundamentally about programs—it’s about invariance under transformations. That might be a more natural framing for understanding inductive biases in neural networks and other learning systems.
Third, it gives an alternate universe for programs to live in. The problem of program search can be framed an algebraic problem of searching through a lattice of subgroups of a symmetry group.
Symmetries as Programs: A Geometric Coding Theorem
This post serves as an introduction to a generalization of the Coding Theorem from programs to symmetries.
Link: arXiv:2607.13796
Summary
The classical Coding Theorem says: if many programs produce a string, that string is simple.
I generalize this to symmetries—computable bijections on binary strings. A symmetry “defines” a string if that string is its only fixed point. The symmetry prior is the probability that a random symmetry from a group
The main result: if the group
This generalizes Solomonoff induction to symmetry-based descriptions, gives a Galois connection between subgroups and fixed-point sets, and reframes inductive inference as search through a subgroup lattice rather than a program tree.
The Classical Picture
Solomonoff induction is one of the cleanest ideas we have about how to do induction from first principles. The setup is simple: you have a universal Turing machine, and you feed it random programs. The probability that a particular string
The Coding Theorem: This probability is essentially
This is the foundation of universal induction, Occam’s razor, and most Bayesian approaches to intelligence. It tells us that simplicity is deeply connected to the distribution of programs.
References:
Less Wrong posts by Lang and Soares.
Lecture Notes on Algorithmic Information Theory, Charles Alexandre Bédard
Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, 4th edition, 2019.
The Symmetry Generalization
Now, what if we replace “programs” with “symmetries”? A symmetry is a computable bijection on the space of binary strings—a way of rearranging the universe that preserves some structure. A symmetry “defines” a string
The symmetry prior is then the probability that a randomly chosen symmetry (from some group
The answer is yes—provided the group
A Simulation Argument
Why does this work? The key is that symmetries and ordinary programs can sometimes simulate each other with only a constant overhead. The goal of the paper is to find out the exact conditions on the symmetry group for which this is possible.
From symmetries to programs: If you have a symmetry that isolates
From programs to symmetries: If you have a program that outputs
Because these simulations are uniform and length-preserving up to a constant, the probability masses and complexity measures on both sides are asymptotically equivalent. This is the core mechanism that makes the Geometric Coding Theorem true.
The Lattice Insight
Here’s where it gets even more interesting. In classical Solomonoff induction, the search space is the set of all programs, which is a tree. You search for programs that output
This suggests that inductive inference can be rephrased as navigating a lattice of symmetries. That’s a potentially richer and more structured search space than the program tree, and it might lead to new ways of thinking about inductive bias.
Related Work
In 2000, Trejo et. al. published a short but significant paper: “Choosing a Physical Model: Why Symmetries?” .
Their motivation came from physics. In modern fundamental physics, theories are often chosen not because they are the shortest description of the data, but because they have the simplest symmetry group. The question they asked was: does this symmetry-based Occam principle lose anything compared to the standard one?
Their answer was no. They proved that for every binary string
The Trejo–Kreinovich–Longpré paper established the basic equivalence for the full group of all computable bijections. My work generalizes this in several ways:
From one group to all groups: I characterize exactly which symmetry groups satisfy the coding theorem. The key property is fix-retractability: the group must have a computable way to pick an isolating symmetry for every string. This gives a precise criterion that separates groups that work (like all computable bijections) from those that don’t (like polynomial-time or affine groups).
From single symmetries to subgroups: Where the original paper looked at individual symmetries with singleton fixed point sets, I develop a Galois connection between subgroups of
A proof that the symmetry prior is a universal semi-measure: I show that when
Computability analysis: I prove that the symmetry prior is lower semi-computable when
The lattice-search view: I reframe the search for isolating symmetries as search through the subgroup lattice of
Why This Matters for AI
First, it bridges two foundational ideas: Solomonoff induction and symmetry. This paper gives an algorithmic foundation for why symmetry-based simplicity priors work: they are universal in the same sense as Solomonoff’s prior.
Second, it re-frames simplicity. The classical Coding Theorem says “many programs → simple.” This paper says “many symmetries → simple.” That suggests that simplicity is not fundamentally about programs—it’s about invariance under transformations. That might be a more natural framing for understanding inductive biases in neural networks and other learning systems.
Third, it gives an alternate universe for programs to live in. The problem of program search can be framed an algebraic problem of searching through a lattice of subgroups of a symmetry group.