跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2609.40290 · v3

Orbits as Strong Models: Kolmogorov Structure Function under Symmetry

首次提交 2026-10-01 01:49
版本更新 2026-11-18 08:15
雷达观测 2026-11-19 19:08
arXiv ↗PDF ↗

摘要

Strong models in algorithmic statistics are essentially the cells of simple partitions of {0,1}n\{0,1\}^n. We study the partitions that come from symmetry, the orbit partitions of groups acting on strings, and the structure function hxGh^G_x they induce. A set is a cell of such a partition exactly when its setwise stabiliser acts transitively on it, so hxGh^G_x is Kolmogorov's structure function restricted to GG-homogeneous sets. For the full symmetric group this recovers all models and exactly the strong ones. For GL(n,2)GL(n,2) the cells are the linearly homogeneous sets, hxGLh^{GL}_x lies in a band between C(x)−αC(x)-α and n−αn-α 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.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-18 08:15 · 最新观测版本

Orbits as Strong Models: Kolmogorov Structure Function under Symmetry

Strong models in algorithmic statistics are essentially the cells of simple partitions of {0,1}n\{0,1\}^n. We study the partitions that come from symmetry, the orbit partitions of groups acting on strings, and the structure function hxGh^G_x they induce. A set is a cell of such a partition exactly when its setwise stabiliser acts transitively on it, so hxGh^G_x is Kolmogorov's structure function restricted to GG-homogeneous sets. For the full symmetric group this recovers all models and exactly the strong ones. For GL(n,2)GL(n,2) the cells are the linearly homogeneous sets, hxGLh^{GL}_x lies in a band between C(x)−αC(x)-α and n−αn-α 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.

查看此版本解读 →查看此版本原文 ↗