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

对称群上的几何编码定理:fix-retractable 群下对称先验为通用半可计算半测度

A Geometric Coding Theorem

AI 导读

论文在对称群框架下建立了经典编码定理的直接类比:对二元字符串定义“对称先验”,即随机选取群 G 中对称使 x 成为唯一不动点的概率。作者证明,对任意 fix-retractable 对称群 G(存在可计算截面为每个字符串选出隔离对称),该对称先验是通用下半可计算半测度,几何编码定理成立。

正文 · AI 翻译

查看 PDF HTML(实验性)

摘要:本文在对称群的框架下建立了经典编码定理的直接类比。我们考虑二元字符串集合上的可计算双射,并将字符串 x 的对称先验定义为:从给定群 G 中随机选取的一个对称恰好以 x 为唯一不动点的概率。我们证明,对于任何固定可收缩(fix-retractable)的对称群 G——即存在一个可计算截面,为每个字符串选取一个隔离对称的群——其对称先验是一个通用的下半可计算半测度。在这种情况下,几何编码定理成立。这一结果是 Trejo、Kreinovich 和 Longpré 一个定理的编码论重述,他们证明了用一个以该字符串为唯一不动点的对称来描述该字符串的复杂度等于其 Kolmogorov 复杂度。我们的贡献在于将其重新表述为算法概率的形式,并将对称群视为参数,从而确定固定可收缩性正是对称复杂度坍缩为 Kolmogorov 复杂度的条件。
学科: 信息论(cs.IT);人工智能(cs.AI);范畴论(math.CT);群论(math.GR)
MSC 分类号: 68Q30, 03D32, 20B99
引用为: arXiv:2607.13796 [cs.IT]
  (或 arXiv:2607.13796v3 [cs.IT] 查看此版本)
  https://doi.org/10.48550/arXiv.2607.13796

由 DataCite 颁发的 arXiv DOI

提交历史

来自:Romie Banerjee [查看邮箱]
[v1] 2026年7月15日星期三 12:59:32 UTC(10 KB)
[v2] 2026年10月5日星期一 13:49:44 UTC(13 KB)
[v3] 2026年11月18日星期三 00:31:41 UTC(12 KB)

来源:arXiv cs.AI · arxiv.org