arXiv 论文提出几何编码定理:对称群下的编码定理类比
A Geometric Coding Theorem
AI 导读
一篇 arXiv 论文建立了经典编码定理在对称群设定下的直接类比:将字符串 x 的对称先验定义为随机选取的群 G 对称以 x 为唯一不动点的概率。论文证明,对任意 fix-retractable 对称群,对称先验是通用的下半可计算半测度,此时几何编码定理成立。
正文 · 原文
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 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. This result is a coding-theoretic restatement of a theorem of Trejo, Kreinovich and Longpré, who showed that the complexity of describing a string by a symmetry with that string as its unique fixed point equals its Kolmogorov complexity. Our contribution is to recast it in terms of algorithmic probability and to treat the symmetry group as a parameter, identifying fix-retractability as exactly the condition under which symmetry complexity collapses onto Kolmogorov complexity.
| Subjects: | Information Theory (cs.IT); Artificial Intelligence (cs.AI); Category Theory (math.CT); Group Theory (math.GR) |
| MSC classes: | 68Q30, 03D32, 20B99 |
| Cite as: | arXiv:2607.13796 [cs.IT] |
| (or arXiv:2607.13796v3 [cs.IT] for this version) | |
| https://doi.org/10.48550/arXiv.2607.13796 arXiv-issued DOI via DataCite |
Submission history
From: Romie Banerjee [view email]
[v1]
Wed, 15 Jul 2026 12:59:32 UTC (10 KB)
[v2]
Mon, 5 Oct 2026 13:49:44 UTC (13 KB)
[v3]
Wed, 18 Nov 2026 00:31:41 UTC (12 KB)
来源:arXiv cs.AI · arxiv.org