Algorithmic statistics reveals symmetrical patterns in data structure
CAS II: Symmetric Partitions as Kolmogorov Models
Information TheoryArtificial Intelligence
Summary
This paper explores how patterns in data can be explained by groups of symmetries acting on binary strings. The authors study how symmetric partitions help identify what parts of data’s regularities are due to symmetry, distinguishing simple from complex patterns. They show that different symmetry groups correspond to different types of models and reveal when apparent structure is hidden from simpler symmetric views. This work connects ideas from algorithms, group theory, and statistics to better understand data complexity.
What this means in practice
- •For data compression engineers: Inform design of compression algorithms that exploit symmetries by identifying simple symmetric models for data structures.
- •For cryptographic system designers: Guide analysis of data randomness by identifying structural symmetries that affect security assumptions on information complexity.
A theory result. No direct application yet.
Authors
Romie Banerjee
Abstract
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. Vereshchagin's strong models, those computable from the data by a total algorithm, are essentially the cells of simple partitions. We read a partition of binary strings as a hypothesis, with the cell containing x as its model, and 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 a lattice of symmetric partitions, with canonical certificates, canonical costs, and an algebra of hypotheses. The resulting structure function and symmetric sophistication measure which part of the regularity of x is symmetric. For the full symmetric group every partition is symmetric: cells recover all Kolmogorov models, cells of cheap partitions recover exactly the strong models, and normal and strange strings are characterized by symmetry. For GL(n,2) the cells are exactly the linearly homogeneous sets, so linear symmetry is a restricted model class. For nonzero x, the linear-symmetry structure function lies in a band between the sufficiency line and the trivial bound, and both edges are attained: there are stochastic normal strings whose simple structure is invisible to linear symmetry. We also give coordinates on the space of permutation groups: each group is an element of a Burnside ring (its type) together with a permutation (its placement), and restriction moves refine partitions via the Mackey formula. In these coordinates the collapse for the symmetric group is a statement about placement, a linear hypothesis is determined by its type up to n^2 bits, and the maximal gap theorem shows that any space of symmetry hypotheses small enough to search is small enough to miss simple structure.