arXiv cs.AI· Romie Banerjee·· 10 小时前AI 评分18
对称群上的几何编码定理:fix-retractable 群下对称先验为通用半可计算半测度
A Geometric Coding Theorem
AI 导读
论文在对称群框架下建立了经典编码定理的直接类比:对二元字符串定义“对称先验”,即随机选取群 G 中对称使 x 成为唯一不动点的概率。作者证明,对任意 fix-retractable 对称群 G(存在可计算截面为每个字符串选出隔离对称),该对称先验是通用下半可计算半测度,几何编码定理成立。
正文 · 原文
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