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

对称性下的轨道作为强模型:Kolmogorov 结构函数研究

Orbits as Strong Models: Kolmogorov Structure Function under Symmetry

AI 导读

这篇 arXiv 论文研究群作用于字符串产生的轨道划分及其诱导的 Kolmogorov 结构函数 h^G_x,证明一个集合是划分单元当且仅当其集稳定子在其上传递作用。对全对称群可恢复全部强模型;对 GL(n,2),单元是线性齐次集合,h^{GL}_x 介于 C(x)−α 与 n−α 之间且两端可达。作者还将轨道模型搜索转化为子群格上的价值估计,给出可计算界、认证训练目标及格版蒙特卡洛树搜索。

正文 · 原文

View PDF HTML (experimental)

Abstract:Strong models in algorithmic statistics are essentially the cells of simple partitions of $\{0,1\}^n$. We study the partitions that come from symmetry, the orbit partitions of groups acting on strings, and the structure function $h^G_x$ they induce. A set is a cell of such a partition exactly when its setwise stabiliser acts transitively on it, so $h^G_x$ is Kolmogorov's structure function restricted to $G$-homogeneous sets. For the full symmetric group this recovers all models and exactly the strong ones. For $GL(n,2)$ the cells are the linearly homogeneous sets, $h^{GL}_x$ lies in a band between $C(x)-\alpha$ and $n-\alpha$ with both edges attained, and some stochastic normal strings have simple structure that is invisible to linear symmetry. Writing each permutation group as a Burnside-ring type with a placement, we show that any space of symmetry hypotheses small enough to search is small enough to miss simple structure. Finally we cast the search for orbit models as value estimation on subgroup lattices, with computable bounds, certified training targets and a lattice version of Monte Carlo tree search.
Subjects: Information Theory (cs.IT); Artificial Intelligence (cs.AI); Group Theory (math.GR)
Cite as: arXiv:2609.40290 [cs.IT]
  (or arXiv:2609.40290v3 [cs.IT] for this version)
  https://doi.org/10.48550/arXiv.2609.40290

arXiv-issued DOI via DataCite

Submission history

From: Romie Banerjee [view email]
[v1] Wed, 30 Sep 2026 17:49:15 UTC (21 KB)
[v2] Mon, 5 Oct 2026 13:13:19 UTC (29 KB)
[v3] Wed, 18 Nov 2026 00:15:04 UTC (33 KB)

来源:arXiv cs.AI · arxiv.org