← News

Models & toolsSources: arXiv · 19 Nov 2026

arXiv paper links symmetry orbits to Kolmogorov structure functions

A new theory paper studies which statistical models arise when groups act on binary strings, connecting orbit partitions to strong models and structure functions.

In plain words

A paper on arXiv examines how symmetry shapes statistical models of binary strings. When a group of transformations acts on strings, its orbits — the sets of strings reachable from each other — form simple models. The authors show these orbit-based models connect directly to a classical measure of structure in data.

What was announced

The paper, posted on arXiv, studies strong models in algorithmic statistics, which the authors describe as cells of simple partitions of binary strings. They focus on partitions induced by symmetry: the orbits of groups acting on strings, and the structure function these orbits define. A set is a cell of such a partition exactly when its setwise stabiliser acts transitively on it, meaning the induced function is Kolmogorov's structure function restricted to homogeneous sets. For the full symmetric group, this construction recovers all models and exactly the strong ones; for the general linear group, the cells are linearly homogeneous sets, and the induced function sits in a band whose both edges are attained.

The authors also report a limitation with practical weight: any space of symmetry hypotheses small enough to search is small enough to miss simple structure, with some stochastic normal strings carrying structure invisible to linear symmetry. To make the search tractable anyway, they cast finding orbit models as value estimation on subgroup lattices, offering computable bounds, certified training targets, and a lattice variant of Monte Carlo tree search.

What it does not show

  • The source is only the paper's abstract, so the results are not independently verified and full proofs, examples and details are not covered here.
  • The abstract is truncated mid-sentence, so the exact statement of the band's upper and lower bounds for the general linear group is incomplete.

Sources

Source-support review completed 20 Nov 2026. This story was drafted with AI assistance and checked against retained source passages. Automated checking is not independent verification.

Coverage: arXiv: abstract.

Updates and corrections

No corrections so far.

First published 20 Nov 2026

New to the subject? AI from the Ground Up starts from the beginning.