CAS II：作为Kolmogorov模型的对称划分

在算法统计学中，字符串x由包含它的有限集解释，Kolmogorov结构函数记录每一复杂度层级上最小的此类模型。Vereshchagin的强模型，即可由全算法从数据中计算的模型，本质上是简单划分的胞元。我们将二进制串的划分视为假设，将包含x的胞元作为其模型，并在此基础上发展针对对称划分（即群作用于串的轨道划分）的算法统计学。子群与划分间的Galois连接赋予每个环境群一个对称划分格，以及规范凭证、规范代价和假设代数。由此得到的结构函数与对称精巧度测量了x的规律性中具有对称性的部分。对全对称群而言，任何划分都是对称的：胞元还原了所有Kolmogorov模型，廉价划分的胞元恰好还原了强模型，正常串与奇异串由对称性刻画。对GL(n,2)而言，胞元恰为线性齐次集，因此线性对称性是受限模型类。对非零x，线性对称结构函数位于充分线与平凡界之间的带状区域，且两条边界均可达到：存在随机正常串，其简单结构对线性对称不可见。我们还给出了置换群空间上的坐标：每个群是Burnside环的一个元素（其类型）连同一次置换（其位置），且限制操作通过Mackey公式加细划分。在这些坐标下，对称群的坍缩是关于位置的陈述，线性假设由其类型决定且精确到n^2比特，而最大间隙定理表明，任何小到足以搜索的对称假设空间，都小到足以遗漏简单结构。