CAS I: A Geometric Coding Theorem

• URL: http://arxiv.org/abs/2607.13796v1
• Date: Wed, 15 Jul 2026 12:59:32 GMT
• Title: CAS I: A Geometric Coding Theorem
• Abstract summary: This paper establishes a direct analogue of the classical Coding Theorem in the setting of symmetry groups.<n>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.
• Score: 0.6091702876917279
• License: http://creativecommons.org/licenses/by/4.0/
• 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).

Related papers

• Lattice 2-group symmetries: operators, defects, and gauging [0.0]
  We construct and study lattice realizations of finite 2-group symmetries in $2+1$d quantum lattice systems with finite-dimensional tensor-product Hilbert spaces.<n>We explore various manifestations of operators carrying symmetry charge, the structure of lattice 2-group symmetry defects, and the dual fusion 2-category symmetries obtained by gauging the lattice 2-group symmetries.
  arXiv  Detail & Related papers  (2026-09-09T18:00:01Z)
• Efficient Learning and Symmetry Discovery under Exact Invariances [62.27019402162741]
  Learning with group invariances is central to many scientific and geometric learning problems.<n>It has been unclear whether one can efficiently compute a regression function that is exactly in subgroup to a given group action.<n>We present the first-time algorithm for learning with exact group invariants that applies uniformly to finite and infinite groups.
  arXiv  Detail & Related papers  (2026-09-07T04:35:19Z)
• A homotopy-type-theoretic generalization of neurosymbolic inference [46.36639624013224]
  neurosymbolic (NeSy) systems compute one functional: a belief-weighted sum of a logical quantity over a space of $$-structures.<n>We develop the framework from scratch for NeSy systems, prove a conservativity theorem that recovers the classical functional when symmetries are trivial, and show that the symmetry our framework exposes is exactly the one behind reasoning shortcuts.
  arXiv  Detail & Related papers  (2026-06-16T12:22:12Z)
• Any-Subgroup Equivariant Networks via Symmetry Breaking [47.72921214239821]
  equivariant architectures are usually highly constrained, designed for symmetries chosen a priori.<n>This precludes the development of flexible, multi-modal foundation models capable of processing diverse data equivariantly.<n>We build a single model that can be simultaneously equivariant to several groups, simply by modulating a certain auxiliary input feature.
  arXiv  Detail & Related papers  (2026-03-19T21:30:41Z)
• Classification of locality preserving symmetries on spin chains [0.0]
  We consider the action of a finite group $G$ by locality preserving automorphisms (quantum cellular automata) on quantum spin chains.<n>We prove that the anomaly of such symmetries provides an isomorphism between the group of stable equivalence classes of symmetries with the cohomology group $H3(G,U(1))$.
  arXiv  Detail & Related papers  (2025-03-19T10:38:57Z)
• Predicting symmetries of quantum dynamics with optimal samples [41.42817348756889]
  Identifying symmetries in quantum dynamics is a crucial challenge with profound implications for quantum technologies.<n>We introduce a unified framework combining group representation theory and subgroup hypothesis testing to predict these symmetries with optimal efficiency.<n>We prove that parallel strategies achieve the same performance as adaptive or indefinite-causal-order protocols.
  arXiv  Detail & Related papers  (2025-02-03T15:57:50Z)
• Quantum Cellular Automata on Symmetric Subalgebras [6.158725838873227]
  We investigate quantum cellular automata on one-dimensional spin systems defined over a subalgebra of the full local operator algebra.<n>For systems where each site carries a regular representation of $G$, we establish a complete classification of such subalgebra QCAs.
  arXiv  Detail & Related papers  (2024-11-28T17:22:50Z)
• Symmetries from outer automorphisms and unorthodox group extensions [0.0]
  Symmetries play an essential role in the construction and phenomenology of quantum field theories (QFTs) We discuss how to construct symmetries of QFTs by extending minimal "seed" symmetry groups to larger groups that contain the seed as subgroup(s) We show that all symmetry groups, including the different possible classes of CP and continuous symmetry groups, can be obtained from extensions of the smallest possible symmetry CP1 by consecutive outer automorphisms.
  arXiv  Detail & Related papers  (2024-10-14T19:59:22Z)
• Symmetry-restricted quantum circuits are still well-behaved [45.89137831674385]
  We show that quantum circuits restricted by a symmetry inherit the properties of the whole special unitary group $SU(2n)$. It extends prior work on symmetric states to the operators and shows that the operator space follows the same structure as the state space.
  arXiv  Detail & Related papers  (2024-02-26T06:23:39Z)
• A Menagerie of Symmetry Testing Quantum Algorithms [0.0]
  We show how to generate a notion of symmetry from a discrete, finite group and how this generalizes to a continuous group. We propose quantum algorithms capable of testing whether a Hamiltonian exhibits symmetry with respect to a group. We prove that the acceptance probability of each algorithm is equal to the maximum symmetric fidelity of the state being tested.
  arXiv  Detail & Related papers  (2023-05-23T22:55:02Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  We design a deep-learning algorithm for the discovery and identification of the continuous group of symmetries present in a labeled dataset. We use fully connected neural networks to model the transformations symmetry and the corresponding generators. Our study also opens the door for using a machine learning approach in the mathematical study of Lie groups and their properties.
  arXiv  Detail & Related papers  (2023-01-13T16:25:25Z)
• A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group [29.714239628405515]
  We consider the class of synchronization problems which the group is a closed subgroup. We propose a unified approach for solving this class of problems. We show that our approach outperforms existing approaches.
  arXiv  Detail & Related papers  (2020-09-16T07:25:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.