跳到正文
arXiv cs.AI· Romie Banerjee·· 2 小时前AI 评分20

arXiv 论文提出几何编码定理:对称群下的编码定理类比

A Geometric Coding Theorem

AI 导读

一篇 arXiv 论文建立了经典编码定理在对称群设定下的直接类比:将字符串 x 的对称先验定义为随机选取的群 G 对称以 x 为唯一不动点的概率。论文证明,对任意 fix-retractable 对称群,对称先验是通用的下半可计算半测度,此时几何编码定理成立。

正文 · 原文

View PDF HTML (experimental)

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