💻 computer science

Formalizing Abstract Simplicial Complexes & Stellar Subdivisions in Lean

This paper presents the first formalization in the Lean proof assistant of abstract simplicial complexes and stellar subdivisions, providing a purely combinatorial framework that defines morphisms, operations like links and joins, and proves new identities regarding their interactions, including results previously absent from standard literature.

Original authors: Garett Cunningham, Daniel Zach, Stefan Friedl

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Garett Cunningham, Daniel Zach, Stefan Friedl

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, invisible box of LEGO bricks. In the world of math, these bricks are called simplicial complexes. Usually, when mathematicians build with them, they insist on a very strict rule: every brick must sit perfectly on a flat, 3D table (like a real table in your kitchen). They have to measure exactly how the bricks glue together in that physical space.

But here's the twist: the authors of this paper, Garett, Daniel, and Stefan, decided to throw the table out the window. They asked, "What if we just care about which bricks are connected to which, without worrying about the table?" They built a new, purely digital version of these structures called Abstract Simplicial Complexes. Think of it like a recipe card that lists ingredients and how they mix, without needing a physical kitchen to cook them. This makes the math much lighter and easier to carry around.

The Big Adventure: The "Stellar" Makeover
The main event of their paper is a specific trick they call a stellar subdivision. Imagine you have a LEGO tower, and you want to make it look more detailed without changing its overall shape (like turning a smooth sphere into a bumpy one that still feels like a sphere).

Here is how they do it in their digital world:

You pick a specific face (a flat side) of your LEGO structure.
You magically remove the "inside" of that face.
You drop a brand-new, magical LEGO brick right in the middle of the hole (this is the "barycenter").
You connect this new brick to every edge of the hole, filling in the gaps.

The result is a more complex structure that is mathematically "equivalent" to the old one. The authors call this a stellar move. They proved a series of identities showing how these moves interact with other operations, like "joins" (gluing shapes together). While they didn't prove the full theorem that any two shapes of the same type can be transformed into each other using these moves, they laid the essential groundwork for Pachner's theorem. That famous theorem—which says you can turn a coffee mug into a donut just by rearranging the LEGO bricks without tearing them apart—is a major goal for their future work, building on the solid foundation they established here.

The "Lean" Proof Assistant
Now, here is the coolest part. The authors didn't just write this on a chalkboard; they built it inside a computer program called Lean. Lean is like a super-strict robot teacher. You can't just say "it looks like it works." You have to type out every single logical step, and the robot checks it to make sure there are absolutely no holes in your logic.

This paper is the first time anyone has ever programmed stellar subdivisions into a proof assistant. It's like being the first person to teach a robot how to do a specific, complicated dance move. Before this, the dance moves were just "folklore"—things everyone knew how to do but had never written down in a way a robot could verify.

What They Didn't Do (and Why)
The paper is very clear about what it doesn't do. They explicitly ruled out the idea of keeping the "table" (the physical space) in their definitions. They argue that trying to keep the bricks glued to a specific coordinate system (like a map with X and Y numbers) makes the math too heavy and full of unnecessary baggage. They stripped that away to focus purely on the connections.

They also avoided trying to make their definitions work with a rule that says "every possible point must be a vertex." They showed that if you force that rule, it becomes a nightmare to add new bricks later because you run out of names for them. So, they stuck to a more flexible system where you only name the bricks you actually use.

How Sure Are They?
The authors are 100% sure about the things they proved. Because they used the Lean robot, they didn't just "suggest" these ideas work; they proved them. Every single identity they wrote down—like how the "link" (the neighborhood around a face) changes when you do a stellar subdivision—was checked by the computer.

For example, they proved a new identity about how these subdivisions interact with "joins" (gluing two shapes together). They showed that doing a subdivision on a joined shape is the same as joining the subdivided shapes. This wasn't just a guess; it was a rigorous, computer-verified fact. In fact, they found some of these rules had no references in standard textbooks, meaning they discovered new, verified truths that were previously just "folklore."

The Bottom Line
This paper is a foundational step. It's not the final destination, but it's the first time a robot has been taught the rules of this specific LEGO game. The authors hope that by building this solid, verified foundation, future mathematicians can use it to prove even bigger theorems about shapes and spaces, without worrying that their logic might have a hidden crack. They turned a messy, intuition-based art into a clean, verified science, one LEGO brick at a time.

Technical Summary: Formalizing Abstract Simplicial Complexes & Stellar Subdivisions in Lean

Problem Statement

The theory of simplicial complexes is fundamental to algebraic and combinatorial topology, serving as a primary tool for computing invariants such as homology and genus, and for studying homotopy types via discrete Morse theory and collapse algorithms. While classical definitions often rely on geometric embeddings in Euclidean space (using barycentric coordinates and affine independence), such approaches introduce extraneous data that complicates formal computation.

The authors identify a gap in the Lean proof assistant ecosystem: while mathlib contains various formalizations related to simplicial complexes, they lack interconnection, and there is no existing formalization of stellar subdivisions. Furthermore, existing formalizations in other assistants (Rocq, ACL2) are heavily oriented toward specific computational applications (e.g., persistent homology, Alexander duals) rather than providing a cohesive combinatorial foundation for structural theorems like those of Alexander and Pachner regarding manifold triangulations. The paper addresses the need for a purely combinatorial framework in Lean 4 that supports the rigorous verification of identities involving stellar subdivisions, links, and joins, while maintaining compatibility with existing library content and computability.

Methodology

The authors adopt a purely combinatorial framework, defining Abstract Simplicial Complexes as collections of finite sets (faces) closed under the subset relation, independent of any ambient geometric space. This approach strips away geometric conditions (affine independence, convex hull intersections) found in mathlib's SimplicialComplex structure, thereby reducing overhead and simplifying type signatures.

Key methodological choices include:

Type-Casting and Coercions: To handle operations that change the underlying vertex type (e.g., joins, subdivisions), the authors define SimplicialCoe, a structure representing injective maps on vertex sets. This allows for "lossless" relabeling without requiring global bijections on the ambient types.
Disjoint Unions for Joins: To define the join of two complexes ( $K \star L$ ) without assuming disjoint vertex sets, the authors utilize a product type $E \times k$ (where $k$ is a nontrivial semiring) to index faces, effectively creating disjoint copies of the vertex sets.
Stellar Subdivisions: The subdivision $\sigma_s K$ of a face $s$ is defined combinatorially by removing the interior of the star of $s$ and replacing it with the join of the link of $s$ , the boundary of $s$ , and a new barycenter vertex $x$ .
Formal Verification: All definitions and theorems are implemented in Lean 4. The authors prioritize preserving computability and minimizing assumptions to facilitate future integration with mathlib.

Key Contributions

The paper presents the first formalization of stellar subdivisions in any proof assistant. The specific contributions are:

Formalization of Abstract Simplicial Complexes:
- Definition of the core structure AbstractSimplicialComplex and its conversion to/from geometric SimplicialComplex instances.
- Formalization of morphisms (SimplicialMap), isomorphisms (SimplicialIso), and coercions (SimplicialCoe).
- Implementation of standard operations: unions, intersections, subcomplexes, and dimension calculations.
Formalization of Subcomplexes and Operations:
- Rigorous definitions and proofs of properties for links ($Lk(K, s)$), face boundaries ( $\partial s$ ), stars ($St(K, s)$), star complements, cones, and joins ( $K \star L$ ).
- Proof of distributive laws, associativity, and commutativity (up to isomorphism/coercion) for joins.
- Establishment of identities showing how these operations interact with isomorphisms and coercions.
Formalization of Stellar Subdivisions:
- Definition of the stellar subdivision $\sigma_s K$ and the stellar weld (the inverse operation).
- Definition of stellar equivalence ( $K \cong_{st} L$ ) as the transitive closure of stellar moves.
- Proof that stellar equivalence is preserved under injective type-casting (Theorem 3.2), ensuring that the equivalence relation is robust against changes in vertex labeling.
New Theorems and Identities:
- Derivation of identities describing the interaction between stellar subdivisions and links. Notably, Theorem 3.9 establishes that for a face $t$ in the link of the subdivided face, the link of $t$ in the subdivided complex is the stellar subdivision of the original link: $Lk(\sigma_s K, t) = \sigma_{s \setminus t}(Lk(K, t))$ .
- The authors note that this specific identity, along with several others regarding the "anticommutativity" of links and subdivisions, has no standard reference in the literature and was derived during the formalization process.

Results

The formalization successfully verifies a suite of identities commonly used in the study of triangulated manifolds:

Link Preservation: If a face $t$ lies outside the subdivided star, its link remains unchanged ( $Lk(\sigma_s K, t) = Lk(K, t)$ ).
Join Compatibility: Stellar subdivisions distribute over joins in specific ways, e.g., $(\sigma_s K) \star L = \sigma_{s \sqcup \emptyset}(K \star L)$ .
Equivalence Preservation: Stellar equivalence is preserved under simplicial isomorphisms and injective type-casting, provided the target type has sufficient "room" for new barycenter labels.
Code Volume: The project currently comprises approximately 14,000 lines of Lean code, covering definitions, utility lemmas, and proofs.

Significance and Claims

The authors position this work as a foundational step toward the formalization of Alexander's and Pachner's theorems, which state that triangulations of manifolds are homeomorphic if and only if they are related by a sequence of stellar (or bistellar) moves.

First of its Kind: The paper claims to be the first formalization of stellar subdivisions in any proof assistant.
Bridging Theory and Computation: By adopting a combinatorial framework, the work aims to make the theory of simplicial complexes more amenable to computational techniques and algorithmic applications (e.g., in Topological Data Analysis and software like Regina).
Cataloging Folklore: The authors argue that many technical identities in combinatorial topology have drifted into "folklore" status due to the tediousness of their proofs. This formalization serves to catalog and verify these results, ensuring their logical gaps are filled.
Modest Scope: The authors explicitly state that this is "initial legwork." They do not claim to have formalized Pachner's theorems yet but have provided the necessary infrastructure (subdivisions, links, joins, and equivalence relations) to do so. They also acknowledge that while they have isolated the combinatorial aspects, future work is required to fully integrate these results with the geometric SimplicialComplex definitions in mathlib and to handle the complexities of total complexes (where every singleton is a face).

The work emphasizes a design philosophy that prioritizes computability and compatibility with mathlib, aiming to create a streamlined foundation for future developments in combinatorial topology within the Lean ecosystem.