Metraipolis › archive › dc_feca7304bcb4

CAS II: Orbits as Models: Kolmogorov's Structure Function under Symmetry — arXiv:2609.40290

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.40290
License (as archived)
CC0-1.0
Archived
2026-10-07T12:46:19.912Z
SHA-256 of the archived text
306319a4e2e30371b19f980e72149d8deabc881e78a84caa490c6798136d7fc9
Stable URL of this page
https://metraipolis.com/documento/dc_feca7304bcb4

How to cite

CAS II: Orbits as Models: Kolmogorov's Structure Function under Symmetry — arXiv:2609.40290 — arXiv (en), https://arxiv.org/abs/2609.40290 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_feca7304bcb4 (Metraipolis archive dc_feca7304bcb4, sha256 306319a4e2e30371b19f980e72149d8deabc881e78a84caa490c6798136d7fc9)
BibTeX
@misc{dcfeca7304bcb4,
  title = {CAS II: Orbits as Models: Kolmogorov's Structure Function under Symmetry — arXiv:2609.40290},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40290},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_feca7304bcb4; sha256 306319a4e2e30371b19f980e72149d8deabc881e78a84caa490c6798136d7fc9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40290. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In algorithmic statistics a string x is explained by a finite set containing it, and Kolmogorov's structure function records the smallest such model at each level of complexity. Strong models, those computable from the data by a total algorithm, are essentially the cells of simple partitions, so a partition of {0,1}^n can be read as a hypothesis and the cell containing x as the model it assigns. We develop algorithmic statistics over symmetric partitions, the orbit partitions of groups acting on strings. The Galois connection between subgroups and partitions gives each ambient group G a lattice of symmetric partitions with canonical certificates, joins and meets. A set is a cell of a symmetric partition exactly when its setwise stabiliser in G acts transitively on it, so the resulting structure function is Kolmogorov's restricted to these G-homogeneous sets. With a symmetric sophistication, it measures which part of the regularity of x is symmetric. Under the full symmetric group, cells recover all models and cells of cheap partitions recover exactly the strong models, so normal and strange strings are characterised by symmetry. For GL(n,2) the homogeneous sets are the linearly homogeneous ones, whose XOR dependencies look the same from every point. The GL structure function of a nonzero x lies in a band between C(x) - alpha and n - alpha, and both edges are attained: some stochastic normal strings have simple structure invisible to linear symmetry, with sophistication near 0 but GL-sophistication near C(x). We coordinatise permutation groups by a Burnside ring element (type) and a permutation (placement). In these coordinates a linear hypothesis is determined by its type up to n^2 bits, and any space of symmetry hypotheses small enough to search is small enough to miss simple structure. This sets up learned search over orbit models, the subject of later papers in the series.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-10-01 in cs.AI).
Categorie arXiv: Information Theory (cs.IT) ; Artificial Intelligence (cs.AI); Group Theory (math.GR).
Pagina del lavoro: https://arxiv.org/abs/2609.40290 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T12:14:14.248Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).