This paper, authored by Hector Zenil and colleagues, explores a fascinating intersection between geometry and computer science: how do we measure the "simplicity" or "symmetry" of a shape using the language of algorithms? By moving beyond traditional statistical measures like Shannon entropy, the authors demonstrate that Algorithmic Probability can provide a more robust and "feature-free" way to profile the complexity of everything from Tetris pieces to high-dimensional hypercubes.
TL;DR
The authors propose a new definition of "algorithmic symmetry" based on Kolmogorov-Chaitin complexity. Using the Block Decomposition Method (BDM), they show that algorithmic complexity can capture deep geometric and topological features of polyominoes and polyhedral graphs that traditional statistical measures like Shannon entropy fail to detect.
What Problem Does This Paper Address?
Measuring symmetry and complexity is a cornerstone of fields ranging from crystallography to molecular biology. Traditionally, researchers have used group theory (for exact geometric symmetry) or Shannon entropy (for statistical regularity). However, both have blind spots.
Shannon entropy, for instance, only looks at the frequency of symbols. It might see a highly structured sequence and a random-looking one as equally complex if their bit-counts are the same. Similarly, standard lossless compression (like ZIP or Gzip) is often just a proxy for entropy and fails to recognize "causal" simplicity—like the fact that the infinite digits of $\pi$ can be generated by a very short program. The authors aim to fill this gap by providing a universal, unbiased measure of complexity that captures "algorithmic" regularities—patterns that exist because a simple rule or program generated them.
Methods
The paper relies on two primary pillars of Algorithmic Information Theory:
- Kolmogorov-Chaitin Complexity ($K$): The theoretical length of the shortest computer program needed to describe an object. Since $K$ is technically uncomputable, the authors use approximations.
- Algorithmic Probability (AP) & The Coding Theorem: AP describes the likelihood that a random program will produce a specific output. The Coding Theorem Method (CTM) allows researchers to estimate $K$ by looking at how often small Turing machines produce a certain pattern.
- Block Decomposition Method (BDM): To handle larger objects like adjacency matrices of graphs, the authors use BDM. This technique breaks a large matrix into smaller $d \times d$ blocks, calculates the complexity of those blocks using CTM, and then sums them up (applying a logarithmic penalty for repetitions).
By defining Algorithmic Symmetry as invariance under "recursively enumerable" (computable) transformations, they create a framework where an object is considered symmetric if it can be transformed into another version of itself by a short program.
Datasets
The authors evaluated their methods on several classes of geometric and graph-theoretic objects:
- Polyominoes: Sets of "free" polyominoes (shapes made of squares) of sizes 4 (tetrominoes), 5 (pentominoes), and 6 (hexominoes).
- Polyhedral Graphs: The 5 Platonic solids (tetrahedron, cube, etc.) and the 13 Archimedean solids.
- Dual Graphs: Pairs of graphs where vertices and faces are interchanged (e.g., the cube and the octahedron).
- Synthetic Graphs: Growing complete graphs (to test symmetry breaking) and random graphs.
- Polytopes: Hypercubes of varying dimensions (up to 7D).
- Wolfram GraphData: A library of standard graphs used for broader validation.
Key Insights and Ideas
- Symmetry Breaking as Information Generation: The authors show that starting with a perfectly symmetrical "complete graph," removing a single random edge causes a spike in algorithmic complexity. Conversely, removing a node (which results in a smaller but still perfectly symmetrical complete graph) keeps complexity low. This demonstrates that BDM is sensitive to the loss of structural rules.
- Representation Independence: One of the most striking findings is that BDM yields nearly identical complexity rankings for polyominoes whether they are represented as 2D bitmaps or as topological networks (graphs of their corners and edges). Shannon entropy and LZW compression failed to maintain this consistency.
- Duality and Complexity: Because the algorithm to turn a graph into its "dual" is fixed and short, the theory predicts their complexities should be very similar. The numerical results confirmed this, showing that dual polyhedra (like the dodecahedron and icosahedron) cluster together in complexity space.
- Beyond Statistics: The method successfully distinguishes between "random-looking" but algorithmically simple objects and truly random ones, a feat that entropy-based measures cannot reliably achieve.
Key Results
- Correlation Strength: In classifying polyominoes across different representations, the AP-based measure (BDM) achieved a Spearman rank correlation of $\rho = 0.99$. In contrast, standard compression (Compress) scored $\rho = 0.44$, and Shannon Entropy scored a statistically insignificant $\rho = 0.227$.
- Platonic vs. Archimedean: The results numerically confirmed that Archimedean solids (which use two types of polygons) are more complex than Platonic solids (which use only one), aligning with intuitive geometric hierarchy.
- Total Order of Symmetry: The authors were able to produce a numerical "symmetry ranking" for various objects, providing a total ordering where group theory usually only provides partial orders.
Limitations and Future Work
- Computational Intensity: While BDM is a significant optimization over pure CTM, it still requires pre-calculating the output distributions of millions of Turing machines, which is computationally expensive.
- Convergence: While the Invariance Theorem guarantees these measures will eventually converge to the "true" Kolmogorov complexity, the specific rate of convergence for different types of data remains an open theoretical question.
- Real-world Applications: The authors suggest these tools could revolutionize "molecular complexity" studies in chemistry (QSPR/QSAR), but this paper focuses primarily on abstract geometric objects. Future work would involve applying BDM to large-scale biological or chemical networks.
Note: This summary is based on the paper "Symmetry and Algorithmic Complexity of Polyominoes and Polyhedral Graphs" by Zenil et al. (2018).
Summary updated