用对称群定义新复杂度，统一算法信息与群论。
CAS I: A Geometric Coding Theorem
- 以对称群的唯一不动点定义字符串复杂度
- 证明该复杂度是通用下可计算半测度
- 适合研究对称性与信息复杂度的交叉领域
本文在对称群框架下建立了经典编码定理的直接类比。考虑二进制串上的可计算双射（称为对称），定义字符串的对称先验为：随机选取一个群内对称时，该字符串是其唯一不动点的概率。我们证明，对于任意可固定收缩的对称群（即存在可计算截面为每条字符串选择隔离对称），该对称先验是通用的下可计算半测度。此时几何编码定理成立。我们还建立了群的子群与二进制串子集之间的伽罗瓦连接，刻画了闭点与极大闭子群，并探索了稠密子群的并半格结构。结果将算法信息论与群论统一，为研究对称诱导的复杂度度量提供了框架。本文是计算算法统计学（CAS）系列的第一篇。
原文摘要 · Abstract (English)
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).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。